THE VIRTUAL ISOMORPHISM PROBLEM FOR FINITELY GENERATED GROUPS

SIMON THOMAS

Abstract. We prove that the problem of classifying finitely generated groups up to virtual isomorphism is strictly harder than that of classifying them up to isomorphism, in the sense that there is a Borel reduction from the isomorphism problem to the virtual isomorphism problem, but not vice versa.

1. Introduction

Two groups G_{1}, G_{2} are said to be virtually isomorphic or commensurable up to finite kernels, written G_{1} ≈ G_{2}, iff there exist subgroups N_{i} ⩽ H_{i} ⩽ G_{i} for i = 1, 2 satisfying the following conditions.

(a) [G_{1} : H_{1}], [G_{2} : H_{2}] < ∞.

(b) N_{1}, N_{2} are finite normal subgroups of H_{1}, H_{2} respectively.

(c) H_{1}/N_{1} ≅ H_{2}/N_{2}. It is easily checked that ≈ is an equivalence relation on the class of groups. In this paper, we shall show that the problem of classifying finitely generated groups up to virtual isomorphism is strictly harder than that of classifying them up to isomorphism, in the sense that there is an explicit reduction from the isomorphism problem to the virtual isomorphism problem, but not vice versa.

Before we can give exact statements of our main results, we first need to situate our classification problems within the context of descriptive set theory and to discuss the notion of Borel reducibility. (Here we follow Friedman-Stanley [1] and Hjorth-Kechris [3].) We shall begin by describing how to represent the class of countably infinite structures of a given first order language by the elements of a standard Borel space; i.e., a Polish space equipped with its associated σ-algebra of Borel subsets. For convenience, we shall work only with relational first-order languages. If there are function symbols, as is the case with the language of group theory, then we replace them by relation symbols representing the graphs of the

Research partially supported by NSF Grants.

2 SIMON THOMAS

associated functions. Given a countable first-order language L = {R_{i} | i ∈ I}, where R_{i} is an n_{i}-ary relation symbol, let

X_{L} = ∏_{i∈I} 2^{ℕ^{n_{i}}} .

(Here 2^{ℕ^{n_{i}}} denotes the space of all n_{i}-ary functions f : ℕ^{n_{i}} → {0, 1} with the natural product topology.) Then X_{L} is a Polish space and the elements of X_{L} code L-structures with universe ℕ as follows. Given x = (x_{i})_{i∈I} ∈ X_{L}, the structure

M_{x} = ⟨ℕ, R_{i}^{x}⟩_{i∈I}

represented by x is defined by:

R_{i}^{x}(k_{1}, …, k_{n_{i}}) iff x_{i}(k_{1}, …, x_{n_{i}}) = 1.

Recall that the set of formulas of the infinitary language L_{ω_{1},ω} is defined as follows. (i) Every atomic formula is an L_{ω_{1},ω} formula. (ii) If φ, ψ are L_{ω_{1},ω} formulas and x is a variable, then ¬φ, φ ∧ ψ, φ ∨ ψ, φ → ψ,

φ ↔ ψ, ∀φ and ∃xφ are also L_{ω_{1},ω} formulas. (iii) If {φ_{n} | n ∈ ω} is a countable set of L_{ω_{1},ω} formulas, then the countable

conjunction ⋀_{n∈ω} φ_{n} and the countable disjunction ⋁_{n∈ω} φ_{n} are also L_{ω_{1},ω} formulas.

If σ is an L_{ω_{1},ω} sentence, then

Mod(σ) = {x ∈ X_{L} | M_{x} ⊧ σ}

represents the class of all countably infinite models of σ. It is easily checked that Mod(σ) is a Borel subset of X_{L}. Hence, by Kechris [4, 13.4], Mod(σ) is a standard Borel space. We shall usually denote the restriction of the isomorphism relation ≅ to Mod(σ) by ≅_{σ}; and when working with Mod(σ), we shall usually identify M_{x} with x.

In this paper, we shall be mainly interested in the standard Borel space G of (infinite) finitely generated groups. (Clearly the class of finitely generated groups is axiomatizable by an L_{ω_{1},ω} sentence in the language L = {R} consisting of a ternary relation which represents the graph of the multiplication operation.) Unless otherwise stated, throughout this paper, ≅ will always denote the isomorphism relation on G.

