Sofic groups: graph products and graphs of groups

Laura Ciobanu, Derek F. Holt and Sarah Rees

Warwick, 21st June 2013

Abstract

We prove that graph products of sofic groups are sofic, as are graphs of groups for which vertex groups are sofic and edge groups are amenable.

2010 Mathematics Subject Classification: 20F65, 37B05.

Key words: sofic, graph products, free and direct products, groups of graphs.

1 Introduction

We prove the following results.

Theorem 1.1. A graph product of sofic groups is sofic.

Theorem 1.2. The fundamental group of a graph of groups is sofic if each vertex group is sofic and each edge group is amenable.

Theorem 1.1 generalises Theorem 1 of [3], and our proof is based on ideas used in the proof of that theorem. Theorem 1.2 is an extension of the result that free products of sofic groups amalgamated over amenable subgroups are sofic, proved independently in [4, Theorem 1] and [7, Corollary 2.3]; most of the argument needed to extend the result is already found in [1, Corollary 3.6].

The term sofic groups is attributed to Weiss [12], and applied to a definition due to Gromov [6]; this is a class of groups which, together with the related class of hyperlinear groups, has inspired much recent study, through its connections to a variety of different mathematical areas. A very useful introduction to sofic groups is provided by [8]. There are many open questions, including the question of whether all groups are sofic.

A number of quite distinct, but equivalent, definitions exist for sofic groups, and are proved equivalent in [8]. The definition in [12] for finitely generated groups involves finite subsets of the Cayley graph of the group, and is essentially the same as the definition in [6] of the Cayley graph being initially subamenable. An alternative and equivalent definition of [8] defines a group to be sofic if it embeds as a subgroup in an ultraproduct of symmetric groups. Another (equivalent) definition, found in [3], is phrased in terms of quasi-actions. We shall work with a variation of that definition, given below as Definition 1.4; we phrase it in terms of (what we call) special quasi-actions. That this is equivalent to the definition of [3] (and hence to the others) follows from [3, Lemma 2.1].

For a finite set A, let S(A) be the group of all permutations of A. For ϵ > 0, we say that two elements f_{1}, f_{2} of S(A) are ϵ-similar if the number of elements a ∈ A for which f_{1}(a) ≠ f_{2}(a) is at most ϵ|A|. Note that for ϵ ≥ 1 this condition is always satisfied.

Definition 1.3. Suppose that G is a group, ϵ > 0 a real number and F ⊆ G a finite subset of G. A special (F, ϵ)-quasi-action of G on a finite set A is a function ϕ : G → S(A) with the following properties:

(a) ϕ(1) = 1;

(b) ∀g ∈ G, ϕ(g)^{−1} = ϕ(g^{−1});

(c) for g ∈ F \ {1}, ϕ(g) has no fixed points;

(d) for g_{1}, g_{2} ∈ F the map ϕ(g_{1}g_{2}) is ϵ-similar to ϕ(g_{1})ϕ(g_{2}).

For a ∈ A, g ∈ G, we write a^{ϕ(g)} for the image of a under ϕ(g).

Definition 1.4. A group G is sofic if, for each number ϵ ∈ (0, 1) and any finite subset F ⊆ G, G admits a special (F, ϵ)-quasi-action.

It is immediate from the definition that a group is sofic precisely if every one of its finitely generated subgroups is sofic. We note at this stage also the following elementary result, which will be useful to us later.

Lemma 1.5. Let ϕ_{i} be special (F, ϵ)-quasi-actions of G on A_{i} for 1 ≤ i ≤ n, let A = A_{1} × ⋯ × A_{n}, and define ϕ : G → S(A) by (a_{1}, …, a_{n})^{ϕ(g)} = (a_{1}^{ϕ_{1}(g)}, …, a_{n}^{ϕ_{n}(g)}). Then ϕ is a special (F, nϵ)-quasi-action.

Proof. The conditions (a), (b) and (c) of the definition are straightforward to check for ϕ. The equality (a_{1}, …, a_{n})^{ϕ(g_{1})ϕ(g_{2})} = (a_{1}, …, a_{n})^{ϕ(g_{1}g_{2})} holds whenever a_{i}^{ϕ_{i}(g_{1})ϕ_{i}(g_{2})} = a_{i}^{ϕ_{i}(g_{1}g_{2})} for each a_{i}, which is the case for at least (1 − ϵ)^{n}|A| elements (a_{1}, …, a_{n}) ∈ A. The result now follows, since (1 − ϵ)^{n} ≥ 1 − nϵ for all n ≥ 1.

This article contains two further sections; Section 2 contains the proof of Theorem 1.1 and Section 3 the proof of Theorem 1.2.

2 Proof of the graph product theorem

Let Γ be a simple graph and, for each vertex v of Γ, let G_{v} be a group. The graph product of the groups G_{v} with respect to Γ is defined to be the quotient of their free product by the normal closure of the relators [g_{v}, g_{w}] for all g_{v} ∈ G_{v}, g_{w} ∈ G_{w} for which {v, w} is an edge of Γ.

