Presentation of a group





In mathematics, one method of defining a group is by a presentation. One specifies a set S of generators so that every element of the group can be written as a product of powers of some of these generators, and a set R of relations among those generators. We then say G has presentation


S∣R⟩.{displaystyle langle Smid Rrangle .}langle Smid Rrangle .

Informally, G has the above presentation if it is the "freest group" generated by S subject only to the relations R. Formally, the group G is said to have the above presentation if it is isomorphic to the quotient of a free group on S by the normal subgroup generated by the relations R.


As a simple example, the cyclic group of order n has the presentation


a∣an=1⟩.{displaystyle langle amid a^{n}=1rangle .}langle amid a^{n}=1rangle .

where 1 is the group identity. This may be written equivalently as


a∣an⟩,{displaystyle langle amid a^{n}rangle ,}langle amid a^{n}rangle ,

since terms that do not include an equals sign are taken to be equal to the group identity. Such terms are called relators, distinguishing them from the relations that include an equals sign.


Every group has a presentation, and in fact many different presentations; a presentation is often the most compact way of describing the structure of the group.


A closely related but different concept is that of an absolute presentation of a group.




Contents






  • 1 Background


  • 2 Notation


  • 3 Definition


  • 4 Finitely presented groups


  • 5 Recursively presented groups


  • 6 Examples


    • 6.1 History


    • 6.2 Common examples




  • 7 Some theorems


    • 7.1 Novikov–Boone theorem




  • 8 Constructions


  • 9 Deficiency


  • 10 Geometric group theory


  • 11 See also


  • 12 Notes


  • 13 References


  • 14 External links





Background


A free group on a set S is a group where each element can be uniquely described as a finite length product of the form:


s1a1s2a2⋯snan{displaystyle s_{1}^{a_{1}}s_{2}^{a_{2}}cdots s_{n}^{a_{n}}}{displaystyle s_{1}^{a_{1}}s_{2}^{a_{2}}cdots s_{n}^{a_{n}}}

where the si are elements of S, adjacent si are distinct, and ai are non-zero integers (but n may be zero). In less formal terms, the group consists of words in the generators and their inverses, subject only to canceling a generator with an adjacent occurrence of its inverse.


If G is any group, and S is a generating subset of G, then every element of G is also of the above form; but in general, these products will not uniquely describe an element of G.


For example, the dihedral group D8 of order sixteen can be generated by a rotation, r, of order 8; and a flip, f, of order 2; and certainly any element of D8 is a product of r's and f's.


However, we have, for example, rfr = f, r7 = r−1, etc., so such products are not unique in D8. Each such product equivalence can be expressed as an equality to the identity, such as




rfrf = 1


r8 = 1


f2 = 1.


Informally, we can consider these products on the left hand side as being elements of the free group F = <r, f>, and can consider the subgroup R of F which is generated by these strings; each of which would also be equivalent to 1 when considered as products in D8.


If we then let N be the subgroup of F generated by all conjugates x−1Rx of R, then it is straightforward to show that every element of N is a finite product x1−1r1x1{displaystyle cdots }cdots xm−1rm xm of members of such conjugates. It follows that
N is a normal subgroup of F; and that each element of N, when considered as a product in D8, will also evaluate to 1. Thus D8 is isomorphic to the quotient group F/N. We then say that D8 has presentation


r,f∣r8=1,f2=1,(rf)2=1⟩.{displaystyle langle r,fmid r^{8}=1,f^{2}=1,(rf)^{2}=1rangle .}{displaystyle langle r,fmid r^{8}=1,f^{2}=1,(rf)^{2}=1rangle .}

Here the set of generators is S = {r, f}, and the set of relations is R = {r 8 = 1, f 2 = 1, (rf )2 = 1}. We often see R abbreviated, giving the presentation


r,f∣r8=f2=(rf)2=1⟩.{displaystyle langle r,fmid r^{8}=f^{2}=(rf)^{2}=1rangle .}langle r,fmid r^{8}=f^{2}=(rf)^{2}=1rangle .

