A Sharp Bound for Additive Complements

Source abstract

Let $A$ and $B$ be infinite sets of nonnegative integers whose sum contains all sufficiently large integers, and let $A(x)$ and $B(x)$ be their counting functions. We give a discrete proof of the sharp implication $$\limsup_{x\to\infty}\frac{A(x)B(x)}{x}<\frac32 \quad\Longrightarrow\quad A(x)B(x)-x\longrightarrow+\infty.$$ The constant $3/2$ is best possible. Using finite convolution sums, we show that a long gap in one set forces a gap in the other. We then compare the counting functions before and after the gap to obtain the sharp bound.