Section 3.6 introduced free groups (Definition 3.6.6), presentations (Definition 3.6.13), and the standard method for proving that a group has a given presentation: check that the relations hold in the group, which gives a surjection from the presented group (Proposition 3.6.14), and then show that this surjection is injective. It also posed the word problem: given two words in the generators of , decide whether they represent the same element. For groups whose elements we can compute with directly, such as groups of permutations or of matrices, this is easy: evaluate both words and compare. For a group known only through a presentation it can be hard, and by the Novikov–Boone theorem there are finitely presented groups for which no algorithm solves it.
This chapter develops two tools for understanding a group given by generators and relations. The Cayley graph turns the group into a geometric object, and normal forms single out a preferred word for each element. We apply them to the symmetric groups, the braid groups, and the groups and .
12.1.1 Definition and First Examples
Definition 12.1.1 (Cayley graph). Let be a group generated by . The Cayley graph of with respect to these generators has:
one vertex for each element of ;
for each and each generator , a directed edge from to , labeled .
Every vertex has one outgoing and one incoming edge with each label. When a generator satisfies , the edges and come in pairs, and we draw each pair as a single undirected edge. A word in the letters describes a path from to , following the edge labeled forward for each letter and backward for each letter . Since the generate , the Cayley graph is connected.
Note. acts on its Cayley graph by left multiplication: sends the vertex to and the edge to the edge , which has the same label. This action is transitive on vertices, and transitive on the edges with a given label, so the Cayley graph looks the same from every vertex.
Example 12.1.2 (Cayley graph of ). With the generator , the Cayley graph of is the integer number line:
Example 12.1.3 (Cayley graph of ). Take the generators and . Since , we draw undirected edges. The six vertices form a hexagon whose edges are alternately labeled (red) and (blue); next to each vertex we give the permutation in cycle notation.
Every vertex has exactly one -edge and one -edge. The two paths from to the bottom vertex show that ; given , this relation is equivalent to , which says that the path around the hexagon closes up. In fact , the case of Theorem 3.6.18.
Example 12.1.4 (Cayley graph of ). Take the generators ,, and . In the figure, each vertex is labeled by the string (the one-line notation of ). The vertex is obtained from by swapping the entries in positions and , since and . Edges labeled ,, are drawn in red, blue, and green, and edges at the back are dashed.
The 24 vertices and 36 edges form the edges of a truncated octahedron, also called the permutohedron. Its faces correspond to relations. The six squares have edges alternately labeled and , and express . The eight hexagons have edges alternately labeled or , and express and . The identity is at the bottom and at the top; Section 12.2 will show that every edge going up increases the distance from by one.
12.1.2 Word Length and Growth
Definition 12.1.5 (Word length). Let be generated by . The word length of is the distance from to in the Cayley graph, where edges may be followed in either direction. Equivalently, is the smallest such that with each .
For finite groups the Cayley graph is finite, but word lengths remain interesting; we study them for in the next section. For infinite groups, the Cayley graph also records how fast the group grows.
Definition 12.1.6 (Growth). Let be generated by , and let be the number of elements with . The group has polynomial growth if there are constants and with for all , and exponential growth if there are constants and with for all .
These notions do not depend on the choice of generators. If is another generating set, with word length and counting function , choose such that each is a product of at most letters . Then , so , and a bound gives . Exchanging the roles of the two generating sets, with a constant , gives for all ; so if , then taking ,
Example 12.1.7 (Growth of abelian and free groups). If is abelian and generated by , every element of word length at most can be written with , so : finitely generated abelian groups have polynomial growth. In the free group with , distinct reduced words are distinct elements, and the word length of an element is the length of its reduced word. There are reduced words of length exactly , so has exponential growth. (The free group has polynomial growth.)
Note. A deep theorem of Gromov (1981) characterizes polynomial growth: a finitely generated group has polynomial growth if and only if it has a nilpotent subgroup of finite index. Here a group is nilpotent if the sequence , the subgroup generated by all with and , reaches ; abelian groups are the case .