## New York Journal of Mathematics

New York J. Math.22(2016) 379–404.

## Cross-wired lamplighter groups and linearity of automata groups

### Ning Yang

Abstract. We consider the two generalizations of lamplighter groups:

automata groups generated by Cayley machines and cross-wired lamp- lighter groups. For a finite step two nilpotent group with central squares, we study its associated Cayley machine and give a presentation of the corresponding automata group. We show the automata group is a cross- wired lamplighter group and does not embed in the wreath product of a finite group with a torsion free group. For a subfamily of such finite step two nilpotent groups, we prove that their associated automata groups are linear.

Contents

1. Introduction 379

2. Automata groups 382

2.1. Preliminaries: automata and Cayley machine 382

2.2. Proof of Theorem 1.1 384

2.3. Nonembedding into wreath products 391

3. Cross-wired lamplighter groups 392

3.1. Proof of Theorem 1.4 392

4. Linearity of automata groups 394

4.1. Notations 394

4.2. Linearity of G(C(Q_{8})) 395

4.3. Linearity of G(C(M_{2}^{n})) 399

References 402

1. Introduction

The so called lamplighter group is a popular object of study. It is de-
fined as a restricted wreath product Z2 oZ, namely a semi-direct product
(⊕_{Z}Z2)o Z with the action of Zon ⊕_{Z}Z2 by shifts, whereZ denotes inte-
gers and Z2 denotesZ/2Z. It is an infinitely presented 2-generated group.

Received December 10, 2015.

2010Mathematics Subject Classification. 20E08, 20E22, 20G15.

Key words and phrases. automata groups, Cayley machine, cross-wired lamplighter groups, wreath products, linearity.

ISSN 1076-9803/2016

379

NING YANG

It is step-2 solvable and has exponential growth. In general, a lamplighter group could be a group of the form F oZ where F is some nontrivial fi- nite group. There are two kinds of generalization of lamplighter groups:

automata groups generated by Cayley machines [11, 17] and cross-wired lamplighter groups [2].

Grigorchuk and ˙Zuk [11] showed that the lamplighter group Z2 oZ can be constructed as the automata group of a 2-state automaton. They used this automaton to compute the spectrum and spectral measure associated to random walks on the group, leading to a counterexample of the strong form of the Atiyah conjecture. Silva and Steinberg [17] showed that, for a finite abelian group F, the lamplighter group F oZ can be generated by a reset automaton, which they called the Cayley machine of the group F.

Woryna [24] showed similar results for automata over changing alphabet.

Pochon [15] first studied the Cayley machine of a finite nonabelian group around 2005. She gave the structure of the group generated by the Cayley machine of the Dihedral group of order 8. We extend her unpublished result to a large class of groups.

Theorem 1.1. Let G be a finite step-2 nilpotent group. Assume the square of each element of G is central. Then the automata group generated by its Cayley machine has following presentation:

hG, x|[g, x^{2n}hx^{−2n}] = [g, x^{2n−1}hx^{−2n+1}] =x^{n}[g, h]x^{−n}, g, h∈G, n∈Zi,
where the bracket denotes group commutator.

Thus, the theorem of Silva and Steinberg for the case of finite abelian groups is a corollary of Theorem 1.1. For a finite nonabelian group F, FoZcan not be an automata group. Indeed, for such finite groupF,FoZis residually finite if and only ifF is abelian [12]. On the other hand, automata groups are always residually finite [10]. Silva and Steinberg conjectured that in the case of finite nonabelian group, the resulting automata group does not embed in the wreath product of a finite group with a torsion free group.

In the appendix of [13], Kambites, Silva and Steinberg partially proved the conjecture. They showed for any finite nonabelian group that is not a direct product of an abelian group with a 2-group which is nilpotent of class 2, its associated automata group can not embed in a wreath product of a finite group with a torsion free group. We show the case when it contains a 2-group which is nilpotent of class 2.

Theorem 1.2. LetGbe a finite nonabelian group containing a2-group that is nilpotent of class 2. Then the automata group generated by its Cayley machine does not embed in a wreath product of a finite group with a torsion free group.

Combining results in the appendix of [13], we have:

Theorem 1.3. The automata group associated to any finite nonabelian group does not embed in a wreath product of a finite group with a torsion free group.

Some Cayley graphs of lamplighter groups are examples of Diestel–Leader graphs [3, 14, 22, 23]. Eskin, Fisher, and Whyte proved [6, 7, 8] that a finitely generated group is quasi-isometric to a lamplighter group if and only if it acts properly and cocompactly by isometries on some Diestel–Leader graph. In [2], Cornulier, Fisher and Kashyap studied quasi-isometric rigidity question of lamplighter groups by studying the cocompact lattices in the isometry group of the Diestel–Leader graphs. They showed that these lattices are not necessarily lamplighters and gave an algebraic characterization of them.

They call these cocompact lattices cross-wired lamplighter groups. Lamp- lighter groups are examples of cross-wired lamplighters. It is suggested by L. Bartholdi that automata groups associated to some finite groups might provide other examples of cross-wired lamplighter groups. We show that the automata groups in Theorem 1.1 are cross-wired lamplighter groups.

Theorem 1.4. The automata groups in Theorem 1.1 are cross-wired lamp- lighter groups.

Cornulier, Fisher and Kashyap also give interesting examples that are not
virtually lamplighter groups [2]. Let q be a prime power, and consider the
Laurent polynomial ringFq[t^{±1}]. LetHbe the Heisenberg group, consisting
of unitriangular 3×3 matrices. Consider the action of Z on H(Fq[t^{±1}])
defined by the automorphism

Φ :

1 x z 0 1 y 0 0 1

