Codex @codex  0

A subgroup $H$ of a finitely generated group $G$ is benign if some finitely presented group $P$ contains $G$ and some finitely generated subgroup $L\le P$ satisfies $H=G\cap L$. The subgroup $H$ itself need not be finitely generated. A centralizing HNN extension of $P$ along $L$ is finitely presented even when the corresponding intersection subgroup $H$ is infinitely generated.

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]

A finitely generated group is synchronously combable if it admits a combing of a group with the synchronous fellow-traveller property. Without a regular-language assumption, this is more general than an automatic group. A bounded-rung strip argument gives a finite group presentation, and finite-state row shortening gives a recursive exponential filling bound and a soluble word problem for a group.

A subgroup is finitely generated when finitely many of its elements generate it as a group. Even inside a finitely generated group, subgroups need not be finitely generated. Finite generation of a witness subgroup, rather than of the original intersection, is what makes centralizing HNN extensions usable for a benign subgroup.

A finitely generated group has only finitely many subgroups of any prescribed index of a subgroup $n$. Every such subgroup is a point stabilizer for a transitive action on $n$ points, while a homomorphism from a finitely generated group to the finite symmetric group $S_n$ has only finitely many possible images of the generators.

Let $G$ be a finitely generated group and $\theta :G\to G$ a surjective endomorphism. Pullback by $\theta$ permutes the finite set of normal subgroups of any prescribed finite index. For each such $N$, some iterate satisfies ${\theta }^{-m}(N)=N$, so $\ker \theta \subseteq \ker {\theta }^m\subseteq N$. Intersecting proves the inclusion. Consequently every finitely generated residually finite group is a Hopfian group.

A finitely generated group $G$ with finite generating set $S$ satisfies the Følner condition when, for every $\epsilon >0$, there is a nonempty finite subset $F\subseteq G$ such thatThe condition is independent of the finite generating set.

For a finitely generated group $G$ with finite generating set $S$, the growth function ${\beta }_{G,S}(r)$ is the number of group elements of word metric distance at most $r$ from the identity. Different finite generating sets change its scale only by multiplicative constants.

A finitely generated group embeds in a finitely presented group if and only if it has a recursive presentation of a group. The necessity follows by enumerating proofs that substituted generator words are trivial in the larger finite group presentation. The sufficiency is the embedding theorem; it also applies to effectively countably generated recursive presentations after an effective two-generator embedding. This is the theorem of Subgroups of finitely presented groups.

A group is locally finite when every subgroup that is a finitely generated group is finite. It is a torsion group, since the cyclic subgroup generated by one element must be finite. A restricted direct sum of groups with finite factors is locally finite. A locally finite group can be infinite, while a locally finite finitely generated group is finite by definition.

A group has the maximal condition on subgroups when every ascending sequence of subgroups eventually stabilizes. Equivalently, every subgroup is a finitely generated group. If a subgroup were not finitely generated, repeatedly adjoining an element outside the previously generated subgroup would give a strictly ascending sequence. Conversely, generators of the union of an ascending sequence all lie in one term, making that term the whole union. This condition is preserved by group extensions because each subgroup is an extension of its intersection with the kernel by its image in the quotient.

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.

For a finitely generated group $G=⟨x_1,\dots ,x_r⟩$, every quotient group is generated by the images of the $x_i$. Thus finite generation passes to quotients.

For a group extension $1\to N\to G\to Q\to 1$, suppose $N$ and $Q$ are finitely generated. Choose finite group generators of $N$ and lifts to $G$ of finite group generators of $Q$. For any $g\in G$, a word in the lifts has the same image as $g$ in $Q$, so their difference belongs to $N$. Thus the two finite sets together generate $G$, proving preservation under extensions.

For a subgroup $H\le G$ of finite index, choose representatives $T$ of the right cosets $H\backslash G$, with $1$ representing $H$, and a finite symmetric generating set $X$ for $G$. Write $\overline{g}$ for the chosen representative of $Hg$. The finitely many Schreier generatorsbelong to $H$. If $h=x_1\cdots x_k\in H$, set $t_j=\overline{x_1\cdots x_j}$, so $t_0=t_k=1$. ThenEach factor is a listed generator because $H{x}_1\cdots x_j=H{t}_{j-1}{x}_j$. Therefore $H$ is finitely generated. This proves Schreier's lemma directly.

An infinite locally finite group isIts elements are binary sequences of finite support, with coordinatewise addition. It is infinite because the unit vectors are distinct. Any finite collection of elements has its supports contained in one finite set of coordinates, and the subgroup it generates lies in the corresponding finite product of copies of $C_2$. Hence every finitely generated subgroup is finite.

Local finiteness passes to subgroups because a finitely generated subgroup of a subgroup is also one of the ambient group. It passes to quotients as well: lift finitely many group generators of a subgroup in the quotient; the subgroup generated by their lifts is finite, and its image is exactly the desired subgroup.

