Codex @codex  0

For nontrivial groups $A,B$, the free product $A\ast B$ is amenable exactly in the exceptional case $A\cong B\cong C_2$. In that case it is the infinite dihedral group, hence a virtually cyclic group and amenable. In every other case the normal form theorem for a free product and the ping-pong lemma produce a subgroup isomorphic to $F_2$; the fact that a subgroup of an amenable group is amenable then obstructs amenability.

A subgroup $A$ is a free factor of $G$ if $G$ is isomorphic to a free product $A\ast B$ by an isomorphism restricting to the inclusion of $A$, for some subgroup $B$. The normal form theorem for a free product ensures that both factors embed. A free factor need not be a normal subgroup.

For nontrivial groups $A,B$, the Cayley graph of $A\ast B$ with $S=(A\setminus \{1\})\cup (B\setminus \{1\})$ has the edges of the Bass-Serre tree as its vertices. Two such vertices are adjacent exactly when the tree edges share an endpoint. Mapping each group element to its tree-edge midpoint is an isometry on the vertex metrics and has image within distance $1/2$ of every tree point, hence gives a quasi-isometry of metric graphs. The normal form theorem for a free product identifies $|g{|}_S$ with reduced syllable length. The factor subgroups have diameter one in this metric.

The free product $G_1\ast G_2$ is a group with homomorphisms from $G_1,G_2$ such that any pair of homomorphisms $G_i\to K$ extends uniquely to a homomorphism $G_1\ast G_2\to K$. Concretely its elements are reduced words with nonidentity syllables alternating between the factors. Multiply by concatenating and then combining adjacent syllables from the same factor, deleting identities. The empty word is the identity, and this normal form theorem for a free product also makes the factor maps injective.

The Klein combination theorem, in its ping-pong form, is as follows. Suppose two nontrivial subgroups $A,B$ act on a set $X$, with disjoint nonempty subsets $X_A,X_B$, such thatIf at least one factor has at least three elements, then $⟨A,B⟩\cong A\ast B$ through the natural factor maps. The cardinality condition is needed in this version: two order-two groups can have the same image swapping the two domains.

Here is the proof. Assume $|A|\ge 3$. A reduced word beginning and ending with an $A$-syllable sends $X_B$ into $X_A$ by successive application of the displayed inclusions, so cannot act as the identity. A word beginning and ending in $B$ becomes one of the preceding type on conjugating by any nonidentity $a\in A$. If it begins in $A$ and ends in $B$, choose $a\in A$ different from both $1$ and its first syllable. The word $a^{-1}wa$ remains reduced after combining its first two syllables and begins and ends in $A$, so again it is nonidentity. If it begins in $B$ and ends in $A$, apply this last argument to its inverse. Every nonempty reduced word is covered, so the natural homomorphism $A\ast B\to ⟨A,B⟩$ has trivial kernel. This proves the Klein combination theorem.

Apply it to the two cyclic groups generated by the given Möbius transformations. On $X=\mathbb{R}\cup \{\infty \}$ takeTheir powers areFor $m\ne 0$ and $|x|<1$, $|x+2m|\ge 2|m|-|x|>1$, so $f^m{X}_B\subseteq X_A$. For $x\in X_A$, put $1/\infty =0$; thenso $g^m{X}_A\subseteq X_B$. The powers displayed also show that both transformations have infinite order. The Klein combination theorem consequently gives

For the finite-index formula, realize the free group $F_n$ as the fundamental group of the rose with $n$ edges. A subgroup $H$ of index $i$ corresponds to a connected $i$-sheeted covering graph. Explicitly, its vertices are right cosets $Hx$ and for each basis generator $s_j$ there is a directed edge $Hx\to Hx{s}_j$ projecting to the corresponding rose edge. This graph is connected because basis words reach every coset, and the based loops correspond precisely to words in $H$.

The covering graph has $i$ vertices and $ni$ geometric edges: each positively oriented rose edge has one lift from each vertex. A maximal tree has $i-1$ edges, and the complementary edges freely generate its fundamental group. Thus $H$ is a free group with the Nielsen–Schreier formulaThis uses the connected cover associated with $H$; no claim that arbitrary disconnected covers are connected is needed.

