CAYLEY GRAPHS OF FINITELY GENERATED GROUPS

SIMON THOMAS

Abstract. There does not exist a Borel choice of generators for each finitely generated group which has the property that isomorphic groups are assigned isomorphic Cayley graphs.

1. Introduction

Let G be a finitely generated group and let S ⊆ G ∖ 1 be a finite generating set. Then the corresponding Cayley graph Cay(G, S) is the graph with vertex set G and edge set

E = {{x, y} | y = xs for some s ∈ S ∪ S^{−1}}.

Of course, if G is an arbitrary finitely generated group, then G does not have a “canonical” finite generating set S; and if S, S′ ⊆ G ∖ 1 are different finite generating sets, then the Cayley graphs Cay(G, S) and Cay(G, S′) are usually not isomorphic. In this paper, we shall prove that there does not exist an explicit choice of generators for each finitely generated group which has the property that isomorphic groups are assigned isomorphic Cayley graphs.

Before we can give an exact statement of our main result, we first need to recall how to represent the class of infinite finitely generated groups by the elements of a standard Borel space; i.e., a Polish space equipped with its associated σ-algebra of Borel subsets. Let G be the set of finitely generated groups G with underlying set ℕ; and let 2^{ℕ^{3}} be the Polish space of all 3-ary functions f : ℕ^{3} → {0, 1} with the natural product topology. Then, identifying each group G ∈ G with the graph of its multiplication operation m_{G} ∈ 2^{ℕ^{3}}, it is easily checked that G is a Borel subset of 2^{ℕ^{3}}. It follows that G is a standard Borel space. (For more details, see Hjorth-Kechris [4] or Thomas-Velickovic [8]. For later use, we note that a similar argument

1991 Mathematics Subject Classification. 03E15, 20F05.

Research partially supported by NSF Grants.

2 SIMON THOMAS

shows that the set of graphs C with vertex set ℕ also forms a standard Borel space.) Finally let [ℕ]^{<ω} be the set of finite subsets of ℕ, regarded as a discrete space.

Theorem 1.1. There does not exist a Borel function f : G → [ℕ]^{<ω} such that for all G, H ∈ G,

(a) f(G) generates G; and

(b) if G ≅ H, then Cay(G, f(G)) ≅ Cay(H, f(H)).

Here a function h : X → Y between standard Borel spaces X, Y is said to be Borel iff the graph of f is a Borel subset of X × Y. Equivalently, h : X → Y is a Borel function iff h^{−1}(B) is a Borel subset of X for every Borel subset B of Y. In fact, the proof of Theorem 1.1 establishes the slightly stronger result that there does not exist a measurable function f satisfying conditions 1.1(a) and 1.1(b). Hence, by Solovay’s Theorem [6], it is impossible to prove the existence of a function f satisfying conditions 1.1(a) and 1.1(b) without an essential appeal to the Axiom of Choice.

Acknowledgements. I would like to thank Ilya Kapovich, Alexander Kechris and Boban Velickovic for very helpful discussions concerning the material in this paper.

2. Cayley graphs and Quasi-isometries

In this section, we shall prove Theorem 1.1, modulo a technical lemma which will be proved in Section 3. Our proof is based upon the observation that the classification problem for finitely generated groups is much more difficult than that for Cayley graphs. In order to state this precisely, it is first necessary to recall the notions of a Borel homomorphism and a Borel reduction.

Suppose that E, F are equivalence relations on the standard Borel spaces X, Y respectively. Then φ : ⟨X, E⟩ → ⟨Y, F ⟩ is a Borel homomorphism iff φ : X → Y is a Borel function such that xEy implies φ(x)F φ(y) for all x, y ∈ X. If φ satisfies the stronger condition that xEy iff φ(x)F φ(y) for all x, y ∈ X, then φ is said to be a Borel reduction. The equivalence relation E on the standard Borel space X is said to be smooth iff there exists a Borel reduction φ : ⟨X, E⟩ → ⟨Y, =⟩ for some standard Borel space Y.

CAYLEY GRAPHS OF FINITELY GENERATED GROUPS 3

Let C be the standard Borel space of graphs with vertex set ℕ; and let C_{t} be the set of those graphs Γ ∈ C which satisfy the following conditions.

(i) Each vertex v ∈ Γ has finite degree.

