A purely combinatorial proof of Snevily's conjecture on transversals of Cayley addition tables of odd-order abelian groups

Snevily's conjecture (1999) states that for any two $k$ -element subsets $A$ and $B$ of a finite abelian group $G$ of odd order, the elements of $A$ and $B$ can be paired so that all $k$ sums are distinct; equivalently, every subsquare of the Cayley addition table of $G$ cut out by $k$ rows and $k$ columns contains a transversal (a selection of $k$ cells with no repeated row, column, or symbol). The conjecture is now a theorem: Alon settled prime-order cyclic groups (2000), Dasgupta–Károlyi–Serra–Szegedy settled all odd-order cyclic groups (2001), and Arsovski (2011), with a refinement of Feng–Sun–Xiang (2011), settled the general case — but every known proof runs through an algebraic engine (Combinatorial Nullstellensatz, exterior algebra, group characters, or determinant identities in characteristic 2). Harcos–Károlyi–Kós (2011), after giving a shortened proof of this lineage, posed the open problem considered here: find a purely combinatorial proof — one using only permutations, counting, induction, and elementary combinatorial constructions on the group table — with no characters, Fourier analysis, determinants, exterior algebra, or polynomial method, and valid for all odd orders and all subset sizes. The nearest progress is the absorption-based proof of Müyesser–Pokrovskiy (2025), which confirms Snevily's conjecture in a strong form but only for sufficiently large subsquares, explicitly leaving the exact all-sizes statement to algebraic methods. The problem of a slack-free purely combinatorial proof of the exact statement remains open.

Background

