MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have a sequence $d_i<2n$ for $i=1,\ldots,n$ and we want to select $n$ disjoint pairs from $Z_p$, $x_i,y_i$ such that $x_i-y_i=d_i \mod p$. Then how big $p$ has to be compared to $n$ to do this? I am primary interested on an upper bound on $p$. Is it true that there is always a $p\le (1+\epsilon)2n+O(1)$?

My comments. It is trivial that $p\ge 2n$ because all the numbers $x_i,y_i$ must be different and $d_1=1, d_2=2$ shows that this is not always enough. I also guess that it helps if $p$ is a prime, maybe the smallest prime bigger than $2n$ works which would answer the question.

share|cite|improve this question
up vote 9 down vote accepted

Your last guess is correct. The smallest prime number $>2n$ works, see [Preissmann, Emmanuel; Mischler, Maurice Seating couples around the King's table and a new characterization of prime numbers. Amer. Math. Monthly 116 (2009), no. 3, 268--272.]

share|cite|improve this answer
See also N. Alon, Additive Latin transversals, Isreal J. Math. 117 (2000) 125--130. – Douglas S. Stones May 10 '10 at 22:39

For those who are not afraid of a little spanish, here is a short proof using Nullstellensatz pointed to me by Preissmann, Emmanuel:

And yet another proof (or in fact two) which even generalizes a bit:

share|cite|improve this answer
And if you are afraid, just ask for a translation! I'm sure the authors would not mind doing it :) – Mariano Suárez-Alvarez May 31 '10 at 22:18

Here you can see the first proof that Domotorp pointed out (in english)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.