Chapter 07 - Generators and Cayley Digraphs

Generating sets describe how a group is assembled from a small stock of elements and their inverses. Cayley digraphs turn that algebraic description into a combinatorial and geometric object. This chapter connects the algebraic notion of generation to graph theory and lays the groundwork for presentations of groups.

§7.1 Generating Sets

Definition 7.1 (Generating set). Let $G$ be a group and $S \subseteq G$. A word in $S$ is a finite product

The subgroup generated by $S$, written $\langle S \rangle$, is the set of all such words (including the empty word, which represents $e$). We say $S$ generates $G$ if $\langle S \rangle = G$.

The inclusion of inverses is essential. In a non-abelian group, positive words alone generally do not close under inversion, so they do not form a subgroup.

Definition 7.2 (Finitely generated group). A group $G$ is finitely generated if there exists a finite subset $S \subseteq G$ with $\langle S \rangle = G$.

§7.2 The Intersection Characterization

Theorem 7.3. Let $G$ be a group and $S \subseteq G$. Then $\langle S \rangle$ equals the intersection of all subgroups of $G$ that contain $S$:

Proof of Theorem 7.3

Step 1: $\langle S \rangle$ is a subgroup containing $S$. Each $s \in S$ is a one-letter word in $S$, so $S \subseteq \langle S \rangle$. The empty word gives $e \in \langle S \rangle$. If

$$x = s_1^{\varepsilon_1} \cdots s_r^{\varepsilon_r}, \qquad y = t_1^{\delta_1} \cdots t_m^{\delta_m},$$

then

$$xy^{-1} = s_1^{\varepsilon_1} \cdots s_r^{\varepsilon_r}\, t_m^{-\delta_m} \cdots t_1^{-\delta_1}$$

is again a word in $S$ and inverses. By the subgroup test, $\langle S \rangle \le G$.

Step 2: $\langle S \rangle$ is contained in every subgroup containing $S$. Let $H \le G$ with $S \subseteq H$. Since $H$ is closed under products and inverses, every finite word in elements of $S$ and their inverses lies in $H$. Hence $\langle S \rangle \subseteq H$.

Step 3: Conclusion. By Step 1, $\langle S \rangle$ is one of the subgroups being intersected. By Step 2, $\langle S \rangle$ is contained in each such subgroup. Therefore $\langle S \rangle$ equals the intersection. $\blacksquare$

This theorem says that “smallest subgroup containing $S$” is not informal language; it is a well-defined closure operation.

§7.3 Standard Examples of Generation

Example 7.4 ($\mathbb{Z}$ with one generator). The integers under addition satisfy $\mathbb{Z} = \langle 1 \rangle$. Every integer is a finite sum of copies of $1$ or $-1$.

Example 7.5 ($\mathbb{Z}$ with two generators). We also have $\mathbb{Z} = \langle 2, 3 \rangle$. Indeed, $1 = 3 + (-2) = 3 - 2$, and since $1$ generates $\mathbb{Z}$, so does $\{2, 3\}$. This shows generating sets need not be minimal.

Example 7.6 ($S_n$ generated by transpositions). The symmetric group $S_n$ is generated by the set of all transpositions. Every permutation can be decomposed as a product of transpositions (cf. Chapter 9). Hence

Example 7.7 ($S_3$ with two generators). More efficiently, $S_3 = \langle (1\;2),\, (1\;2\;3) \rangle$. One verifies:

so all three transpositions are obtained. Together with the two 3-cycles and the identity, all six elements are accounted for.

Example 7.8 (Dihedral group). The dihedral group $D_n$ of symmetries of a regular $n$-gon satisfies $D_n = \langle r, s \rangle$, where $r$ is a rotation by $2\pi/n$ and $s$ is a reflection. Every element can be written as $r^k$ or $sr^k$ for $0 \le k < n$, so $|D_n| = 2n$ and two generators suffice.

Computational criterion in cyclic groups

The following result reduces generation questions in cyclic groups to gcd computations. It is the main tool for Exercises 7.1–7.2 and any problem asking “does this subset generate $\mathbb{Z}_n$?”

Proposition 7.8a (Generation in cyclic groups). Let $G = \langle g \rangle$ have order $n$, and let $a_1, \dots, a_r$ be integers. Then

