Erdős Problems

Tags Prizes

SOLVED

Let $A\subseteq \mathbb{N}$. Can there exist some constant $c>0$ such that \[\sum_{n\leq N} 1_A\ast 1_A\ast 1_A(n) = cN+O(1)?\]

#764: [Er70c]

number theory, additive combinatorics

The case of $1_A\ast 1_A(n)$ is the subject of [763].

The answer is no, proved in a strong form by Vaughan [Va72], who showed that in fact \[\sum_{n\leq N} 1_A\ast 1_A\ast 1_A(n) = cN+o\left(\frac{N^{1/4}}{(\log N)^{1/2}}\right)\] is impossible. Vaughan proves a more general result that applies to any $h$-fold convolution, with different main terms permitted.