In 1945, Alfred Tarski asked the question:

Let G be a group. How to determine the groups elementarily equivalent to G?

We answered the question when G is a divisible group in the previous note Elementary Theories of Divisible Groups. However, Tarski’s problem seemed to be dramatically difficult when G is a free group; in particular, it was not known wether two non-abelian free groups of finite rank were elementarily equivalent.

Some partial results have been showed in the last half of the twentieth century, but the first complete answer was given by Z. Sela between 2001 and 2006 in a series of papers untitled Diophantine Geometry over Groups. Of course, because of its complexity, it is not possible to describe the solution here: we restrict ourself to the weaker problem

How to describe the finitely generated groups having the same universal theory as a free group of finite rank?

The solution described here is based on the paper Limit groups as limits of free groups by C. Champetier and V. Guirardel, simplifying an argument of Z. Sela. Another argument, without using the space of marked groups, can be found in Chiswell’s book, Introduction to \Lambda-trees.

First, notice that \mathrm{Th}_{\forall}(\mathbb{F}_n)= \mathrm{Th}_{\forall} (\mathbb{F}_m) for all n,m \geq 2. It is a consequence of our previous note A free group contains a free group of any rank, showing that \mathbb{F}_n \hookrightarrow \mathbb{F}_m and \mathbb{F}_m \hookrightarrow \mathbb{F}_n. So the problem becomes

How to describe the finitely generated groups G satisfying \mathrm{Th}_{\forall}(G)= \mathrm{Th}_{\forall} (\mathbb{F}_2) or \mathrm{Th}_{\forall}(G)= \mathrm{Th}_{\forall} (\mathbb{Z})?

The space of marked groups has already been defined in our previous note Cantor-Bendixson rank in group theory. The link between universal theories and the space of marked groups is made explicit by the following lemma:

Lemma 1: Let (H_i,R_i) be a sequence of marked groups converging to (G,S). Then

\limsup\limits_{i \to + \infty} \mathrm{Th}_{\forall}(H_i) \subset \mathrm{Th}_{\forall}(G).

Conversely, if G and H are two finitely generated groups satisfying \mathrm{Th}_{\forall} (H) \subset \mathrm{Th}_{\forall} (G) then, for every marking S, (G,S) is the limit of (H,R_i) for some markings R_i.

Proof. Let (H_i,R_i) be a sequence of marked groups converging to (G,S) and let \sigma \notin \mathrm{Th}_{\forall} (G) be a universal formula. Then \neg \sigma \in \mathrm{Th}_{\exists} (G) and we may write

\neg \sigma = \exists x_1, \dots , x_m \Sigma(x_1, \dots, x_m),

where \Sigma is a system of equations and inequations. In particular, there exist g_1, \dots, g_m \in G such that G \models \Sigma(g_1, \dots, g_m). For all 1 \leq i \leq m, let w_i be a word so that g_i=w_i(S) in G.

Because G \models \Sigma(w_1(S),\dots, w_m(S)), we deduce that for all but finitely many i

H_i \models \Sigma(w_1(R_i),\dots, w_m(R_i)),

ie. \neg \sigma \in \mathrm{Th}_{\exists}(H_i) or \sigma \notin \mathrm{Th}_{\forall} (H_i). Thus, \sigma \notin \limsup\limits_{i \to + \infty} \mathrm{Th}_{\forall} (H_i).

Let G, H be two finitely generated groups satisfying \mathrm{Th}_{\forall} (H) \subset \mathrm{Th}_{\forall} (G) and let S be a marking of G. Let \{w_i \mid i \in I\} be the set of reduced words of length at most n over an alphabet of size |S|=m.

With J= \{i \in I \mid G \models (w_i(S)=1) \} and K= \{ i \in I \mid G \models (w_i(S) \neq 1) \} (in particular, I= J \coprod K), let \Sigma(x_1,\dots, x_m) be the system

\{ w_j(x_1, \dots, x_m)=1 \mid j \in J \} \cup \{ w_k(x_1,\dots, x_m) \neq 1 \mid k \in k \}.