This subgroup has order $n/d$ and index $d$ in $G$.

Proof

Write $H = \langle g^{a_1}, \dots, g^{a_r} \rangle$. Since $G$ is cyclic, every subgroup of $G$ is cyclic (Chapter 4), so $H = \langle g^m \rangle$ for some divisor $m$ of $n$. We show $m = d$.

($d \mid m$): Each $g^{a_i} \in H = \langle g^m \rangle$ implies $m \mid a_i$. Since also $m \mid n$, we get $m \mid \gcd(a_1, \dots, a_r, n) = d$.

($m \mid d$): By Bezout’s identity, there exist integers $c_1, \dots, c_r, c$ with

$$c_1 a_1 + \cdots + c_r a_r + cn = d.$$

Then

$$g^d = (g^{a_1})^{c_1} \cdots (g^{a_r})^{c_r} \cdot \underbrace{(g^n)^c}_{= e} \in H = \langle g^m \rangle,$$

so $m \mid d$.

Therefore $m = d$, and $|\langle g^d \rangle| = n/d$. $\blacksquare$

Corollary (Generators of $\mathbb{Z}_n$). The element $\bar{a}$ generates $\mathbb{Z}_n$ if and only if $\gcd(a, n) = 1$. Hence $\mathbb{Z}_n$ has exactly $\varphi(n)$ generators, where $\varphi$ is Euler’s totient function.

Example 7.8b. In $\mathbb{Z}_{20}$, $\langle \bar{8}, \overline{14} \rangle = \langle \overline{\gcd(8,14,20)} \rangle = \langle \bar{2} \rangle$, a cyclic subgroup of order $10$. In $\mathbb{Z}_{15}$, $\langle \bar{6}, \overline{10} \rangle = \langle \overline{\gcd(6,10,15)} \rangle = \langle \bar{1} \rangle = \mathbb{Z}_{15}$.

Non-abelian groups

This gcd criterion applies only to cyclic (and more generally abelian) groups. In non-abelian groups, generation questions must be settled by explicit computation — there is no shortcut analogous to gcd. For instance, $\langle (1\;2), (3\;4) \rangle \cong V_4$ in $S_4$ (a proper subgroup), while $\langle (1\;2), (1\;2\;3\;4) \rangle = S_4$ (the full group). The difference is not visible from the cycle lengths alone.

§7.4 Cayley Digraphs

Definition 7.9 (Cayley digraph). Let $G$ be a group and $S$ a generating set for $G$. The Cayley digraph $\operatorname{Cay}(G, S)$ is the directed graph defined by:

• Vertices: the elements of $G$.
• Edges: for each $g \in G$ and each $s \in S$, there is a directed edge $g \to gs$, colored (or labeled) by $s$.

How to read the graph:

§7.5 Cayley Digraphs for Small Groups

Example 7.10 ($\mathbb{Z}_4$, generator $\{\bar{1}\}$). Figure: Cayley digraph of $\mathbb{Z}_4$ generated by $\bar{1}$.

Example 7.11 ($\mathbb{Z}_6$, generator $\{\bar{1}\}$). A directed 6-cycle:

Using the generating set $\{\bar{1}, \bar{2}\}$ instead adds a second family of edges (each vertex also connects to the vertex two steps ahead), producing a denser graph on the same vertex set.

Example 7.12 ($V_4 = \{e, a, b, c\}$, generators $\{a, b\}$). The Klein four-group $V_4 \cong \mathbb{Z}_2 \times \mathbb{Z}_2$ with $ab = c$, $a^2 = b^2 = e$. The Cayley digraph has:

• $a$-edges (say, solid): $e \leftrightarrow a$ and $b \leftrightarrow c$.
• $b$-edges (say, dashed): $e \leftrightarrow b$ and $a \leftrightarrow c$.

Since every generator is its own inverse, each directed edge is paired with its reverse, and the graph looks like a square with opposite sides identified by different colors.

Example 7.13 ($S_3$, generators $\{(1\;2),\, (1\;2\;3)\}$). The Cayley digraph has 6 vertices and two families of edges. The $(1\;2\;3)$-edges form two directed 3-cycles (one through $\{e, (1\;2\;3), (1\;3\;2)\}$ and one through $\{(1\;2), (2\;3), (1\;3)\}$). The $(1\;2)$-edges pair elements across the two 3-cycles. The graph visually displays the non-abelian structure: following generators in different orders leads to different vertices.

