The Alon–Tarsi conjecture for even-order Latin squares and its equivalent rectangular-plethysm and SU(n)-integral formulations

The Alon–Tarsi conjecture predicts that for every even $n$ the number of even Latin squares of order $n$ differs from the number of odd ones; it is known only for $n=p\pm1$ with $p$ an odd prime, which covers all even orders up to 24, the smallest unsettled order being 26. Kumar and Landsberg proved that for each even $n$ the conjecture is equivalent to the rectangular plethysm statement that the irreducible module $S_{(n^n)}V$ does not lie in the kernel of the plethysm map $h_{n,n}$ (a borderline case of the Hadamard–Howe and Foulkes plethysm program) and to the nonvanishing of explicit Haar integrals over the special unitary group, including $\int_{\mathrm{SU}(n)}(\mathrm{perm}\,g)^n\,d\mu$ and $\int_{\mathrm{SU}(n)}\prod_{i,j}g^i_j\,d\mu$. This problem asks for a resolution of that equivalence class of statements — the Latin-square parity imbalance, the plethysm non-membership, or the integral nonvanishing — for all even $n$.

Background

A Latin square of order $n$ is an $n\times n$ array with entries in $\{1,\dots,n\}$ in which every row and every column contains each symbol exactly once. Reading each row (or column) as a permutation of $\{1,\dots,n\}$, one defines the row sign (column sign) of the square as the product of the signs of its $n$ row (column) permutations, and the sign of the square as the product of the two; a square is even or odd according to this sign. For odd $n$ a simple symmetry forces the numbers of even and odd Latin squares to be equal, so the parity question is vacuous. For even $n$, the Alon–Tarsi conjecture predicts that the number of even Latin squares of order $n$ differs from the number of odd ones. The conjecture emerged from the authors' study of graph list-coloring (coloring vertices from assigned color lists) via the polynomial method, where this parity difference is the coefficient that governs colorability, and it is equivalent to the column-sign Latin square conjecture of Huang and Rota, which predicts the analogous imbalance for the column sign alone. It is proven for orders $n=p\pm1$ with $p$ an odd prime (Drisko for $p+1$, Glynn for $p-1$), which covers every even $n\le24$; the smallest even order not covered is 26, and no even order outside this family is settled.

On the representation-theoretic side, let $V$ be a finite-dimensional complex vector space and $S^nV$ its $n$-th symmetric power, realized as the space of homogeneous degree-$n$ polynomials on the dual space. The plethysm map $h_{d,n}:S^d(S^nV)\to S^n(S^dV)$ is the $\mathrm{GL}(V)$-equivariant map obtained by regrouping a tensor of $nd$ factors in two ways and symmetrizing; for example $h_{d,n}((x_1)^n\cdots(x_d)^n)=(x_1\cdots x_d)^n$. It is an isomorphism when $\dim V=2$ (a classical nineteenth-century result), and Hadamard and Howe expected it to have maximal rank in general — injective for $d\le n$ and surjective for $d\ge n$. This expectation is false: a computation of Müller and Neunhöffer shows $h_{5,5}$ is not injective. The direct sum $\bigoplus_d h_{d,n}$ has kernel equal to the ideal of the Chow variety $\mathrm{Ch}_n(V^*)$, the variety of completely decomposable forms $\ell_1\cdots\ell_n$ (products of linear forms), whose coordinate-ring normalization is $\bigoplus_d S^n(S^dV)$. Irreducible polynomial $\mathrm{GL}(V)$-modules are indexed by partitions $\pi$ and denoted $S_\pi V$, so one may ask which rectangular modules $S_{(d^n)}V$ occur in $\ker h_{d,n}$; Kumar conjectured that $S_{(d^n)}V$ never lies in the kernel. This is closely tied to Foulkes' conjecture (1950): for $d>n$, every irreducible $[\pi]$ of the symmetric group $\mathfrak{S}_{dn}$ should occur in the permutation module induced from the trivial module of the wreath product $\mathfrak{S}_n\wr\mathfrak{S}_d$ (the subgroup of block permutations with arbitrary rearrangements inside blocks of size $n$) at least as often as in the analogous module with the roles of $d$ and $n$ exchanged. Restricting $h_{d,n}$ to weight-zero subspaces identifies the two sides with these induced modules, and the conjecture remains open in general.

On the analytic side, let $\mathrm{SU}(n)$ be the special unitary group of $n\times n$ complex matrices with $gg^\dagger=\mathrm{Id}$ and $\det g=1$, equipped with its normalized Haar measure $d\mu$ (the unique translation-invariant probability measure). For any $\mathrm{SU}(n)$-module $W$, averaging over the group, $v\mapsto\int_{\mathrm{SU}(n)}g\cdot v\,d\mu$, realizes the projection onto the invariant subspace $W^{\mathrm{SU}(n)}$; when that subspace is one-dimensional, nonvanishing of the integral of $g\cdot v$ is equivalent to nonvanishing of the pairing of $v$ with the invariant functional. In $S^{\delta}(\mathrm{End}(V))$ for $\delta$ a multiple of $n$ there is, up to scale, a unique $\mathrm{SL}(V)$-invariant, namely a power of the determinant; the permanent $\mathrm{perm}_n$ — the determinant with all signs omitted, i.e., the unsigned sum over permutations of products of matrix entries — supplies the natural polynomial to test against it.

