Paper Info
Title
Product growth and mixing in finite groups
Abstract
We prove the following inequality on the convolution of distributions over a finite group G: {display equation} where X, Y are probability distributions over G, the * denotes convolution, U the uniform distribution over G, and || · || the l2-norm; n is the order of G, and m denotes the minimum dimension of nontrivial real representations of G. This inequality can be viewed as a new expansion property of a large class of groups, including all Lie-type simple groups of bounded rank, all of which satisfy m cnβ (where c 0 is an absolute constant and β 0 depends on the rank bound only). Best among them are the groups G = SL2(q) (2 x 2 matrices with determinant 1 over 𝔽q) where m ∼ n1/3/2. We derive applications of the convolution inequality (0.1) to a variety of areas, ranging from stochastic processes to additive combinatorics to group theory. An immediate consequence is a product growth inequality for subsets of G: if A, B ⊆ G then |AB| n/(1 + Δ) where Δ = n2/(m|A||B|). On the one hand, this corollary strengthens a recent result of Gowers which served as the inspiration to the present work; on the other hand, it gives a strong (and best possible) affirmative answer to a problem regarding the product growth of subsets of SL2(q) recently posed by Venkatesh and Green at a conference in the newly flourishing area of "additive combinatorics." Another corollary to the main inequality shows that for groups with large m, mixing in the strongest sense (ℓ∞-norm) occurs more rapidly than expected; we prove that if X, Y, Z are distributions over G then {display equation} This generalizes a result of Gowers. By easy induction, our main inequality generalizes to the convolution of multiple terms and thereby results in rapid mixing estimates for time-inhomogeneous Cayley walks on G. It also gives estimates for the size of the product of several subsets, resulting in diameter estimates for Cayley graphs and tying in with the broad subject of "bounded generation" in group theory. An illustration of the connection to diameters: for G = SL2(q) it follows that if A ⊆ G and |A| ≥ n2/3+ε then At = G where t = O(1/ε); we also show that the elements of G are represented nearly uniformly as words of length t over A. The connection to "bounded generation" is illustrated by one of the main applications of our results: every finite simple group of Lie type of characteristic p is the product of 5 Sylow p-subgroups. - Results of this type are among the ingredients of the recent breakthrough result that all finite simple groups have bounded degree expander Cayley graphs [KLN]; our results improve and greatly simplify these ingredients. The results and techniques used in this paper were inspired by a link between quasirandomness and group representation theory recently found by Gowers [Go].
Year
DOI
Venue
2008
10.5555/1347082.1347110
SODA
Keywords
Field
DocType
main inequality generalizes,display equation,convolution inequality,group theory,product growth inequality,groups g,bounded generation,finite simple group,main inequality,following inequality,finite group,satisfiability,simple group,productivity growth,cayley graph,probability distribution,mixing time,stochastic process,ising model,group representation theory,uniform distribution
Discrete mathematics,Group representation,Combinatorics,Classification of finite simple groups,Sylow theorems,Group theory,Cayley graph,Finite group,Mathematics,Simple group,Bounded function
Conference
ISBN
Citations 
PageRank 
978-0-89871-698-6
3
0.40
References 
Authors
7
3
Name
Order
Citations
PageRank
Laszlo Babai13537573.58
Nikolay Nikolov27218.15
László Pyber3418.92