TOPICS
Search

Sidon Set


A Sidon set is a set A of integers for which all sums a+b, with a,b in A and a<=b, are distinct. For a finite Sidon set, this condition is equivalent to requiring that all positive differences between elements be distinct. Subtracting the minimum element from every element therefore turns each finite Sidon set into a Golomb ruler, while every Golomb ruler is a finite Sidon set.

For example, the marks 0, 1, 4, 9, and 11 form a Sidon set and an optimal five-mark Golomb ruler of length 11.

Let R(N) denote the largest possible number of elements in a Sidon set contained in the interval [1,N], and let G(k) denote the minimum length of a k-mark Golomb ruler. Then

 R(N)=max{k:G(k)<=N-1}.
(1)

With R(0)=0, the sizes for N=0, 1, 2, ... begin 0, 1, 2, 2, 3, 3, 3, 4, ... (OEIS A143824). Since G(k) is known exactly through k=28, this relation determines R(N) exactly for N<=586 (distributed.net 2022).

Singer's (1938) construction using a finite projective plane gives the asymptotic lower bound

 R(N)>=(1-o(1))sqrt(N).
(2)

Carter et al. (2025) proved the upper bound

 R(N)<=sqrt(N)+0.98183N^(1/4)+O(1).
(3)

Hou and Zhao (2026) subsequently improved this result in a preprint to

 R(N)<=sqrt(N)+0.94601N^(1/4)+O(1).
(4)

Carter et al. (2026) further improved the bound to

 R(N)<=sqrt(N)+0.945N^(1/4)+0.447.
(5)

They also proved that the diameter maxA-minA of a k-element Sidon set A is at least k^2-1.89k^(3/2), with the coefficient improved to 1.88607 for k>=483. Carter et al. (2026) report that work with AlphaEvolve led to the underlying theoretical framework. Claude supplied an alternative optimization implementation, checked using human-written verification code.

The question whether R(N)=sqrt(N)+O_epsilon(N^epsilon) for every epsilon>0 is problem 30 in the Erdős problems collection. The improved coefficient of N^(1/4) does not resolve that error-term question.


See also

B2-Sequence, Golomb Ruler

Explore with Wolfram|Alpha

References

Carter, D.; Hunter, Z.; and O'Bryant, K. "On the Diameter of Finite Sidon Sets." Acta Math. Hungar. 175, 108-126, 2025. https://doi.org/10.1007/s10474-024-01499-8.distributed.net. "Completion of OGR-28 Project." Nov. 23, 2022. https://blogs.distributed.net/2022/11/23/03/28/bovine/.Carter, D.; O'Bryant, K.; and Tao, T. "On the Diameter and Distribution of Sidon Sets." 26 Oct 2026. https://arxiv.org/abs/2610.36207.Hou, J. and Zhao, H. "Vector-Valued Smoothing for Finite Sidon Sets." July 1, 2026. https://arxiv.org/abs/2607.01169.Singer, J. "A Theorem in Finite Projective Geometry and Some Applications to Number Theory." Trans. Amer. Math. Soc. 43, 377-385, 1938. https://doi.org/10.1090/S0002-9947-1938-1501951-4.Sloane, N. J. A. Sequence A143824 in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Sidon Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SidonSet.html

Subject classifications