Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 5 (Geometric Group Theory)

Use the homotopy lifting theorem for a covering map: a homotopy of paths has a unique lift once its initial path is lifted. Also use uniqueness of lifts to a covering space: a lift of a constant path with a specified starting point is constant.

Let $\tilde{\gamma }$ be a loop based at ${\tilde{x}}_0$ whose image under $p_{\ast }$ is trivial. There is a homotopy $F:I\times I\to X$ from $p\tilde{\gamma }$ to the constant loop at $x_0$, fixing both endpoints. Lift this homotopy with initial path $\tilde{\gamma }$. Both vertical boundary paths are constant lifts at ${\tilde{x}}_0$. Its final path is a lift of the constant loop and hence is also constant at ${\tilde{x}}_0$. Thus the lifted homotopy contracts $\tilde{\gamma }$ relative to its endpoints. The kernel of the induced group homomorphism is trivial, provingNo universal-cover assumption is needed for this injection; it holds for any actual covering map.

For the classical subgroup-covering construction, assume $X$ is path-connected, locally path-connected, and semilocally simply connected. These are the usual hypotheses underlying the classification of connected covering spaces; an arbitrary space, as literally allowed by the wording, need not admit every subgroup covering.

Construct the path-class construction of a subgroup covering directly. Consider paths $\alpha$ starting at $x_0$, and identify $\alpha ,\beta$ when they have the same endpoint and the loop class $[\alpha {\beta }^{-1}]$ belongs to $H$. The subgroup properties make this an equivalence relation. Let $Y$ be its set of classes and define $p([\alpha ])=\alpha (1)$.

Choose a path-connected open neighbourhood $U$ of $\alpha (1)$ whose loops become null-homotopic in $X$. Such neighbourhoods form a local basis under the stated local hypotheses. Define a sheetFor each point of $U$ the resulting class is independent of the chosen path $\eta$, since the difference is a loop in $U$, conjugated by $\alpha$, and is trivial in ${\pi }_1(X,x_0)$. Thus $p$ maps this sheet bijectively onto $U$. Give $Y$ the topology generated by these sheets. Restrictions to smaller such neighbourhoods show that the sheets form a basis and that their endpoint maps are homeomorphisms. Two sheets over $U$ that intersect coincide, by concatenating and reversing paths within $U$; otherwise they are disjoint. Therefore $p^{-1}(U)$ is a disjoint union of copies of $U$, and $p$ is a covering map.

The basepoint is the class of the constant path. The path $\alpha$ lifts to its successive prefix classes, giving a path from this basepoint to $[\alpha ]$; hence $Y$ is path-connected. A loop $\gamma$ lifts closed exactly when its final prefix class agrees with the constant class, namely when $[\gamma ]\in H$. Consequently $p_{\ast }({\pi }_1(Y))=H$. Part (i) supplies injectivity, so

The missing local hypothesis is substantive. In the Hawaiian earring, every neighbourhood of the common basepoint contains a whole sufficiently small circle. Its loop is nontrivial in the whole space, since retracting onto that circle preserves it. An evenly covered neighbourhood would lift that loop to a closed loop in one sheet, so the image subgroup of any covering contains a nontrivial element. Therefore the trivial subgroup cannot be realized by a simply connected covering of this space. The intended result is valid under the local covering-space hypotheses above, not for every topological space.

Let $F$ be the free group on a set $A$. Form the rose $R_A$, a topological graph with one vertex and one oriented loop for each generator. Reading edge labels identifies ${\pi }_1(R_A)$ with $F$: cancellation of an edge followed by its reverse is exactly free reduction. This also applies to an infinite generating set, using the graph's CW topology rather than an accumulation topology.

Apply the subgroup-covering construction to obtain a connected covering graph $Y\to R_A$ with ${\pi }_1(Y)\cong H$. Choose a spanning tree $T\subseteq Y$ and a base vertex $v_0$. For every edge $e\notin T$, choose one orientation and form the loop consisting of the unique tree path from $v_0$ to the initial vertex of $e$, the edge $e$, and the unique tree path back from its terminal vertex.

