The Finitary Andrews-Curtis Conjecture

Alexandre V. Borovik  Alexander Lubotzky

Alexei G. Myasnikov

12 June 2003

To Slava Grigorchuk as a token of our friendship.

Abstract The well known Andrews-Curtis Conjecture [2] is still open. In this paper, we establish its finite version by describing precisely the connected components of the Andrews-Curtis graphs of finite groups. This finite version has independent importance for computational group theory. It also resolves a question asked in [5] and shows that a computation in finite groups cannot lead to a counterexample to the classical conjecture, as suggested in [5].

1 Andrews-Curtis graphs

Let G be a group and G^{k} be the set of all k-tuples of elements of G.

The following transformations of the set G^{k} are called elementary Nielsen transformations (or moves):

(1) (x_{1}, …, x_{i}, …, x_{k}) ⟶ (x_{1}, …, x_{i}x_{j}^{±1}, …, x_{k}), i ≠ j;

(2) (x_{1}, …, x_{i}, …, x_{k}) ⟶ (x_{1}, …, x_{j}^{±1}x_{i}, …, x_{k}), i ≠ j;

(3) (x_{1}, …, x_{i}, …, x_{k}) ⟶ (x_{1}, …, x_{i}^{−1}, …, x_{k}).

Elementary Nielsen moves transform generating tuples of G into generating tuples. These moves together with the transformations

(4) (x_{1}, …, x_{i}, …, x_{k}) ⟶ (x_{1}, …, x_{i}^{w}, …, x_{k}), w ∈ S ∪ S^{−1} ⊂ G,

A.V. Borovik, A. Lubotzky and A.G. Myasnikov • The Finitary Andrews-Curtis Conjecture • 12.06.03 2

where S is a fixed subset of G, form a set of elementary Andrews-Curtis transformations relative to S (or, shortly, AC_{S}-moves). If S = G then AC-moves transform n-generating tuples (i.e., tuples which generate G as a normal subgroup) into n-generating tuples. We say that two k-tuples U and V are AC_{S}- equivalent, and write U ∼_{S} V, if there is a finite sequence of AC_{S}-moves which transforms U into V. Clearly, ∼_{S} is an equivalence relation on the set G^{k} of k-tuples of elements from G. In the case when S = G we omit S in the notations and refer to AC_{S}-moves simply as to AC-moves.

We slightly change notation from that of [5]. For a subset Y ⊂ G we denote by gp_{G}(Y) the normal closure of Y in G, by d(G) the minimal number of generators of G, and by d_{G}(G) the minimal number of normal generators of G. Now, d_{G}(G) coincides with nd(G) of [5].

Let N_{k}(G), k ⩾ d_{G}(G), be the set of all k-tuples of elements in G which generate G as a normal subgroup:

N_{k}(G) = { (g_{1}, …, g_{k}) | gp_{G}(g_{1}, …, g_{k}) = G } .

Then the Andrews–Curtis graph Δ_{k}^{S}(G) of the group G with respect to a given subset S ⊂ G is the graph whose vertices are k-tuples from N_{k}(G) and such that two vertices are connected by an edge if one of them is obtained from another by an elementary AC_{S}-transformation. Again, if S = G then we refer to Δ_{k}^{G}(G) as to the Andrews-Curtis graph of G and denote it by Δ_{k}(G). Clearly, if S is a generating set of G then the graph Δ_{k}^{S}(G) is connected if and only if the graph Δ_{k}(G) is connected. Observe, that if S is finite then Δ_{k}^{S}(G) is a regular graph of finite degree.

The famous Andrews-Curtis conjecture [2] can be stated in the following way.

AC-Conjecture: For a free group F_{k} of rank k ⩾ 2, the Andrews– Curtis graph Δ_{k}(F_{k}) is connected.

There are some doubts whether this well known old conjecture is true. Indeed, Akbulut and Kirby [1] suggested a series of potential counterexamples for k = 2:

(u, v_{n}) = (xyxy^{−1}x^{−1}y^{−1}, x^{n}y^{−(n+1)}), n ⩾ 2.  (1)

In [5], it has been suggested that one may be able to confirm one of these potential counterexamples by showing that for some homomorphism ϕ : F_{2} → G into a finite group G the pairs (u^{ϕ}, v_{n}^{ϕ}) and (x^{ϕ}, y^{ϕ}) lie in different connected components of Δ_{2}(G). Notice that in view of [15] the group G in the counterexample cannot be soluble.

Our main result describes the connected components of the Andrews-Curtis graph of a finite group. As a corollary we show that (u^{ϕ}, v_{n}^{ϕ}) and (x^{ϕ}, y^{ϕ}) lie in the same connected components of Δ_{2}(G) for every finite group G and any homomorphism ϕ : F_{2} → G, thus resolving the question from [5].

Theorem 1.1 Let G be a finite group and k ⩾ max{d_{G}(G), 2}. Then two tuples U, V from N_{k}(G) are AC-equivalent if and only if they are AC-equivalent in the abelianisation Ab(G) = G/[G, G], i.e., the connected components of the AC-graph Δ_{k}(G) are precisely the preimages of the connected components of the AC-graph Δ_{k}(Ab(G)).

Notice that, for the abelian group A = Ab(G), a normal generating set is just a generating set and the non-trivial Andrews-Curtis transformations are Nielsen moves (1)–(3). Therefore the vertices of Δ_{k}(A) are the same as these of the product replacement graph Γ_{k}(A) [7, 17]: they are all generating k-tuples of A. The only difference between Γ_{k}(A) and Δ_{k}(A) is that the former has edges defined only by ‘transvections’ (1)–(2), while in the latter the inversion of components (3) is also allowed. The connected components of product replacements graphs Γ_{k}(A) for finite abelian groups A have been described by Diaconis and Graham [7]; a slight modification of their proof leads to the following observation

Fact 1.2 (Diaconis and Graham [7]) Let A be a finite abelian group and

A = Z_{1} × ⋯ × Z_{d}

its canonical decomposition into a direct product of cyclic groups such that |Z_{i}| divides |Z_{j}| for i < j. Then

