The following problems provide a wider context for the study of diameters of Cayley graphs of
$S{L}_{N}\left({\mathbb{F}}_{p}\right)$
.
Problem 1.3
Fix
$N\ge 3$
. Does
$S{L}_{N}(\mathbb{Z})$
enjoy uniform Property (T )?
Problem 1.4
(An Independence Problem for
$S{L}_{N}(\mathbb{Z})$
.) Fix
$N\ge 3$
. Is
$$\left\{Cay(S{L}_{N}(\mathbb{Z})/H,X)\left\right[S{L}_{N}(\mathbb{Z}):H]<\infty ,\langle X\rangle =S{L}_{N}(\mathbb{Z})\right\}$$
a family of expanders?
Problem 1.5
Fix
$N\ge 2$
. Does there exist
$K>0$
such that for all generating sets
$X$
for
$S{L}_{N}(\mathbb{Z})$
and all primes
$p$
$$DiamCay(S{L}_{N}({\mathbb{F}}_{p}),X)\le Klogp?$$
For fixed
$N\ge 3$
, an affirmative answer to Problem 1.3 would imply an affirmative answer to 1.4 , and that, in turn, would imply an affirmative answer to 1.5 . In the case
$N=2$
, the same implications apply between 1.5 and the following analogues of 1.3 and 1.4 : does
$S{L}_{2}(\mathbb{Z})$
enjoy uniform Property (
$\tau $
) with respect to congruence subgroups (“The Selberg Property” [
?]
), and is
$\left\{Cay(S{L}_{2}(\mathbb{Z}/m\mathbb{Z}),X)\langle X\rangle =S{L}_{2}(\mathbb{Z})\right\}$
a family of expanders?
More details can be found in [
?]
and [
?]
; groups in which the analogue of Problem 1.3 has a negative answer are constructed in [
?]
; the original (more general) independence problems are in [
?]
; and a rare example of an independence result is due to Gamburd [
?]
who (roughly speaking) finds a large class of generating sets
$X$
for
$S{L}_{2}(\mathbb{Z})$
and primes
$p$
for which
$Cay(S{L}_{2}({\mathbb{F}}_{p}),X)$
forms a family of expanders.
We briefly mention related results for
$S{L}_{N}(\mathbb{Z})$
and
$S{L}_{N}\left({\mathbb{F}}_{p}\right)$
when
$N=2$
.
Property (
$\tau $
) is enjoyed by
$S{L}_{2}(\mathbb{Z})$
as a consequence of Selberg's Theorem (see [
?]
, [
?]
, [
?]
), and so for any fixed finite generating set
$X$
for
$S{L}_{2}(\mathbb{Z})$
, we find
$$\left\{Cay(S{L}_{N}({\mathbb{F}}_{p}),X)p\text{prime}\right\}$$
is a family of expanders. So there exists
$K>0$
such that
$$DiamCay(S{L}_{2}({\mathbb{F}}_{p}),X)\le Klogp$$
for all primes
$p$
. This proof (explained in [
?]
) is not constructive and neither is the only other known proof, which uses the circle method for lifting elements of
$S{L}_{2}\left({\mathbb{F}}_{p}\right)$
to elements of
$S{L}_{2}(\mathbb{Z})$
with short word representations [
?]
. But Larsen [
?]
has given an algorithm that produces word representations of length
$O(logploglogp)$
. In common with this article, representing powers such as
${{e}_{12}}^{m}$
by short words is key, and the subtractive version of Euclid's algorithm plays a role.
Another constructive result is due to Gamburd and Shahshahani [
?]
and is in the direction of Problem 1.5 in the case
$N=2$
. They give an algorithm that produces paths in Cayley graphs to prove the following uniform diameter bound: for all primes
$p>2$
, and for all finite sets
$X$
of elements of
$PS{L}_{2}(\mathbb{Z})$
such that
$\langle X\rangle $
is a
${p}^{2}$
dense subgroup of
$PS{L}_{2}(\mathbb{Z})$
$$DiamCay(PS{L}_{2}(\mathbb{Z}/{p}^{n}\mathbb{Z}),X)=c{log}^{d}\leftPS{L}_{2}(\mathbb{Z}/{p}^{n}\mathbb{Z})\right,$$
where
$d={log}_{2}420$
and
$c$
depends on
$X$
. This has been recently improved by Dinai [
?]
who shows that for all
$d>3$
, there exists
$c>0$
such that
$DiamCay(S{L}_{2}(\mathbb{Z}/{p}^{n}\mathbb{Z}),X)\le c{log}^{d}\leftS{L}_{2}(\mathbb{Z}/{p}^{n}\mathbb{Z})\right$
for all generating sets
$X$
for
$S{L}_{2}(\mathbb{Z})$
.
Acknowledgements.
I am grateful to Tsachik Gelander, Martin Kassabov and Alex Lubotzky for explaining background to the subject of diameters of the Cayley graphs of
$S{L}_{N}\left({\mathbb{F}}_{p}\right)$
to me, and to Karen Vogtmann for encouragement to investigate Thurston's claims about isoperimetric function for
$S{L}_{N}(\mathbb{Z})$
.
I additionally wish to thank Martin Kassabov for providing Lemma
5.2 , improving a lemma in an earlier version of this article.
2 Compressing powers
${{e}_{ij}}^{m}$
This section is devoted to proving the following result about representing powers
${{e}_{ij}}^{m}$
in
$S{L}_{N}(\mathbb{Z})$
by words of length
$O(log(1+\leftm\right\left)\right)$
.
Proposition 2.1
Suppose
$N,m,i,j\in \mathbb{Z}$
with
$N\ge 3$
, with
$1\le i,j\le N$
, and with
$i\ne j$
. There exists a word
${w}_{m}\in {\left\{{{e}_{pq}}^{\pm 1}1\le p,q\le N,p\ne q\right\}}^{\u25c6}$
such that
${w}_{m}={{e}_{ij}}^{m}$
in
$S{L}_{N}(\mathbb{Z})$
and
$$\ell \left(w\right)\le 4+6{log}_{\tau}(1+\leftm\right\sqrt{5}).$$
It suffices to prove the result for
$N=3,m>0,i=1$
and
$j=3$
, which we do by giving
${w}_{m}$
explicitly in the second of the two lemmas below. The first lemma addresses the case where
$m$
is a Fibonacci number (defined recursively by
${F}_{0}=0,{F}_{1}=1,{F}_{i+2}={F}_{i+1}+{F}_{i}$
), and will be superseded by the second lemma. The detailed calculation in the proof of the first lemma is key to understanding the proof of the second.
Lemma 2.2
For nonnegative integers
$n$
, the words
${{e}_{23}}^{1}\left({e}_{23}{e}_{32}{)}^{n}{{e}_{13}}^{1}\right({e}_{23}{e}_{32}{)}^{n}{{e}_{23}}^{1}\left({e}_{23}{e}_{32}{)}^{n}{e}_{13}\right({e}_{23}{e}_{32}{)}^{n}{{e}_{23}}^{2},$
and
${{e}_{23}}^{1}\left({e}_{23}{e}_{32}{)}^{n}{{e}_{12}}^{1}\right({e}_{23}{e}_{32}{)}^{n}{{e}_{23}}^{1}\left({e}_{23}{e}_{32}{)}^{n}{e}_{12}\right({e}_{23}{e}_{32}{)}^{n}{{e}_{23}}^{2}$
equal
${{e}_{13}}^{{F}_{2n}}$
and
${{e}_{13}}^{{F}_{2n+1}}$
, respectively, in
$S{L}_{3}(\mathbb{Z})$
.
Proof. We multiply out the first of these words from right to left as follows.
The calculation for the second is very similar. The notation for each step shown is
$\mathcal{A}\to \mathcal{\mathcal{B}}\mathcal{\mathcal{B}}\mathcal{A}$
.
$\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)$
$\to {{e}_{23}}^{2}$
$\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 2\\ 0& 0& 1\end{array}\right)$
$\to ({e}_{23}{e}_{32}{)}^{n}$
$\left(\begin{array}{ccc}1& 0& 0\\ 0& {F}_{2n+1}& {F}_{2n+3}\\ 0& {F}_{2n}& {F}_{2n+2}\end{array}\right)$
$\to {e}_{13}$
$\left(\begin{array}{ccc}1& {F}_{2n}& {F}_{2n+2}\\ 0& {F}_{2n+1}& {F}_{2n+3}\\ 0& {F}_{2n}& {F}_{2n+2}\end{array}\right)$
$\to ({e}_{23}{e}_{32}{)}^{n}$
$\left(\begin{array}{ccc}1& {F}_{2n}& {F}_{2n+2}\\ 0& 1& 2\\ 0& 0& 1\end{array}\right)$
$\to {{e}_{23}}^{1}$
$\left(\begin{array}{ccc}1& {F}_{2n}& {F}_{2n+2}\\ 0& 1& 1\\ 0& 0& 1\end{array}\right)$
$\to ({e}_{23}{e}_{32}{)}^{n}$
$\left(\begin{array}{ccc}1& {F}_{2n}& {F}_{2n+2}\\ 0& {F}_{2n+1}& {F}_{2n+2}\\ 0& {F}_{2n}& {F}_{2n+1}\end{array}\right)$
$\to {{e}_{13}}^{1}$
$\left(\begin{array}{ccc}1& 0& {F}_{2n}\\ 0& {F}_{2n+1}& {F}_{2n+2}\\ 0& {F}_{2n}& {F}_{2n+1}\end{array}\right)$
$\to ({e}_{23}{e}_{32}{)}^{n}$
$\left(\begin{array}{ccc}1& 0& {F}_{2n}\\ 0& 1& 1\\ 0& 0& 1\end{array}\right)$
$\to {{e}_{23}}^{1}$
$\left(\begin{array}{ccc}1& 0& {F}_{2n}\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)$
The following result can be proved by an easy induction.
Zeckendorf 's Theorem [
?]
, [
?]
. Every positive integer
$m$
can be expressed in a unique way as
$$\begin{array}{c}m={F}_{{k}_{1}}+{F}_{{k}_{2}}+\cdots +{F}_{{k}_{r}},\end{array}$$ 
(1)

