A suitably constructed random set has this property if we are allowed to ignore an exceptional set of density zero. The challenge is obtaining this with no exceptional set. Erdős believed the answer should be no. Erdős and Sárközy proved that\[\frac{\lvert 1_A\ast 1_A(n)-\log n\rvert}{\sqrt{\log n}}\to 0\]is impossible. Erdős suggests it may even be true that the $\liminf$ and $\limsup$ of $1_A\ast 1_A(n)/\log n$ are always separated by some absolute constant.

Horváth [Ho07] proved that\[\lvert 1_A\ast 1_A(n)-\log n\rvert \leq (1-\epsilon)\sqrt{\log n}\]cannot hold for all large $n$.

View the LaTeX source

This page was last edited 17 October 2025.