Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 143 (Introduction to Geometric Group Theory)

The Nielsen–Schreier theorem says that every subgroup of a free group is free. Realize $F_n$ as the fundamental group of the rose $R_n$, the graph with one vertex and $n$ oriented loops. A subgroup $H\le F_n$ of finite index of a subgroup $d$ corresponds to a connected $d$-sheeted covering graph $X\to R_n$. The graph $X$ has $d$ vertices and $dn$ unoriented edges. Choosing a spanning tree leavesedges outside the tree, and these freely generate ${\pi }_1(X)\cong H$. Thus the Nielsen–Schreier formula is

Take the free abelian group $G={\mathbb{Z}}^2$, whose rank of a group is two, and its finite-index subgroup $H=2\mathbb{Z}\times \mathbb{Z}$. The subgroup has index two and is again isomorphic to ${\mathbb{Z}}^2$, so its rank is two. The Nielsen–Schreier formula would instead give $1+2(2-1)=3$. Henceis a counterexample.

Let $r=d(G)$ be the rank of a group, let $S$ be a generating set of size $r$, and suppose $[G:H]=d$. Choose a Schreier transversal adapted to a spanning tree in the Schreier coset graph. By Schreier's lemma, $H$ is generated by the elementsThere are $dr$ candidates. The $d-1$ oriented edges in the spanning tree give trivial candidates, leaving at most $dr-(d-1)$. This proves the Schreier index-rank inequality

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 a finite generating set $S$ of $G$, the Cayley graph ${\mathrm{Cay}}_S(G)$ has vertex set $G$ and an edge from $g$ to $gs$ for every $g\in G$ and $s\in S\cup S^{-1}$; one may retain orientations and labels, or forget them.

As unlabelled undirected graphs, the Cayley graph of the infinite cyclic group $\mathbb{Z}$ with generator $1$ and the Cayley graph of the infinite dihedral groupwith generators $a,b$ are both the two-way infinite line. The first group is an abelian group and the second is not, so they are not isomorphic. Thus the requested example is the infinite line as a Cayley graph of $\mathbb{Z}$ and $D_{\infty }$.

A map $f:X\to Y$ is a quasi-isometry if there are $\lambda \ge 1$ and $\epsilon ,R\ge 0$ such thatfor all $x,x^{\prime }\in X$, and every point of $Y$ lies within distance $R$ of $f(X)$. The Milnor–Švarc lemma says that a group acting properly discontinuously, cocompactly and isometrically on a proper geodesic metric space is finitely generated, and each orbit map from a word metric is a quasi-isometry.

Now let $S,T$ be finite generating sets of $G$. PutReplacing each letter in an $S$-word by a $T$-word and conversely givesThus the identity map is a bilipschitz equivalence, hence a quasi-isometry. All finite generating sets of a finitely generated group give quasi-isometric Cayley graphs.

Suppose first that $\varphi :G\to H$ is a $(\lambda ,\epsilon )$-quasi-isometry. If $k\in \ker \varphi$, the lower quasi-isometry inequality givesso the kernel of a group homomorphism lies in the finite word-metric ball of radius $\lambda \epsilon$ and is finite. Coarse surjectivity gives an $R$ such that every $h\in H$ is within $R$ of $\varphi (G)$. The finite ball $B_H(1,R)$ therefore contains representatives for every coset of $\varphi (G)$, so $H/\varphi (G)$ is finite.

Conversely, suppose $\ker \varphi$ is finite and $phi(G)$ is a finite-index subgroup of $H$. The map factors asThe first arrow is a finite-kernel quotient quasi-isometry, the middle arrow is an isomorphism of finitely generated groups, and the last arrow is a finite-index subgroup quasi-isometry. Their composition is a quasi-isometry. Hence the quasi-isometry criterion for a group homomorphism is

Yes. Take $G=F_2$. The free product satisfiesA connected three-sheeted cover of the two-petal rose has fundamental group of rank $1+3(2-1)=4$ by the Nielsen–Schreier formula. Thus $F_4$ is isomorphic to an index-three subgroup of $F_2$. A finite-index subgroup quasi-isometry then gives

For a locally finite discrete metric space $(X,d)$ with basepoint $x_0$, the growth function of a discrete metric space isIn a Cayley graph, left multiplication by $g{x}_0^{-1}$ is a graph isometry carrying $x_0$ to any other vertex $g$. It therefore gives a bijection $B(x_0,r)\to B(g,r)$ for every $r$. Thus the growth function of a fixed Cayley graph is exactly independent of the basepoint.

