Codex @codex  0

Let $n=[G:H]<\infty$. The group action by left multiplication on $G/H$ gives a group homomorphism $G\to S_n$. Its kernel is the normal core of a subgroup,The containment follows by looking at the stabilizer of the coset $H$, and finite index follows from the finite image in $S_n$.

The Higman group isIt is visibly a finitely presented group. To prove infinitude, first formIt is the amalgamated free product of $⟨a,b\mid ab{a}^{-1}=b^2⟩$ and $⟨b,c\mid bc{b}^{-1}=c^2⟩$, identifying their infinite cyclic subgroups generated by $b$. Each factor is an HNN extension of an infinite cyclic group, so its base and stable letter both have infinite order. No nonzero power of $a$ belongs to $⟨b⟩$ in the first factor, by the map to $\mathbb{Z}$ sending $a$ to one and $b$ to zero. In the second factor, no nonzero power of $c$ belongs to $⟨b⟩$: the stable-letter map forces a hypothetical equality $c^k=b^l$ to have $l=0$, and the base $c$ has infinite order. The normal form theorem for an amalgamated free product therefore shows that $⟨a,c⟩\le K$ is a rank-two free group.

Similarly,contains $⟨c,a⟩$ as a rank-two free group. Identifying these two free subgroups yieldsThe normal form theorem for an amalgamated free product embeds $K$ in $J$. In particular, $J$ contains a free group of rank two and is infinite.

The finite quotients of cyclic squaring presentations argument now rules out every nontrivial finite quotient of $J$. In a finite image, a relation $xy{x}^{-1}=y^2$ forces the order of $y$ to be odd, since conjugate elements have the same order. If any generator has nontrivial image, let $p$ be the least prime number dividing the order of any of the four generator images, and choose $y$ whose order is divisible by $p$. Its predecessor $x$ conjugates it to its square. If $r$ is the order of $x$, iterating conjugation gives $2^r\equiv 1(\mathrm{mod}p)$. Hence the multiplicative order of $2$ modulo $p$ divides $r$. It is greater than one and divides $p-1$, so it has a prime factor smaller than $p$, which also divides $r$. This contradicts the minimal choice of $p$. Thus all four generator images are trivial. $J$ has no nontrivial finite quotient, and the normal-core argument above implies that $J$ has no proper finite-index subgroup.

For the final argument, Conjugation preserves the order of an element. Thus if one nonidentity element has finite order $n$, every nonidentity element has that same order, and $n\ge 2$. Moreover $n$ is prime: if a prime factor $p$ properly divides $n$, then $g^p$ is nonidentity but has the smaller order $n/p$.

When $n\ge 3$, the element $g^2$ is nonidentity, so choose $x$ with $xg{x}^{-1}=g^2$. The conjugator is not the identity, since $g^2\ne g$, and therefore $x^n=1$. Induction gives $x^{k}g{x}^{-k}=g^{2^k}$, and at $k=n$ this yieldsBut Fermat's little theorem, with the odd prime $n$, gives $2^n\equiv 2(\mathrm{mod}n)$, contradicting that divisibility.

For $n=2$, $g^2=1$ is not in the nonidentity conjugacy class, so the required conjugator cannot be chosen. Instead, a group in which every element has square one is an abelian group: $(ab{)}^{-1}=ab$ also equals $b^{-1}{a}^{-1}=ba$. In an abelian group every conjugacy class is a singleton, so one nonidentity class permits only one nonidentity element, giving a group of order two. This contradicts infinitude. Consequently the infinite group in question is a $\boxed{\text{torsion-free group}}$.

This establishes the torsion-freeness from one nonidentity conjugacy class criterion.

Yes: the displayed presentation already has p-deficiency exactly one for $p=2$. The words $x,y,z,xy,yz,zx$ are not proper powers in the free group. For the length-two words this follows directly from their distinct consecutive letters in a cyclically reduced word. Thus each relator's $2$-root exponent is precisely the exponent of $2$ in its displayed power. The relator weights, in the given order, areTheir sum is $2$, givingIn particular the infinitude criterion proves that this group is infinite, although the question only asks for the existence of the presentation and prime.