A Latin square of order $n$ is an $n\times n$ array filled with $n$ symbols so that each symbol appears exactly once in each row and each column; a transversal is a choice of $n$ cells of the array with no two in the same row, no two in the same column, and no two bearing the same symbol. The Cayley addition table of a finite (additively written) group $G$ — the table with entry $a+b$ in row $a$ , column $b$ — is a Latin square, and it is natural to ask which subsquares obtained by keeping $k$ chosen rows (a set $A$ ) and $k$ chosen columns (a set $B$ ) still contain a transversal. In multiplicative language such a transversal is a bijection $\phi:A\to B$ with $a\phi(a)$ pairwise distinct; additively, it is a permutation $\pi$ of $\{1,\dots,k\}$ such that the sums $a_{1}+b_{\pi(1)},\dots,a_{k}+b_{\pi(k)}$ are pairwise distinct, so the question is exactly a 'pairwise-distinct-sums' matching problem between two equal-sized subsets of the group. Hunter S. Snevily conjectured in 1999 that for abelian groups of odd order deleting rows and columns can never destroy all transversals: if $|G|$ is odd, every such subsquare $A\times B$ has a transversal. (For even-order groups this can fail — e.g. the whole table of an even-order cyclic group has no transversal — which is why oddness is essential.) The conjecture has a long history of partially successful algebraic attacks: Alon (2000) proved the case of cyclic groups of prime order using the Combinatorial Nullstellensatz (a polynomial method that certifies a nonvanishing value of a multivariate polynomial from a condition on one of its coefficients); Dasgupta, Károlyi, Serra, and Szegedy (2001) extended this to all odd-order cyclic groups using exterior-algebra arguments (the exterior algebra of a module is the algebra generated by the module's elements subject to the anticommuting product rule $u\wedge v=-v\wedge u$ ) over Galois rings (finite commutative rings in which the needed group characters can be realized); Gao and Wang (2004) gave another treatment via group rings (rings of formal linear combinations of group elements); and Sun (2003) proved related results on restricted sumsets (sums $a+b$ taken only over pairs with $a\neq b$ ). Feng, Sun, and Xiang (2011) reformulated the problem in exterior algebra and posed a conjecture on the existence of a $k$ -tuple of group characters (homomorphisms from $G$ to the multiplicative group of a field, i.e. the Fourier basis of the group) for which two associated character-evaluation matrices are both nonsingular; they showed this conjecture implies Snevily's. Arsovski (2011) proved exactly that, settling Snevily's conjecture in full via character theory and determinants. Harcos, Károlyi, and Kós (2011) then gave a considerably shortened proof of the Feng–Sun–Xiang conjecture and hence of Snevily's conjecture; in retrospect their argument rests on a single determinant identity valid in fields of characteristic 2, together with a purely combinatorial lemma (an induction showing that some pairing of $A$ and $B$ yields a multiset of sums not shared by any other pairing). They close by remarking that it would be very interesting to find a purely combinatorial proof. This is the problem recorded here: it is a methodological open question attached to an already-settled theorem, of a standard genre in combinatorics (like asking for a bijective proof of a known enumerative identity). Subsequently, Müyesser and Pokrovskiy (2025), developing the absorption method (a combinatorial technique that extends partial matchings to spanning ones by pre-embedding flexible 'gadget' structures) for multiplication hypergraphs of groups (the 3-uniform hypergraph whose vertices are the group elements and whose edges are the product triples $(a,b,ab)$ ), confirmed Snevily's conjecture in a strong form — in fact characterizing all large subsquares without transversals in arbitrary finite groups — but only for sufficiently large subsquares, explicitly deferring a characterization valid for all sizes. Thus no purely combinatorial proof of the exact statement, valid for all odd group orders and all $k$ , is known; the algebraic step is the only known route to the small cases.

Problem Statement

Prove Snevily's conjecture by purely combinatorial means: show, using only combinatorial reasoning, that for every finite abelian group $G$ of odd order, every positive integer $k$ , and every two $k$ -element subsets $A=\{a_{1},\dots,a_{k}\}$ and $B=\{b_{1},\dots,b_{k}\}$ of $G$ , there exists a permutation $\pi$ of $\{1,\dots,k\}$ such that the sums $a_{1}+b_{\pi(1)},\dots,a_{k}+b_{\pi(k)}$ are pairwise distinct. 'Purely combinatorial' is an operational restriction fixed by the tools the proof uses: admissible steps are elementary combinatorial reasoning about the group operation and the two subsets, including the elementary structure of finite abelian groups (the Chinese remainder and primary decompositions), bijections and permutations, counting and double counting, induction, extremal and structural case analysis, finite probabilistic arguments such as first- and second-moment estimates, and matching- or absorption-style constructions on the group addition table itself. Inadmissible are group characters or Fourier analysis on groups, group rings or the group algebra, field extensions, and any step that establishes the invertibility, nonsingularity, or nonvanishing of a matrix, a determinant, or a polynomial identity over a ring or a field (equivalently, any rank or minor argument); this operational test rules out the Combinatorial Nullstellensatz, exterior-algebra arguments, and character-evaluation determinants. The proof must hold for all odd orders and all $k$ with no size threshold (so the large- $n$ absorption results of Müyesser–Pokrovskiy do not by themselves answer it). This is a methodological open problem attached to a theorem of Arsovski: the scientific objective is not new truth but a combinatorial explanation of why the pairwise-distinct-sums matching always exists in odd-order abelian groups.

References

G. Harcos, Gy. Károlyi, G. Kós, 'Remarks to Arsovski's proof of Snevily's conjecture', Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 54 (2011) 57–61; arXiv:1004.0253; DOI 10.48550/arXiv.1004.0253; https://arxiv.org/abs/1004.0253 (source of the open question)
H. S. Snevily, 'The Cayley addition table of Z_n', The American Mathematical Monthly 106 (1999) 584–585; DOI 10.2307/2589472; https://doi.org/10.2307/2589472
N. Alon, 'Additive Latin transversals', Israel Journal of Mathematics 117 (2000) 125–130; DOI 10.1007/BF02773567; https://doi.org/10.1007/bf02773567
S. Dasgupta, Gy. Károlyi, O. Serra, B. Szegedy, 'Transversals of additive Latin squares', Israel Journal of Mathematics 126 (2001) 17–28; DOI 10.1007/BF02784149; https://doi.org/10.1007/bf02784149
W. D. Gao, D. J. Wang, 'Additive Latin transversals and group rings', Israel Journal of Mathematics 140 (2004) 375–380; DOI 10.1007/BF02786641; https://doi.org/10.1007/bf02786641
Z.-W. Sun, 'On Snevily's conjecture and restricted sumsets', Journal of Combinatorial Theory, Series A 103 (2003) 291–304; DOI 10.1016/S0097-3165(03)00099-2; https://doi.org/10.1016/s0097-3165(03)00099-2
T. Feng, Z.-W. Sun, Q. Xiang, 'Exterior algebras and two conjectures on finite abelian groups', Israel Journal of Mathematics 182 (2011) 425–437; arXiv:0808.2753; DOI 10.1007/s11856-011-0037-1; https://arxiv.org/abs/0808.2753
B. Arsovski, 'A proof of Snevily's conjecture', Israel Journal of Mathematics 182 (2011) 505–508; DOI 10.1007/s11856-011-0040-6; https://doi.org/10.1007/s11856-011-0040-6
A. Müyesser, A. Pokrovskiy, 'A random Hall–Paige conjecture', Inventiones Mathematicae 240 (2025) 779–867; arXiv:2204.09666; DOI 10.1007/s00222-025-01328-x; https://arxiv.org/abs/2204.09666
D. Grynkiewicz, 'Character and Linear Algebraic Methods: Snevily's Conjecture', in Developments in Mathematics, Springer (2013) 271–278; DOI 10.1007/978-3-319-00416-7_18; https://doi.org/10.1007/978-3-319-00416-7_18