8
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.]

$\endgroup$
  • 2
    $\begingroup$ See also N. Alon, Additive Latin transversals, Isreal J. Math. 117 (2000) 125--130. $\endgroup$ – Douglas S. Stones May 10 '10 at 22:39
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ And if you are afraid, just ask for a translation! I'm sure the authors would not mind doing it :) $\endgroup$ – Mariano Suárez-Álvarez May 31 '10 at 22:18
1
$\begingroup$

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

$\endgroup$

Your Answer

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

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