Logo
All Random Solved Random Open
SOLVED
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$?
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.

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$.