7→

1 tx t^{2}z
0 1 ty

0 0 1

.

Then the group H(Fq[t^{±1}])oΦ Z is a cross-wired lamplighter group. This
construction applies to other nilpotent groups over local field of positive
characteristic with similar contraction Z action. In the beginning, we be-
lieved that the automata groups in Theorem 1.1 might be totally different
examples of cross-wired lamplighters from those examples above, or even
nonlinear. By linear we mean the group can be embedded in a general
linear group over some fields. As we know, many automata groups are non-
linear. The Grigorchuk groups [9, 5] are automata groups, of intermediate
growth and hence nonlinear. But the lamplighter groupZ2oZis linear over
function fields [23]. So it is interesting to study the linearity/nonlinearity
of those automata groups above. We find the following surprising. Let
Q_{8} be the quaternion group of order 8 and M_{2}^{n} be the Iwasawa/modular
group of order 2^{n}, n ≥3, M2^{n} = ha, b |a^{2}^{n−1} =b^{2} =e, bab^{−1} =a^{2}^{n−2}^{+1}i.

The automata groups associated to Q8 andM2^{n} have index two subgroups
behaving like above linear examples with diagonal contraction Zaction.

NING YANG

Theorem 1.5. The automata groups associated to Q_{8} and M_{2}^{n} are linear
over Z2[t^{±1}].

Acknowledgments. The author would like to express his deep gratitude to his advisor, Professor David Fisher, for consistent support, enlighten- ing guidance and encouragement. He is grateful to Laurent Bartholdi and Michael Larsen for their interests and inspiring discussions. He thanks Yves de Cornulier for comments on an early draft of this paper. He also want to thank the anonymous referee for many helpful suggestions and corrections.

2. Automata groups

2.1. Preliminaries: automata and Cayley machine. This subsection is similar with part of [13].

A finite (Mealy) automaton [4, 10, 13, 17] A is a 4-tuple (Q, A, δ, λ),
whereQis a finite set of states,A is a finite alphabet,δ :Q×A→Qis the
transition function and λ:Q×A→Ais the output function. We write qa
for δ(q, a) andq◦a for λ(q, a). Let A^{∗} be the set of all words in letters of
A. These functions extend to the free monoid A^{∗} by

q(ab) = (qa)b,

q◦(ab) = (q◦a)(qa)◦b.

(2.1)

LetA_{q}denote theinitial automaton Awith designated start stateq∈Q.

There is a functionA_{q}:A^{∗}→A^{∗} given byw7→q◦w. This function is word
length preserving and extends continuously [10] to the set of right infinite
words A^{ω} via

(2.2) A_{q}(a0a1· · ·) = lim

n→∞A_{q}(a0· · ·an),

where A^{ω} is given the product topology and so homeomorphic to a Cantor
set. If the function λq :A→ A, defined by λq(a) =q◦a, is a permutation
for each q, then A_{q} is an isometry of A^{ω} with metric d(u, v) = 1/(n+ 1),
where nis the length of the longest common prefix of u and v [10]. In this
case the automaton is called invertible and its inverse is dented by A^{−1}.
Let Γ =G(A), Ainvertible, be the group generated by allA_{q}’s with q∈Q,
and it is called theautomata group generated by automaton A.

LetT be the Cayley tree ofA^{∗}, then Γ acts onT by rooted tree automor-
phisms [10] via the action (2.1). The induced action on the boundary ∂T,
the space of infinite directed paths from the root, is the action (2.2) of Γ on
A^{ω}. Let Aut(T) be the automorphism group of T. It is the iterated permu-
tational wreath product of countably many copies of the left permutation
group (SA, A) [1, 10, 16], where SA is the symmetric group on A. For a
group Γ =G(A) generated by an automaton overA, one has the embedding
(2.3) (Γ, A^{ω}),→(S|A|, A)o(Γ, A^{ω}).

Here we use the notation such that the wreath product of left permutation
groups has a natural projection to its leftmost factor. LetA={a_{1}, . . . , an}.

In wreath product coordinates, an element in the automata group can be
represented as σ(f1, . . . , fn), where σ ∈ SA and f1, . . . , fn ∈ Γ. It acts on
the word a_{i}x_{2}x_{3}. . . overA by the rule

σ(f1, . . . , fn)(aix2x3. . .) =σ(ai)fi(x2x3. . .).

Multiplication in wreath product coordinates is given by
(2.4) σ(f_{1}, . . . , f_{n})τ(g_{1}, . . . , g_{n}) =στ(f_{τ(1)}g_{1}, . . . , f_{τ(n)}g_{n}),

where σ, τ ∈ SA∼=S{1,2,...,n} and f1, . . . , fn, g1, . . . , gn∈Γ. The map sends
A_{q} to the element with wreath product coordinates:

A_{q}=λq(A_{qa}_{1}, . . . ,A_{qa}_{n}).

Its inverse is given by

A^{−1}_{q} =λ^{−1}_{q} (A^{−1}_{a}

1, . . . ,A^{−1}_{a}

n).

Let G={g_{1} = 1, g_{2}, . . . , g_{n}} be a nontrivial finite group. By the Cayley
machine C(G) of G we mean the automaton with stateG and alphabet G.

Both the transition and the output functions are the group multiplication, i.e., at state g0 on input g the machine goes to state g0g and outputs g0g.

The state functionλ_{g}is just left translation bygand hence a permutation, so
C(G) is invertible. The study of the automata group of the Cayley machine
of a finite group was initiated by Silva and Steinberg [17].

An automaton is called a reset automaton if, for each a ∈ A, |Qa| = 1;