These loops generate ${\pi }_1(Y)$. Indeed, in any edge loop insert the tree paths to and from the base vertex between consecutive edges. A tree edge contributes a contractible loop; a non-tree edge contributes the chosen loop or its inverse. They are freely independent as well: reducing an edge path cancels backtracking, and, after suppressing the tree portions, a nonempty freely reduced word in the oriented non-tree edges cannot disappear. Equivalently, collapsing the tree gives a rose whose petals are precisely the non-tree edges, and the same edge-path reduction identifies its fundamental group with the free group on those petals.

Thus ${\pi }_1(Y)$ is free, and its isomorphism with $H$ proves the Nielsen–Schreier theorem:The non-tree edges may be infinite in number; the argument does not require $H$ to have finite index or be finitely generated.

A quasi-isometry $f:X\to Y$ has constants $\lambda \ge 1$, $ϵ\ge 0$ such thatfor all $x,x^{\prime }$, and every $y\in Y$ is within $ϵ$ of some point of $f(X)$. One may use a separate coarse-surjectivity constant and enlarge $ϵ$ to include it. No continuity is required.

Choose $f^{\prime }(y)\in X$ with $d_Y(f(f^{\prime }(y)),y)\le ϵ$. The triangle inequality givesCombining this with the distortion inequalities for $f$ yieldsAlso $d_Y(f(f^{\prime }(f(x))),f(x))\le ϵ$, so the lower distortion inequality gives $d_X(f^{\prime }(f(x)),x)\le 2\lambda ϵ$. Hence every point of $X$ is within $2\lambda ϵ$ of the image of $f^{\prime }$. Taking the larger common error constant shows that $f^{\prime }$ is a $(\lambda ,3\lambda ϵ)$ quasi-isometry. It is a quasi-inverse of a quasi-isometry; both composites are uniformly close to their respective identities.

For a finite generating set $A$, use the symmetric alphabet $\Sigma =A\cup A^{-1}$. The Cayley graph has a vertex for each $g\in G$ and an oriented edge labelled $a$ from $g$ to $ga$. Give every edge length one. Its vertex word metric isTwo finitely presented groups are quasi-isometric when their Cayley graphs, with these path metrics, are quasi-isometric. The choice of finite generating set is immaterial, as the following proof shows; the relators identify vertices but do not otherwise enter the metric definition.

Given finite generating sets $A,B$ of the same group, put $L=\max (1,{\max }_{a\in A^{\pm 1}}|a{|}_B)$ and $M=\max (1,{\max }_{b\in B^{\pm 1}}|b{|}_A)$. Replace each letter in a shortest $A$-word by a fixed $B$-word to obtain $|g{|}_B\le L|g{|}_A$. Reversing the roles gives $|g{|}_A\le M|g{|}_B$. Therefore the vertex identity map satisfiesIt is onto, and hence a quasi-isometry. Map each edge to the fixed word path for its label, or pass through the uniformly dense vertex sets, to obtain the corresponding graph quasi-isometry with a bounded additive error. This proves equivalence of finite word metrics and independence of the two finite group presentations.

Choose representatives $T$ of the right cosets $Hg$, including $1$, and let $M={\max }_{t\in T}|t{|}_A$. This is finite because the index is finite. For $t\in T$ and $a\in A^{\pm 1}$, let $\overline{ta}\in T$ represent $Hta$. The elementsform a finite generating set $S$ for $H$, after adjoining inverses and discarding identities. To see generation rather than merely quote Schreier's lemma, write $h=a_1\cdots a_n$ and let $t_i$ represent $H{a}_1\cdots a_i$. Then $t_0=t_n=1$ andEach factor is a Schreier generator. For a shortest $A$-word this gives $|h{|}_S\le |h{|}_A$. Conversely every Schreier generator has $A$-length at most $2M+1$, so $|h{|}_A\le (2M+1)|h{|}_S$. Hence the inclusion $H\hookrightarrow G$ obeysEvery $g\in G$ can be written $g=ht$, and $d_A(g,h)=|t{|}_A\le M$. Thus the inclusion is coarsely onto and is a finite-index subgroup quasi-isometry.

