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 ${A}$ is a set of integers with the property that all the sums ${a + b}$ with ${a, b \in A}$ and ${a \leq b}$ are distinct. Equivalently, all the differences ${a-b}$ , ${a, b \in A}$ are distinct, except at ${0}$ where of course there is a large multiplicity. A basic question (Erdős problem #30) asks for the largest size ${k = |A|}$ of a Sidon set in ${\{1,\dots,N\}}$ . Several algebraic constructions of Sidon sets (by Singer, Bose, and Ruzsa) are known with ${k = N^{1/2} - O(1)}$ and special choices of ${N}$ ; see this survey of O’Bryant for details. Erdős and Turán have conjectured that ${k}$ cannot exceed ${N^{1/2} + O(N^{o(1)})}$ , with the bound ${N^{1/2} + O(1)}$ also proposed by Erdős as “perhaps too optimistic”.

For some time, the best upper bound was of the shape

$\displaystyle k \leq N^{1/2} + N^{1/4} + O(1) \ \ \ \ \ (1)$

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

$\displaystyle k \leq N^{1/2} + 0.94304 N^{1/4} + O(1) \ \ \ \ \ (2)$

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 (1). The fact that all the non-zero differences of ${A}$ are disjoint gives rise to a pointwise convolution bound

$\displaystyle 1_A * \tilde 1_A (x) \leq 1 + k 1_{x=0}$

where ${\tilde f(x) = f(-x)}$ denotes the reflection of ${f}$ . Taking inner products with a non-negative autocorrelation function ${w * \tilde w}$ to be chosen later, we conclude that

$\displaystyle \| 1_A * w \|_2^2 \leq \| w \|_1^2 + k \|w\|_2^2.$

Taking the inner product of ${1_A * w}$ with a further weight ${t}$ , and rearranging, we conclude the bound

$\displaystyle \langle 1_A, t * \tilde w \rangle^2 \leq \|t\|_2^2 ( \| w \|_1^2 + k \|w\|_2^2 ).$

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

$\displaystyle t * \tilde w \geq \lambda$

on ${\{1,\dots,N\}}$ , then the left-hand side is at least ${(\lambda k)^2}$ . This gives an inequality

$\displaystyle (\lambda k)^2 \leq \|t\|_2^2 ( \| w \|_1^2 + k \|w\|_2^2 )$

that can be used to bound ${k}$ by choosing ${t, w}$ appropriately. For instance if one selects

$\displaystyle w := 1_{[1, k^{3/2}]}$

and

$\displaystyle t := 1_{[-k^{3/2}, N]}$

then one basically has ${\lambda = k^{3/2}}$ , and the above bound becomes (after ignoring some lower order terms)

$\displaystyle k^5 \leq (N + k^{3/2}) (k^3 + k^{5/2})$

which after some algebra gives (1).

One can improve this bound by replacing the sharply truncated cutoff functions ${w,t}$ 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 ${w,t}$ , but with random choices of ${w,t}$ , in which inequalities such as ${0 \leq w * \tilde w}$ are only true after performing an expectation. The calculations get quite messy (and highly computer-assisted), but eventually give (2). The method also extends to the more general class of ${\gamma}$ -Golomb rulers, in which a given non-zero difference is permitted to appear up to ${\gamma}$ times.

Source: Terence Tao · terrytao.wordpress.com

More From The Board

The mathematical sciences in an AI-enabled world

Weekend reads: Mega-journal on hold at PubMed; 1,400 retractions in one day; ‘I Used AI to Fake a Scientific Paper’

Report of the Summit on Math Research in the Age of AI

Discussion