Example 7.14 ($D_4$, generators $\{r, s\}$). The Cayley digraph has 8 vertices. The $r$-edges form two directed 4-cycles: one through $\{e, r, r^2, r^3\}$ and one through $\{s, sr, sr^2, sr^3\}$. The $s$-edges connect each $r^k$ to $sr^k$ (and back, since $s^2 = e$). The relation $srs = r^{-1}$ manifests as the fact that the second 4-cycle is traversed in the opposite direction.

§7.6 What Cayley Digraphs Reveal

Theorem 7.15 (Vertex-transitivity). The Cayley digraph $\operatorname{Cay}(G, S)$ is vertex-transitive: for any two vertices $g, h \in G$, the map $x \mapsto hg^{-1}x$ is a graph automorphism sending $g$ to $h$.

Proof of Theorem 7.15

Define $\varphi: G \to G$ by $\varphi(x) = hg^{-1}x$. This is a bijection (left multiplication by the fixed element $hg^{-1}$). We check it preserves edges: if $x \xrightarrow{s} xs$ is an edge, then

$$\varphi(x) = hg^{-1}x \xrightarrow{s} hg^{-1}(xs) = \varphi(xs),$$

so the image pair is also an $s$-edge. Since $\varphi(g) = hg^{-1}g = h$, the map sends $g$ to $h$. $\blacksquare$

Vertex-transitivity means the graph “looks the same from every vertex,” which reflects the algebraic fact that every group element can serve as the identity of a translated copy.

Theorem 7.16 (Connectivity criterion). The Cayley digraph $\operatorname{Cay}(G, S)$ is connected if and only if $S$ generates $G$.

Proof of Theorem 7.16

($\Rightarrow$) If the graph is connected, then for every $g \in G$ there is a directed path from $e$ to $g$. This path spells out a word $s_1^{\varepsilon_1} \cdots s_r^{\varepsilon_r} = g$ with each $s_i \in S$. Hence $g \in \langle S \rangle$, so $\langle S \rangle = G$.

($\Leftarrow$) If $S$ generates $G$, then every $g \in G$ can be written as a word in $S$ and their inverses. Each letter in the word corresponds to traversing an edge (forward for $s$, backward for $s^{-1}$). Hence there is a path from $e$ to $g$. By vertex-transitivity, the graph is connected. $\blacksquare$

Cycle structure and relations. A cycle in the Cayley digraph that returns to its starting vertex corresponds to a relation among the generators. For instance, the 4-cycle in $\operatorname{Cay}(\mathbb{Z}_4, \{\bar{1}\})$ corresponds to the relation $1 + 1 + 1 + 1 = 0$ (i.e., $\bar{1}^4 = \bar{0}$). In $\operatorname{Cay}(D_4, \{r, s\})$, the cycle $e \xrightarrow{s} s \xrightarrow{r} sr \xrightarrow{s} r^{-1} = r^3$ (and continuing back to $e$) encodes the relation $srs = r^{-1}$.

Detecting group properties from the digraph

Commutativity. A group $G$ is abelian if and only if for every pair of generators $s, t \in S$ and every vertex $g$, the two paths

arrive at the same vertex. Visually: every “parallelogram” formed by two different arc types closes. By vertex-transitivity it suffices to check at a single vertex (say $e$): the group is abelian if and only if $st = ts$ for all generator pairs $s, t \in S$.

Example. In $\operatorname{Cay}(S_3, \{(1\;2),\, (1\;2\;3)\})$, start at $e$. Following $(1\;2)$ then $(1\;2\;3)$ gives $(1\;2)(1\;2\;3) = (2\;3)$. Following $(1\;2\;3)$ then $(1\;2)$ gives $(1\;2\;3)(1\;2) = (1\;3)$. Different vertices, so $S_3$ is non-abelian. In $\operatorname{Cay}(V_4, \{a, b\})$, starting at $e$: both orders give $ab = ba = c$. Every parallelogram closes, confirming $V_4$ is abelian.

