Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums - MathOverflow

Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums

2013-01-29T09:21:39Z

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:

$1 + 1 = 2$

$1 + 2 = 3$

$1 + 3 = 4$

$2 + 2 = 4$

$2 + 3 = 5$

$3 + 3 = 6$

Here, the minimum difference between any two pairwise sums is trivially: $(4 - 4) = 0$.

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.

If we set $N = 100$ and do a computational experiment, we find:

For $k = 3$:

Optimal minimum distance between pairwise sums: $33$

Example of subset that achieves the optimal minimum pairwise difference (there are $6$ total): {{0,33,99}}

All pairwise (and self-) sums for this example subset: {{0,33,66,99,132,198}}

For $k = 4$:

Optimal minimum distance between pairwise sums: $16$

Example of subset that achieves the optimal minimum pairwise difference (there are $50$ total): {{0,16,64,96}}

All pairwise (and self-) sums for this example subset: {{0,16,32,64,80,96,112,128,160,192}}

For $k = 5$:

Optimal minimum distance between pairwise sums: $9$

Example of subset that achieves the optimal minimum pairwise difference (there are $12$ total): {{0,9,36,81,99}}

All pairwise (and self-) sums for this example subset: {{0,9,18,36,45,72,81,90,99,108,117,135,162,180,198}}

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?

Answer by quid for Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums

2013-01-29T13:49:02Z

This is in part a bit informal, but I hope it is still of interest.

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.

This is a very well studied notion. See for example the survey by Kevin O'Bryant http://www1.combinatorics.org/Surveys/ds11.pdf . 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.)

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

Now, set $d= \lfloor N/n(k) \rfloor$ and dilate $A'$ by the factor $d$, so $A = d \cdot A'$.

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

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

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

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.

Answer by Peter Mueller for Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums

2013-01-29T14:35:32Z

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.

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.

Answer by Javier for Selecting $k$ integers from an interval $[0, N]$ to maximize the minimum difference between pairwise sums

2013-01-29T21:02:25Z

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

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]

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)}$.

[1] J. Cilleruelo and I. Ruzsa, "Real and p-adic Sidon sets", Acta Sci. Math. (Szegez) vol 70, nº 3-4 (2004). http://www.uam.es/personal_pdi/ciencias/cillerue/