## How Stallings proved finitely generated groups are subgroup separable

In this note, we deal with a construction on finite graphs due to Stallings, exposed in his article Topology of finite graphs, admitting some exciting recent generalizations to some graphs of groups (see Henry Wilton’s articles Elementary free groups are subgroup separable and Hall’s theorem for limit groups) or cube complexes (see Haglund and Wise’s article A combination theorem for special cube complexes). A next note will be dedicated to Wise’s construction for Salvetti complexes, and more generally for special cube complexes, but our main result here is:

Main Theorem: Finitely generated groups are subgroup separable.

Definition: Let $G$ be a group and $H$ be a subgroup. We say that $H$ is separable if, for every $g \notin H$, there exists a finite-index subgroup $K$ containing $H$ and such that $g \notin K$.

Moreover, if the trivial subgroup is separable, $G$ is said residually finite or RF; if every subgroups of $G$ are separable, $G$ is said ERF (Extended Residually Finite); if every finitely-generated subgroups of $G$ are separable, $G$ is said subgroupe separable or LERF (Locally Extended Residually Finite).

Theses definitions have topological interpretations:

Definition: Let $G$ be a group. Defining the set of finite-index subgroups as a fundamental system of neighborhoods of the identity element, we get the profinite topology. Clearly, endowed with its profinite topology, $G$ is a topological group. Moreover, a morphism between two groups endowed with their profinite topologies is automatically continuous.

Nota Bene: Because a finite-index subgroup $H$ always contains a normal finite-index subgroup (namely $\bigcap\limits_{g \in G} gHg^{-1}$), finite-index subgroups in the definitions of profinite topology and separable subgroup may be supposed normal.

Lemma: Let $G$ be a group and $H$ be a subgroup. Then $H$ is separable if and only if it is closed for the profinite topology.

Proof. Suppose that $H$ is separable and let $g \notin H$. By hypothesis, there exists a finite-index subgroup $K$ containing $H$ but not containing $g$. Then $gK$ is an open set disjoint from $H$: if there exists $x \in H \cap gK$, then there exists $k \in K$ such that $x=gk$, hence $g=xk^{-1} \in K$, a contradiction with $gK \cap H = \emptyset$. Therefore, $H$ is closed.

Conversely, suppose that $H$ is closed and let $g \notin H$. By hypothesis, there exists an open subset, say $pK$ for some normal finite-index subgroup $G$ and $p \in G$, containing $g$ and disjoint from $H$. Because we chose $K$ normal, $HK$ is a subgroup of $G$; clearly, it contains $H$ and it is a finite-index subgroup of $G$. Furthermore, it does not contain $g$: indeed, $g \in HK$ implies $pK \cap HK \neq \emptyset$, hence $pK \cap H \neq \emptyset$, a contradiction. Therefore, $H$ is separable. $\square$

Corollary: A group is residually finite if and only if its profinite topology is Hausdorff.

Genarally, it is not easy to prove that a given subgroup is separable. A useful tool for that is:

Definition: Let $G$ be a group and $H$ be a subgroup. We say that $H$ is a retract if there exists a morphism (a retraction) $r : G \to H$ such that $r_{|H}= \mathrm{Id}_H$. We say that $H$ is a virtual retract if it is a retract in some finite-index subgroup of $G$.

Lemma: Let $G$ be a residually finite group and $H$ be a subgroup. If $H$ is a virtual retract then it is separable.

Sketch of proof. It is sufficient to notice that the image of a (topological) retraction in a Hausdorff topological space is closed. So let $X$ be a Hausdorff space and $r : X \to Y \subset X$ be a retraction. Here, we only work with finitely-generated groups so that profinite topologies are second-countable, therefore it is sufficient to show that $Y$ is sequentially closed; for the more general case, the same argument works with ultrafilters.

Let $(x_n) \subset Y$ be a sequence converging to some $\in X$. Then, $(r(x_n))=(x_n)_n$ converges to $r(x)$. Because $X$ is Hausdorff, we deduce that $x=r(x) \in Y$. Therefore, $Y$ is sequentially closed. $\square$

The construction introduced by Stallings, is the following (recall that an immersion is a locally injective simplicial map):

Theorem: Let $B$ be a finite bouquet of circles, $X$ be a finite graph and $X \to B$ be an immersion. Just by adding edges to $X$, it is possible to construct a covering $C(X,B) \to B$ and a retraction $r : C(X,B) \to X$. Moreover, we get a commutative diagram:

We say that $C(X,B)$ is the canonical completion and $r$ the canonical retraction.

Now, let us see  how to conclude thanks to Stallings’ construction:

Proof of the main theorem: Let $F$ be a finitely generated free groups. We first prove that $F$ is residually finite in order to apply the previous lemma.

Let $B$ be a bouquet of circles satisfying $\pi_1(B) \simeq F$; let $\widehat{B}$ denote its universal covering. Now, thinking of $g \in F \backslash \{1 \}$ as a non trivial loop in $B$, let $X \subset \widehat{B}$ be a finite subgraph containing a lift of $g$. Then, the fundamental group of the canonical completion $C(X,B)$ is a finite-index subgroup of $\pi_1(B) \simeq F$ not containing $g$. We just proved that $F$ is residually finite.

Now let $H$ be a finitely generated subgroup of $F$. Because $F$ is residually finite, it is sufficient to prove that $H$ is a virtual retract to conclude that $H$ is separable.

Again, let us see $F$ as the fundamental group of a bouquet of circles $B$ and let $Y \to B$ denote the covering associated to the subgroup $H$. If $T \subset Y$ is a maximal subtree, because $H$ is finitely generated, $Y \backslash T$ has only finitely many edges; let $X \subset Y$ be a ball containing all theses edges. Then the canonical retraction $r: C(X,B) \to X$ gives a retraction

$r_* : K:= \pi_1(C(X,B)) \to H \simeq \pi_1(X)$

so that $H$ be a retract in $K$, and therefore a virtual rectract in $F$. $\square$

During the proof above, the construction of an immersion $X \to B$ with $\pi_1(X) \simeq H$ can be made directly. For example, if $F = \langle a,b \mid \ \rangle$ and $H = \langle ab^{-2}a^{-1}, abab^2 \rangle$:

Notice that the main theorem cannot be extended to the separability of all subgroups, ie. every non-abelian (finitely-generated) free group is not ERF: Suppose by contradiction that there exists an ERF non-abelian free group. Because any quotient of an ERF group is RF, we deduce that any two-generator group is RF, and a fortiori Hopfian. However, we already proved in a previous note that the Baumslag-Solitar group $BS(1,2)$ is not Hopfian.

We now turn on the proof of Stallings’ construction. The figure below illustrates an example; the reader is encouraged to keep in mind this particular case in order to visualize how the argument is simple.

Proof of Stallings’ construction: Because $X \to B$ is an immersion, for any vertex $v \in V$ and any label $x_i$, there is at most one edge labelled $x_i$ starting from $v$ or ending at $v$. We want to add edges to $X$ so that exactly one edge of any label start from and end at any vertex; such a graph will be a covering of $B$.

Step 1: Let $e \in X$ be an edge labelled $x_i$ and let $p = (e_0, \dots, e_r)$ denote the path of oriented edges labelled $x_i$ containing $e$ of maximal length (such a path is uniquely defined). Two cases happens: either $p$ is a loop, and there is nothing to do, or $p$ is not a loop, and we add an edge labelled $x_i$ between the extremities of $p$.

Doing the same thing for every edges of $X$ and for every label, we get a graph $X'$ satisfying: for any vertex $v \in X'$ and any label $x_i$, either there is no edge labelled $x_i$ adjacent to $x_i$, or there are two such edges, one starting from $v$ and the other ending at $v$.

Step 2: Let $v \in X$ be a vertex and $x_i$ a label. If there is no edge labelled $x_i$ adjacent to $v$, then add a loop labelled $x_i$ based at $v$. Keep going for every every vertex and for every label.

Let $C(X,B)$ denote our new graph. It is a covering $C(X,B) \to B$ extending by construction the immersion $X \to B$, so we have the commutative diagram.

To conclude the proof, let us define a retraction $r : C(X,B) \to X$. Of course, we only have to define $r(e)$, where $e$ is an edge added to $X$. Two cases happen: either $e$ is a loop based at a vertex $v \in X$, and we define $r(e)=v$, or $e$ completes a path $p\subset X$ to a loop, and we send $e$ on $p$ (first choose a subdivision of $e$) so that $r(e)=p$. $\square$

Nota Bene: In general, the retraction defined above is not simplicial.

## Euler product formula from probability

From the discussion A simple way to obtain $\prod_{p \in \mathbb{P}} \frac{1}{1-p^{-s}} = \sum_{n =1}^{\infty} \frac{1}{n^s}$ on math.stackexchange, I learnt an elementary proof of Euler product formula; in fact, I found it so remarkable that I decided to write a post on it.

We only need the two following basic lemmas; only sketchs of proof are given, we refer to Jean Jacod’s book, Probability essentials, for more information.

Definition: $\{ E_i \mid i \in I \}$ is a family of independent events if for every finite subset $J \subset I$,

$\displaystyle P \left( \bigcap\limits_{j \in J} E_j \right)= \prod\limits_{j \in J} P(E_j)$.

Lemma: Let $P$ be a probability measure and $\{ E_i \mid i \geq 1 \}$ be a family of independent events. Then

$\displaystyle P \left( \bigcap\limits_{i \geq 1} E_i \right) = \prod\limits_{i \geq 1} P(E_i)$.

Sketch of proof. $\left( \bigcap\limits_{i=1}^n E_i \right)$ is a decreasing sequence of events, hence

$\displaystyle P \left( \bigcap\limits_{i \geq 1} E_i \right) = \lim\limits_{n \to + \infty} P \left( \bigcap\limits_{i=1}^n E_i \right)= \lim\limits_{n \to + \infty} \prod\limits_{i=1}^n P(E_i) = \prod\limits_{i \geq 1} P(E_i)$. $\square$

Lemma: If $\{ E_i \mid i \in I \}$ is a familiy of independent events, then $\{ E_i^c \mid i \in I \}$ so is.

Sketch of proof. Using inclusion-exclusion principle, prove by induction on $n$ that every subfamily $\{E_{i_1}, \dots E_{i_n} \}$ of cardinality $n$ satisfies

$P \left( \bigcap\limits_{k=1}^n E_{i_k}^c \right)= \prod\limits_{k=1}^n P \left( E_{i_k}^c \right)$.

For $n=2$, we have

$\begin{array}{lcl} P(E_1^c \cap E_2^c ) & = & 1- P(E_1 \cup E_2)= 1- P(E_1) - P(E_2 ) + P(E_1 \cap E_2) \\ \\ & = & 1- P(E_1) - P(E_2) + P(E_1) P(E_2) = ( 1 - P(E_1)) (1- P(E_2)) \\ \\ & = & P(E_1^c) P(E_2^c) \hspace{1cm} \square \end{array}$

Theorem: Let $s > 1$. Then $\displaystyle \zeta(s):= \sum\limits_{n \geq 1} \frac{1}{n^s} = \prod\limits_{p \in \mathbb{P}} \frac{1}{1-p^{-s}}$.

Proof. Let $X : \mathbb{N} \to \mathbb{N}$ be a random variable and $P$ be a probability measure such that

$\displaystyle P(X=n)= \frac{\zeta(s)^{-1}}{n^s}$;

for example, take $X= \mathrm{Id}$ and $P ( \{n \})= \frac{\zeta(s)^{-1}}{n^s}$. Let $E_k$ be the event “$X$ is divisible by $k$“. Notice that

$\displaystyle P(E_k)= \sum\limits_{i \geq 1} P(X=ik) = \sum\limits_{i \geq 1} \frac{\zeta(s)^{-1}}{n^s} = k^{-s}$.

Therefore, for any primes $k_1 , \dots, k_r$,

$\displaystyle P \left( \bigcap\limits_{j=1}^r E_{k_j} \right)= P \left( E_{\prod\limits_{j=1}^r k_j} \right) = \prod\limits_{j=1}^r k_j^{-s} = \prod\limits_{j=1}^r P(E_{k_j})$.

We deduce that $\{ E_k \mid k \ \text{prime} \}$ is a family of independent events. Because $X=1$ if and only if $X$ is not divisible by any prime, we have

$\displaystyle \frac{1}{\zeta(s)} = P(X=1)= P \left( \bigcap\limits_{p \in \mathbb{P}} E_p^c \right) =\prod\limits_{p \in \mathbb{P}} \left( 1- P(E_p) \right) = \prod\limits_{p \in \mathbb{P}} \left( 1-p^{-s} \right)$. $\square$