Subgroup visibility. If $H \le G$ and $S' = S \cap H$ generates $H$, then $\operatorname{Cay}(H, S')$ appears as the induced subgraph on the vertex set $H$ inside $\operatorname{Cay}(G, S)$. The left cosets $gH$ appear as isomorphic copies of this subgraph: restricting the $S'$-edges to any coset reproduces the same pattern, shifted by left multiplication.

Example. In $\operatorname{Cay}(S_3, \{(1\;2),\, (1\;2\;3)\})$, the $(1\;2\;3)$-edges restricted to $\{e, (1\;2\;3), (1\;3\;2)\}$ form a directed 3-cycle — this is $\operatorname{Cay}(\langle (1\;2\;3) \rangle, \{(1\;2\;3)\})$. The other three vertices $\{(1\;2), (2\;3), (1\;3)\}$ form a parallel 3-cycle: this is the coset $(1\;2)\langle (1\;2\;3) \rangle$, not a subgroup but a shifted copy of one.

Connection to Cayley’s theorem. Each generator $s \in S$ defines a permutation $\rho_s: G \to G$ by $\rho_s(g) = gs$. The map $g \mapsto \rho_g$ (where $\rho_g(x) = xg$) extends to an injective homomorphism $G \hookrightarrow \operatorname{Sym}(G)$. This is exactly the right regular representation, and the Cayley digraph is its visual encoding. The fact that this map is injective is the content of Cayley’s theorem (Chapter 8): every group embeds in a symmetric group.

§7.7 Finitely Generated Groups

Not every group is finitely generated. The following is a standard and instructive example.

Theorem 7.17. The group $(\mathbb{Q}, +)$ is not finitely generated.

Proof of Theorem 7.17

Suppose toward a contradiction that $\mathbb{Q}$ is generated by finitely many rationals

$$\frac{a_1}{b_1},\; \frac{a_2}{b_2},\; \dots,\; \frac{a_r}{b_r}$$

written in lowest terms. Set $B = b_1 b_2 \cdots b_r$. Every integer linear combination of these generators has the form

$$n_1 \cdot \frac{a_1}{b_1} + \cdots + n_r \cdot \frac{a_r}{b_r}$$

and when brought to a common denominator, the result is $m / B$ for some integer $m$ (since each denominator $b_i$ divides $B$). Therefore every element of $\langle a_1/b_1, \dots, a_r/b_r \rangle$ has the form $m/B$.

Now choose a prime $p$ that does not divide $B$ (infinitely many primes exist). Then $1/p$ cannot be written as $m/B$ for any integer $m$, because that would require $B = mp$, forcing $p \mid B$. This contradicts $1/p \in \mathbb{Q} = \langle a_1/b_1, \dots, a_r/b_r \rangle$. $\blacksquare$

This proof is a model of how finite-generation questions reduce to arithmetic obstructions. The essential point is that a finite generating set in an additive group of rationals constrains denominators, but $\mathbb{Q}$ has unbounded denominators.

Remark. The additive group $\mathbb{R}$ is also not finitely generated (same style of argument, or by cardinality: a finitely generated subgroup of an abelian group is countable, but $\mathbb{R}$ is uncountable). By contrast, every finite group is finitely generated (take $S = G$).

§7.8 Relations and Presentations

A generating set tells us which elements build the group; relations tell us when different words represent the same element. A presentation packages both into a compact description that determines the group up to isomorphism.

Free groups

To make presentations precise, we need the notion of a group with no relations at all.

Definition 7.18 (Free group, informal). The free group $F(S)$ on a set $S$ consists of all reduced words in the alphabet $S \cup S^{-1}$, where “reduced” means no adjacent pair $ss^{-1}$ or $s^{-1}s$ appears. Multiplication is concatenation followed by cancellation of inverse pairs until the word is reduced. The empty word is the identity.

The free group on one generator is $F(\{a\}) \cong \mathbb{Z}$: every reduced word is $a^k$ for some $k \in \mathbb{Z}$. The free group on two or more generators is non-abelian and infinite — for instance, in $F(\{a, b\})$, the words $ab$ and $ba$ are distinct elements.

The key property of $F(S)$ is universality: every group generated by $|S|$ elements is a quotient of $F(S)$. If $G = \langle s_1, \dots, s_k \rangle$, then the map $F(\{s_1, \dots, s_k\}) \to G$ sending each formal generator to the corresponding group element is a surjective homomorphism. Its kernel consists of exactly those words that equal $e$ in $G$ — the relations.

