The Lumenary · Research pathways

Geometric group theory

Name: ______________________

Date: ______________________

You will learn to

Draw Cayley graphs, compute word metrics and balls, and prove that changing the finite generating set changes the word metric only by a bi-Lipschitz map
Define quasi-isometries and decide, with invariants such as growth and hyperbolicity, when two groups are or are not quasi-isometric
State and prove the Švarc–Milnor lemma, and apply it to fundamental groups of closed manifolds and their universal covers
Prove Sanov's theorem by ping-pong, and define δ-hyperbolic and amenable groups, proving that free groups are paradoxical and hence non-amenable
Describe Gromov's polynomial growth theorem and the Banach–Tarski paradox, and separate established results from open problems

1.
Let $F_2$ be the free group on $a, b$ with generating set $S = \{a^{\pm1}, b^{\pm1}\}$ . How many elements does the ball $B_S(3)$ of radius $3$ contain (including the identity)?
2.
Which of these pairs of finitely generated groups are quasi-isometric? (Choose all that apply.)
- A. $\mathbb{Z}$ and $\mathbb{Z} \times S_3$
- B. $F_2$ and $F_3$
- C. $\mathbb{Z}^2$ and $\mathbb{Z}^3$
- D. $\mathbb{Z}^2$ and the fundamental group of a closed surface of genus 2
- E.Any finite group and the trivial group
3.
The group $\mathbb{Z}$ acts on $\mathbb{R}^2$ by $n \cdot (x, y) = (x + n, y)$ . Yet $\mathbb{Z}$ is not quasi-isometric to $\mathbb{R}^2$ . Which hypothesis of the Švarc–Milnor lemma fails?
- A.The action is not proper.
- B.The action is not cocompact.
- C.The action is not by isometries.
- D. $\mathbb{R}^2$ is not a proper geodesic space.
4.
In the ping-pong lemma, $X_1, X_2$ are disjoint and non-empty, $a^n(X_2) \subseteq X_1$ and $b^n(X_1) \subseteq X_2$ for $n \ne 0$ . For $w = a^{2} b^{-5} a^{-1}$ , which inclusion does the proof establish, and why does it show $w \ne 1$ ?
- A. $w(X_2) \subseteq X_1$ ; since $X_2 \ne \varnothing$ and $X_1 \cap X_2 = \varnothing$ , $w$ moves a point.
- B. $w(X_1) \subseteq X_2$ ; so $w$ moves every point of $X_1$ .
- C. $w(X_1) \subseteq X_1$ ; so $w$ has a fixed set, hence $w \ne 1$ .
- D.Non-emptiness is not needed; disjointness alone shows $w \ne 1$ .
5.
The integer Heisenberg group $H_3(\mathbb{Z})$ has lower central series $G_1 = H_3(\mathbb{Z}) \supset G_2 = Z \supset G_3 = 1$ , where $Z \cong \mathbb{Z}$ is the centre, and $G_1 / G_2 \cong \mathbb{Z}^2$ . By the Bass–Guivarc'h formula, what is the degree $d$ of polynomial growth, $|B(r)| \sim r^d$ ?
6.
Let sanovA sanovB : SL(2, ℤ) be Sanov's matrices. Which Lean statement says that they generate a free group of rank 2?
- A.Function.Injective (FreeGroup.lift ![sanovA, sanovB])
- B.Function.Surjective (FreeGroup.lift ![sanovA, sanovB])
- C.sanovA * sanovB ≠ sanovB * sanovA
- D.∀ n : ℤ, n ≠ 0 → sanovA ^ n ≠ 1
7.
Which of these groups are amenable? (Choose all that apply.)
- A. $\mathbb{Z}^3$
- B.The Heisenberg group $H_3(\mathbb{Z})$
- C. $\mathrm{SL}(2, \mathbb{Z})$
- D.The lamplighter group $\mathbb{Z}/2 \wr \mathbb{Z}$
- E. $F_2 \times \mathbb{Z}$
8.
Which statement about the Banach–Tarski paradox is correct?
- A.It uses the axiom of choice to pick one point from each orbit of a free subgroup of $\mathrm{SO}(3)$ , and the resulting pieces are not Lebesgue measurable.
- B.It shows that Lebesgue measure is not countably additive.
- C.The same works for a disc in the plane with rigid motions.
- D.It needs infinitely many pieces.
9.
Write ball_size(generators, multiply, identity, r) returning $|B(r)|$ , the number of group elements that are products of at most $r$ generators, by breadth-first search. The generators are assumed closed under inverses. Test it on $\mathbb{Z}$ with generating set $\{\pm 2, \pm 3\}$ , where $|B(1)| = 5$ and $|B(2)| = 13$ .
Computational — Practice