with
${k}_{1}\ge 2$
and
${k}_{j+1}{k}_{j}\ge 2$
for all
$1\le j<r$
.
In fact,
${F}_{{k}_{r}}$
is the largest Fibonacci number no bigger than
$m$
, and
${F}_{{k}_{r1}}$
is the largest no bigger than
$m{F}_{{k}_{r}}$
, and so on. Recall that
${F}_{n}=({\tau}^{n}(\tau {)}^{n})/\sqrt{5}$
for all
$n$
, where
$\tau :=(1+\sqrt{5})/2$
, and so
$$\begin{array}{c}{F}_{n}\ge \frac{{\tau}^{n}1}{\sqrt{5}}.\end{array}$$ 
(2)

Thus, as
${F}_{{k}_{r}}\le m$
,
$$\begin{array}{ccc}{k}_{r}& \le & {log}_{\tau}(1+m\sqrt{5}).\end{array}$$ 
(3)

Lemma 2.3
Suppose
$m$
is a positive integer expressed as in ( 1 ). Write
$$m=({F}_{{\hat{k}}_{1}}+{F}_{{\hat{k}}_{2}}+\cdots +{F}_{{\hat{k}}_{\hat{r}}})+({F}_{{\overline{k}}_{1}}+{F}_{{\overline{k}}_{2}}+\cdots +{F}_{{\overline{k}}_{\overline{r}}})$$
where
${\hat{k}}_{1}<\dots <{\hat{k}}_{\hat{r}}$
are the even numbers amongst
${k}_{1},\dots ,{k}_{r}$
and
${\overline{k}}_{1}<\dots <{\overline{k}}_{\overline{r}}$
are the odd numbers. Let
$n$
be the integer such that either
$2n={k}_{r}$
or
$2n+1={k}_{r}$
. Let
${u}_{m}$
be the word
$${a}_{n}{b}_{n}\left({e}_{23}{e}_{32}\right)\dots {a}_{2}{b}_{2}\left({e}_{23}{e}_{32}\right){a}_{1}{b}_{1}\left({e}_{23}{e}_{32}\right)$$
in which
${a}_{i}={e}_{13}$
if
$2i\in \{{\hat{k}}_{1},\dots ,{\hat{k}}_{\hat{r}}\}$
and is the empty string otherwise, and
${b}_{i}={e}_{12}$
if
$2i+1\in \left\{{\overline{k}}_{1},\dots ,{\overline{k}}_{\overline{r}}\right\}$
and is the empty string otherwise. Let
${v}_{m}$
be the word obtained from
${u}_{m}$
by replacing every
${e}_{12}$
and
${e}_{13}$
by
${{e}_{12}}^{1}$
and
${{e}_{13}}^{1}$
, respectively. Define
$${w}_{m}:={{e}_{23}}^{1}\left({e}_{23}{e}_{32}{)}^{n}{v}_{m}{{e}_{23}}^{1}\right({e}_{23}{e}_{32}{)}^{n}{u}_{m}{{e}_{23}}^{2}.$$
Then
${w}_{m}$
equals
${{e}_{13}}^{m}$
in
$S{L}_{3}(\mathbb{Z})$
and has length
$$\begin{array}{ccc}\ell \left({w}_{m}\right)\le 4+6{log}_{\tau}(1+m\sqrt{5}).& & \end{array}$$ 
(4)

