Additive Subset Picking
How can we choose a subset of $\{1,\ldots,n\}$ with as many elements as possible such that the sum of any two elements is distinct?
Formally, we want a subset $A\subseteq S=\{1,\ldots,n\}$ such that for all distinct unordered pairs
$\{a,b\} \ne \{c,d\},\, a+b\ne c+d$.
If we have two pairs of numbers such that $a-b=x$ and $c-d=x$ where $x\ne 0$, then we would have $a+d=b+c$, and thus
the difference between any two numbers in our subset is unique.
Of note, our valid subsets will be the elements $x \le n$ of
$B_2$ sequences, and are thus
Sidon sets. I'll also use the term
sumset for the set of pairwise sums.
Our problem is the exact one of finding optimal Golomb rulers.
A Sidon set chosen from $\{1,\dots,n\}$ can be shifted to $\{1+d,\ldots,n+d\}$ by an integer $d$, and the resulting
set is still a Sidon set with its sumset shifted by $2d$. Additionally, the set of negated elements of a Sidon set is
still a Sidon set, but with its sumset negated. Thus if $A$ is a Sidon set chosen from $\{1,\dots,n\}$,
its negated pair $B=\{n-x+1 \mid x\in A\}$ is also a Sidon set in $\{1,\dots,n\}$. Unless otherwise specified, I'll
consider Sidon sets here to have their least element be $1$, and I'll additionall call them canonical if its in-order
list of elements is lexicographically before those of its negated pair. This may change in the future,
given any additional symmetries or contraints. For example, $\{4,6,7\}$ is equivalent to
$\{1,3,4\}$, and its canonical form is $\{1,2,4\}$.
The naive approach starts with $\{1\}$ and then counts up and adding a number only if it doesn't introduce
a duplicate pairwise sum. This results in $\{1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, \ldots\}$, known as the
Mian-Chowla sequence
(OEIS A005282). Sidon sets from this sequence are not necessarily the largest;
$\{1,2,5,7\}$ is larger than the Mian-Chowla subsequence $\{1,2,4\}$ for Sidon subsets of $\{1,\ldots,7\}$.
Code
All code related to this problem is at https://github.com/jonathanolson/sidon-sets.
Coming soon
Or maybe these are exercises left to the reader?
- Put into terminology of Golomb rulers
- Investigate referenced articles for $B_2$ sequences and Sidon sets.
- Extend to sums of $m$ elements, i.e. using $B_m$ sequences.
- Investigate gaps in the sumset. Is there a unique Sidon set for every valid sumset? Can we construct Sidon sets in a more optimal way from sumsets?
- More structure in canonical forms that can be extracted out?
Appendix
Maximal Canonical Sidon Sets
Sets are in black. Gaps in the difference set are in red, gaps in the sumset are in green.
- 1: $\{1\}$
- 2: $\{1,2\}$
- 3: $\{1,2,4\}$$\{7\}$
- 4: $\{1,2,5,7\}$$\{5,11,13\}$
- 5: $\{1,2,5,10,12\}$$\{6\}$$\{5,8,9,16,18,19,21,23\}$
- 5: $\{1,3,8,9,12\}$$\{10\}$$\{3,5,7,8,14,19,22,23\}$
- 6: $\{1,2,5,11,13,18\}$$\{14,15\}$$\{5,8,9,11,17,21,25,27,28,30,32,33,34,35\}$
- 6: $\{1,2,5,11,16,18\}$$\{8,12\}$$\{5,8,9,11,14,15,24,25,26,28,30,31,33,35\}$
- 6: $\{1,2,9,12,14,18\}$$\{14,15\}$$\{5,6,7,8,9,12,17,22,25,29,31,33,34,35\}$
- 6: $\{1,2,9,13,15,18\}$$\{10,15\}$$\{5,6,7,8,9,12,13,21,23,25,29,32,34,35\}$
- 7: $\{1,2,5,11,19,24,26\}$$\{11,12,16,20\}$$\{5,8,9,11,14,15,17,18,19,23,32,33,34,36,39,40,41,42,44,46,47,49,51\}$
- 7: $\{1,2,8,12,21,24,26\}$$\{8,15,17,21\}$$\{5,6,7,8,11,12,15,17,18,19,21,30,31,35,37,39,40,41,43,44,46,49,51\}$
- 7: $\{1,2,12,17,20,24,26\}$$\{13,17,20,21\}$$\{5,6,7,8,9,10,11,12,15,16,17,20,23,30,31,33,35,39,42,45,47,49,51\}$
- 7: $\{1,3,4,11,17,22,26\}$$\{12,17,20,24\}$$\{3,9,10,11,13,16,17,19,24,31,32,35,36,38,40,41,42,45,46,47,49,50,51\}$
- 7: $\{1,3,8,14,22,23,26\}$$\{10,16,17,24\}$$\{3,5,7,8,10,12,13,14,18,19,20,21,32,33,35,38,39,41,42,43,47,50,51\}$
- 8: $\{1,2,5,10,16,23,33,35\}$$\{16,20,24,26,27,29\}$$\{5,8,9,13,14,16,19,22,23,27,29,30,31,41,42,44,47,48,50,52,53,54,55,57,59,60,61,62,63,64,65,67,69\}$
- 9: $\{1,2,6,13,26,28,36,42,45\}$$\{18,21,28,31,33,37,38,42\}$$\{5,6,9,10,11,13,16,17,18,20,21,22,23,24,25,31,33,35,36,40,45,50,53,57,59,60,61,63,65,66,67,69,74,75,76,77,79,80,82,83,85,86,88,89\}$
- 10: $\{1,2,7,11,24,27,35,42,54,56\}$$\{36,37,38,39,42,44,46,48,50,51\}$$\{5,6,7,10,11,15,16,17,19,20,21,23,24,27,30,32,33,39,40,41,45,47,50,52,60,64,68,71,72,73,74,75,76,79,82,85,86,87,88,90,92,93,94,95,97,99,100,101,102,103,104,105,106,107,109,111\}$
- 11: $\{1,2,5,14,29,34,48,55,65,71,73\}$$\{11,22,30,35,38,40,45,48,49,52,55,56,58,61,62,65,67\}$$\{5,8,9,11,12,13,14,17,18,20,21,22,23,24,25,26,27,29,32,33,37,38,40,41,42,44,45,46,47,51,52,54,55,59,61,64,65,71,80,81,83,86,88,90,91,92,93,95,97,98,101,104,106,108,109,111,112,114,115,116,117,118,122,123,124,125,127,129,131,132,133,134,135,137,139,140,141,143,145\}$
- 11: $\{1,2,10,20,25,32,53,57,59,70,73\}$$\{26,29,35,36,40,42,44,46,54,59,61,62,64,65,66,67,70\}$$\{5,6,7,8,9,10,13,14,15,16,17,18,19,23,24,25,28,29,31,32,36,37,38,39,41,43,44,46,47,48,49,51,53,56,62,65,66,68,70,76,81,86,87,88,92,94,96,97,99,100,101,103,104,107,108,109,111,113,115,117,119,120,121,122,124,125,128,131,133,134,135,136,137,138,139,141,142,144,145\}$
- 12: $\{1,3,7,25,30,41,44,56,69,76,77,86\}$$\{48,50,54,57,58,59,60,63,64,65,67,71,72,77,78,80,81,82,84\}$$\{3,5,7,9,11,12,13,15,16,17,18,19,20,21,22,23,24,25,27,29,30,34,35,36,38,39,40,41,43,46,49,52,53,54,56,58,61,62,64,65,67,68,73,75,90,91,92,95,96,98,103,104,105,108,109,114,115,119,122,123,124,126,128,129,131,134,135,136,137,139,140,141,143,144,147,148,149,150,151,156,157,158,159,160,161,164,165,166,167,168,169,170,171\}$
- 13: $\{1,3,6,26,38,44,60,71,86,90,99,100,107\}$$\{24,31,44,49,50,51,53,58,66,67,71,72,75,76,77,78,79,82,86,88,90,91,92,95,100,102,103,105\}$$\{3,5,8,10,11,13,14,15,16,17,18,19,20,21,22,23,24,25,26,28,30,31,33,34,35,36,37,38,40,42,43,46,48,49,51,53,54,55,56,57,58,59,60,62,65,67,68,69,71,73,75,78,79,80,81,83,84,85,90,94,95,99,107,111,114,117,118,119,121,122,123,127,129,132,135,136,139,140,141,147,148,149,152,153,154,155,156,158,162,163,164,165,166,168,169,173,174,175,177,179,181,182,183,184,187,188,191,192,194,195,196,201,202,203,204,205,208,209,210,211,212,213\}$
References
Feedback
Please let me know below if you have any ideas, questions, or corrections about this problem. I'd love to hear new
approaches or useful concepts that I haven't mentioned (as I may be unaware of them).