Answer key — Geometric group theory

1.
Reduced words of length $k \ge 1$ : $4$ choices for the first letter and $3$ for each later one (anything except the inverse of the previous letter), so $4 \cdot 3^{k-1}$ . Hence $|B(3)| = 1 + 4 + 12 + 36 = 53$ . In general $|B(r)| = 2 \cdot 3^r - 1$ : exponential growth.
2.
Quasi-isometric: $\mathbb{Z} \sim \mathbb{Z} \times S_3$ (finite-index subgroup), $F_2 \sim F_3$ (regular trees of degree $\ge 3$ are quasi-isometric) and finite groups $\sim$ a point. Not quasi-isometric: $\mathbb{Z}^2$ and $\mathbb{Z}^3$ (growth $r^2$ versus $r^3$ ), and $\mathbb{Z}^2$ and a genus-2 surface group (polynomial versus exponential growth).
3.
The action is by isometries and proper, and $\mathbb{R}^2$ is proper and geodesic, but the action is not cocompact: the orbit $\mathbb{Z} \cdot K$ of a compact set stays in a horizontal strip. The proof of the lemma uses cocompactness to find group elements near every point of a geodesic; without it, the orbit map $n \mapsto (n, 0)$ is a quasi-isometric embedding but is far from coarsely surjective.
4.
Reading right to left: $a^{-1}(X_2) \subseteq X_1$ , then $b^{-5}(X_1) \subseteq X_2$ , then $a^{2}(X_2) \subseteq X_1$ . So $w(X_2) \subseteq X_1$ . Pick $x \in X_2$ (non-empty); then $w(x) \in X_1$ , which is disjoint from $X_2$ , so $w(x) \ne x$ and $w \ne 1$ .
5.
$d = 1 \cdot \operatorname{rank}(\mathbb{Z}^2) + 2 \cdot \operatorname{rank}(\mathbb{Z}) = 2 + 2 = 4$ . The reason for the weight 2: the commutator $[x^n, y^n] = (0, 0, n^2)$ shows that central elements of size $n^2$ are reached by words of length $\sim n$ . The lesson's experiment estimates the degree numerically and finds values approaching 4.
6.
FreeGroup.lift ![sanovA, sanovB] is the homomorphism $F_2 \to \mathrm{SL}(2, \mathbb{Z})$ with $a \mapsto A$ , $b \mapsto B$ . Its image is $\langle A, B \rangle$ , and it is injective iff its kernel is trivial iff no non-trivial reduced word is the identity — the definition of ' $A, B$ freely generate'. The other statements are true consequences or false.
7.
Amenable: $\mathbb{Z}^3$ , $H_3(\mathbb{Z})$ and the lamplighter group (all solvable). Not amenable: $\mathrm{SL}(2, \mathbb{Z})$ and $F_2 \times \mathbb{Z}$ , which contain $F_2$ . The lamplighter group shows that amenable groups can have exponential growth.
8.
The proof takes a free subgroup $F \le \mathrm{SO}(3)$ , removes the countably many fixed points of its non-trivial elements from the sphere, chooses (by the axiom of choice) one point in each $F$ -orbit, and transports the paradoxical decomposition of $F_2$ (Theorem 5). The pieces are non-measurable, so there is no conflict with measure theory. In the plane the motion group is amenable and no such paradox exists.

def ball_size(generators, multiply, identity, r):
    seen = {identity}
    frontier = [identity]
    for _ in range(r):
        new = []
        for g in frontier:
            for s in generators:
                h = multiply(g, s)
                if h not in seen:
                    seen.add(h)
                    new.append(h)
        frontier = new
    return len(seen)

For $\mathbb{Z}$ with $\{\pm2, \pm3\}$ : $B(1) = \{0, \pm2, \pm3\}$ and $B(2) = \{-6, \dots, 6\}$ (for instance $1 = 3 - 2$ and $4 = 2 + 2$ ). From far away this Cayley graph is still a line: $|B(r)| \approx 6r$ , linear growth, as for the generators $\pm 1$ .