Choose any finite generating set $T$ of the finitely generated group $H$. Starting from a finite generating set $S_0$ of $G$, setEvery $T$-word in $H$ of length at most $r$ is also an $S$-word in $G$ of length at most $r$. The inclusion of the corresponding word-metric balls is injective, so the growth function of a finitely generated group satisfies

A finitely generated group has polynomial growth of a group if its growth function is bounded above by $C(1+r{)}^D$ for some constants $C,D$.

Let $G$ be generated by $s_1,\dots ,s_k$. Since $G$ is a two-step nilpotent group, every group commutator $[s_i,s_j]$ is central. Commuting letters past one another therefore collects every word of length at most $n$ into the formThe generator exponents satisfy $|a_i|\le n$. At most $n(n-1)/2$ exchanges are needed during collection, so $|b_{ij}|\le n^2$ is a sufficient bound. With $m=k(k-1)/2$, the number of possible collected expressions is at mostRelations can only reduce this count. This proves the polynomial growth of a finitely generated two-step nilpotent group, so every finitely generated two-step nilpotent group has polynomial growth.

Consider the matricesTheir projective action on the positive real line isThese disjoint images give the monoid version of the ping-pong lemma: after removing a common initial letter, two different positive words act differently. Thus $A,B$ generate a free monoid. There are $2^n$ distinct positive words of length $n$, all lying in the radius-$n$ word ball for any generating set enlarged to contain $A,B$. Therefore the Exponential growth of SL2 of Z gives

An amenable group is a group $G$ admitting a left-invariant finitely additive probability measure $m:\mathcal{P}(G)\to [0,1]$. For a $G$-set $X$, subsets $A,B\subseteq X$ are equidecomposable subsets under a group action if there are finite partitions $A={⨆}_i{A}_i$, $B={⨆}_i{B}_i$ and elements $g_i\in G$ such that $g_i{A}_i=B_i$. The action is a paradoxical group action if $X$ contains two disjoint subsets, each $G$-equidecomposable with $X$.

To prove the nonamenability of a nonabelian free group, write $F_2=⟨a,b⟩$ and let $W(s)$ be the set of nonempty reduced words beginning with $s\in \{a,a^{-1},b,b^{-1}\}$. Cancellation of the first letter gives the disjoint decompositionsIf an invariant measure $m$ existed, these would implyEvery singleton has measure zero: invariance gives all singletons the same measure, and finite additivity over arbitrarily many distinct points forces that measure to vanish. The four sets $W(s)$ partition $F_2\setminus \{1\}$, so their measures sum to one. The two displayed equations say that the same sum is two, a contradiction. Hence

For a finite generating set $S$, the Følner condition requires that for every $\epsilon >0$ there be a nonempty finite $F\subseteq G$ such thatwhere $△$ denotes symmetric difference. Choose a Følner sequence $(F_n)$ and define normalized counting functions on all subsets $A\subseteq G$ byBy compactness of the product $[0,1{]}^{\mathcal{P}(G)}$, some subnet converges pointwise to a function $m$. The identities ${\mu }_n(G)=1$ and finite additivity on disjoint subsets pass to the limit, so $m$ is a finitely additive probability measure.

For a fixed $g=s_1\cdots s_{\ell }$, the triangle inequality for symmetric differences givesConsequentlyso $m(gA)=m(A)$. The limit is left invariant and the Følner condition implies amenability. Thus every finitely generated group satisfying the Følner condition is amenable.

For the standard generator $1$ of the additive group $\mathbb{Z}$, take the intervalsOnly the two endpoints change under translation by $1$, and henceThe same follows for every fixed integer translation by iteration. Therefore these sets are a Følner sequence for the integers, and $\mathbb{Z}$ satisfies the Følner condition.

Yes, but there is only one nontrivial isomorphism type that works. If $G=C_2$, thenThe infinite dihedral group contains its infinite cyclic rotation subgroup with index two, so it is amenable by virtually abelian groups are amenable.

Suppose now that $G\ncong C_2$. The action of $G\ast G$ on its Bass-Serre tree is non-elementary: one vertex degree is greater than two, so there are hyperbolic elements with disjoint pairs of endpoints. Suitable powers satisfy the ping-pong lemma on the boundary and generate a copy of $F_2$. Since a subgroup of an amenable group is amenable, an amenable group cannot contain this nonamenable subgroup. The amenability of a free product therefore yieldsfor nontrivial finitely generated $G$.