## Amalgamated products and HNN extensions

I present here a series of four notes about constructions using amalgamated products and HNN extensions. These operations are central in geometric group theory, thanks to van Kampen theorem and Bass-Serre theory (both are in fact related, see Scott and Wall’s article, Topological method in group theory). We begin by defining them:

Definition: Let $A,B,C$ be three groups and $\varphi : C \to A$, $\psi : C \to B$ be two monomorphisms. If $\langle X \mid R \rangle$ (resp. $Y \mid S \rangle$) is a presentation of $A$ (resp. of $B$), we define the amalgamated product $A \underset{C}{\ast} B$ by the presentation

$\langle X, Y \mid R, S, \varphi(c)= \psi(c) \ \forall c \in C \rangle$.

Therefore, we glue $A$ and $B$ together along $C$.

Definition: Let $A, C$ be two groups and $\varphi : C \to A$, $\psi : C \to A$ be two monomorphisms. If $\langle X \mid R \rangle$ is a presentation of $A$, we define the HNN extension $\underset{C}{\ast} A$ by the presentation

$\langle X, t \mid R, t \varphi(c) t^{-1} = \psi(c) \ \forall c \in C \rangle$.

We say that $t$ is the stable letter of the extension.

Therefore, we force the two isomorphic subgroups $\varphi(C)$ and $\psi(C)$ to be conjugated.

It is worth noticing that the amalgamated products and the HNN extensions depend on the monomorphisms we chose, although they do not appear in the notations. However, the new groups we build do not depend on the specific presentations we use; it can be noticed directly. Alternatively, these operations may be defined thanks to universal properties, whithout refering to any presentation.

A remarkable fact is that normal forms are known for amalgamated products and HNN extensions:

Property: Let $A \underset{C}{\ast} B$ be an amalgamated product. Let $T_A$ (resp. $T_B$) be a transversal of $A$ (resp. $B$) modulo $C$; for the coset $C$, we take $1$ as a coset representative. Any element of $A \underset{C}{\ast} B$ may be uniquely written as

$c \cdot a_1 \cdot b_1 \cdots a_n \cdot b_n$,

where $n \geq 1$, $a_i \in T_A \backslash \{1\}$ for $2 \leq i \leq n$, $a_1 \in T_A$, $b_i \in T_B \backslash \{1\}$ for $1 \leq i \leq n-1$, $b_n \in T_B$ and $c \in C$.

Property: (Britton’s lemma) Let $\underset{C}{\ast} A$ be a HNN extension. Let $T_1, T_2$ be transversals of the images of $C$ into $A$; for the trivial cosets, we take $1$ as a coset representative. Any element of $\underset{C}{\ast} A$ may be uniquely written as

$a_1 \cdot t^{\epsilon_1} \cdots a_n \cdot t^{\epsilon_n} \cdot a_{n+1}$,

where $n \geq 1$, $a_{n+1} \in A$, $a_i \in T_1$ if $\epsilon_i = 1$, $a_i \in T_2$ if $\epsilon_i = -1$, and $a_i \neq 1$ if $\epsilon_i \neq \epsilon_{i+1}$.

In particular, it is possible to deduce the following corollaries, which will be useful in the sequel:

Corollary: The factors $A,B$ of an amalgamated product $A \underset{C}{\ast} B$ embed naturally into $A \underset{C}{\ast} B$. The factor $A$ of a HNN extension $\underset{C}{\ast} A$ embeds naturally into $\underset{C}{\ast} A$.

Corollary: Up to conjugaison, an element of finite order in an amalgamated product of a HNN extension belongs to a factor. In particular, the amalgamated product of torsion-free groups or the HNN extension of a torsion-free group is torsion-free.

Our first note deals with an embedding theorem:

Theorem: Every countable group can be embedded into a two-generator groups.

(Notice that we gave a proof of this theorem without using amalgamated products and HNN extensions in the note A free group contains a free group of any rank.)

As a corollary, we prove the following theorem of B. H. Neumann that we already proved using the space of marked groups and small cancellation groups in the note Cantor-Bendixson rank in group theory: A theorem of B.H. Neumann:

Theorem: Up to isomorphism, there exist $2^{\aleph_0}$ two-generator groups.

A consequence of the theorem above is that almost all finitely-generated groups are not finitely presented: clearly, there exist only countably many finitely-presented groups. However, in general it is not easy to prove that a group is not finitely-presented of even to find such a finitely-generated group. It turns out that amalgamated products and HNN extensions can be used to give examples of finitely-generated not finitely-presented groups. More precisely, we prove

Theorem: Let $A,B$ be two finitely-presented groups. The amalgamated product $A \underset{C}{\ast} B$ is finitely-presented if and only if $C$ is finitely-generated.

Theorem: Let $A$ be a finitely-presented group. The HNN extension $\underset{C}{\ast} A$ is finitely-presented if and only if $C$ is finitely-generated.

We also use Britton’s lemma to deal with some lamplighter groups:

Theorem: The groups $\mathbb{Z}_n \wr \mathbb{Z}$ and $\mathbb{Z} \wr \mathbb{Z}$ are not finitely-presented.

Another kind of counterexamples provided by amalgamated products and HNN extensions is the class of finitely-generated non-Hopfian groups.

A group $G$ is said Hopfian if every epimorphism $G \twoheadrightarrow G$ is in fact an isomorphism. Several years was needed to fin a non-Hopfian finitely-generated group, and the first examples which were given are precisely based on amalgamated products and HNN extensions. Defining the Baumslag-Solitar group $BS(n,m)$ by the presentation

$\langle a,t \mid ta^nt^{-1}=a^m \rangle$,

we prove:

Theorem: Let $n,m \in \mathbb{Z} \backslash \{0\}$ be two coprime numbers with $n \neq \pm 1$. Then $BS(n,m)$ is not Hopfian.

Another embedding theorem that can be proved using amalgamated products and HNN extensions is the following one:

Higmann embedding theorem: A group can be embedded into a finitely-presented group if and only if it is recursively-presented.

As a corollary, it may be deduced that there exists a finitely-presented group with an insoluble word problem. Unfortunately, the proof of this result is much more evolved that the previous ones, and I had not the time to write such a proof. By the way, I hope to be able to add a note on this theorem soon; meanwhile, a proof can be found in Lyndon and Schupp’s book.