Proof. Lemma 2.2 is a special case of this lemma: when
$m={F}_{2n}$
we find
${u}_{m}={e}_{13}({e}_{23}{e}_{32}{)}^{n}$
and
${v}_{m}={{e}_{13}}^{1}({e}_{23}{e}_{32}{)}^{n}$
, and when
$m={F}_{2n+1}$
we find
${u}_{m}={e}_{12}({e}_{23}{e}_{32}{)}^{n}$
and
${v}_{m}={{e}_{12}}^{1}({e}_{23}{e}_{32}{)}^{n}$
. Multiply out
${w}_{m}$
from right to left, as follows, using a more general and concise version of the calculation used to establish Lemma 2.2 . All the sums are over
$i=1,\dots ,r$
.
$\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 2\\ 0& 0& 1\end{array}\right)$
$\to {u}_{n}$
$\left(\begin{array}{ccc}1& \sum {F}_{{k}_{i}}& \sum {F}_{{k}_{i}+2}\\ 0& {F}_{2n+1}& {F}_{2n+3}\\ 0& {F}_{2n}& {F}_{2n+2}\end{array}\right)$
$\to ({e}_{23}{e}_{32}{)}^{n}$
$\left(\begin{array}{ccc}1& \sum {F}_{{k}_{i}}& \sum {F}_{{k}_{i}+2}\\ 0& 1& 2\\ 0& 0& 1\end{array}\right)$
$\to {v}_{m}{{e}_{23}}^{1}$
$\left(\begin{array}{ccc}1& 0& \sum ({F}_{{k}_{i}+2}{F}_{{k}_{i}+1})\\ 0& {F}_{2n+1}& {F}_{2n+2}\\ 0& {F}_{2n}& {F}_{2n+1}\end{array}\right)$
$\to {{e}_{23}}^{1}({e}_{23}{e}_{32}{)}^{n}$
$\left(\begin{array}{ccc}1& 0& \sum {F}_{{k}_{i}}\\ 0& 1& 0\\ 0& 0& 1\end{array}\right).$
The length of
${w}_{m}$
is
$4+8n+2r$
, from which we get ( 4 ) by using ( 3 ),
$r\le {k}_{r}$
and
$n\le {k}_{r}/2$
.
3 Accelerating the subtractive version of Euclid's algorithm
The subtractive version of Euclid's algorithm for finding the greatest common divisor of an
$N$
tuple of integers differs from the standard Euclid's algorithm in that at each step an addition or subtraction is made rather than a remainder taken. That is, in one step an
$N$
tuple
$({a}_{i+1}^{1},\dots ,{a}_{i+1}^{N})$
is produced from the previous
$k$
tuple
$({a}_{i}^{1},\dots ,{a}_{i}^{N})$
, as follows. Take
$p$
and
$q$
so that
${a}_{i}^{p}$
and
${a}_{i}^{q}$
have the greatest and second greatest absolute values amongst
${a}_{i}^{1},\dots ,{a}_{i}^{N}$
. (To resolve deadheats, take
$p$
minimal, and then take
$q$
minimal amongst the remaining indices.) Define
${a}_{i+1}^{p}:={a}_{i}^{p}\pm {a}_{i}^{p}$
, with the sign chosen so that
$\left{a}_{i+1}^{p}\right<\left{a}_{i}^{p}\right$
, and define
${a}_{i+1}^{j}:={a}_{i}^{j}$
for all
$j\ne p$
. Stop when all but one entry is zero and output the absolute value of that entry.
For example, in 6 steps the algorithm gives
$gcd(32,8,12)=4$
:
$$(32,8,12)\mapsto (20,8,12)\mapsto (8,8,12)\mapsto (8,8,4)$$
$$\mapsto (0,8,4)\mapsto (0,4,4)\mapsto (0,0,4).$$
There is a non–deterministic version of this algorithm in which obtaining
$({a}_{i+1}^{1},\dots ,{a}_{i+1}^{N})$
from
$({a}_{i}^{1},\dots ,{a}_{i}^{N})$
by adding one entry to another or by subtracting one entry from another constitutes a step. Again, the algorithm stops when all but one entry is zero, and the output is the absolute value of that entry.
Yao and Knuth [
?]
proved that the average number of steps to compute
$gcd(m,n)$
by the (deterministic) subtractive version of Euclid's algorithm, where
$m$
is uniformly distributed in the range
$1\le m\le n$
, is
$6{\pi}^{2}(lnn{)}^{2}+O(logn(loglogn{)}^{2})$
. We will show that the worst–case non–deterministic complexity of Euclid's algorithm for computing the
$gcd$
of
$N\ge 3$
integers
$({a}^{1},\dots ,{a}^{N})$
is
$O(logn)$
, where
$n:=max\left\{\left{a}^{1}\right,\dots ,\left{a}^{N}\right\right\}$
. (In particular, the greatest common divisor of two integers
$({a}^{1},{a}^{2})$
can be calculated nondeterministically in
$O(log(n\left)\right)$
steps by starting with
$({a}^{1},{a}^{2},0)$
.) That is, we prove:
Theorem 3.1
Suppose
$({a}^{1},\dots ,{a}^{N})$
is an
$N$
tuple of integers, not all zero, and
$N\ge 3$
. Define
$n:=max\left\{\left{a}^{1}\right,\dots ,\left{a}^{N}\right\right\}$
. There is a constant
$K>0$
, independent of
$n$
and
$N$
, such that there is a sequence of no more than
$K(N1)(1+logn)$
additions and subtractions of one entry to or from another, after which all but one entry in the
$N$
tuple are zero.
Proof. First consider running the standard Euclid's algorithm on the first two entries
${a}_{0}:={a}^{1}$
and
${b}_{0}:={a}^{2}$
in the
$N$
tuple. This proceeds via a sequence
$({a}_{i},{b}_{i})$
of pairs of integers finishing with a pair
$({a}_{k},{b}_{k})$
one of which is zero. The pair
$({a}_{i+1},{b}_{i+1})$
is obtained from
$({a}_{i},{b}_{i})$
by replacing the entry with the larger absolute value by the remainder on division by the other. So for all
$i=0,\dots ,k1$
there is some integer
${q}_{i}$
such that either (
${a}_{i+1}={a}_{i}\pm {q}_{i}{b}_{i}$
and
${b}_{i+1}={b}_{i}$
), or (
${a}_{i+1}={a}_{i}$
and
${b}_{i+1}={b}_{i}\pm {q}_{i}{a}_{i}$
).
It takes the standard subtractive algorithm
${q}_{i}$
steps to get from
$({a}_{i},{b}_{i})$
to
$({a}_{i+1},{b}_{i+1})$
. But, as
$N\ge 3$
, Proposition 2.1 gives us a word
${w}^{{q}_{i}}$
that has length at most
$4+6{log}_{\tau}(1+{q}_{i}\sqrt{5}))$
and that, reading righttoleft, describes a sequence of steps with the same effect. (The step described by the letter
${{e}_{pq}}^{\pm 1}$
corresponds to leftmultiplying the transpose of the
$N$
tuple. The entries
${a}^{3},\dots ,{a}^{N}$
in the
$N$
tuple may be disturbed in the course of these steps, but are recovered.) Define
${c}_{i}:=max\left\{\left{a}_{i}\right,\left{b}_{i}\right\right\}$
. Then
${q}_{i}\le {c}_{i}/{c}_{i+1}$
and
${q}_{0}\le n$
. So it is possible to get from
$({a}_{0},{b}_{0})$
to
$({a}_{k},{b}_{k})$
in
$S$
steps where
$$S\le {\sum}_{i=0}^{k1}\left(4+6{log}_{\tau}\left(1+\frac{{c}_{i}}{{c}_{i+1}}\sqrt{5}\right)\right).$$
But, as
${c}_{i}/{c}_{i+1}\ge 1$
for all
$0\le i\le k1$
, and
${c}_{0}/{c}_{k}\le n$
, this is at most
$$\begin{array}{ccc}S& \le & 4k+6{\sum}_{i=0}^{k1}{log}_{\tau}\left(\frac{{c}_{i}}{{c}_{i+1}}\left(1+\sqrt{5}\right)\right)\end{array}$$  
$$\begin{array}{ccc}& \le & 4k+6\left({log}_{\tau}n+k{log}_{\tau}\left(1+\sqrt{5}\right)\right).\end{array}$$ 
(5)