Then \exists x_1, \dots, x_m \Sigma(x_1, \dots, x_m) \in \mathrm{Th}_{\exists}(G) \subset \mathrm{Th}_{\exists}(H) so there exist h_1,\dots, h_m \in H such that H \models \Sigma(h_1, \dots, h_m). Finally, with R_n= (h_1, \dots, h_m), d((H,R_n),(G,S)) \leq e^{-n} by construction hence (H,R_n) \underset{n \to + \infty}{\longrightarrow} (G,S). \square

The lemma above justifies the following family of groups as a possible solution of our weak Tarski’s problem:

Definition: A finitely generated group G is a limit group if there exists a marking S such that (G,S) is a limit of marked free groups.

We first notice that the property does not depend on the marking S, so that being a limit group becomes an algebraic property:

Lemma 2: Let (H_i,R_i) be a sequence of marked groups converging to (G,S) and let \tilde{S} be a marking of G. Then (G, \tilde{S}) is the limit of (H_i,\tilde{R}_i) for some marking \tilde{R}_i of H_i.

Proof. Let \tilde{S} = (\tilde{s}_1, \dots, \tilde{s}_m). Then for each 1 \leq i \leq m, there exists a word w_i such that \tilde{s}_i=w_i(S). Let \tilde{r}_{in} = w_i(R_n) and \tilde{R}_n= (\tilde{r}_{1n} , \dots, \tilde{r}_{mn}).

Notice that for any word ww(\tilde{s}_1, \dots, \tilde{s}_m)=w(w_1(S), \dots, w_m(S)), so w(\tilde{S})=1 in G if and only if w(\tilde{R}_n)= w(w_1(R_n), \dots, w_m(R_n))=1 in H_n for all but finitely many n (because (H_n, R_n) converges to (G,S)). Therefore, (H_n, \tilde{R}_n) converges to (G,\tilde{S}). \square

In particular, lemma 1 solves (weak) Tarski’s problem for \mathbb{Z}^m:

Corollary: A finitely generated group G has the same universal theory as \mathbb{Z} if and only if it is isomorphic to \mathbb{Z}^n for some n \geq 1.

Proof. If G has the same universal theory as \mathbb{Z} then G is a finitely generated torsion-free abelian group, so it is isomorphic to a free abelian group of finite rank. Conversely, it is sufficient to show that \mathbb{Z} and \mathbb{Z}^m have the same universal theory for every m \geq 1.

Because \mathbb{Z} \subset \mathbb{Z}^n, \mathrm{Th}_{\forall} (\mathbb{Z}^n) \subset \mathrm{Th}_{\forall}(\mathbb{Z}). Conversely, according to lemma 1, it is sufficient to notice that (\mathbb{Z}^m, \mathrm{can}) (where \mathrm{can}= \left( (1,0, \dots, 0),(0,1,\dots,0), \dots, (0,0, \dots, 1) \right) is the canonical marking) is the limit of (\mathbb{Z}, S_n) where S_n= \{ 1, 2^{2n}, 2^{3n}, \dots, 2^{mn} \}. More precisely, it can be shown that d((\mathbb{Z},S_n),(\mathbb{Z}^m, \mathrm{can})) \leq e^{1- 2^n}. \square

Corollary: Let G be a finitely generated group and m \geq 1. Then G and \mathbb{Z}^m are elementarily equivalent if and only if they are isomorphic.

Proof. Let \{ w_i \mid i \in I\} be the set of words of the form x_1^{\epsilon_1} \cdots x_m^{\epsilon_m} with \epsilon_i \in \{ 0,1 \} and

\sigma_m = \exists x_1,\dots,x_m \forall x \exists y \left( \bigvee\limits_{i \in I} x = 2y+ w_i(x_1, \dots,x_m) \right).

Then \mathbb{Z}^n \models \sigma_m is equivalent to | \mathbb{Z}^n / 2 \mathbb{Z}^n | \leq 2^m, ie. n \leq m. Therefore, \mathbb{Z}^n and \mathbb{Z}^m are elementarily equivalent if and only if n=m. Finally, we conclude using the previous corollary. \square

Now, we may prove that limit groups actually solve weak Tarski’s problem:

Theorem 1: Let G be a finitely generated group. Then G has the same universal theory as \mathbb{F}_2 or \mathbb{Z} if and only if G is an limit group.

