Probabilistic Growth Methods for Linear Algebraic Groups

Definitions and mathematical statement

Let $F$ be a finite field and let $n$ be a positive integer. Write \[ H=\operatorname{SL}_n(F)=\{g\in\operatorname{Mat}_{n\times n}(F):\det(g)=1\}. \] Let $A\subseteq H$ satisfy $\langle A\rangle=H$. Let $\mathcal P_n(F)\subseteq\operatorname{GL}_n(F)$ denote the set of permutation matrices, namely the matrices having exactly one entry equal to $1$ in each row and each column and all other entries equal to $0$. The original problem additionally assumes \[ \mathcal P_n(F)\subseteq A. \] This assumption has an unresolved compatibility qualification: when $n\geq2$ and $F$ has odd characteristic, a transposition matrix has determinant $-1$, so not all permutation matrices belong to $H$. Thus the literal hypotheses have no instances in that case. In characteristic $2$, every permutation matrix does belong to $H$. The source does not specify a characteristic restriction or a replacement for its permutation-matrix assumption; neither is imposed here.

For clarity about the unspecified Cayley-graph convention, define two possible diameters. For a subset $B\subseteq H$, let $B^0=\{1_H\}$, and let $B^k$ be the set of products of exactly $k$ elements of $B$. Define \[ \begin{aligned} D_+(H,A)&=\min\left\{L\in\mathbb Z_{\geq0}:H=\bigcup_{k=0}^{L}A^k\right\},\\ D_{\pm}(H,A)&=\min\left\{L\in\mathbb Z_{\geq0}:H=\bigcup_{k=0}^{L}(A\cup A^{-1})^k\right\}. \end{aligned} \] These are respectively the directed diameter with edges $g\to ga$, $a\in A$, and the undirected diameter allowing multiplication by generators and their inverses. Both are finite because $H$ is finite and $A$ generates $H$. The source writes $\operatorname{diam}(\Gamma(H,A))$ without specifying which convention is intended or assuming $A=A^{-1}$.

Source problem (Problem 1). For generating sets satisfying the stated permutation-matrix assumption, obtain a good upper bound on $\operatorname{diam}(\Gamma(H,A))$. The source tentatively suggests a bound of the form \[ D(H,A)\leq C\left(\log|H|\right)^c, \qquad C>0,\quad c>0, \] for nontrivial $H$, where $D$ must be assigned an intended Cayley-graph convention. The source presents this polylogarithmic bound as a possibility, rather than specifying it as a fixed conjecture. It does not state whether $C$ and $c$ must be independent of $n$, $F$, and $A$, or may depend on the rank. Consequently, it does not determine a unique fully quantified bound. For the trivial group the diameter is $0$.

The accompanying broader methodological question asks whether probabilistic arguments can prove growth results for linear algebraic groups over finite fields; $\operatorname{SL}_n$ is given as an example. No general class of groups, definition of growth, quantitative growth inequality, or required probabilistic method is specified. The concrete diameter question above preserves the additional content of the original statement, but the unresolved qualifications prevent a unique complete conjectural formulation.

Short English statement

The source asks for probabilistic approaches to growth in linear algebraic groups over finite fields. Its concrete example seeks a strong Cayley-graph diameter bound for $\operatorname{SL}_n(F)$ generated by a set containing every permutation matrix, tentatively suggesting a polylogarithmic bound. The permutation-matrix hypothesis conflicts with odd characteristic when $n\geq2$; the graph convention and dependence of the proposed bound on rank are unspecified. These issues require human review.

Sources

• Local UnsolvedMath registry: data/unsolvedmath/problems.json, permanent ID $30005878$, title Probabilistic Growth Methods for Linear Algebraic Groups, source code catalogue entry. The supplied record identifies the original question as Problem 1 and gives proposed year 2024; no individual proposer is supplied.
• Supplied source citation: Mini-Workshop: Growth and Expansion in Groups (2024), Oberwolfach Reports, DOI 10.4171/owr/2024/17, pp. 1005--1040. https://doi.org/10.4171/owr/2024/17. The supplied background describes these reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature source, labelled "Helfgott growth survey": https://arxiv.org/abs/1804.03049.
• Supplied literature source, labelled "OWR report": https://doi.org/10.4171/owr/2024/17.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and states that probabilistic and random-walk methods give important special growth results, while the general question, especially a rank-uniform theory, remains unresolved. This is supplied dated curation derived from the OWR material, not an independently verified literature assessment; its status and cited claims require independent verification.
• The supplied statement-status label is corrected_verified. Its accompanying qualification says that only formula delimiters, notation, grammar, and typography were repaired, with mathematical content and scope preserved. This supplied label does not establish mathematical correctness or resolve the formulation issues above.