Only finite generation of $G$ was needed for the metric argument. Under the given finite-presentation hypothesis, $H$ is also finitely presented: the corresponding finite-sheeted cover of a finite presentation complex has finitely many cells, and a spanning-tree reduction of its one-skeleton gives a finite group presentation. Therefore it belongs to the class of groups used in part (ii).

An algorithm is a finite effective procedure on finitely encoded inputs; a Turing machine is one precise model. A decision algorithm must halt on every permitted input and answer correctly. An algorithmic problem specifies the input encoding and the required output; enumerating positive answers alone is not a decision algorithm.

For a fixed finite group presentation $\mathcal{P}=⟨A\mid R⟩$, the word problem for a group takes a finite word in $A^{\pm 1}$ and asks whether it represents the identity. Equality of two represented elements is equivalent to testing $u^{-1}v$. Positive answers are recursively enumerable: enumerate finite products of conjugates of relators and their inverses, freely reduce them, and compare with the input. Equivalently enumerate finite labelled disc diagrams. The van Kampen lemma ensures that every null word eventually appears. For a non-null word this search continues forever. Solvability requires a procedure that also terminates with a negative answer.

For a null word $w$, define its area as the least number of conjugates of defining relators or their inverses whose product is $w$ in the free group. By the van Kampen lemma, this is also its minimum number of relator faces in a disc diagram. The Dehn function isThe maximum is finite because there are finitely many words of bounded length. An isoperimetric function of a group presentation is a nondecreasing upper bound on ${\delta }_{\mathcal{P}}$. Here subrecursive means bounded above by a total computable function, not merely recursively enumerable.

Suppose ${\delta }_{\mathcal{P}}(n)\le F(n)$ with $F$ computable. Let $\ell$ be the maximum relator length, taking $\ell \ge 1$ even if there are no relators. A minimum-area diagram for a boundary word of length $n$, with at most $N$ faces, can be chosen with no unnecessary tree branches. Every remaining edge occurs on a face boundary or the outside boundary, so there are at most $\ell N+n$ edges. Thus only finitely many combinatorial planar diagrams of area at most $N$ and this edge bound exist. Their finite edge labels and face labels can be enumerated, and the planar contractible diagram topology (allowing boundary spurs and pinched vertices), relator face boundaries and outside boundary word can be checked by finite combinatorial operations.

For the input $w$, compute $N=F(|w|)$ and inspect all these diagrams. Answer yes if one has boundary $w$, and no otherwise. The diagram bound and van Kampen lemma prove correctness, including the negative answer. This finite search avoids the invalid attempt to bound area while allowing unbounded conjugating words.

Conversely, suppose a word problem decider is available. For each $n$, enumerate the finitely many words of length at most $n$ and use the decider to identify exactly the null words. For each such word search diagrams in increasing area, with the finite edge bound just given at each area. The search terminates, and the first successful area is its minimum area. Taking the maximum of these finitely many minima computes ${\delta }_{\mathcal{P}}(n)$. This proves the recursive area bounds and the word problem equivalence:In fact, for finite group presentations, a word decider computes the minimal Dehn function itself.

The required quasi-isometry is the identity on the group vertices. For each $a\in A$ choose a fixed $B$-word $T(a)$ representing it and map an $a$-edge to that word path. The bounded substitutions in Q2(ii) prove the distortion inequalities.

For the area comparison, choose a reverse substitution $U$ sending each $b\in B$ to an $A$-word. Let $L$ bound the lengths of $T(a)$. Every word $U(s)$ for a defining relator $s\in S$ is null over the first group presentation. Since there are finitely many such words, their areas have a common bound $C$. Similarly every generator correction $a(UT(a){)}^{-1}$ has area bounded by a constant $D$; include inverses in this bound.

