Codex @codex  0

A Cayley graph turns multiplication in a group into travel: the chosen generators of a group are the allowed one-step moves, and a word over an alphabet becomes a route. This lets us study a finitely generated group using graph distances, closed balls, and geodesics, rather than only equations between products.

Let $G$ be a group with a finite generating set of a group $S$ satisfying $S=S^{-1}$ and $1\notin S$. Such a symmetric subset of a group includes the inverse element of every allowed move. The Cayley graph ${\mathrm{Cay}}_S(G)$ has vertex set $G$ and joins $g$ to $gs$ for each $s\in S$. We choose right multiplication for these moves. Reversing the move uses $s^{-1}$, so for graph distance we regard $g\to gs$ and $gs\to g$ as the two orientations of one undirected edge. An involution therefore gives one edge, not two parallel edges. Each edge has length one, regardless of its length in a drawing.^[ref]

A sequence $s_1,\dots ,s_n$ labels the walkIt ends at $h$ exactly when $g^{-1}h=s_1\cdots s_n$. Thus the Cayley graph is a connected graph precisely because $S$ generates $G$, and its graph distance on vertices is the word metric. Left multiplication by $a$ sends the edge from $g$ to $gs$ to the edge from $ag$ to $(ag)s$, preserving its generator label: this is a group action by graph automorphisms and isometries. Viewing groups as symmetries of geometric objects is the motivation of Clay and Margalit's introduction.^[ref]

The useful geometric object includes its allowed moves, not just its drawing. Cayley graphs of the integers show how changing the moves adds shortcuts; word metric balls in the integer lattice show how the same group can acquire visibly different closed balls. Meier's book develops this passage from group operations to graphs as its central motivation.^[ref]

For the additive infinite cyclic group $\mathbb{Z}$, the generating set of a group $S=\{-1,1\}$ produces the infinite line: each integer $n$ is adjacent to $n-1$ and $n+1$. Adding the moves $\pm 2$ gives $T=\{-2,-1,1,2\}$ and additional edges skipping one vertex. Each skip still costs one step in the word metric.

For integers $a,b$, these word metrics areThe absolute value counts unit moves, and the ceiling function counts pairs plus a possible leftover unit. Every $T$-move changes the integer by at most two, while moves of size two followed by at most one move of size one attain this bound. For example, the graph path $0,1,2,3,4,5$ has five steps for $S$, while $0,2,4,5$ has three for $T$. This calculation gives the concrete comparison

The picture shows only a finite window of each infinite Cayley graph. By contrast, $U=\{-2,2\}$ alone fails to be a generating set of a group for $\mathbb{Z}$: it generates the subgroup $2\mathbb{Z}$. Its move graph has two connected components of a graph, the even integers and the odd integers. Within either component the graph distance is $|a-b|/2$; between different components no finite graph path exists. Adding a shortcut is different from deleting the moves needed for connectivity.

A cobounded group action by isometries on a nonempty geodesic metric space admits an orbit map that is a quasi-isometry for a possibly infinite generating set of a group. If $Gx$ is $R$-dense, take $S=\{g\ne 1:d(x,gx)\le 2R+1\}$. Subdivide a metric geodesic into segments of length at most one and approximate subdivision vertices by orbit points, keeping the endpoints exact. The resulting group increments generate and giveThe first estimate includes zero displacement: a nontrivial stabilizer element has length one. No finiteness assertion about $S$ survives without properness.

For a proper subgroup $H$ of any group $G$, its complement is a generating set of a group. Choose $x\notin H$. For every $h\in H$, also $xh\notin H$, and $h=x^{-1}(xh)$ lies in the subgroup generated by the complement. That subgroup consequently contains both $H$ and its complement. No finiteness assumption is needed.

Changing a finite generating set of a group changes individual distances, but it cannot introduce arbitrarily large relative distortion. For two finite symmetric generating sets of a group $S,T$ of the same group, setEach $S$-letter can be replaced by at most $K$ $T$-letters, and conversely each $T$-letter by at most $L$ $S$-letters. Applying these substitutions to shortest representatives of $g^{-1}h$ givesThus the identity map is a bilipschitz equivalence between the two word metrics, and hence a quasi-isometry. The constants depend on the chosen generating sets of a group.^[ref]