Presentations

Definition 7.19 (Group presentation). A group presentation

specifies generators $s_1, \dots, s_k$ and relations $r_1, r_2, \dots$ (each $r_i$ is an equation among words in the generators). Formally, $G \cong F(s_1, \dots, s_k) / N$, where $N = \langle\!\langle r_1, r_2, \dots \rangle\!\rangle$ is the normal closure of the relators — the smallest normal subgroup of $F$ containing them.

The group defined by a presentation is the “largest” group generated by the $s_i$ in which all the $r_i$ hold: any other such group is a quotient of it.

Example 7.20 (Cyclic presentation).

Starting from $F(\{a\}) \cong \mathbb{Z}$, the relation $a^n = e$ forces $a^k = a^{k \bmod n}$, giving $\mathbb{Z}/n\mathbb{Z}$.

Example 7.21 (Dihedral presentation).

The first two relations bound the orders of the generators. The third is the conjugation relation: conjugating $r$ by $s$ inverts it, encoding “reflection reverses rotation.” Equivalently, $sr = r^{-1}s$, which is the commutation rule that reduces any word to the normal form $s^i r^j$ ($i \in \{0,1\}$, $0 \le j < n$). These three relations completely determine $D_n$ up to isomorphism.

Example 7.22 (Klein four-group).

Without the commutativity relation $ab = ba$, the group $\langle a, b \mid a^2 = e, b^2 = e \rangle$ would be the infinite dihedral group $D_\infty$ (the free product $\mathbb{Z}_2 {*} \mathbb{Z}_2$). Adding commutativity collapses it to the finite group $V_4$.

Example 7.23 (Quaternion group).

This is a non-abelian group of order 8, distinct from $D_4$. The presentations of $D_4$ and $Q_8$ differ only in the second relation: $s^2 = e$ for $D_4$ versus $j^2 = i^2$ for $Q_8$. In $D_4$ the reflection has order 2; in $Q_8$ both generators have order 4 and the unique element of order 2 is $i^2 = j^2 = -1$.

The word problem

Given a presentation $\langle S \mid R \rangle$, the word problem asks: given a word $w$ in the generators and their inverses, does $w = e$ in the presented group? Equivalently, does $w$ lie in the normal closure of the relators?

For finite groups this is always decidable (enumerate all elements). But in general the word problem is undecidable: Novikov (1955) and Boone (1959) independently proved that there exists a finitely presented group for which no algorithm can determine whether an arbitrary word equals the identity.

This means presentations, while compact, can be deceptively hard to work with. A presentation defines a group precisely, but extracting information from it — the order of the group, whether two words represent the same element, whether the group is trivial — can be computationally intractable. This tension between the elegance of presentations and the difficulty of computing with them runs through much of combinatorial group theory.

Presentations become essential tools in later chapters, particularly for factor groups (Chapter 15) and the structure of finitely presented groups.

Worked Examples

Worked Example A. Show that $\mathbb{Z}_{12} = \langle \bar{5}, \bar{8} \rangle$.

We need $\gcd(5, 8, 12) \mid d$ for all $d$ in the generated subgroup, but more directly: in $\mathbb{Z}_{12}$, the subgroup $\langle \bar{5}, \bar{8} \rangle$ contains $\bar{5}$ and $\bar{8}$. Their difference is

Now $\bar{5} - \bar{3} = \bar{2}$, and $\bar{3} - \bar{2} = \bar{1}$. Since $\bar{1} \in \langle \bar{5}, \bar{8} \rangle$ and $\bar{1}$ generates $\mathbb{Z}_{12}$, we conclude $\langle \bar{5}, \bar{8} \rangle = \mathbb{Z}_{12}$.

Alternatively, note that $\gcd(5, 8) = 1$ and $\gcd(1, 12) = 1$, so $\langle \bar{5}, \bar{8} \rangle$ contains an element of order 12.

Worked Example B. Find $\langle (1\;2), (3\;4) \rangle$ in $S_4$.

Both generators have order 2 and they are disjoint, so they commute:

The generated subgroup is $\{e,\; (1\;2),\; (3\;4),\; (1\;2)(3\;4)\} \cong V_4$. This is a proper subgroup of $S_4$, so $\{(1\;2), (3\;4)\}$ does not generate $S_4$.