Let $w$ be null over $A$ with length at most $n$. Its substituted word $T(w)$ has length at most $Ln$ and a diagram of area at most ${\delta }_B(Ln)$. Replace each $B$-edge by its $U$-path. Each original relator face can then be filled over $A$ using at most $C$ faces, so $UT(w)$ has area at most $C{\delta }_B(Ln)$. Attach the correction strips changing its letters back to those of $w$, at cost at most $Dn$. ThereforeThe reverse substitutions give the corresponding inequality for ${\delta }_B$. Enlarging the constants to the single constant in the paper's comparison proves ${\delta }_A{\sim }_e{\delta }_B$. This is Dehn functions under a change of finite presentation.

Two qualifications are necessary for the printed continuation. The invariant is the optimal isoperimetric function, namely the Dehn function, not arbitrary upper bounds. For example, the relator-free group presentation of $\mathbb{Z}$ has zero area on all null words, so both $n$ and $2^n$ are isoperimetric upper bounds for that same group presentation; they are not equivalent under ${\sim }_e$.

Also, the comparison supplies no recursive bound unless one was available beforehand. Its actual consequence, by part (ii), isThe unconditional assertion that every finitely presented group has a solvable word problem is false. Finitely presented counterexamples are established in the primary paper The Word Problem. Thus the missing solvability premise cannot be inferred from group presentation equivalence alone.

Work with a finite symmetric alphabet $\Sigma =A^{\pm 1}$. If $w=a_1\cdots a_m$, its path $\hat{w}$ starts at $1$, visits $a_1\cdots a_j$ at integer time $j$, travels at unit speed along the intervening generator edges, and stays at its endpoint for $t\ge m$.

Two such paths synchronously $K$-fellow travel ifAn asynchronous version permits increasing time reparametrizations. Checking all integer times suffices after a bounded enlargement of $K$ for the edge interiors.

A combing of a group chooses a representative word $\sigma (g)$ for every $g$, with $\sigma (1)$ empty. A synchronous combing has a uniform constant $K$ such that representatives with adjacent endpoints satisfy the synchronous fellow-traveller property. A group admitting this is a synchronous combable group. The formal language need not be regular or computable. A regular language of representatives satisfying the synchronous condition instead gives an automatic group. This distinction is relevant to the finite-state automata request in part (iii); the present argument uses the synchronous meaning throughout. The definitions and distinction are also made explicitly in Combings of Groups and the Grammar of Reparameterization, Section 1.

Take an integer $K\ge 1$ bounding synchronous distances at integer times. Let $R_K$ be all words over $\Sigma$ of length at most $2K+2$ that represent the identity in $G$. This is a finite set. We claim that $⟨\Sigma \mid R_K⟩$ presents $G$, interpreting inverse letters in the usual way.

To prove it, let $w=a_1\cdots a_n$ be any null word and let $g_i=a_1\cdots a_i$, with $g_0=g_n=1$. Draw the combing paths $\sigma (g_i)$ as vertical columns, completed paths being padded by stationary steps. At each integer height join consecutive columns by a rung labelled by a word of length at most $K$ representing their displacement. At the bottom choose empty rungs, and at a common final height choose the actual boundary letters $a_i$ as rungs.

Every elementary strip cell has two rungs of length at most $K$ and two vertical steps of length at most one. Its boundary word has length at most $2K+2$ and is null in $G$, because the four paths close in the actual Cayley graph. It is therefore a relator in $R_K$. Gluing all cells fills the top loop $w$: the bottom row and the two copies of the identity column collapse to the basepoint. Thus every null word is a product of conjugates of these finitely many short relators. The reverse containment holds because each relator is already an identity in $G$.

Hence the finite presentation from a synchronous combing provesThis is an existence proof of a finite relator set. It does not assume an algorithm for identifying identities in an arbitrary group presentation before establishing decidability.

