5
$\begingroup$

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?

$\endgroup$

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ @quid I wasn't aware of the terminology before, but the notion that one should find the smallest possible $N$ or $n(k)$ s.t. all pairwise sums are unique, and and "diluting" for larger $N$, makes a lot of sense to me. $\endgroup$
    – ayas
    Jan 29, 2013 at 18:42
  • $\begingroup$ @quid From table 5 of the survey you link to, for $k = 5$ we can find a minimum Sidon subset of: {0, 1, 4, 9, 11}, which seems to imply that for $k \in [0, 100]$ we should have a dilution factor of $d=Floor[\frac{100}{12}] = 8$ as the minimum difference between pairwise sums. I achieved $9$ with an exhaustive enumeration, so this is rather excellent. Where did you get your $4$ from? $\endgroup$
    – ayas
    Jan 29, 2013 at 19:33
  • $\begingroup$ @ayas: I am glad the notion is interesting for you. For the '4': sorry for being a bit unclear there, I meant to say the asymptotics is (known to be) imprecise , but still it is this pattern. The $4$ arises if one would 'blindly' use the asym $N/k^2$ for $N=100$ and $k=5$. This is not a good idea, as you and I notices, as for $k=5$ the $n(k)$ is $11$ and not $25$ (the "aymp value"). Also note, that as I said one can actually divide $N$ by $n(k)$ where $n(k)$ is for the interval starting at $0$, so for $5$ one gets really the floor of $100/11$, ie $9$ (your value) not just $8$. $\endgroup$
    – user9072
    Jan 30, 2013 at 0:05
  • $\begingroup$ And by the asympotoics is know to be imprecise, I mean, it is known that the aymp value is not so close to the truth for small $k$. Indeed, the asymptotics itself apparently is precise (which I did neither know nor really dare to claim), as poited out by Javier (one of the leading experts in this subject, as suggested by user name and confirmed by user page). OT: Since I already need to write comments to clarify my comments clarifiying my answer, I will leave now for some rest. $\endgroup$
    – user9072
    Jan 30, 2013 at 0:11
  • $\begingroup$ @quid Thanks so much for your input! However I don't really understand why you would divide by $n(k)$ and not $(n(k)+1)$ since this is the "true" length of the interval starting at $0$? $\endgroup$
    – ayas
    Jan 30, 2013 at 0:17
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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/

$\endgroup$
1
  • $\begingroup$ Welcome to MO, Javier! I did not at all expect my vague guess is known to be true, that's great, thanks! $\endgroup$
    – user9072
    Jan 29, 2013 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.