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

comments powered by Disqus