Graph products were introduced by Green in her PhD thesis [5], and their basic properties are established there. For a graph product of vertex groups G_{1}, …, G_{n} with respect to a finite graph Γ with vertices 1, …, n, and for J ⊆ {1, …, n}, we define G_{J} := ⟨G_{j} | j ∈ J⟩. By [5, Proposition 3.31], G_{J} is isomorphic to the graph product of G_{j} (j ∈ J) on the full subgraph of Γ with vertex set J. Note that G_{∅} is the trivial group.

Green only considered graph products of finitely many vertex groups, but the definition applies equally well to graphs with infinite vertex sets I. Since any relation in a group is a consequence of finitely many defining relations, the property that, for any J ⊆ I, G_{J} is isomorphic to the graph product of G_{j} (j ∈ J) on the full subgraph of Γ with vertex set J, extends to graph products with infinitely many vertex groups. Hence, since a group is sofic if and only if all of its finitely generated subgroups are sofic, it suffices to prove Theorem 1.1 for graph products of finitely many groups, so we shall assume from now on that the graph Γ is finite.

Any non-identity element in a graph product can be written as a product g_{1} ⋯ g_{l} for some l > 1, where each g_{i} is a non-trivial element of a vertex group G_{j_{i}}. By [5, Theorem 3.9], we can get from any such expression of minimal length to any other by swapping the order in the expression of elements g_{i}, g_{i+1} from commuting vertex groups. Hence every minimal length expression for an element g has the same length l, which we call the syllable length of g, and involves the same set {g_{1}, g_{2}, … g_{l}} of vertex group elements, with the same multiplicities, the syllables of g. Whenever g_{1} ⋯ g_{l} is a minimal length expression for g, we call each product g_{1} ⋯ g_{i} a left divisor of g, and each product g_{i+1} ⋯ g_{n} a right divisor of g, for 0 ≤ i ≤ n.

We also note that, for any finite subset of a graph product of groups G_{i}, there is a bound N on the syllable lengths of its elements, and there are finite subsets F_{i} of the vertex groups G_{i} that contain all the syllables of those elements. Hence Theorem 1.1 follows from the following proposition.

Proposition 2.1. There is a function f : ℕ → ℕ with the following property. Let G_{1}, …, G_{n} be sofic groups, and G their graph product with respect to a finite graph Γ. Let ϵ > 0 be given, and for each i = 1, … n, let F_{i} be a finite subset of G_{i}, A_{i} a finite set, and suppose that ψ_{i} : G_{i} → S(A_{i}) is a special (F_{i}, ϵ)-quasi-action of G_{i} on A_{i}.

Then, for any N ∈ ℕ, G has a special (F, f(n)ϵ)-quasi-action ϕ on a finite set C, where F is the set of elements of G of syllable length at most N for which each syllable is in some F_{i}, such that the following additional properties hold:

(1) whenever x, y are in distinct vertex groups, ϕ(xy) = ϕ(x)ϕ(y);

(2) C admits equivalence relations ∼_{1}, …, ∼_{n} such that, for each c ∈ C, g ∈ F and J ⊆ {1, …, n},

c^{ϕ(g)} ∼_{J} c ⟺ g ∈ G_{J}

(where ∼_{J} is the join of those equivalence relations ∼_{j} for which j ∈ J).

Note that, by definition, a ∼_{J} b if and only if there is a sequence a = c_{1}, …, c_{m} = b of elements with c_{i} ∼_{j_{i}} c_{i+1} for some j_{i} ∈ J. In particular, x ∼_{∅} y ⟺ x = y.

Note that the conditions (1) and (2) imposed on the special quasi-action ϕ are necessary for the inductive proof of the proposition, rather than to deduce the theorem. Condition (1) ensures in particular that ϕ(x)ϕ(y) = ϕ(y)ϕ(x) whenever x, y are from commuting vertex groups.

Proof. The proof is by induction on n. Suppose first that n = 1. Then G = G_{1} and F = F_{1} (for any value of N ∈ ℕ). We put F := F_{1} and C := A_{1}, and define the equivalence relation ∼_{1} by c ∼_{1} d for all c, d ∈ C. Then ϕ is a special (F, ϵ)-quasi-action on C, and the additional property (1) holds vacuously. To see that the additional property (2) also holds, note that there are only two possibilities for J: J = {1} and J = ∅. If J = {1} then G = G_{J}, so the left and right hand sides of the equivalence in (2) are true for all g ∈ G. If J = ∅ then, by the definition of a special (F, ϵ)-quasi-action, both the left and right hand sides of the equivalence are true if and only if g = 1. So the property (2) holds, and the statement of the proposition is true with f(n) = 1.

So now we proceed to prove the inductive step. We shall prove that the result holds with f(n) = n(nf(n − 1) + 1).