If we suppose that there exists a finitely-presented group with an insoluble word problem, it turns out that many other decision problems can be shown to be insoluble. More precisely, if we define a Markov property $\mathcal{M}$ as a property of finitely-presented groups, preserved by isomorphism, and such that there exist a finitely-presented group satisfying $\mathcal{M}$ and a finitely-presented group not embeddable into any finitely-presented group satisfying $\mathcal{M}$, we prove:

Theorem: Let $\mathcal{M}$ be a Markov property. There is no algorithm to decide whether or not a finitely-presented group satisfies $\mathcal{M}$.

In particular,

Corollary: There is no algorithm to decide whether or not a finitely presented group is abelian, finite, trivial, free, torsion-free or cyclic.

Corollary: There is no algorithm to decide whether or not two presentations represent the same group.

Because any finitely-presented group is the fundamental group of a closed $n$-manifold for any $n \geq 4$, several facts about decision problems in topology may be deduced. For example,

Corollary: Let $n \geq 4$. There is no algorithm to decide whether two closed $n$-manifolds are homeomorphic (or even simply connected).

The main references I used in this series of notes are Lyndon and Schupp’s book, Combinatorial Group Theory, and Baumslag’s book, Topics in Combinatorial Group Theory.

## Amalgamated products and HNN extensions (IV): Markov properties

This is the fourth and last note of our series dedicated to constructions using amalgamated products and HNN extensions. Our main goal is to exhibit several insoluble decision problems in group theory, assuming that there exists a finitely-presented group with an insoluble word problem.

Definition: Let $\mathcal{M}$ be a property of finitely presented groups. We say that $\mathcal{M}$ is a Markov property if $\mathcal{M}$ is preserved by isomorphism, if there exists a finitely presented group satisfying $\mathcal{M}$ and if there exists a finitely presented group which cannot be embedded into a finitely presented group satisfying $\mathcal{M}$.

Theorem: (Adyan) Let $\mathcal{M}$ be a Markov property. There is no algorithm to decide whether or not a finitely presented group satisfies $\mathcal{M}$.

Proof. Let $G_1$ be a finitely presented group satisfying $\mathcal{M}$ and $G_2$ be a finitely presented group which cannot be embedded into a finitely presented group satisfying $\mathcal{M}$. Let $U$ be a finitely generated group with insoluble word problem.

First, we give a finite presentation to the free product

$U_0:= U \ast G_2 = \langle x_1, \dots, x_m \mid R(x_1,\dots, x_m) \rangle$.

Notice that $U_0$ has an insoluble word problem, because $U$ does. If $w=w(x_1,\dots,x_m)$ is any word, we want to construct a finitely presented group $G_w$, such that $G_w$ satisfies $\mathcal{M}$ if and only if $w=1$. It will be sufficient to deduce our theorem.

Let $\langle y_0 \rangle$ be a infinite cyclic group and define $U_1 := U_0 \ast \langle y_0 \rangle$. In particular, with $y_i:= y_0x_i$ when $1 \leq i \leq m$, we have

$U_1 = \langle y_0,y_1, \dots, y_m \mid R(y_0^{-1}y_1, \dots, y_0^{-1}y_m) \rangle$.

Because the $y_i$‘s have an infinite order, we may take successively $(m+1)$ HNN extensions from $U_1$ in order to obtain the group

$U_2 := \langle y_0,y_1, \dots, y_m,t_0,\dots, t_m \mid R, t_iy_it_i^{-1} = y_i^2, 0 \leq i \leq m \rangle$.

From Britton’s lemma, we know that the subgroups $H := \langle t_0, \dots, t_m \rangle$ and $K := \langle t_0^2, \dots, t_m^2 \rangle$ of $U_2$ are freely generated. Therefore, the map $t_i \mapsto t_i^2$ defines an isomorphism $H \to K$, and we have the following associated HNN extension

$U_3 := \langle y_0,y_1, \dots, y_m , t_0, \dots, t_m,z \mid R, t_iy_it_i^{-1}= y_i^2, zt_iz^{-1}= t_i^2, 0 \leq i \leq m \rangle$.

Let $V_1 := \langle r \rangle$ be an infinite cyclic group, $V_2:= \langle r,s \mid srs^{-1}=r^2 \rangle$ a HNN extension of $V_1$ (in fact $V_2$ is isomorphic to the Baumslag-Solitar group $BS(1,2)$), and the following HNN extension of $V_2$:

$V_3 := \langle r,s,t \mid srs^{-1}=r^2, tst^{-1}=s^2 \rangle$.

The successive HNN extensions are well-defined because $r$ and $s$ have an infinite order in $V_1$ and $V_2$ respectively.

Finally, if $w=w(x_1,\dots, x_n)$ is any word, we define $W$ as the group $U_3 \ast V_3$ quotiented by the relations $r=z$ and $t= [y,y_0]$.

Notice that, if $w \neq 1$ in $U_0$ (or equivalently, in $W$), then $[w,y_0]$ has an infinite order in $U_1$, and a fortiori in $U_3$; in particular, the subgroup $\langle z, [w,y_0] \rangle$ of $U_3$ is freely generated. Therefore, because the subgroup $\langle r,t \rangle$ of $V_3$ is also freely generated, $W$ is an amalgamated product of $U_3$ and $V_3$ identifying the two previous subgroups. In particular, we have the embeddings

$G_2 \hookrightarrow U_0 \hookrightarrow U_1 \hookrightarrow U_2 \hookrightarrow U_3 \hookrightarrow W$.

By definition of $G_2$, we deduce that $W$ does not satisfy $\mathcal{M}$.

If $w=1$ in $U_0$ (or equivalently, in $W$), we deduce successively

$w=1 \Rightarrow t=1 \Rightarrow s=1 \Rightarrow r=1 \Rightarrow z=1 \Rightarrow t_i=1 \Rightarrow y_i=1$.

Therefore, $W$ is trivial since it is generated by the elements just mentionned.

To conclude, let $G_w := W \ast G_1$. If $w=1$ in $U_0$, $G_w= G_1$ satisfies $\mathcal{M}$. Otherwise, $G_2$ embedds into $W$ and a fortiori into $G_w$, so $G_w$ does not satisfies $\mathcal{M}$. $\square$