The source paper of Kumar and Landsberg proves (its Theorem 1.9) that for each fixed even $n$ the following are equivalent: (a) the Alon–Tarsi conjecture for $n$; (b) $S_{(n^n)}V\notin\ker h_{n,n}$ for $V=\mathbb{C}^n$, i.e., the unique $\mathrm{SL}(V)$-invariant $P\in S_{(n^n)}V^*\subset S^n(S^nV^*)$ — explicitly a signed sum over $n$-tuples of permutations — evaluates nonzero on $(e_1\cdots e_n)^n$, meaning $P$ is not in the ideal of the Chow variety; (c) $\int_{\mathrm{SU}(n)}(\mathrm{perm}(g))^n\,d\mu\neq0$; (d) the pairing $\langle(\mathrm{perm}_n^{V^*})^n,(\mathrm{det}_n^V)^n\rangle\neq0$; (e) $\int_{\mathrm{SU}(n)}\prod_{1\le i,j\le n}g^i_j\,d\mu\neq0$; and (f) the corresponding pairing with $(\mathrm{det}_n^V)^n$. The proof expands the group-averaged invariant and identifies the coefficient of $(e_1\cdots e_n)^n$ with the column-sign imbalance of Latin squares. The investigation was motivated by geometric complexity theory (GCT), an algebraic-geometric approach to the algebraic-complexity separation $\mathrm{VP}\neq\mathrm{VNP}$ — the algebraic analogue of P versus NP, in which $\mathrm{VP}$ and $\mathrm{VNP}$ are the classes of polynomial families computed by polynomial-size arithmetic circuits, respectively without and with existentially guessed inputs — through orbit closures of the determinant and permanent polynomials: non-membership of the rectangular modules in the Chow ideal would guarantee that whole families of irreducible representations occur in the coordinate ring of the determinant's orbit closure, providing occurrence obstructions — irreducible representations that occur in the coordinate ring of one orbit closure but not the other, whose existence separates the closures and hence the underlying polynomials. The authors note that the displayed $\mathrm{SU}(n)$-integrals 'do not appear to be known' and that rectangular ($d\neq n$) versions of the equivalences can be formulated but are not developed.

Problem Statement

Decide the Alon–Tarsi conjecture: prove, or refute, that for every even positive integer $n$ the number of even Latin squares of order $n$ is different from the number of odd Latin squares of order $n$ (with the sign of a Latin square defined as the product of its row sign and column sign, each the product of the signs of the $n$ permutations read off from its rows or columns). By Theorem 1.9 of Kumar–Landsberg, for each even $n$ this is equivalent to each of the following, so a uniform resolution of any one of them for all even $n$ resolves the problem: (i) $S_{(n^n)}V\notin\ker h_{n,n}$ for $V=\mathbb{C}^n$, i.e., the fundamental $\mathrm{SL}(V)$-invariant $P\in S_{(n^n)}V^*$ evaluates nonzero on $(e_1\cdots e_n)^n$, equivalently does not belong to the ideal of the Chow variety $\mathrm{Ch}_n$; (ii) $\int_{\mathrm{SU}(n)}(\mathrm{perm}\,g)^n\,d\mu\neq0$; (iii) $\int_{\mathrm{SU}(n)}\prod_{1\le i,j\le n}g^i_j\,d\mu\neq0$; together with the equivalent pairing statements $\langle(\mathrm{perm}_n^{V^*})^n,(\mathrm{det}_n^V)^n\rangle\neq0$ and $\langle\prod_{i,j}g^i_j,(\mathrm{det}_n^V)^n\rangle\neq0$. The question concerns every even $n$, including orders such as 26 and 34 that are not of the form $p\pm1$; the cases $n=p\pm1$ with $p$ an odd prime, covering all even $n\le24$, are known prior results. A refutation consists of a specific even $n$ for which the two counts are exactly equal.

References