(ii) The automorphism group Aut(Γ) acts transitively on the vertices of Γ. If G is a finitely generated group and S ⊆ G ∖ 1 is a finite generating set, then G acts as a transitive group of automorphisms of Cay(G, S) via left translations. Hence Cay(G, S) ∈ C_{t}. Lemma 2.1 (Folklore). (a) C_{t} is a standard Borel space.

(b) The isomorphism relation on C_{t} is smooth.

Proof. If Γ ∈ C, v ∈ Γ and n ≥ 1, then B_{Γ}(v, n) = {w ∈ Γ | d_{Γ}(v, w) ≤ n}, where d_{Γ} is the combinatorial distance function on the graph Γ.

(a) Suppose that Γ ∈ C and that each vertex v ∈ Γ has finite degree. By König’s Lemma, Aut(Γ) acts transitively on Γ iff for all v, w ∈ Γ and n ≥ 1, the finite induced subgraphs B_{Γ}(v, n) and B_{Γ}(w, n) are isomorphic. It follows that C_{t} is a Borel subset of C and hence C_{t} is a standard Borel space.

(b) Applying König’s Lemma once again, if Γ_{1}, Γ_{2} ∈ C_{t}, then Γ_{1} ≅ Γ_{2} iff B_{Γ_{1}}(0, n) ≅ B_{Γ_{2}}(0, n) for all n ≥ 1. (Recall that each Γ ∈ C has vertex set ℕ. In particular, 0 is a vertex of each graph Γ ∈ C_{t}.) In other words, if Γ ∈ C_{t}, then Γ is determined up to isomorphism by the sequence of finite graphs ⟨B_{Γ}(0, n) | n ≥ 1⟩. This easily implies that there exists a Borel reduction

φ : ⟨C_{t}, ≅⟩ → ⟨ℕ^{ℕ}, =⟩.

(Here ℕ^{ℕ} denotes the standard Borel space of infinite sequences of natural numbers.) □

Now suppose that f : G → [ℕ]^{<ω} is a Borel function satisfying conditions 1.1(a) and 1.1(b). Then f induces a Borel homomorphism

φ : ⟨G, ≅⟩ → ⟨C_{t}, ≅⟩

such that for all G ∈ G, there exists a finite generating set S ⊆ G ∖ 1 such that φ(G) ≅ Cay(G, S). It is well-known that the isomorphism relation on G is not smooth. (A detailed account of the Borel complexity of the isomorphism relation for finitely generated groups can be found in Thomas-Velickovic [8].) Hence the Borel

4 SIMON THOMAS

homomorphism φ is necessarily very far from being a Borel reduction. Of course, this is not yet a contradiction, since there exist nonisomorphic finitely generated groups G, H such that Cay(G, S) ≅ Cay(H, T) for suitably chosen finite generating sets S, T. However, recall that if G, H have isomorphic Cayley graphs with respect to suitably chosen finite generating sets, then G and H are quasi-isometric; i.e. if S, T are any finite generating sets for G, H respectively, then there exists a map π : G → H, together with constants λ ≥ 1 and C ≥ 0, such that the following conditions are satisfied.

• For all x, y ∈ G, \frac{1}{λ}d_{S}(x, y) − C ≤ d_{T} (π(x), π(y)) ≤ λd_{S}(x, y) + C.

• For all z ∈ H, d_{T} (z, π[G]) ≤ C.

Here d_{S}, d_{T} are the corresponding word metrics on G, H respectively. (A clear account of the basic properties of the quasi-isometry relation for finitely generated groups can be found in de la Harpe [3].)

Hence Theorem 1.1 is an immediate consequence of the following result. Lemma 2.2. Suppose that

φ : ⟨G, ≅⟩ → ⟨C_{t}, ≅⟩

is a Borel homomorphism. Then there exist groups G, H ∈ G such that (a) G and H are not quasi-isometric.

(b) φ(G) ≅ φ(H).

In order to see that Lemma 2.2 holds, consider the shift action of ℤ on 2^{ℤ} defined by

(z · h)(x) = h(x − z)

for each z, x ∈ ℤ and h ∈ 2^{ℤ}. Let E_{ℤ} be the orbit equivalence relation of ℤ on 2^{ℤ} and let μ be the usual product probability measure on 2^{ℤ}. Then μ is ℤ-invariant and ℤ acts ergodically on ⟨2^{ℤ}, μ⟩; i.e. if B ⊆ 2^{ℤ} is a ℤ-invariant Borel subset, then either μ(B) = 0 or μ(B) = 1. It follows that if Y is a standard Borel space and σ : 2^{ℤ} → Y is a ℤ-invariant Borel function, then there exists a ℤ-invariant Borel subset B ⊆ ℤ with μ(B) = 1 such that σ ↾ B is a constant function. In particular, since the isomorphism relation ≅ on C_{t} is smooth, this implies that if

