
Navigating in the Cayley Graphs of SL_{N}(Z) and SL_{N}(F_{p})
Tim R. Riley Geometriae Dedicata, 113(1), pages 215229, 2005. We give a nondeterministic algorithm that expresses elements of SL_{N}(Z), for N>2, 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 nondeterministic timecomplexity of the subtractive version of Euclid's algorithm for finding the greatest common divisor of N>2 integers a_{1}, ..., a_{N} is at most a constant times N log max {a_{1}, ..., a_{N}}. This leads to an elementary proof that for N>2 the word metric in SL_{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>2 and primes p, the diameter of the Cayley graph of SL_{N}(F_{p}) with respect to the generating set {e_{ij}  i \neq j } is at most K N^{2} log p .