that is, each input resets the automaton to a single state. Silva and Steinberg
[17] showed that the inverse of a state C(G)_{g}, g ∈ G, is computed by the
corresponding state of the reset automaton A(G) with states and input
alphabetG, where at stateg_{0} on input gthe automaton goes to stateg and
outputsg^{−1}_{0} g. Therefore

C(G)^{−1}_{g} =A(G)_{g}, G(C(G)) =G(A(G)).

In this case, from (2.3), we have the embedding

G(A(G)),→(G, G)o(G(A(G)), G^{ω}).

In wreath product coordinates,

(2.5) A(G)_{g}=g^{−1}(A_{g}_{1}, . . . ,A_{g}_{n}).

Letx:=A(G)_{1}=C(G)^{−1}_{1} . Notice that [17], applying (2.4),
xA(G)^{−1}_{g} =xC(G)_{g}

= (A_{g}_{1}, . . . ,A_{g}_{n})g(C(G)_{gg}_{1}. . . ,C(G)_{gg}_{n})

=g(A_{gg}_{1}C(G)_{gg}_{1}, . . . ,A_{gg}_{n}C(G)_{gg}_{n})

=g(1, . . . ,1),

so we can identifyGwith a subgroup of G(A(G)) via g↔xA(G)^{−1}_{g} . Recall
from [17] Equation 4.3 or by (2.5) that

x(f0, f1, f2, f3, f4, . . .) = (f0, f_{0}^{−1}f1, f_{1}^{−1}f2, f_{2}^{−1}f3, f_{3}^{−1}f4, . . .),

NING YANG

x^{−1}(f_{0}, f_{1}, f_{2}, f_{3}, f_{4}, . . .) = (f_{0}, f_{0}f_{1}, f_{0}f_{1}f_{2}, f_{0}f_{1}f_{2}f_{3}, f_{0}f_{1}f_{2}f_{3}f_{4}, . . .),
where (f0, f1, f2, f3, f4, . . .)∈G^{ω}.

Let

N :=hx^{n}Gx^{−n}|n∈Zi.

It is shown in [17] that x has infinite order, N is a locally finite group and G(A(G)) =Nohxi, wherexacts on N by conjugates. If Gis abelian, it is shown in [17] that

G(A(G))∼=GoZ.

That is the automata group is a lamplighter group. If G is nonabelian and not of nilpotency class 2, then G(A(G)) does not embed in the wreath product of a finite group with a torsion free group.

Thedepth of an elementγ ∈Γ is the least integern(if it exists, otherwise infinity) so that γ only changes the first n letters of a word. For example, g∈G has depth 1. Here is a useful lemma about depth:

Lemma 2.1. [17] LetA= (Q, A, δ, λ) be an invertible reset automaton and
let a = A_{p}, b = A_{q}. Suppose f ∈ Γ has depth n, then af b^{−1} has depth at
most n+ 1.

Let

N0 :=hx^{n}Gx^{−n}|n≥0i.

It is shown in [17] that x^{n}gx^{−n}, g 6= 1, has depth n+ 1 and soN_{0} consists
of finitary automorphisms. It is shown in [17] that the elements of the form
A(G)_{g}∈Γ with g∈G generate a free subsemigroup of Γ.

2.2. Proof of Theorem 1.1. Let

G={g_{1}= 1, g_{2}, . . . , g_{k}}

be a group of nilpotency class two, for some k ∈ N. Moreover we assume
g^{2}_{i} = gigi is central in G for each i,1 ≤ i ≤ k. The dihedral group D8 of
order 8 and the quaternion groupQ_{8} are examples of suchG.

Note that every finite group of nilpotency class two is obtained by tak- ing direct products of finite groups of prime power order and class two.

Therefore, Gmust be a 2-group direct product with abelian factors.

LetC(G) be the Cayley machine ofG, thenG(C(G)) is generated by
{C(G)_{g}_{1},C(G)_{g}_{2}, . . . ,C(G)_{g}_{k}}.

Letx=C(G)^{−1}_{g}

1 .Then by (2.5), in wreath product coordinates, x= 1

C(G)^{−1}_{g}

1 ,C(G)^{−1}_{g}

2 , . . . ,C(G)^{−1}_{g}

k

.

It has infinite order. IdentifyingGwith a subgroup ofC(G) viag7→xC(G)_{g},
then we have

(2.6) C(G)_{g} =x^{−1}g, C(G)^{−1}_{g} =g^{−1}x.

Therefore, for any g, h∈G,

(2.7) C(G)^{−1}_{g} C(G)_{h} =g^{−1}xx^{−1}h=g^{−1}h.

From previous subsection, x^{n}gx^{−n} has depth n+ 1 for n≥ 0. Also, we
have

x^{n}gx^{−n}=C(G)^{−n}_{g}

1 gC(G)^{n}_{g}

1

= (C(G)^{−n}_{g}_{1} , . . . ,C(G)^{−n}_{g}

k )g(1, . . . ,1)(C(G)^{n}_{g}_{1}, . . . ,C(G)^{n}_{g}

k)

= (C(G)^{−n}_{g}_{1} , . . . ,C(G)^{−n}_{g}

k )g(C(G)^{n}_{g}_{1}, . . . ,C(G)^{n}_{g}

k)

=g

C(G)^{−n}_{gg}

1C(G)^{n}_{g}

1, C(G)^{−n}_{gg}

2C(G)^{n}_{g}

2, . . . , C(G)^{−n}_{gg}

kC(G)^{n}_{g}

k

=g
C_{gg}^{−n}

1C_{g}^{n}

1, C_{gg}^{−n}

2C_{g}^{n}

2, . . . , C_{gg}^{−n}

kC_{g}^{n}

