×

Growth and generation in \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\). (English) Zbl 1213.20045

From the introduction: We show that every subset of \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\) grows rapidly when it acts on itself by the group operation. It follows readily that, for every set of generators \(A\) of \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\), every element of \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\) can be expressed as a product of at most \(O((\log p)^c)\) elements of \(A\cup A^{-1}\), where \(c\) and the implied constant are absolute.
1.1. Background. Let \(G\) be a finite group. Let \(A\subset G\) be a set of generators of \(G\). By definition, every \(g\in G\) can be expressed as a product of elements of \(A\cup A^{-1}\). We would like to know the length of the longest product that might be needed; in other words, we wish to bound from above the diameter \(\text{diam}(\Gamma(G,A))\) of the Cayley graph of \(G\) with respect to \(A\). (The Cayley graph \(\Gamma(G,A)\) is the graph \((V,E)\) with vertex set \(V=G\) and edge set \(E=\{(ag,g):g\in G,\;a\in A\}\). The diameter of a graph \(X=(V,E)\) is \(\max_{v_1,v_2\in V}d(v_1,v_2)\), where \(d(v_1,v_2)\) is the length of the shortest path between \(v_1\) and \(v_2\) in \(X\).)
If \(G\) is Abelian, the diameter can be very large: if \(G\) is cyclic of order \(2n+1\), and \(g\) is any generator of \(G\), then \(g^n\) cannot be expressed as a product of length less than \(n\) on the elements of \(\{g,g^{-1}\}\). However, if \(G\) is non-Abelian and simple, the diameter is believed to be quite small:
Conjecture (Babai, [L. Babai and Á. Seress, Eur. J. Comb. 13, No. 4, 231-243 (1992; Zbl 0783.20001)]). For every non-Abelian finite simple group \(G\), \[ \text{diam}(\Gamma(G,A))\ll(\log|G|)^c,\tag{1.1} \] where \(c\) is some absolute constant and \(|G|\) is the number of elements of \(G\).
This conjecture is far from being proved. Even for the basic cases, viz., \(G=A_n\) and \(G=\text{PSL}_2(\mathbb{Z}/p\mathbb{Z})\), the conjecture has remained open until now; these two choices of \(G\) seem to present, already, many of the main difficulties of the general case.
Work on both kinds of groups long predates the general conjecture in [loc. cit.]. Let us focus on \(G=\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\). There are some classical results for certain specific generators. Let \(A=\left\{\left(\begin{smallmatrix} 1&1\\ 0&1\end{smallmatrix}\right),\left(\begin{smallmatrix} 1&0\\ 1&1\end{smallmatrix}\right)\right\}\). Selberg’s spectral-gap theorem for \(\text{SL}_2(\mathbb{Z})\backslash\mathbb{H}\) [A. Selberg, Proc. Symp. Pure Math. 8, 1-15 (1965; Zbl 0142.33903)] implies that \(\{\Gamma(\text{SL}_2(\mathbb{Z}/p\mathbb{Z}),A)\}_{p\geq 5}\) is a family of expander graphs. It follows easily that \(\text{diam}(\Gamma(\text{SL}_2(\mathbb{Z}/p\mathbb{Z}),A))\ll\log p\). Unfortunately, this argument works only for a few other choices of \(A\). For example, no good bounds were known up to now for \(\text{diam}(\Gamma(\text{SL}_2(\mathbb{Z}/p\mathbb{Z}),A))\) with, say, \(A=\left\{\left(\begin{smallmatrix} 1&3\\ 0&1\end{smallmatrix}\right),\left(\begin{smallmatrix} 1&0\\ 3&1\end{smallmatrix}\right)\right\}\), let alone for general \(A\), uniformly on \(A\) or not.
1.2. Results. We prove the conjecture for \(G=\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\).
Main Theorem. Let \(p\) be a prime. Let \(A\) be a set of generators of \(G=\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\). Then the Cayley graph \(\Gamma(G,A)\) has diameter \(O((\log p)^c)\), where \(c\) and the implied constant are absolute.
The theorem is a direct consequence of the following statement.
Key Proposition. Let \(p\) be a prime. Let \(A\) be a subset of \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\) not contained in any proper subgroup.
(a) Assume that \(|A|<p^{3-\delta}\) for some fixed \(\delta>0\). Then \(|A\cdot A\cdot A|>c|A|^{1+\varepsilon}\), where \(c>0\) and \(\varepsilon>0\) depend only on \(\delta\).
(b) Assume that \(|A|>p^\delta\) for some fixed \(\delta>0\). Then there is an integer \(k>0\), depending only on \(\delta\), such that every element of \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\) can be expressed as a product of at most \(k\) elements of \(A\cup A^{-1}\).

MSC:

20G40 Linear algebraic groups over finite fields
20F05 Generators, relations, and presentations of groups
20F69 Asymptotic properties of groups
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
11B75 Other combinatorial number theory
20D60 Arithmetic and combinatorial problems involving abstract finite groups
PDFBibTeX XMLCite
Full Text: DOI arXiv Link