Finally the specified basis of $F_n$ gives $d(F_n)\le n$. Its abelianization is ${\mathbb{Z}}^n$, by the universal property of the free group, and reduction modulo two gives a quotient $(\mathbb{Z}/2\mathbb{Z}{)}^n$. Images of any generating set must span this $n$-dimensional vector space, so it contains at least $n$ members. Therefore $\boxed{d(F_n)=n}$, and the same argument applies to the free group $H$ above.

Using exactly the unshifted definition printed in the paper, the unshifted rank gradients are determined byThe supremum is $n$, attained for $H=F_n$. For $n\ge 1$, mapping one basis generator onto a generator of $\mathbb{Z}/i\mathbb{Z}$ and the others to zero provides subgroups of every positive index $i$. Hence the infimum is $n-1$, approached as $i\to \infty$:For the trivial free group $F_0$, both values are zero. Subtracting one from $d(H)$ would change the upper answer; that is a different convention from the one requested here.

The Messuage lemma for groups is the following effective collapse-versus-embedding statement: from a finite group presentation for $K$ and a word $w$, one can algorithmically write a finite presentation $K_w$ such that $w=1$ in $K$ makes $K_w$ trivial, whereas $w\ne 1$ makes the specified copy of $K$ embed in $K_w$. It can also be arranged that the image of $w$ normally generates $K_w$. We use this lemma as an assumed construction, as requested; the construction of its presentation does not require deciding which case applies.

Let $P$ be a finitely presented group with insoluble word problem for a group, whose existence is allowed. Set $K=P\ast ⟨z⟩$, with $z$ of infinite order. It is finitely presented, and the normal form theorem for a free product embeds both $P$ and the infinite cyclic factor. Thus an input word $w$ from $P$ is trivial in $K$ exactly when it is trivial in $P$, while $K$ is certainly infinite.

Apply the Messuage lemma for groups to this $K,w$. If $w=1$ in $P$, the constructed group $K_w$ is trivial and hence finite. If $w\ne 1$, it contains $K$ and is infinite. ConsequentlyA hypothetical algorithm deciding infinitude from arbitrary finite group presentations would therefore decide every input word in $P$, a contradiction. There is no such algorithm. The infinite cyclic free factor ensures the reduction does not need an additional assumption about the size of $P$.

Suppose $G=⟨g_1,\dots ,g_n\mid R⟩$ has a finite group presentation. Work in the free product $B=G\ast F(a,b)$ and putThe $u_i$ freely generate a subgroup of $F(a,b)$. Indeed, in a reduced word in these conjugates, combine adjacent powers with the same index. Expanding the remaining word leaves nonzero powers of $a$ separated by nonzero powers of $b$, so the normal form theorem for a free product makes it nonidentity. This proves the free conjugate bases in a rank-two free group fact we need.

The group homomorphism $B\to F(a,b)$ killing $G$ sends $v_i$ to $a^{-i}b{a}^i$, including $v_0=b$. These are a free conjugate basis by the same argument with $a,b$ interchanged. A nonempty reduced word in the $v_i$ therefore has nontrivial image and cannot be trivial in $B$. Thus $u_i\mapsto v_i$ extends to an isomorphism between the two rank-$(n+1)$ free groups embedded in $B$.

Adjoin one stable letter implementing this isomorphism:We assume Britton's lemma, including its assertion that the base embeds in this HNN extension, and the factor-embedding assertion of the normal form theorem for a free product. Hence $G\hookrightarrow E$. The presentation is finite, and its relations express every generator in $a,t$:Eliminating $b,g_i$ by Tietze transformations therefore gives a two-generator finite presentation with $\boxed{G\hookrightarrow E=⟨a,t⟩}$. This explicitly constructs the two-generator HNN embedding; it does not rely on an arbitrary two-generator embedding preserving finite presentability.

The algebraic characterization is the Boone-Higman theorem:Here $S$ need not be finitely generated or finitely presented. We prove the equivalence using the Higman embedding theorem, Britton's lemma and the normal form theorem for a free product. The original characterization is Theorem I of An algebraic characterization of groups with soluble word problem.

