## 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 contribution | Navigating in the Cayley Graphs of SL_{N}(Z) and SL_{N}(F_{p}) |
---|---|

Original language | English |

Pages (from-to) | 215 - 229 |

Number of pages | 15 |

Journal | Geometriae Dedicata |

Volume | 113 (1) |

DOIs | |

Publication status | Published - Jun 2005 |