Now
$n\ge {F}_{k+1}$
by an easy induction. So by inequality ( 2 ) of Section 2
$$n\ge \frac{{\tau}^{k+1}1}{\sqrt{5}},$$
and thus
$k\le 1+{log}_{\tau}(1+n\sqrt{5})$
. This inequality together with ( 5 ) shows there exists
$K>0$
such that
$S\le K+Klogn$
.
Obtain the bound claimed in the theorem by next arguing as above for
${a}^{3}$
and whichever or the first and second entries in the
$N$
tuple is now nonzero, and then similarly for
${a}^{4}$
, and so on, until finally for
${a}^{N}$
.
The proof above can be developed into a deterministic algorithm to calculate
$gcd({a}^{1},\dots ,{a}^{N})$
. What are needed are the
${q}_{i}$
together with the words
${w}^{{q}_{i}}$
of Lemma 2.3 . But those
${w}^{{q}_{i}}$
are built using the expression for
${q}_{i}$
of Zeckendorf 's Theorem. Whilst is not hard to write routines to supply the
${q}_{i}$
and the expressions as per Zeckendorf 's Theorem, it is not clear that producing a deterministic algorithm to calculate
$gcd({a}^{1},\dots ,{a}^{N})$
in this manner has any computational advantages.
Theorem
3.1 fails when
$N=2$
(it is likely the following results are well known, but we include them for completeness and for the contrast):
Proposition 3.2
To convert
$(1,n)$
to
$(\pm 1,0)$
or
$(0,\pm 1)$
by successively subtracting one entry from, or adding one entry to, the other, requires
$n$
steps.
Proof. The number of steps required is at least the distance from
${{e}_{21}}^{n}$
to the identity in the word metric on
$S{L}_{2}(\mathbb{Z})$
with respect to the generating set
${e}_{12},{e}_{21}$
. This is because reading a word
$w$
that represents
${{e}_{21}}^{n}$
from right to left would give a sequence of steps that transforms
$(1,0{)}^{t}$
to
$(1,n{)}^{t}$
.
But such a word
$w$
descends to a word
$\hat{w}$
in the images
$\text{}{\hat{e}}_{12}{\text{}}^{\pm 1}$
,
$\text{}{\hat{e}}_{21}{\text{}}^{\pm 1}$
of
${{e}_{12}}^{\pm 1}$
,
${{e}_{21}}^{\pm 1}$
under the natural map
$S{L}_{2}(\mathbb{Z})\to \to PS{L}_{2}(\mathbb{Z})$
. And
$PS{L}_{2}(\mathbb{Z})\sim =(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/3\mathbb{Z})$
, presented by
$\langle \hat{s},\hat{t}{\hat{s}}^{2},{\hat{t}}^{3}\rangle $
, where
$$s=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\text{and}t=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right).$$
Now,
$st={e}_{21}$
and so
$(st{)}^{n}={{e}_{21}}^{n}$
. And
$(\hat{s}\hat{t}{)}^{n}$
is of minimal length amongst all words in
${\left\{{\hat{s}}^{\pm 1},{\hat{t}}^{\pm 1}\right\}}^{\u25c6}$
that represent
$\text{}{\hat{e}}_{21}{\text{}}^{n}$
in the free product
$(\mathbb{Z}/2\mathbb{Z})*(\mathbb{Z}/3\mathbb{Z})$
. So the minimal length of words in
${\left\{{{e}_{12}}^{\pm 1},{{e}_{21}}^{\pm 1}\right\}}^{\u25c6}$
that equal
$\text{}{e}_{21}{\text{}}^{n}$
in
$S{L}_{2}(\mathbb{Z})$
is
$n$
.
Corollary 3.3
The (worst case ) nondeterministic time complexity of the subtractive version of Euclid's algorithm for finding the greatest common divisor of two integers
$a,b$
with
$n:=max\left\{\lefta\right,\leftb\right\right\}$
is between
$n$
and
$2n$
.
In the next section we will need the following more technical result that is proved in the same way as Theorem 3.1 .
Theorem
3.1
${}^{\prime}$
Suppose
$({a}^{1},\dots ,{a}^{N})$
is an
$N$
tuple of integers, not all zero, where
$N\ge 3$
, and suppose
$1\le k\le N$
. Define
$n:=max\left\{\left{a}^{Nk+1}\right,\dots ,\left{a}^{N}\right\right\}$
.
There is a constant
$K>0$
, independent of
$k,n$
and
$N$
, such that there is a sequence of no more than
$(k1)K(1+logn)$
steps after which the first
$Nk$
entries in the
$N$
tuple are unchanged, all but one of the remaining entries in the
$N$
tuple are zero, and that remaining entry is
$\pm gcd({a}^{Nk+1},\dots ,{a}^{N})$
.
4 The MozesLubotzkyRaghunathan Theorem
In this section we give an elementary proof of the following result which is an instance of a theorem of Mozes, Lubotzky and Raghunathan on irreducible lattices in semisimple Lie groups of rank at least 2. In [
?]
they proved the case addressed below before generalising it to lattices in other Lie groups in [
?]
. We add information about the constants. (For a matrix
$\mathcal{\mathcal{M}}$
with real entries,
$\left\right\mathcal{\mathcal{M}}\left\right$
denotes the supnorm, the maximum of the absolute values of the entries.)
Theorem 4.1
Fix
$N\ge 3$
. Let
$\ell (\mathcal{\mathcal{M}})$
denote the word length of
$\mathcal{\mathcal{M}}\in S{L}_{N}(\mathbb{Z})$
, with respect to a fixed finite generating set. There exist
${C}_{1},{C}_{2}>0$
such that for all
$\mathcal{\mathcal{M}}\in S{L}_{N}(\mathbb{Z})$
$${C}_{1}log\left\right\mathcal{\mathcal{M}}\left\right\le \ell (\mathcal{\mathcal{M}})\le {C}_{2}log\left\right\mathcal{\mathcal{M}}\left\right.$$
Moreover, if the generating set is
$\left\{{e}_{ij}i\ne j\right\}$
then
${C}_{1}$
is independent of
$N$
and
${C}_{2}\le {C}_{3}{N}^{N}$
for a constant
${C}_{3}>0$
that is independent of
$N$
.
Proof. One easily checks that if the first part of the theorem holds for one finite generating set for
$S{L}_{N}(\mathbb{Z})$
then it holds for all. We will work with the generating set
$\left\{{e}_{ij}i\ne j\right\}$
.
The first inequality is straightforward. The supnorm of a matrix that is the product of
$n$
matrices in
$\left\{{e}_{ij}i\ne j\right\}$
is at most
${F}_{n}$
, and
${F}_{n}$
grows exponentially with
$n$
.
The second inequality will take more work. Suppose
$\mathcal{\mathcal{M}}\in S{L}_{N}(\mathbb{Z})$
.
Below, is a (wellknown) procedure for reducing
$\mathcal{\mathcal{M}}$
to the identity by row operations. Each row operation corresponds to leftmultiplication by some
${{e}_{ij}}^{\pm 1}$
and so a word
$w\in {\left\{{{e}_{ij}}^{\pm 1}i\ne j\right\}}^{\u25c6}$
that equals
$\mathcal{\mathcal{M}}$
in
$S{L}_{N}(\mathbb{Z})$
can be extracted.