Write I = {1, 2, …, n}, and for each k ∈ I, I_{k} = I \ {k}. For each k ∈ I, let H_{k} := G_{I_{k}} be the subgroup of G that is the graph product of the groups G_{i} for i ≠ k with respect to the appropriate subgraph of Γ. By the induction hypothesis, we may assume that, for ϵ′ := f(n−1)ϵ, and F_{H_{k}} := F ∩H_{k}, H_{k} has a special (F_{H_{k}}, ϵ′)-quasi-action θ_{k} on a set D_{k} admitting equivalence relations ≃_{i}^{k}, for each i ≠ k, such that

(1) θ_{k}(xy) = θ_{k}(x)θ_{k}(y) for x, y in distinct vertex groups of H_{k}; and

(2) for d ∈ D_{k}, h ∈ F_{H_{k}}, and J ⊆ I_{k}, d^{θ_{k}(h)} ≃_{J} d ⟺ h ∈ G_{J}.

For each k ∈ I, we shall build a set C_{k} related to D_{k}, admitting equivalence relations ∼_{i}^{k} for each i ∈ I, and then construct a special quasi-action ϕ_{k} of G on C_{k} that satisfies Condition (1) and more. We shall then construct ϕ and the equivalence relations ∼_{1}, …, ∼_{n} on the set C := C_{1} × C_{2} × ⋯ × C_{n} in terms of the special quasi-actions ϕ_{k} and the equivalence relations ∼_{i}^{k}, using Lemma 1.5.

For k ∈ I, let L_{k} ⊆ I_{k} be the set of vertices joined in Γ to k. Let ≃_{L_{k}} be the join of the equivalence relations ≃_{i}^{k} for i ∈ L_{k}, and let π_{k} be the projection from D_{k} to its set of equivalence classes under ≃_{L_{k}} (for which the image of d ∈ D_{k} is its equivalence class).

Now, using ideas from [3, Theorem 1] we choose a finite group V_{k}, with generating set π_{k}(D_{k}) × A_{k}, for which all relators among the generators have length greater than N, and we let C_{k} := D_{k} × A_{k} × V_{k}.

We define equivalence relations ∼_{i}^{k} on C_{k}, for i ≠ k, by the rules

(d, a, v) ∼_{i}^{k} (d′, a′, v′) ⟺ d ≃_{i}^{k} d′, a = a′, v = v′.

Then we define ∼_{k}^{k} on C_{k} by specifying its equivalence classes; for d ∈ D_{k}, v ∈ V_{k}; the class α_{k}(d, v) is the subset {(d, a, v ∘ (π_{k}(d), a)) : a ∈ A_{k}} of C_{k}. Multiplication ∘ within the third component is the group multiplication of V_{k}.

We define a special quasi-action ϕ_{k} of G on C_{k} as a composite of natural extensions to C_{k} of the special quasi-actions θ_{k}, ψ_{k} of H_{k} and G_{k} on D_{k}, A_{k}.

For h ∈ H_{k}, we define

(d, a, v)^{ϕ_{k}(h)} = (d^{θ_{k}(h)}, a, v).

Then, for g ∈ G_{k}, we define

(d, a, v)^{ϕ_{k}(g)} = (d, a^{ψ_{k}(g)}, v ∘ (π_{k}(d), a)^{−1} ∘ (π_{k}(d), a^{ψ_{k}(g)})).

Now it follows, essentially from [5, lemma 3.20], that each element g ∈ G has a unique expression as a product g = x_{1}y_{1} ⋯ x_{m}y_{m}, with each x_{i} ∈ H_{k}, each y_{i} ∈ G_{k}, x_{i} nontrivial for i > 1, y_{i} nontrivial for i < m, and such that, for i > 1, x_{i} has no non-trivial left divisor in the subgroup G_{L_{k}}; we call this expression the normal form for g. We note that the y_{i}’s are syllables, the x_{i}’s products of syllables and the number of terms at most the syllable length of g. We use that expression for g to extend to G the definitions of ϕ_{k} on H_{k} and G_{k}, that is, for g ∈ G, ϕ_{k}(g) := ϕ_{k}(x_{1})ϕ_{k}(y_{1}) ⋯ ϕ_{k}(x_{m})ϕ_{k}(y_{m}).

We need now the following lemma, whose proof we defer.

Lemma 2.2. Let ϵ′′ := (nf(n − 1) + 1)ϵ. Then, for each k, ϕ_{k} is a special (F, ϵ′′)-quasi-action of G on C_{k}, such that

(1) whenever x, y are in distinct vertex groups, ϕ_{k}(xy) = ϕ_{k}(x)ϕ_{k}(y), (2′) for each c ∈ C_{k}, g ∈ F, we have g ∈ G_{J} ⇒ c^{ϕ_{k}(g)} ∼_{J}^{k} c for all J ⊆ I,

and c^{ϕ_{k}(g)} ∼_{J}^{k} c ⇒ g ∈ G_{J} for all J ⊆ I_{k}.

Now we define a map ϕ : G → S(C), where C := C_{1}×⋯×C_{n}, by (c_{1}, …, c_{n})^{ϕ(g)} = (c_{1}^{ϕ_{1}(g)}, …, c_{n}^{ϕ_{n}(g)}). It follows from Lemma 1.5 that this is a (F, f(n)ϵ)-quasi-action with f(n) = n(nf(n−1)+1). Condition (1) of the proposition is inherited from the maps ϕ_{k}.

