In 1945, Alfred Tarski asked the question:
Let be a group. How to determine the groups elementarily equivalent to ?
We answered the question when is a divisible group in the previous note Elementary Theories of Divisible Groups. However, Tarski’s problem seemed to be dramatically difficult when 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 -trees.
First, notice that for all . It is a consequence of our previous note A free group contains a free group of any rank, showing that and . So the problem becomes
How to describe the finitely generated groups satisfying or ?
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 be a sequence of marked groups converging to . Then
Conversely, if and are two finitely generated groups satisfying then, for every marking , is the limit of for some markings .
Proof. Let be a sequence of marked groups converging to and let be a universal formula. Then and we may write
where is a system of equations and inequations. In particular, there exist such that . For all , let be a word so that in .
Because , we deduce that for all but finitely many
ie. or . Thus, .
Let , be two finitely generated groups satisfying and let be a marking of . Let be the set of reduced words of length at most over an alphabet of size .
With and (in particular, ), let be the system
Then so there exist such that . Finally, with , by construction hence .
The lemma above justifies the following family of groups as a possible solution of our weak Tarski’s problem:
Definition: A finitely generated group is a limit group if there exists a marking such that is a limit of marked free groups.
We first notice that the property does not depend on the marking , so that being a limit group becomes an algebraic property:
Lemma 2: Let be a sequence of marked groups converging to and let be a marking of . Then is the limit of for some marking of .
Proof. Let . Then for each , there exists a word such that . Let and .
Notice that for any word , , so in if and only if in for all but finitely many (because converges to ). Therefore, converges to .
In particular, lemma 1 solves (weak) Tarski’s problem for :
Corollary: A finitely generated group has the same universal theory as if and only if it is isomorphic to for some .
Proof. If has the same universal theory as then 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 and have the same universal theory for every .
Because , . Conversely, according to lemma 1, it is sufficient to notice that (where is the canonical marking) is the limit of where . More precisely, it can be shown that .
Corollary: Let be a finitely generated group and . Then and are elementarily equivalent if and only if they are isomorphic.
Proof. Let be the set of words of the form with and
Then is equivalent to , ie. . Therefore, and are elementarily equivalent if and only if . Finally, we conclude using the previous corollary.
Now, we may prove that limit groups actually solve weak Tarski’s problem:
Theorem 1: Let be a finitely generated group. Then has the same universal theory as or if and only if is an limit group.
Lemma 3: Let be a sequence of marked groups converging to , be a subgroup and be a marking of . Then there exist subgroups and markings of such that converges to .
Proof. Let . In particular, for all , there exists a word such that . Let , and . Then for any word :
Therefore, converges to .
Lemma 4: A non-abelian -generator subgroup of a limit group is isomorphic to .
Proof. Let be a limit group and let . Using lemma 3, we deduce that is a limit group, and using lemma 2, we deduce that there exist free groups and markings such that converges to .
If were not free over , there would exist a non-trivial relation in . In particular, in for all but finitely many , so . Therefore, would be the limit of abelian marked groups that is would be abelian itself: a contradiction.
Proof of theorem 1. The case where is abelian is clear according to our previous corollaries. If , then is a limit group according to lemma 1. Conversely, suppose that is a limit group. According to lemma 1, . Moreover, if do not commute, according to lemma 4 hence .
Because of Los’ theorem, a natural way to “construct” a limit group is the following: Let be a free group of finite rank and let be a non-principal ultrafilter over . Then the ultrapower is elementarily equivalent to ; therefore, any finitely generated subgroup is a limit group since 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 where is non-principal. Our theorem is an easy consequence of the following lemma:
Lemma 5: Let be a sequence of marked groups converging to . Then for all non-principal ultrafilter , embeds into the ultraproduct . Conversely, if is a finitely generated subgroup of an ultraproduct (where is non-principal), then for every marking of , there exist an increasing sequence , subgroups , markings of such that converges to .
Proof. Let be a sequence of marked groups converging to . Notice that for any words and , if then for all but finitely many hence in . Therefore, the morphism
for any word
is well-defined. Let . Then belongs to and is infinite in particular, so there exists arbitrarily large such that in , hence . Therefore, is an embedding.
Let be a finitely generated subgroup of an ultraproduct and let be a marking of . Let where . Set and .
Now notice that belongs to and in particular is infinite. Therefore, there exists arbitrarily large such that . We deduce that the sequence can be easily constructed by induction.
Finally, a purely algebraic characterization of limit groups can be stated:
Definition: A group is fully residually free if for every finite set there exists a morphism from to a free group such that for all .
Theorem 3: A finitely generated group is a limit group if and only if it is fully residually free.
Lemma 6: Let be a non-principal ultrafilter and let be a finitely generated subring of . Then is fully residually , that is for every finite subset there exists a ring homomorphism such that for all .
Proof. Because is finitely generated, there exist such that . Let denote the ring of -variable polynomials and let
be the canonical projection. Because is noetherian, is generated by finitely many elements .
Let and such that for all . Then
Therefore, for all (resp. ) and for -almost all , (resp. ). Thus, there exist such that
Now let be the only morphism satisfying for all . Because for all , induces a morphism . Because for all , for all .
We deduce that is fully residually .
Proof of theorem 3. Suppose that is fully residually free. Let be a finite generator set and let be the set of non-trivial elements of length at most over . For all , let be a morphism from to a free group such that for all . Finally, let the morphism
where is a non-principal ultrafilter. Let such that . Then so for all . Thus, ie. . Therefore, is injective and is a limit group according to theorem 2.
Conversely, suppose that is a limit group. According to theorem 2, there exists a non-principal ultrafilter such that . The canonical projection induces a morphism . Then the modular group is a non-abelian free group.
(This fact is shown in Serre’s book, Trees. The idea is to notice that acts on a tree in the hyperbolic plane, to deduce that and finally to show that a subgroup of is free if and only if it is torsion-free.)
Thus, if is induced by the canonical projection ,
Therefore, we may suppose without loss of generality that is a subgroup of . Moreover, because is finitely generated, there exists a finitely generated subring of such that .
Let and let denote the non-zero coefficients of the matrices . According to lemma 6, there exists a ring homomorphism such that for all . In particular, induces a ring homomorphism .
Noticing that since and that , we deduce that is fully residually free.
Finally, we proved:
Theorem A: Let be a finitely generated group. Then the following statements are equivalent:
- is an abelian limit group,
- has the same universal theory as ,
- is abelian and embeds into an ultrapower ,
- is abelian and fully residually free,
- is isomorphic to for some .
Theorem B: Let be a finitely generated group. Then the following statements are equivalent:
- is a non-abelian limit group,
- has the same universal theory as ,
- embeds into an ultrapower ,
- 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:
- A limit group is torsion-free,
- A limit group is commutative-transitive (ie. if commute with and , then and commute),
- A limit group is residually finite,
- A finitely-generated subgroup of a limit group is a limit group,
- A non-trivial -generator subgroup of a limit group is isomorphic to either , or ,
- Let be finitely generated groups. Then is a limit group if and only if 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 be a sequence of epimorphisms between finitely generated residually free groups. Then all but finitely many epimorphisms are isomorphisms.
Indeed, if is an epimorphism but not an isomorphism (where is finitely generated and residually free), then the sequence contradicts the lemma.
Proof: Let be a generator set of ; then is a generator set of by surjectivity of . Let be the set of such that for every relation of .
Notice that is an affine algebraic variety in and , so the sequence is eventually constant. To conclude, it is sufficient to show that if is not an isomorphism, then .
Let be a word such that in but in . being residually free, there exists a morphism such that . Because is a subgroup of , we may suppose that .
Let . Then so . If is a word over such that is a relation of , then so .
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 -trees, for a proof based on actions on -trees.
To conclude this note, let us mention a result giving examples of non-free limit groups:
Theorem 4: Let be a free group and be a cyclic subgroup closed under taking roots. Then 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 is a limit group when is not a non-orientable surface whose Euler characteristic -1, 0 or 1.