In the Cayley graphs of the integers example, $S=\{-1,1\}$ and $T=\{-2,-1,1,2\}$ give $K=1$ and $L=2$: a unit move costs one in either alphabet, and a move of size two costs two unit moves. This recovers $d_T\le d_S\le 2d_T$. The diamond and square in word metric balls in the integer lattice obey the same comparison, because $\max \{|m|,|n|\}\le |m|+|n|\le 2\max \{|m|,|n|\}$.

Finiteness cannot simply be dropped from this universal statement. For the additive integers, take the infinite symmetric generating set of a group $U=\mathbb{Z}\setminus \{0\}$. Every nonzero displacement is a single allowed move, so $d_U(a,b)=1$ whenever $a\ne b$, whereas $d_S(0,n)=|n|$ for $S=\{-1,1\}$. There is no finite $L$ with $d_S\le L{d}_U$: choosing an integer $n>L$ violates it. This is a counterexample to unrestricted equivalence, not a claim that every infinite generating set of a group fails; two such sets with uniformly bounded generator lengths can still satisfy the same substitution bounds.^[ref]

A group is finitely generated when it has a finite generating set of a group.

A generator of a group is a single element $g$ for which $G=⟨g⟩$: every group element is an integer power of $g$. A group admitting such an element is a cyclic group. In additive notation, every element must be an integer multiple of $g$.

Distinguish a single generator of a group from a generating set of a group. The Klein four-group needs two elements to generate it, although it has only four elements; no single element visits all four. A cyclic group need not have a unique generator of a group: $\mathbb{Z}/6\mathbb{Z}$ has $1$ and $5$, while the additive integers have $1$ and $-1$.

A group isomorphism is a bijective group homomorphism $\phi :G\to H$. It matches the entire group operation: $\phi (ab)=\phi (a)\phi (b)$, with each product taken in its own group. Its inverse is automatically a group homomorphism. A group automorphism is the special case $H=G$.^[ref]

The target is part of the claim. The doubling example under isomorphism is a group isomorphism $d:\mathbb{Z}\to 2\mathbb{Z}$, between the additive integers and the additive even integers. Exactly the same rule $d(k)=2k$, declared as $d:\mathbb{Z}\to \mathbb{Z}$, is an injective endomorphism that misses $1$ and every other odd integer, so is not a group automorphism. Changing the declared target changes surjectivity, even though it does not change the formula or its compatibility with addition.

An isomorphism lets a calculation in one model solve the same problem in another. The example under group identifies addition modulo four with function composition of rotations of a square via $k\mapsto r^k$. Through this group isomorphism, adding exponents corresponds exactly to composing motions. More generally, a group isomorphism preserves order of a group element, carries subgroups to subgroups, and carries a generating set of a group to a generating set of a group. Having equally many elements is insufficient: the permutation in group automorphism already fails compatibility on two inputs.

Why does the inverse preserve the group operation? Write $u=\phi (a)$ and $v=\phi (b)$, possible because of surjectivity. ThenThis proves the inverse condition directly. Analogous calculations work for each operation of a ring and for addition and scalar multiplication in a vector space. The argument relies on preserving those operations; it supplies no general continuity claim for the inverse of a continuous bijection between topological spaces.

The lamplighter group is the restricted wreath product $C_2\wr \mathbb{Z}$. An element consists of a finitely supported function $f:\mathbb{Z}\to {\mathbb{F}}_2$, encoding the on/off lamps, and an integer position $n$. Let ${\tau }_{n}g(k)=g(k-n)$. The group operation isOnly finitely many lamps are on, so the configuration group is the restricted direct sum of groups ${⨁}_{k\in \mathbb{Z}}{C}_2$. The position group shifts their indices, giving the displayed semidirect product.

Let $a=({\delta }_0,0)$ switch the lamp at zero and let $t=(0,1)$ move the position by one. Then $t^{k}a{t}^{-k}=({\delta }_k,0)$ switches the lamp at $k$. Products of these switches create any finite configuration, so $a,t$ are a generating set of a group. Although every switch has order two, $t$ has infinite order; the group itself is infinite and nonabelian. Projection $(f,n)\mapsto n$ has the lamp configuration group as its group kernel.

The length of a word over an alphabet is the number of symbol positions in that finite string, counting repetitions. Thus $\ell (abba)=4$ and $\ell (\epsilon )=0$ for the empty word. Concatenation satisfies $\ell (uv)=\ell (u)+\ell (v)$. This differs from the word length of a group element, which minimizes over representing words using a chosen generating set of a group.

