S. D. V. Stephens

notes / Studies in Algebra and Group Theory / chapter 8: Presentations and the Modular Group

29 Presentations, Cayley Graphs, and Normal Forms

· Denis Auroux

Original Professor Auroux’s handwritten notes (PDF), behind a password for now:

Generators, presentations, and Cayley graphs

Recall.

  • The free group on generators . Its elements are all reduced words (Non-reduced words: reduce them by

    • if , combining ;
    • if an exponent is zero, removing .

    Repeat until the word is reduced.)

  • This is the “largest” group with generators: all others are quotients of . If is generated by , define a homomorphism by setting (and so ).

  • A finitely generated group is said to be finitely presented if the kernel of is the smallest normal subgroup of containing some finite subset (words in the generators), i.e. the subgroup generated by the ’s and their conjugates . Write

Example 29.1. .

Example 29.2. .

  • Concretely, given generators , it is not hard to find relations , i.e. words in the free group such that under , , we have . If these relations hold in , then induces a surjective homomorphism This is an isomorphism once we have found a complete set of relations among the , i.e. when and their conjugates generate .

  • How to work with a group described by generators and relations? Sometimes we know what is, but sometimes we don’t. Two useful ideas (among many): (1) the Cayley graph; (2) normal forms.

The Cayley graph

Definition 29.3. Given generators , the Cayley graph of has

  • vertices = the elements of the group;
  • two vertices connected by an edge labelled when .

[Here we’re doing right multiplication; one could do left multiplication instead.]

Example 29.4. with its usual generator :

Cayley graph of the integers with generator 1: a horizontal line of vertices labelled -2, -1, 0, 1, 2, continuing in both directions, with an arrow labelled 1 from each vertex to the next.

Example 29.5. with generators , . (Here , so the edges are undirected.)

Cayley graph of S3 with generators s1=(12) and s2=(23): a hexagon whose vertices are e, s1=(12), s1s2=(123), (13), s2s1=(132), s2=(23), with edges alternately labelled s1 and s2.

The fact that this closes up shows the relation (). Since any word in with relations can be reduced to , one can use this to check .

Example 29.6. with generators , (the “permutohedron”):

Cayley graph of S4 with generators s1, s2, s3 drawn as a permutohedron: 24 vertices labelled by permutations in one-line notation, 1234 at the bottom and 4321 at the top, edges coloured by generator, forming square and hexagonal faces; edges at the back are dashed.

The faces are squares, giving the relation , and hexagons, giving and .

More generally, has the following presentation:

Proposition 29.7 (Fact). acts on its Cayley graph by “left multiplication”: on vertices , on edges .

This action is transitive on vertices (and on edges of a given label ): the graph is very symmetric!

  • The word length of an element of (in the given generators) the shortest distance from to in the Cayley graph.

  • For infinite groups, we can ask about the growth rate of : given a set of generators , how does the number of elements represented by words of length grow with ? Especially: does it grow polynomially or exponentially?

    Even if we change our set of generators to some other , the word length of a given element changes by a bounded factor only (bound = word lengths of the new generators in terms of the old ones and vice versa). So the exponential or polynomial nature of the growth is independent of the set of generators.

Example 29.8. Finitely generated abelian groups have polynomial growth; free groups have exponential growth.

  • For finite groups, the Cayley graph is finite and growth isn’t relevant, but questions about word length remain interesting!

Example 29.9. In , with generators : the longest element is , of word length , and the word length of is the number of inversions (pairs such that ).

This is best understood by representing permutations as diagrams:

A permutation drawn as a diagram: n points on a top line labelled 1, 2, ..., n joined by strands to points on a bottom line; the strand from 1 ends at the point labelled sigma(1) and the strand from 2 at the point labelled sigma(2).
  • Composition = stacking diagrams.
  • The expression in terms of the comes from decomposing the diagram into layers with a single crossing:
The generator s_i as a diagram: vertical strands between two horizontal lines, except that the strands in positions i and i+1 cross once.
  • The presentation of any two diagrams for are related by the moves