First construct the bounded-difference automaton. Fix $K$ as above, enlarging it if necessary. Its states are the finitely many elements $d\in B_K(1)$, together with a reject state and finite flags recording when padding has started on each tape. The initial state is $1$. Read the pair of words synchronously, padding their ends with a symbol $\#$ representing the identity. If the current prefixes represent $g,h$, the difference state is $d=g^{-1}h$. A letter pair $(u,v)$ updates it byReject if the new difference lies outside $B_K(1)$; padding must occur only in the final suffix of a tape. The accepting state for the generator $a$ is $d=a$. Induction on the prefix length proves that the machine accepts exactly the padded pairs whose prefix differences stay bounded by $K$ and whose final difference is $a$. In particular it correctly recognizes multiplication by $a$ for any pair of the chosen combing representatives with adjacent endpoints. Taking accepting state $1$ gives the equality machine.

If the combing formal language $L$ is regular, take the product with its two word acceptors. These are the usual group multiplier automata, accepting exactly $(w_1,w_2)\in L^2$ with ${\overline{w_1}}^{-1}\overline{w_2}=a$. From a known representative $u\in L$, a finite-state automaton search with its first tape fixed finds a representative $v$ of $\overline{u}a$: existence is guaranteed, so the breadth-first search terminates. Equality is tested by the identity multiplier. Starting with a representative of $1$, repeat these operations over the generators, identifying equal vertices, to build any prescribed finite-radius region of the Cayley graph and all its generator-labelled edges. Iterating multiplication over an input word and testing equality with the identity gives a word problem algorithm.

A bare geometric combing does not imply that $L$ is a regular language. Nor can a finite-state automaton recognize the indicated endpoint relation on all words without any restriction: in $\mathbb{Z}=⟨a⟩$, which has its usual geodesic synchronous combing, fixing the second word to $a$ would make the multiplier for $a$ recognize precisely the first words equal to the identity. Intersecting those words with $a^{\ast }(a^{-1}{)}^{\ast }$ gives $\{a^n(a^{-1}{)}^n:n\ge 0\}$, a nonregular language: pumping the initial block changes its exponent without changing the inverse block, contradicting acceptance of precisely the equal exponents. Thus the literal unrestricted-pair request is false; the machines above recognize bounded fellow-travelling pairs, or full representative-pair relations under the additional automatic-language hypothesis.

Nevertheless the final decidability assertion is true for a synchronous combable group, without a regular-language assumption. Here is a terminating filling bound, avoiding any assumption that the given combing is computable. Let $D$ be the number of words of length at most $K$ over $\Sigma$. A horizontal row of the diagram in part (ii) is encoded by its ordered $n$ rung words, so there are at most $D^n$ possible row types. If two rows have the same word tuple, delete the band between them and identify corresponding labelled rungs. This preserves the outside boundary and leaves a valid diagram of the same short relators. Equivalently, the first column is always at $1$, so identical rung tuples describe the same vertex configuration. Repeatedly remove such bands. At most $D^n$ distinct rows remain, with at most $n$ short-relator cells per layer.

This finite-state row shortening of a combing diagram gives the recursive bound ${\delta }_{R_K}(n)\le n(D^n+1)$. For the given finite group presentation, every short identity in the finite set $R_K$ has some fixed diagram over its defining relators. Let $C$ bound their areas. Replacing each short face by its fixed diagram givesPart 3(ii) now supplies a terminating word decider. This also constructs finite Cayley graph regions for a nonregular combing: enumerate words of bounded length, use the decider on $u^{-1}v$ to identify vertices, and use it on $u^{-1}v{a}^{-1}$ to determine the generator edges. The finite ball $B_K(1)$ and transition table of the bounded-difference machines can consequently be computed. The constants depend on a fixed combing and are not a uniform procedure certifying combability of an arbitrary input group presentation. Every finite group presentation of this synchronous combable group has solvable word problem, by the presentation-invariance proof in Q3.

For a finite symmetric generating alphabet $\Sigma$, the growth function of a finitely generated group isIt counts distinct elements, not words. Relations affect which words coincide, while the resulting coarse growth type is independent of the finite generating set.