(
$1$
)
Convert
$\mathcal{\mathcal{M}}$
to an upper triangular matrix whose diagonal entries are all
$\pm 1$
, as follows.

(
${1}_{1}$
)
Run Euclid's algorithm on the first column. This will leave all entries zero except one that is
$\pm 1$
, because
$det\mathcal{\mathcal{M}}=1$
. Let
${i}_{1}$
be the row containing the nonzero entry in the first column.
If
${i}_{1}\ne 1$
then premultiply by
${e}_{1{i}_{1}}{{e}_{{i}_{1}1}}^{1}{e}_{1{i}_{1}}$
, which reverses the signs of the entries in row 1 and then interchanges rows
$1$
and
${i}_{1}$
.

(
${1}_{2}$
)
Run Euclid's algorithm on the entries in rows
$2$
to
$N$
of second column, leaving all zero except one that is
$\pm 1$
and lies in row
${i}_{2}$
. If
${i}_{2}\ne 2$
then premultiply by
${e}_{2{i}_{2}}{{e}_{{i}_{2}2}}^{1}{e}_{2{i}_{2}}$
.

.

(
${1}_{N1}$
)
Run Euclid's algorithm on the entries in rows
$N1$
and
$N$
of the
$(N1)$
st column, to make one entry
$0$
and the other
$\pm 1$
. Then, if necessary, premultiply by
${e}_{N1,N}{{e}_{N,N1}}^{1}{e}_{N1,N}$
to get an upper triangular matrix.

