Walks on graphs and lattices -- effective bounds and applications

Igor Rivin

paper

Walks on graphs and lattices -- effective bounds and applications

arXiv:math/0703533

Abstract

We consider the following situation: G is a finite directed graph, where to each vertex of G is assigned an element of a finite group Gamma. We consider all walks of length N on G, starting from v_i and ending at v_j To each such walk $w$ we assign the element of Gamma equal to the product of the elements along the walk. The set of all walks of length N from v_i to v_j thus induces a probability distribution $F_{N} o n G amma I n p r e v i o u s w or k w e ha v e g i v e nn ecess a r y an d s u f f i c i e n t co n d i t i o n s f or t h e l imi t a s N g oes t o in f ini t y o f F_{N} t oe x i s t an d t o b e t h e u ni f or m d e n s i t y o n G amma . T h eco n v er g e n ces p ee d i s t h e n e x p o n e n t ia l in N . I n t hi s p a p er w eco n s i d er (G, G amma) w h er e G ammai s a g r o u pp ossess in g K a z h d a n^{'} s p r o p er t y T (or, l essr es t r i c t i v e l y, p r o p er t y t a u w i t h r es p ec tt or e p r ese n t a t i o n s w i t h f ini t e ima g e), an d a f ami l y o f h o m o m or p hi s m s ψ_{k} : G amma - > G amm a_{k} w i t h f ini t e ima g e . E a c h F_{N} in d u ces a d i s t r ib u t i o n$ F_{N, k} on Gamma_k (by push-forward). Our main result is that, under mild technical assumptions, the exponential rate of convergence of $F_{N, k} to the uniform distribution on Gamma_k does not depend on k. As an application, we prove effective versions of the results of the author on the probability that a random (in a suitable sence) element of SL(n, Z) or Sp(n, Z) has irreducible characteristic polynomial, generic Galois group, etc.

References in corpus (1)

Walks on groups, counting reducible matrices, polynomials, and surface and free group automorphisms