Shortest Nontrivial Laws for Symmetric Groups

Definitions and mathematical statement

For a positive integer $n$, let $S_n$ be the group of permutations of $\{1,\ldots,n\}$, and let $F_2=\langle x,y\rangle$ be the free group on two generators. For $w\in F_2$, let $|w|$ denote the number of letters in its freely reduced expression over $\{x,x^{-1},y,y^{-1}\}$. Thus powers are counted by their expanded length. This standard word-length convention makes explicit a convention not specified in the supplied statement.

For $\sigma,\tau\in S_n$, write $w(\sigma,\tau)$ for the image of $w$ under the homomorphism $F_2\to S_n$ sending $x$ to $\sigma$ and $y$ to $\tau$. A nontrivial two-variable law for $S_n$ is a word $w\ne 1$ in $F_2$ such that \[ \forall\sigma\in S_n\;\forall\tau\in S_n,\qquad w(\sigma,\tau)=\operatorname{id}. \] Here "nontrivial" refers to the element of the free group. Membership in $F_2$ does not require both generators to occur; the supplied statement imposes no such additional condition.

Define \[ L(n)=\min\left\{|w|:w\in F_2\setminus\{1\},\ \forall\sigma,\tau\in S_n,\ w(\sigma,\tau)=\operatorname{id}\right\}. \] Problem. Determine how small $L(n)$ can be, in particular its asymptotic growth as $n\to\infty$. The asymptotic emphasis comes from the supplied background; the source does not specify a conjectured formula or the desired precision of an asymptotic determination.

The supplied dated curation labels this problem open and states that known constructions are quasi-polynomial whereas even the best lower bounds remain linear. These are supplied literature assessments, not independently verified mathematical assertions in this draft.

Short English statement

Find the shortest nonidentity reduced word in two free generators that becomes the identity under every substitution of two permutations from $S_n$. The main target suggested by the supplied background is the growth of this minimum length as $n$ tends to infinity.

Sources

• Local UnsolvedMath registry, supplied record with permanent ID $30003130$, title "Shortest Nontrivial Laws for Symmetric Groups," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied; the proposed year is recorded as 2016.
• Supplied report citation: Combinatorics and Probability (2017), Oberwolfach Reports, DOI 10.4171/owr/2016/22, pp. 1189--1257. https://doi.org/10.4171/owr/2016/22. The report title's year and the DOI's year component differ in the supplied record; this draft retains both without resolving the discrepancy.
• Kozma and Thom, Divisibility and Laws in Finite Simple Groups. Supplied literature link: https://arxiv.org/abs/1403.2324.
• Beker, Milićević, and Mrazović, A Note on the Shortest Law. Supplied literature link: https://arxiv.org/abs/2607.08557.
• Literature assessment date: 2026-08-21. This is supplied dated curation derived from the OWR record, not independently verified here. It labels the problem open and reports quasi-polynomial constructions and lower bounds that remain linear; time-sensitive status and cited claims require independent verification.