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\}$

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