Can select many disjoint pairs with prescribed differences from Z_n?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

3 Answers

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

-

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

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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

-

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 2010 at 22:18

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

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9019923806190491, "perplexity_flag": "middle"}