VIRTUAL ISOMORPHISM OF FINITELY GENERATED GROUPS 3

The notion of Borel reducibility will enable us to compare the complexity of equivalence relations on standard Borel spaces; and, in particular, will provide us with a measure of the complexity of the isomorphism relation ≅ and the virtual isomorphism relation ≈ on G. Suppose that E, F are equivalence relations on the standard Borel spaces X, Y respectively. Then we say that E is Borel reducible to F and write E ≤_{B} F if there exists a Borel function f : X → Y such that xEy iff f(x)F f(y). Such a map f is called a Borel reduction from E to F. We say that E and F are Borel bireducible and write E ∼_{B} F if both E ≤_{B} F and F ≤_{B} E. Finally we write E <_{B} F if both E ≤_{B} F and F ≰_{B} E.

The notion of a Borel reduction is intended to capture the idea of an explicit reduction. For example, let S be a fixed infinite finitely generated simple group and consider the Borel map f : G → G defined by

f(A) = (Alt(5) wr A) wr S.

(Strictly speaking, f(A) should be a group with underlying set ℕ. However, this causes no difficulties, since each group f(A) has a canonical isomorphism to such a group f^{∗}(A) ∈ G.) In Section 2, we shall prove that if A, B ∈ G, then

A ≅ B iff f(A) ≈ f(B).

Thus f is a Borel reduction from ≅ to ≈.

Theorem 1.1. (≅) ≤_{B} (≈).

In Section 3, we shall prove that (≈) ≰_{B} (≅) and hence that (≅) <_{B} (≈). In order to see why this is true, we need to recall some results from the theory of Polish group actions. Let G be a Polish group. Then a standard Borel G-space is a standard Borel space X equipped with a Borel action (g, x) ↦ g · x of G on X. The corresponding orbit equivalence relation E_{G}^{X} on X is defined by

xE_{G}^{X}y iff there exists g ∈ G such that g · x = y.

For example, let L be a countable language and consider the standard Borel space X_{L} of countably infinite L-structures. The symmetric group S_{∞} on ℕ is a Polish group with the usual product topology inherited from ℕ^{ℕ} and the natural action of S_{∞} on X_{L} is continuous. Furthermore, if x, y ∈ X_{L}, then x, y lie in the same S_{∞}-orbit iff M_{x} ≅ M_{y}. Thus X_{L} is a standard Borel S_{∞}-space and the

4 SIMON THOMAS

isomorphism relation on X_{L} is precisely the S_{∞}-orbit equivalence relation relation. In [5], Kechris-Louveau found the following basic obstruction for Borel reducibility to an equivalence relation of the form E_{G}^{X}.

Definition 1.2. E_{1} is the Borel equivalence relation on (2^{ℕ})^{ℕ} defined by

xE_{1}y iff x(m) = y(m) for almost all m ∈ ℕ.

Theorem 1.3 (Kechris-Louveau [5]). Suppose that G is a Polish group and that X is a Polish G-space. Then E_{1} ≰_{B} E_{G}^{X}.

In Section 3, we shall prove the following result.

Theorem 1.4. E_{1} ≤_{B} (≈).

Hence if L be a countable language and σ is an L_{ω_{1},ω} sentence, then (≈) ≰_{B} (≅_{σ}). In particular, (≈) ≰_{B} (≅), where ≅ is the isomorphism relation on the standard Borel space G of finitely generated groups, and so we obtain the following result.

Theorem 1.5. (≅) <_{B} (≈).

It is easily checked that ≈ is a Borel equivalence relation. Thus ≈ is a natural example of a Borel equivalence relation which is not Borel reducible to the orbit equivalence relation of a Borel action of a Polish group. (A detailed account of the Borel complexity of the isomorphism relation ≅ for finitely generated groups can be found in Thomas-Velickovic [9].)

Finally let ∼ denote the quasi-isometry relation on the standard Borel space G of finitely generated groups. (A clear account of the basic properties of the quasiisometry relation can be found in de la Harpe [2].) It is well-known that if G_{1}, G_{2} are virtually isomorphic, then G_{1}, G_{2} are quasi-isometric. It is natural to ask about the Borel complexity of the quasi-isometry relation ∼.