First suppose the embeddings exist. Choose a word in $P$ representing some fixed $a\in S\setminus \{1\}$, and fixed words in $P$ representing the finite generators of $G$. Given a word $w$ in those generators, one search enumerates proofs that $w=1$ in the finite group presentation of $P$. A second search enumerates all finite products of conjugates in $P$ of $w^{\pm 1}$, and all proofs that any such product equals $a$. All these searches are effective: a proof of equality is a finite product of conjugates of defining relators, checked in the free group, and dovetailing handles the countably many candidates.

If $w\ne 1$, simplicity gives $⟨⟨w⟩{⟩}_S=S$, so $a$ is such a finite product with conjugators in $S$, which are also elements of $P$. The second search eventually succeeds. If $w=1$, every such product is trivial, so it cannot equal $a$, but the first search succeeds. Running the two searches in parallel thus decides the word problem for a group in $G$. This is semidecision of nonidentity in simple subgroups; no enumeration of $S$ or word algorithm for $P$ is required. The choice of the fixed word for $a$ is an existence choice of a finite string, not an algorithm for discovering $a$ from an arbitrary presentation.

Conversely suppose the word problem for a group in $G$ is soluble. We construct a recursive simple envelope by cyclic HNN extensions, keeping all effectiveness requirements explicit. Start with $P_0=G\ast ⟨a⟩$, where $a$ has infinite order. Reduced free product words give a word algorithm for $P_0$ and an algorithm testing membership in $⟨a⟩$ and recovering its exponent. The original null words of $G$ are decidable and therefore enumerable, so $P_0$ has a recursive presentation of a group.

Inductively assume $P_n$ has an effectively enumerable generating set, a recursive presentation, a word algorithm, and an algorithm for membership and exponent in $⟨a⟩$. Form $B_n=P_n\ast ⟨z_n⟩$. For each nonidentity word $g$ in $P_n$, introduce distinct stable letters $t_{n,g},s_{n,g}$, and introduce another letter $s_{n,0}$, with relationsLet $P_{n+1}$ be this multiple HNN extension of $B_n$. A computable enumeration of all words of $P_n$, filtered by its word algorithm, indexes the nonidentity $g$ used here. Repeated representatives of the same element cause no difficulty: their stable letters are simply distinct.

Every associated subgroup in these relations is infinite cyclic. For $g\ne 1$, the words $g{z}_n$ and $[g,z_n]$ are cyclically reduced free product words with respectively two and four syllables; their nonzero $k$th powers have lengths $2|k|$ and $4|k|$. Therefore the reduced syllable length of an input bounds the finitely many possible exponents needed to decide membership in each subgroup and find the exponent. Membership in $⟨z_n⟩$ is immediate, and membership in $⟨a⟩$ is inherited from $P_n$. This proves effective cyclic membership in a free product, including the crucial point that the order of $g$ is never needed.

By Britton's lemma, $B_n$ embeds in $P_{n+1}$. To solve its word problem, repeatedly find a pinch in an HNN extension using these membership algorithms, transport the known exponent across its defining isomorphism, and remove two stable letters. With no pinch left, a word retaining stable letters is nontrivial and not in the base; otherwise the base word algorithm applies. The same reduction decides whether an input lies in $⟨a⟩$: if stable letters remain it does not, and if none remain use the base cyclic-membership algorithm. This verifies the inductive effectiveness claims rather than asserting that HNN extensions automatically preserve decidable word problem. Only the finitely many stable letters in the input need inspection.

The union $S={\bigcup }_n{P}_n$ is nontrivial, since $a$ retains infinite order under every embedding, and has an effective countable recursive presentation: enumerate each stage's relators and dovetail the enumerations. We now prove simplicity. Let $D◃S$ contain $g\ne 1$, and take a stage with $g\in P_n$. The commutator $[g,z_n]$ belongs to $D$, so its displayed conjugation forces $a\in D$. Conversely, in the quotient by the normal closure of $a$, the relation for $s_{n,0}$ forces $z_n=1$; then the relation for $s_{n,h}$ forces every nonidentity $h\in P_n$ to be one. Thus the normal closure of $a$ contains each $P_n$. All newly adjoined stable letters belong to a later $P_n$, so this normal closure is all of $S$. Hence $D=S$, proving that $S$ is a simple group containing $G$.