We define equivalence relations ∼_{1}, ∼_{2}, …, ∼_{n} on C by (c_{1}, …, c_{n}) ∼_{j} (c′_{1}, …, c′_{n}) if and only if c_{k} ∼_{j}^{k} c′_{k} for 1 ≤ k ≤ n. We need now to verify Condition (2).

Let J ⊆ I. The fact that g ∈ G_{J} implies that c^{ϕ(g)} ∼_{J} c for all c ∈ C is inherited from the maps ϕ_{k}. If J = I, then G = G_{J} and the converse statement is immediate. Otherwise we have J ⊆ I_{k} for some k with 1 ≤ k ≤ n. If g ∉ G_{J}, and c = (c_{1}, …, c_{n}) ∈ C, then c_{k}^{ϕ_{k}(g)} ≁_{J}^{k} c_{k} and hence c^{ϕ(g)} ≁_{J} c.

So the proof of the proposition will be complete once the proof of Lemma 2.2 has been provided.

Proof of Lemma 2.2: Note that it is clear that the restriction of ϕ_{k} to H_{k} is a special (F_{H_{k}}, ϵ′)-quasi-action for H_{k}, since θ_{k} is. And certainly that quasi-action preserves each of the ∼_{i}^{k} equivalence classes with i ≠ k. And it is clear that the restriction of ϕ_{k} to G_{k} is a special (F ∩ G_{k}, ϵ)-quasi-action for G_{k}, since ψ_{k} is. That quasi-action preserves the ∼_{k}^{k} equivalence classes, since both (d, a, v) and (d, a, v)^{ϕ_{k}(g)} are in α_{k}(d, v ∘ (π_{k}(d), a)^{−1}).

The equation (d, a, v)^{ϕ_{k}(1_{G})} = (d, a, v) follows immediately from (d, a, v)^{ϕ_{k}(h)} = (d^{θ_{k}(h)}, a, v), for h ∈ H_{k}, and hence Condition (a) of Definition 1.3 is verified for ϕ_{k}.

We shall verify the remaining conditions in the order (c), (1), (b), (d), (2′).

First we introduce some notation. We need to consider ϕ_{k}(g) for a general element g in the graph product, written in normal form as x_{1}y_{1} ⋯ x_{m}y_{m}. We write x for the group product x_{1} ⋯ x_{m}, then y for the group product y_{1} ⋯ y_{m}, and x[i], y[i] for the products x_{1} ⋯ x_{i}, y_{1}, ⋯ y_{i}, where x[0] = y[0] = 1.

We see then that

(d, a, v)^{ϕ_{k}(g)} = (d, a, v)^{ϕ_{k}(x_{1}y_{1}···x_{m}y_{m})} = (d^{θ_{k}(x[m])}, a^{ψ_{k}(y[m])}, v ∘ u),
where u = ∏_{i=1}^{m}(π_{k}(d^{θ_{k}(x[i])}), a^{ψ_{k}(y[i−1])})^{−1} ∘ (π_{k}(d^{θ_{k}(x[i])}), a^{ψ_{k}(y[i])}).

unless y_{m} is the identity, in which case the product for u is from i = 1 to m − 1.

Our next step is to establish Condition (c) of Definition 1.3 for ϕ_{k}. Let g be a non-trivial element of F, with normal form x_{1}y_{1} ⋯ x_{m}y_{m}. So 2m ≤ N and, for each i, x_{i} ∈ F_{H_{k}} and y_{i} ∈ F_{k}. Suppose first that u, in the above expression, is not the empty word. Since ψ_{k} is a special quasi-action, Condition (c) for ψ_{k} implies that a^{ψ_{k}(y[i−1])} ≠ a^{ψ_{k}(y[i])} for each i. Since x_{i+1} ∉ G_{L_{k}}, it follows from the induction hypothesis that θ_{k}(x_{i+1}) cannot map any element of D_{k} to an element in the same ≃_{L_{k}} equivalence class, that is, π_{k}(d^{θ_{k}(x[i])}) ≠ π_{k}(d^{θ_{k}(x[i+1])}). So no generator in the word of length 2m representing u can freely cancel with the generator either before it or after it. The fact that V admits no short relators now ensures that u is nontrivial. In that case certainly (d, a, v)^{ϕ_{k}(g)} ≠ (d, a, v).

So now suppose that u is empty. Then m = 1, y_{1} is trivial, and g = x_{1}. So x = x_{1} is a non-identity element of F_{H_{k}}, and hence d^{θ_{k}(x)} ≠ d. So again (d, a, v)^{ϕ_{k}(g)} ≠ (d, a, v). Hence we have shown that the map ϕ_{k} from G to S(C_{k}) allows no non-identity element of length less than N in F to fix any element of C_{k}, and so Condition (c) of Definition 1.3 is verified for ϕ_{k}.

