Mathematics – Group Theory
Scientific paper
2005-04-06
Geometriae Dedicata, 113(1), pages 215-229, 2005
Mathematics
Group Theory
18 pages, no figures
Scientific paper
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 \neq j} is at most K N^2 \log p.
No associations
LandOfFree
Navigating in the Cayley graphs of SL_N(Z) and SL_N(F_p) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Navigating in the Cayley graphs of SL_N(Z) and SL_N(F_p), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Navigating in the Cayley graphs of SL_N(Z) and SL_N(F_p) will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-38369