Navigating in the Cayley graphs of S L N ( Z )   and S L N ( F p )  

T. R. RileySupport from NSF grant 0404767 is gratefully acknowledged.

October 2004

Abstract
We give a non-deterministic algorithm that expresses elements of S L N ( Z )   , for N ≥ 3   , as words in a finite set of generators, with the length of these words at most a constant times the word metric. We show that the non-deterministic time-complexity of the subtractive version of Euclid's algorithm for finding the greatest common divisor of N ≥ 3   integers a 1 , … , a N   is at most a constant times N log n   where n : = max { | a 1 | , … , | a N | }   . This leads to an elementary proof that for N ≥ 3   the word metric in S L N ( Z )   is biLipschitz equivalent to the logarithm of the matrix norm – an instance of a theorem of Mozes, Lubotzky and Raghunathan. And we show constructively that there exists K > 0   such that for all N ≥ 3   and primes p   , the diameter of the Cayley graph of S L N ( F p )   with respect to the generating set { e i j | i ≠ j }   is at most K N 2 log p   .
2000 Mathematics Subject Classification: 20F05 Key words and phrases: special linear, normal form, diameter, Cayley graph, Euclid's algorithm

1 Introduction

This paper concerns expressing elements of S L N ( Z )   and S L N ( F p )   , for N ≥ 3   , as words in the generating set { e i j | i ≠ j }   consisting of the N 2 − N   elementary matrices e i j   that have 1   's along the diagonal, the off-diagonal i j   -entry 1   , and all other entries 0.
What gets our study off the ground is an explicit means of writing powers e i j m   in S L N ( Z )   , for N ≥ 3   , as products of O ( log ( 1 + | m | ) )   matrices in { e i j | i ≠ j } ± 1   . This is explained in Section  2 and involves expressing m   as a sum of Fibonacci numbers. It is used (in Section  3 ) in a study of the non-deterministic time complexity of the subtractive Euclid's algorithm for finding the greatest common divisor of integers a 1 , … , a N   . This differs from the standard Euclid's algorithm in that in each step one integer is added to or subtracted from another, rather than a remainder on division taken.
Yao and Knuth [?]  proved that the average number of steps to compute g c d ( m , n )   by the (deterministic) subtractive version of Euclid's algorithm, where m   is uniformly distributed in the range 1 ≤ m ≤ n   , is 6 π − 2 ( ln n ) 2 + O ( log n ( log log n ) 2 )   . We show that the worst–case non–deterministic complexity of Euclid's algorithm for computing the g.c.d. of N ≥ 3   integers ( a 1 , … , a N )   is O ( N log n )   , where n : = max { | a 1 | , … , | a N | }   .
Theorem  3.1 Suppose ( a 1 , … , a N )   is an N   -tuple of integers, not all zero, and N ≥ 3   . Define n : = max { | a 1 | , … , | a N | }   . There is a constant K > 0   , independent of n   and N   , such that there is a sequence of no more than K ( N − 1 ) ( 1 + log n )   additions and subtractions of one entry from another, after which all but one entry in the N   -tuple are zero.
The innovation is to use the compression techniques of Section  2 to accelerate repeated additions or subtractions of one entry to or from another. By contrast, the non–deterministic complexity is ∼ n   in the case N = 2   – we supply a group theoretic proof of this, presumably well-known, result. A vivid example is that it requires | n |   steps (additions and subtractions) to convert ( 1 , n )   to ( 1 , 0 )   , but ( 1 , n , 0 )   can be reduced to ( 1 , 0 , 0 )   in O ( log | n | )   steps.
Then, in Section  4 , we run our accelerated version of Euclid's algorithm of Section  3 on the columns of a matrix ℳ   in S L N ( Z )   , in the course of reducing ℳ   to the identity by row operations. This leads to a new proof of an instance of a celebrated theorem of Mozes, Lubotzky and Raghunathan [?] , [?] , and we contribute information about the constants:
Theorem  4.1 Fix N ≥ 3   . Let ℓ ( ℳ )   denote the word length of ℳ ∈ S L N ( Z )   , with respect to a fixed finite generating set. There exist C 1 , C 2 > 0   such that for all ℳ ∈ S L N ( Z )   C 1 log | | ℳ | | ≤ ℓ ( ℳ ) ≤ C 2 log | | ℳ | | .   Moreover, if the generating set is { e i j | i ≠ j }   then C 1   is independent of N   and C 2 ≤ C 3 N N   for a constant C 3 > 0   that is independent of N   .
Our proof of Theorem  4.1 is constructive (as are the proofs of the results in Sections  2 and  3 it appeals to) and amounts to an effective algorithm for finding a normal form for S L N ( Z )   for N ≥ 3   – that is, for every ℳ ∈ S L N ( Z )   , a word w ℳ   on a fixed finite generating set and representing ℳ   .
Equivalently, a normal form is a choice for all ℳ   of path in the Cayley graph from the identity to ℳ   . By homogeneity, it amounts to a means of navigating between any two vertices in the graph.
Our normal form for S L N ( Z )   is of linearly bounded length ; that is, there exists K > 0   such that for all ℳ ∈ S L N ( Z )   , the length of w ℳ   is at most K   times the length ℓ ( ℳ )   of the shortest word that represents ℳ   . This is because, the length of w ℳ   is at most C 2 log | | ℳ | |   , on account of its role in the proof of Theorem  4.1 , and C 2 log | | M | | ≤ ( C 2 / C 1 ) ℓ ( ℳ )   .
The author's original motivation for embarking on the work in this article was a potential application to the construction of van Kampen diagrams to establish certain isoperimetric functions (concerning filling loops with discs):
a long-standing claim of Thurston, originally quoted in [?]  and repeated in [?,§5.A8̇] , is that SL N ( Z )   admits a quadratic isoperimetric function for all N ≥ 4   . By contrast, Epstein and Thurston showed that the minimal isoperimetric function for S L 3 ( Z )   grows at least exponentially [?,Chapter 10] . By a theorem of Gromov [?,§5A7̇] , S L 3 ( Z )   admits an exponential isoperimetric function. The author hopes the normal form will be of use towards proving Thurston's assertion and giving an elementary proof of Gromov's result.
However there may be formidable obstacles; the geometry of the normal form has to be complicated in the following sense. For N ≥ 3   , no normal form for S L N ( Z )   of linearly bounded length can (either synchronously or asynchronously ) fellow-travel. This result was proved by Epstein and Thurston [?,Chapter 10] to show that S L N ( Z )   is not automatic for N ≥ 3   ; they use isoperimetric inequalities concerning filling ( N − 2 )   -spheres with ( N − 1 )   -balls (we mentioned the case N = 3   above).
Finally, in Section  5 , we apply similar techniques to S L N ( F p )   . We find a normal form and prove the following result about Cayley graph diameter. Theorem  5.1 There exists C > 0   such that for all N ≥ 3   and primes p   , D i a m C a y ( S L N ( F p ) , { e i j | i ≠ j } ) ≤ C N 2 log p .   We remark, for comparison, that a lower bound on the diameter of a constant times ( N 2 / log N ) log p   follows from | S L N ( F p ) | ∼ p N 2 − 1   because | { e i j | i ≠ j } | = N 2 − N   .
Define A N : = ( 1 1 1 1 . . . 1 ) , ℬ N : = ( 0 1 0 1 0 . . . . . . 1 ( − 1 ) N − 1 0 ) .   In Lemma  5.2 (which is due to M. Kassabov) we show using elementary, constructive means that every e i j   equals a word in A N ± 1   and ℬ N ± 1   of length at most 10 N   . Applying this to Theorem  5.1 we get:
Corollary 1.1 There exists C > 0   such that for all N ≥ 3   and primes p   , D i a m C a y ( S L N ( F p ) , { A N , ℬ N } ) ≤ C N 3 log p .  
Lubotzky [?]  explains a non-constructive proof that given N ≥ 3   and a generating set X   for S L N ( Z )   , there exists K > 0   , that will depend on N   and potentially (see Problem  1.5 below) on X   , such that D i a m C a y ( S L N ( F p ) , X ) ≤ K log p   for all primes p   : since S L N ( Z )   enjoys Property (T ) for N ≥ 3   , the graphs { C a y ( S L N ( Z / n Z ) , X ) | n ∈ N }   are a family of expanders, and the result follows. This article supplies an elementary, constructive proof that avoids the big guns of Property (T ) and Selberg's Theorem. The prior absence of such a proof is lamented on of [?,page102] .
The argument above can be made quantitative as follows to yield a result that is weaker than that of Theorem  5.1 in that it gives N 3   in place of the N 2   term in the estimate. Kassabov [?] , extending methods of Shalom [?] , [?] , shows that the Kazhdan constant for S L N ( F p )   with respect to { e i j | i ≠ j }   is at least k : = ( 31 N + 700 ) − 1   . Define Γ N , p : = C a y ( S L N ( F p ) , { e i j | i ≠ j } )   .
The first non-zero eigenvalue λ 1   of the discrete Laplacian on l 2 ( Γ N , p )   is 1 − s   where s   is the spectral gap; s ≥ k 2 / 2   by [?] ; and D i a m Γ N , p ≤ − ( log 2 | S L N ( F p ) | ) / ( log λ 1 )   by [?,Proposition 5.24] . In fact, any upper bound on diameter obtained this way is also an upper bound on mixing time of the random walk on the Cayley graph, and so Theorem  5.1 suggests that, as is often the case, mixing time and diameter differ for Γ N , p   .
It is an open question 1   [?,Problem8.1.3] whether the N 3   of Corollary  1.1 can be improved to N 2   . Such a result would be best possible because | S L N ( F p ) | ∼ p N 2 − 1   . Lubotzky, himself, gets close by proving with Babai and Kantor:
Proposition 1.2 [?] , [?,Proposition8.1.7] There exists C > 0   such that for all N ≥ 3   and primes p   , there is a set S   of three generators for S L N ( F p )   such that D i a m C a y ( S L N ( F p ) , S ) ≤ C N 2 log p .   In fact, S   can be taken to be { A N , ℬ N , C N }   where A N   and ℬ N   are defined above and C N : = e 12 e 21 − 1 e 12   .
The proof in [?]  appeals to Selberg's Theorem, but the proof in [?]  is constructive and elementary save that “unnatural” generators of S L 2 ( F p ) ≤ S L N ( F p )   are used in place of A N   and C N   . An alternative route to Corollary  1.1 is to apply Lemma  5.2 to Proposition  1.2 .
The following problems provide a wider context for the study of diameters of Cayley graphs of S L N ( F p )   .
Problem 1.3 Fix N ≥ 3   . Does S L N ( Z )   enjoy uniform Property (T )?
Problem 1.4 (An Independence Problem for S L N ( Z )   .) Fix N ≥ 3   . Is { C a y ( S L N ( Z ) / H , X ) | [ S L N ( Z ) : H ] < ∞ , 〈 X 〉 = S L N ( Z ) }   a family of expanders?
Problem 1.5 Fix N ≥ 2   . Does there exist K > 0   such that for all generating sets X   for S L N ( Z )   and all primes p   D i a m C a y ( S L N ( F p ) , X ) ≤ K log p ?  
For fixed N ≥ 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 ( Z )   enjoy uniform Property ( τ   ) with respect to congruence subgroups (“The Selberg Property” [?] ), and is { C a y ( S L 2 ( Z / m Z ) , X ) | 〈 X 〉 = S L 2 ( Z ) }   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 ( Z )   and primes p   for which C a y ( S L 2 ( F p ) , X )   forms a family of expanders.
We briefly mention related results for S L N ( Z )   and S L N ( F p )   when N = 2   .
Property ( τ   ) is enjoyed by S L 2 ( Z )   as a consequence of Selberg's Theorem (see [?] , [?] , [?] ), and so for any fixed finite generating set X   for S L 2 ( Z )   , we find { C a y ( S L N ( F p ) , X ) | p prime }   is a family of expanders. So there exists K > 0   such that D i a m C a y ( S L 2 ( F p ) , X ) ≤ K log p   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 ( F p )   to elements of S L 2 ( Z )   with short word representations [?] . But Larsen [?]  has given an algorithm that produces word representations of length O ( log p log log p )   . 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 P S L 2 ( Z )   such that 〈 X 〉   is a p 2   -dense subgroup of P S L 2 ( Z )   D i a m C a y ( P S L 2 ( Z / p n Z ) , X ) = c log d | P S L 2 ( Z / p n Z ) | ,   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 D i a m C a y ( S L 2 ( Z / p n Z ) , X ) ≤ c log d | S L 2 ( Z / p n Z ) |   for all generating sets X   for S L 2 ( 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 ( F p )   to me, and to Karen Vogtmann for encouragement to investigate Thurston's claims about isoperimetric function for S L N ( Z )   .
I additionally wish to thank Martin Kassabov for providing Lemma  5.2 , improving a lemma in an earlier version of this article.