In order to establish Condition (1) of the Lemma for ϕ_{k}, we suppose first that x ∈ G_{L_{k}}, and y ∈ G_{k}. By definition ϕ_{k}(xy) = ϕ_{k}(x)ϕ_{k}(y), and

(d, a, v)^{ϕ_{k}(x)ϕ_{k}(y)} = (d^{θ_{k}(x)}, a^{ψ_{k}(y)}, v ∘ (π_{k}(d^{θ_{k}(x)}), a)^{−1} ∘ (π_{k}(d^{θ_{k}(x)}), a^{ψ_{k}(y)}))

while

(d, a, v)^{ϕ_{k}(y)ϕ_{k}(x)} = (d, a^{ψ_{k}(y)}, v ∘ (π_{k}(d), a)^{−1}) ∘ (π_{k}(d), a^{ψ_{k}(y)}))^{ϕ_{k}(x)}
= (d^{θ_{k}(x)}, a^{ψ_{k}(y)}, v ∘ (π_{k}(d), a)^{−1} ∘ (π_{k}(d), a^{ψ_{k}(y)})).

Then since d ≃_{L_{k}} d^{θ_{k}(x)}, we have π_{k}(d) = π_{k}(d^{θ_{k}(x)}), and so

(d, a, v)^{ϕ_{k}(x)ϕ_{k}(y)} = (d, a, v)^{ϕ_{k}(y)ϕ_{k}(x)},

that is, for x ∈ G_{L_{k}}, y ∈ H_{k}, ϕ_{k}(xy) = ϕ_{k}(x)ϕ_{k}(y) = ϕ_{k}(y)ϕ_{k}(x).

Now suppose that x, y are in distinct vertex groups, G_{i}, G_{j}. If i, j ≠ k then Condition (1) follows immediately by induction applied to H_{k}. If j = k, or if i = k and G_{i}, G_{j} do not commute, then xy is in normal form, and Condition (1) follows from the definition of ϕ_{k}. Finally if i = k and G_{i}, G_{j} commute, then x ∈ G_{L_{k}}, y ∈ H_{k}, and we can deduce Condition (1) for ϕ_{k} from the result above.

Next suppose that g = x_{1}y_{1} ⋯ x_{m}y_{m} ∈ G. We compare ϕ_{k}(g)^{−1} and ϕ_{k}(g^{−1}). We have g^{−1} = y_{m}^{−1}x_{m}^{−1} ⋯ y_{1}^{−1}x_{1}^{−1}. The expression for g^{−1} is not necessarily in normal form, because some of the x_{i}^{−1} could have left divisors in G_{L_{k}}, but we can transform it into normal form by splitting any such x_{i}^{−1} into syllables and then applying commuting relations to move left divisors of x_{i}^{−1} in G_{L_{k}} past y_{i}^{−1}. By the results of the preceding two paragraphs, if we apply the corresponding transformations to ϕ_{k}(y_{m}^{−1})ϕ_{k}(x_{m}^{−1}) ⋯ ϕ_{k}(y_{1}^{−1})ϕ_{k}(x_{1}^{−1}), then we do not change the resulting permutation. Hence we have ϕ_{k}(g^{−1}) = ϕ_{k}(y_{m}^{−1})ϕ_{k}(x_{m}^{−1}) ⋯ ϕ_{k}(y_{1}^{−1})ϕ_{k}(x_{1})^{−1}. It follows from Condition (b) of Definition 1.3 that ϕ_{k}(y_{i}^{−1}) is inverse to ϕ_{k}(y_{i}) and from the induction hypothesis on H_{k} that ϕ_{k}(x_{i}^{−1}) is inverse to ϕ_{k}(x_{i}). Hence ϕ_{k}(g^{−1}) = ϕ_{k}(g)^{−1}, which verifies Condition (b) of Definition 1.3 for ϕ_{k}.

We proceed now to verify Condition (d) of Definition 1.3 for ϕ_{k}; that is, to show that for all g_{1}, g_{2} ∈ F, ϕ_{k}(g_{1}g_{2}) is ϵ′′-similar to ϕ_{k}(g_{1})ϕ_{k}(g_{2}). Let g_{1} = x_{1}y_{1} ⋯ x_{m}y_{m}, g_{2} = x′_{1}y′_{1} ⋯ x′_{p}y′_{p} be the normal forms of g_{1}, g_{2} ∈ F. In the following discussion, we refer to an element of H_{k} or of G_{k} as a block, and to a product of blocks as an expression. The normal form for g_{1}g_{2} is derived from the concatenation x_{1}y_{1} ⋯ x_{m}y_{m}x′_{1}y′_{1} ⋯ x′_{p}y′_{p} by a sequence of moves, each of which is one of four types:

(a) deletion of a block that is equal to the identity;

(b) cancellation (that is, merger of two adjacent mutually inverse blocks that are either both in H_{k} or both in G_{k});

(c) expression of a block in H as a product of a left divisor in G_{L_{k}} and a right divisor, and moving the left divisor to the left, past a block in G_{k};

