9
$\begingroup$

Let $k$ be a positive integer. Let $A=\{a_1,\cdots, a_{2^k}\}$ be a subset of $\mathbf{Z}/2^{k+1}\mathbf{Z}$ whose image in $\mathbf{Z}/2^k\mathbf{Z}$ is the whole $\mathbf{Z}/2^k\mathbf{Z}$. Let $B=\{b_1,\cdots, b_{2^k}\}$ be a subset with the same property. Is it always possible to find a permutation $\sigma$ on $2^k$ letters such that

$a_1+b_{\sigma(1)},\cdots, a_{2^k}+b_{\sigma(2^k)}$

are pairwise distinct?

A little background. (A weaker version of) Snevily's conjecture asserts that, if $l<n$ and $n$ is odd, then for any two subsets $A=\{a_1,\cdots,a_l\}$, $B=\{b_1,\cdots, b_l\}$ of $\mathbf{Z}/n\mathbf{Z}$, there is always a permutation $\sigma$ on $l$ letters such that

$a_1+b_{\sigma(1)},\cdots, a_{l}+b_{\sigma(l)}$

are pairwise distinct. This has been proved in full generality by Arsovski. The theorem is certainly false if $n$ is allowed to be even. Intuitively, it's the power of 2 in $n$ that will cause the problem. So I only look at $\mathbf{Z}/2^k\mathbf{Z}$ and want to see what can be said. The above question is my gut feeling.

$\endgroup$
  • $\begingroup$ do you mean to say $\mathbb{Z}/2^k\mathbb{Z}$? $\endgroup$ – setholopolus Dec 15 '16 at 19:38
  • $\begingroup$ Yes. My shorthand. Now edited. $\endgroup$ – user160886 Dec 15 '16 at 19:46
  • $\begingroup$ A curious question! Where did you run into this problem? Giving such context makes questions more welcome here. $\endgroup$ – Jyrki Lahtonen Dec 15 '16 at 19:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.