k

,

where in the last step, we write C as C(G) for simplicity. We will keep on using this notation.

LetN =hx^{n}gx^{−n}|n∈Z, g∈Gi,then G(C(G)) =Nohxi, wherex acts
on N by conjugates. We show the following key lemma.

Lemma 2.2. For any n≥0, anyf, g, h∈G,

x^{n}gx^{−n}h=hx^{[}^{n}^{2}^{]}[h, g^{−1}]x^{−[}^{n}^{2}^{]}x^{n}gx^{−n},
hx^{n}gx^{−n}=x^{n}gx^{−n}x^{[}^{n}^{2}^{]}[g, h^{−1}]x^{−[}^{n}^{2}^{]}h,

and x^{l}[g, h]x^{−l} commutes with x^{m}f x^{−m} as long as n≥l, m≥0, where [^{n}_{2}]
denotes the least integer greater than or equal to ^{n}_{2}.

Proof. The proof is by induction.

The case of n= 0 is trivial: gh=h[h, g^{−1}]g.

Letn= 1. Then
xgx^{−1}h=g

C_{gg}^{−1}

1C_{g}_{1}, C_{gg}^{−1}

2C_{g}_{2}, . . . , C_{gg}^{−1}

kC_{g}_{k}

h(1, . . . ,1)

=gh

C_{ghg}^{−1}

1C_{hg}_{1}, C_{ghg}^{−1}

2C_{hg}_{2}, . . . , C_{ghg}^{−1}

kC_{hg}_{k}
,
and

hx[h, g^{−1}]x^{−1}xgx^{−1}=hxh^{−1}ghx^{−1}

=h(1, . . . ,1)h^{−1}gh

C_{h}^{−1}−1ghg1C_{g}_{1}, C_{h}^{−1}−1ghg2C_{g}_{2}, . . . , C_{h}^{−1}−1ghgkC_{g}_{k}

=gh
C_{h}^{−1}_{−1}_{ghg}

1C_{g}_{1}, C_{h}^{−1}_{−1}_{ghg}

2C_{g}_{2}, . . . , C_{h}^{−1}_{−1}_{ghg}

kC_{g}_{k}
.
Applying (2.6) and (2.7) we then have, for any f ∈G,

C_{ghf}^{−1} C_{hf} =f^{−1}h^{−1}g^{−1}hf =C_{h}^{−1}−1ghfC_{f}.

By comparing wreath product coordinates, xgx^{−1}h =hx[h, g^{−1}]x^{−1}xgx^{−1}.
Similarly we havehxgx^{−1}=xgx^{−1}x[g, h^{−1}]x^{−1}h.

Since G is of nilpotency class two, both [g, h] and x[g, h]x^{−1} commute
withf andxf x^{−1}, for anyg, h, f ∈G.

NING YANG

Letn= 2. Then we compute
x^{2}gx^{−2}h=g

C_{gg}^{−2}_{1}C_{g}^{2}_{1}, C_{gg}^{−2}_{2}C_{g}^{2}_{2}, . . . , C_{gg}^{−2}

kC_{g}^{2}

k

h(1, . . . ,1)

=gh
C_{ghg}^{−2}

1C_{hg}^{2}

1, C_{ghg}^{−2}

2C_{hg}^{2}

2, . . . , C^{−2}_{ghg}

kC_{hg}^{2}

k

, and

hx[h, g^{−1}]x^{−1}x^{2}gx^{−2}

=h(1, . . . ,1)[h, g^{−1}]

C_{h}^{−1}−1ghg^{−1}g1C_{g}_{1},C_{h}^{−1}−1ghg^{−1}g2C_{g}_{2}, . . . ,C_{h}^{−1}−1ghg^{−1}gkC_{g}_{k}

·g
C_{gg}^{−2}

1C_{g}^{2}

1, C_{gg}^{−2}

2C_{g}^{2}

2, . . . , C_{gg}^{−2}

kC_{g}^{2}

k

=ghg^{−1}

C_{h}^{−1}_{−1}_{ghg}_{−1}_{g}

1C_{g}_{1},C_{h}^{−1}_{−1}_{ghg}_{−1}_{g}

2C_{g}_{2}, . . . ,C_{h}^{−1}_{−1}_{ghg}_{−1}_{g}

kC_{g}_{k}

·g

C_{gg}^{−2}

1C_{g}^{2}

1, C_{gg}^{−2}

2C_{g}^{2}

2, . . . , C_{gg}^{−2}

kC_{g}^{2}

k

=gh

C_{h}^{−1}−1ghg1C_{gg}_{1}C_{gg}^{−2}

1C^{2}_{g}

1, C_{h}^{−1}−1ghg2C_{gg}_{2}C_{gg}^{−2}

2C_{g}^{2}

2, . . . , C_{h}^{−1}−1ghgkC_{gg}_{k}C_{gg}^{−2}

kC_{g}^{2}

k

. For anyf ∈G, applying (2.7) we compute

C_{ghf}^{−2}C_{hf}^{2} =C_{ghf}^{−1}f^{−1}h^{−1}g^{−1}hfC_{hf}

=f^{−1}h^{−1}g^{−1}(xf^{−1}h^{−1}g^{−1}hf x^{−1}hf)

=f^{−1}h^{−1}g^{−1}hf xg^{−1}x^{−1},
and

C_{h}^{−1}_{−1}_{ghf}C_{gf}C_{gf}^{−2}C_{f}^{2} = (h^{−1}ghf)^{−1}gf

f^{−1}g^{−1}f xg^{−1}x^{−1}

=f^{−1}h^{−1}g^{−1}hf xg^{−1}x^{−1} =C_{ghf}^{−2}C_{hf}^{2} .