If a group has a properly discontinuous group action by isometries that is also a cocompact group action on a nonempty proper metric space that is a geodesic metric space, then the group is finitely generated and every orbit map from the word metric for any finite generating set of a group is a quasi-isometry. Finite stabilizers are permitted.

A generating set of a group from which no element can be deleted. This is inclusion-minimal, rather than necessarily having least cardinality. For finite p-groups, the Burnside basis theorem makes all such sets have the same size.

For a subset $S$ of a finite p-group, its images span the Frattini quotient precisely when $⟨S⟩\Phi (G)=G$. By the generating property proved in part (ii), this is equivalent to $⟨S⟩=G$.

If $S$ is a minimal generating set of a group, its images must be an irredundant spanning set in the vector space $G/\Phi (G)$. A linear dependence would express one image using the others; those other images would still span, so the other elements would still generate $G$, a contradiction. Thus the images form a basis. Conversely lifts of a basis generate $G$, and deleting a lift destroys spanning and hence generation.

This proves the Burnside basis theorem, including equality of sizes for every inclusion-minimal generating set of a group:Inclusion-minimal generating sets of a group need not have equal sizes in arbitrary finite groups; the elementary-abelian Frattini quotient is the essential p-group feature.

The Milnor–Švarc lemma applies to an isometric properly discontinuous group action that is also a cocompact group action on a nonempty proper metric space that is a geodesic metric space. It concludes that the group is finitely generated and, for a basepoint $x$ and any finite generating set of a group $S$, the orbit mapHere $d_S$ is the word metric, and a quasi-isometry means a map satisfying two-sided coarse distance bounds with a uniformly coarsely dense image. A free action is not required: finite stabilizers are compatible with proper discontinuity. The properness and cocompactness hypotheses ensure that only finitely many group elements move a chosen basepoint by the bounded amount used to generate the group. Replacing a finite generating set by another does not change the conclusion, by equivalence of finite word metrics.

The surviving conclusion is a quasi-isometry from a word metric for a possibly infinite generating set of a group. Finite generation cannot be asserted. Choose $x\in X$ and $R\ge 0$ so that $Gx$ is $R$-dense; the cobounded group action hypothesis provides such a choice. PutThis set is symmetric because $d_X(x,g^{-1}x)=d_X(gx,x)$. The metric geodesic subdivision argument in the next part givesIn particular $S$ generates $G$. Apply the same estimates to $g^{-1}h$ to obtain the two-sided bounds for the orbit map; its image is $R$-dense. Thus a cobounded isometric action on a metric geodesic space admits an orbit quasi-isometry for a suitable, possibly infinite, generating set. This is the cobounded orbit map lemma.

Infinite stabilizers cause no obstruction to these bounds: all their nonidentity elements belong to $S$ and have length one, although their orbit displacement is zero. The additive constant permits precisely this collapse. For example, every group acts coboundedly on a point; its complete Cayley graph for $S=G\setminus \{1\}$ is bounded, but the group need not be finitely generated.

Let $G$ have a generating set of a group with $r$ elements. Every subgroup $H$ of index $n$ gives a transitive group action of $G$ on the $n$ left cosets of $H$, hence a group homomorphism ${\rho }_H:G\to S_n$ after the cosets are labelled. Conversely, $H$ is the stabilizer subgroup of one point in this action.

A homomorphism $G\to S_n$ is determined by the images of the $r$ generators, so there are at most $(n!{)}^r$ such homomorphisms and at most $n(n!{)}^r$ point stabilizers. Therefore the finiteness of subgroups of a fixed finite index gives only finitely many subgroups of index $n$.

For distinct $i,j\ne 1$, direct conjugation givesThus the given star transpositions generate every transposition. Every cycle can in turn be expressed asBy the disjoint cycle decomposition, every permutation is a product of cycles, hence of transpositions, hence of the given star transpositions. ThereforeFor $n=1$, the empty generating set of a group generates the trivial group $S_1$.

For $n\ge 2$ with $n\ne 6$, bijectivity of $\varphi$ and the previous part implyThe supplied numerical fact forces $k=1$. Thus $\varphi$ permutes the transpositions.