Worked Example C. Describe the Cayley digraph of $\mathbb{Z}_2 \times \mathbb{Z}_3$ with generators $a = (1, 0)$ and $b = (0, 1)$.

The group has 6 elements. The $a$-edges swap between the two “layers” (since $a$ has order 2, each $a$-edge is a 2-cycle): $(0,k) \leftrightarrow (1,k)$ for $k = 0, 1, 2$. The $b$-edges form two directed 3-cycles: $(0,0) \to (0,1) \to (0,2) \to (0,0)$ and $(1,0) \to (1,1) \to (1,2) \to (1,0)$. The graph is connected, confirming that $\{a, b\}$ generates the group. Since $\mathbb{Z}_2 \times \mathbb{Z}_3 \cong \mathbb{Z}_6$, the graph could also be drawn as a single directed 6-cycle using the generator $(1,1)$.

Worked Example D. In $\mathbb{Z}_{30}$, determine $\langle \bar{6}, \overline{10}, \overline{15} \rangle$ and find the order of the generated subgroup.

Compute $d = \gcd(6, 10, 15, 30)$. Step by step: $\gcd(6, 10) = 2$, then $\gcd(2, 15) = 1$, then $\gcd(1, 30) = 1$. Since $d = 1$, the Proposition gives $\langle \bar{6}, \overline{10}, \overline{15} \rangle = \langle \bar{1} \rangle = \mathbb{Z}_{30}$.

Concretely: $\overline{10} - \bar{6} = \bar{4}$, then $\bar{6} - \bar{4} = \bar{2}$, then $\overline{15} - 7 \cdot \bar{2} = \overline{15} - \overline{14} = \bar{1}$.

Note that no pair from $\{6, 10, 15\}$ alone generates $\mathbb{Z}_{30}$: $\gcd(6,10,30) = 2$, $\gcd(6,15,30) = 3$, $\gcd(10,15,30) = 5$. All three elements are needed.

Worked Example E. From the Cayley digraph of $D_3 = \langle r, s \rangle$ ($r$ = rotation by $2\pi/3$, $s$ = reflection), read off: (a) the order of each generator, (b) whether the group is abelian, (c) all subgroups visible from single-generator edges.

(a) The $r$-edges form directed 3-cycles, so $|r| = 3$. The $s$-edges pair vertices ($s^2 = e$), so $|s| = 2$.

(b) Start at $e$. Path $e \xrightarrow{r} r \xrightarrow{s} rs$ ends at $rs$. Path $e \xrightarrow{s} s \xrightarrow{r} sr$ ends at $sr$. Since $rs = (1\;3)$ and $sr = (2\;3)$ in the standard labeling of $S_3$, these are different vertices: the group is non-abelian.

(c) The $r$-edges alone decompose the 6 vertices into two directed 3-cycles:

• $\{e, r, r^2\}$: this is the subgroup $\langle r \rangle \cong \mathbb{Z}_3$, the unique subgroup of index 2.
• $\{s, sr, sr^2\}$: this is the coset $s\langle r \rangle$, not a subgroup (it does not contain $e$).

The $s$-edges pair each rotation with a reflection. Each pair $\{g, gs\}$ gives a subgroup $\langle gs \rangle \cong \mathbb{Z}_2$ only when the pair contains $e$: the subgroups $\{e, s\}$, $\{e, sr\}$, $\{e, sr^2\}$ are visible as the $s$-edge from $e$ and the $s$-edges from $r$ and $r^2$ respectively (after relabeling). Together with $\langle r \rangle$ and the trivial subgroups, these are all five subgroups of $S_3$.

Worked Example F. Write a presentation for $Q_8$ and verify that $|Q_8| = 8$ by listing all normal-form elements.

The presentation is $Q_8 = \langle i, j \mid i^4 = e,\; j^2 = i^2,\; jij^{-1} = i^{-1} \rangle$.

The third relation gives $ji = i^{-1}j = i^3 j$, which is the commutation rule. Any word in $i, j$ can be reduced by:

1. Moving all $j$‘s to the right using $ji = i^3 j$.
2. Reducing powers of $i$ mod 4 (since $i^4 = e$).
3. Reducing powers of $j$ mod 2 in the exponent, but noting $j^2 = i^2$ (not $e$). So $j^2$ is replaced by $i^2$, and $j^3 = j^2 \cdot j = i^2 j$.

