Multilinear decay for the Latin squares of random Steiner triple systems

Eberhard, Manners and Mrazović proved that any $n\times n$ Latin square satisfying an operator spectral-gap condition ('A-quasirandomness') has $(e^{-1/2}+o(1))\,n!^2/n^n$ transversals, and showed this covers uniformly random Latin squares as well as multiplication tables of quasirandom groups. They observed that Latin squares arising from Steiner triple systems always fail the spectral condition — the diagonal is a closed class of the associated Markov chain — yet indicated that a uniformly random Steiner triple system should nevertheless satisfy the underlying multilinear decay condition with parameter $\rho=o(1)$ with high probability. This record states that question precisely, as it is left open: is there a function $\rho(n)=o(1)$ such that, with probability $1-o(1)$ as $n\to\infty$, the Steiner-quasigroup Latin square of a uniformly random Steiner triple system of order $n\equiv 1,3\pmod{6}$ satisfies, for every integer $m\ge1$, the bound $|\Lambda(f,g,h)|\le\rho(n)^{m/2}\|f\|_2\|g\|_2\|h\|_2$ over the mean-zero tensor powers of its latin-square tensor? A positive answer is expected to extend the sharp transversal-count asymptotic to this fundamental structured family and to test whether the analytic quasirandomness framework separates algebraic structure from typical structure.

Background

A Latin square of order $n$ is an $n\times n$ array filled with $n$ symbols so that every symbol appears exactly once in each row and each column. A transversal is a set of $n$ entries that shares no row, column, or symbol; equivalently, identifying a Latin square with a set $L\subseteq X\times Y\times Z$ of triples over sets of rows, columns, and symbols (each pair from any two of $X,Y,Z$ lying in exactly one triple), a transversal is a subset of $L$ projecting bijectively onto each of $X$, $Y$, and $Z$. Counting transversals is a classical problem: Kwan showed that almost every $n\times n$ Latin square has $((1+o(1))\,n/e^2)^n$ transversals, and Eberhard, Manners and Mrazović later sharpened the constant, showing that almost every Latin square has $(e^{-1/2}+o(1))\,n!^2/n^n$ transversals.

The method of Eberhard–Manners–Mrazović is analytic. For a Latin square $L\subseteq X\times Y\times Z$ they define the latin-square tensor $\Lambda(f,g,h)=\mathbb{E}_{(x,y,z)\in L}\,f(x)g(y)h(z)$ for functions $f\in L^2(X)$, $g\in L^2(Y)$, $h\in L^2(Z)$ (square-summable complex functions), and more generally $\Lambda$ on the powers $L^m$ (cartesian products, which are again Latin squares of order $n^m$). A loose variant of the circle method expresses the transversal count in terms of $\Lambda$ applied to indicator functions of the set of bijections, and the difficult 'dense minor arc' regime is controlled by a quasirandomness hypothesis. The hypothesis is spectral: define a Markov chain on $X\times Y$ which, from state $(x,y)$, picks $z\in Z$ uniformly at random and moves to the unique $(x',y')$ with $(x,y',z),(x',y,z)\in L$. Writing $A$ for the transition operator and $U$ for the projection to constant functions, $L$ is called A-quasirandom with parameter $\rho$ if $A-U$ has spectral radius at most $\rho$; the chain is connected exactly when $\rho<1$. Every Latin square that is A-quasirandom with a sufficiently small parameter $\rho$ has $(e^{-1/2}+o(1))\,n!^2/n^n$ transversals. Two classes are known to satisfy it: uniformly random Latin squares are A-quasirandom with parameter $o(1)$ with high probability (via substructure results of Kwan, Sah, Sawhney and Simkin), and the multiplication table of a group is A-quasirandom with parameter $1/D$, where $D$ is the minimal dimension of a nontrivial irreducible representation, so on group tables the condition coincides with Gowers's notion of a quasirandom group; in this way the framework recovers, for sufficiently quasirandom groups, the asymptotic form of the Hall–Paige conjecture (which characterises when the multiplication table of a finite group contains a transversal, equivalently when the group admits a complete mapping) previously proved by the same authors.