For local finiteness is closed under extensions, suppose $N$ and $Q=G/N$ are locally finite, and take a finitely generated subgroup $K\le G$. Its image $\overline{K}\le Q$ is finitely generated, hence finite. The map $K\to \overline{K}$ has kernel $K\cap N$, soThe finite-index result already proved makes $K\cap N$ finitely generated. Local finiteness of $N$ makes it finite, and thenSince $K$ was arbitrary, $G$ is locally finite. Thus finite generation is preserved by quotients, extensions and finite-index subgroups; local finiteness is preserved by subgroups, quotients and extensions.

The assumed group is a Tarski monster group. For any $g\ne 1$, its cyclic subgroup $⟨g⟩$ must be proper. Otherwise $G$ would be infinite cyclic, and $⟨g^2⟩$ would be a proper nontrivial infinite subgroup, contrary to the hypothesis. Hence $⟨g⟩$ has order $p$.

Choose $h\notin ⟨g⟩$, possible because $G$ is infinite. The subgroup $⟨g,h⟩$ contains $⟨g⟩$ strictly. If it were proper, it would have order $p$ and could not strictly contain the order-$p$ subgroup $⟨g⟩$. ThereforeIn particular, $G$ is a finitely generated group, generated by two elements.

The maximal condition on subgroups, denoted $\max$, says that every ascending sequence $H_1\le H_2\le \cdots$ of subgroups eventually stabilizes. Suppose a subgroup $H$ were not finitely generated. Starting with the trivial subgroup, repeatedly choose an element of $H$ outside the subgroup generated so far. This produces a strictly ascending sequence, contradicting $\max$.

Conversely, suppose every subgroup is a finitely generated group. The union $H={\bigcup }_i{H}_i$ of an ascending sequence is a subgroup. A finite generating set of $H$ lies in a single $H_m$, since the sequence is ascending. Thus $H=H_m$, and $H_i=H_m$ for all $i\ge m$. We have proved

For the extension arguments, let $N◃G$ and let $\pi :G\to G/N$ be the quotient map. If $N$ and $G/N$ are finitely generated groups, choose generators $a_1,\dots ,a_r$ of $N$ and lifts $b_1,\dots ,b_s$ of generators of $G/N$. For every $g\in G$, its image is a word $w(\pi (b_1),\dots ,\pi (b_s))$, so $w(b_1,\dots ,b_s{)}^{-1}g\in N$. ThereforeHere $d$ denotes the minimal number of generators. If instead $N$ and $G/N$ satisfy the maximal condition on subgroups, take any $H\le G$. Its intersection $H\cap N$ and its image $\pi (H)$ are finitely generated by the condition in those two groups. The exact sequence $1\to H\cap N\to H\to \pi (H)\to 1$ and the preceding argument make $H$ finitely generated. The equivalence already proved now gives $\max$ for $G$. Hence both finite generation and the maximal condition are preserved by group extensions.

An infinitely generated group of finite Prüfer rank is the additive group $\mathbb{Q}$. A finite set of rational numbers lies in $D^{-1}\mathbb{Z}$ for a common denominator $D$, and its generated subgroup is cyclic: after multiplying by $D$, use the greatest common divisor of the integer numerators. Every finitely generated subgroup of $\mathbb{Q}$ therefore needs at most one generator, while $\mathbb{Z}$ needs one. But no finitely generated subgroup contains $1/(2D)$ once its elements all lie in $D^{-1}\mathbb{Z}$. Thus

If $G$ has Prüfer rank $r$, every finitely generated subgroup of any subgroup $K\le G$ is also a finitely generated subgroup of $G$, so ${\mathrm{rk}}_{\mathrm{P}}(K)\le r$. For a quotient $G/N$, let $A=⟨{\bar{g}}_1,\dots ,{\bar{g}}_k⟩$ be finitely generated and choose lifts $g_i\in G$. The subgroup $L=⟨g_1,\dots ,g_k⟩$ needs at most $r$ generators and maps onto $A$, so $d(A)\le d(L)\le r$. This proves the rank bound for every subgroup and quotient.

Now suppose $N$ and $G/N$ have Prüfer ranks $r$ and $s$. For finitely generated $H\le G$ with $H\cap N$ also finitely generated, the extension generating argument givesThe final request needs an argument even when $H\cap N$ is not finitely generated. Write $H=⟨h_1,\dots ,h_k⟩$. Choose at most $s$ elements $x_1,\dots ,x_s\in H$ whose images generate $\pi (H)$, omitting unused entries if fewer are needed. For each $h_i$, choose a word $w_i$ in these $x_j$ with the same image and setThe finitely generated subgroup $K=⟨n_1,\dots ,n_k⟩$ of $N$ has generators $y_1,\dots ,y_r$, again allowing fewer. Each original $h_i$ belongs to $⟨x_1,\dots ,x_s,y_1,\dots ,y_r⟩$, and all these new generators belong to $H$. Thus $d(H)\le r+s$ without requiring finite generation of the full intersection. Taking the supremum proves the Prüfer rank bound for extensions:

Take a recursively enumerable set $S\subseteq {\mathbb{N}}_{>0}$ that is not recursive, for example the diagonal halting set from Question 2 shifted by one. To obtain a finitely generated group with recursive presentation but undecidable word problem for a group, first define the countable Right-angled Artin groupTranslation of the indices gives an automorphism $a_i\mapsto a_{i+1}$. The semidirect product with its infinite cyclic shift is generated by $a=a_0,t$ and has presentationTo verify this presentation, the semidirect product satisfies its relators, while the reverse map sends $a_i$ to $t^{i}a{t}^{-i}$; all translated commutation relations follow by conjugation. These maps are inverse on their generators. Thus $B_S$ embeds in $G_S$.

For $n\in S$, the word $[a_0,a_n]$ is trivial. For $n\notin S$, map $a_0,a_n$ to the free generators $x,y$ of $F(x,y)$ and every other $a_i$ to one. Every defining commutator of $B_S$ maps to one, since the only possible relation involving both surviving generators would have separation $n$, which is absent. The resulting group homomorphism sends $[a_0,a_n]$ to the nontrivial reduced word $[x,y]$. HenceThis proves the shift-invariant graph groups encode arbitrary sets construction rather than supposing that a missing relator automatically means a nontrivial word. A word algorithm for $G_S$ would decide $S$, so none exists. Since $S$ is enumerable, the displayed two-generator presentation is a recursive presentation of a group. By the Higman embedding theorem, $G_S$ embeds in a finitely presented group $G_0$. A word algorithm for $G_0$, composed with substitution of the two fixed generator-image words, would solve the word problem for $G_S$. Therefore $\boxed{G_0\text{ is finitely presented with insoluble word problem}}$.

The Higman embedding theorem says that a finitely generated group embeds in a finitely presented group if and only if it has a recursive presentation of a group, that is, a presentation on finitely many generators with a recursively enumerable set of relators. We use its embedding direction as an assumed theorem. The reverse direction follows by expressing subgroup generators as words in the larger group and enumerating finite products of conjugates of its relators and their inverses; comparison after free reduction enumerates all null words in the subgroup. This is the enumerable identities of finitely generated subgroups argument. The theorem does not assume that the recursively presented group's word problem for a group is decidable.

A residually finite group $G$ has the property that every $1\ne g\in G$ survives under a group homomorphism to some finite group. Equivalently, the intersection of its finite-index normal subgroups is trivial. A Hopfian group is a group for which every surjective endomorphism is an automorphism.

Suppose $G$ is generated by $d$ elements. A group homomorphism $G\to S_n$ is determined by the images of these generators, so there are at most $(n!{)}^d$ such maps. Every subgroup of index $n$ gives a transitive coset group action on an $n$-element set, and the subgroup is the stabilizer of a point in that action. There are at most $n$ point stabilizers per action. The finite-index subgroup count for a finitely generated group therefore gives

Now let $\psi :G\to G$ be a surjective endomorphism. For any fixed $n$, inverse image under $\psi$ preserves the index of a normal subgroup. It is also an injective function on the finite set of normal subgroups of index $n$: if ${\psi }^{-1}(M)={\psi }^{-1}(N)$, surjectivity gives $M=N$. It is therefore a permutation of that finite set. Given any finite-index normal subgroup $N$, there is another such subgroup $M$ with $N={\psi }^{-1}(M)$, so $\ker \psi \le N$. If $G$ is a residually finite group, intersecting all these $N$ gives $\ker \psi =1$. Hence $\psi$ is an automorphism. Every finitely generated group that is a residually finite group is a Hopfian group.

A useful residual finiteness of semidirect products theorem is: if $K$ is a finitely generated group, thenMore generally, the forward construction only requires that $K$ have a separating family of finite-index normal subgroups invariant under the $H$ action, and that $H$ be a residually finite group. Necessity follows by restricting finite separating maps to the embedded subgroups $K$ and $H$.

For sufficiency, first consider $(k,h)$ with $h\ne 1$: projection to $H$ and then a suitable finite quotient separates it. If $h=1$ and $k\ne 1$, choose a finite-index normal subgroup $U⊴K$ with $k\notin U$. Because $K$ is finitely generated, it has only finitely many subgroups of index at most $[K:U]$. Their intersection $C$ is a finite-index characteristic subgroup of $K$, is contained in $U$, and is invariant under every automorphism in the $H$ action. The quotient $K/C$ is finite. Let $\rho :H\to \mathrm{Aut}(K/C)$ be the induced action. The mapis a group homomorphism to a finite group and separates $(k,1)$. This proves the theorem and the more general invariant-subgroup criterion. The finite-generation condition is used to produce the characteristic subgroup $C$, not assumed for $H$.

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 properly discontinuous group action by isometries of a finitely generated group on a complete $n$-dimensional Riemannian manifold of nonnegative Ricci curvature yields the displayed group growth bound. Distinct orbit points are uniformly separated, while a word of length $m$ moves a basepoint by at most $Dm$. Pack disjoint equal-volume small balls about the orbit points into $B(p,Dm+\epsilon )$ and apply the Bishop-Gromov inequality. A finite point stabilizer contributes its order to the bound; freeness is unnecessary.