(
$2$
)
Get a matrix
$\left({m}_{ij}\right)$
for which all the entries on the diagonal are 1 by premultipling by at most
$N/2$
matrices
$({e}_{ij}{{e}_{ji}}^{1}{e}_{ij}{)}^{2}$
that reverse the signs of all the entries in rows
$i$
and
$j$
.

(
$3$
)
Clear all the above–diagonal entries in
$\left({m}_{ij}\right)$
, one column at a time, as follows.

(
${3}_{2}$
)
Premultiply by
${{e}_{12}}^{{m}_{12}}$
.

(
${3}_{3}$
)
Premultiply by
${{e}_{13}}^{{m}_{13}}{{e}_{23}}^{{m}_{23}}$
.

.

(
${3}_{N}$
)
Premultiply by
${{e}_{1,N}}^{{m}_{1,N}}\dots {{e}_{N1,N}}^{{m}_{N1,N}}$
.
As it stands, the number of
${{e}_{ij}}^{\pm 1}$
used in the procedure above may wildly exceed
$log\left\right\mathcal{\mathcal{M}}\left\right$
on account of steps (
$1$
) and (
$3$
). However, we can accelerate (
${1}_{1}$
)–(
${1}_{N1}$
) as per Theorem 3.1
${}^{\prime}$
. Define
${\mathcal{\mathcal{M}}}_{0}:=\mathcal{\mathcal{M}}$
. Performing (
${1}_{1}$
) then takes at most
${k}_{1}:=(N1)K(1+log\mathcal{\mathcal{M}}\left\right)$
steps and leaves a matrix
${\mathcal{\mathcal{M}}}_{1}$
such that
$\left\right{\mathcal{\mathcal{M}}}_{1}\left\right\le \left\right{\mathcal{\mathcal{M}}}_{0}\left\right{F}_{{k}_{1}+2}$
. And, proceeding inductively, (
${1}_{i}$
) costs at most
${k}_{i}:=(Ni)K(1+log\left{\mathcal{\mathcal{M}}}_{i1}\right\left\right)$
steps and leaves a matrix
${\mathcal{\mathcal{M}}}_{i}$
with
$\left\right{\mathcal{\mathcal{M}}}_{i}\left\right\le \left\right{\mathcal{\mathcal{M}}}_{i1}\left\right{F}_{{k}_{i}+2}$
.
So there is a constant
$C>0$
such that for all
$1\le i\le N1$
,
$$\begin{array}{ccc}{k}_{i}& \le & KN(1+log\left{\mathcal{\mathcal{M}}}_{i1}\right\left\right)\text{and}\end{array}$$  
$$\begin{array}{ccc}log\left\right{\mathcal{\mathcal{M}}}_{i}\left\right& \le & C{k}_{i}+log\left\right{\mathcal{\mathcal{M}}}_{i1}\left\right.\end{array}$$  
These inequalites and induction can be used to establish that for
$1\le i\le N$
$$\begin{array}{ccc}log\left\right{\mathcal{\mathcal{M}}}_{i1}\left\right& \le & (1+log\mathcal{\mathcal{M}}\left\right)(1+CKN{)}^{i1}1,\end{array}$$ 
(6)