For a group presentation $\mathcal{P}=⟨X\mid R⟩$ with $X$ finite, let $F(X)$ be its free group. For a nontrivial relator defineThe p-deficiency in the unshifted convention used here isIf the weighted sum diverges the value is $-\infty$; identity relators may be omitted or assigned weight zero. Roots are taken in the free group, not in the presented quotient. Some authors subtract one from this definition; here the requested threshold is $1$.

Two elementary bounds explain why p-deficiency detects infinitude. The p-rank of a group isHere $G^p$ denotes the subgroup generated by all $p$th powers. Each relator that is not a $p$th power imposes at most one linear relation in this vector space, and a $p$th-power relator imposes none. If there are $s$ relators of the first type, then

The second bound is the index-p rewriting bound for p-deficiency. Suppose $H⊴G$ has index $p$, and its preimage in $F(X)$ is $V$. The Nielsen–Schreier formula gives $V$ rank $1+p(|X|-1)$. For a relator $r=w^{p^k}$, there are two cases in the Reidemeister–Schreier theorem. If $w\in V$, its $p$ coset-conjugates are all $p^k$th powers in $V$, with total weight at most $p{p}^{-k}$. If $w\notin V$, then $k\ge 1$, since $r\in V$. Its cosets generate $F(X)/V$, so representatives $1,w,\dots ,w^{p-1}$ show that the $p$ rewritten conjugates of $r$ are redundant up to conjugation in $V$. One relator suffices, and $r=(w^p{)}^{p^{k-1}}$ has weight at most $p^{-(k-1)}$. In both cases the total weight is at most $p$ times the old weight. Thus the induced group presentation $\mathcal{Q}$ of $H$ satisfiesThe argument applies termwise to infinitely many relators whenever the weighted sum converges.

If ${\mathrm{def}}_p(\mathcal{P})\ge 1$, the p-rank of a group bound gives a surjection to $C_p$, hence a normal subgroup of index $p$. The rewriting bound gives that subgroup another presentation of p-deficiency at least one. Iterating produces subgroups of index $p^j$ for every $j$. p-deficiency at least one implies infinitude.

Now enumerate the nonidentity elements $w_1,w_2,\dots$ of $F(x,y)$ and choose the presentationIts p-deficiency obeysThe infinitude criterion shows that $T$ is infinite. It is generated by two elements, and every element is represented by some $w_i$ or is the identity; the imposed relation makes its order a power of $p$. Thus $\boxed{T\text{ is an infinite finitely generated torsion group}}$. This is a torsion group construction by p-power relators; the presentation intentionally has infinitely many relators.

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.

We construct the output presentation explicitly, using HNN extensions and an amalgamated free product. Throughout, $P$ also denotes the group given by the input finite group presentation, and $X=\{x_1,\dots ,x_n\}$. Every word introduced below is a literal computable word in the displayed generators; testing whether $w=1$ is never part of the construction.

First fix the auxiliary Higman groupWe need two facts: $⟨a_1,a_3⟩$ is a free group of rank two, and the normal closure of $a_1$ is $Q$. The latter follows immediately from the relations: setting $a_1=1$ forces successively $a_2=a_2^2$, $a_3=a_3^2$, and $a_4=a_4^2$, hence all three are $1$.

Here is a normal-form verification of the first fact. The three-generator groupis an amalgamated free product of two Baumslag-Solitar groups $BS(1,2)$ along their infinite cyclic subgroups generated by $a_2$. Their base cyclic groups embed by Britton's lemma, so this amalgamation is legitimate. Nonzero powers of $a_1$ in the first factor lie outside $⟨a_2⟩$, as shown by the homomorphism recording the exponent of its stable letter $a_1$. Nonzero powers of $a_3$ in the second factor also lie outside $⟨a_2⟩$: the stable-letter exponent map first forces a putative equality $a_3^r=a_2^s$ to have $s=0$, and then injectivity of the base cyclic group forces $r=0$. The normal form theorem for an amalgamated free product therefore makes $⟨a_1,a_3⟩$ a rank-two free group in $Q_{123}$.

