Navigating in the Cayley graphs of SL_N(Z) and SL_N(F_p)

DOI10.1007/S10711-005-5230-0MaRDI QIDQ6475347arXivFDO

Publication date 6 April 2005

Symbolic computation and algebraic computation (68W30) Generators, relations, and presentations of groups (20F05) Discrete subgroups of Lie groups (22E40) Linear algebraic groups over finite fields (20G40) Unimodular groups, congruence subgroups (group-theoretic aspects) (20H05)

Abstract: We give a non-deterministic 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 non-deterministic time-complexity 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 n where n := 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} mid i eq j} is at most K N^2 log p.

This page was built for publication: Navigating in the Cayley graphs of SL_N(Z) and SL_N(F_p)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6475347)