1. N. Alon and M. Tarsi, Colorings and orientations of graphs, Combinatorica 12 (1992), no. 2, 125–134, DOI: 10.1007/BF01204715, https://doi.org/10.1007/BF01204715
2. A. A. Drisko, On the number of even and odd Latin squares of order p+1, Advances in Mathematics 128 (1997), no. 1, 20–35, DOI: 10.1006/aima.1997.1623, https://doi.org/10.1006/aima.1997.1623
3. D. G. Glynn, The conjectures of Alon-Tarsi and Rota in dimension prime minus one, SIAM Journal on Discrete Mathematics 24 (2010), no. 2, 394–399, DOI: 10.1137/090773751, https://doi.org/10.1137/090773751
4. R. Huang and G.-C. Rota, On the relations of various conjectures on Latin squares and straightening coefficients, Discrete Mathematics 128 (1994), no. 1-3, 225–236, DOI: 10.1016/0012-365X(94)90114-7, https://doi.org/10.1016/0012-365X(94)90114-7
5. H. O. Foulkes, Concomitants of the quintic and sextic up to degree four in the coefficients of the ground form, Journal of the London Mathematical Society s1-25 (1950), no. 3, 205–209, DOI: 10.1112/jlms/s1-25.3.205, https://doi.org/10.1112/jlms/s1-25.3.205
6. J. Hadamard, Mémoire sur l'élimination, Acta Mathematica 20 (1897), 201–238, DOI: 10.1007/BF02418033, https://doi.org/10.1007/BF02418033
7. Roger Howe, (GL_n, GL_m)-duality and symmetric plethysm, Proceedings of the Indian Academy of Sciences - Mathematical Sciences 97 (1987), no. 1-3, 85–109, DOI: 10.1007/BF02837817, https://doi.org/10.1007/BF02837817
8. J. Müller and M. Neunhöffer, Some computations regarding Foulkes' conjecture, Experimental Mathematics 14 (2005), no. 3, 277–283, DOI: 10.1080/10586458.2005.10128928, https://doi.org/10.1080/10586458.2005.10128928
9. Shrawan Kumar, A study of the representations supported by the orbit closure of the determinant, Compositio Mathematica 151 (2015), no. 2, 292–312, DOI: 10.1112/S0010437X14007660 (preprint arXiv:1109.5996), https://doi.org/10.1112/S0010437X14007660
10. Shrawan Kumar and J. M. Landsberg, Connections between conjectures of Alon-Tarsi, Hadamard-Howe, and integrals over the special unitary group, Discrete Mathematics 338 (2015), no. 7, 1232–1238, DOI: 10.1016/j.disc.2015.01.027 (preprint arXiv:1410.8585), https://doi.org/10.1016/j.disc.2015.01.027
11. Douglas S. Stones, Formulae for the Alon–Tarsi conjecture, SIAM Journal on Discrete Mathematics 26 (2012), no. 1, 65–70, DOI: 10.1137/110797540, https://doi.org/10.1137/110797540
12. Levent Alpoge, Square-root cancellation for the signs of Latin squares, Combinatorica 37 (2017), no. 2, 137–142, DOI: 10.1007/s00493-015-3373-7 (preprint arXiv:1412.7574), https://doi.org/10.1007/s00493-015-3373-7
13. Nicholas J. Cavenagh and Ian M. Wanless, There are asymptotically the same number of Latin squares of each parity, Bulletin of the Australian Mathematical Society 94 (2016), no. 2, 187–194, DOI: 10.1017/S0004972716000174 (preprint arXiv:1610.06262), https://doi.org/10.1017/S0004972716000174
14. Carlos Gamas, On the conjecture of Alon-Tarsi, Gulf Journal of Mathematics 4 (2016), no. 4, 108–116, DOI: 10.56947/gjom.v4i4.269, https://doi.org/10.56947/gjom.v4i4.269
15. Benjamin Friedman and Sean McGuinness, The Alon–Tarsi conjecture: A perspective on the main results, Discrete Mathematics 342 (2019), no. 8, 2234–2253, DOI: 10.1016/j.disc.2019.04.018, https://doi.org/10.1016/j.disc.2019.04.018
16. Peter Bürgisser and Christian Ikenmeyer, Fundamental invariants of orbit closures, Journal of Algebra 477 (2017), 390–434, DOI: 10.1016/j.jalgebra.2016.12.035 (preprint arXiv:1511.02927), https://doi.org/10.1016/j.jalgebra.2016.12.035
17. Christian Ikenmeyer and Greta Panova, Rectangular Kronecker coefficients and plethysms in geometric complexity theory, Advances in Mathematics 319 (2017), 40–66, DOI: 10.1016/j.aim.2017.08.024 (preprint arXiv:1512.03798), https://doi.org/10.1016/j.aim.2017.08.024
18. Chris Bowman and Rowena Paget, The partition algebra and the plethysm coefficients I: stability and Foulkes' conjecture, Journal of Algebra 655 (2024), 110–138, DOI: 10.1016/j.jalgebra.2023.08.042 (preprint arXiv:1809.08128), https://doi.org/10.1016/j.jalgebra.2023.08.042
19. Alimzhan Amanov and Damir Yeliussizov, Fundamental invariants of tensors, Latin hypercubes, and rectangular Kronecker coefficients, International Mathematics Research Notices 2023 (2023), no. 20, 17552–17599, DOI: 10.1093/imrn/rnac311 (preprint arXiv:2202.11059), https://doi.org/10.1093/imrn/rnac311
20. Damir Yeliussizov, Stability of the Levi-Civita tensors and an Alon–Tarsi type theorem, Comptes Rendus. Mathématique 361 (2023), G8, 1367–1373, DOI: 10.5802/crmath.505, https://doi.org/10.5802/crmath.505
21. Alimzhan Amanov, Group and algebra hyperdeterminant, arXiv:2603.14378 (2026), https://arxiv.org/abs/2603.14378
22. Gergely Bérczi, Evolving Local Corrections for Global Constructions in Combinatorics, arXiv:2603.06692 (2026), https://arxiv.org/abs/2603.06692