## On a conjecture of Sárközy and Szemerédi

### Volume 169 / 2015

#### Abstract

Two infinite sequences $A$ and $B$ of non-negative integers are
called *infinite additive complements* if their sum contains
all sufficiently large integers. In 1994, Sárközy and
Szemerédi conjectured that there exist infinite additive
complements $A$ and $B$ with $\limsup A(x)B(x)/x\le 1$ and
$A(x)B(x)-x=O(\min\{ A(x),B(x)\})$, where $A(x)$ and $B(x)$ are
the counting functions of $A$ and $B$, respectively.
We prove that, for infinite additive complements $A$ and
$B$, if $\limsup A(x)B(x)/x\le 1$, then, for any given $M>1$, we
have $$A(x)B(x)-x\ge (\min \{ A(x), B(x)\})^M$$ for all
sufficiently large integers $x$. This disproves the
above Sárközy–Szemerédi conjecture. We also pose
several problems for further research.