The spectral condition is only a convenient sufficient condition: all applications of it go through the multilinear decay bound that it implies — for every $m\ge1$, $|\Lambda(f,g,h)|\le\rho^{m/2}\|f\|_2\|g\|_2\|h\|_2$ for all $f\in L^2(X)_0^{\otimes m}$, $g\in L^2(Y)_0^{\otimes m}$, $h\in L^2(Z)_0^{\otimes m}$, where $L^2(X)_0$ is the subspace of mean-zero functions and $L^2(X)_0^{\otimes m}$ its $m$-fold tensor power (functions on $X^m$ with zero average in each coordinate). The authors explicitly view this multilinear decay condition as the more natural quasirandomness condition, noting it is harder to verify and that the $m=1$ case does not obviously imply the general case.

A Steiner triple system (STS) of order $n$ is a collection of $n(n-1)/6$ triples of an $n$-point set $X$ such that every pair of distinct points lies in exactly one triple; such systems exist exactly for $n\equiv 1,3\pmod{6}$, and Keevash's asymptotic enumeration of designs makes 'a uniformly random STS of order $n$' a well-defined probability space. An STS $S$ determines a Steiner quasigroup: the commutative, idempotent operation $x\circ y=z$ when $\{x,y,z\}\in S$ (and $x\circ x=x$), whose multiplication table $L_S\subseteq X\times X\times X$ is a Latin square containing the diagonal $\{(x,x,x):x\in X\}$. For every such square the spectral condition fails identically: the diagonal $\{(x,x)\}$ of $X\times X$ is a closed class of the Markov chain, so $L_S$ is never A-quasirandom with any parameter $\rho<1$. Nevertheless, Eberhard–Manners–Mrazović state that 'a random Steiner triple system is far from having algebraic structure and presumably satisfies (7.1) for $\rho=o(1)$ with high probability as $n\to\infty$' — a presumption they do not prove.

What is known about random Steiner triple systems comes from a different, combinatorial toolbox: Kwan proved that almost all STS have perfect matchings (indeed the maximum number asymptotically) by comparing a uniformly random STS with the outcome of the random greedy triangle-removal process, and Ferber and Kwan proved that almost all STS are almost resolvable. These results control subgraph-count statistics but say nothing about the trilinear norms of the associated quasigroup tensor. Separately, there are other notions of quasirandom Latin squares — notably the ordering-based notion of Cooper–Král'–Lamaison–Mohr, characterized by densities of $2\times3$ symbol-order patterns being $1/720+o(1)$ — which depend on an ordering of the symbol set and are not directly related to the ordering-oblivious A-quasirandomness; which notion is appropriate for which problem is itself left open. Two further motivational gaps recorded by the source paper remain open independently of this question: the exact asymptotic enumeration of $n\times n$ Latin squares is still unknown, and no efficient algorithm for sampling uniformly random Latin squares is known.

Problem Statement

