On the diameter and distribution of Sidon sets

Daniel Carter, Kevin O’Bryant, and I have uploaded to the arXiv our paper On the diameter and distribution of Sidon sets. This is a paper stemming from an interaction on my blog last year, regarding the use of AlphaEvolve to improve the then state of the art on the size of Sidon sets. We obtained a series of further refinements to the bound until progress stalled; after several months of no further progress, we decided to release what we have in this preprint.

Recall that a Sidon set is a set of integers with the property that all the sums with and are distinct. Equivalently, all the differences , are distinct, except at where of course there is a large multiplicity. A basic question (Erdős problem #30) asks for the largest size of a Sidon set in . Several algebraic constructions of Sidon sets (by Singer, Bose, and Ruzsa) are known with and special choices of ; see this survey of O’Bryant for details. Erdős and Turán have conjectured that cannot exceed , with the bound also proposed by Erdős as “perhaps too optimistic”.

For some time, the best upper bound was of the shape of which several proofs are now known. As tracked in the optimization constants repository, the constant factor in the second term has been gradually declining in the last few years; in our preprint we obtain the bound but we appear to be reaching the limit of our current method. Very recently, a slightly sharper bound of 0.942809522 was obtained by a different method, but our focus here is on the method rather than the specific numerical constant obtained. (We also did not try to use 2026-level AI tools to optimize our own bound.)

To illustrate our approach, let us sketch a proof of the bound . The fact that all the non-zero differences of are disjoint gives rise to a pointwise convolution bound

where denotes the reflection of . Taking inner products with a non-negative autocorrelation function to be chosen later, we conclude that

Taking the inner product of with a further weight , and rearranging, we conclude the bound

On the other hand, if one has the pointwise lower bound

on , then the left-hand side is at least . This gives an inequality

that can be used to bound by choosing appropriately. For instance if one selects

and

then one basically has , and the above bound becomes (after ignoring some lower order terms)

which after some algebra gives .

One can improve this bound by replacing the sharply truncated cutoff functions with more complicated cutoffs, which obey some biconvex constraints which one can explore using various optimization algorithms. It turns out that one can do even better by working not with deterministic choices of , but with random choices of , in which inequalities such as are only true after performing an expectation. The calculations get quite messy (and highly computer-assisted), but eventually give . The method also extends to the more general class of -Golomb rulers, in which a given non-zero difference is permitted to appear up to times.