Growth in finite simple groups of Lie type

Abstract:

We prove that if $L$ is a finite simple group of Lie type and $A$ a set of generators of $L$, then either $A$ grows, i.e., $|A^3| > |A|^{1+\varepsilon }$ where $\varepsilon$ depends only on the Lie rank of $L$, or $A^3=L$. This implies that for simple groups of Lie type of bounded rank a well-known conjecture of Babai holds, i.e., the diameter of any Cayley graph is polylogarithmic. We also obtain new families of expanders.

A generalization of our proof yields the following. Let $A$ be a finite subset of $SL(n,\mathbb {F})$, $\mathbb {F}$ an arbitrary field, satisfying $\big |A^3\big |\le \mathcal {K}|A|$. Then $A$ can be covered by $\mathcal {K}^m$, i.e., polynomially many, cosets of a virtually soluble subgroup of $SL(n,\mathbb {F})$ which is normalized by $A$, where $m$ depends on $n$.