Shortest Laws in Symmetric Groups

Definitions and mathematical statement

For an integer $n\geq 1$, let $S_n$ be the group of all permutations of $\{1,\ldots,n\}$. For each integer $r\geq 1$, let $F_r=F(x_1,\ldots,x_r)$ be the free group on $r$ generators. For $w\in F_r$, let $|w|$ denote the number of letters in its freely reduced expression over $\{x_1^{\pm1},\ldots,x_r^{\pm1}\}$. A nontrivial law for $S_n$ is an element $w\neq 1$ of some $F_r$ such that \[ w(\sigma_1,\ldots,\sigma_r)=\operatorname{id} \qquad\text{for every }(\sigma_1,\ldots,\sigma_r)\in S_n^r. \] Under the convention that any finite number of variables is allowed, define \[ L(n)=\min\left\{|w|:r\geq 1,\ w\in F_r\setminus\{1\},\ w\text{ is a law for }S_n\right\}. \] This minimum exists, since the nontrivial word $x_1^{n!}$ is a law for $S_n$.

The problem is to determine the asymptotic growth of $L(n)$ as $n\to\infty$. The supplied record does not specify the number of permitted variables or the convention for word length. The definition above explicitly uses arbitrary finite rank and freely reduced letter length. If the intended convention instead fixes two variables, the corresponding quantity is \[ L_2(n)=\min\left\{|w|:w\in F_2\setminus\{1\},\ w(\sigma,\tau)=\operatorname{id}\text{ for every }\sigma,\tau\in S_n\right\}. \] The intended convention requires source confirmation; no equality between these quantities is asserted here. The record also does not specify whether an asymptotic equivalent or an order-of-growth estimate is sought.

The supplied literature assessment, dated $2026\text{-}08\text{-}22$, labels the problem open and reports a lower bound of $\tfrac52 n-O(1)$, an unconditional upper bound of $\exp\!\left(O((\log n)^4\log\log n)\right)$, and that even superlinear growth remains open. These are supplied dated curation claims, not independently verified results; their precise variable conventions and hypotheses have not been established from the supplied excerpts.

Short English statement

Determine how the minimum length of a nonidentity word that evaluates to the identity for every substitution of permutations in $S_n$ grows as $n\to\infty$. The draft explicitly defines reduced word length and allows any finite number of variables, while flagging the unspecified variable convention. The supplied open status and bounds require independent source review.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005887$, title "Shortest Laws in Symmetric Groups," source problem code catalogue entry; project registry locations data/unsolvedmath/problems.json and catalog/problems.json. No proposer is identified in the supplied record; the proposed year is $2024$.
• Supplied report citation: Mini-Workshop: Growth and Expansion in Groups (2024), Oberwolfach Reports, pp. 1005--1040, DOI 10.4171/owr/2024/17. https://doi.org/10.4171/owr/2024/17. No exact page or named attribution for this question is supplied.
• Supplied literature source labeled "current lower bound": https://arxiv.org/abs/2607.08557.
• Supplied literature source labeled "current upper bound": https://ems.press/content/serial-article-files/53103?nt=1.
• Supplied literature source labeled "short laws": https://arxiv.org/abs/1403.2324.
• Literature assessment checked at 2026-08-22: the open label, reported bounds, and claim that superlinear growth remains open are supplied dated curation, not independently verified here. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The registry supplies the statement-status label corrected_verified and says that only formula delimiters, notation, grammar, and typography were repaired. This records the supplied editorial assessment and does not constitute independent mathematical or source verification.