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?