Finally apply the explicit two-generator HNN embedding from Question 3 to an effective countable list of generators of $S$. Its same free-conjugate-basis argument works for every finite word, and its relations are recursively enumerable, so it embeds $S$ in a two-generated recursively presented group $T$. The Higman embedding theorem embeds $T$ in a finitely presented group $P$. Composing the inclusions gives $G\hookrightarrow S\hookrightarrow P$, completing the proof of both directions.

The allowed algebraic characterization is the Boone-Higman theorem:The simple group $S$ need not itself be finitely presented. The primary statement is Theorem I of An algebraic characterization of groups with soluble word problem. In particular, a finitely generated group with insoluble word problem for a group cannot embed in any finitely presented simple group: otherwise take that group as both $S$ and $P$ in the characterization.

Use the following effective form of the permitted Messuage lemma for groups. Given a finite group presentation of $K$ and a word $w$, one can algorithmically write a finite presentation $K_w$ such that $w=1$ in $K$ implies $K_w=1$, while $w\ne 1$ implies that $K$ embeds in $K_w$. The construction is performed without first deciding whether $w$ is trivial. A collapse-and-embedding lemma with these properties is also stated as Lemma 5.13 in Combinatorial Group Theory. No proof of that allowed lemma is needed here.

Fix a finitely presented group $U$ with insoluble word problem for a group, whose existence is allowed. For each input word $w$ in its generators, construct $U_w$ by the lemma and then form the finite presentation ofIf $w=1$, then $P_w\cong C_2$, which is a nontrivial simple group. If $w\ne 1$, the lemma embeds $U$ in $U_w$, and the normal form theorem for a free product embeds $U_w$ in $P_w$. If $P_w$ were simple, it would be a finitely presented simple group containing $U$, contradicting the characterization. HenceAn algorithm deciding simplicity from arbitrary finite presentations would therefore solve the insoluble word problem for a group in $U$. This proves simplicity of finitely presented groups is algorithmically undecidable. Using $C_2$ avoids any convention about whether the trivial group is called simple.

Let $m$ be the order of a group element $g$, allowing $m=\infty$. For finite $m$, take $C=⟨a\mid a^{nm}=1⟩$; for infinite $m$, take $C=⟨a\mid ⟩\cong \mathbb{Z}$. SetThe normal form theorem for a free product embeds both factors, so $G$ is a free factor. The cyclic subgroup $A=⟨a^n⟩$ has order $m$, just as $D=⟨g⟩$ does. Hence $a^{nr}\mapsto g^r$ is a well-defined group isomorphism $A\to D$, and we may form the HNN extensionThe single displayed conjugacy relation implements the full cyclic isomorphism by taking integer powers. Britton's lemma embeds $G_1$ in $H$, so the original $G$ is preserved. Now takeCancellation of successive $t{t}^{-1}$ gives $h^n=t^{-1}{a}^{n}t=g$. This proves the adjoining a root by an HNN extension construction and all required embedding claims. If $g=1$, then $m=1$, $C=C_n$, and $A=D=\{1\}$; the HNN relation is vacuous and the same calculation gives $h^n=1$. The construction also works for $n=1$. It uses the actual order of $g$ as an existence parameter, not an algorithm for determining an unknown order.

Construct the free product from the empty word and all finite alternating words $g_1\cdots g_k$, whose syllables in a free product are nonidentity elements of tagged copies of $G_1,G_2$, with adjacent syllables from different factors. Multiply by concatenating, multiplying adjacent elements in the same factor, and deleting identities until the word is reduced. The normal form theorem for a free product gives a unique result; reducing three concatenated words gives the same result under either parenthesization, so multiplication is associative. The empty word is the identity, and the inverse reverses the word and inverts each syllable. Each factor embeds as words of length one.

The universal property of a free product says that for every group $K$ and group homomorphisms $f_i:G_i\to K$ there is a unique group homomorphism $f:G_1\ast G_2\to K$ extending both. Explicitly, send a reduced word to the product of its syllable images; reduction preserves this product. This gives existence, while generation by the two factors gives uniqueness.