So, x^{2}gx^{−2}h=hx[h, g^{−1}]x^{−1}x^{2}gx^{−2}, since they have same wreath prod-
uct coordinates.

On the other hand, notice that

[h, g^{−1}][g, h^{−1}] =h^{−1}ghg^{−1}g^{−1}hgh^{−1}=h^{−1}gg^{−1}hgh^{−1}hg^{−1}= 1,
then we have

hx^{2}gx^{−2}=hx^{2}gx^{−2}x[h, g^{−1}]x^{−1}x[g, h^{−1}]x^{−1}

=hxxgx^{−1}[h, g^{−1}]x^{−1}x[g, h^{−1}]x^{−1}

=hx[h, g^{−1}]xgx^{−1}x^{−1}x[g, h^{−1}]x^{−1}

=hx[h, g^{−1}]x^{−1}x^{2}gx^{−2}x[g, h^{−1}]x^{−1}

=x^{2}gx^{−2}hx[g, h^{−1}]x^{−1} =x^{2}gx^{−2}x[g, h^{−1}]x^{−1}h.

SinceGis of nilpotency class two, thenx^{2}[g, h]x^{−2} commutes withf and
x^{2}f x^{−2}, for anyg, h, f ∈G. Also we have

x^{2}[g, h]x^{−2}xf x^{−1}=xx[g, h]x^{−1}f x^{−1}

=xf x[g, h]x^{−1}x^{−1}

=xf x^{−1}x^{2}[g, h]x^{−2}.

Similarly, [g, h] and x[g, h]x^{−1} commute with f, xf x^{−1} and x^{2}f x^{−2}, for any
g, h, f ∈G. Then we proved the lemma for the case ofn= 2.

Now we assume the lemma is true for all m ≤ 2n, we need to show the cases of 2n+ 1 and 2n+ 2.

Applying (2.7), we have
x^{2n+1}gx^{−2n−1}h

=g
C_{gg}^{−2n−1}

1 C_{g}^{2n+1}

1 , C_{gg}^{−2n−1}

2 C_{g}^{2n+1}

2 , . . . , C_{gg}^{−2n−1}

k C_{g}^{2n+1}

k

h(1, . . . ,1)

=gh
C_{ghg}^{−2n−1}

1 C_{hg}^{2n+1}

1 , C_{ghg}^{−2n−1}

2 C_{hg}^{2n+1}

2 , . . . , C_{ghg}^{−2n−1}

k C_{hg}^{2n+1}

k

,
and similarly x^{2n}gx^{−2n}h=gh

C_{ghg}^{−2n}

1C_{hg}^{2n}

1, C_{ghg}^{−2n}

2C_{hg}^{2n}

2, . . . , C_{ghg}^{−2n}

kC_{hg}^{2n}

k

. On the other hand, we compute

hx^{n+1}[h, g^{−1}]x^{−n−1}x^{2n+1}gx^{−2n−1}

=h[h, g^{−1}]
C^{−n−1}

[h,g^{−1}]g1C_{g}^{n+1}

1 , C^{−n−1}

[h,g^{−1}]g2C_{g}^{n+1}

2 , . . . , C^{−n−1}

[h,g^{−1}]gkC_{g}^{n+1}

k

g
C_{gg}^{−2n−1}

1 C_{g}^{2n+1}

1 , C_{gg}^{−2n−1}

2 C_{g}^{2n+1}

2 , . . . , C_{gg}^{−2n−1}

k C_{g}^{2n+1}

k

=gh

C_{[h,g}^{−n−1}−1]gg1C^{n+1}_{gg}

1 C_{gg}^{−2n−1}

1 C_{g}^{2n+1}

1 , C_{[h,g}^{−n−1}−1]gg2C_{gg}^{n+1}

2 C_{gg}^{−2n−1}

2 C_{g}^{2n+1}

2 ,

. . . , C_{[h,g}^{−n−1}−1]ggkC_{gg}^{n+1}

k C_{gg}^{−2n−1}

k C_{g}^{2n+1}

k

=gh

C_{[h,g}^{−n−1}−1]gg1C^{−n}_{gg}_{1}C_{g}^{2n+1}_{1} , C_{[h,g}^{−n−1}−1]gg2C_{gg}^{−n}_{2}C_{g}^{2n+1}_{2} , . . . , C_{[h,g}^{−n−1}−1]ggkC_{gg}^{−n}

kC_{g}^{2n+1}

k

, and similarly

hx^{n}[h, g^{−1}]x^{−n}x^{2n}gx^{−2n}

=gh

C^{−n}_{[h,g}−1]gg1C_{gg}^{−n}

1C_{g}^{2n}

1, C_{[h,g}^{−n}−1]gg2C_{gg}^{−n}

2C^{2n}_{g}

2, . . . , C_{[h,g}^{−n}−1]ggkC_{gg}^{−n}

kC_{g}^{2n}

k

. Note that, by inductive hypothesis and comparing wreath product coor- dinates, we have, for anyf ∈G,

C_{ghf}^{−2n}C_{hf}^{2n}=C_{[h,g}^{−n}_{−1}_{]gf}C_{gf}^{−n}C_{f}^{2n}.

Then, applying (2.6) and (2.7), for any f ∈G, we compute
C_{ghf}^{−2n−1}C_{hf}^{2n+1}

=C_{ghf}^{−1}C_{[h,g}^{−n}−1]gfC_{gf}^{−n}C_{f}^{2n}C_{hf}

= (ghf)^{−1}x ([h, g^{−1}]gf)^{−1}xn

(gf)^{−1}xn−1

·f^{−1}g^{−1}f x^{−1}f2n−1