ψ : ⟨2^{ℤ}, E_{ℤ}⟩ → ⟨C_{t}, ≅⟩

CAYLEY GRAPHS OF FINITELY GENERATED GROUPS 5

is any Borel homomorphism, then there exists a Borel subset B ⊆ 2^{ℤ} with μ(B) = 1 such that ψ maps B into a single ≅-class. Consequently, Lemma 2.2 follows by considering ψ = φ ∘ θ, where θ is the Borel homomorphism given by Lemma 2.3. Lemma 2.3. There exists a Borel homomorphism

θ : ⟨2^{ℤ}, E_{ℤ}⟩ → ⟨G, ≅⟩
s ↦ G_{s}

such that

{⟨s, t⟩ ∈ 2^{ℤ} × 2^{ℤ} | G_{s} and G_{t} are not quasi-isometric }

has μ × μ-measure 1.

We shall prove Lemma 2.3 in Section 3. This will then complete the proof of Theorem 1.1.

3. Champetier’s Construction

In this section, we shall use some ideas of Bowditch [1] and Champetier [2] to prove Lemma 2.3. Recall that the presentation

G = ⟨S | {r_{i} | i ∈ I}⟩

satisfies the C′(1/6) cancellation property if whenever u is a common initial subword of two distinct elements v_{1}, v_{2} of the set R_{I} of all cyclic conjugates of relators and their inverses, then 6|u| < min{|v_{1}|, |v_{2}|}. (Here |w| denotes the length of the word w as an element of the free group on S.) In this case, if w is a cyclically reduced word representing the identity in G and w is not equal to an element of R_{I}, then w is in the normal closure of the elements r_{i}, i ∈ I, such that |r_{i}| < |w|. (For example, see Theorem V.4.5 of Lyndon-Schupp [5].) As Bowditch [1] points out, this means that the “taut loops” in the Cayley graph Cay(G, S) correspond precisely to the elements of R_{I}; and we obtain the following quasi-isomometry invariant for groups satisfying the C′(1/6) cancellation property. Definition 3.1. The subsets H, H′ ⊆ ℕ^{+} are related, written H ≈ H′, iff there exists an integer k ≥ 1 such that the following conditions are satisfied.

(a) For every L ∈ H, there exists L′ ∈ H′ such that L/k ≤ L′ ≤ kL.

(b) For every L′ ∈ H′, there exists L ∈ H such that L′/k ≤ L ≤ kL′.

6 SIMON THOMAS

Theorem 3.2 (Bowditch [1]). Suppose that the presentations G = ⟨S | {r_{i} | i ∈ I}⟩ and H = ⟨T | {w_{j} | j ∈ J}⟩ both satisfy the C′(1/6) cancellation property. If G and H are quasi-isometric, then {|r_{i}| | i ∈ I} ≈ {|w_{j}| | j ∈ J}.

□

The following is a slight variant of Champetier’s construction in Section 4 [2]. Let F be the free group on {a, b} and let g ∈ Aut(F) be the automorphism defined by g(a) = ab and g(b) = ab^{2}. Let n ∈ ℕ^{+} and let

w = ab^{3}ab^{4} ⋯ ab^{n+2}.

Lemma 3.3. If n is sufficiently large, then the presentation

⟨a, b | g^{k}(w) = 1 for all k ∈ ℤ⟩

satisfies the C′(1/6) cancellation property.

Proof. It is easily checked that g^{−1}(a) = ab^{−1}a and g^{−1}(b) = a^{−1}b. Hence

g^{−1}(w) = b(a^{−1}b)b(a^{−1}b)^{2} ⋯ b(a^{−1}b)^{n}.

Thus, letting A = a^{−1}, we have that

g^{−1}(w) = b(Ab)b(Ab)^{2} ⋯ b(Ab)^{n}
g^{−1}(A) = AbA
g^{−1}(b) = Ab.

Clearly if k, ℓ ∈ ℤ, then there will not be significant cancellation between g^{k}(w) and (g^{ℓ}(w))^{−1}. Similarly, there will not be significant cancellation between g^{k}(w) and g^{ℓ}(w) if k ≥ 0 and ℓ < 0. Arguing as in Lemma 4.1 of Champetier [2], if n is sufficiently large, then the families of words {g^{k}(w) | k ≥ 0} and {g^{ℓ}(w) | ℓ < 0} both satisfy the C′(1/6) cancellation property. The result follows. □

