Snevily's conjecture

Importance: High ✭✭✭
Author(s): Snevily, Hunter S.
Recomm. for undergrads: yes
Posted by: mdevos
on: October 13th, 2007

\begin{conjecture} Let $G$ be an abelian group of odd order and let $A,B \subseteq G$ satisfy $|A| = |B| = k$. Then the elements of $A$ and $B$ may be ordered $A = \{a_1,\ldots,a_k\}$ and $B = \{b_1,\ldots,b_k\}$ so that the sums $a_1+b_1, a_2+b_2 \ldots, a_k + b_k$ are pairwise distinct. \end{conjecture}

The motivation for this question comes from the study of \Def[latin squares]{latin square}. The addition table of every (additive) group forms a latin square, and this gives us a rich source of interesting squares. To explain further, we require a couple of definitions. A \emph{transversal} of a $k \times k$ matrix is a collection of $k$ cells, no two of which are in the same row or column, and we say that a transversal is \emph{latin} if no two of its cells contain the same element. Latin transversals are nice structures to find in latin squares. In particular, note that the cells of a $k \times k$ latin square $L$ may be partitioned into $k$ latin transversals if and only if there is a latin square orthogonal to $L$ (see \href[this]{http://www.cut-the-knot.org/arithmetic/latin3.shtml} for a definition of orthogonal latin squares). The above conjecture is perhaps most naturally phrased in terms of latin transversals as follows.

\begin{conjecture}[Snevily's conjecture - version 2] Every $k \times k$ submatrix of the addition table of every abelian group of odd order has a latin transversal. \end{conjecture}

Snevily's conjecture was proved by Alon [A] for abelian groups of prime order using a fairly standard application of the Alon-Tarsi polynomial technique. Later, Dasgupta, Karolyi, Serra, and Szegedy [DKSSz] used a sneaky application of the same technique to prove the conjecture for cyclic groups of odd order (the key to their approach is the fact that for $n$ odd, ${\mathbb Z}_n$ is a subgroup of the multiplicative group of the field of order $2^{\phi(n)}$ where $\phi$ is Euler's totient function). The conjecture is still open for non-cyclic groups.

The full addition table of ${\mathbb Z}_{2n}$ does not have a latin transversal. To see this, note that the sum of the elements in this group is equal to $n$ (here we identify $\{0,1,\ldots,2n-1\}$ with ${\mathbb Z}_{2n}$ in the usual manner). So, if $a_1,\ldots,a_{2n}$ and $b_1,\ldots,b_{2n}$ are two orderings of ${\mathbb Z}_{2n}$, then $\sum_{i=1}^{2n} (a_i + b_i) = 0$, and therefore $a_1 + b_1,\ldots,a_{2n} + b_{2n}$ cannot be an ordering of ${\mathbb Z}_{2n}$. This parity problem is the only obstruction known, and the following conjecture asserts that apart from it, the above conjectures holds for cyclic groups of even order.

\begin{conjecture}[Snevily] Every $k \times k$ submatrix of the addition table of ${\mathbb Z}_{2n}$ has a latin transversal, unless it is a translate of a cyclic subgroup of ${\mathbb Z}_{2n}$ of even order. \end{conjecture}

In fact, it appears that the above conjecture might hold with ${\mathbb Z}_{2n}$ replaced by any abelian group.

Bibliography

[A] N. Alon, \href[Additive Latin transversals]{http://www.tau.ac.il/~nogaa/PDFS/alt2.pdf}. Israel J. Math. 117 (2000), 125--130. \MRhref{MR1760589}

[DKSSz] S. Dasgupta, Gy. Károlyi, O. Serra, B. Szegedy, Transversals of additive Latin squares. Israel J. Math. 126 (2001), 17--28. \MRhref{MR1882032}

*[S] H. S. Snevily, Unsolved Problems: The Cayley Addition Table of Z$\sb n$. Amer. Math. Monthly 106 (1999), no. 6, 584--585. \MRhref{MR1543489}.


* indicates original appearance(s) of problem.

Proof of Snevily's Conjecture

Snevily's Conjecture was in fact proved in 2009. See: Bodan Arsovski, 'A proof of Snevily's Conjecture', Israel Journal of Mathematics, vol. 182 (2011), pp. 505-508. See also Gergely Harcos, Gyula Károlyi and Géza Kós, 'Remarks to Arsovski's proof of Snevily's Conjecture', Annales Univ. Sci. Budapest., vol. 54 (2011), pp. 57-61.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.