Corollary: There is no algorithm to decide whether or not a finitely presented group is abelian, finite, trivial, free, torsion-free or cyclic.

Proof. It is elementary to prove that all these properties, or their negations, are Markov properties. $\square$

Corollary: There is no algorithm to decide whether or not two presentations represent the same group.

Proof. If there were such an algorithm, it would be possible to decide whether or not a finitely-presented group is trivial. We know that it is impossible according to the previous corollary. $\square$

We conclude our note with some consequences on decision problems in topology:

Theorem: Let $n \geq 4$ and $G$ be a finitely-presented group. Then $G$ is isomorphic to the fundamental group of a closed $n$-manifold.

Sketch of proof. Let $\langle x_1,\dots, x_r \mid r_1, \dots, r_s \rangle$ be a finite presentation of our group $G$ and let $M_0$ be the connected sum

$(\mathbb{S}^1 \times \mathbb{S}^{n-1} ) \sharp \cdots \sharp (\mathbb{S}^1 \times \mathbb{S}^{n-1})$   ($r$ times).

Then $\pi_1(M_0)$ is a free group of rank $r$. In particular, the relation $r_1$ may viewed as an element of $\pi_1(M_0)$, and so as an embedding $f : \mathbb{S}^1 \to M_0$; it can be extended to a tubular neighborhood $f : \mathbb{S}^1 \times D^{n-1} \to M_0$. Let $M_1:=M_0 \backslash f( \mathbb{S}^1 \times D^{n-1})$. According to van Kampen theorem,

$\pi_1(M_0) \simeq \pi_1(M_0 \backslash f( \mathbb{S}^1 \times \{0 \})) \underset{\pi_1(\mathbb{S}^1 \times \partial D^{n-1}) }{\ast} \pi_1( \mathbb{S}^1 \times D^{n-1})$.

Because the image of $\pi_1(\mathbb{S}^1 \times \partial D^{n-1})$ in $\pi_1(M_0)$ coincides with $\pi_1( \mathbb{S}^1 \times D^{n-1})$, we deduce that

$\pi_1(M_1) \simeq \pi_1(M_0)$.

Then, notice that the boundary $\partial (\mathbb{S}^1 \times D^{n-1}) = \mathbb{S}^1 \times \partial D^{n-1}$ is homeomorphic to $\partial D^2 \times \mathbb{S}^{n-2}= \partial (D^2 \times \mathbb{S}^{n-2})$; therefore, via $f$ we may glue $D^2 \times \mathbb{S}^{n-2}$ along $\partial f (\mathbb{S}^1 \times \partial D^{n-1})$. Let $M_2$ denote the manifold constructed by this way. By van Kampen theorem,

$\pi_1(M_2) \simeq \pi_1(M_1) \underset{ \pi_1( \partial D^2 \times \mathbb{S}^{n-2}) }{ \ast} \pi_1( D^2 \times \mathbb{S}^{n-2})$.

But $n \geq 4$ implies that $D^2 \times \mathbb{S}^{n-2}$ is simply connected, we saw that $\pi_1(M_1)$ is isomorphic to $\pi_1(M_0)= \langle x_1, \dots, x_r \mid \ \rangle$, and $\pi_1( \partial D^2 \times \mathbb{S}^{n-2} )$ is a cyclic sugbroup generated by the loop $f$. Therefore,

$\pi_1(M_2) \simeq \langle x_1, \dots, x_r \mid r_1 \rangle$.

The same construction can be done successively with $r_2, \dots, r_s$, and the final manifold $M$ is of course closed and $n$-dimensional, and satisfies $\pi_1(M) \simeq G$. $\square$

Corollary: Let $n \geq 4$. There is no algorithm to decide whether or not two closed $n$-manifolds are homeomorphic (or even simply connected).

## Amalgamated products and HNN extensions (III): Examples of non-hopfian groups

This is the third note of our series dedicated to constructions using amalgamated products and HNN extensions.

In the early 1940′s, Hopf asked whether it is possible for a finitely-generated free group to be isomorphic to one of its proper quotients. Later, he proved that it is in fact impossible, but he left open the same question for finitely-generated groups. If a group $G$ is said Hopfian precisely when it is not isomorphic to one of its proper quotients, or equivalently, that any epimorphism $G \to G$ turns out to be an isomorphism, the question becomes : Does there exist a non-Hopfian finitely generated group?

The first example of non-Hopfian finitely-generated groups was only found in 1950 by B. H. Neumann, see his article A two-generator group isomorphic to a proper factor group. In 1951, Higman gave the first example of non-Hopfian finitely presented group using amalgamated products:

Theorem: (Higman) The group $\langle a,s,t \mid sas^{-1}=a^2= tat^{-1} \rangle$ is not Hopfian.

Proof. Let $D= \{ \ell / 2^m \mid \ell \in \mathbb{Z}, m \in \mathbb{N} \}$ denote the additive group of dyadic rationals. We first prove that

$\Pi = \langle x_0,x_1, \dots \mid [x_i,x_{i+1}]=1, x_i^{2^i}=x_0, i \geq 0 \rangle$

is a presentation of $D$. Clearly, the map sending $x_i$ to $1/2^i$ for all $i \geq 0$ extends to an epimorphism $\phi : \Pi \twoheadrightarrow D$. It is sufficient to prove that $\phi$ is one-to-one to conclude. Let

$g:= x_{m_1}^{\ell_1} \cdots x_{m_r}^{\ell_r} \in \mathrm{ker}(\phi)$.

In $\Pi$, notice that for all $i \leq j$,

$x_i^{2^j}= x_i^{2^i \cdot 2^{j-i}} = (x_i^{2^i})^{2^{j-i}} = x_0^{2^{j-i}}$.

Therefore, if $m:= \max(m_1,\dots,m_r)$,

$x_0^{\ell_1 2^{m-m_1} + \cdots + \ell_r 2^{m-m_r}} = g^{2^m} \in \mathrm{ker}(\phi)$.

But $0= \phi \left( g^{2^m} \right) = \ell_1 2^{m-m_1} + \cdots + \ell_r 2^{m-m_r}$, hence $g^{2^m}=x_0^{0}=1$. However, $\Pi$ is an abelian group whose generators are sending to infinite-order element in $D$ by $\phi$, so $\Pi$ is torsion-free; in particular, we necessarily have $g=1$. We just found our presentation.