and for all
$1\le i\le N1$
$$\begin{array}{ccc}{k}_{i}& \le & KN(1+log\mathcal{\mathcal{M}}\left\right)(1+CKN{)}^{i1}.\end{array}$$  
So there is a constant
${C}^{\prime}>0$
, independent of
$\mathcal{\mathcal{M}}$
and
$N$
, such that the contribution of (
$1$
) to
$\ell \left(w\right)$
is at most
${\sum}_{i=1}^{N1}{k}_{i}\le {C}^{\prime}{N}^{N1}log\left\right\mathcal{\mathcal{M}}\left\right$
.
The contribution of step (
$2$
) to
$\ell \left(w\right)$
is at most
$3N$
. To assess the contribution of step (
$3$
), first note that
$\left{m}_{ij}\right\le \left\right{\mathcal{\mathcal{M}}}_{i}\left\right$
for all
$i,j$
because in the course of step (
$1$
), row
$i$
is not disturbed after (
${1}_{i}$
). So, by inequality ( 6 ) and by compressing each of the
$N(N1)/2$
terms
${{e}_{ij}}^{{m}_{ij}}$
as per Proposition 2.1 , we see that the effect of step (
$3$
) can be achieved whilst contributing at most
$$\begin{array}{c}{C}^{\prime}+{C}^{\prime}(1+log\mathcal{\mathcal{M}}\left\right){\sum}_{i=1}^{N1}(Ni)(1+CKN{)}^{i}\end{array}$$ 
(7)