Conjecture 1.6. (≅) <_{B} (∼).

Question 1.7. Is (≈) <_{B} (∼)?

VIRTUAL ISOMORPHISM OF FINITELY GENERATED GROUPS 5

2. Wreath products

In this section, we shall prove Theorem 1.1. Throughout S will denote a fixed infinite finitely generated simple group. We shall prove that if A and B are arbitrary groups, then

A ≅ B iff (Alt(5) wr A) wr S ≈ (Alt(5) wr B) wr S.

In particular, by restricting our attention to the case when A and B are finitely generated, we obtain that (≅) ≤_{B} (≈).

We shall begin by establishing our notation. Let H, C be groups. If f : H → C, then the support σ(f) is defined by

σ(f) = {x ∈ H | f(x) ≠ 1}.

The direct sum of C by H is defined to be the group

C^{(H)} = {f : H → C | σ(f) is finite },

equipped with pointwise multiplication; i.e., if f, g ∈ C^{(H)}, then

(fg)(x) = f(x)g(x) for all x ∈ H.

There is a natural action of H on C^{(H)} defined by f^{a}(x) = f(xa^{−1}) for all f ∈ C^{(H)} and a, x ∈ H. The (restricted) wreath product C wr H is defined to be the corresponding semidirect product

{(a, f) | a ∈ H and f ∈ C^{(H)}}

with multiplication defined by

(a, f)(b, g) = (ab, f^{b}g).

The subgroup C^{(H)} is usually called the base group of C wr H. For each subset X ⊆ H, let C^{(X)} be the subgroup of the base group defined by

C^{(X)} = {f ∈ C^{(H)} | σ(f) ⊆ X}.

As usual, we identify S and C^{(H)} with the corresponding subgroups of C wr H; and we usually write af instead of (a, f).

In the next four lemmas, we shall explain how to recognise the group C within an arbitrary subgroup H of finite index in C wr S.

6 SIMON THOMAS

Lemma 2.1. Let C be an arbitrary group and let K be the base subgroup of the wreath product W = C wr S.

(a) W′ = [S, K]S.

(b) Suppose that N is a normal subgroup of W such that S ⩽ N. Then W′ ⩽ N.

(c) W′′ = W′.

Proof. Clauses 2.1(a) and 2.1(b) follow immediately from Theorem 4.1, Corollary 4.5 and Lemma 8.2 of Neumann [6]. To see that clause 2.1(c) holds, consider the canonical surjection, φ : W → W/W′′. Since S is a simple nonabelian group and W/W′′ is solvable, it follows that S ⩽ W′′. Hence, by 2.1(b), W′ ⩽ W′′.

Lemma 2.2. With the hypotheses of Lemma 2.1, suppose that H ⩽ W is a subgroup of finite index.

(a) H′ = W′.

(b) H has no finite normal subgroups.

Proof. Since [W : H] < ∞, there exists a normal subgroup N ⊴ W such that N ⩽ H and [W : N] < ∞. Since S is an infinite simple group, it follows that S ⩽ N. Hence, by Lemma 2.1(b), W′ ⩽ N. Since W′ ⩽ H ⩽ W, Lemma 2.1(c) yields that W′ = W′′ ⩽ H′ ⩽ W′ and so H′ = W′. To see that clause 2.2(b) holds, note that S ⩽ W′ ⩽ H and that w^{S} is infinite for every 1 ≠ w ∈ W.

Lemma 2.3. With the hypotheses of Lemma 2.1, suppose that 1 ≠ g ∈ W′. Let L = ⟨g^{W′}⟩ and R = ⟨g^{L}⟩. Then C_{L}(R) ≠ 1 iff g ∈ [S, K].

Proof. First suppose that 1 ≠ g ∈ [S, K] and let X = σ(g). Then L ⩽ [S, K] ⩽ K and so R ⩽ C^{(X)}. If s ∈ S, then σ(g^{s}) = σ(g) · s. Hence if s ∈ S is chosen so that σ(g) ∩ σ(g) · s = ∅, then 1 ≠ g^{s} ∈ C_{L}(R).