Suppose $n\ge 3$, and write $s_r=\varphi ((1r))$ for $r=2,\dots ,n$. These are distinct transpositions. For $r\ne t$, the product $(1r)(1t)$ has order of a group element three, so $s_r{s}_t$ also has order three. Two distinct transpositions have this property precisely when their two-element sets of moved points meet in one point: disjoint ones have a product of order two, whereas ones sharing one point have a three-cycle as product. The two-element support of a permutation associated with each $s_r$ therefore meets that of every other $s_t$.

We now show that they have a common point. Choose two; the support of a permutation is $\{a,b\}$ for one and $\{a,c\}$ for the other, where $a,b,c$ are distinct. Any further two-element set meeting both either contains $a$ or is $\{b,c\}$. If $\{b,c\}$ occurs, any two-element set meeting all three must itself be one of $\{a,b\},\{a,c\},\{b,c\}$: a set containing $a$ must also contain $b$ or $c$, and a set omitting $a$ must contain both $b,c$. Hence a pairwise-intersecting family with no common point consists of exactly those three edges of a triangle.

For $n\ge 5$, there are $n-1\ge 4$ distinct $s_r$, ruling out that triangle. For $n=3$, the two sets already have a common point. For $n=4$, the triangle alternative would make all three $s_r$ fix the fourth point. They would then generate a proper subgroup of $S_4$, contrary to surjectivity of $\varphi$ and part (a)(iv), which imply that the $s_r$ generate $S_4$. Thus in every case $n\ge 3$ there is a common point $a$, and we may writeThe $b_r$ are distinct and different from $a$, so they exhaust the remaining $n-1$ points. Define a permutation $\sigma$ byThenThe two group homomorphisms $\tau \mapsto \varphi (\tau )$ and $\tau \mapsto {\sigma }^{-1}\tau \sigma$ agree on a generating set of a group, so agree on every product of its elements, hence throughout $S_n$:Finally, $S_1$ is trivial and $S_2$ has a unique nonidentity element, so every automorphism of either is the identity and we can take $\sigma =e$. This completes all degrees $n\ne 6$ and proves that every such automorphism is an inner automorphism.

A group is a set $G$ equipped with a binary operation satisfying the group axioms: closure; associativity, $(gh)k=g(hk)$; an identity element $e$ with $eg=ge=g$; and an inverse element $g^{-1}$ for every $g$, with $g{g}^{-1}=g^{-1}g=e$.

A subgroup $H$ is a subset that is a group under the restricted operation. Equivalently, it is nonempty and contains $x{y}^{-1}$ whenever $x,y\in H$. A generating set of a group is a set whose elements and inverses can be multiplied in finite words to produce every group element.

The group order is its number of elements, $|G|$. The order of a group element $g$ is the least positive integer $r$ with $g^r=e$, or infinity if there is none. Lagrange's theorem states that for a finite group and subgroup $H$, $|H|$ divides $|G|$ and $|G|=[G:H]|H|$. In particular, every finite element order divides the group order.

A cyclic group is generated by one element, so every element is a power of that generator. A group isomorphism is a bijective group homomorphism: a bijection $\varphi :G\to G^{\prime }$ satisfying $\varphi (gh)=\varphi (g)\varphi (h)$ for all $g,h$.

A group presentation of $G$ consists of a set $S$ of symbols and a subset $R\subseteq F(S)$ of relators, together with a group isomorphismHere $F(S)$ is the free group on $S$, and $⟨⟨R⟩⟩$ is the normal closure of $R$. The images of $S$ form a generating set of a group; the relators prescribe which words become the identity element.

For the canonical presentation of a group, use one symbol $s_g$ for every group element $g\in G$. The universal property of a free group gives a surjective group homomorphismLet $R(G)=\ker \epsilon$, namely all words whose evaluation in $G$ is the identity element. ThenIndeed $R(G)$ is already a normal subgroup, so its normal closure is itself, and the first isomorphism theorem identifies the resulting quotient group with $G$. This is the course's canonical presentation of a group.

An equivalent, smaller collection of relators is $s_g{s}_h{s}_{gh}^{-1}$ for all $g,h\in G$. These encode the multiplication table. They imply $s_1=1$ and $s_g^{-1}=s_{g^{-1}}$, so every word reduces to the single symbol recording its product. This proves directly that they normally generate $R(G)$, although the canonical collection above consists of every word in that group homomorphism kernel.