Lemma 3: Let (H_i,R_i) be a sequence of marked groups converging to (G,S), K \subset G be a subgroup and T be a marking of K. Then there exist subgroups F_i \subset H_i and markings Q_i of F_i such that (F_i, Q_i) converges to (K,T).

Proof. Let T= (t_1, \dots, t_m). In particular, for all 1 \leq k \leq m, there exists a word w_k such that t_k=w_k(S). Let h_{ik}=w_k(R_i), F_i= \langle h_{i1}, \dots, h_{im} \rangle \leq H_i and Q_i=(h_{i1}, \dots, h_{im} ). Then for any word w:

w(T)=1 \ \text{in} \ K \Leftrightarrow w(w_1(S), \dots, w_m(S))=1 \ \text{in} \ G \\ \\ \hspace{1cm} \Leftrightarrow w(w_1(R_i), \dots, w_m(R_i)) = 1 \ \text{in} \ H_i \ \text{for all but finitely many} \ i \\ \\ \hspace{1cm} \Leftrightarrow w(Q_i)=1 \ \text{in} \ F_i \ \text{for all but finitely many} \ i

Therefore, (F_i,Q_i) converges to (K,T). \square

Lemma 4: A non-abelian 2-generator subgroup of a limit group is isomorphic to \mathbb{F}_2.

Proof. Let G be a limit group and let a,b \in G \backslash \{1\}. Using lemma 3, we deduce that \langle a,b \rangle is a limit group, and using lemma 2, we deduce that there exist free groups F_k and markings (e_k,f_k) such that (F_k,(e_k,f_k)) converges to (\langle a,b \rangle, (a,b)).

If \langle a,b \rangle were not free over \{a,b\}, there would exist a non-trivial relation w(a,b)=1 in G. In particular, w(e_k,f_k)=1 in F_k for all but finitely many k, so \mathrm{rank}(F_k) < 2. Therefore, (\langle a,b \rangle, (a,b)) would be the limit of abelian marked groups that is \langle a,b \rangle would be abelian itself: a contradiction. \square

Proof of theorem 1. The case where G is abelian is clear according to our previous corollaries. If \mathrm{Th}_{\forall} (G)= \mathrm{Th}_{\forall}(\mathbb{F}_2), then G is a limit group according to lemma 1. Conversely, suppose that G is a limit group. According to lemma 1, \mathrm{Th}_{\forall} (\mathbb{F}_2) \subset \mathrm{Th}_{\forall} (G). Moreover, if a,b \in G do not commute, \langle a,b \rangle \simeq \mathbb{F}_2 according to lemma 4 hence \mathrm{Th}_{\forall} (G) \subset \mathrm{Th}_{\forall} (\mathbb{F}_2). \square

Because of Los’ theorem, a natural way to “construct” a limit group is the following: Let \mathbb{F}_n be a free group of finite rank n \geq 2 and let \omega be a non-principal ultrafilter over \mathbb{N}. Then the ultrapower \mathbb{F}_n^{\omega} is elementarily equivalent to \mathbb{F}_n; therefore, any finitely generated subgroup L \subset \mathbb{F}_n^{\omega} is a limit group since \mathrm{Th}_{\forall} ( \mathbb{F}_n) = \mathrm{Th}_{\forall} \left( \mathbb{F}_n^{\omega} \right) \subset \mathrm{Th}_{\forall} (L) and using lemma 1.

In fact, the converse is also true:

Theorem 2: A finitely generated group is a limit group if and only if it embeds into an ultrapower of a free group of finite rank.

Notice that it is sufficient to consider the ultrapowers \mathbb{F}_2^{\omega} where \omega is non-principal. Our theorem is an easy consequence of the following lemma:

Lemma 5: Let (H_k,R_k) be a sequence of marked groups converging to (G,S). Then for all non-principal ultrafilter \omega, G embeds into the ultraproduct \prod\limits_{k \geq 1} H_k / \omega. Conversely, if G is a finitely generated subgroup of an ultraproduct \prod\limits_{k \geq 1} G_k / \omega (where \omega is non-principal), then for every marking S of G, there exist an increasing sequence (i_k), subgroups H_{i_k} \subset G_{i_k}, markings R_{i_k} of H_{i_k} such that (H_{i_k},R_{ik}) converges to (G,S).