Now suppose that g = af, where 1 ≠ a ∈ S and f ∈ [S, K]. In this case, it is easily seen that for each b ∈ S, there exists f_{b} ∈ [S, K] such that bf_{b} ∈ R. Suppose that sh ∈ C_{L}(R), where s ∈ S and h ∈ [S, K]. Then it is clear that s = 1. Also for each b ∈ S, we have that

(b, f_{b}h) = (b, f_{b})(1, h) = (1, h)(b, f_{b}) = (b, h^{b}f_{b})

and so h^{b} = f_{b}hf_{b}^{−1}. Hence

σ(h) · b = σ(h^{b}) = σ(f_{b}hf_{b}^{−1}) = σ(h)

for all b ∈ S, which implies that σ(h) = ∅ and so h = 1.

Lemma 2.4. With the hypotheses of Lemma 2.1, suppose that s, t are distinct elements of S. Then

(W′ ∩ C^{({s,t})}) / (W′ ∩ C^{({t})}) ≅ C.

Proof. Consider the homomorphism φ : W′ ∩ C^{({s,t})} → C defined by φ(f) = f(s). Clearly ker φ = W′ ∩ C^{({t})}. By Theorem 4.1 and Corollary 4.5 of Neumann [6],

W′ ∩ K = [S, K] = {f ∈ K | ∏_{x∈σ(f)} f(x) ∈ C′}.

It follows that φ is surjective.

Theorem 2.5. If A and B are arbitrary groups, then

A ≅ B iff (Alt(5) wr A) wr S ≈ (Alt(5) wr B) wr S.

Proof. For each group A, let Â = Alt(5) wr A and let W_{A} = Â wr S. Let K̂_{A}, K_{A} be the base groups of Â, W_{A} respectively. Suppose that A, B are groups such that W_{A} ≈ W_{B}. By Neumann [6, 10.10.1],

Alt(5) wr A ≅ Alt(5) wr B iff A ≅ B.

Hence it is enough to show that Â ≅ B̂. Lemma 2.2(b) implies that there exist subgroups H_{A}, H_{B} of finite index in W_{A}, W_{B} respectively such that H_{A} ≅ H_{B}; say, π : H_{A} → H_{B} is an isomorphism. By Lemma 2.2(a), π (W′_{A}) = W′_{B}; and hence, by Lemma 2.3, π ([S, K_{A}]) = [S, K_{B}]. Let 1 ≠ c ∈ S. Then, by Lemma 2.4, it is enough to prove the following result.

Claim 2.6. There exist s ≠ t ∈ S such that π (W′_{A} ∩ Â^{({c})}) = W′_{B} ∩ B̂^{({t})} and π (W′_{A} ∩ Â^{({1,c})}) = W′_{B} ∩ B̂^{({s,t})}.

To see this, for each f ∈ [S, K_{A}], let L_{f} = ⟨f^{[S,K_{A}]}⟩ and R_{f} = C_{[S,K_{A}]}(L_{f}). Using the fact that Alt(5) is a simple nonabelian group, it is easily checked that the base group K̂_{A} is the unique nontrivial minimal normal subgroup of Â = Alt(5) wr A. It now follows that

{h ∈ W′_{A} ∩ Â^{(σ(f))} | h(x) ∈ K̂_{A} for all x ∈ X} ⩽ L_{f} ⩽ W′_{A} ∩ Â^{(σ(f))}

8 SIMON THOMAS

and hence that

R_{f} = {h ∈ [S, K_{A}] | h(x) = 1 for all x ∈ X}.

This implies that

C_{[S,K_{A}]}(R_{f}) = W′_{A} ∩ Â^{(σ(f))}.

(In particular, |σ(f)| = 1 iff C_{[S,K_{A}]}(R_{f}) is minimal amongst the subgroups of the form C_{[S,K_{A}]}(R_{h}) for h ∈ [S, K_{A}], etc.) Of course, the analogous result also holds for each f ∈ [S, K_{B}]; and Claim 2.6 follows easily. This completes the proof of Theorem 2.5.

3. Central extensions of Tarski monsters

