Pairs promoting diversity

Question

Let $p$ be a prime number at least three and let ${k}$ be a positive integer smaller than $p$. Given ${a}_1, \ldots, {a}_{{k}} \in \mathbb{F}_p$ and distinct elements ${b}_1, \ldots, {b}_{{k}} \in \mathbb{F}_p$, prove that there exists a permutation $\sigma$ of $[{k}]$ such that the values of ${a}_{{i}}+{b}_{\sigma({i})}$ are distinct.

I am not sure if the below solution logic contains fallacy or not, but this is my progress so far:

$\textbf{Solution (so far):}$ The statement we want to prove is equivalent to the following: If $a_1,...,a_k$ and $b_1,...,b_k$ are distinct elements of $\mathbb{F}p$, there exists a permutation $\sigma$ of $[k]$ such that the numbers $a_i-b_{\sigma(i)}$ are all distinct modulo $p$.

Consider all the $k!$ permutations of the $b_i$'s. For each permutation, we can form a set of k numbers of the form $a_i - b_{\sigma(i)}$. Thus we have a total of $k\,k!$ numbers.

We want to show that we must have at least $k$ distinct numbers in some set, which will be equivalent to proving the existence of a permutation such that the numbers $a_i - b_{\sigma(i)}$ are distinct.

Since these numbers are taken modulo $p$, there are only $p$ possible values. If we assume that we can't find $k$ distinct numbers in any set, then each set can have at most $k-1$ distinct numbers. Thus, in total, we would have at most $(k-1)k!$ distinct numbers.

However, we know that the total number of numbers is $k\,k!$ and this is strictly less than $p$ since $p$ is a prime number larger than $k$. Therefore, we must have $k\,k! \leq (k-1)k!$, which is a contradiction. Hence, there must exist a permutation such that the numbers $a_i - b_{\sigma(i)}$ are distinct modulo $p$.

Answer 1

The proof follows from Combinatorial Nullstellensatz: See: https://www.cs.tau.ac.il/~nogaa/PDFS/alt2.pdf

Answer 2

It is interesting for your solution to try to force a satisfying permutation out of all permutations by counting the number of distinct elements in two different ways. However your solution is incorrect.

---

Since your solution does not use $p$ is a prime, had your solution been correct, the proposition would have been true for $p=4$ as well.

Let $p=4$, $k=2$, $a_1=0, a_2=2, b_1=0, b_2=2$. There are two permutations of $\{1,2\}.$

• $\sigma$ is the identity. $\ a_1+b_{\sigma(1)}=a_2+b_{\sigma(2)}=0\bmod4.$
• $\sigma$ swaps $1$ and $2$. $\ a_1+b_{\sigma(1)}=a_2+b_{\sigma(2)}=2\bmod4.$

Hence the proposition does not hold for $p=4$. This shows that your solution cannot be correct.

When "we have a total of $k\,k!$ numbers", those numbers are not necessarily distinct. (In fact, they are probably not.) H Although it is true that "we would have at most $(k-1)\,k!$ distinct numbers", we cannot conclude that "therefore, we must have $k\, k!\le (k-1)\,k!$". This is where your solution breaks.

---

The proposition in the question is a stronger version (where $a_i$'s need not be distinct) of the special case (where the group is of prime order) of Snevily's conjecture It was first proved in paper Additive Latin transversals by Noga Alon. Snevily's conjecture was proved in 2009 by Bodan Arsovski, A proof of Snevily's Conjecture, Israel Journal of Mathematics, vol. 182 (2011), pp. 505-508.