(d) merger of two adjacent blocks that are either both in H_{k} or both in G_{k}, and whose product is not the identity, to give a new block from that same subgroup.

Note that in (c) the left and right divisors of a block in H_{k} are simply subblocks, whose concatenation is a permutation of the original block; that is, the (multi)set of syllables of the block in H_{k} is the union of the (multi)sets of syllables of those left and right divisors. By contrast, a move of type (d) will normally change the (multi)set of syllables in an expression. Starting with the permutation

ϕ(x_{1})ϕ(y_{1}) ⋯ ϕ(x_{m})ϕ(y_{m})ϕ(x′_{1})ϕ(y′_{1}) ⋯ ϕ(x′_{p})ϕ(y′_{p}),

we study the sequence of composites of permutations of C_{k} defined by the various expressions that arise when we apply the corresponding operations to this expression of images during this rewrite process, and keep track of the proportion of elements of C_{k} on which they differ. We note that, as a consequence of what we have proved so far, two expressions that differ only on moves of types (a), (b) and (c) correspond to composites of permutations that have the same effect on all points of C. Hence we only need to concern ourselves with moves of type (d).

Suppose that a move converts an expression w to an expression w′. Let σ, σ′ be the permutations corresponding to the two expressions. If the move merges two blocks from G_{k}, then the permutations σ and σ′ differ on the same proportion of elements of C_{k} as do permutations for the quasi-action of G_{k} on the set A_{k}, that is, on at most ϵ|C_{k}| of the elements, by the hypothesis.

If the move merges two blocks from H_{k}, then the permutations σ and σ′ differ on the same proportion of elements of C_{k} as do permutations for the quasi-action of H_{k} on the set D_{k}, that is, on at most f(n − 1)ϵ|C_{k}| of the elements, by the induction hypothesis. Notice however that if the two blocks z_{1}, z_{2} being merged are left and right divisors of z_{1}z_{2} (or, equivalently, if the syllable length of z_{1}z_{2} is the sum of the syllable lengths of z_{1} and z_{2}), then our induction hypothesis on H ensures that ϕ_{k}(z_{1}z_{2}) = ϕ_{k}(z_{1})ϕ_{k}(z_{2}). We shall call such mergers nonreducing, and other mergers, for which this equality is not guaranteed to hold, reducing.

Condition (d) can now be now established by application of the following lemma.

Lemma 2.3. During the rewrite process, we perform at most n reducing mergers of blocks of H_{k} and at most one reducing merger of blocks of G_{k}.

Proof. We may assume that m, p > 0 (since otherwise one of g_{1}, g_{2} is the identity) and split the proof into three cases (1) 1 ≠ y_{m} and x′_{1} ∉ G_{L_{k}}; (2) y_{m} = 1; and (3) 1 ≠ y_{m} and x_{1} ∈ G_{L_{k}}.

We deal with Case 1 first, proving by induction on m that in this case the product can be rewritten using at most |L_{k}| mergers, all of which are within H_{k}. Using that result we then deal with the remaining two cases together, also using induction on m.

Case 1. 1 ≠ y_{m} and x′_{1} ∉ G_{L_{k}}.

Let x′_{1} = z_{1}z_{2}, where z_{1} is the longest left divisor of x′_{1} in G_{L_{k}}. Suppose that z_{1} ∈ G_{L′} for some L′ ⊆ L_{k}. We prove by induction on m that this product can be rewritten using at most |L′| (≤ |L_{k}|) H_{k}-mergers and no G_{k}-mergers.

If m = 1 then there can be at most one H_{k}-merger x_{1}x′_{1}, so the result is clear. So suppose that m > 1; then y_{m−1} ≠ 1, and x_{m} is nontrivial with no left divisor in G_{L}. If z_{1} commutes with x_{m}, then the claim follows by induction applied to the product (x_{1}y_{1} ⋯ x_{m−1}y_{m−1})(z_{1}x_{m}y_{m}z_{2}y′_{1} ⋯ x′_{p}y′_{p}). Otherwise, we can write z_{1} = z_{11}z_{12}, where z_{11} (which may be trivial) is the longest left divisor of z_{1} that commutes with x_{m}. So z_{11} ∈ G_{L′′} with |L′′| < |L′|. We can then perform the rewriting by performing an H_{k}-merger x_{m}z_{12} (if necessary) and, by induction, at most |L′′| further H_{k}-mergers resulting from moving z_{11} further to the left. This completes the proof of the claim, and of the lemma in Case 1.

So now we may assume that m, p > 0, and that we are in Case 2 or 3.

Case 2. y_{m} = 1.

If m = 1, then there is at most one H_{k}-merger x_{1}x′_{1}, and so the result holds. So suppose that m > 1 and hence that y_{m−1} ≠ 1, and x_{m} is nontrivial with no left divisor in G_{L_{k}}.