Let $f:G\to H$ be a quasi-isometry between the vertex word metrics, with constants $\lambda ,ϵ$. A quasi-isometry of the metric graphs can be rounded to vertices with only bounded changes of these constants. If $f(g)=f(g^{\prime })$, its lower distortion bound gives $d_G(g,g^{\prime })\le \lambda ϵ$. Thus every nonempty fibre has at most $M={\beta }_G(\lceil \lambda ϵ\rceil )$ elements, independently of its centre. Also $f(B_G(1,n))$ lies in the ball of radius $\lambda n+ϵ$ about $f(1)$. Left translation in $H$ preserves ball cardinalities, soApply the same argument to a quasi-inverse of a quasi-isometry to get the reverse comparison. Enlarging all constants to an integer $K$ gives the two inequalities required by the paper's $\lesssim$ relation, and therefore ${\beta }_G{\sim }_e{\beta }_H$. This proves quasi-isometry invariance of the stated growth class.

For the exponential upper bound, put $q=|\Sigma |$. Every element in the radius-$n$ ball has a representative of length at most $n$. Hencewhere the last inequality follows by comparison with the binomial expansion of $(q+1{)}^n$; it also holds for the empty alphabet of the trivial group. Thus every finitely generated group has at most exponential growth, with no finite-relator assumption needed.

Use the standard coordinate generators of ${\mathbb{Z}}^d$. Its word metric is the ${\ell }^1$ metric, so its radius-$r$ ball consists of integer points satisfying ${\sum }_i|x_i|\le r$. For $d\ge 1$ it contains the cube $|x_i|\le \lfloor r/d\rfloor$ and is contained in the cube $|x_i|\le r$. Thusand its growth is bounded above and below by constant multiples of $r^d$ for large $r$.

If ${\mathbb{Z}}^n$ and ${\mathbb{Z}}^m$ are quasi-isometric, part (i) gives equivalent growth functions of a finitely generated group. For positive $n>m$, the required comparison $r^n\lesssim r^m$ would bound a positive constant times $r^n$ by $O(r^m+r)$, impossible as $r\to \infty$. Interchanging $n,m$ rules out $m>n$. Hence $n=m$. Conversely, for equal dimensions the identity is an isometry with standard generators; changing finite generators preserves quasi-isometry by Q2(ii). ThereforeIf dimension zero is allowed, ${\mathbb{Z}}^0$ is bounded and cannot be quasi-isometric to an unbounded positive-dimensional lattice. This boundedness argument is needed because the additive linear term in ${\sim }_e$ makes constant and linear growth functions of a finitely generated group equivalent; growth equivalence alone would not distinguish dimensions zero and one.

The answer is exponential growth in the paper's coarse-equivalence sense. Here are direct upper and lower bounds, avoiding an unsupported appeal to distortion.

Represent the generators by affine maps of the real line: $y(t)=t+1$ and $x(t)=t/3$. Then $x^{-1}yx(t)=t+3=y^3(t)$, so the defining relator is respected. In particular $y$ has infinite order: its distinct integral powers have distinct translation images.

Given $k$ digits $d_j\in \{0,1,2\}$, define $m_0=0$, $m_{j+1}=3m_j+d_{j+1}$ and $W_0$ empty, $W_{j+1}=x^{-1}{W}_{j}x{y}^{d_{j+1}}$. Induction using the relation shows $W_j=y^{m_j}$ in the group. Each step increases word length by at most four, so $|W_k|\le 4k$. The digit strings yield precisely all integers $0\le m_k<3^k$, and their corresponding group elements are distinct. ThereforeFor the upper bound, in the four-letter symmetric alphabet $\{x,x^{-1},y,y^{-1}\}$ there are at most $4\cdot 3^{j-1}$ freely reduced words of length $j\ge 1$. Every element of the ball has such a representative, givingThese bounds prove the exponential growth of the ternary affine Baumslag-Solitar group and show $\beta {\sim }_e(n\mapsto 2^n)$, since positive exponential bases and constant rescalings of the argument give the same coarse class. This determines its growth under the convention of the question; it does not assert an exact cardinality formula for every radius.