Let θ : 2^{ℤ} → G be the Borel function defined by θ(s) = G_{s}, where G_{s} is the group with presentation

⟨a, b | g^{k}(w) = 1 iff s(k) = 1⟩.

CAYLEY GRAPHS OF FINITELY GENERATED GROUPS 7

Clearly if s, t ∈ 2^{ℤ} lie in the same ℤ-orbit, then G_{s} ≅ G_{t} and so θ is a Borel homomorphism from ⟨2^{ℤ}, E_{ℤ}⟩ to ⟨G, ≅⟩. Hence the following result completes the proof of Lemma 2.3. Lemma 3.4. The set

{⟨s, t⟩ ∈ 2^{ℤ} × 2^{ℤ} | G_{s} and G_{t} are not quasi-isometric }

has μ × μ-measure 1.

Proof. In the following proof, if b < c are integers, then [b, c] denotes the set {z ∈ ℤ | b ≤ z ≤ c}. We write c ≫ b when we wish to indicate that c is “much larger” than b.

Suppose that k, ℓ ≥ 1. Since g(a) = ab and g(b) = ab^{2}, we have that

3.4(a)  |g^{k+ℓ}(w)| > 2^{k}|g^{ℓ}(w)|

Similarly, we have that

3.4(b)  |g^{−k−ℓ}(w)| > 2^{k}|g^{−ℓ}(w)|

For each n ≥ 1 and r ≫ n, let

D_{n}(r) = {r^{∗} | |g^{r}(w)|/2^{n} ≤ |g^{ℓ}(w)| ≤ 2^{n}|g^{r}(w)|}.

Then the following claim is an easy consequence of 3.4(a) and 3.4(b).

Claim 3.5. Suppose that r^{∗}, s^{∗} ∈ D_{n}(r).

(a) If r^{∗} ≥ 0, then |r^{∗} − r| ≤ n.

(b) If r^{∗}, s^{∗} < 0, then |r^{∗} − s^{∗}| ≤ 2n.

□

Thus there exists r^{∗} ≪ −2n such that

D_{n}(r) = [r − n, r + n] ∪ [r^{∗} − 2n, r^{∗} + 2n].

Hence, with μ-probability 1, if s ∈ 2^{ℤ}, then for each n ≥ 1, there exist infinitely many pairwise disjoint sets of the form D_{n}(r) such that s ↾ D_{n}(r) ≡ 0. Fix some such s ∈ 2^{ℤ}. With μ-probability 1, if t ∈ 2^{ℤ}, then for each n ≥ 1, there exist infinitely many pairwise disjoint sets of the form D_{n}(r) such that s ↾ D_{n}(r) ≡ 0 and t(r) = 1. Applying Theorem 3.2, we see that G_{s} and G_{t} are not quasi-isometric for such s, t ∈ 2^{ℤ}. The result follows. □

In [1], Bowditch proved that there are 2^{ω} finitely generated groups up to quasiisometry. Applying Lemma 2.3, we obtain the following slightly stronger result. Theorem 3.6. The quasi-isometry relation on the space G of finitely generated groups is not smooth.

□

In [7], it was shown 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. Here two finitely generated groups G_{1}, G_{2} are said to be virtually isomorphic or commensurable up to finite kernels 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}.

Thus G_{1}, G_{2} are virtually isomorphic iff they are “obviously quasi-isometric”. It is natural to conjecture that the problem of classifying finitely generated groups up to quasi-isometry is also strictly harder than that of classifying them up to isomorphism.

References

[1] B. H. Bowditch, Continuously many quasiisometry classes of 2-generator groups, Comment. Math. Helv. 73 (1998), 232–236.

[2] C. Champetier, L’espace des groupes de type fini, Topology 39 (2000), 657–680.

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

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

[5] R. C. Lyndon and P. E. Schupp, Combinatorial Group Theory, Springer-Verlag, 1977.

[6] R. M. Solovay, A model of set theory in which every set of reals is Lebesgue measurable, Ann. Math. 92 (1970), 1–56.

[7] S. Thomas, The virtual isomorphism problem for finitely generated groups, Bull. Lond. Math. Soc. 35 (2003), 777–784.

[8] 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