Problem Statement
Let $A,B\subseteq \mathbb{N}$ be infinite sets such that $A+B$ contains all large integers. Let $A(x)=\lvert A\cap [1,x]\rvert$ and similarly for $B(x)$. Is it true that if $A(x)B(x)\sim x$ then\[A(x)B(x)-x\to \infty\]as $x\to \infty$?
Categories:
Additive Combinatorics
Progress
A conjecture of Erdős and Danzer. Such sets $A$ and $B$ (with all large integers in $A+B$ and $A(x)B(x)\sim x$) are called exact additive complements. Danzer [Da64] proved that exact additive complements exist (Hanani had earlier conjectured they do not exist).The answer is yes, proved by Sárközy and Szemerédi [SaSz94]. Ruzsa [Ru17] has constructed, for any function $w(x)\to \infty$, such a pair of sets with\[A(x)B(x)-x<w(x)\]for infinitely many $x$.
Source: erdosproblems.com/785 | Last verified: January 16, 2026