Normal forms: $i^a j^b$ with $0 \le a \le 3$ and $b \in \{0, 1\}$, giving 8 elements:

Under the standard identification: $i^2 = -1$, $i^3 = -i$, $ij = k$, $i^2 j = -j$, $i^3 j = -k$.

Flashcard Summary

Key facts for rapid review

1. $\langle S \rangle$ concretely: all finite products $s_1^{\pm 1} \cdots s_r^{\pm 1}$ with $s_i \in S$ (including the empty product $= e$).

2. $\langle S \rangle$ abstractly: the intersection of all subgroups of $G$ containing $S$ (Theorem 7.3).

3. Key examples of generation:

   • $\mathbb{Z} = \langle 1 \rangle = \langle 2, 3 \rangle$ (but $\langle 2 \rangle = 2\mathbb{Z} \neq \mathbb{Z}$).
   • $S_n = \langle \text{all transpositions} \rangle = \langle (1\;2), (1\;2\;\cdots\;n) \rangle$.
   • $D_n = \langle r, s \rangle$ with $|D_n| = 2n$.

4. Cayley digraph $\operatorname{Cay}(G, S)$: vertices = group elements; edge $g \xrightarrow{s} gs$ for each generator $s$.

5. Vertex-transitive: left multiplication by any group element is a graph automorphism.

6. Connected iff $S$ generates $G$ (Theorem 7.16).

7. Cycles = relations among generators.

8. The digraph depends on the choice of generators, not just on the group.

9. Generation in $\mathbb{Z}_n$: $\langle \bar{a}_1, \dots, \bar{a}_r \rangle = \langle \overline{\gcd(a_1, \dots, a_r, n)} \rangle$. Generates $\mathbb{Z}_n$ iff $\gcd = 1$.

10. Commutativity from digraph: check that all generator-pair parallelograms close at any single vertex.

11. Subgroup visibility: $\operatorname{Cay}(H, S \cap H)$ appears as induced subgraph; cosets appear as shifted copies.

12. Not finitely generated: $(\mathbb{Q}, +)$ — finite generators constrain denominators.

13. Presentation $G = \langle S \mid R \rangle$: formally $G \cong F(S)/\langle\!\langle R \rangle\!\rangle$, quotient of the free group by the normal closure of relators.

14. Key presentations: $\mathbb{Z}_n = \langle a \mid a^n \rangle$, $D_n = \langle r, s \mid r^n, s^2, srs r \rangle$, $Q_8 = \langle i, j \mid i^4, j^2 i^{-2}, jij^{-1}i \rangle$.

15. Word problem: deciding $w = e$ from a presentation is undecidable in general (Novikov—Boone).

Mastery Checklist

Before leaving Chapter 7, verify that you can:

• Compute $\langle S \rangle$ explicitly in $\mathbb{Z}_n$, $S_n$, and $D_n$ for small cases.
• State and prove that $\langle S \rangle$ is the intersection of all subgroups containing $S$.
• Explain why inverses are needed in the definition of generation (give a counterexample without them).
• Draw a Cayley digraph for a given group and generating set; read off the identity, multiplication, and inverses.
• State and prove: the Cayley digraph is connected iff the generating set generates the group.
• Prove that $(\mathbb{Q}, +)$ is not finitely generated.
• Write the presentation of $D_n$ and explain what each relation means geometrically.
• Determine whether a given subset generates a given group (using gcd in abelian cases, explicit computation otherwise).
• Apply the gcd criterion: $\langle \bar{a}_1, \dots, \bar{a}_r \rangle = \langle \overline{\gcd(a_1, \dots, a_r, n)} \rangle$ in $\mathbb{Z}_n$.
• Detect commutativity from a Cayley digraph by checking parallelograms at a single vertex.
• Identify subgroups and their cosets as subgraphs in a Cayley digraph.
• Explain why different generating sets for the same group yield different Cayley digraphs.
• Define the free group on a set and explain how presentations arise as quotients.
• State the quaternion group presentation and explain how it differs from $D_4$.
• Explain the word problem and state why it is undecidable in general.
• Use the fact that homomorphisms are determined by their values on generators (Exercise 7.6).