If x_{m}x′_{1} ∉ G_{L_{k}}, then we perform an H_{k}-merger (if necessary) on x_{m}x′_{1}, and now observe that the product (x_{1}y_{1} ⋯ x_{m−1}y_{m−1})(x_{m}x′_{1}y′_{1} ⋯ x′_{p}y′_{p}) satisfies the conditions of Case 1, and so can be rewritten using at most |L_{k}| further H_{k}- mergers and no G_{k}-mergers. So in this case too, the lemma is proved.

If x_{m}x′_{1} ∈ G_{L_{k}} then, since x_{m} has no left divisor in G_{L_{k}}, the product x_{m}x′_{1} can be evaluated by writing x_{m} and x′_{1} as products of syllables and then performing commuting and cancellation moves only so we can rewrite x_{m}x′_{1} as z ∈ G_{L_{k}} without performing any mergers, to arrive at the product

(x_{1}y_{1} ⋯ x_{m−1}y_{m−1})(zy′_{1} ⋯ x′_{p}y′_{p}),

which satisfies the conditions of Case 3 for m − 1. The lemma now follows by induction applied to that product.

Case 3. 1 ≠ y_{m} and x′_{1} ∈ G_{L_{k}}.

If y_{m}y′_{1} ≠ 1, then we perform the G_{k}-merger y_{m}y′_{1}, and the H_{k}-merger x_{m}x′_{1} (which cannot be in G_{L_{k}}, since x_{m} ∉ G_{L_{k}}, x′_{1} ∈ G_{L_{k}}). Then we can apply the result of Case 1 to the product (x_{1}y_{1} ⋯ x_{m−1}y_{m−1})(x_{m}x′_{1}y_{m}y′_{1} ⋯ x′_{p}y′_{p}), and the proof is complete.

If y_{m}y′_{1} = 1 then the result is clear if p = 1 and otherwise, since x′_{2} has no left divisor in G_{L}, the merger x′_{1}x′_{2} is non-reducing, so the result follows by applying Case 2 to the product (x_{1}y_{1} ⋯ x_{m−1}y_{m−1}x_{m})(x′_{1}x′_{2}y′_{2} ⋯ x′_{p}y′_{p}).

This completes the proof of Condition (d), and hence we see that ϕ_{k} is a special (F, ϵ′′)-quasi-action, with ϵ′′ = (nf(n − 1) + 1)ϵ.

It remains to verify Condition (2′). We have shown already that, for each i ∈ I, the action of ϕ_{k}(G_{i}) on C preserves each of the ∼_{i}^{k}-equivalence classes, from which it follows immediately that g ∈ G_{J} with J ⊆ I implies c^{ϕ_{k}(g)} ∼_{J}^{k} c.

Now suppose that J ⊆ I_{k}, c = (d, a, v) ∈ C_{k}, g ∈ F, and that c^{ϕ_{k}(g)} ∼_{J}^{k} c. Since k ∉ J, it is immediate from the definition of ∼_{j}^{k} for j ∈ J that

(d, a, v) ∼_{J}^{k} (d′, a′, v′) ⟺ d ≃_{J} d′, a = a′, v = v′.

So now, arguing as in our earlier proof of Condition (c) of Definition 1.3 for ϕ_{k} that, for 1 ≠ g ∈ F, (d^{θ_{k}(g)}, a, v) ≠ (d, a, v) we find that, for g ∈ F, (d^{θ_{k}(g)}, a, v) ∼_{J} (d, a, v) if and only if g ∈ H_{k} and d^{θ_{k}(g)} ≃_{J} d. By our inductive hypothesis, this is true if and only if g ∈ G_{J}. Hence Condition (2′) holds. □

3 Graphs of groups

In this section we prove Theorem 1.2.

We recall the definition of a graph of groups, which arises from the work of Bass and Serre [11, 10]

Definition 3.1. A graph of groups G consists of

(1) a connected graph Γ (in which loops are allowed, but no multiple edges), with vertex set V, edge set E,

(2) a collection of vertex groups G_{v} : v ∈ V and edge groups G_{e} : e ∈ E,

(3) for each edge e = {v_{1}, v_{2}} of Γ, monomorphisms θ_{e}^{1} : G_{e} → G_{v_{1}} and θ_{e}^{2} : G_{e} → G_{v_{2}}.

The fundamental group π_{1}(G) of a graph of groups G can defined in various different (but equivalent) ways. The following definition is essentially [2, Definition I.3.4]. The definition is given in terms of a selected spanning tree T of Γ, but (up to isomorphism) the resulting group is independent of this choice. The associated fundamental group π_{1}(G, T) is then the group generated by the groups G_{v} : v ∈ V together with generators t_{e}, one for each (oriented) edge in E), given the following relations.

(1) all the relations of the groups G_{v},

(2) t_{e}^{−1}θ_{e}^{1}(g)t_{e} = θ_{e}^{2}(g), for each e ∈ E, g ∈ G_{e},

(3) t_{e} = 1 for each edge e of T.

