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.



Can select many disjoint pairs with prescribed differences from Z_n?
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.]