Afterwards, let $G$ denote the semi-direct product $D \rtimes \mathbb{Z}$ where $\mathbb{Z}$ acts by multiplication by $2$. Then

$G= \langle x_0,x_1, \dots, t \mid [x_i,x_{i+1}]=1, x_i^{2^i}=x_0, tx_it^{-1}=x_{i-1}, i \geq 0 \rangle$.

The third relation implies $x_i = t^{-i}x_0t^i$, so the presentation above may be simplified as

$G= \langle x_0, t \mid [tx_0t^{-1},x_0]=1, tx_0t^{-1}=x_0^2 \rangle = \langle x_0,t \mid tx_0t^{-1}=x_0^2 \rangle$.

Let $G_1 = \langle a,s \mid sas^{-1} = a^2 \rangle$ and $G_2 = \langle b,t \mid tbt^{-1}=b^2 \rangle$ be two copies of $G$. From the discution above, we know that $a$ and $b$ have an infinite order in $G_1$ and $G_2$ respectively (in fact, recognizing a HNN extension, it immediatly follows from Britton’s lemma). Therefore, we may define the amalgamated product

$K:= G_1 \underset{\langle a \rangle = \langle b \rangle}{\ast} G_2 = \langle a,s,t \mid sas^{-1}=a^2= tat^{-1} \rangle$.

Let $\alpha : G_1 \to G_1$ (resp. $\beta : G_2 \to G_2$) be a morphism sending $a$ to $a^2$ and $s$ to $s$ (resp. $b$ to $b^2$ and $t$ to $t$). Noticing that $\alpha$ and $\beta$ agree on $\langle a \rangle = \langle b \rangle$, we may define $\mu = \alpha \ast \beta : K \to K$.

We first notice that $\mu$ is onto. Indeed, $\mu(s)=s$, $\mu(t)=t$, $\mu (s^{-1}as)= s^{-1}a^2s=a$ and $\mu (t^{-1}bt)=t^{-1}b^2t=b$.

Then, we notice that $\mu$ is not one-to-one. Let $g := s^{-1}ast^{-1}b^{-1}t$. In $K$,

$\mu(g)=s^{-1}a^2 st^{-1}b^{-2}t = ab^{-1}=1$,

so $g \in \mathrm{ker}(\mu)$. On the other hand,

$g = \underset{ \in G_1 \backslash \langle a \rangle }{ \underbrace{ (s^{-1} as ) }} \cdot \underset{ \in G_2 \backslash \langle b \rangle }{ \underbrace{ (t^{-1} b t )^{-1} }} \neq 1$.

We justify that $s^{-1}as \notin \langle a \rangle$ (and in the same way that $t^{-1}bt \notin \langle b \rangle$) by saying that otherwise there would be a $k \in \mathbb{Z}$ such that $s^{-1}as =a^k$, hence

$a=sa^ks^{-1}=(sas^{-1})^k =a^{2k}$,

a contradiction with the fact that $G_1$ is torsion-free. $\square$

In 1962, Baumslag and Solitar found a simple family of non-Hopfian one-relator groups using HNN extensions.

Definition: Let $n,m \in \mathbb{Z} \backslash \{0 \}$. The Baumslag-Solitar group $BS(n,m)$ is the HNN extension of $\mathbb{Z}$ with respect to the subgroups $n \mathbb{Z}$ and $m \mathbb{Z}$, and the obvious isomorphisms.

$BS(n,m)= \langle a,t \mid ta^nt^{-1} = a^m \rangle$.

In particular, $BS(1,2)$ is the semi-direct product $D \rtimes \mathbb{Z}$ we described above.

Theorem: If $m,n \in \mathbb{Z} \backslash \{ 0\}$ are coprime with $n \neq \pm 1$, then $BS(n,m)$ is not Hopfian.

Proof. Let $\varphi : BS(n,m) \to BS(n,m)$ be the morphism sending $a$ to $a^n$ and $t$ to $t$; $\varphi$ is well-defined since

$\varphi( ta^nt^{-1} a^{-m}) =ta^{n^2} t^{-1} a^{-mn} = (ta^nt^{-1})^n a^{-mn} = a^{mn} a^{-mn}= 1$.

First, $\varphi$ is onto. Indeed, $t = \varphi(t)= \mathrm{Im}(\varphi)$ and

