MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

5 Brief note about constructing (achievable) upperbounds for the minimum pairwise difference within a k-sized subset.

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?

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}}