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
- Javier Cilleruelo's publications
- Frank Chu. Notes on the Mian-Chowla Sequence
- P. Erdos, P. Turán. On a problem of Sidon in additive number theory, and on some related problems
- God Plays Dice. On the Mian-Chowla sequence
- Kevin O'Bryant. A Complete Annotated Bibliography of Work Related to Sidon Sequences
- Javier Cilleruelo, Imre Ruzsa, Carlos Vinuesa. Generalized Sidon sets
- (FIND PAPER): A dense infinite Sidon sequence
- Imre Ruzsa. An infinite Sidon Sequence
- Erdos, Freud. On Disjoint Sets of Differences, or here
- Pollington. On the density of $B_2$-bases
- Cilleruelo. Infinite Sidon Sequences
- possibly: Singer. A Theorem in Finite Projective Geometry and Some Applications to Number Theory
- Gowers: Some unsolved problems in additive/combinatorial number theory
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).