An even shorter form drops the equality and identity signs, to list just the set of relators, which is {r 8, f 2, (rf )2}. Doing this gives the presentation


r,f∣r8,f2,(rf)2⟩.{displaystyle langle r,fmid r^{8},f^{2},(rf)^{2}rangle .}{displaystyle langle r,fmid r^{8},f^{2},(rf)^{2}rangle .}

All three presentations are equivalent.



Notation


Although the notation S|R used in this article for a presentation is now the most common, earlier writers used different variations on the same format. Such notations include:



  • S|R

  • (S|R)


  • {S;R}

  • S;R



Definition


Let S be a set and let FS be the free group on S. Let R be a set of words on S, so R naturally gives a subset of FS{displaystyle F_{S}}F_S. To form a group with presentation S∣R⟩{displaystyle langle Smid Rrangle }{displaystyle langle Smid Rrangle }, the idea is to take FS{displaystyle F_{S}}F_S quotient by the smallest normal subgroup such that each element of R gets identified with the identity. Note that R might not be a subgroup, let alone a normal subgroup of FS{displaystyle F_{S}}F_S , so we cannot take a quotient by R. The solution is to take the normal closure N of R in FS{displaystyle F_{S}}F_S . The group S∣R⟩{displaystyle langle Smid Rrangle }{displaystyle langle Smid Rrangle } is then defined as the quotient group


S∣R⟩=FS/N.{displaystyle langle Smid Rrangle =F_{S}/N.}langle Smid Rrangle =F_{S}/N.

The elements of S are called the generators of S∣R⟩{displaystyle langle Smid Rrangle }{displaystyle langle Smid Rrangle } and the elements of R are called the relators. A group G is said to have the presentation S∣R⟩{displaystyle langle Smid Rrangle }{displaystyle langle Smid Rrangle } if G is isomorphic to S∣R⟩{displaystyle langle Smid Rrangle }{displaystyle langle Smid Rrangle }.


It is a common practice to write relators in the form x=y{displaystyle x=y}x=y where x and y are words on S. What this means is that y−1x∈R{displaystyle y^{-1}xin R}{displaystyle y^{-1}xin R}. This has the intuitive meaning that the images of x and y are supposed to be equal in the quotient group. Thus e.g. rn in the list of relators is equivalent with rn=1{displaystyle r^{n}=1}{displaystyle r^{n}=1}. Another common shorthand is to write [x,y]{displaystyle [x,y]}[x,y] for a commutator xyx−1y−1{displaystyle xyx^{-1}y^{-1}}{displaystyle xyx^{-1}y^{-1}}.


For a finite group G, the multiplication table provides a presentation. We take S to be the elements gi{displaystyle g_{i}}g_{i} of G and R to be all words of the form gigjgk−1{displaystyle g_{i}g_{j}g_{k}^{-1}}g_{i}g_{j}g_{k}^{-1}, where gigj=gk {displaystyle g_{i}g_{j}=g_{k} }g_{i}g_{j}=g_{k} is an entry in the multiplication table. A presentation can then be thought of as a generalization of a multiplication table.



Finitely presented groups


A presentation is said to be finitely generated if S is finite and finitely related if R is finite. If both are finite it is said to be a finite presentation. A group is finitely generated (respectively finitely related, finitely presented) if it has a presentation that is finitely generated (respectively finitely related, a finite presentation). A group which has a finite presentation with a single relation is called a one-relator group.



Recursively presented groups


If S is indexed by a set I consisting of all the natural numbers N or a finite subset of them, then it is easy to set up a simple one to one coding (or Gödel numbering) f : FSN from the free group on S to the natural numbers, such that we can find algorithms that, given f(w), calculate w, and vice versa. We can then call a subset U of FS recursive (respectively recursively enumerable) if f(U) is recursive (respectively recursively enumerable). If S is indexed as above and R recursively enumerable, then the presentation is a recursive presentation and the corresponding group is recursively presented. This usage may seem odd, but it is possible to prove that if a group has a presentation with R recursively enumerable then it has another one with R recursive.


