Navigating in the Cayley Graphs of SLN(Z) and SLN(Fp)

TR Riley

Research output: Contribution to journalArticle (Academic Journal)

10 Citations (Scopus)

Abstract

We give a nondeterministic algorithm that expresses elements of SLN(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 nondeterministic time-complexity of the subtractive version of Euclid's algorithm for finding the greatest common divisor of Nu >= 3 integers a(1)(,...,)a(Nu) is at most a constant times N log max {vertical bar a(1)vertical bar(,...,)vertical bar a(Nu)vertical bar}. This leads to an elementary proof that for Nu >= 3 the word metric in SLNu(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 SLN(F-p) with respect to the generating set {e(ij) vertical bar i not equal j} is at most KN2 logp.
Translated title of the contributionNavigating in the Cayley Graphs of SLN(Z) and SLN(Fp)
Original languageEnglish
Pages (from-to)215 - 229
Number of pages15
JournalGeometriae Dedicata
Volume113 (1)
DOIs
Publication statusPublished - Jun 2005

Bibliographical note

Publisher: Springer

Fingerprint Dive into the research topics of 'Navigating in the Cayley Graphs of SL<sub>N</sub>(Z) and SL<sub>N</sub>(F<sub>p</sub>)'. Together they form a unique fingerprint.

Cite this