{
  "id": "math/0504091",
  "version": "v1",
  "published": "2005-04-06T04:23:35.000Z",
  "updated": "2005-04-06T04:23:35.000Z",
  "title": "Navigating in the Cayley graphs of SL_N(Z) and SL_N(F_p)",
  "authors": [
    "T. R. Riley"
  ],
  "comment": "18 pages, no figures",
  "journal": "Geometriae Dedicata, 113(1), pages 215-229, 2005",
  "categories": [
    "math.GR",
    "math.CO"
  ],
  "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 \\neq j} is at most K N^2 \\log p.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2005-04-06T04:23:35.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20F05"
    ],
    "keywords": [
      "cayley graph",
      "constant times",
      "word metric",
      "greatest common divisor",
      "matrix norm"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......4091R"
    }
  }
}