In this section, we shall prove Theorem 1.4. First we shall need to discuss presentations over free products and their corresponding free central extensions. (For a full account of these notions, see Ol’shanskii [8, Chapter 11].) For our purposes, it will be enough to consider the case when there are only two factors. Let A, B be nontrivial groups and let F = A ∗ B be their free product. Suppose that G is a group which can be generated by isomorphic copies of A, B. Then G can be naturally identified with the quotient group F/N, where N is the kernel of the canonical surjective homomorphism F → G. Clearly N can be specified as the normal closure in F of a set of relations R. We say that

G = ⟨F | r = 1, r ∈ R⟩ (3.1)

is a presentation of G over the free product F. The corresponding free central extension of G is defined to be Γ = F/[F, N]. Note that Γ is an extension of G = F/N by the central subgroup \overline{N} = N/[F, N]. The group G = F/N is said to be (diagrammatically) aspherical if every spherical diagram over the presentation (3.1) is either non-reduced or consists entirely of 0-cells. (The definition of a spherical diagram can be found in Ol’shanskii [8, Chapter 11]. However, a knowledge of this definition is not necessary in order to understand the rest of this paper.) We shall make use of the following result of Ol’shanskii [8, 34.1] in the proof of Theorem 1.4.

Theorem 3.1. If G = F/N is aspherical, then \overline{N} = N/[F, N] is a free abelian group with basis \{\overline{r} | r ∈ R\}, where \overline{r} = r[F, N].

VIRTUAL ISOMORPHISM OF FINITELY GENERATED GROUPS 9

Recall that a group G is said to be complete iff Z(G) = 1 and every automorphism of G is inner. We shall also make use of the following result. (Obraztsov does not mention explicitly that R is infinite. However, this is an easy consequence of the proof of Ol’shanskii [8, 34.15].)

Theorem 3.2 (Obraztsov [7]). Let p be a sufficiently large prime and let A = ⟨a⟩, B = ⟨b⟩ be cyclic groups of order p. Then there exists a presentation

G = ⟨F | r = 1, r ∈ R⟩

over F = A ∗ B which satisfies the following properties.

(i) G is an infinite simple complete group, all of whose proper subgroups are cyclic of order p.

(ii) G is aspherical. (iii) R is infinite.

Fix such a group G = F/N and let Γ = F/[F, N] be the corresponding free central extension. Let R = {r_{n} | n ∈ ℕ} and let {q_{n} | n ∈ ℕ} be an enumeration of the primes q ≠ p. For each x ∈ (2^{ℕ})^{ℕ}, we shall define a corresponding group Γ_{x} by adding further relations to the presentation

Γ = ⟨F | [r, a] = [r, b] = 1, r ∈ R⟩. (3.2)

These relations will be chosen to trivialize suitably chosen elements of \overline{N}, so that each Γ_{x} will also be a central extension of G.

Definition 3.3. Express ℕ = ⨆{I_{m} | m ∈ ℕ} as the disjoint union of countably many infinite subsets; and for each m ∈ ℕ, let {ℓ_{m,j} | j ∈ ℕ} be the increasing enumeration of I_{m}. Then Γ_{x} is the group defined by adding the following relations to the presentation (3.2):

• r_{t} = 1, if t = ℓ_{m,j} and x(m)(j) = 0;

• r_{t}^{q_{m}} = 1, if t = ℓ_{m,j} and x(m)(j) = 1;

• r_{s} = r_{t}, if s = ℓ_{m,i}, t = ℓ_{m,j} and x(m)(i) = x(m)(j) = 1. For each m ∈ ℕ, let z_{x,m} ∈ Γ_{x} be the central element defined by z_{x,m} = r_{t}, where t = ℓ_{m,j} satisfies x(m)(j) = max{x(m)(i) | i ∈ ℕ}.

10 SIMON THOMAS

Thus Z(Γ_{x}) is the direct sum of the cyclic subgroups ⟨z_{x,m}⟩ such that x(m) ≢ 0. We shall split the proof of Theorem 1.4 into a sequence of lemmas.

Lemma 3.4. Γ_{x} ≅ Γ_{y} iff x = y.

Proof. Suppose that φ : Γ_{x} → Γ_{y} is an isomorphism. Then φ induces an automorphism

\overline{φ} : G = Γ_{x}/Z(Γ_{x}) → Γ_{y}/Z(Γ_{y}) = G.