Every finitely presented group is recursively presented, but there are recursively presented groups that cannot be finitely presented. However a theorem of Graham Higman states that a finitely generated group has a recursive presentation if and only if it can be embedded in a finitely presented group. From this we can deduce that there are (up to isomorphism) only countably many finitely generated recursively presented groups. Bernhard Neumann has shown that there are uncountably many non-isomorphic two generator groups. Therefore, there are finitely generated groups that cannot be recursively presented.



Examples



History


One of the earliest presentations of a group by generators and relations was given by the Irish mathematician William Rowan Hamilton in 1856, in his icosian calculus – a presentation of the icosahedral group.[1]


The first systematic study was given by Walther von Dyck, student of Felix Klein, in the early 1880s, laying the foundations for combinatorial group theory.[2]



Common examples


The following table lists some examples of presentations for commonly studied groups. Note that in each case there are many other presentations that are possible. The presentation listed is not necessarily the most efficient one possible.












































































































Group Presentation Comments
the free group on S

S∣{displaystyle langle Smid varnothing rangle }langle Smid varnothing rangle
A free group is "free" in the sense that it is subject to no relations.
Cn, the cyclic group of order n

a∣an⟩{displaystyle langle amid a^{n}rangle }langle amid a^{n}rangle

Dn, the dihedral group of order 2n

r,f∣rn,f2,(rf)2⟩{displaystyle langle r,fmid r^{n},f^{2},(rf)^{2}rangle }langle r,fmid r^{n},f^{2},(rf)^{2}rangle
Here r represents a rotation and f a reflection
D, the infinite dihedral group

r,f∣f2,(rf)2⟩{displaystyle langle r,fmid f^{2},(rf)^{2}rangle }langle r,fmid f^{2},(rf)^{2}rangle

Dicn, the dicyclic group

r,f∣r2n,rn=f2,frf−1=r−1⟩{displaystyle langle r,fmid r^{2n},r^{n}=f^{2},frf^{-1}=r^{-1}rangle }langle r,fmid r^{2n},r^{n}=f^{2},frf^{-1}=r^{-1}rangle
The quaternion group is a special case when n = 2

Z × Z

x,y∣xy=yx⟩{displaystyle langle x,ymid xy=yxrangle }langle x,ymid xy=yxrangle


Z/mZ × Z/nZ

x,y∣xm,yn,xy=yx⟩{displaystyle langle x,ymid x^{m},y^{n},xy=yxrangle }langle x,ymid x^{m},y^{n},xy=yxrangle

the free abelian group on S

S∣R⟩{displaystyle langle Smid Rrangle }langle Smid Rrangle where R is the set of all commutators of elements of S

Sn, the symmetric group on n symbols
generators: σ1,…n−1{displaystyle sigma _{1},ldots ,sigma _{n-1}}sigma _{1},ldots ,sigma _{n-1}
relations:


  • σi2=1{displaystyle sigma _{i}^{2}=1}sigma _{i}^{2}=1,


  • σj=σi if j≠1{displaystyle sigma _{i}sigma _{j}=sigma _{j}sigma _{i}{mbox{ if }}jneq ipm 1}sigma _{i}sigma _{j}=sigma _{j}sigma _{i}{mbox{ if }}jneq ipm 1,

  • σi+1σi=σi+1σi+1 {displaystyle sigma _{i}sigma _{i+1}sigma _{i}=sigma _{i+1}sigma _{i}sigma _{i+1} }sigma _{i}sigma _{i+1}sigma _{i}=sigma _{i+1}sigma _{i}sigma _{i+1}


The last set of relations can be transformed into


  • i+1)3=1 {displaystyle {(sigma _{i}sigma _{i+1}})^{3}=1 }{(sigma _{i}sigma _{i+1}})^{3}=1

using σi2=1{displaystyle sigma _{i}^{2}=1}sigma _{i}^{2}=1.


Here σi is the permutation that swaps the ith element with the i+1 one. The product σiσi+1 is a 3-cycle on the set {i, i+1, i+2}.
Bn, the braid groups
generators: σ1,…n−1{displaystyle sigma _{1},ldots ,sigma _{n-1}}sigma _{1},ldots ,sigma _{n-1}