(a) If k > d then Δ_{k}(A) is connected.

(b) If k = d ⩾ 2, fix generators z_{1}, …, z_{d} of the subgroups Z_{1}, …, Z_{d}, correspondingly. Let m = |Z_{1}|. Then Δ_{d}(A) has ϕ(m)/2 connected components (here ϕ(n) is the Euler function). Each of these components has a representative of the form

(z_{1}^{λ}, z_{2}, …, z_{d}), λ ∈ (ℤ/mℤ)^{∗}.

Two tuples

(z_{1}^{λ}, z_{2}, …, z_{d}) and (z_{1}^{μ}, z_{2}, …, z_{d}), λ, μ ∈ (ℤ/mℤ)^{∗},

belong to the same connected component if and only if λ = ±μ.

Taken together, Theorem 1.1 and Fact 1.2 give a complete description of components of the Andrews-Curttis graph Δ_{k}(G) of a finite group G.

Notice that in an abelian group A

(xyxy^{−1}x^{−1}y^{−1}, x^{n}y^{−(n+1)}) ∼ (xy^{−1}, x^{n}y^{−(n+1)})
∼ (xy^{−1}, x^{n−1}y^{−n})
⋮
∼ (yx^{−1}, y^{−1})
∼ (x, y)

so for every homomorphism ϕ : F_{2} → G as above the images (u^{ϕ}, v_{n}^{ϕ}) and (x^{ϕ}, y^{ϕ}) are AC equivalent in the abelianisation of G, hence they lie in the same connected component of Δ_{2}(G).

The following corollary of Theorem 1.1 leaves no hope of finding an counterexample to the Andrews-Curtis conjecture by looking at the connected components of the Andrews-Curtis graphs of finite groups.

Corollary 1.3 For any k ⩾ 2, and any epimorphism ϕ : F_{k} → G onto a finite group G, the image of Δ_{k}(F_{k}) in Δ_{k}(G) is connected.

One may try to reject the AC-conjecture by testing AC-equivalence of the tuples (u, v_{n}) and (x, y) in the infinite quotients of the group F_{2}. To this end we introduce the following definition.

Definition: We say that a group G satisfies the generalised Andrews-Curtis conjecture if for any k ⩾ max{ d_{G}(G), 2 } tuples U, V ∈ N_{k}(G) are AC-equivalent in G if and only if their images are ACequivalent in the abelianisation Ab(G).

Problem: Find a group G which does not satisfy the generalised Andrews-Curtis conjecture.

It will be interesting to look, for example, at the Grigorchuk group [8, 9]. It is a finitely generated residually finite 2-group G which is just-infinite, that is, every normal subgroup has finite index. Therefore the generalised Andrews-Curtis conjecture holds in every proper factor group of G by Theorem 1.1. What might be also relevant, the conjugacy problem in the Grigorchuk group is solvable [13, 18, 3]. This makes the Grigorchuk group a very interesting testing ground for the generalised Andrews-Curtis conjecture.

2 Relativised Andrews-Curtis graphs and blackbox groups

Following [5], we also introduce a relativised version of the Andrews-Curtis transformations of the set G^{k} for the situation when G admits some fixed group of operators Ω (that is, a group Ω which acts on G by automorphisms); we shall say in this situation that G is an Ω-group^{1}. In that case, we view the group G as a subgroup of the natural semidirect product G·Ω of G and Ω. In particular, the set of AC_{GΩ}-moves is defined and the set G^{k} is invariant under these moves. In particular, if N is a normal subgroup of G, we view N as a G-subgroup in the sense of this definition. As we shall soon see, AC_{GΩ}-moves appear in the product replacement algorithm for generating pseudo-random elements of a normal subgroup in a black box finite group.

For a subset Y ⊂ G of an Ω-group G we denote by gp_{GΩ}(Y) the normal closure of Y in G · Ω, and by d_{GΩ}(G) the minimal number of normal generators of G as a normal subgroup of G · Ω.

Let N_{k}(G, Ω), k ⩾ d_{GΩ}(G), be the set of all k-tuples of elements in G which generate G as a normal Ω-subgroup:

N_{k}(G, Ω) = { (g_{1}, …, g_{k}) | gp_{G·Ω}(g_{1}, …, g_{k}) = G } .

1We shall use the terms Ω-subgroup, normal Ω-subgroup, Ω-simple Ω-subgroup, etc. in their obvious meaning.

Then the relativised Andrews–Curtis graph Δ_{k}^{Ω}(G) of the group G is the graph whose vertices are k-tuples from N_{k}(G, Ω) and such that two vertices are connected by an edge if one of them is obtained from another by an elementary AC_{GΩ}-transformation.

