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:

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:

Figure1

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.

Figure2

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

Follow

Get every new post delivered to your Inbox.