A standard form of Klein's combination theorem, or the ping-pong lemma, is the following. Let nontrivial subgroups $G_1,G_2$ of the homeomorphisms of a topological space $X$ have disjoint nonempty subsets $X_1,X_2$ withAssume also that at least one factor has at least three elements. Then the generated subgroup is $\boxed{⟨G_1,G_2⟩\cong G_1\ast G_2}$. The cardinality hypothesis cannot simply be omitted: the same involution swapping two disjoint sets would otherwise provide a counterexample with both factors equal to $C_2$.

Here is the ping-pong lemma proof. A reduced word of odd length begins and ends in the same factor, so repeated application of the displayed inclusions sends the other factor's domain into that factor's domain. Disjointness shows that the word is not the identity. For an even reduced word, relabel the factors so that $|G_1|\ge 3$, and invert the word if necessary to make it begin with $g\in G_1$ and end in $G_2$. Choose $s\in G_1\setminus \{1,g^{-1}\}$. The conjugate $sw{s}^{-1}$ reduces to an odd-length word beginning with $sg\ne 1$ and ending with $s^{-1}$, both in $G_1$, so it is nontrivial. Thus no nonempty reduced word lies in the kernel of the natural group homomorphism $G_1\ast G_2\to ⟨G_1,G_2⟩$, proving the theorem.

For an explicit example, let $X=\mathbb{R}\cup \{\infty \}$ be the one-dimensional Real projective space, and take the Möbius transformationsFor every nonzero integer $n$, $A^n(t)=t+2n$ sends $X_2$ into $X_1$, while $B^n(t)=t/(2nt+1)$ sends $X_1$ into $X_2$. Indeed $|2nt+1|>|t|$ when $|t|>1$, and $B^n(\infty )=1/(2n)$. Both transformations have infinite order. Hence the ping-pong lemma gives $\boxed{⟨A,B⟩\cong \mathbb{Z}\ast \mathbb{Z}=F_2}$, a free product of two nontrivial finitely presented groups.

A finitely presented group admits a group presentation $⟨S\mid R⟩$ with both $S$ and $R$ finite; it is the quotient of the free group on $S$ by the normal closure of $R$. Ifwith disjoint generator sets, thenMaps from this group presentation to any group are exactly pairs of maps from $G$ and $H$, so the universal property of a free product proves the formula.

For a group homomorphism $\varphi :H\to \mathrm{Aut}(G)$, choose a word $w_{t,s}(S)$ representing $\varphi (t)(s)$ for each $t\in T,s\in S$. The presentation of a semidirect product isThe presentation maps onto the specified semidirect product. Conversely, its conjugation relations allow any word to be written as a word from $G$ followed by one from $H$. The natural maps from the two factors to the presented group satisfy the full action relation, because conjugation agrees with $\varphi$ first on generators and hence on all elements. They define the reverse group homomorphism $(g,h)\mapsto gh$. The two maps are inverse on every generator, proving the group isomorphism. There are finitely many cross-relations, so the result is again a finitely presented group.

Apply this to the specified permutation action. The presentation isEliminate $y=cx{c}^{-1}$ and $z=c^{2}x{c}^{-2}$. The last cross-relation becomes $c^{3}x{c}^{-3}=x$, already implied by $c^3=1$. ThusBoth factors are nontrivial finitely presented groups, as required.

The free product $G_1\ast G_2$ is obtained by taking disjoint copies of the elements of the two groups as generators and imposing precisely their internal multiplication relations. Equivalently, if $G_i=⟨X_i\mid R_i⟩$ with disjoint $X_i$, thenA nontrivial free product has both factors different from the trivial group.

The normal form theorem for a free product says that every element has a unique expressionwhere the empty expression represents the identity. The $g_j$ are called syllables in a free product. Thus nonempty alternating products cannot be the identity, and the natural maps of the factors into the free product are injective.

For existence, multiply adjacent syllables from the same factor and delete identity syllables until the word alternates. Each change uses a defining relation and decreases the number of syllables. To establish uniqueness without assuming that these reductions are confluent, let $\mathcal{W}$ be the set of alternating nonidentity syllable sequences, including the empty sequence. For $h\in G_i$, define a permutation $L_h$ of $\mathcal{W}$ by prepending $h$, multiplying into the first syllable if it belongs to $G_i$, and deleting it if that product is the identity; for $h=1$, do nothing.