Proof. Let (H_k,R_k) be a sequence of marked groups converging to (G,S). Notice that for any words w_1 and w_2, if w_1(S)=w_2(S) then w_1(R_k)=w_2(R_k) for all but finitely many k hence (w_1(R_k))=(w_2(R_k)) in \prod\limits_{k \geq 1} H_k / \omega. Therefore, the morphism

\varphi : \left\{ \begin{array}{ccc} G & \to & \prod\limits_{k \geq 1} H_k / \omega \\ w(S) & \mapsto & (w(R_k)) \end{array} \right. for any word w

is well-defined. Let w(S) \in \mathrm{ker}(\varphi). Then \{k \geq 1 \mid w(R_k)=1 \} belongs to \omega and is infinite in particular, so there exists k arbitrarily large such that w(R_k)=1 in H_k, hence w(S)=1. Therefore, \varphi is an embedding.

Let G be a finitely generated subgroup of an ultraproduct \prod\limits_{k \geq 1} H_k / \omega and let S be a marking of G. Let S=(s_1, \dots, s_m) where s_i=(r_{ik}). Set H_k= \langle r_{1k}, \dots, r_{mk} \rangle \leq G_k and R_k= (r_{1k}, \dots, r_{mk} ).

Now notice that \bigcap\limits_{ \ell g(w) \leq n} \{ k \geq 1 \mid w(R_k)=1 \Leftrightarrow w(S)=1 \} belongs to \omega and in particular is infinite. Therefore, there exists p arbitrarily large such that d((H_p,R_p),(G,S)) \leq e^{-n}. We deduce that the sequence (i_k) can be easily constructed by induction. \square

Finally, a purely algebraic characterization of limit groups can be stated:

Definition: A group G is fully residually free if for every finite set S \subset G \backslash \{1\} there exists a morphism \varphi from G to a free group F such that \varphi(g) \neq 1 for all g\in S.

Theorem 3: A finitely generated group G is a limit group if and only if it is fully residually free.

Lemma 6: Let \omega be a non-principal ultrafilter and let R be a finitely generated subring of \mathbb{Z}^{\omega}. Then R is fully residually \mathbb{Z}, that is for every finite subset S \subset R \backslash \{0\} there exists a ring homomorphism \rho : R \to \mathbb{Z} such that \rho(s) \neq 0 for all s \in S.

Proof. Because R is finitely generated, there exist t_1, \dots, t_n \in \mathbb{Z}^{\omega} such that R= \mathbb{Z} [t_1, \dots, t_n]. Let \mathbb{Z}[T_1, \dots, T_n ] denote the ring of n-variable polynomials and let

\varphi : \mathbb{Z}[T_1, \dots, T_n] \twoheadrightarrow \mathbb{Z} [t_1, \dots, T_n] = R

be the canonical projection. Because \mathbb{Z} [T_1, \dots, T_n] is noetherian, \mathrm{ker}(\varphi) is generated by finitely many elements f_1, \dots, f_s \in \mathbb{Z}[T_1, \dots, T_n].

Let r_1, \dots, r_m \in R \backslash \{0\} and g_1, \dots, g_m \in \mathbb{Z}[T_1, \dots, T_n] such that \varphi(g_i)=r_i for all 1 \leq i \leq m. Then

\left\{ \begin{array}{ll} f_i(t_1, \dots, t_n)=0, & 1 \leq i \leq s \\ g_i(t_1, \dots,t_n ) \neq 0, & 1 \leq i \leq m \end{array} \right.

Therefore, for all 1 \leq i \leq s (resp. 1 \leq i \leq m) and for \omega-almost all k, f_i(t_{1k}, \dots,t_{nk})=0 (resp. g_i(t_{1k}, \dots, t_{nk}) \neq 0). Thus, there exist x_1, \dots, x_n \in \mathbb{Z} such that

\left\{ \begin{array}{ll} f_i(x_1, \dots, x_n)=0, & 1 \leq i \leq s \\ g_i(x_1, \dots,x_n ) \neq 0, & 1 \leq i \leq m \end{array} \right.

 Now let \phi : \mathbb{Z}[T_1, \dots, T_n] \to \mathbb{Z} be the only morphism satisfying \phi(T_i)=x_i for all i. Because f_i(x_1, \dots, x_n)=0 for all i, \phi induces a morphism \overline{\phi} : R \to \mathbb{Z}. Because g_i(x_1, \dots, x_n) \neq 0 for all i, \overline{\phi}(r_i)= \phi(g_i) \neq 0 for all i.

We deduce that R is fully residually \mathbb{Z}. \square

Proof of theorem 3. Suppose that G is fully residually free. Let X be a finite generator set and let G_n \subset G \backslash \{1\} be the set of non-trivial elements of length at most n over X. For all n, let \phi_n be a morphism from G to a free group F_n such that \phi_n(g) \neq 1 for all g \in G_n. Finally, let the morphism

\varphi : \left\{ \begin{array}{ccc} G & \to & \prod\limits_{n \geq 1} F_n / \omega \\ g & \mapsto & (\phi_n(g)) \end{array} \right.,

where \omega is a non-principal ultrafilter. Let g \in G such that \ell g(g)=m \geq 1. Then g \in \bigcap\limits_{n \geq m} G_n so \phi_n(g) \neq 1 for all n \geq m. Thus, \{n \geq 1 \mid \phi_n(g) \neq 1 \} \in \omega ie. \varphi(g) \neq 1. Therefore, \varphi is injective and G is a limit group according to theorem 2.

Conversely, suppose that G is a limit group. According to theorem 2, there exists a non-principal ultrafilter \omega such that G \hookrightarrow \mathbb{F}_2^{\omega}. The canonical projection \mathbb{Z} \twoheadrightarrow \mathbb{Z}_p induces a morphism \varphi : SL_2(\mathbb{Z}) \to SL_2(\mathbb{Z}_p). Then the modular group \Gamma_p = \mathrm{ker}(\varphi) is a non-abelian free group.

(This fact is shown in Serre’s book, Trees. The idea is to notice that SL_2(\mathbb{Z}) acts on a tree in the hyperbolic plane, to deduce that SL_2(\mathbb{Z}) \simeq \mathbb{Z}_4 \underset{\mathbb{Z}_2}{\ast} \mathbb{Z}_6 and finally to show that a subgroup of SL_2(\mathbb{Z}) is free if and only if it is torsion-free.)

Thus, if \varphi^* : SL_2(\mathbb{Z}^{\omega}) \to SL_2(\mathbb{Z}_p^{\omega}) is induced by the canonical projection \mathbb{Z}^{\omega} \twoheadrightarrow \mathbb{Z}_p^{\omega},

G \hookrightarrow \mathbb{F}_2^{\omega} \hookrightarrow \Gamma_p^{\omega} \simeq \mathrm{ker}(\varphi^*).

Therefore, we may suppose without loss of generality that G is a subgroup of SL_2(\mathbb{Z}^{\omega}). Moreover, because G is finitely generated, there exists a finitely generated subring R of \mathbb{Z}^{\omega} such that G \leq SL_2(R).

Let g_1, \dots, g_n \in G \backslash \{1\} and let a_1, \dots, a_r \in R denote the non-zero coefficients of the matrices g_i - \mathrm{Id}. According to lemma 6, there exists a ring homomorphism \rho : R \to \mathbb{Z} such that \rho(a_i) \neq 0 for all i. In particular, \rho induces a ring homomorphism \overline{\rho} : SL_2(R) \to SL_2(\mathbb{Z}).

Noticing that \rho(G) \subset \Gamma_p since G \subset \mathrm{ker}(\varphi^*) and that \rho(g_i) \neq \mathrm{Id}, we deduce that G is fully residually free. \square

Finally, we proved:

Theorem A: Let G be a finitely generated group. Then the following statements are equivalent:

  1. G is an abelian limit group,
  2. G has the same universal theory as \mathbb{Z},
  3. G is abelian and embeds into an ultrapower \mathbb{F}_2^{\omega},
  4. G is abelian and fully residually free,
  5. G is isomorphic to \mathbb{Z}^n for some n\geq 1.

Theorem B: Let G be a finitely generated group. Then the following statements are equivalent:

  1. G is a non-abelian limit group,
  2. G has the same universal theory as \mathbb{F}_2,
  3. G embeds into an ultrapower \mathbb{F}_2^{\omega},
  4. G is non-abelian and fully residually free.

From theorems A and B, we may deduce the following properties of limit groups:

Property 1: The following statements hold:

  1. A limit group is torsion-free,
  2. A limit group is commutative-transitive (ie. if y \neq 1 commute with x and z, then x and y commute),
  3. A limit group is residually finite,
  4. A finitely-generated subgroup of a limit group is a limit group,
  5. A non-trivial 2-generator subgroup of a limit group is isomorphic to either \mathbb{Z}, \mathbb{Z}^2 or \mathbb{F}_2,
  6. Let G_1, \dots, G_n be finitely generated groups. Then G_1 \ast \cdots \ast G_n is a limit group if and only if G_1, \dots, G_n are limit groups.

We also have the following property as a consequence of lemma 7:

Property 2: A limit group (and more generally, any residually free group) is hopfian.

Lemma 7: Let G_1 \overset{\varphi_1}{\twoheadrightarrow} G_2 \overset{\varphi_2}{\twoheadrightarrow} G_3 \overset{\varphi_2}{\twoheadrightarrow} \dots be a sequence of epimorphisms between finitely generated residually free groups. Then all but finitely many epimorphisms are isomorphisms.

Indeed, if \varphi : G \to G is an epimorphism but not an isomorphism (where G is finitely generated and residually free), then the sequence G \overset{\varphi}{\twoheadrightarrow} G \overset{\varphi}{\twoheadrightarrow} G \overset{\varphi}{\twoheadrightarrow} \dots contradicts the lemma.

Proof: Let S_1=(s_1^{(1)}, \dots, s_n^{(1)}) be a generator set of G_1; then S_k:= \varphi_k(S_1)= (s_1^{(k)}, \dots, s_n^{(k)}) is a generator set of G_k by surjectivity of \varphi_k. Let V_k be the set of (M_1, \dots, M_n) \in SL_2(\mathbb{C})^n such that r(M_1, \dots, M_n)= \mathrm{Id} for every relation r of G_k.

Notice that V_k is an affine algebraic variety in \mathbb{C}^{4n} and V_1 \supset V_2 \supset \cdots, so the sequence (V_k) is eventually constant. To conclude, it is sufficient to show that if \varphi_k : G_k \to G_{k+1} is not an isomorphism, then V_{k+1} \subsetneq V_k.

Let r be a word such that r(S_{k+1})=1 in G_{k+1} but r(S_k) \neq 1 in G_k. G_k being residually free, there exists a morphism \rho : G_k \to \mathbb{F}_2 such that \rho(r) \neq 1. Because \mathbb{F}_2 is a subgroup of SL_2(\mathbb{C}), we may suppose that \rho : G_k \to SL_2(\mathbb{C}).

Let N_i = \rho(s_i^{(k)}) \in SL_2(\mathbb{C}). Then r(N_1, \dots, N_n)= \rho(r) \neq 1 so (N_1, \dots, N_n) \notin V_{k+1}. If w is a word over S_k such that w is a relation of G_k, then w(N_1, \dots, N_n) = \rho(w) = \rho(1)=1 so (N_1, \dots, N_n) \in V_k. \square

A difficult result about limit groups is:

Property: A limit group is finitely presented.

See for example V. Guirardel’s article, Limit groups and groups acting freely on \mathbb{R}^n-trees, for a proof based on actions on \Lambda-trees.

To conclude this note, let us mention a result giving examples of non-free limit groups:

Theorem 4: Let F be a free group and C \leq F be a cyclic subgroup closed under taking roots. Then F \underset{C}{\ast} F is a limit group.

A proof can be found in Henry Wilton’s document, An introduction to limit groups (proprosition 2.9). In particular, the fundamental group of a surface \Sigma is a limit group when \Sigma is not a non-orientable surface whose Euler characteristic -1, 0 or 1.

Advertisements