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\H{o}s believed the answer should be no. Erd\H{o}s and S\'{a}rk\"{o}zy proved that\[\frac{\lvert 1_A\ast 1_A(n)-\log n\rvert}{\sqrt{\log n}}\to 0\]is impossible. Erd\H{o}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\'{a}th \cite{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$.


References


[Ho07] G. Horv\'{a}th, An improvement of a theorem of Erd\H{o}s and S\'{a}rk\"{o}zy. Pollack Periodica (2007), 155-161.