2007/03/19 by Igor Rivin, Rivin, Igor
Computer Science · Mathematics · #11G99 #20E05 #57M60 #Coding theory and cryptography #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Number Theory (math.NT) #math.NT #msc:11G99 #msc:20E05 #msc:57M60
paper · pdf · doi:10.48550/arxiv.math/0703533
arxiv created 2007/03/19 · openalex publication_date 2007/03/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 vi and ending at vj 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 vi to vj thus induces a probability distribution FN on Gamma In previous work we have given necessary and sufficient conditions for the limit as N goes to infinity of FN to exist and to be the uniform density on Gamma. The convergence speed is then exponential in N. In this paper we consider (G, Gamma) where Gamma is a group possessing Kazhdan's property T (or, less restrictively, property tau with respect to representations with finite image), and a family of homomorphismsψk: Gamma -> Gammak with finite image. Each FN induces a distribution FN, k on Gammak (by push-forward). Our main result is that, under mild technical assumptions, the exponential rate of convergence of FN, k to the uniform distribution on Gammak 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.