From this description it is not hard to see that π_{1}(G, T) is isomorphic to a multiple HNN extension, with stable letters t_{e} for e ∉ E(T), of the amalgamated product of the groups G_{v} in which θ_{e}^{1}(g) and θ_{e}^{2}(g) are identified for all e ∈ E(T), g ∈ G_{e}. Independent results of Elek and Szabo ([4, Theorem 1]) and Paunescu ([7, Corollary 2.3]) already prove that the amalgamated product of two sofic groups over an amenable subgroup is sofic. Hence Theorem 1.2 follows immediately by combining that result with

Proposition 3.2. An HNN extension of a sofic group H over an amenable subgroup K is sofic.

We deduce Proposition 3.2 as a corollary of the amalgamated product result. We note that the argument to do this was already provided by Collins and Dykema in order to deduce their result [1, Corollary 3.6] as a corollary of their result [1, Theorem 3.4], that is to deduce the same result as above in the situation where the associated subgroups (in both amalgamated products and HNN extensions) are monotileably amenable. The argument of [1] goes through without any modification, when monotileability of the associated subgroup is dropped, to deduce the Proposition from the results of [4, 7]. But we include the argument here for completeness.

Proof. Let G be an HNN extension of H over K, as in the proposition, and let L be the subgroup t^{−1}Kt. Define H_{i} = t^{−i}Ht^{i}, K_{i} = t^{−i}Kt^{i}, L_{i} = t^{−i}Lt^{i} for each i ∈ ℤ, and define S := ⟨H_{i} | i ∈ ℤ⟩. Then G can be expressed as an extension of S by ℤ. Since ℤ is amenable, and by [3, Theorem 1(3)] an extension of a sofic group by an amenable group is sofic, in order to prove G sofic it is enough to prove S sofic.

Now S can be expressed as an iterated amalgamated product of the (countably many) H_{i}s, with amalgamation over subgroups isomorphic to K. More precisely, S is the fundamental group of the graph of groups associated with the graph of the integers, where H_{i} is the vertex group of the vertex i, each edge group is isomorphic to K, and the copy of K associated with edge {i, i + 1} maps to the subgroup L_{i} of H_{i}, and the subgroup K_{i+1} of H_{i+1}, as in Figure 1.

⋯ H_{i−1}^{L_{i−1}↩ ↪K_{i}} H_{i} ^{L_{i}↩ ↪K_{i+1}} H_{i+1} ^{L_{i+1}↩ ↪K_{i+2}}H_{i+2} ⋯

Figure 1: The graph of groups H

To prove S sofic we now need to verify soficity for each of its finitely generated subgroups. So let M be such a subgroup. Then for some k, l, all the generators of M are within vertex subgroups H_{i} for k ≤ i ≤ l, that is, M is a subgroup of the amalgamated product

H_{j} ∗_{L_{j}=K_{j+1}} H_{j+1} ∗_{L_{j+1}=K_{j+2}} ∗ ⋯ ∗_{L_{l−1}=K_{l}} H_{l}.

Since this is sofic, by [4, 7], so is M.

Acknowledgments

All three authors were partially supported by the Marie Curie Reintegration Grant 230889. The first named author was also supported by the Swiss National Science Foundation grant Ambizione PZ00P-136897/1.

References

[1] B. Collins and K. J. Dykema, Free products of sofic groups with amalgamation over monotileably amenable groups, Münster J. Math. 4 (2011), 101–118.

[2] W. Dicks and M.L.Dunwoody, Groups acting on graphs, Cambridge studies in advanced mathematics 17, C.U.P. 1989.

[3] G. Elek and E. Szabo, On sofic groups, J. Group Theory 9 (2006), 161 –171.

[4] G. Elek and E. Szabo, Sofic representations of amenable groups, Proc. Amer. Math. Soc. 139 (2011), 4285–4291.

[5] E. Green, Graph products of groups, Ph.D. thesis, University of Leeds, 1990.

[6] M. Gromov, Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc (JEMS) 1 (1999) 109–197.

[7] L. Paunescu, On sofic actions and equivalence relations, J. Funct. Anal. 261 (2011) 2461-2485.

[8] V.G. Pestov, Hyperlinear and sofic groups: a brief guide, Bull. Symbolic Logic 14 (2008), 449–480.

[9] V.G. Pestov and A. Kwiatkowska, An introduction to hyperlinear and sofic groups (preprint) http://arxiv.org/pdf/0911.4266.

[10] J.-P. Serre, Trees, Springer Monogr. Math., Springer, Berlin 2003.

[11] J.-P.Serre, Arbres, amalgames, SL_{2}, Astérisque 46 (1977).

[12] B. Weiss, Sofic groups and dynamical systems, Ergodic Theory and Harmonic Analysis 2000 (62) 350–359.

L. Ciobanu, Mathematics Department, University of Neuchâtel, Rue Emile - Argand 11, CH-2000 Neuchâtel, Switzerland

E-mail address: laura.ciobanu@unine.ch

D. F. Holt, Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK

E-mail address: D.F.Holt@warwick.ac.uk

S. Rees, School of Mathematics and Statistics, University of Newcastle, Newcastle NE1 7RU, UK

E-mail address: Sarah.Rees@newcastle.ac.uk