Let $n\equiv 1,3\pmod{6}$ tend to infinity, let $X$ be an $n$-element set, and let $S$ be a Steiner triple system of order $n$ on $X$ chosen uniformly at random (a well-defined ensemble by Keevash's asymptotic enumeration of designs). Let $L_S\subseteq X\times X\times X$ be the Latin square of the associated Steiner quasigroup, i.e. $L_S=\{(x,y,z)\in X^3:\{x,y,z\}\in S\text{ or }x=y=z\}$, so that $L_S$ contains the diagonal $\{(x,x,x):x\in X\}$. For $m\ge1$ let $L^2(X)_0^{\otimes m}$ denote the $m$-fold tensor power of the space of mean-zero functions on $X$, identified with the functions on $X^m$ having zero average in each coordinate, and define the latin-square tensor on powers by $\Lambda(f,g,h)=\mathbb{E}_{(x,y,z)\in L_S^m}\,f(x)g(y)h(z)$.

Question (raised in Remark 7.5 of Eberhard–Manners–Mrazović, left open): does there exist a function $\rho(n)=o(1)$ such that, with probability $1-o(1)$ as $n\to\infty$, for every integer $m\ge1$,

$$|\Lambda(f,g,h)|\le\rho(n)^{m/2}\,\|f\|_2\,\|g\|_2\,\|h\|_2$$

for all $f,g,h\in L^2(X)_0^{\otimes m}$? This is the multilinear decay condition (7.1) of the source paper with parameter $\rho=o(1)$, which the authors assert only as a presumption for random Steiner triple systems; even the weaker variant in which $\rho$ is allowed to depend on each fixed $m\ge1$ separately is open. Note that the spectral condition of Definition 7.1 must fail identically for every such square (the diagonal of $X\times X$ is a closed class of the associated Markov chain), so the question genuinely concerns the multilinear condition. The statement above requires a single $\rho(n)=o(1)$ working simultaneously for all $m\ge1$, which is the direct formalization of the source's presumption, since a single spectral parameter yields the bound (7.1) for every $m\ge1$ via Lemma 7.3 of the source. Note also that the source's proof of its counting theorem (Theorem 2.4) applies the multilinear bound with $m$ as large as $\epsilon n$, so a full transfer of the transversal asymptotic $(e^{-1/2}+o(1))\,n!^2/n^n$ to the Latin squares $L_S$ of random Steiner triple systems requires decay for $m$ growing linearly in $n$ — which the single-$\rho$ statement supplies but a fixed-$m$-only result would not; the transfer itself is expected rather than proven in the source, since the source hypothesizes the spectral condition.

References

1. Sean Eberhard, Freddie Manners, Rudi Mrazović, Transversals in quasirandom latin squares, Proc. London Math. Soc. 127 (2023), no. 1, 84–115, DOI 10.1112/plms.12538, arXiv:2209.02180, https://arxiv.org/abs/2209.02180
2. Matthew Kwan, Almost all Steiner triple systems have perfect matchings, Proc. Lond. Math. Soc. (3) 121 (2020), no. 6, 1468–1495, DOI 10.1112/plms.12373, arXiv:1611.02246, https://arxiv.org/abs/1611.02246
3. Matthew Kwan, Ashwin Sah, Mehtaab Sawhney, Michael Simkin, Substructures in Latin squares, Israel J. Math. 256 (2023), no. 2, 363–416, DOI 10.1007/s11856-023-2513-9, arXiv:2202.05088, https://arxiv.org/abs/2202.05088
4. W. T. Gowers, Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363–387, DOI 10.1017/S0963548307008826, https://doi.org/10.1017/S0963548307008826
5. Jacob W. Cooper, Daniel Král', Ander Lamaison, Samuel Mohr, Quasirandom Latin squares, Random Structures Algorithms 61 (2022), no. 2, 298–308, DOI 10.1002/rsa.21060, arXiv:2011.07572, https://arxiv.org/abs/2011.07572
6. Richard Montgomery, Transversals in Latin Squares, in Surveys in Combinatorics 2024, London Math. Soc. Lecture Note Series, pp. 131–158, DOI 10.1017/9781009490559.006, arXiv:2406.19873, https://arxiv.org/abs/2406.19873
7. Sean Eberhard, Freddie Manners, Rudi Mrazović, An asymptotic for the Hall–Paige conjecture, Adv. Math. 404 (2022), Paper No. 108423, DOI 10.1016/j.aim.2022.108423, https://doi.org/10.1016/j.aim.2022.108423
8. Asaf Ferber, Matthew Kwan, Almost all Steiner triple systems are almost resolvable, Forum Math. Sigma 8 (2020), article e39, DOI 10.1017/fms.2020.29, arXiv:1907.06744, https://arxiv.org/abs/1907.06744
9. Lior Gishboliner, Stefan Glock, Amedeo Sgueglia, Steiner triple systems with high discrepancy, J. Combin. Designs 34 (2026), no. 1, 5–14 (first published online 2025), DOI 10.1002/jcd.22004, arXiv:2503.23252, https://arxiv.org/abs/2503.23252
10. Candida Bowtell, Richard Montgomery, Almost every Latin square has a decomposition into transversals, arXiv:2501.05438, https://arxiv.org/abs/2501.05438
11. Peter Keevash, Counting designs, J. Eur. Math. Soc. 20 (2018), no. 4, 903–927, DOI 10.4171/jems/779, https://doi.org/10.4171/jems/779
12. Tantan Dai, Alexander Divoux, Tom Kelly, Entropy bounds for perfect matchings in bipartite hypergraphs, Electron. J. Combin. 33 (2026), no. 2, article P2.20, DOI 10.37236/14339, arXiv:2506.17652, https://arxiv.org/abs/2506.17652