relations:




  • σj=σi if j≠1{displaystyle sigma _{i}sigma _{j}=sigma _{j}sigma _{i}{mbox{ if }}jneq ipm 1}sigma _{i}sigma _{j}=sigma _{j}sigma _{i}{mbox{ if }}jneq ipm 1,

  • σi+1σi=σi+1σi+1 {displaystyle sigma _{i}sigma _{i+1}sigma _{i}=sigma _{i+1}sigma _{i}sigma _{i+1} }sigma _{i}sigma _{i+1}sigma _{i}=sigma _{i+1}sigma _{i}sigma _{i+1}


Note the similarity with the symmetric group; the only difference is the removal of the relation σi2=1{displaystyle sigma _{i}^{2}=1}sigma _{i}^{2}=1.

T ≅ A4, the tetrahedral group

s,t∣s2,t3,(st)3⟩{displaystyle langle s,tmid s^{2},t^{3},(st)^{3}rangle }langle s,tmid s^{2},t^{3},(st)^{3}rangle


O ≅ S4, the octahedral group

s,t∣s2,t3,(st)4⟩{displaystyle langle s,tmid s^{2},t^{3},(st)^{4}rangle }langle s,tmid s^{2},t^{3},(st)^{4}rangle


I ≅ A5, the icosahedral group

s,t∣s2,t3,(st)5⟩{displaystyle langle s,tmid s^{2},t^{3},(st)^{5}rangle }langle s,tmid s^{2},t^{3},(st)^{5}rangle

Q8, the quaternion group

i,j∣jij=i,iji=j⟩{displaystyle langle i,jmid jij=i,iji=jrangle ,}langle i,jmid jij=i,iji=jrangle ,
For an alternative presentation see Dicn above.
SL(2, Z)

a,b∣aba=bab,(aba)4⟩{displaystyle langle a,bmid aba=bab,(aba)^{4}rangle }langle a,bmid aba=bab,(aba)^{4}rangle
topologically you can visualize a and b as Dehn twists on the torus
GL(2, Z)

a,b,j∣aba=bab,(aba)4,j2,(ja)2,(jb)2⟩{displaystyle langle a,b,jmid aba=bab,(aba)^{4},j^{2},(ja)^{2},(jb)^{2}rangle }langle a,b,jmid aba=bab,(aba)^{4},j^{2},(ja)^{2},(jb)^{2}rangle
nontrivial Z/2Z – group extension of SL(2, Z)
PSL(2, Z), the modular group

a,b∣a2,b3⟩{displaystyle langle a,bmid a^{2},b^{3}rangle }langle a,bmid a^{2},b^{3}rangle
PSL(2, Z) is the free product of the cyclic groups Z/2Z and Z/3Z

Heisenberg group

x,y,z∣z=xyx−1y−1,xz=zx,yz=zy⟩{displaystyle langle x,y,zmid z=xyx^{-1}y^{-1},xz=zx,yz=zyrangle }langle x,y,zmid z=xyx^{-1}y^{-1},xz=zx,yz=zyrangle

BS(m, n), the Baumslag–Solitar groups

a,b∣an=bamb−1⟩{displaystyle langle a,bmid a^{n}=ba^{m}b^{-1}rangle }langle a,bmid a^{n}=ba^{m}b^{-1}rangle


Tits group

a,b∣a2,b3,(ab)13,[a,b]5,[a,bab]4,((ab)4ab−1)6⟩{displaystyle langle a,bmid a^{2},b^{3},(ab)^{13},[a,b]^{5},[a,bab]^{4},((ab)^{4}ab^{-1})^{6}rangle }{displaystyle langle a,bmid a^{2},b^{3},(ab)^{13},[a,b]^{5},[a,bab]^{4},((ab)^{4}ab^{-1})^{6}rangle }
[a, b] is the commutator

An example of a finitely generated group that is not finitely presented is the wreath product Z≀Z{displaystyle mathbf {Z} wr mathbf {Z} }mathbf {Z} wr mathbf {Z} of the group of integers with itself.



Some theorems


Theorem. Every group has a presentation.