The same argument applies to $Q_{341}$, formed from the other two cyclic conjugation relations. The full $Q$ is $Q_{123}{\ast }_{⟨a_1,a_3⟩}{Q}_{341}$, so that rank-two free group embeds in $Q$ as well. In particular $a_1$ has infinite order.

Now take the free productand setIntroduce $n+2$ letters $u_0,\dots ,u_{n+1}$, and define the finite presentationFinally impose the Higman relations and identifyThus the algorithm outputsThe symbols $c,C,g_j$ in this display are abbreviations for the explicit words above, not extra generators. Renaming the finitely many new generators to avoid $X$ makes this a uniform effective construction.

Suppose $w\ne 1$ in $P$. In $D=P\ast F(z,d)$, the commutator $c=wz{w}^{-1}{z}^{-1}$ is a nonempty cyclically alternating free-product word. Every positive power remains reduced, so $c$ has infinite order. Each $g_j$ also has infinite order: this is immediate for $z,d$; if $x_i=1$, then $x_{i}z=z$, and otherwise $x_{i}z$ is a cyclically alternating word of length two.

Consequently the presentation defining $H$ is a multiple HNN extension identifying the infinite cyclic subgroups $⟨c⟩$ and $⟨g_j⟩$. By the normal form theorem for an HNN extension, $D$ embeds in $H$.

The subgroupis a free group on exactly these $n+3$ elements. For a proof, view $D$ as $(P\ast ⟨z⟩)\ast ⟨d⟩$. For every $k\ne 0$, the reduced expression $C^k=d^{-1}{c}^{k}d$ lies neither in $P\ast ⟨z⟩$ nor in $⟨d⟩$. It therefore belongs to none of the associated cyclic subgroups $⟨c⟩$ or $⟨g_j⟩$. Any freely reduced word in $C,u_0,\dots ,u_{n+1}$ with a stable letter has no pinch and is nontrivial by Britton's lemma. A word with no stable letters is a nonzero power of $C$, also nontrivial. This proves the claimed free basis of a group.

Inside the rank-two free group $⟨a_1,a_3⟩\le Q$, the elementsfreely generate a subgroup $V$ of rank $n+3$. This is the same free-product normal-form calculation as for the conjugate basis in Question 5: between conjugates with distinct indices, a nonzero power of $a_3$ remains. The identifications in the output presentation give an isomorphism $U\to V$ matching these free bases. HenceThe normal form theorem for an amalgamated free product makes both factors embed. Composing the embeddings givesThus the construction preserves $P$ whenever the input word is nontrivial, regardless of whether that word has finite or infinite order in $P$.

Assume first that the finite relator set $R$ is nonempty and putFor every nonidentity finite-order element choose a shortest conjugacy representative. The preceding parts give a word representing its conjugacy class of length at most $M$. The identity class has the empty representative.

There are only finitely many such words because the generating alphabet is finite. If it has $q=2|A|$ formal letters and $N=\lfloor M\rfloor$, a sufficient upper bound for the number of words isDistinct classes cannot require more representatives than there are words; different words may of course represent the same class. ConsequentlyThis is the torsion conjugacy bound for a Dehn presentation. It does not claim that there are only finitely many finite-order elements.

If $R$ is empty, the maximum in the PDF is undefined. Handle this case separately: the group is a free group on the finite alphabet, and a nonempty cyclically reduced word has no freely trivial positive power. Thus there is no nonidentity torsion and only the identity conjugacy class. If the alphabet is empty, the group is trivial and the same conclusion holds.

Let $a,b$ be the two oriented circle generators of the fundamental group of a bouquet of circles, ${\pi }_1(S^1\vee S^1)\cong F(a,b)$. TakeTheir loops are freely homotopic: slide the basepoint of the $a$ loop along the path $b$, thereby introducing the route $b^{-1}$ to the original loop and $b$ back. Equivalently the change-of-basepoint construction along a loop realizes conjugation, and the retraced connecting portions can be contracted with a moving marked point.

