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 l₂-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 = SL₂(q) (2 x 2 matrices with determinant 1 over 𝔽_q) where m ∼ n^1/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 Δ = n²/(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 SL₂(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 = SL₂(q) it follows that if A ⊆ G and |A| ≥ n^2/3+ε then A^t = 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].

REFERENCES

• 1: {APPS} M. Abért, P. P. Pálfy, L. Pyber, B. Szegedy: Groups of finite abelian or solvable width. In preparation
• 2: {AS} N. Alon, J. H. Spencer: The Probabilistic Method. Wiley, 1992.
• 3: László Babai, On the diameter of Eulerian orientations of graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.822-831, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109648]
• 4: László Babai , Ákos Seress, On the diameter of permutation groups, European Journal of Combinatorics, v.13 n.4, p.231-243, July 1992 [doi>10.1016/S0195-6698(05)80029-0]
• 5: {BaSo} L. Babai, V. T. Sós: Sidon sets in groups and induced subgraphs of Cayley graphs. Europ. J. Combinatorcs 6 (1985), 101--114.
• 6: {BoG} J. Bourgain, A. Gamburd: Uniform expansion bound for Cayley graphs of SL₂(Z/pZ). Ann. Math. to appear.
• 7: {BoKT} J. Bourgain, N. Katz, T. Tao: A sum-product estimate in finite fields and applications. Geom. and Funct. Anal. 14 (2004), 27--57.
• 8: {Ca} R. Carter: Simple groups of Lie type. Pure and Applied Mathematics, Vol. 28. John Wiley & Sons, London-New York-Sydney, 1972.
• 9: {CGW} F. R. K. Chung, R. L. Graham, R. M. Wilson: Quasi-random graphs. Combinatorica 9 (1989), 345--362.
• 10: {CL} Problems presented at the workshop on Recent Trends in Additive Combinatorics, collected by E. Croot and V. F. Lev. American Institute of Mathematics, Palo Alto, 2004. http://www.aimath.org/WWW/additivecomb/additivecomb.pdf
• 11: {DSV} G. Davidoff, P. Sarnak, A. Valette: Elementary Number Theory, Group Theory, and Ramanujan Graphs. Cambridge U. Press, 2003.
• 12: {Fr} G. Frobenius: Über Gruppencharactere. Sitzungsber. Königl. Preuß. Akad. Wiss. Berlin (1896), 985--1021.
• 13: W. T. Gowers, Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs, Combinatorics, Probability and Computing, v.15 n.1-2, p.143-184, January 2006 [doi>10.1017/S0963548305007236]
• 14: {Gow2} W. T. Gowers: Quasirandom groups. Manuscript, 2006.
• 15: {Ha} Y. O. Hamidoune: An application of connectivity theory in graphs to factorizations of elements in groups. Eur. J. Comb. 2 (1981) 349--355.
• 16: {He} H. A. Helfgott: Growth and generation in SL₂(Z/pZ). Ann. Math. to appear.
• 17: {HruP} E. Hrushovski, A. Pillay: Definable subgroups of algebraic groups over finite fields. J. Reine Angew. Math. 462 (1995), 69--91.
• 18: {KLN} M. Kassabov, A. Lubotzky, N. Nikolov: Finite simple groups as expanders. Proc. Nat. Acad. USA 103 (2006), 6116--6119.
• 19: Kiran S. Kedlaya, Large product-free subsets of finite groups, Journal of Combinatorial Theory Series A, v.77 n.2, p.339-343, Feb. 1997 [doi>10.1006/jcta.1997.2715 ]
• 20: {LanS} V. Landazuri, G. Seitz: On the minimal degrees of projective representations of the finite Chevalley groups. J. Algebra 32 (1974), 418--443.
• 21: {LP} M. W. Liebeck, L. Pyber: Finite linear groups and bounded generation. Duke Math. J. 107 (2001), 159--171.
• 22: {LuPS} A. Lubotzky, R. Phillips, P. Sarnak: Ramanujan graphs. Combinatorica 8 (1988), 261--277.
• 23: {KL} P. Kleidman, M. Liebeck: The subgroup structure of the finite classical groups. LMS Lecture Notes 129, Cambridge Univ. Press 1990.
• 24: {Ma} G. Margulis: Explicit group-theoretical constructions of combinatorial schemes and their applications to the design of expanders and concentrators. J. Problems Info. Transmission 24/1 (1988), 39--46.
• 25: {Ni} N. Nikolov: A product decomposition for classical quasisimple groups. J. Group Th. 10 (2007), 43--53.
• 26: {NP} N. Nikolov, L. Pyber: Product decomposition of quasirandom groups and a Jordan type theorem. Manuscript. arXiv:math/0703343 (March 2007)
• 27: {NS} N. Nikolov, D. Segal: On finitely generated profinite groups II. Products in quasisimple groups. Ann. Math. 165 (2007), 239--273.
• 28: {Ol} J. E. Olson: On the sum of two sets in a group. J. Number Theory 18 (1984), 110--120.
• 29: {SarX} P. Sarnak, X. Xue: Bounds for multiplicities of automorphic representations. Duke Math. J. 64 (1991), 207--227.
• 30: {Shv} A. Shalev: Word maps, conjugacy classes, and a non-commutative Waring-type theorem. Ann. Math. to appear
• 31: {Shm} Y. Shalom: Bounded generation and Kazhdan's property (T). Publ. Math. IHES 90 (1999/2001) 145--168.
• 32: {TaV} T. Tao, Van H. Vu: Additive Combinatorics. Cambridge University Press, 2006.
• 33: {Th} A. Thomason: Pseudo-random graphs. In: Proc. Conf. on Random Graphs, Poznań 1985. (M. Karoński, ed.) Annals of Discrete Math. 33 (North Holland 1987), 307--331.
• 34: {Wig} E. P. Wigner: Über die elastischen Eigenschwingungen symmetrischer Systeme. Nachr. der Ges. der Wiss. zu Göttingen. Math-Phys. Kl. (1930) 133--146.
• 35: {Wil} J. S. Wilson: On simple pseudofinite groups. J. London Math. Soc. 51 (1995), 471--490.