to
$\ell \left(w\right)$
, for some constant
${C}^{\prime}>0$
independent of
$\mathcal{\mathcal{M}}$
and
$N$
. But the summation term in ( 7 ) is at most a constant times
$1+N+{N}^{2}+\cdots +{N}^{N}$
, which is at most
$4{N}^{N}$
as
$N>2$
. The outstanding claims of the theorem then follow.
5 The diameter of
$S{L}_{N}\left({\mathbb{F}}_{p}\right)$
.
We adopt the notation
${\alpha}^{\beta}:={\beta}^{1}\alpha \beta $
and
$[\alpha ,\beta ]={\alpha}^{1}{\beta}^{1}\alpha \beta $
.
Theorem 5.1
There exists
$C>0$
such that for all
$N\ge 3$
and primes
$p$
,
$$DiamCay(S{L}_{N}({\mathbb{F}}_{p}),\left\{{e}_{ij}i\ne j\right\})\le C{N}^{2}logp.$$
Proof. Suppose
$\mathcal{\mathcal{M}}\in S{L}_{N}\left({\mathbb{F}}_{p}\right)$
. We reduce
$\mathcal{\mathcal{M}}$
to the identity matrix by successively premultiplying by matrices in
$\left\{{e}_{ij}i\ne j\right\}$
in a similar manner to that used to prove Theorem 4.1 .
First lift the entries in the first column of
$\mathcal{\mathcal{M}}$
to
$[0,p1]$
and run the accelerated version of the subtractive version of Euclid's algorithm on the first column of the matrix. Then swap two rows (changing the sign of one) to move the nonzero entry to the first row. Next run the accelerated version of the subtractive version of Euclid's algorithm on the lift to
$[0,p1]$
of all but the first entry of second column, and move the nonzero entry to place 2,2 in the matrix. Continue similarly through all the columns. By Theorem 3.1
${}^{\prime}$
, the cost is at most a constant times
$$logp{\sum}_{j=1}^{N1}(Nj)<{N}^{2}logp.$$
We now have an upper triangular matrix
$\left({m}_{ij}\right)$
such that every diagonal entry is nonzero. As
$p$
is prime and the diagonal entries in the matrix are nonzero, we can clear all the
$N(N1)/2$
entries above the diagonal by premultiplying by matrices of the form
${{e}_{ij}}^{{m}_{ij}}$
where
$j>i$
. By Proposition 2.1 the effect of premultiplying by
${{e}_{ij}}^{{m}_{ij}}$
can be achieved by premultiplying by a sequence of at most a constant times
$logp$
matrices in
$\left\{{{e}_{ij}}^{\pm 1}i\ne j\right\}$
. So we can reduce
$\mathcal{\mathcal{M}}$
to a diagonal matrix
$\mathcal{D}=\text{diag}({a}_{1},\dots ,{a}_{N})$
with total cost at most a constant times
${N}^{2}logp$
.
As
${a}_{1}$
and
${a}_{1}{a}_{2}$
are invertible in
${\mathbb{F}}_{p}$
, we can convert
$\mathcal{D}$
to
$\text{diag}(1,{a}_{1}{a}_{2},{a}_{3},\dots ,{a}_{N})$
by premultiplying by
${{e}_{12}}^{\pm 1},{{e}_{21}}^{\pm 1}$
as follows,
$\left(\begin{array}{ccc}{a}_{1}& 0& \\ 0& {a}_{2}\\ & & ...\end{array}\right)$
$\to {e}_{12}{{e}_{21}}^{1}{e}_{12}$
$\left(\begin{array}{ccc}0& {a}_{2}& \\ {a}_{1}& 0& \\ & & ...\end{array}\right)$
$\to {{e}_{12}}^{{{a}_{1}}^{1}}$
$\left(\begin{array}{ccc}1& {a}_{2}& \\ {a}_{1}& 0& \\ & & ...\end{array}\right)$
$\to {{e}_{21}}^{{a}_{1}}$
$\left(\begin{array}{ccc}1& {a}_{2}& \\ 0& {a}_{1}{a}_{2}& \\ & & 0\end{array}\right)$
$\to {{e}_{12}}^{{a}_{2}({a}_{1}{a}_{2}{)}^{1}}$
$\left(\begin{array}{ccc}1& 0& \\ 0& {a}_{1}{a}_{2}& \\ & & ...\end{array}\right).$
Using Proposition 2.1 the same effect can achieved by premultiplying by at most a constant times
$logp$
matrices in
$\left\{{{e}_{ij}}^{\pm 1}i\ne j\right\}$
. Applying this same process to the second and third rows, and then the third and fourth, and so on we reduce the matrix to the identity, at a total cost of at most a constant times
$Nlogp$
.
To deduce Corollary
1.1 we use the following lemma, due to M. Kassabov, concerning the matrices
${\mathcal{A}}_{N}$
and
${\mathcal{\mathcal{B}}}_{N}$
given in Section 1 .
Lemma 5.2
For all
$1\le i,j\le N$
with
$i\ne j$
it is possible to express
${e}_{ij}$
as a word in
${{\mathcal{A}}_{N}}^{\pm 1}$
and
${{\mathcal{\mathcal{B}}}_{N}}^{\pm 1}$
of length at most
$10N$
.
Proof. We will drop the subscripts from
${\mathcal{A}}_{N}$
and
${\mathcal{\mathcal{B}}}_{N}$
. For all
$i\ne j$
we have
${{e}_{i,j}}^{\mathcal{\mathcal{B}}}={{e}_{i+1,j+1}}^{\pm 1}$
where the indices are in
$\left\{1,\dots ,N\right\}$
and are taken modulo
$N$
. So it suffices to express all
${e}_{1,1+k}$
, for
$1\le k\le N1$
, as words in
${\mathcal{A}}^{\pm 1}$
and
${\mathcal{\mathcal{B}}}^{\pm 1}$
of length at most
$8N$
.
For
$k=2,\dots ,n$
define
${\mathcal{P}}_{k}:={e}_{12}{e}_{23}\dots {e}_{k1,k}$
. Then
$${\mathcal{P}}_{k}=\mathcal{A}{\mathcal{A}}^{\mathcal{\mathcal{B}}}\cdots {\mathcal{A}}^{{\mathcal{\mathcal{B}}}^{k2}}=\mathcal{A}{\mathcal{\mathcal{B}}}^{1}\mathcal{A}{\mathcal{\mathcal{B}}}^{1}\dots \mathcal{A}{\mathcal{\mathcal{B}}}^{1}\mathcal{A}{\mathcal{\mathcal{B}}}^{k2}.$$
Now
${\mathcal{N}}_{k}:={\mathcal{P}}_{k}{{\mathcal{P}}_{k1}}^{1}$
which, due to cancellations, equals a word of length
$4k7$
in
${\mathcal{A}}^{\pm 1}$
and
${\mathcal{\mathcal{B}}}^{\pm 1}$
, and is
$$\begin{array}{ccc}\left(\begin{array}{cccccc}1& 1& ...& 1& 1& \\ & 1& \ddots & \vdots & \vdots & \\ & & \ddots & 1& 1& \\ & & & 1& 1& \\ & & & & 1& \\ & & & & & {\text{Id}}_{nk}\end{array}\right)\left(\begin{array}{cccccc}1& 1& & & & \\ & 1& \ddots & & & \\ & & \ddots & 1& & \\ & & & 1& & \\ & & & & 1& \\ & & & & & {\text{Id}}_{nk}\end{array}\right)=\left(\begin{array}{cccccc}1& & & & 1& \\ & 1& & & 1& \\ & & \ddots & & \vdots & \\ & & & 1& 1& \\ & & & & 1& \\ & & & & & {\text{Id}}_{nk}\end{array}\right).& & \end{array}$$  
For
$k=3,\dots ,n$
, we calculate that
${\mathcal{N}}_{k}({\mathcal{\mathcal{B}}}^{1}{\mathcal{N}}_{k1}\mathcal{\mathcal{B}}{)}^{1}$
is
$$\begin{array}{ccc}\left(\begin{array}{cccccc}1& & & & 1& \\ & 1& & & 1& \\ & & \ddots & & \vdots & \\ & & & 1& 1& \\ & & & & 1& \\ & & & & & {\text{Id}}_{nk}\end{array}\right)\left(\begin{array}{cccccc}1& & & & 0& \\ & 1& & & 1& \\ & & \ddots & & ...& \\ & & & 1& 1& \\ & & & & 1& \\ & & & & & {\text{Id}}_{nk}\end{array}\right)={e}_{1k}.& & \end{array}$$  
So
${e}_{1k}$
can be expressed as a word of length
$8k16$
in
${\mathcal{A}}^{\pm 1},{\mathcal{\mathcal{B}}}^{\pm 1}$
.
Tim R. Riley
Mathematics Department, 10 Hillhouse Avenue, P.O. Box 208283, New Haven, CT 065208283, USA tim.riley@yale.edu, http://www.math.yale.edu/users/riley/