The multiplication law inside $G_i$ gives $L_h{L}_k=L_{hk}$ for $h,k\in G_i$, and $L_h^{-1}=L_{h^{-1}}$. This can be checked at the first syllable: if a product deletes it, the next syllable belongs to the other factor and is treated as a new first syllable. Hence the defining relations give a group action of $G_1\ast G_2$ on $\mathcal{W}$. An alternating word $g_1\cdots g_r$ sends the empty sequence to its own syllable sequence. Two such words representing the same group element induce the same permutation, and therefore have identical sequences. This proves the normal form theorem for a free product.

The universal property of a free product states that, for group homomorphisms $f_i:G_i\to H$, there is a unique group homomorphism $f:G_1\ast G_2\to H$ extending both. Explicitly,The internal multiplication relations are respected because each $f_i$ is a group homomorphism, so this assignment descends from words to the presented group. Alternatively, multiplication of two normal forms is concatenation followed by precisely those internal relations, which do not change its value in $H$. Uniqueness holds because the two factors generate the free product.

The base free product for the group encoding of a modular machine isThe letters $x,y$ generate the first factor, and $t$ generates the second. Let $T_K$ be the kernel of the group homomorphism $K\to ⟨x,y⟩\cong {\mathbb{Z}}^2$ that kills $t$. Thenis a free group with this displayed free basis of a group. Indeed every word in $K$ can be rewritten as a product of such conjugates followed by an element of $⟨x,y⟩$, so they generate the kernel. A freely reduced product of these conjugates is nontrivial by the normal form theorem for a free product: after combining adjacent occurrences of the same conjugate, different successive indices give a nonzero intervening $x,y$-syllable. Thus there is no relation among the proposed basis elements.

For clarity, a modular machine of modulus $m>1$ has at most one instruction for each residue pair $(a,b)$, with $0\le a,b<m$ and $0\le c<m^2$. Its right and left transitions are respectivelyIts halting set at a designated terminal configuration $H_0(\mathcal{M})$ consists of the nonnegative pairs whose forward computation reaches $(0,0)$, including $(0,0)$ itself. These formulas explain the exponents in the associated-subgroup maps below.

For $M>a\ge 0$ and $N>b\ge 0$, defineThe normal form theorem for a free product giveswhere $X,Y,T$ map to $x^M,y^N,t(a,b)$. To see injectivity, expand an alternating word in $⟨x^M,y^N⟩$ and powers of $t(a,b)$. The conjugating $x,y$ factors commute with the lattice syllables, so each intervening nonidentity lattice syllable stays nonidentity in the expanded free-product normal form.

Its intersection with $T_K$ is the free group with basisThis follows by moving all $x^M,y^N$ factors to the right; the zero-exponent lattice remainder characterizes membership in the kernel.

The required isomorphisms are specified on the three generators byandEach source and target has the same presentation $⟨X,Y,T\mid [X,Y]=1⟩$, and each displayed assignment identifies its three abstract generators. Hence these are genuine isomorphisms, not merely maps of generating sets.

On the kernel basis they give exactly the machine transitions:For example, rewrite the first input as $x^{-mu}{y}^{-mv}t(a_i,b_i)x^{mu}{y}^{mv}$ and apply ${\varphi }_i$ to each factor. These identities also hold for negative $u,v$, since they are identities in the groups.

The auxiliary Higman group $Q$ has no nontrivial finite quotients of a group. One can use this permitted property directly, but there is a short verification. In any finite quotient, let $n_i$ be the order of the image of $a_i$. Since conjugation sends $a_{i+1}$ to its square, $n_{i+1}$ must be odd. If some $n_i>1$, choose the least prime number $p$ dividing any $n_i$. It is odd. Conjugation by the preceding generator givesThe multiplicative order of $2$ modulo $p$ is therefore a divisor of $n_{i-1}$. It is greater than one and divides $p-1$ by the Fermat little theorem, so it has a prime divisor smaller than $p$. That prime also divides $n_{i-1}$, contradicting the choice of $p$. Hence every $n_i=1$ and the quotient is trivial.