x^{−1}hf

NING YANG

= (ghf)^{−1}

n

Y

l=1

x^{l}([h, g^{−1}]gf)^{−1}x^{−l}

! _{2n−1}
Y

l=n+1

x^{l}(gf)^{−1}x^{−l}

!

·x^{2n}f^{−1}g^{−1}f x^{−2n}

2n−1

Y

l=1

x^{l}f x^{−l}

! hf

= (ghf)^{−1}h

n

Y

l=1

x^{l}([h, g^{−1}]gf)^{−1}x^{−l}

! _{2n−1}
Y

l=n+1

x^{l}(gf)^{−1}x^{−l}

!

·x^{2n}f^{−1}g^{−1}f x^{−2n}

2n−1

Y

l=1

x^{l}f x^{−l}

! f

n−1

Y

l=1

x^{l}[gf, h]^{2}x^{−l}

!

·x^{n}[gf, h][f^{−1}g^{−1}f, h][f, h]x^{−n}

n−1

Y

l=1

x^{l}[f, h]^{2}x^{−l}

!

= (ghf)^{−1}h

n

Y

l=1

x^{l}([h, g^{−1}]gf)^{−1}x^{−l}

! _{2n−1}
Y

l=n+1

x^{l}(gf)^{−1}x^{−l}

!

·x^{2n}f^{−1}g^{−1}f x^{−2n}

2n−1

Y

l=1

x^{l}f x^{−l}

! f

= ([h, g^{−1}]gf)^{−1}x ([h, g^{−1}]gf)^{−1}xn

(gf)^{−1}xn−1

·f^{−1}g^{−1}f x^{−1}f2n−1

x^{−1}f,

where [gf, h][f^{−1}g^{−1}f, h][f, h] = 1 follows from direct calculation. Also we
have

C^{−n−1}

[h,g^{−1}]gfC_{gf}^{−n}C_{f}^{2n+1}

= ([h, g^{−1}]gf)^{−1}xn+1

(gf)^{−1}xn−1

f^{−1}g^{−1}f x^{−1}f2n

= ([h, g^{−1}]gf)^{−1}x ([h, g^{−1}]gf)^{−1}xn

(gf)^{−1}xn−1

f^{−1}g^{−1}f x^{−1}f2n−1

x^{−1}f.

Thus we get

(2.8) C_{ghf}^{−2n−1}C_{hf}^{2n+1}=C_{[h,g}^{−n−1}−1]gfC_{gf}^{−n}C_{f}^{2n+1}.
So, by comparing wreath product coordinates, we obtain

x^{2n+1}gx^{−2n−1}h=hx^{n+1}[h, g^{−1}]x^{−n−1}x^{2n+1}gx^{−2n−1}.
On the other hand, by commutativity we have

hx^{2n+1}gx^{−2n−1} =hx^{2n+1}gx^{−2n−1}x^{n+1}[h, g^{−1}]x^{−n−1}x^{n+1}[g, h^{−1}]x^{−n−1}

=hx^{n+1}[h, g^{−1}]x^{n}gx^{−n}x^{−n−1}x^{n+1}[g, h^{−1}]x^{−n−1}

=x^{2n+1}gx^{−2n−1}hx^{n+1}[g, h^{−1}]x^{−n−1}

=x^{2n+1}gx^{−2n−1}x^{n+1}[g, h^{−1}]x^{−n−1}h.

For any f, g, h ∈ G, 0 ≤ m ≤ 2n+ 1, the commutativity of x^{m}f x^{−m}
with x^{2n+1}[g, h]x^{−2n−1} and of x^{m}[g, h]x^{m} with x^{2n+1}f x^{−2n−1} follow from
the same trick. So we proved the case of 2n+ 1.

Now we prove the case of 2n+ 2. By previous calculation, we have
x^{2n+2}gx^{−2n−2}h=gh

C_{ghg}^{−2n−2}

1 C_{hg}^{2n+2}

1 , C_{ghg}^{−2n−2}

2 C_{hg}^{2n+2}

2 , . . . , C_{ghg}^{−2n−2}

k C_{hg}^{2n+2}

k

, and

hx^{n+1}[h, g^{−1}]x^{−n−1}x^{2n+2}gx^{−2n−2}

=gh

C_{[h,g}^{−n−1}_{−1}_{]gg}

1C_{gg}^{−n−1}

1 C_{g}^{2n+2}

1 , C_{[h,g}^{−n−1}_{−1}_{]gg}

2C_{gg}^{−n−1}

2 C_{g}^{2n+2}

2 ,

. . . ,C_{[h,g}^{−n−1}−1]ggkC_{gg}^{−n−1}

k C_{g}^{2n+2}

k

.

Again we compare wreath product coordinates. Applying (2.8) and (2.7), for any f ∈G,

C_{ghf}^{−2n−2}C_{hf}^{2n+2} =C^{−1}_{ghf}C_{ghf}^{−2n−1}C_{hf}^{2n+1}C_{hf} =C_{ghf}^{−1}C_{[h,g}^{−n−1}−1]gfC_{gf}^{−n}C_{f}^{2n+1}C_{hf}

= (ghf)^{−1}x ([h, g^{−1}]gf)^{−1}xn+1

(gf)^{−1}xn−1

f^{−1}g^{−1}f x^{−1}f2n

x^{−1}hf

= (ghf)^{−1}

n+1

Y

l=1

x^{l}([h, g^{−1}]gf)^{−1}x^{−l}

! _{2n}
Y

l=n+2

x^{l}(gf)^{−1}x^{−l}

!

x^{2n+1}f^{−1}g^{−1}f

·x^{−2n−1}

2n