$\left\{ \begin{array}{l} a^n = \varphi(a) \in \mathrm{Im}(\varphi) \\ \\ a^m = ta^nt^{-1} = \varphi(t^{-1}at) \in \mathrm{Im}(\varphi) \end{array} \right.$ implies $a=a^{pn+qm}= (a^n)^p \cdot (a^m)^q \in \mathrm{Im}(\varphi)$,

where $p,q \in \mathbb{Z}$ are two integers such that $pn+qm=1$ (they exist because $n$ and $m$ are coprime).

Then, we notice that $\varphi$ is not one-to-one. Because $n \neq \pm 1$, we deduce from Britton’s lemma that

$[t^{-1}at, a]= tat^{-1} a ta^{-1} t^{-1} a^{-1} \neq 1$,

On the other hand,

$\varphi ([t^{-1}at, a]) = \underset{=a^m}{\underbrace{ ta^{n} t^{-1} }} a^{n} \underset{ = a^{-m} }{\underbrace{ ta^{-n}t^{-1} }} a^{-n} = 1$,

so $[t^{-1}at, a ] \in \mathrm{ker}(\varphi)$. $\square$

## Amalgamated products and HNN extensions (II): Examples of non-finitely presented groups

We proved in the previous note of our series that there exist $2^{\aleph_0}$ finitely generated groups (up to isomorphism). However, clearly there exist only $\aleph_0$ finitely presented groups (up to isomorphism), so we deduce that almost all finitely generated groups are not finitely presented. In this note, we give some examples of such groups.

Lemma: Let $\langle X \mid R \rangle$ be a presentation of a group $G$, where $X$ is finite and $R$ infinite. If $G$ is finitely presented, then there exists $R' \subset R$ finite such that $\langle X \mid R' \rangle$ is a presentation of $G$.

Roughly, it is possible to argue as follow: Let $\langle X \mid W \rangle$ be a finite presentation. For any relation $w \in W$, it is possible to write a proof of $w=1$ using the relations $R$; such a proof uses only finite many relations $R_w \subset R$. Let $R' = \bigcup\limits_{w \in W} R_w$. Then $\langle X \mid R' \rangle$ is a finite presentation of $G$, because any relation may be deduced from $W$ and a fortiori from $R'$.

Avoiding proof theory (and Gödel’s completeness theorem), we give below a rigorous proof based on model theory.

Proof. Let $w(X)$ be a word over $X$ such that $w(X)=1$ in $G$. We first prove that the equality $w(X)=1$ can be deduced from a finite set $R_w \subset R$ of relations.

Let $\mathcal{T}_{\text{group}}$ denote the theory of group, and let us define the theory

$\mathcal{T} = \mathcal{T}_{\text{group}} \cup \{ r(X)=1, \ r \in R \}$.

Clearly, $G$ is a model of $\mathcal{T}$; let $H$ be another model. Let $g_x$ (resp. $h_x$) denote the interpretation of $x \in X$ in $G$ (resp. in $H$). Then the map $g_x \mapsto h_x$ extends to a morphism $\varphi : G \to H$. We deduce that

$w(h_x, \ x \in X)= \varphi (w ( g_x, \ x \in X))= \varphi(1)=1$,

so $H$ satisfies $w(X)=1$. Because it is true for any model, $\mathcal{T} \models w(X)=1$. From compactness theorem, we deduce that there exists $\Delta \subset \mathcal{T}$ finite such that $\Delta \models w(X)=1$. Now, it is sufficient to set

$R_w= \Delta \cap \{ r(X)=1, \ r \in R \}$.

Then, let $\langle Y \mid W \rangle$ be a finite presentation of $G$ and $\phi : \langle Y \mid W \rangle \to \langle X \mid R \rangle$ be an isomorphism; in particular, for any word $w$ over $Y$ (resp. over $X$), let $\phi(w)$ (resp. $\phi^{-1}(w)$) denote the word over $X$ (resp. over $Y$) corresponding to $w$ via $\phi$ (resp. via $\phi^{-1}$). Let

$R'= \bigcup\limits_{w \in W} R_w$.

To conclude, it is sufficient to notice that any relation $r \in R$ may be deduced from the relations of $R'$. But this is clear, because $\phi^{-1}(r)=1$ may be deduced from the relations $W$, so $r=1$ may be deduced from the relations $\phi(W)$, and so from the relations $R'$ by construction. $\square$

Property: Let $A,B$ be two finitely presented groups. The amalgamation $A \underset{C}{\ast} B$ is finitely presented if and only if $C$ is finitely generated.

Proof. By contradiction, suppose that $C$ is not finitely generated and that $A \underset{C}{\ast} B$ is finitely presented.

Let $\langle X \mid R \rangle$ (resp. $\langle Y \mid S \rangle$) be a finite presentation of $A$ (resp. $B$). Let $\varphi_1 : C \hookrightarrow A$ and $\varphi_2 : C \hookrightarrow B$ be the two monomorphisms associated to our amalgamation. Then we have the following presentation

$A \underset{C}{\ast} B = \langle X,Y \mid R,S, \varphi_1(c)= \varphi_2(c) \ \forall c \in C \rangle$.

Because $A \underset{C}{\ast} B$ is finitely presented, there exist $c_1, \dots, c_n \in C$ such that

$\Pi = \langle X,Y \mid R,S, \varphi_1(c_i) = \varphi_2(c_i), 1 \leq i \leq n \rangle$

is a presentation of $A \underset{C}{\ast} B$. Let $P$ denote the subgroup of $C$ generated by $\{c_1, \dots, c_n \}$. Then $\Pi$ may be identified with the amalgamated product $A \underset{P}{\ast} B$.

Because $C$ is not finitely generated, there exists $c \in C \backslash P$, and $\varphi_1(c) \varphi_2(c)^{-1} \neq 1$ in $\Pi$ since $\varphi_1(c) \notin \varphi_1(P)$ and $\varphi_2(c) \notin \varphi_2(P)$. However, $\varphi_1(c) = \varphi_2(c)$ in $A \underset{C}{\ast} B$, hence $\Pi \neq A \underset{C}{\ast} B$, a contradiction. $\square$

Property: Let $A$ be a finitely presented group. The HNN extension $\underset{C}{\ast} A$ is finitely presented if and only if $C$ is finitely generated.

Proof. Suppose by contradiction that $\underset{C}{\ast} A$ is finitely generated but that $C$ is not finitely generated. Let $\varphi_i : C \hookrightarrow A$ ($i=1,2$) denote the monomorphisms associated to our HNN extension; in particular, if $\langle X \mid R \rangle$ is a presentation of $A$,

$\underset{C}{\ast} A = \langle X,t \mid R, t \varphi_1(c) t^{-1}= \varphi_2(c) \ \forall c \in C \rangle$.

Because $\underset{C}{\ast} A$ is finitely presented, there exist $c_1, \dots, c_n \in C$ such that

$\Pi = \langle X ,t \mid R, t\varphi_1(c_i) t^{-1} = \varphi_2(c_i), 1 \leq i \leq n \rangle$

is a presentation of $\underset{C}{\ast} A$. Let $P$ denote the subgroup of $C$ generated by $\{ c_1, \dots, c_n \}$. In particular, $\Pi$ may be identified with the HNN extension $\underset{P}{\ast} A$.

Because $C$ is not finitely generated, there exists $c \in C \backslash P$. Since $\varphi_i(c) \notin \varphi_i(P)$ ($i=1,2$), $t\varphi_1(c) t^{-1} \varphi_2(c)^{-1} \neq 1$ in $\Pi$ according to Britton’s lemma; however, $t \varphi_1(c)t^{-1}= \varphi_2(c)$ in $\underset{C}{\ast} A$, hence $\Pi \neq \underset{C}{\ast} A$, a contradiction. $\square$

For example, we saw in the note A free group contains a free group of any rank that the derived subgroup of the free group $\mathbb{F}_2$ of rank two is not finitely-generated. Therefore, the following amalgamated product $\mathbb{F}_2 \underset{ [\mathbb{F}_2, \mathbb{F}_2] }{\ast} \mathbb{F}_2$ is not finitely-presented:

$\langle a,b, x,y \mid a^ib^ja^{-1} b^{-j} a^{1-i} = x^i y^j x^{-1}y^{-j} x^{1-i}, a^{-i} b^j ab^{-j}a^{i-1}= x^{-i} y^j xy^{-j} x^{i-1} \rangle$,

where $i > 0$ and $j \in \mathbb{Z} \backslash \{0\}$. The same thing can be done with a HNN extension.

Property: The lamplighter groups $L_n = \mathbb{Z}_n \wr \mathbb{Z}$ and $L= \mathbb{Z} \wr \mathbb{Z}$ are not finitely presented.

Proof. We give the proof only for $L_2$ : the other cases are similar. We have the presentation

$L_2= \langle a,t \mid a^2=1, [t^nat^{-n}, t^{n+1}at^{-n-1} ]=1, n \in \mathbb{Z} \rangle$.

In order to show that $L_2$ is not finitely presented, it is sufficient to show that the groups

$G_k = \langle a,t \mid a^2=1, [t^nat^{-n}, t^{n+1}at^{-n-1} ]=1, -k \leq n \leq k-1 \rangle$

are not isomorphic to $L_2$. First, with $a_n= t^nat^{-n}$, we get the equivalent presentation

$G_k = \langle a_{-k}, \dots, a_k,t \mid a_n^2=a_k^2=1, [a_n,a_{n+1}]=1, a_{n+1}= ta_nt^{-1} \rangle$,

where $-k \leq n\leq k-1$. We may recognize an HNN extension: Let

$A_k = \langle a_{-k}, \dots, a_k \mid a_n^2=a_k^2=1, [a_n,a_{n+1}]=1, -k \leq n \leq k-1 \rangle$,

$B_k = \langle a_{-k}, \dots, a_{k-1} \rangle$ and $C_k= \langle a_{-k+1}, \dots, a_k \rangle$ two subgroups of $A_k$, and $\varphi_k : B_k \to C_k$ the isomorphism defined by $\varphi_k(a_i)=a_{i+1}$ for all $-k \leq i \leq k-1$. Then

$G_k=HNN (A_k, B_k, C_k, \varphi_k)$.

Using Britton’s lemma, we deduce that the subgroup $\langle a_0,t \rangle$ of $G_k$ is isomorphic to $\mathbb{Z}_2 \ast \mathbb{Z}$. But $\mathbb{Z}_2 \ast \mathbb{Z}$  is not solvable, because it contains a nonabelian free group (for example, $abab^{-1}$ and $ab^2ab^{-2}$ generate a free group of rank two; see the third proof in A free group contains a free group of any rank); so $G_k$ cannot be solvable, whereas $L_2$ so is (as a semi-direct product of two abelian groups). In particular, $G_k$ and $L_2$ cannot be isomorphic. $\square$

## Amalgamated products and HNN extensions (I): A theorem of B.H. Neumann

This is the first note of a series dedicated to constructions using amalgamated products and HNN extensions. We begin with an embedding theorem (an alternative proof can be found in our previous note A free group contains a free group of any rank):

Theorem: (Higman-Neumann-Neumann) Any countable group $G$ can be embedded into a two-generator group $E$. Moreover, it can be supposed that any torsion element of $E$ is conjugated to a element of $G$.

Proof. Let $g_0=1, g_1,g_2, \dots$ be the elements of $G$ (not necessarily pairwise distinct), and let $U= \langle u,v \mid \ \rangle$, $B= \langle a,b \mid \ \rangle$ be two copies of the free group of rank two.

We first define the free product $A= G \ast U$. Clearly,

$\{g_0u, g_1vuv^{-1}, g_2 v^2uv^{-2}, \dots \}$

freely generates a subgroup $H \subset A$, because its projection into $U$ is the free subgroup generated by

$\{u, vuv^{-1}, v^2uv^{-2}, \dots \}$.

In the same way,

$\{ a, bab^{-1}, b^2ab^{-2}, \dots \}$

freely generates a subgroup $K \subset B$. Therefore, we may define the amalgamated free product $P= A \underset{H=K}{\ast} B$ by identifying $g_iv^iuv^{-i}$ with $b^iab^{-i}$. By construction, $P$ is generated by

$\{g_0,g_1,g_2, \dots, u,v,a,b \}$.

Because $g_iv^ivu^{-i}=b^ia b^{-i}$ and $u=g_0u=a$, in fact $P$ turns out to be generated by only the three elements $\{v,a,b\}$.

Then, notice that $\langle a,v \rangle$ and $\langle a,b \rangle$ are two subgroups of $P$ isomorphic to the free group of rank two. Indeed,

$\langle a,b \rangle \simeq B$ and $\langle v,a \rangle \simeq \langle v,g_0u \rangle \simeq \langle u,v \rangle \simeq U$.

Therefore, if $\varphi$ denotes the isomorphism between $\langle a,v \rangle$ and $\langle a,b \rangle$ sending $v$ to $a$ and $a$ to $b$, we may define the associated HNN extension $E$; let $t$ denotes its stable letter. Now $E$ is generated by $\{v,a,b,t \}$, but $tvt^{-1}=a$ and $tat^{-1}=b$, so $E$ is in fact generated by $\{v,t\}$.

Consequently, we just embedded $G$ into the two-generator group $E$. Moreover, we notice that a torsion element of $E$ is conjugated to an element of $G$ because a torsion element of an amalgamated product or of a HNN extension is necessarily conjugated to an element of a factor (and because $U$ and $B$ are torsion-free). $\square$

As a corollary, we deduce the following theorem that we already proved in the note Cantor-Bendixson rank in group theory: A theorem of B.H. Neumann, using the space of marked groups and small cancellation groups.

Theorem: (B.H. Neumann) There exist exactly $2^{\aleph_0}$ nonisomorphic two-generator groups.

Proof. First, because any two-generator group is a quotient of a free group of rank two, there are at most $2^{\aleph_0}$ nonisomorphic two-generator groups. To conclude, it is sufficient to exhibit a family of $2^{\aleph_0}$ nonisomorphic two-generator groups.

Let $p_1 < p_2 < \cdots$ denote the sequence of consecutive primes. For any subset $I \subset \mathbb{N}$, we define

$A_I = \bigoplus\limits_{i \in I} \mathbb{Z}_{p_i}$,

and $G_I$ the two-generator group associated to $A_I$ given by the previous theorem.

If $I \neq J$, say there exists $i \in I \backslash J$, $A_I$ (and a fortiori $G_I$) has an element of order $p_i$; however, $A_J$ (and a fortiori $G_J$) don’t. Therefore, $G_I$ and $G_J$ are not isomorphic. $\square$