Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T02:23:22Z http://mathoverflow.net/feeds/question/120187 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120187/selecting-k-integers-from-an-interval-0-n-to-maximize-the-minimum-differen Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums ayas 2013-01-29T09:21:39Z 2013-01-31T10:44:23Z <p>I have an optimization problem where I need to select $k$ integers over the interval $[0, N]$ s.t. I maximize the minimum difference between any pairwise sum of the $k$ integers (where we also include the sum of one selected integer with itself). For example, if $k = 3$, $N = 3$, and we select the set of integers $(1, 2, 3)$, we have a set of $\frac{1}{2}k(k+1) = 6$ pairwise sums:</p> <p>$1 + 1 = 2$</p> <p>$1 + 2 = 3$</p> <p>$1 + 3 = 4$</p> <p>$2 + 2 = 4$</p> <p>$2 + 3 = 5$</p> <p>$3 + 3 = 6$</p> <p>Here, the minimum difference between any two pairwise sums is trivially: $(4 - 4) = 0$. </p> <p>As a function of $N$, how does one select the optimal set of $k \leq N$ integers? What happens in the limit where $N \to \infty$? I'd also be interested to understand how the number of optimal subsets of $k$ integers scales as $N$ becomes large. </p> <hr> <p>If we set $N = 100$ and do a computational experiment, we find: </p> <hr> <p>For $k = 3$: </p> <p>Optimal minimum distance between pairwise sums: $33$</p> <p>Example of subset that achieves the optimal minimum pairwise difference (there are $6$ total): {{0,33,99}} </p> <p>All pairwise (and self-) sums for this example subset: {{0,33,66,99,132,198}} </p> <hr> <p>For $k = 4$: </p> <p>Optimal minimum distance between pairwise sums: $16$</p> <p>Example of subset that achieves the optimal minimum pairwise difference (there are $50$ total): {{0,16,64,96}}</p> <p>All pairwise (and self-) sums for this example subset: {{0,16,32,64,80,96,112,128,160,192}}</p> <hr> <p>For $k = 5$: </p> <p>Optimal minimum distance between pairwise sums: $9$</p> <p>Example of subset that achieves the optimal minimum pairwise difference (there are $12$ total): {{0,9,36,81,99}}</p> <p>All pairwise (and self-) sums for this example subset: {{0,9,18,36,45,72,81,90,99,108,117,135,162,180,198}}</p> <hr> <hr> <p>Note: From quid's comment, and also given the computational expensive of finding values for $N = 100$ and $k > 5$, it occurs to me that it would be very nice to have some kind of an upperbound, known to the achievable, for the maximum minimum difference for a $k$-sized subset as a function of $k$. If optimal solutions are dense (I have no reason to suspect that this is the general trend), this could allow for the use of a more efficient probabilistic search procedure to find an optimal "diluted" Sidon subset. Does anyone have any good ideas for how to construct such an upperbound? </p> http://mathoverflow.net/questions/120187/selecting-k-integers-from-an-interval-0-n-to-maximize-the-minimum-differen/120208#120208 Answer by quid for Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums quid 2013-01-29T13:49:02Z 2013-01-29T13:49:02Z <p>This is in part a bit informal, but I hope it is still of interest.</p> <p>First, let us recall a somewhat related property: a subset $S$ of $\lbrace 1, \dots, n \rbrace =: [[1,N]]$ is called a Sidon set if all pairwaise sums of elements of $A$ are distinct, i.e., if your minimal difference is non-zero. </p> <p>This is a very well studied notion. See for example the survey by Kevin O'Bryant <a href="http://www1.combinatorics.org/Surveys/ds11.pdf" rel="nofollow">http://www1.combinatorics.org/Surveys/ds11.pdf</a> . In particular it is well-know that the maximal size of a Sidon subset of $[[1,N]]$ is asymyptotically $\sqrt{N}$. (I use the set starting from $1$ not $0$ since this is common in that context, yet changes not too much.) </p> <p>A way to construct a (possibly/likely) reasonable set of your type seems like so: given $k$, determine the smallest (a small) $n(k)$ such that $[[0,n(k)]]$ contains a Sidon subset $A'$ of size $k$ (or put differently construct an 'efficient' Sidon set of size $k$); good constructions are known see the survey mentioned above. This $n(k)$ will be asymptotically of size $k^2$. </p> <p>Now, set $d= \lfloor N/n(k) \rfloor$ and dilate $A'$ by the factor $d$, so $A = d \cdot A'$.</p> <p>Then $A \subset [[0,N]]$ is a $k$ element set, and your distance is $d$ (or a multiple thereof) and the size of $d$ is about $N/k^2$.</p> <p>Note that for example for $N=100$ and $k=5$ this constructions (yielding $4$) at first seems quite far from what you got; however, it is not, since I only mentioned the asymptotics for Sidon sets. Indeed all your examples are dilation of 'smaller' sets. It is just that you can find a $5$ element Sidon set already in $[[0,11]]$ and for this small value you do not need to go up to $k^2 = 25$.</p> <p>I am not sure if optimal constructions should always arise in this form, but perhaps at least frequently. (There could be issues near rounding thresholds though.)</p> <p>However, also note that Sidon sets (after a lot of effort!) are not fully understood so a really optimal answer seems to much to ask for anyway. </p> http://mathoverflow.net/questions/120187/selecting-k-integers-from-an-interval-0-n-to-maximize-the-minimum-differen/120218#120218 Answer by Peter Mueller for Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums Peter Mueller 2013-01-29T14:35:32Z 2013-01-29T14:35:32Z <p>I think it could be interesting to look at the continuous analogue of the question, where you look for the reals in the interval $[0,1]$ instead of the integers in $[0,N]$, because multiplying by $N$ and rounding gives solutions for you original problem, provided that $N$ is big enough.</p> <p>I made a Monte-Carlo test for small values of $k$. It seems to be the case that the optimal solutions arise from $k$-element Sidon-subsets of ${0,1,\dots,n}$ divided by $n$, with minimal $n$. I'm wondering if that always holds.</p> http://mathoverflow.net/questions/120187/selecting-k-integers-from-an-interval-0-n-to-maximize-the-minimum-differen/120259#120259 Answer by Javier for Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums Javier 2013-01-29T21:02:25Z 2013-01-31T10:44:23Z <p>As @quiz says, there exists $k$ integers $a_1,\dots,a_k\in [1,N]$ with $\min|a_i+a_j-(a_r+a_s)|\sim N/k^2$ when $k,\ N/k^2\to \infty$.</p> <p>Indeed the asymptotic is sharp. To see this, consider the real numbers $x_j=a_j/N$ and apply the following result of J. Cilleruelo and I. Ruzsa [1]</p> <p>Theorem: Let $x_1,\dots ,x_k\in [0,1]$ and let $\delta=\min|x_i+x_j-(x_r+x_s)|$. Then $\delta\le \frac 1{k(k-2\sqrt k)}$.</p> <p>[1] J. Cilleruelo and I. Ruzsa, "Real and p-adic Sidon sets", Acta Sci. Math. (Szegez) vol 70, nº 3-4 (2004). <a href="http://www.uam.es/personal_pdi/ciencias/cillerue/" rel="nofollow">http://www.uam.es/personal_pdi/ciencias/cillerue/</a></p>