To see this, given a group G, consider the free group FG on G. By the universal property of free groups, there exists a unique group homomorphism φ : FGG whose restriction to G is the identity map. Let K be the kernel of this homomorphism. Then K is normal in FG, therefore is equal to its normal closure, so <G | K> = FG/K. Since the identity map is surjective, φ is also surjective, so by the First Isomorphism Theorem, <G | K> ≅ im(φ) = G. This presentation may be highly inefficient if both G and K are much larger than necessary.


Corollary. Every finite group has a finite presentation.


One may take the elements of the group for generators and the Cayley table for relations.



Novikov–Boone theorem


The negative solution to the word problem for groups states that there is a finite presentation <S | R> for which there is no algorithm which, given two words u, v, decides whether u and v describe the same element in the group. This was shown by Pyotr Novikov in 1955[3] and a different proof was obtained by William Boone in 1958.[4]



Constructions


Suppose G has presentation <S | R> and H has presentation <T | Q> with S and T being disjoint. Then



  • the free product GH has presentation <S, T | R, Q> and

  • the direct product G × H has presentation <S, T | R, Q, [S,T]>, where [S,T] means that every element from S commutes with every element from T (cf. commutator).



Deficiency


The deficiency of a finite presentation <S | R> is just |S| − |R| and the deficiency of a finitely presented group G, denoted def G, is the maximum of the deficiency over all presentations of G. The deficiency of a finite group is non-positive. The Schur multiplicator of a group G can be generated by −def G generators, and G is efficient if this number is required.[5]



Geometric group theory





A presentation of a group determines a geometry, in the sense of geometric group theory: one has the Cayley graph, which has a metric, called the word metric. These are also two resulting orders, the weak order and the Bruhat order, and corresponding Hasse diagrams. An important example is in the Coxeter groups.


Further, some properties of this graph (the coarse geometry) are intrinsic, meaning independent of choice of generators.



See also



  • Nielsen transformation

  • Tietze transformation

  • Presentation of a module



Notes





  1. ^ Sir William Rowan Hamilton (1856). "Memorandum respecting a new System of Roots of Unity" (PDF). Philosophical Magazine. 12: 446..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}


  2. ^ Stillwell, John (2002). "Mathematics and its history". Springer: 374. ISBN 978-0-387-95336-6.


  3. ^ Novikov, Pyotr S. (1955), "On the algorithmic unsolvability of the word problem in group theory", Proceedings of the Steklov Institute of Mathematics (in Russian), 44: 1–143, Zbl 0068.01301


  4. ^ Boone, William W. (1958), "The word problem" (PDF), Proceedings of the National Academy of Sciences, 44 (10): 1061–1065, doi:10.1073/pnas.44.10.1061, PMC 528693, Zbl 0086.24701


  5. ^ Johnson, D.L.; Robertson, E.L. (1979). "Finite groups of deficiency zero". In Wall, C.T.C. Homological Group Theory. London Mathematical Society Lecture Note Series. 36. Cambridge University Press. pp. 275–289. ISBN 0-521-22729-1. Zbl 0423.20029.




References




  • Coxeter, H. S. M.; Moser, W. O. J. (1980). Generators and Relations for Discrete Groups. New York: Springer-Verlag. ISBN 0-387-09212-9. ― This useful reference has tables of presentations of all small finite groups, the reflection groups, and so forth.


  • Johnson, D. L. (1997). Presentations of Groups (2nd ed.). Cambridge: Cambridge University Press. ISBN 0-521-58542-2. ― Schreier's method, Nielsen's method, free presentations, subgroups and HNN extensions, Golod–Shafarevich theorem, etc.


  • Sims, Charles C. (1994). Computation with Finitely Presented Groups (1st ed.). Cambridge: Cambridge University Press. ISBN 978-0-521-13507-8. ― fundamental algorithms from theoretical computer science, computational number theory, and computational commutative algebra, etc.



External links



  • de Cornulier, Yves. "Group Presentation". MathWorld.

  • Small groups and their presentations on GroupNames




Popular posts from this blog

Y

Mount Tamalpais

Indian Forest Service