The three moves on permutation diagrams: (1) two successive crossings of the same pair of strands equal two straight strands, s_i squared equals e; (2) crossings of far-apart pairs of strands can slide past each other, s_i s_j = s_j s_i when |i-j| is at least 2; (3) three crossings among three strands can be rearranged, s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}.

  • The word length is now clear.

  • We can even list all the shortest words that can represent a given permutation! Namely: Call the set of such the “ending set” of . Then for each ending set, repeat the process for .

  • For each we can find a preferred expression of as a word in by choosing at each step the smallest such that to end the word.

    This gives a normal form for elements of (i.e. a preferred word representing each element), and hence a solution to the word problem: when do two words represent the same element? ( when does a word represent ?)

For , or other groups where it’s well understood how to “calculate elements” (e.g. groups of matrices, etc.), we don’t need fancy algorithms or normal forms to solve the word problem. In many groups, however, this is all we have!

The braid group

Example 29.10. The braid group (but ).

Braid group generators: s_i, in which the strand starting in position i passes over the strand starting in position i+1; s_i inverse, in which it passes under; and the braid relation, two equivalent three-strand braids s_i s_{i+1} s_i and s_{i+1} s_i s_{i+1}.

Thus a braid is something like the picture below, up to isotopy, where strands never turn back up (important in knot theory, etc.!).

Left: a braid on four strands between two horizontal lines, with strands crossing over and under one another. Right: the same braid with its closure, each bottom endpoint joined by a blue arc around the right side back to the corresponding top endpoint.

Theorem 29.11 (Markov’s theorem). Every knot or link in can be represented as the closure of a braid, and two braids have isotopic closures iff they’re related by a sequence of moves of 2 types:

  • conjugation in : for all ;
  • stabilization: , and .

is much bigger than , but its algorithmic aspects can be approached by the same method, using:

Definition 29.12. Permutation braids are braids in which any 2 strands cross at most once, and all crossings are positive (of the same kind as in , not ). For example:

A permutation braid on four strands: each pair of strands crosses at most once, and at every crossing the strand moving to the right passes over.

These form a finite set, in bijection with .

Let the longest permutation braid. Since its shortest word can start/end with any , is still a permutation braid. Also note , which lets us move ’s to the left.

Thus any element of can be written as “Moving to the left everything that can be” we can find an expression such that i.e. any way of adding the initial letter of a shortest word of to the end of would cause it to no longer be a permutation braid.

This gives rise to the “Garside normal form” and a solution to the word problem in (Garside 1969 + Thurston and Elrifai–Morton, early 1990s).

Notes not reached in this lecture, covered at the start of Lecture 30

and

One more example:

Proposition 29.13. is generated by and .

Proof. Given , we want to express it in terms of and .

  • If , then , and is either or .
  • Now assume , and repeatedly apply the following algorithm to modify :
    • if , use Euclidean division to write , . Then This decreases .
    • if , brings us back to .

After finitely many steps we find that the product of with some word in and has and , hence is or . ∎

  • There is a different, geometric proof, based on the fact that acts on the upper half plane by Now acts by and by .

The region is a fundamental domain of this action, in the sense that and its images under exactly tile .

Tiling of the upper half plane by images of the fundamental domain of PSL2(Z): the shaded region I above the unit circle between Re z = -1/2 and 1/2, neighbouring vertical strips T, T^2, T^-1, T^-2, the regions S, TS, T^2S, T^-1S, T^-2S under the unit circles centred at the integers, and smaller regions such as ST, STS, ST^-1, TST bounded by circles of radius 1/3; the real axis is marked from -2 to 2.

Since the regions immediately adjacent to are and , the regions immediately next to are and . The structure of the tiling reproduces exactly the Cayley graph of with generators , and the fact that all regions can be reached from in finitely many steps is equivalent to: generate .

  • Other generators: instead of and , we could use
    • and . These have finite order! .
    • and . These are conjugates! .
    • The images of these matrices in also generate .

Theorem 29.14.

(Next time.)