Since G is complete, after adjusting φ by an inner automorphism of Γ_{y} if necessary, we can suppose that there exist elements z_{1}, z_{2} ∈ Z(Γ_{y}) such that φ(a) = az_{1} and φ(b) = bz_{2}. Since the order of each nontrivial element of Z(Γ_{y}) is relatively prime to p, we must have that z_{1} = z_{2} = 1. Hence a, b satisfy exactly the same identities in Γ_{x} and Γ_{y}; and this implies that x = y.

Lemma 3.5. If xE_{1}y, then Γ_{x} ≈ Γ_{y}.

Proof. Let xE_{1}y and let F = {m ∈ ℕ | x(m) ≠ y(m)}. Then N_{x} = ⟨z_{x,m} | m ∈ F ⟩ and N_{y} = ⟨z_{y,m} | m ∈ F ⟩ are finite normal subgroups of Γ_{x}, Γ_{y} respectively and clearly Γ_{x}/N_{x} ≅ Γ_{y}/N_{y}.

Lemma 3.6. (a) Every finite normal subgroup of Γ_{x} is central.

(b) Γ_{x} has no proper subgroups of finite index.

Proof. Let π : Γ_{x} → G be the canonical surjection. If N ⊴ Γ_{x} is a finite normal subgroup, then clearly π(N) = 1 and so N ⩽ ker π = Z(Γ_{x}).

Now suppose that H ⩽ Γ_{x} is a subgroup of finite index. Then π(H) = G and so there exist elements z_{1}, z_{2} ∈ Z(Γ_{x}) such that az_{1}, bz_{2} ∈ H. Since the orders of z_{1}, z_{2} are relatively prime to p, it follows that a, b ∈ H and hence H = Γ_{x}.

Lemma 3.7. If Γ_{x} ≈ Γ_{y}, then xE_{1}y.

Proof. Suppose that Γ_{x} ≈ Γ_{y}. By Lemma 3.6, there exist finite central subgroups N_{x}, N_{y} such that Γ_{x}/N_{x} ≅ Γ_{y}/N_{y}. Since Z(Γ_{x}) = ⟨z_{x,m} | m ∈ ℕ⟩ is a direct sum of cyclic groups of distinct prime orders, it follows that there exists a finite subset F ⊆ ℕ such that N_{x} = ⟨z_{x,m} | m ∈ F ⟩ and hence there exists x′ ∈ (2^{ℕ})^{ℕ} with x′E_{1}x such that Γ_{x}/N_{x} ≅ Γ_{x′}. Similarly there exists y′ ∈ (2^{ℕ})^{ℕ} with y′E_{1}y such that Γ_{y}/N_{y} ≅ Γ_{y′}. By Lemma 3.4, x′ = y′ and hence xE_{1}y.

This completes the proof of Theorem 1.4.

References

[1] H. Friedman and L. Stanley, A Borel reducibility theory for classes of countable structures, Journal of Symbolic Logic 54 (1989), 894–914.

[2] P. de la Harpe, Topics in Geometric Group Theory, Chicago Lectures in Mathematics Series, The University of Chicago Press, Chicago, 2000.

[3] G. Hjorth and A. S. Kechris, Borel equivalence relations and classification of countable models, Annals of Pure and Applied Logic 82 (1996), 221–272.

[4] A. S. Kechris, Classical Descriptive Set Theory, Graduate Texts in Mathematics, Springer-Verlag, Berlin, 1995.

[5] A. S. Kechris and A. Louveau, The structure of hypersmooth Borel equivalence relations, J. Amer. Math. Soc. 10 (1997), 215–242.

[6] P. M. Neumann, On the structure of standard wreath products of groups, Math. Z. 84 (1964), 343–373.

[7] V. N. Obraztsov, On infinite complete groups, Comm. Algebra 22 (1994), 5875–5887.

[8] A. Yu. Ol’shanskii, Geometry of defining relations in groups, Mathematics and Its Applications (Soviet Series), vol. 70, Kluwer Academic Publishers, Dordrecht, 1991.

[9] S. Thomas and B. Velickovic, On the complexity of the isomorphism relation for finitely generated groups, J. Algebra 217 (1999), 352-373.

Mathematics Department, Rutgers University, 110 Frelinghuysen Road, Piscataway, New Jersey 08854-8019, USA

  E-mail address: sthomas@math.rutgers.edu