Can select many disjoint pairs with prescribed differences from Z_n? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T01:45:20Z http://mathoverflow.net/feeds/question/24108 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24108/can-select-many-disjoint-pairs-with-prescribed-differences-from-z-n Can select many disjoint pairs with prescribed differences from Z_n? domotorp 2010-05-10T14:16:10Z 2010-06-15T14:10:19Z <p>Suppose we have a sequence $d_i&lt;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)$?</p> <p>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.</p> http://mathoverflow.net/questions/24108/can-select-many-disjoint-pairs-with-prescribed-differences-from-z-n/24113#24113 Answer by Roland Bacher for Can select many disjoint pairs with prescribed differences from Z_n? Roland Bacher 2010-05-10T14:50:56Z 2010-05-10T15:06:58Z <p>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.]</p> http://mathoverflow.net/questions/24108/can-select-many-disjoint-pairs-with-prescribed-differences-from-z-n/26161#26161 Answer by domotorp for Can select many disjoint pairs with prescribed differences from Z_n? domotorp 2010-05-27T16:03:24Z 2010-06-01T10:16:37Z <p>For those who are not afraid of a little spanish, here is a short proof using Nullstellensatz pointed to me by Preissmann, Emmanuel: <a href="http://grupofundamental.wordpress.com/2010/03/05/il-faut-exiger-de-chacun-ce-que-chacun-peut-donner/" rel="nofollow">http://grupofundamental.wordpress.com/2010/03/05/il-faut-exiger-de-chacun-ce-que-chacun-peut-donner/</a></p> <p>And yet another proof (or in fact two) which even generalizes a bit: <a href="http://arxiv.org/abs/1005.1177" rel="nofollow">http://arxiv.org/abs/1005.1177</a></p> http://mathoverflow.net/questions/24108/can-select-many-disjoint-pairs-with-prescribed-differences-from-z-n/28254#28254 Answer by Daniel Kohen for Can select many disjoint pairs with prescribed differences from Z_n? Daniel Kohen 2010-06-15T14:10:19Z 2010-06-15T14:10:19Z <p>Here you can see the first proof that Domotorp pointed out <a href="http://arxiv.org/abs/1006.2571" rel="nofollow">http://arxiv.org/abs/1006.2571</a> (in english)</p>