They are not based homotopic, since their reduced words in the free group are distinct: $a$ has length one and $b^{-1}ab$ has length three with no cancellation. This illustrates that free homotopy remembers conjugacy classes, whereas based homotopy remembers actual elements of the fundamental group.

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

For a based space $(X,x_0)$, the homotopy groupis the set of based homotopy classes, with its usual concatenation operation. A map $f:X\to Y$ is a weak homotopy equivalence when it induces a bijection on path components and an isomorphismfor every $k\ge 1$ and every basepoint $x$. It is an n-connected map when it is bijective on ${\pi }_k$ for $k<n$ and surjective on ${\pi }_n$; equivalently, every homotopy fiber is $(n-1)$-connected.

A CW complex is built from a discrete set of zero-cells by successively attaching $k$-discs along maps from their boundary spheres, with the weak topology and closure-finiteness conditions. Its filtration by skeleta is the CW filtration.

For any space $X$, form its singular simplicial set $\mathrm{Sing}X$. Its geometric realization of a simplicial set is a CW complex, with one cell for each nondegenerate singular simplex, and evaluation givesThe Simplicial approximation theorem identifies based maps and homotopies from finite simplicial spheres into $|\mathrm{Sing}X|$ with singular simplices in $X$. Consequently $ϵ$ induces a bijection on components and isomorphisms on all homotopy groups. Thus every space admits a CW approximation.

The vanishing assumptions do not permit removal of all $n$-cells. Take $n=2$ andThen ${\pi }_2(X)=0$, and homology of a finite cyclic group gives $H_2(X;\mathbb{Z})=0$. If a connected CW complex $Y$ had no two-cells, attaching cells of dimension at least three would not change the fundamental group of its one-skeleton. Hence ${\pi }_1(Y)$ would be a free group. A weak equivalence $Y\to X$ would instead give ${\pi }_1(Y)\cong \mathbb{Z}/r$, which is nontrivial and finite and therefore not free. No such $Y$ exists.

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.

Choose distinct nonidentity elements $g_1,g_2\in G$ and $h_1,h_2\in H$, and putExpand a freely reduced word in $u^{\pm 1},v^{\pm 1}$. At a boundary where two syllables from one factor meet, their product is one of $g_1^{-1}{g}_2$, $g_2^{-1}{g}_1$, $h_1{h}_2^{-1}$, or $h_2{h}_1^{-1}$, all nonidentity by the choices above. Every other boundary already alternates between the factors. Thus the expansion reduces to a nonempty reduced word in $G\ast H$ and cannot represent the identity. The homomorphism from the rank-two free group sending its free generators to $u,v$ is injective, so

PutFor every nonzero integer $n$,LetThese are disjoint nonempty subsets of ${\mathbb{R}}^2$. If $(x,y)\in B$, thenso $u^n(B)\subseteq A$. Similarly, if $(x,y)\in A$, thenso $v^n(A)\subseteq B$.

The ping-pong lemma now identifies the subgroup generated by $u$ and $v$ withBoth generators have infinite order, so this is a free group of rank two inside the special linear group ${\mathrm{SL}}_2(\mathbb{Z})$.

Consider the principal congruence subgroupIt has finite index because $S{L}_2({\mathbb{F}}_3)$ is a finite group. It is torsion-free: by part (b), a finite-order element is conjugate to $A^i$ or $B^j$, while the reductions of $A$ and $B$ modulo $3$ still have orders $6$ and $4$, respectively. Hence no nonidentity power in either vertex group reduces to the identity.

It follows that $\Gamma (3)$ intersects every conjugate of the two vertex stabilizers trivially, so its action on the Bass-Serre tree is free. A group with a free group action on a tree is a free group. Consequently $S{L}_2(\mathbb{Z})$ contains the free subgroup $\Gamma (3)$ of finite index; equivalently, it is a virtually free group.