Dense infinite Sidon sets

A finite Sidon set in $\{1,\dots,N\}$ can have about $\sqrt N$ elements, but an infinite Sidon set cannot keep up this density at every scale. Erdős asked whether an infinite Sidon set can come within $N^{\varepsilon}$ of the square root for every $\varepsilon$; the best construction, due to Ruzsa, reaches only the exponent $\sqrt2-1\approx0.414$.

Problem

A set $A\subseteq\mathbb{N}$ is a Sidon set if all sums $a+b$ with $a,b\in A$, $a\le b$, are distinct. Is there an infinite Sidon set $A$ such that for every $\varepsilon>0$

$$\lvert A\cap\{1,\dots,N\}\rvert \gg_\varepsilon N^{1/2-\varepsilon}\quad\text{for all } N\ge 1\,?$$

Erdős offered $500 for this question.

Background

Finite Sidon sets in $\{1,\dots,N\}$ of size $(1-o(1))\sqrt N$ exist, but Erdős proved that every infinite Sidon set satisfies

$$\liminf_{N\to\infty}\frac{\lvert A\cap\{1,\dots,N\}\rvert}{N^{1/2}}=0,$$

so the square-root density cannot be sustained. The question is how close one can come. Erdős raised it repeatedly from the 1950s on, with growing rewards: $25 in 1973 for any exponent above $1/3$, later $100 for beating $N^{1/3}$ by any factor tending to infinity. The problem is discussed under C9 in Guy's Unsolved Problems in Number Theory.

What is known

• Greedy. Adding integers one at a time whenever the Sidon property survives gives density $\gg N^{1/3}$.
• Ajtai, Komlós and Szemerédi (1981) found an infinite Sidon set with $\lvert A\cap[1,N]\rvert\gg (N\log N)^{1/3}$, the first improvement over the greedy bound.
• Ruzsa (1998) proved by a probabilistic argument that there is an infinite Sidon set with $\lvert A\cap[1,N]\rvert\ge N^{\sqrt2-1+o(1)}$; Cilleruelo (2014) gave an explicit construction with the same exponent, based on the discrete logarithm. This exponent is still the record.
• Relaxing the Sidon condition. Erdős and Rényi showed by a random construction that, for every $\varepsilon>0$, there are sets with $\lvert A\cap[1,N]\rvert\gg_\varepsilon N^{1/2-\varepsilon}$ in which every integer has a bounded number of representations as $a+b$; the difficulty is to make that number at most one.

What would count as progress

• An infinite Sidon set with $\lvert A\cap[1,N]\rvert\ge N^{c}$ for all large $N$ and some $c>\sqrt2-1$, described explicitly enough that the Sidon property and the density can be checked.
• A proof that some exponent $c<1/2$ cannot be exceeded, which would answer the question negatively.
• A formal proof against the Lean statement in formal-conjectures.

References

1. M. Ajtai, J. Komlós and E. Szemerédi, A dense infinite Sidon sequence, European J. Combin. 2 (1981), 1–11. doi:10.1016/S0195-6698(81)80014-5
2. I. Z. Ruzsa, An infinite Sidon sequence, J. Number Theory 68 (1998), 63–71. doi:10.1006/jnth.1997.2192
3. P. Erdős and A. Rényi, Additive properties of random sequences of positive integers, Acta Arith. 6 (1960), 83–110. doi:10.4064/aa-6-1-83-110
4. J. Cilleruelo, Infinite Sidon sequences, Adv. Math. (2014). arXiv:1209.0326
5. H. Halberstam and K. F. Roth, Sequences, Springer (1983 reprint of the 1966 edition). doi:10.1007/978-1-4613-8227-0

Source

Imported from Erdős Problems 39, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.