1   Added 31st January, 2005: this question has been answered in the affirmative by M. Kassabov and the author.

2 Compressing powers e i j m  

This section is devoted to proving the following result about representing powers e i j m   in S L N ( Z )   by words of length O ( log ( 1 + | m | ) )   .
Proposition 2.1 Suppose N , m , i , j ∈ Z   with N ≥ 3   , with 1 ≤ i , j ≤ N   , and with i ≠ j   . There exists a word w m ∈ { e p q ± 1 | 1 ≤ p , q ≤ N , p ≠ q } ◆   such that w m = e i j m   in S L N ( Z )   and ℓ ( w ) ≤ 4 + 6 log τ ( 1 + | m | 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 non-negative integers n   , the words
e 23 − 1 ( e 23 e 32 ) − n e 13 − 1 ( e 23 e 32 ) n e 23 − 1 ( e 23 e 32 ) − n e 13 ( e 23 e 32 ) n e 23 2 ,   and e 23 − 1 ( e 23 e 32 ) − n e 12 − 1 ( e 23 e 32 ) n e 23 − 1 ( e 23 e 32 ) − n e 12 ( e 23 e 32 ) n e 23 2  
equal e 13 F 2 n   and e 13 F 2 n + 1   , respectively, in S L 3 ( 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 A − → ℬ ℬ A   .
( 1 0 0 0 1 0 0 0 1 )   − − − − − → e 23 2   ( 1 0 0 0 1 2 0 0 1 )   − − − − − → ( e 23 e 32 ) n   ( 1 0 0 0 F 2 n + 1 F 2 n + 3 0 F 2 n F 2 n + 2 )   − − − − → e 13   ( 1 F 2 n F 2 n + 2 0 F 2 n + 1 F 2 n + 3 0 F 2 n F 2 n + 2 )   − − − − − → ( e 23 e 32 ) − n   ( 1 F 2 n F 2 n + 2 0 1 2 0 0 1 )   − − − − → e 23 − 1   ( 1 F 2 n F 2 n + 2 0 1 1 0 0 1 )   − − − − − → ( e 23 e 32 ) n   ( 1 F 2 n F 2 n + 2 0 F 2 n + 1 F 2 n + 2 0 F 2 n F 2 n + 1 )   − − − − → e 13 − 1   ( 1 0 F 2 n 0 F 2 n + 1 F 2 n + 2 0 F 2 n F 2 n + 1 )   − − − − − → ( e 23 e 32 ) − n   ( 1 0 F 2 n 0 1 1 0 0 1 )   − − − − → e 23 − 1   ( 1 0 F 2 n 0 1 0 0 0 1 )  
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
m = F k 1 + F k 2 + ⋯ + F k r , (1)
with k 1 ≥ 2   and k j + 1 − k j ≥ 2   for all 1 ≤ j < r   .
In fact, F k r   is the largest Fibonacci number no bigger than m   , and F k r − 1   is the largest no bigger than m − F k r   , and so on. Recall that F n = ( τ n − ( − τ ) − n ) / 5   for all n   , where τ : = ( 1 + 5 ) / 2   , and so
F n ≥ τ n − 1 5 . (2)
Thus, as F k r ≤ m   ,
k r ≤ log τ ( 1 + m 5 ) . (3)
Lemma 2.3 Suppose m   is a positive integer expressed as in ( 1 ). Write m = ( F k ^ 1 + F k ^ 2 + ⋯ + F k ^ r ^ ) + ( F k ¯ 1 + F k ¯ 2 + ⋯ + F k ¯ r ¯ )   where k ^ 1 < … < k ^ r ^   are the even numbers amongst k 1 , … , k r   and k ¯ 1 < … < k ¯ r ¯   are the odd numbers. Let n   be the integer such that either 2 n = k r   or 2 n + 1 = k r   . Let u m   be the word a n b n ( e 23 e 32 ) … a 2 b 2 ( e 23 e 32 ) a 1 b 1 ( e 23 e 32 )   in which a i = e 13   if 2 i ∈ { k ^ 1 , … , k ^ r ^ }   and is the empty string otherwise, and b i = e 12   if 2 i + 1 ∈ { k ¯ 1 , … , k ¯ r ¯ }   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 ( e 23 e 32 ) − n v m e 23 − 1 ( e 23 e 32 ) − n u m e 23 2 .   Then w m   equals e 13 m   in S L 3 ( Z )   and has length
ℓ ( w m ) ≤ 4 + 6 log τ ( 1 + m 5 ) . (4)
Proof. Lemma  2.2 is a special case of this lemma: when m = F 2 n   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 2 n + 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 , … , r   .
( 1 0 0 0 1 2 0 0 1 )   − − − − − → u n   ( 1 ∑ F k i ∑ F k i + 2 0 F 2 n + 1 F 2 n + 3 0 F 2 n F 2 n + 2 )   − − − − − − − − − → ( e 23 e 32 ) − n   ( 1 ∑ F k i ∑ F k i + 2 0 1 2 0 0 1 )   − − − − − − − − − → v m e 23 − 1   ( 1 0 ∑ ( F k i + 2 − F k i + 1 ) 0 F 2 n + 1 F 2 n + 2 0 F 2 n F 2 n + 1 )   − − − − − − − − − → e 23 − 1 ( e 23 e 32 ) − n   ( 1 0 ∑ F k i 0 1 0 0 0 1 ) .  
The length of w m   is 4 + 8 n + 2 r   , from which we get ( 4 ) by using ( 3 ), r ≤ k r   and n ≤ 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 , … , a i + 1 N )   is produced from the previous k   -tuple ( a i 1 , … , 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 , … , a i N   . (To resolve dead-heats, take p   minimal, and then take q   minimal amongst the remaining indices.) Define a i + 1 p : = a i p ± a i p   , with the sign chosen so that | a i + 1 p | < | a i p |   , and define a i + 1 j : = a i j   for all j ≠ 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 g c d ( − 32 , 8 , − 12 ) = 4   :
( − 32 , 8 , − 12 ) ↦ ( − 20 , 8 , − 12 ) ↦ ( − 8 , 8 , − 12 ) ↦ ( − 8 , 8 , − 4 )   ↦ ( 0 , 8 , − 4 ) ↦ ( 0 , 4 , − 4 ) ↦ ( 0 , 0 , − 4 ) .   There is a non–deterministic version of this algorithm in which obtaining ( a i + 1 1 , … , a i + 1 N )   from ( a i 1 , … , 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 g c d ( m , n )   by the (deterministic) subtractive version of Euclid's algorithm, where m   is uniformly distributed in the range 1 ≤ m ≤ n   , is 6 π − 2 ( ln n ) 2 + O ( log n ( log log n ) 2 )   . We will show that the worst–case non–deterministic complexity of Euclid's algorithm for computing the g c d   of N ≥ 3   integers ( a 1 , … , a N )   is O ( log n )   , where n : = max { | a 1 | , … , | a N | }   . (In particular, the greatest common divisor of two integers ( a 1 , a 2 )   can be calculated non-deterministically in O ( log ( n ) )   steps by starting with ( a 1 , a 2 , 0 )   .) That is, we prove:
Theorem 3.1 Suppose ( a 1 , … , a N )   is an N   -tuple of integers, not all zero, and N ≥ 3   . Define n : = max { | a 1 | , … , | a N | }   . There is a constant K > 0   , independent of n   and N   , such that there is a sequence of no more than K ( N − 1 ) ( 1 + log n )   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 , … , k − 1   there is some integer q i   such that either ( a i + 1 = a i ± q i b i   and b i + 1 = b i   ), or ( a i + 1 = a i   and b i + 1 = b i ± 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 ≥ 3   , Proposition  2.1 gives us a word w q i   that has length at most 4 + 6 log τ ( 1 + q i 5 ) )   and that, reading right-to-left, describes a sequence of steps with the same effect. (The step described by the letter e p q ± 1   corresponds to left-multiplying the transpose of the N   -tuple. The entries a 3 , … , a N   in the N   -tuple may be disturbed in the course of these steps, but are recovered.) Define c i : = max { | a i | , | b i | }   . Then q i ≤ c i / c i + 1   and q 0 ≤ n   . So it is possible to get from ( a 0 , b 0 )   to ( a k , b k )   in S   steps where S ≤ ∑ i = 0 k − 1 ( 4 + 6 log τ ( 1 + c i c i + 1 5 ) ) .   But, as c i / c i + 1 ≥ 1   for all 0 ≤ i ≤ k − 1   , and c 0 / c k ≤ n   , this is at most
S ≤ 4 k + 6 ∑ i = 0 k − 1 log τ ( c i c i + 1 ( 1 + 5 ) )
≤ 4 k + 6 ( log τ n + k log τ ( 1 + 5 ) ) . (5)
Now n ≥ F k + 1   by an easy induction. So by inequality ( 2 ) of Section  2  n ≥ τ k + 1 − 1 5 ,   and thus k ≤ − 1 + log τ ( 1 + n 5 )   . This inequality together with ( 5 ) shows there exists K > 0   such that S ≤ K + K log n   .
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 non-zero, 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 g c d ( a 1 , … , 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 g c d ( a 1 , … , 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 ( ± 1 , 0 )   or ( 0 , ± 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 ( 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 w ^   in the images e ^ 12 ± 1   , e ^ 21 ± 1   of e 12 ± 1   , e 21 ± 1   under the natural map S L 2 ( Z ) → → P S L 2 ( Z )   . And P S L 2 ( Z ) ∼ = ( Z / 2 Z ) * ( Z / 3 Z )   , presented by 〈 s ^ , t ^ | s ^ 2 , t ^ 3 〉   , where s = ( 0 − 1 1 0 ) and t = ( 1 1 − 1 0 ) .   Now, s t = e 21   and so ( s t ) n = e 21 n   . And ( s ^ t ^ ) n   is of minimal length amongst all words in { s ^ ± 1 , t ^ ± 1 } ◆   that represent e ^ 21 n   in the free product ( Z / 2 Z ) * ( Z / 3 Z )   . So the minimal length of words in { e 12 ± 1 , e 21 ± 1 } ◆   that equal e 21 n   in S L 2 ( Z )   is n   .
Corollary 3.3 The (worst case ) non-deterministic time complexity of the subtractive version of Euclid's algorithm for finding the greatest common divisor of two integers a , b   with n : = max { | a | , | b | }   is between n   and 2 n   .
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  ′   Suppose ( a 1 , … , a N )   is an N   -tuple of integers, not all zero, where N ≥ 3   , and suppose 1 ≤ k ≤ N   . Define n : = max { | a N − k + 1 | , … , | a N | }   .
There is a constant K > 0   , independent of k , n   and N   , such that there is a sequence of no more than ( k − 1 ) K ( 1 + log n )   steps after which the first N − k   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 ± g c d ( a N − k + 1 , … , a N )   .

4 The Mozes-Lubotzky-Raghunathan 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 semi-simple 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 ℳ   with real entries, | | ℳ | |   denotes the sup-norm, the maximum of the absolute values of the entries.)
Theorem 4.1 Fix N ≥ 3   . Let ℓ ( ℳ )   denote the word length of ℳ ∈ S L N ( Z )   , with respect to a fixed finite generating set. There exist C 1 , C 2 > 0   such that for all ℳ ∈ S L N ( Z )   C 1 log | | ℳ | | ≤ ℓ ( ℳ ) ≤ C 2 log | | ℳ | | .   Moreover, if the generating set is { e i j | i ≠ j }   then C 1   is independent of N   and C 2 ≤ 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 ( Z )   then it holds for all. We will work with the generating set { e i j | i ≠ j }   .
The first inequality is straightforward. The sup-norm of a matrix that is the product of n   matrices in { e i j | i ≠ j }   is at most F n   , and F n   grows exponentially with n   .
The second inequality will take more work. Suppose ℳ ∈ S L N ( Z )   .
Below, is a (well-known) procedure for reducing ℳ   to the identity by row operations. Each row operation corresponds to left-multiplication by some e i j ± 1   and so a word w ∈ { e i j ± 1 | i ≠ j } ◆   that equals ℳ   in S L N ( Z )   can be extracted.
  • ( 1   ) Convert ℳ   to an upper triangular matrix whose diagonal entries are all ± 1   , as follows.
    • ( 1 1   ) Run Euclid's algorithm on the first column. This will leave all entries zero except one that is ± 1   , because det ℳ = 1   . Let i 1   be the row containing the non-zero entry in the first column.
      If i 1 ≠ 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 ± 1   and lies in row i 2   . If i 2 ≠ 2   then premultiply by e 2 i 2 e i 2 2 − 1 e 2 i 2   .
    • .
      .
      .
    • ( 1 N − 1   ) Run Euclid's algorithm on the entries in rows N − 1   and N   of the ( N − 1 )   -st column, to make one entry 0   and the other ± 1   . Then, if necessary, premultiply by e N − 1 , N e N , N − 1 − 1 e N − 1 , N   to get an upper triangular matrix.
  • ( 2   ) Get a matrix ( m i j )   for which all the entries on the diagonal are 1 by premultipling by at most N / 2   matrices ( e i j e j i − 1 e i j ) 2   that reverse the signs of all the entries in rows i   and j   .
  • ( 3   ) Clear all the above–diagonal entries in ( m i j )   , 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 … e N − 1 , N − m N − 1 , N   .
As it stands, the number of e i j ± 1   used in the procedure above may wildly exceed log | | ℳ | |   on account of steps ( 1   ) and ( 3   ). However, we can accelerate ( 1 1   )–( 1 N − 1   ) as per Theorem  3.1  ′   . Define ℳ 0 : = ℳ   . Performing ( 1 1   ) then takes at most k 1 : = ( N − 1 ) K ( 1 + log | | ℳ | | )   steps and leaves a matrix ℳ 1   such that | | ℳ 1 | | ≤ | | ℳ 0 | | F k 1 + 2   . And, proceeding inductively, ( 1 i   ) costs at most k i : = ( N − i ) K ( 1 + log | | ℳ i − 1 | | )   steps and leaves a matrix ℳ i   with | | ℳ i | | ≤ | | ℳ i − 1 | | F k i + 2   .
So there is a constant C > 0   such that for all 1 ≤ i ≤ N − 1   ,
k i ≤ K N ( 1 + log | | ℳ i − 1 | | ) and
log | | ℳ i | | ≤ C k i + log | | ℳ i − 1 | | .
These inequalites and induction can be used to establish that for 1 ≤ i ≤ N  
log | | ℳ i − 1 | | ≤ ( 1 + log | | ℳ | | ) ( 1 + C K N ) i − 1 − 1 , (6)
and for all 1 ≤ i ≤ N − 1  
k i ≤ K N ( 1 + log | | ℳ | | ) ( 1 + C K N ) i − 1 .
So there is a constant C ′ > 0   , independent of ℳ   and N   , such that the contribution of ( 1   ) to ℓ ( w )   is at most ∑ i = 1 N − 1 k i ≤ C ′ N N − 1 log | | ℳ | |   .
The contribution of step ( 2   ) to ℓ ( w )   is at most 3 N   . To assess the contribution of step ( 3   ), first note that | m i j | ≤ | | ℳ i | |   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 ( N − 1 ) / 2   terms e i j − m i j   as per Proposition  2.1 , we see that the effect of step ( 3   ) can be achieved whilst contributing at most
C ′ + C ′ ( 1 + log | | ℳ | | ) ∑ i = 1 N − 1 ( N − i ) ( 1 + C K N ) i (7)
to ℓ ( w )   , for some constant C ′ > 0   independent of ℳ   and N   . But the summation term in ( 7 ) is at most a constant times 1 + N + N 2 + ⋯ + 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 ( F p )   .

We adopt the notation α β : = β − 1 α β   and [ α , β ] = α − 1 β − 1 α β   .
Theorem 5.1 There exists C > 0   such that for all N ≥ 3   and primes p   , D i a m C a y ( S L N ( F p ) , { e i j | i ≠ j } ) ≤ C N 2 log p .  
Proof. Suppose ℳ ∈ S L N ( F p )   . We reduce ℳ   to the identity matrix by successively premultiplying by matrices in { e i j | i ≠ j }   in a similar manner to that used to prove Theorem  4.1 .
First lift the entries in the first column of ℳ   to [ 0 , p − 1 ]   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 non-zero entry to the first row. Next run the accelerated version of the subtractive version of Euclid's algorithm on the lift to [ 0 , p − 1 ]   of all but the first entry of second column, and move the non-zero entry to place 2,2 in the matrix. Continue similarly through all the columns. By Theorem  3.1  ′   , the cost is at most a constant times log p ∑ j = 1 N − 1 ( N − j ) < N 2 log p .   We now have an upper triangular matrix ( m i j )   such that every diagonal entry is non-zero. As p   is prime and the diagonal entries in the matrix are non-zero, we can clear all the N ( N − 1 ) / 2   entries above the diagonal by premultiplying by matrices of the form e i j − m i j   where j > i   . By Proposition  2.1 the effect of premultiplying by e i j − m i j   can be achieved by premultiplying by a sequence of at most a constant times log p   matrices in { e i j ± 1 | i ≠ j }   . So we can reduce ℳ   to a diagonal matrix D = diag ( a 1 , … , a N )   with total cost at most a constant times N 2 log p   .
As a 1   and a 1 a 2   are invertible in F p   , we can convert D   to diag ( 1 , a 1 a 2 , a 3 , … , a N )   by premultiplying by e 12 ± 1 , e 21 ± 1   as follows,
( a 1 0 0 a 2 . . . )   − − − − − − − → e 12 e 21 − 1 e 12   ( 0 a 2 − a 1 0 . . . )   − − − − − − − − → e 12 − a 1 − 1   ( 1 a 2 − a 1 0 . . . )   − − − − − − − → e 21 a 1   ( 1 a 2 0 a 1 a 2 0 )   − − − − − − − − → e 12 − a 2 ( a 1 a 2 ) − 1   ( 1 0 0 a 1 a 2 . . . ) .  
Using Proposition  2.1 the same effect can achieved by pre-multiplying by at most a constant times log p   matrices in { e i j ± 1 | i ≠ j }   . 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 N log p   .
To deduce Corollary  1.1 we use the following lemma, due to M. Kassabov, concerning the matrices A N   and ℬ N   given in Section  1 .
Lemma 5.2 For all 1 ≤ i , j ≤ N   with i ≠ j   it is possible to express e i j   as a word in A N ± 1   and ℬ N ± 1   of length at most 10 N   .
Proof. We will drop the subscripts from A N   and ℬ N   . For all i ≠ j   we have e i , j ℬ = e i + 1 , j + 1 ± 1   where the indices are in { 1 , … , N }   and are taken modulo N   . So it suffices to express all e 1 , 1 + k   , for 1 ≤ k ≤ N − 1   , as words in A ± 1   and ℬ ± 1   of length at most 8 N   .
For k = 2 , … , n   define P k : = e 12 e 23 … e k − 1 , k   . Then P k = A A ℬ ⋯ A ℬ k − 2 = A ℬ − 1 A ℬ − 1 … A ℬ − 1 A ℬ k − 2 .   Now N k : = P k P k − 1 − 1   which, due to cancellations, equals a word of length 4 k − 7   in A ± 1   and ℬ ± 1   , and is
( 1 1 . . . 1 1 1 ⋱ ⋮ ⋮ ⋱ 1 1 1 1 1 Id n − k ) ( 1 − 1 1 ⋱ ⋱ − 1 1 1 Id n − k ) = ( 1 1 1 1 ⋱ ⋮ 1 1 1 Id n − k ) .
For k = 3 , … , n   , we calculate that N k ( ℬ − 1 N k − 1 ℬ ) − 1   is
( 1 1 1 1 ⋱ ⋮ 1 1 1 Id n − k ) ( 1 0 1 − 1 ⋱ . . . 1 − 1 1 Id n − k ) = e 1 k .
So e 1 k   can be expressed as a word of length 8 k − 16   in A ± 1 , ℬ ± 1   .
Tim R. Riley Mathematics Department, 10 Hillhouse Avenue, P.O. Box 208283, New Haven, CT 06520-8283, USA tim.riley@yale.edu, http://www.math.yale.edu/users/riley/