View Single Post
 2016-12-29, 13:47 #1 Nick     Dec 2012 The Netherlands 68716 Posts Basic Number Theory 14: a first look at groups Modern Number Theory makes intensive use of several abstract algebraic concepts and we are going to take a first look at one: the idea of a group. Groups can be useful in any situation involving symmetry. Let $$z,w$$ be complex numbers. Then $$z=x+yi$$ and $$w=u+vi$$ for some real numbers $$u,v,x,y$$ and we saw that we can visualize $$z$$ and $$w$$ by identifying them with points in a plane (namely the points whose co-ordinates are $$(x,y)$$ and $$(u,v)$$ respectively). We defined $$|z|=\sqrt{x^2+y^2}$$, called the modulus or absolute value of $$z$$, which gives the distance between the points for $$z$$ and 0 in the plane. Similarly, we saw that $$|z-w|=\sqrt{(x-u)^2+(y-v)^2}$$ gives the distance between $$z$$ and $$w$$. A function $$f:\mathbb{C}\rightarrow\mathbb{C}$$ is called an isometry if it preserves distance, i.e. for all complex numbers $$z,w$$, $$|f(z)-f(w)|=|z-w|$$. Examples 1. Fix a complex number $$t$$ and let $$f:\mathbb{C}\rightarrow\mathbb{C}$$ be the function $$z\mapsto z+t$$. Geometrically, this function is a translation, i.e. it shifts all points of the plane by the same distance in the same direction (for example, if $$t=3+2i$$ then $$f$$ shifts each point of the plane by 3 to the right and 2 up) So $$f$$ preserves distance, and algebraically we can prove this: for any complex numbers $$z,w$$, $$|f(z)-f(w)|=|(z+t)-(w+t)|=|z-w|$$. Thus $$f$$ is an isometry. 2. Fix a complex number $$t$$ with $$|t|=1$$, and let $$f:\mathbb{C}\rightarrow\mathbb{C}$$ be the function $$z\mapsto tz$$. As $$|t|=1$$, there exists a real number $$\alpha$$ such that $$t=\cos(\alpha)+i\sin(\alpha)$$ and, geometrically, this function is a rotation, turning each point of the plane through the angle $$\alpha$$ anticlockwise around 0. (This follows from proposition 47.) Such a rotation preserves distance, and we can prove this algebraically: for any complex numbers $$z,w$$, proposition 45(ii) gives $$|f(z)-f(w)|=|tz-tw|=|t|\cdot |z-w|=|z-w|$$ as $$|t|=1$$. Hence $$f$$ is again an isometry. 3. Let $$z=x+yi$$ be a complex number (where $$x,y\in\mathbb{R}$$) and recall that its complex conjugate $$\bar{z}$$ is the complex number $$x-yi$$. In particular, $$|\bar{z}|=\sqrt{x^2+(-y)^2}=\sqrt{x^2+y^2}=|z|$$. Thus, for all complex numbers $$z,w$$, we have by proposition 43 that $$|\bar{z}-\bar{w}|=|\overline{z-w}|=|z-w|$$ so the function $$f:\mathbb{C}\rightarrow\mathbb{C}$$ given by $$z\mapsto\bar{z}$$ is an isometry. Geometrically, this function is a reflection in the $$x$$-axis (if $$z=x+yi$$ then $$z$$ corresponds with the point $$(x,y)$$ while $$\bar{z}$$ corresponds with $$(x,-y)$$). 4. Let $$f,g:\mathbb{C}\rightarrow\mathbb{C}$$ be isometries. Then their composition $$g\circ f$$ (i.e. $$g$$ after $$f$$) is also an isometry since, for all $$z,w\in\mathbb{C}$$, $$|(g\circ f)(z)-(g\circ f)(w)|=|g(f(z))-g(f(w))|=|f(z)-f(w)|=|z-w|$$. Thus any combination of reflections in the $$x$$-axis, rotations about 0 and translations is an isometry of the plane. But does this give us all isometries? And can we "factorize" an isometry uniquely into such a composition? Let us find out. Proposition 67 Let $$f:\mathbb{C}\rightarrow\mathbb{C}$$ be an isometry such that $$f(0)=0$$, $$f(1)=1$$ and $$f(i)=i$$. Then $$f$$ is the identity function $$i_\mathbb{C}$$, i.e. for all $$z\in\mathbb{C}$$, $$f(z)=z$$. proof Take any $$z\in\mathbb{C}$$ and let $$w=f(z)\in\mathbb{C}$$. Then $$z=x+yi$$ and $$w=u+vi$$ for some $$u,v,x,y\in\mathbb{R}$$. As $$f$$ is an isometry, we have $$|f(z)-f(0)|=|z-0|$$ and therefore $$|f(z)-f(0)|^2=|z-0|^2$$. And $$f(z)=w$$, $$f(0)=0$$ so $$|w|^2=|z|^2$$ i.e. $u^2+v^2=x^2+y^2.$ Similarly, $$|f(z)-f(1)|^2=|z-1|^2$$ with $$f(1)=1$$ so $(u-1)^2+v^2=(x-1)^2+y^2$ Subtracting from the previous equation, we see that $$2u-1=2x-1$$ hence $$u=x$$. In the same way, $$|f(z)-f(i)|^2=|z-i|^2$$ with $$f(i)=i$$ so $u^2+(v-1)^2=x^2+(y-1)^2$ and, subtracting from the first equation, we see that $$2v-1=2y-1$$ hence $$v=y$$. Thus $$f(z)=w=z$$. ∎ Theorem 68 Let $$f:\mathbb{C}\rightarrow\mathbb{C}$$ be an isometry. Then $$f$$ is a reflection in the $$x$$-axis followed by a rotation about 0 followed by a translation, with the possible omission of some of these steps. Moreover, this decomposition of $$f$$ is unique. proof EXISTENCE Let $$w=f(0)$$ and define $$g:\mathbb{C}\rightarrow\mathbb{C}$$ by $$z\mapsto f(z)-w$$. Then $$g$$ is an isometry with $$g(0)=0$$. Let $$t=g(1)$$. Then $$|t|=|g(1)-g(0)|=|1-0|=1$$ so the function $$h:\mathbb{C}\rightarrow\mathbb{C}$$ given by $$z\mapsto \frac{g(z)}{t}$$ is also an isometry, with $$h(0)=0$$ and $$h(1)=1$$. Now $$h(i)=u+vi$$ for some $$u,v\in\mathbb{R}$$, with $$u^2+v^2=|h(i)|^2=|h(i)-h(0)|^2=|i-0|^2=1$$ and $$(u-1)^2+v^2=|h(i)-1|^2=|h(i)-h(1)|^2=|i-1|^2=2$$. Subtracting, we see that $$2u-1=-1$$ so $$u=0$$ and $$v^2=1$$ so $$v=\pm 1$$. If $$v=1$$ then $$h(i)=i$$ and, by proposition 67, $$h$$ is the identity function. Thus, for all $$z\in\mathbb{C}$$, $$z=\frac{f(z)-w}{t}$$ so $$f(z)=zt+w$$ with $$|t|=1$$, making $$f$$ a rotation about 0 followed by a translation. Otherwise, $$v=-1$$ so $$h(i)=-i$$. Let $$\bar{h}:\mathbb{C}\rightarrow\mathbb{C}$$ be the function $$z\mapsto\overline{h(z)}$$. Then $$\bar{h}(0)=0$$, $$\bar{h}(1)=1$$ and $$\bar{h}(i)=i$$ so $$\bar{h}$$ is the identity function (again by propostion 67). Thus, for all $$z\in\mathbb{C}$$, $$z$$ is the complex conjugate of $$\frac{f(z)-w}{t}$$ so $$f(z)=\bar{z}t+w$$ with $$|t|=1$$, making $$f$$ a reflection in the $$x$$-axis followed by a rotation about 0 followed by a translation. UNIQUENESS Take any complex numbers $$t,w,t',w'$$ with $$|t|=1=|t'|$$ and let $$h:\mathbb{C}\rightarrow\mathbb{C}$$ be either the identity function $$z\mapsto z$$ or complex conjugation $$z\mapsto\bar{z}$$, and similarly for $$h'$$. Suppose for all $$z\in\mathbb{C}$$ that $$f(z)=h(z)t+w$$ and also that $$f(z)=h'(z)t'+w'$$. Then $$w'=f(0)=w$$ so also $$t'=f(1)-w'=f(1)-w=t$$. And $$t\neq 0$$ (since $$|t|=1$$) so $$h'(i)=\frac{f(i)-w'}{t'}=\frac{f(i)-w}{t}=h(i)$$ hence $$h'=h$$. ∎ Corollary 69 Let $$f:\mathbb{C}\rightarrow\mathbb{C}$$ be an isometry. Then $$f$$ is bijective. proof Suppose first that $$f$$ is a translation. Then there exists $$w\in\mathbb{C}$$ such that, for all $$z\in\mathbb{C}$$, $$f(z)=z+w$$. Let $$g:\mathbb{C}\rightarrow\mathbb{C}$$ be the function $$z\mapsto z-w$$. Then for all $$z\in\mathbb{C}$$ we have $$g(f(z))=z$$ and $$f(g(z))=z$$ so $$f$$ has an inverse $$g$$ and therefore $$f$$ is bijective (by proposition 25). Suppose instead that $$f$$ is a rotation about 0. Then there exists $$t\in\mathbb{C}$$ with $$|t|=1$$ such that, for all $$z\in\mathbb{C}$$, $$f(z)=zt$$. In particular, $$t\neq 0$$, so $$f$$ has an inverse $$g:\mathbb{C}\rightarrow\mathbb{C}$$ given by $$z\mapsto \frac{z}{t}$$ and therefore $$f$$ is bijective. Suppose now for all $$z\in\mathbb{C}$$ that $$f(z)=\bar{z}$$. Then $$f$$ is its own inverse, so again $$f$$ is bijective. In the general case, by theorem 68, $$f$$ is a composition of such functions. Thus $$f$$ is a composition of bijections so $$f$$ is also a bijection (exercise 29). ∎ Notation Let $$A,B$$ be sets and $$f:A\rightarrow B$$ a function. For any subset $$C\subset A$$, we write $$f(C)$$ for the set $$\{f(c):c\in C\}$$, which is a subset of $$B$$. Let $$S\subset\mathbb{C}$$. A symmetry operation of $$S$$ is an isometry $$f:\mathbb{C}\rightarrow\mathbb{C}$$ such that $$f(S)=S$$, i.e. the images of the points in $$S$$ give precisely all the points of $$S$$ again. Example Let $$w=\frac{1}{2}(-1+i\sqrt{3})$$ and define $T=\{a\cdot 1+bw+cw^2:a,b,c\mbox{ non-negative real numbers with }a+b+c=1\}.$ Then the complex numbers in $$T$$ give the points of the solid equilateral triangle in the plane whose vertices are $$1,w$$ and $$w^2$$. Let $$\rho:\mathbb{C}\rightarrow\mathbb{C}$$ be the isometry which rotates all points through an angle of $$\frac{2\pi}{3}$$ (i.e. 120°) anticlockwise about 0. (Algebraically, this is the function given by $$\rho(z)=wz$$.) The triangle looks exactly the same after this rotation as it did before, because of its symmetry. Thus $$\rho(T)=T$$ and $$\rho$$ is a symmetry operation of $$T$$. The isometry $$\rho\circ\rho$$, which we shall write simply as $$\rho^2$$, is also a symmetry operation of $$T$$, rotating all points through an angle of $$\frac{4\pi}{3}$$ (i.e. 240°) anticlockwise, or (equivalently) through $$\frac{2\pi}{3}$$ clockwise about 0. And the isometry $$\rho^3=\rho\circ\rho\circ\rho$$ is also a symmetry operation of $$T$$, but this is just the identity function $$i_\mathbb{C}$$ (rotating all points through an angle of $$2\pi$$, i.e. 360°, has the same effect as doing nothing). Let $$\sigma:\mathbb{C}\rightarrow\mathbb{C}$$ be the isometry which reflects all points in the $$x$$-axis. (Algebraically, this is the function given by $$\sigma(z)=\bar{z}$$.) For example, $$\sigma(w)=w^2$$, $$\sigma(w^2)=w$$ and $$\sigma(1)=1$$. Then $$\sigma(T)=T$$ so $$\sigma$$ is another symmetry operation of $$T$$. In this case, $$\sigma^2=i_\mathbb{C}$$ (flipping the triangle over twice has the same effect as doing nothing). Composing $$\rho$$ with $$\sigma$$, however, gives us two extra symmetry operations of $$T$$, $$\rho\circ\sigma$$, which we shall write simply as $$\rho\sigma$$, and $$\rho^2\sigma$$. We now have 6 distinct symmetry operations of $$T$$, namely $$i_\mathbb{C},\rho,\rho^2,\sigma,\rho\sigma,\rho^2\sigma$$. Other reflections, rotations and/or translations do not yield a symmetry operation of $$T$$, so we have found all of them. In particular, any composition of these 6 functions must give one of the 6 functions again, so we can draw up a composition table: $\begin{array}{l|llllll} & i_\mathbb{C} & \rho & \rho^2 & \sigma & \rho\sigma & \rho^2\sigma \\ \hline i_\mathbb{C} & i_\mathbb{C} & \rho & \rho^2 & \sigma & \rho\sigma & \rho^2\sigma \\ \rho & \rho & \rho^2 & i_\mathbb{C} & \rho\sigma & \rho^2\sigma & \sigma \\ \rho^2 & \rho^2 & i_\mathbb{C} & \rho & \rho^2\sigma & \sigma & \rho\sigma \\ \sigma & \sigma & \rho^2\sigma & \rho\sigma & i_\mathbb{C} & \rho^2 & \rho \\ \rho\sigma & \rho\sigma & \sigma & \rho^2\sigma & \rho & i_\mathbb{C} & \rho^2 \\ \rho^2\sigma & \rho^2\sigma & \rho\sigma & \sigma & \rho^2 & \rho & i_\mathbb{C} \end{array}$ For example, the entry in this table on the row for $$\sigma$$ and in the column for $$\rho$$ is $$\rho^2\sigma$$ because $$\sigma\rho=\rho^2\sigma$$ (rotating the triangle and then flipping it over has the same effect as flipping it over and then rotating it twice). We have shown that any isometry of the plane is a bijection. More abstractly, we can look at the bijections from any set to itself. Let $$X$$ be a set. A permutation of $$X$$ is a bijective function $$f:X\rightarrow X$$. We write $$S(X)$$ for the set of all permutations of $$X$$. If $$X$$ is the set $$\{1,2,3,\ldots,n\}$$ for some non-negative integer $$n$$, then we write $$S(X)$$ simply as $$S_n$$. Example Let $$X=\{1,2,3\}$$. Then there are $$3!=6$$ permutations of $$X$$: One of them is just the identity function $$i_X$$, sending each element of $$X$$ to itself. We write $$(1\ 2\ 3)$$ for the permutation which sends 1 to 2, 2 to 3 and 3 back to 1. Similarly, $$(1\ 3\ 2)$$ is the permutation sending 1 to 3, 3 to 2 and 2 back to 1. By agreeing that any element of $$X$$ which we do not mention gets sent to itself, we can use this notation for the other 3 permutations, too. Thus $$(1\ 2)$$ is the permutation sending 1 to 2, 2 back to 1 (and 3 to 3), and similarly for $$(1\ 3)$$ and $$(2\ 3)$$. With this cycle notation, we omit the "$$\circ$$" symbol when composing functions. For example, $$(1\ 3)(1\ 2)$$ means $$(1\ 3)$$ after $$(1\ 2)$$, which therefore sends 1 to 2, 2 to 3 (via 1) and 3 to 1, giving $$(1\ 2\ 3)$$. Just as with symmetry operations, we can construct a composition table. $\begin{array}{c|cccccc} & i_X & (1\ 2\ 3) & (1\ 3\ 2) & (1\ 2) & (1\ 3) & (2\ 3) \\ \hline i_X & i_X & (1\ 2\ 3) & (1\ 3\ 2) & (1\ 2) & (1\ 3) & (2\ 3) \\ (1\ 2\ 3) & (1\ 2\ 3) & (1\ 3\ 2) & i_X & (1\ 3) & (2\ 3) & (1\ 2) \\ (1\ 3\ 2) & (1\ 3\ 2) & i_X & (1\ 2\ 3) & (2\ 3) & (1\ 2) & (1\ 3) \\ (1\ 2) & (1\ 2) & (2\ 3) & (1\ 3) & i_X & (1\ 3\ 2) & (1\ 2\ 3) \\ (1\ 3) & (1\ 3) & (1\ 2) & (2\ 3) & (1\ 2\ 3) & i_X & (1\ 3\ 2) \\ (2\ 3) & (2\ 3) & (1\ 3) & (1\ 2) & (1\ 3\ 2) & (1\ 2\ 3) & i_X \end{array}$ For example, the entry in this table on the row for $$(1\ 2)$$ and in the column for $$(1\ 2\ 3)$$ is $$(2\ 3)$$ because $$(1\ 2)(1\ 2\ 3)=(2\ 3)$$. If we compare this table with the table of symmetry operations of the triangle, we see that they have the same pattern. For example, the permutation $$(1\ 2\ 3)$$ occurs in the above table at exactly the same positions where $$\rho$$ occurs in the previous one. This suggests that what we should really be studying are these underlying patterns, and that is what groups are about. Let $$S$$ be a set (of elements - we make no assumptions about what they actually are). A binary operation on $$S$$ is a function from $$S\times S$$ to $$S$$, i.e. a method which takes a pair of elements of $$S$$ and combines them in some way, resulting in an element of $$S$$ again. For example, addition is a binary operation on the set $$\mathbb{R}$$ of all real numbers: if we choose a pair of real numbers (possibly the same number twice), we can always add them together, and their sum is also a real number (possibly equal to one of the original two). In the same way, multiplication is a binary operation on $$\mathbb{R}$$, and also gives us a binary operation on $$\mathbb{R}\setminus\{0\}$$: for any real numbers $$x,y$$, their product $$xy$$ is a real number, and if $$x$$ and $$y$$ are both non-zero then so is $$xy$$. Let * be a binary operation on $$S$$. For elements $$x,y\in S$$, we shall write $$*(x,y)$$ as $$(x*y)$$, or simply $$x*y$$ if leaving out the brackets does not lead to ambiguity (just as we are used to with addition and multiplication). We say that * is commutative if, for all $$x,y\in S$$, $$x*y=y*x$$. We say that * is associative if, for all $$x,y,z\in S$$, $$(x*y)*z=x*(y*z)$$. Example Function composition is a binary operation on the set of all symmetry operations of the equilateral triangle. It is associative (we proved this in proposition 24) but not commutative, as we see from the first composition table above: $$\sigma\rho=\rho^2\sigma\neq\rho\sigma$$. Proposition 70 Let * be an associative binary operation on a set $$S$$, $$n\geq 3$$ an integer and $$s_1,s_2,\ldots,s_n\in S$$. Then $$s_1*s_2*\ldots *s_n$$ has the same value no matter where we place the brackets. proof Induction on $$n$$. In the case $$n=3$$, as * is associative, we immediately have $$(s_1*s_2)*s_3=s_1*(s_2*s_3)$$. Take any integer $$N>3$$ and suppose the proposition holds for all $$n2$$ then this group is not abelian. The more mathematics we learn, the more examples of groups we discover. Notation To prove a theorem for all groups, we will need to work with an unspecified group, and in that situation we will use multiplicative notation from now on, i.e. we shall write $$x*y$$ as $$x\cdot y$$ or simply $$xy$$, use 1 (instead of $$e$$) to denote the neutral element and, for each element $$x$$, write $$x^{-1}$$ for the inverse of $$x$$ under the group's binary operation. Proposition 73 Let $$G$$ be a group (i.e. $$G$$ is a set which comes with a binary operation satisfying the 3 conditions listed above). Then, for all $$x,y,z\in G$$, if $$xz=yz$$ or $$zx=zy$$ then $$x=y$$. proof Take any $$x,y,z\in G$$. If $$xz=yz$$ then $x=x\cdot 1=x(zz^{-1})=(xz)z^{-1}=(yz)z^{-1}=y(zz^{-1})=y\cdot 1=y.$ Similarly, if $$zx=zy$$ then $x=1\cdot x=(z^{-1}z)x=z^{-1}(zx)=z^{-1}(zy)=(z^{-1}z)y=1\cdot y=y.$ ∎ In a group which is not abelian, we may have $$xz=zy$$ but $$x\neq y$$, however. In $$S_3$$, for example, $$(1\ 3\ 2)(1\ 2)=(2\ 3)=(1\ 2)(1\ 2\ 3)$$ but $$(1\ 3\ 2)\neq (1\ 2\ 3)$$. Exercises 63. Let $$f:\mathbb{C}\rightarrow\mathbb{C}$$ be the isometry which rotates each point through a right angle anticlockwise about the point given by $$1+i$$. By theorem 68, the same effect can be obtained using a rotation about 0 instead, followed by a translation. What is the translation? 64. Find all complex numbers $$z$$ for which $$z^2=\bar{z}$$. 65. Let $$f:\mathbb{C}\rightarrow\mathbb{C}$$ be an isometry for which $$f(0)=0$$. Show for all complex numbers $$z,w$$ and all real numbers $$r$$ that $$f(z+w)=f(z)+f(w)$$ and $$f(rz)=rf(z)$$. 66. Let $$f:\mathbb{C}\rightarrow\mathbb{C}$$ be an isometry. Show for all positive integers $$n$$ and all complex numbers $$z_1,z_2,\ldots,z_n$$ that $$f(\frac{z_1+z_2+\ldots+z_n}{n})=\frac{f(z_1)+f(z_2)+\ldots +f(z_n)}{n}$$. 67. Let $$G$$ be a group and $$g\in G$$. Prove that $$(g^{-1})^{-1}=g$$. 68. Construct the composition table for all symmetry operations of a rectangle (which is not square). Compare it with the multiplication table for the unit group of the integers modulo 8.