Erdős #1194 · additive combinatorics / additive basis

Such a set is called a perfect difference set; they can be constructed, for example, by a greedy approach (as detailed by Lev [Le04]). The greedy construction achieves $a_n\ll n^3$.

Erdős [Er80] wrote it is 'easy to see' that

Indeed, since $A$ must be a Sidon set, if $a_n \leq f(n)n$ for all $n$, then all differences in $[1,x/f(x)]$ can be realised by differences from $A\cap [1,x]$, and hence $\lvert A\cap [1,x]\rvert^2 \gg x/f(x)$. Erdős (see for example [HaRo66]) proved that for infinitely many $x$ $\lvert A\cap [1,x]\rvert \ll (x/\log x)^{1/2}$, which is a contradiction for a suitable choice of $f$.

This argument proves that $a_n\gg n\log n$ for infinitely many $n$.

Cilleruelo and Nathanson [CiNa08] describe a method for construction dense perfect difference sets from dense Sidon sets, allowing many of the results for the latter to transfer to the former.

GPT-5.4 Pro (see the comments) has given an argument which proves that $a_n\gg n^{2-o(1)}$ infinitely often; in fact $a_n \gg n^2/f(n)$ infinitely often for any function $f$ such that $\sum \frac{1}{nf(n)}$ diverges.

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.