A black box group G is a finite group with a device (‘oracle’) which produces its (pseudo)random (almost) uniformly distributed elements; this concept is of crucial importance for computational group theory, see [10]. If the group G is given by generators, the so-called product replacement algorithm [6, 17] provides a very efficient and practical way of producing random elements from G; see [14] for a likely theoretical explanation of this (still largely empirical) phenomenon in terms of the (conjectural) Kazhdan’s property (T) [11] for the group of automorphisms of the free group F_{k} for k > 4. In the important case of generation of random elements in a normal subgroup G of a black box group Ω, the following simple procedure is a modification of the product replacement algorithm: start with the given tuple U ∈ N_{k}(G, Ω), walk randomly over the graph Δ_{k}^{Ω}(G) (using the ‘oracle’ for Ω for generating random AC_{GΩ}-moves and return randomly chosen components v_{i} of vertices V on your way. See [4, 5, 12] for a more detailed discussion of this algorithm, as well as its further enhancements.

Therefore the understanding of the structure—and ergodic properties—of the Andrews-Curtis graphs Δ_{k}^{Ω}(G) is of some importance for the theory of black box groups.

The following results are concerned with the connectivity of the relativised Andrews-Curtis graphs of finite groups.

Theorem 2.1 Let G be a finite Ω-group which is perfect as an abstract group, G = [G, G]. Then the graph Δ_{k}^{Ω}(G) is connected for every k ⩾ 2.

Of course, this result can be immediately reformulated for normal subgroups of finite groups:

Corollary 2.2 Let G be a finite group and N ◁ G a perfect normal subgroup. Then the graph Δ_{k}^{G}(N) is connected for every k ⩾ 2.

We would like to record another immediate corollary of Theorem 2.1.

Corollary 2.3 Let G be a perfect finite group, g_{1}, …, g_{k}, k ⩾ 2 generate G as a normal subgroup and ϕ : F_{k} ⟶ G an epimorphism. Then there exist f_{1}, …, f_{k} ∈ F_{k} such that ϕ(f_{i}) = g_{i}, i = 1, …, k, and f_{1}, …, f_{k} generate F_{k} as a normal subgroup.

Note that if we take g_{1}, …, g_{k} as a set of generators for G, then in general we cannot pull them back to a set f_{1}, …, f_{k} of generators for F_{k}, an example can be found in G = Alt_{5}, the alternating group on 5 letters [16].

In case of non-perfect finite groups we prove the following theorem.

Theorem 2.4 Let G be a finite Ω-group. Then the graph Δ_{k}^{Ω}(G) is connected for every k ⩾ d_{GΩ}(G) + 1.

Note this is not true for k = d_{GΩ}(G), e.g. for when G is abelian.

Corollary 2.5 Let G be a finite group and N ◁ G a normal subgroup. Then the graph Δ_{k}^{G}(N) is connected for every k ⩾ d_{G}(N) + 1.

These results lead us to state the following conjecture.

Relativised Finitary AC-Conjecture: Let G be a finite Ωgroup and k = d_{GΩ}(G) ⩾ 2. Then two tuples U, V from N_{k}(G, Ω) are AC_{GΩ}-equivalent if and only if they are AC_{ΩAb(G)}-equivalent in the abelianisation Ab(G) = G/[G, G], i.e., the connected components of the graph Δ_{k}^{Ω}(G) are precisely the preimages of the connected components of the graph Δ_{k}^{Ω}(Ab(G)).

Theorem 1.1 confirms the conjecture when G = Ω.

3 Elementary properties of AC-transformations

Let G be an Ω-group. From now on for tuples U, V ∈ G^{k} we write U ∼_{G} V, or simply U ∼ V, if the tuples U, V are AC_{GΩ}-equivalent in G.

Lemma 3.1 Let G be an Ω-group, N a normal Ω-subgroup of G, and ϕ : G → G/N the canonical epimorphism. Suppose (u_{1}, …, u_{k}) and (v_{1}, …, v_{k}) are two k-tuples of elements from G. If

(u_{1}^{ϕ}, …, u_{k}^{ϕ}) ∼_{G/N} (v_{1}^{ϕ}, …, v_{k}^{ϕ})

then there are elements m_{1}, …, m_{k} ∈ N such that

(u_{1}, …, u_{k}) ∼_{G} (v_{1}m_{1}, …, v_{k}m_{k}).

Moreover, one can use the same system of elementary transformations (after replacing conjugations by elements gN ∈ G/N by conjugations by elements g ∈ G) .

Proof. Straightforward. □

Lemma 3.2 Let G be an Ω-group. If (w_{1}, …, w_{k}) ∈ G^{k} then for every i and every element g ∈ gp_{GΩ}(w_{1}, …, w_{i−1}, w_{i+1}, …, w_{k})

(w_{1}, …, w_{k}) ∼_{G} (w_{1}, …, w_{i}g, …, w_{k}).

Proof. Obvious. □

4 The N-Frattini subgroup and semisimple decompositions

Definition 1 Let G be an Ω-group. The N-Frattini subgroup of G is the intersection of all proper maximal normal Ω-subgroups of G, if such exist, and the group G, otherwise. We denote it by W (G).

Observe, that if G has a non-trivial finite Ω-quotient then W (G) ≠ G.

An element g in an Ω-group G is called non-N-generating if for every subset Y ⊂ G if gp_{G}(Y ∪ {g}) = G then gp_{G}(Y) = G.

Lemma 4.1

(1) The set of all non-N-generating elements of an Ω-group G coincides with W (G).

(2) A tuple U = (u_{1}, …, u_{k}) generates G as a normal Ω-subgroup if and only if the images (ū_{1}, …, ū_{k}) of elements u_{1}, …, u_{k} in Ḡ = G/W (G) generate Ḡ as normal Ω-subgroup.

(3) G/W (G) is an Ω-subgroup of an (unrestricted) Cartesian product of Ωsimple Ω-groups (that is, Ω-groups which do not have proper non-trivial normal Ω-subgroups).

(4) As an abstract group, G/W (G) is a subgroup of an (unrestricted) Cartesian product of characteristically simple groups. In particular, if G is finite then G/W (G) is a product of simple groups.

Proof. (1) and (2) are similar to the standard proof for the analogous property of the Frattini subgroup.

To prove (3) let N_{i}, i ∈ I, be the set of all maximal proper normal Ωsubgroups of G. The canonical epimorphisms G → G/N_{i} = G_{i} give rise to a homomorphism ϕ : G → \overline{∏}_{i∈I}G_{i} of G into the unrestricted Cartesian product of Ω-groups G_{i}. Clearly, ker ϕ = W (G). So G/W (G) is an Ω-subgroup of the Cartesian product of Ω-simple Ω-groups G_{i}.

To prove (4) it suffices to notice that G_{i} = G/N_{i} has no Ω-invariant normal subgroups, hence is characteristically simple. □

To study the quotient G/W (G) we need to recall a few definitions. Let

G = ∏_{i∈I} G_{i}

be a direct product of Ω-groups. Elements g ∈ G are functions g : I → ⋃ G_{i} such that g(i) ∈ G_{i} and with finite support supp(g) = {i ∈ I | g_{i} ≠ 1}. By π_{i} : G → G_{i} we denote the canonical projection π_{i}(g) = g(i), we also denote π_{i}(g) = g_{i}. Sometimes we identify the group G_{i} with its image in G under the canonical embedding λ_{i} : G_{i} → G such that π_{i}(λ_{i}(g)) = g and π_{j}(λ_{i}(g)) = 1 for j ≠ i.

An embedding (and we can always assume it is an inclusion) of an Ω-group H into the Ω-group G

ϕ : H ↪ ∏_{i∈I} G_{i}  (2)

is called a subdirect decomposition of H if π_{i}(H) = G_{i} for each i (here H is viewed as a subgroup of G). The subdirect decomposition (2) is termed minimal if H ∩ G_{i} ≠ {1} for any i = 1, …, n, where both G_{i} and H are viewed as subgroups of G. It is easy to see that given a subdirect decomposition of H one can obtain a minimal one by deleting non-essential factors (using Zorn’s lemma).

Definition 2 An Ω-group G admits a finite semisimple decomposition if W (G) ≠ G and G/W (G) is a finite direct product of Ω-simple Ω-groups.

The following lemma shows that any minimal subdirect decomposition into simple groups is, in fact, a direct decomposition.

Lemma 4.2 Let ϕ : G → ∏_{i∈I} G_{i} be a minimal subdirect decomposition of an Ω-group G into Ω-simple Ω-groups G_{i}, i ∈ I. Then G = ∏_{i∈I} G_{i}.

Proof. Let K_{i} = G ∩ G_{i}, i ∈ I. It suffices to show that K_{i} = G_{i}. Indeed, in this event G ⩾ ∏_{i∈I} G_{i} and hence G = ∏_{i∈I} G_{i}..

Fix an arbitrary i ∈ I. Since ϕ is minimal there exists a non-trivial g_{i} ∈ K_{i}. For an arbitrary x_{i} ∈ G_{i} there exists an element x ∈ G such that π_{i}(x) = x_{i}. It follows that g_{i}^{x} = g_{i}^{x_{i}} ∈ K_{i}. Hence K_{i} ⩾ gp_{G_{i}Ω}(g_{i}) = G_{i}, as required. □

Lemma 4.3 If an Ω-group G has a finite semisimple decomposition then it is unique (up to a permutation of factors).

Proof. Obvious. □

Obviously, an Ω-group G admits a finite semisimple decomposition if and only if W (G) is intersection of finitely many maximal normal Ω-subgroups of G. This implies the following lemma.

Lemma 4.4 A finite Ω-group admits a finite semisimple decomposition.

5 Connectivity of Andrews-Curtis graphs of perfect finite groups

Recall that a group G is called perfect if [G, G] = G.

Lemma 5.1 Let an Ω-group G admits a finite semisimple decomposition:

G/W (G) = G_{1} × ⋯ × G_{k}.

Then G is perfect if and only if all Ω-simple Ω-groups G_{i} are non-abelian.

Proof. Obvious. □

We need the following notations to study normal generating tuples in an Ω-group G admitting finite semisimple decomposition. If g ∈ ∏_{i∈I} G_{i} then by supp(g) we denote the set of all indices i such that π_{i}(g) ≠ 1.

Lemma 5.2 Let G = ∏_{i∈I} G_{i} be a finite product of Ω-simple non-abelian Ωgroups. If g ∈ G then gp_{GΩ}(g) ⩾ G_{i} for any i ∈ supp(g).

Proof. If g ∈ G and g_{i} = π_{i}(g) ≠ 1, then there exists x_{i} ∈ G_{i}Ω with [g_{i}, x_{i}] ≠ 1. Hence 1 ≠ [g, x_{i}] = [g_{i}, x_{i}] ∈ gp_{GΩ}(g) ∩ G_{i}. Since G_{i} is Ω-simple it coincides with the nontrivial normal Ω-subgroup gp_{GΩ}(g) ∩ G_{i}, as required. □

Let G/W (G) = ∏_{i∈I} G_{i} be the canonical semisimple decomposition of an Ω-group G. For an element g ∈ G by ḡ we denote the canonical image gW (G) of g in G/W (G) and by supp(g) we denote the support supp(ḡ) of ḡ. □

Lemma 5.3 Let G be a finite perfect Ω-group and G/W (G) = ∏_{i∈I} G_{i} be its canonical semisimple decomposition. Then a finite set of elements g_{1}, …, g_{m} ∈ G generates G as a normal Ω-subgroup if and only if

supp(g_{1}) ∪ ⋯ ∪ supp(g_{m}) = I.

Proof. It follows from Lemma 5.2 and Lemma 4.1. □

Proof of Theorem 2.1. We can now prove Theorem 2.1 which settles the Relativised Finitary AC-Conjecture in affirmative for finite perfect Ω-groups.

Let G be a finite perfect Ω-group, \overline{G} = G/W (G), and \overline{G} = ∏_{i∈I} G_{i} be its canonical semisimple decomposition. Fix an arbitrary k ⩾ 2.

Claim 1. Let U = (u_{1}, …, u_{k}) ∈ N_{k}(G, Ω). Then there exists an element g ∈ G with supp(g) = I such that

(u_{1}, …, u_{k}) ∼_{G} (g, u_{2}, …, u_{k}).

Indeed, by Lemma 4.1 the tuple U generates G as a normal subgroup if and only if its image \overline{U} generates \overline{G} as a normal subgroup. Lemma 3.1 shows that it suffices to prove the claim for the Ω-group \overline{G} (recall that supp(g) = supp(ḡ)). So we can assume that G = ∏_{i∈I} G_{i}. Since U ∈ N_{k}(G, Ω), Lemma 5.3 implies that

supp(u_{1}) ∪ ⋯ ∪ supp(u_{k}) = I.

Let i ∈ I and i ∉ supp(u_{1}). Then there exists an index j such that i ∈ supp(u_{j}). By Lemma 5.2, gp_{GΩ}(u_{j}) ⩾ G_{i}. So there exists a non-trivial h ∈ gp_{GΩ}(u_{j}) with supp(h) = {i}. By Lemma 3.2, U ∼ (u_{1}h, u_{2}, …, u_{k}) = U^{∗} and supp(u_{1}h) = supp(u_{1}) ∪ {i}. Now the claim follows by induction on the cardinality of I ∖ supp(u_{1}). In fact, one can bound the number of elementary AC-moves needed in Claim 1. Indeed, since G_{i} is non-abelian Ω-simple there exists an element x ∈ GΩ such that u_{j}^{x} ≠ u_{j}. Then the element h above can be taken in the form h = u_{j}^{x}u_{j}^{−1}, and only four moves are needed to transform U into U^{∗}. This proves the claim.

Claim 2. Every k-tuple U_{1} = (g, u_{2}, …, u_{k}) with supp(g) = I is ACequivalent to a tuple U_{2} = (g, 1, …, 1).

By Lemma 5.3 g generates G as a normal Ω-subgroup. Now the claim follows from Lemma 3.2.

Claim 3. Every two k-tuples U_{2} = (g, 1, …, 1) and U_{3} = (h, 1, …, 1) from N_{k}(G, Ω) are AC-equivalent.

Indeed, U_{2} is AC-equivalent to (g, 1, …, 1, g). By Lemma 3.2 the former one is AC-equivalent to (h, …, 1, g), which is AC-equivalent to (h, 1, …, 1), as required.

The theorem follows from Claims 1, 2, and 3. □

6 Arbitrary finite groups

Lemma 6.1 Let

G = G_{1} × ⋯ × G_{s} × A  (3)

be a direct decomposition of an Ω-group G into a product of non-abelian Ω-simple Ω-groups G_{i}, i = 1, … s, and an abelian Ω-group A. Then, assuming G ≠ 1,

d_{GΩ}(G) = max{d_{AΩ}(A), 1}.

Proof. Put S(G) = G_{1} × ⋯ × G_{s}. Since A is a quotient of G then d_{GΩ}(G) ⩾ d_{AΩ}(A). Therefore, d_{GΩ}(G) ⩾ max{d_{AΩ}(A), 1}. On the other hand, if g generates S(G) as a normal Ω-subgroup (such g exists by Lemma 5.3) and a_{1}, …, a_{d_{Ω}(A)} generate A then we claim that the tuple of elements from G:

(ga_{1}, a_{2}, …, a_{d_{Ω}(A)})

generates G as a normal Ω-subgroup. Indeed, let g = g_{1} ⋯ g_{s} with 1 ≠ g_{i} ∈ G_{i}. Since G_{i} is non-abelian then g_{i} is not central in G_{i} and hence there exists h_{i} ∈ G_{i} such that [g_{i}, h_{i}] ≠ 1. It follows that if h = h_{1} … h_{s} then [g, h] ≠ 1 and supp([g, h]) = {1, …, n}. In particular, [g, h] belongs to N = gp_{GΩ}(ga_{1}, a_{2}, …, a_{d_{Ω}(A)}) and generates S(G) as a normal Ω-subgroup. Therefore, S(G) ⊂ N and hence a_{1}, …, a_{d_{Ω}(A)} ∈ N, which implies that G = N. This shows that d_{GΩ}(G) = max{d_{Ω}(A), 1}, as required.

Proof of Theorem 2.4. Let G be a minimal counterexample to the statement of the theorem. Then G is not perfect. G is also non-abelian by Fact 1.2. Put t = d_{GΩ}(G) and k ⩾ t + 1. Let M be a minimal non-trivial normal Ωsubgroup of G. It follows that M ≠ G, and the theorem holds for the Ω-group \overline{G} = G/M. Obviously, k > d_{GΩ}(G) ⩾ d_{ḠΩ}(\overline{G}), hence the AC-graph Δ_{k}^{Ω}(\overline{G}) is connected. Fix any tuple (z_{1}, …, z_{t}) ∈ N_{t}(G, Ω). If (y_{1}, …, y_{k}) is an arbitrary tuple from N_{k}(G, Ω) then the k-tuples (ȳ_{1}, …, ȳ_{k}) and (z̄_{1}, …, z̄_{t}, 1, …, 1) are AC-equivalent in \overline{G}. Hence by Lemma 3.1 there are elements m_{1}, …, m_{k} ∈ M such that

(y_{1}, …, y_{k}) ∼ (z_{1}m_{1}, …, z_{t}m_{t}, m_{t+1}, …, m_{k}).

We may assume that one of the elements m_{t+1}, …, m_{k} in distinct from 1, say m_{k} ≠ 1. Indeed, if m_{t+1} = … = m_{k} = 1 then the elements z_{1}m_{1}, …, z_{t}m_{t} generate G as a normal Ω-subgroup, hence applying AC-transformations we can get any non-trivial element from M in the place of m_{k}. Since M is a minimal normal Ω-subgroup of G it follows that M is the GΩ-normal closure of m_{k} in G, in particular, every m_{i} is a product of conjugates of m_{k}^{±1}. Applying AC-transformations we can get rid of all elements m_{i}, i = 1, …, m_{t}, in the tuple above. Hence,

(z_{1}m_{1}, …, z_{t}m_{t}, m_{t+1}, …, m_{k}) ∼ (z_{1}, …, z_{t}, 1, …, 1, m_{k}).

But (z_{1}, …, z_{t}) ∈ N_{t}(G, Ω), hence

(z_{1}, …, z_{t}, 1, …, m_{k}) ∼ (z_{1}, …, z_{t}, 1, …, 1).

We showed that any k-tuple (y_{1}, …, y_{k}) ∈ N_{k}(G, Ω) is AC-equivalent to the fixed tuple (z_{1}, …, z_{t}, 1, …, 1). So the AC-graph Δ_{k}^{Ω}(G) is connected and G is not a counterexample. This proves the theorem. □

7 Proof of Theorem 1.1

We denote by g̃ the image of g ∈ G in the abelinisation Ab(G) = G/[G, G].

We systematically, and without specific references, use elementary properties of Andrews-Curtis transformations, Lemmas 3.1 and 3.2.

Suppose Theorem 1.1 is false. Consider a counterexample G of minimal order for a given k ⩾ d_{G}(G). For a given k-tuple (g_{1}, …, g_{k}) ∈ N_{k}(G) we denote by C(g_{1}, …, g_{k}) the set

{(h_{1}, …, h_{k}) ∈ N_{k}(G) | (g̃_{1}, …, g̃_{k}) ∼ (h̃_{1}, …, h̃_{k}) & (g_{1}, …, g_{k}) ≁ (h_{1}, …, h_{k})}

Put

D = {(g_{1}, …, g_{k}) ∈ N_{k}(G) | C(g_{1}, …, g_{k}) ≠ ∅}.

Then the set D is not empty. Consider the following subset of D:

E = {(g_{1}, …, g_{k}) ∈ D | |gp_{G}(g_{2}, …, g_{k})| is minimal possible}.

Finally, consider the subset F of E:

F = {(g_{1}, …, g_{k}) ∈ E | |gp_{G}(g_{1})| is minimal possible }

In order to prove the theorem it suffices to show that G is abelian.

Fix an arbitrary tuple (g_{1}, …, g_{k}) ∈ F and an arbitrary tuple (h_{1}, …, h_{k}) ∈ C(g_{1}, …, g_{k}). Denote G_{1} = gp_{G}(g_{1}) and G_{2} = gp_{G}(g_{2}, …, g_{k}).

The following series of claims provides various inductive arguments which will be in use later.

Notice that the minimal choice of g_{1} and g_{2}, …, g_{k} can be reformulated as

Claim 1.1 Let f_{1} ∈ G_{1}, f_{2}, …, f_{k} ∈ G_{2} such that (f_{1}, f_{2}, …, f_{k}) ∈ C(g_{1}, …, g_{k}). Then

gp_{G}(f_{1}) = G_{1} and gp_{G}(f_{2}, …, f_{k}) = G_{2}.

Claim 1.2 Let f_{1} ∈ G, f_{2}, …, f_{k} ∈ G_{2} such that (f_{1}, f_{2}, …, f_{k}) ∈ C(g_{1}, …, g_{k}). Then

gp_{G}(f_{2}, …, f_{k}) = G_{2}.

Claim 1.3 Let M be a non-trivial normal subgroup of G. Then

(h_{1}, …, h_{k}) ∼ (g_{1}m_{1}, …, g_{k−1}m_{k−1}, g_{k}m_{k})

for some m_{1}, …, m_{k} ∈ M.

Indeed, obviously

(h_{1}M, …, h_{k}M), (g_{1}M, …, g_{k}M) ∈ N_{k}(G/M).

Moreover, since

(g̃_{1}, …, g̃_{k}) ∼ (h̃_{1}, …, h̃_{k})

there exists a sequence of AC-moves t_{1}, …, t_{n} (where each t_{i} is one of the transformations (1)–(4), with the specified values of w in the case of transformations (4)) and elements c_{1}, …, c_{k} ∈ [G, G] such that

(h_{1}, …, h_{k})t_{1} ⋯ t_{k} = (g_{1}c_{1}, …, g_{k}c_{k})

Therefore

(h_{1}M, …, h_{k}M)t_{1} ⋯ t_{k} = (g_{1}c_{1}M, …, g_{k}c_{k}M)

Since c_{i}M ∈ [G/M, G/M] for every i = 1, …, k this shows that the images of the tuples (h_{1}M, …, h_{k}M) and (g_{1}M, …, g_{k}M) are AC-equivalent in the abelianisation Ab(G/M). Now the claim follows from the fact that |G/M| < |G| and the assumption that G is the minimal possible counterexample.

The following claim says that the set C(g_{1}, …, g_{k}) is closed under ∼.

Claim 1.4 If (e_{1}, …, e_{k}) ∈ C(g_{1}, …, g_{k}) and (f_{1}, …, f_{k}) ∼ (e_{1}, …, e_{k}) then (f_{1}, …, f_{k}) ∈ C(g_{1}, …, g_{k})

Now we study the group G in a series of claims.

Claim 2. G = G_{1} × G_{2}.

Indeed, it suffices to show that G_{1} ∩ G_{2} = 1. Assume the contrary, then M = G_{1} ∩ G_{2} ≠ 1 and by Claim 1.3

(h_{1}, …, h_{k}) ∼ (g_{1}m_{1}, …, g_{k−1}m_{k−1}, g_{k}m_{k})

for some m_{1}, …, m_{k} ∈ M. By Claim 1.4

(g_{1}m_{1}, …, g_{k−1}m_{k−1}, g_{k}m_{k}) ∈ C(g_{1}, …, g_{k})

By Claim 1.1,

gp_{G}(g_{1}m_{1}) = G_{1}, gp_{G}(g_{2}m_{2}, …, g_{k}m_{k}) = G_{2}

and we can represent the elements m_{2}, …, m_{k} ∈ G_{1} ∩ G_{2} as products of conjugates of g_{1}m_{1}, therefore deducing that

(g_{1}m_{1}, g_{2}m_{2} …, g_{k}m_{k}) ∼ (g_{1}m_{1}, g_{2}, …, g_{k}).

Since m_{1} ∈ gp_{G}(g_{2}, …, g_{k}⟩, we conclude that

(g_{1}m_{1}, g_{2}, …, g_{k}) ∼ (g_{1}, g_{2}, …, g_{k}),

and therefore

(h_{1}, …, h_{k}) ∼ (g_{1}, …, g_{k}),

a contradiction. This proves the claim. □

Claim 3. [G_{2}, G_{2}] = 1. In particular, G_{2} ⩽ Z(G).

Indeed, assume the contrary. Then M = [G_{2}, G_{2}] ≠ 1 and by Claim 1.3

(h_{1}, …, h_{k}) ∼ (g_{1}m_{1}, …, g_{k}m_{k}), m_{1}, …, m_{k} ∈ M ⩽ G_{2}.

By virtue of Claims 1.4 and 1.2, gp_{G}(g_{2}m_{2}, …, g_{k}m_{k}) = G_{2} and hence m_{1} ∈ gp_{G}(g_{2}m_{2}, …, g_{k}m_{k}). It follows that

(g_{1}m_{1}, g_{2}m_{2}, …, g_{k}m_{k}) ∼ (g_{1}, g_{2}m_{2} …, g_{k}m_{k}).

Therefore it will be enough to prove

(g_{1}, g_{2}m_{2}, …, g_{k}m_{k}) ∼ (g_{1}, g_{2}, …, g_{k}).

We proceed as follows, systematically using the fact that g_{2}, …, g_{k} and all their conjugates commute with all the conjugates of g_{1}.

We start with a series of Nielsen moves which lead to

(g_{1}, g_{2}m_{2} …, g_{k}m_{k}) ∼ (g_{1}, g_{1} · g_{2}m_{2}, g_{3}m_{3}, …, g_{k}m_{k})
∼ (g_{1} · m_{2}, g_{1}g_{2}m_{2}, g_{3}m_{3}, …, g_{k}m_{k}).

The last transformation is the key for the whole proof and requires some explanation. Since m_{2} belongs to

[G_{2}, G_{2}] = [gp_{G}(g_{2}m_{2}, …, g_{k}m_{k}), gp_{G}(g_{2}m_{2}, …, g_{k}m_{k})],

m_{2} can be expressed as a word

w(x_{2}, …, x_{k}) = (x_{i_{1}}^{f_{1}})^{ε_{1}} ⋯ (x_{i_{l}}^{f_{l}})^{ε_{l}}

where x_{i} = g_{i}m_{i}, i = 2, …, k, f_{j} ∈ G and the word w is balanced for each variable x_{i}, that is, for each h = 2, …, k, the sum of exponents for each x_{h} is zero:

∑_{i_{j}=h} ε_{j} = 0.

Moreover, since G = G_{1} × G_{2}, we can choose f_{j} ∈ G_{2}, whence commuting with g_{1} ∈ G_{1}. Therefore

w(g_{1}x_{2}, x_{3}, …, x_{k}) = w(x_{2}, x_{3}, …, x_{k})

and

w(g_{1}g_{2}m_{2}, g_{3}m_{3}, …, g_{k}m_{k}) = m_{2}.

Hence, by several consecutive multiplications by appropriate conjugates of g_{1}g_{2}m_{2} and g_{i}m_{i}, i = 3, …, k, we can produce the factor m_{2} in the leftmost position in the tuple. We now continue:

(g_{1}m_{2}, g_{1}g_{2}m_{2}, g_{3}m_{3}, …, g_{k}m_{k}) ∼ (g_{1}m_{2}, g_{1}g_{2}m_{2} · (g_{1}m_{2})^{−1}, g_{3}m_{3}, …, g_{k}m_{k})
= (g_{1}m_{2}, g_{2}, g_{3}m_{3}, …, g_{k}m_{k}).

Again by Claims 1.4 and 1.2 G_{2} = gp_{G}(g_{2}, g_{3}m_{3}, …, g_{k}m_{k}⟩. Since m_{2} ∈ G_{2},

(g_{1}m_{2}, g_{2}, g_{3}m_{3}, …, g_{k}m_{k}) ∼ (g_{1}, g_{2}, g_{3}m_{3}, …, g_{k}m_{k}).

Next we want to kill m_{3}. Present m_{3} as a balanced word in g_{2}, g_{3}m_{3}, …, g_{k}m_{k} conjugated by elements f_{i} ∈ G_{2}. Note that they all commute with g_{1}. As before,

m_{3} = w(g_{2}, g_{1}g_{3}m_{3}, g_{4}m_{4}, …, g_{k}m_{k})

(and, actually, m_{3} = w(g_{2}, y_{3}, …, y_{k}) where y_{i} are arbitrarily chosen from g_{i}m_{i} or g_{1}g_{i}m_{i}, i = 3, …, k.).

Thus we have:

(g_{1}, g_{2}, g_{3}m_{3}, …, g_{k}m_{k}) ∼ (g_{1}, g_{2}, g_{1}g_{3}m_{3}, g_{4}m_{4}, …, g_{1}g_{k}m_{k})
∼ (g_{1}m_{3}, g_{2}, g_{1}g_{3}m_{3}, g_{4}m_{4}, …, g_{k}m_{k})
∼ (g_{1}m_{3}, g_{2}, g_{3}, g_{4}m_{4}, …, g_{k}m_{k})
∼ (g_{1}, g_{2}, g_{3}, g_{4}m_{4}, …, g_{k}m_{k})

(the last transformation uses the fact that gp_{G}(g_{2}, g_{3}, g_{4}m_{4}, …, g_{k}m_{k}) = G_{2} by Claims 1.4 and 1.2).

One can easily observe that we can continue this argument in a similar way until we come to (g_{1}, g_{2}, …, g_{k}) - contradiction, which completes the proof of the claim. □

Claim 4.

[G_{1}, G_{1}] = 1.

Let [G_{1}, G_{1}] ≠ 1. For a proof, take a minimal non-trivial normal subgroup M of G which lies in [G_{1}, G_{1}]. Again, by Claim 1.3, we conclude that

(h_{1}, …, h_{k}) ∼ (g_{1}m_{1}, g_{2}m_{2}, …, g_{k}m_{k})

for some m_{1}, …, m_{k} ∈ M. We assume first that M ⩽ gp_{G}(g_{1}m_{1}). Then

(g_{1}m_{1}, g_{2}m_{2} …, g_{k}m_{k}) ∼ (g_{1}m_{1}, g_{2}, …, g_{k})

and gp_{G}(g_{1}m_{1}) = gp_{G}(g_{1}) by Claims 1.4 and 1.1. In particular,

M ⩽ [gp_{G}(g_{1}m_{1}), gp_{G}(g_{1}m_{1})] = [gp_{G}(g_{2}g_{1}m_{1}), gp_{G}(g_{2}g_{1}m_{1})],

where the last equality follows from the observation that g_{2} ∈ Z(G). We shall use this in further transformations:

(g_{1}m_{1}, g_{2}, …, g_{k}) ∼ (g_{1}m_{1}, g_{2}g_{1}m_{1}, g_{3}, …, g_{k})
∼ (g_{1}, g_{2}g_{1}m_{1}, g_{3}, …, g_{k})
∼ (g_{1}, g_{2}, g_{3}, …, g_{k}).

This shows that (h_{1}, …, h_{k}) ∼ (g_{1}, …, g_{k}) - contradiction. Therefore we can assume that M ⊈ gp_{G}(g_{1}m_{1}) and hence M ∩ gp_{G}(g_{1}m_{1}) = 1. We claim that not all of the elements m_{2}, …, m_{k}, are trivial. Otherwise

(h_{1}, …, h_{k}) ∼ (g_{1}m_{1}, g_{2}, …, g_{k}),

and we can repeat the previous argument and come to a contradiction. So we assume, with out loss of generality, that m_{2} ≠ 1.

If M is non-abelian then

M = [M, M] = [gp_{G}(m_{2}), gp_{G}(m_{2})] = [gp_{G}(g_{2}m_{2}), gp_{G}(g_{2}m_{2})]

and

(g_{1}m_{1}, g_{2}m_{2}, g_{3}m_{3}, …, g_{k}m_{k}) ∼ (g_{1}, g_{2}m_{2}, g_{3}m_{3}, …, g_{k}m_{k})
∼ (g_{1}, g_{2}, g_{3}, …, g_{k});

we use in the last transformation that gp_{G}(g_{1}) = G_{1} ⩾ M.

Therefore we can assume that M is abelian. Since M ∩ gp_{G}(g_{1}m_{1}) = 1 we conclude that [M, gp_{G}(g_{1}m_{1})] = 1. But then [M, gp_{G}(g_{1})] = 1. In particular, M ⩽ Z(G) and the subgroup [gp_{G}(g_{1}m_{1}), gp_{G}(g_{1}m_{1})] = [gp_{G}(g_{1}), gp_{G}(g_{1})] contains M. But this is a contradiction with M ∩ gp_{G}(g_{1}m_{1}) = 1. This proves the claim. □

Final contradiction. Claims 3 and 4 now yield that G is abelian, as required. □ □

References

[1] S. Akbut and R. Kirby, ‘A potential smooth counterexample in dimension 4 to the Poincare conjecture, the Schoenflies conjecture, and the Andrews-Curtis conjecture’, Topology 24 (1985), 375–390.

[2] J. J. Andrews and M. L. Curtis, ‘Free groups and handlebodies’, Proc. Amer. Math. Soc. 16 (1965), 192–195.

[3] L. Bartholdi, R. I. Grigorchuk and Z. Sunik, ‘Branch groups’, in Handbook of Algebra, vol. 3 (M. Hazelwinkel, ed.), 2003.

[4] A. V. Borovik, ‘Centralisers of involutions in black box groups’, Computational and Statistical Group Theory (R. Gilman et al., eds.), Contemporary Mathematics 298 (2002), 7–20; math.GR/0110233.

[5] A. V. Borovik, E. I. Khukhro, A. G. Myasnikov, ‘The Andrews-Curtis Conjecture and black box groups’, to appear in Int. J. Algebra and Computation.

[6] F. Celler, C. Leedham-Green, S. Murray, A. Niemeyer and E. O’Brien, ‘Generating random elements of a finite group’, Comm. Algebra 23 (1995), 4931–4948.

[7] P. Diaconis and R. Graham, ‘The graph of generating sets of an abelian group’, Colloq. Math. 80 (1999), 31–38.

[8] R. I. Grigorchuk,‘Degrees of growth of finitely generated groups and the theory of invariant means’, Math. USSR – Izv. 25, 2 (1985), 259–300.

[9] R. I. Grigorchuk, ‘Just infinite branch groups’, in New Horizons in pro-p-groups (M. P. F. du Sautoy, D. Segal and A. Shalev, eds.), Birkhäuser, Boston, 2000, 121–179.

[10] W. Kantor and A. Seress, ‘Black box classical groups’, Memoirs Amer. Math. Soc. 149, No. 708, Amer. Math. Soc., Providence, RI, 2000.

[11] D. A. Kazhdan, ‘On the connection of the dual space of a group with the structure of its closed subgroups’, Funkcional. Anal. i Prilozh. 1 (1967), 71–74.

[12] C. R. Leedham-Green and S. H. Murray, ‘Variants of product replacement’, Computational and statistical group theory (R. Gilman et al., eds.), Contemp. Math., 298 (2002), 97–104.

[13] Y. G. Leonov, ‘The conjugacy problem in a class of 2-groups’, Mat. Zametki 64 4 (1998), 573—583.

[14] A. Lubotzky and I. Pak, ‘The product replacement algorithm and Kazhdan’s property (T)’, J. Amer. Math. Soc. 14 (2001), 347–363.

[15] A. G. Myasnikov, ‘Extended Nielsen transformations and the trivial group’, Math. Notes 35 (1984) no. 3–4, 258–261.

[16] B. H. Neumann and H. Neumann, ‘Zwei Klassen characteristischer Untergruppen und ihre Faktorgruppen’, Math. Nachr. 4 (1951), 106-125.

[17] I. Pak, ‘What do we know about the product replacement algorithm’, in Groups and Computation III (W. Kantor and A. Seress, eds.), DeGruyter, Berlin, 2001, pp. 301–348.

[18] A. V. Rozhkov, ‘The conjugacy problem in an automorphism group of an infinite tree’, Mat. Zametki 64 4 (1998), 592–597.

Alexandre V. Borovik, Department of Mathematics, UMIST, PO Box 88, Manchester M60

1QD, United Kingdom; borovik@umist.ac.uk; http://www.ma.umist.ac.uk/avb/

Alexander Lubotzky, Department of Mathematics, Hebrew University, Givat Ram, Jerusalem

91904, Israel; alexlub@math.huji.ac.il

Alexei G. Myasnikov, Department of Mathematics, The City College of New York, New

York, NY 10031, USA; alexeim@att.net; http://home.att.net/~alexeim/index.htm