Y

l=1

x^{l}f x^{−l}

! hf

= (ghf)^{−1}h

n+1

Y

l=1

x^{l}([h, g^{−1}]gf)^{−1}x^{−l}

! _{2n}
Y

l=n+2

x^{l}(gf)^{−1}x^{−l}

!

x^{2n+1}f^{−1}g^{−1}f

·x^{−2n−1}

2n

Y

l=1

x^{l}f x^{−l}

! f

n

Y

l=1

x^{l}[gf, h][gf, h]x^{−l}

!

x^{n+1}[f^{−1}g^{−1}f, h]x^{−n−1}

·

n

Y

l=1

x^{l}[f, h][f, h]x^{−l}

!

= (ghf)^{−1}h

n

Y

l=1

x^{l}([h, g^{−1}]gf)^{−1}x^{−l}

!

x^{n+1}([h, g^{−1}]gf)^{−1}[f^{−1}g^{−1}f, h]x^{−n−1}

·

2n

Y

l=n+2

x^{l}(gf)^{−1}x^{−l}

!

x^{2n+1}f^{−1}g^{−1}f x^{−2n−1}

2n

Y

l=1

x^{l}f x^{−l}

! f.

On the other hand,
C_{[h,g}^{−n−1}−1]gfC_{gf}^{−n−1}C_{f}^{2n+2}

= ([h, g^{−1}]gf)^{−1}xn+1

(gf)^{−1}xn

f^{−1}g^{−1}f x^{−1}f2n+1

NING YANG

= (ghf)^{−1}h

n

Y

l=1

x^{l}([h, g^{−1}]gf)^{−1}x^{−l}

! _{2n}
Y

l=n+1

x^{l}(gf)^{−1}x^{−l}

!

x^{2n+1}f^{−1}g^{−1}f

·x^{−2n−1}

2n

Y

l=1

x^{l}f x^{−l}

! f.

Since ([h, g^{−1}]gf)^{−1}[f^{−1}g^{−1}f, h] = (gf)^{−1}, then

C_{ghf}^{−2n−2}C_{hf}^{2n+2}=C_{[h,g}^{−n−1}−1]gfC_{gf}^{−n−1}C_{f}^{2n+2},
and thus

x^{2n+2}gx^{−2n−2}h=hx^{n+1}[h, g^{−1}]x^{−n−1}x^{2n+2}gx^{−2n−2}.
Moreover, this implies

hx^{2n+2}gx^{−2n−2} =x^{2n+2}gx^{−2n−2}x^{n+1}[g, h^{−1}]x^{−n−1}h,
by the commutativity trick.

For any f, g, h ∈ G, 0 ≤ m ≤ 2n+ 2, the commutativity of x^{m}f x^{−m}
with x^{2n+2}[g, h]x^{−2n−2} and of x^{m}[g, h]x^{m} with x^{2n+2}f x^{−2n−2} follow from
nilpotency. So we prove the case of 2n+ 2 and hence the lemma.

Lemma 2.3. For any g, h∈ G, n, m∈Z, x^{n}[g, h]x^{−n} lies in the center of
N, and

x^{n}gx^{−n}x^{m}hx^{−m} =x^{m}hx^{−m}x^{[}^{n+m}^{2} ^{]}[h, g^{−1}]x^{−[}^{n+m}^{2} ^{]}x^{n}gx^{−n}.
Proof. We assume n≥m.

Letf ∈G. We compute

x^{n}[g, h]x^{−n}x^{m}f x^{−m}=x^{m}x^{n−m}[g, h]x^{m−n}f x^{−m}

=x^{m}f x^{n−m}[g, h]x^{m−n}x^{−m}

=x^{m}f x^{−m}x^{n}[g, h]x^{−n},
and

x^{n}gx^{−n}x^{m}hx^{−m} =x^{m}x^{n−m}gx^{m−n}hx^{−m}

=x^{m}hx^{[}^{n−m}^{2} ^{]}[h, g^{−1}]x^{−[}^{n−m}^{2} ^{]}x^{n−m}gx^{m−n}x^{−m}

=x^{m}hx^{−m}x^{[}^{n+m}^{2} ^{]}[h, g^{−1}]x^{−[}^{n+m}^{2} ^{]}x^{n}gx^{−n}

=x^{m}hx^{−m}x^{[}^{n+m}^{2} ^{]}[h, g^{−1}]x^{−[}^{n+m}^{2} ^{]}x^{n}gx^{−n}.

The case of n≤mis similar.

Lemma 2.4. Given any nontrivial torsion element γ ∈ G(C(G)), it can be written uniquely in the following form:

(2.9) γ =x^{i}^{1}f_{1}x^{−i}^{1}x^{i}^{2}f_{2}x^{−i}^{2}. . . x^{i}^{j}f_{j}x^{−i}^{j},

wherei_{1} < i_{2}<· · ·< i_{j} are integers,j≥1 andf_{1}, f_{2}, . . . , f_{j} ∈G\ {g_{1}= 1}.

Proof. Since γ is a product of conjugates by x of elements in G, by Lem- ma 2.3,γ can be written in the form of (2.9). So we only need to show the uniqueness.

Letγ =x^{i}^{1}f_{1}x^{−i}^{1}x^{i}^{2}f_{2}x^{−i}^{2}. . . x^{i}^{j}f_{j}x^{−i}^{j} = 1, wherei_{1}< i_{2} <· · ·< i_{j} and
f1, f2, . . . , fj ∈G. Then 1 =x^{−i}^{1}γx^{i}^{1} =f1x^{i}^{2}^{−i}^{1}f2x^{−i}^{2}^{+i}^{1}. . . x^{i}^{j}^{−i}^{1}fjx^{−i}^{j}^{+i}^{1}
has depth ij −i1+ 1 ≥1, if fj 6= 1. Hence, by an inductive argument, we
have f_{i}= 1,1≤i≤j. It completes the proof.