Given any finitely presented group $P$, form $\hat{P}=P\ast ⟨v⟩$, and apply part (a) to the word $w=v$. This word is nontrivial by the normal form theorem for a free product, so the output $J=\hat{P}(v)$ contains $P$ by the embedding already proved.

To check its finite quotients, let $f:J\to F$ be any group homomorphism to a finite group. The image of the copy of $Q$ is trivial by the preceding property. The identifications $u_j=a_3^{j+1}{a}_1{a}_3^{-(j+1)}$ make all $f(u_j)$ trivial. Thus the equations $u_j^{-1}c{u}_j=g_j$ give, in the image,Since $f(c)=f(z)$, this forces $f(x_i)=1$ for all generators of $\hat{P}$, including $v$. The defining word $c=[v,z]$ then has trivial image, so $f(z)=f(d)=1$ as well. Every generator of $J$ has trivial image. ThereforeThis uses the concrete construction of part (a), not an assumption that arbitrary quotients preserve an embedding of $P$.

Each factor is a free abelian group of rank two. Take the infinite symmetric generating setThe Bass-Serre tree has an edge $e_g$ joining $gA$ to $gB$ for every $g\in A\ast B$. Indeed, the normal form theorem for a free product gives $A\cap B=\{1\}$, so a nonempty coset intersection consists of exactly one element. Let $m_g$ be the midpoint of $e_g$ and send the Cayley vertex $g$ to $m_g$.

Two distinct edges $e_g,e_h$ share an endpoint precisely when $g^{-1}h\in A\setminus \{1\}$ or $g^{-1}h\in B\setminus \{1\}$. This is exactly adjacency in the Cayley graph for $S$. A path in that graph therefore gives a path between the midpoints of the same length in the tree. Conversely, the unique tree segment between two edge midpoints passes through a succession of adjacent edges and gives a Cayley path of that length. Hence, on vertices,All edge midpoints occur, and every tree point is within $1/2$ of one of them. Extending along Cayley edges gives a quasi-isometry of the metric graphs; ambiguity from folding the cliques at a tree vertex costs only a bounded additive error. This is the free product with factor generating set construction.

For finite generating sets the answer changes. Use $S_0=\{a,a^{\prime },b,b^{\prime }{\}}^{\pm 1}$. The retraction $A\ast B\to A$ killing $B$ sends every generator to a generator of $A$ or to the identity. Therefore the restriction of $d_{S_0}$ to $A$ is exactly the standard ${\ell }^1$ word metric on ${\mathbb{Z}}^2$.

In this grid, take vertices $(0,0),(2N,0),(0,2N)$. Use the two axis segments as two sides, and the path from $(2N,0)$ through $(2N,2N)$ to $(0,2N)$ as the third. All are metric geodesics in the whole Cayley graph, by the retraction argument. The corner $(2N,2N)$ is at distance $2N$ from either of the other sides. These metric geodesic triangles are arbitrarily thick, so this Cayley graph is not a Gromov-hyperbolic metric space.

A tree is $0$-hyperbolic. Hyperbolicity is invariant under quasi-isometry for metric geodesic spaces, and all finite word metrics on this group are equivalent. Consequently no Cayley graph for a finite generating set is quasi-isometric to any tree, including a locally infinite one.

A reduced word is either the empty word or a productin which every syllable $u_i$ is a nonidentity element of $G$ or $H$, and consecutive syllables belong to different factors.

Let $\mathcal{W}$ be the set of reduced words. Each $g\in G$ acts on the right of $\mathcal{W}$: if the last syllable lies in $H$, append $g$; if it lies in $G$, multiply it by $g$ and delete it when the product is the identity. Define the action of each $h\in H$ analogously. These rules give genuine actions of the two factors by permutations of $\mathcal{W}$, hence an action of the free group $F(X\bigsqcup Y)$. Every relation in $R\bigsqcup S$ acts trivially, so the action factors through the displayed presentation of $G\ast H$.

The element represented by a reduced word $w$ sends the empty word to $w$. Therefore two reduced words representing the same element induce the same permutation and have the same value on the empty word. They must be identical. This proves the normal form theorem for a free product.