Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

3 Answers

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|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
add comment

For those who are not afraid of a little spanish, here is a short proof using Nullstellensatz pointed to me by Preissmann, Emmanuel: http://grupofundamental.wordpress.com/2010/03/05/il-faut-exiger-de-chacun-ce-que-chacun-peut-donner/

And yet another proof (or in fact two) which even generalizes a bit: http://arxiv.org/abs/1005.1177

share|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
add comment

Here you can see the first proof that Domotorp pointed out http://arxiv.org/abs/1006.2571 (in english)

share|improve this answer
add comment

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.