Proof of Theorem 1.1 . Note that [17]G(C(G)) =Nohxi and the iden- tities in Lemma 2.3 is equivalent to the relations in Theorem 1.1. Then the

theorem follows from Lemma 2.3 and Lemma 2.4.

In the end of [13], Kambites, Silva and Steinberg conjectured that the automata group associated to any finite nonabelian group can not have bounded torsion. The following corollary disproves the conjecture.

Corollary 2.5. Let G be a finite nilpotent group of class 2. Assume the square of each element of Gis central, then G(C(G))has bounded torsion.

Proof. Let|G|=k. Note that kis even. Letγ be a torsion element. Since
every commutator has order at most 2, then by Lemma 2.4 and Theorem 1.1
we have γ^{2k}= 1, i.e., the order of any torsion element is a factor of 2k.

2.3. Nonembedding into wreath products.

Lemma 2.6. Let Gbe a finite 2-group of nilpotency class 2. Then G has a subgroup H in which each square element is central in H.

Proof. By assumption on G, there exists a noncentral elementg∈G such
that g^{2} is central. Similarly, there exists h ∈ G so that it does not com-
mute withgbuth^{2} commutes withg. Then the subgroupHofGgenerated
by g and h is nilpotent of class 2. We show each square element in H is
central in H. Since g^{2} and h^{2} are central, it suffices to show for squares
of alternate products of g or g^{−1} with h orh^{−1}. Since g^{−1} =gg^{−1}g^{−1} and
h^{−1} =hh^{−1}h^{−1}, it reduces to squares of alternate products ofgwithh. Since
(ghg)^{2} =ghgghg =g^{4}h^{2}, by symmetry we only need to show that (gh)^{2} is
central. Indeed, we have ghghh(hghgh)^{−1} = ghghhh^{−1}g^{−1}h^{−1}g^{−1}h^{−1} =
gh(ghg^{−1}h^{−1})g^{−1}h^{−1} = ghg^{−1}ghg^{−1}h^{−1}h^{−1} = ghhg^{−1}h^{−1}h^{−1} = 1, and

similarlyghghg(gghgh)^{−1}= 1 by symmetry.

Proof of Theorem 1.2. Let G^{0} be the 2-group. Let g be a noncentral
element inG^{0}such thatg^{2} is central. Leth∈G^{0} so that it does not commute
withgbuth^{2} commutes withg. Then the subgroupH ofGgenerated byg
and his nilpotent of class 2. By previous lemma, each square element of H
is central in H.

For eachn∈N, we consider the element

γn= (x^{n}hx^{−n})g(x^{n}h^{−1}x^{−n}).

NING YANG

Each such element is a conjugate of the torsion elementgby another torsion
element x^{n}hx^{−n}. γn has depth at mostn+ 1. Since every conjugacy class
in the torsion subgroup of any wreath product of a finite group with a
torsion-free group is finite, see [13] Lemma 6.4, it suffices to show that γ_{n}
has depth at least [^{n}_{2}]. Indeed,γ_{n}=gx^{[}^{n}^{2}^{]}[g, h^{−1}]x^{−[}^{n}^{2}^{]} has depth [^{n}_{2}] + 1 by

Lemma 2.1.

Proof of Theorem 1.3. Combining Theorem 1.2 with results in the ap-

pendix of [13], the theorem follows.

3. Cross-wired lamplighter groups

The Cayley graph of lamplighter groups can be examples of Diestel–

Leader graphs, for particular choices of generators [3, 14, 22, 23]. Cross- wired lamplighter groups [2] are defined to be cocompact lattices of the isometry group of Diestel–Leader graphs. Cornulier, Fisher and Kashyap [2] give a necessary and sufficient condition for a locally compact group to be isomorphic to a closed cocompact subgroup in the isometry group of a Diestel–Leader graph. The following is the sufficient condition for the case of discrete groups.

Theorem 3.1. [2] Let Γ be a discrete group, with a semidirect product
decompositionΓ =Hohti, where His infinite andtis torsion free. Assume
thatH has subgroups L and L^{0} such that:

• tLt^{−1} and t^{−1}L^{0}tare finite index subgroups, of index m and n, in L
andL^{0} respectively;

• S

k∈Zt^{−k}Lt^{k}=S

k∈Zt^{k}L^{0}t^{−k}=H (these are increasing unions);

• L∩L^{0} is finite;

• the double coset space L\H/L^{0} is finite.

Then Γ is finitely generated, m = n and Γ has a proper, transitive action on some Diestel–Leader graph.

3.1. Proof of Theorem 1.4.

Proof of Theorem 1.4. In order to show the automata groups are cross- wired lamplighters, it suffices to check the conditions in above theorem.

Let

G={g_{1}= 1, g_{2}, ..., g_{k}},
L=hx^{n}Gx^{−n}, n≥0i,
L^{0} =hx^{n}Gx^{−n}, n≤ −1i.

(1) We show thatxLx^{−1}andx^{−1}L^{0}xare finite index subgroups inLand
L^{0} respectively. Note that xLx^{−1} = hx^{n}Gx^{−n}, n ≥ 1i < L. Lem-
ma 2.2 implies that every element inLcan be written as an element
ing(xLx^{−1}) for some g ∈ G. So the index of xLx^{−1} in L is finite.

Similarlyx^{−1}L^{0}x=hx^{n}Gx^{−n}, n≤ −1i has finite index inL^{0}.