Discrete spheres and arithmetic progressions in product sets

Abstract

We prove that if $B$ is a set of $N$ positive integers such that $B\cdot B$ contains an arithmetic progression of length $M$, then for some absolute $C>0$, $$\pi (M)+C\frac{M^{2/3}}{{\log }^{2}M}\le N,$$ where $\pi$ is the prime counting function. This improves on previously known bounds of the form $N=\Omega (\pi (M))$ and gives a bound which is sharp up to the second order term, as Pach and Sándor gave an example for which $$N<\pi (M)+O\left(\frac{M^{2/3}}{{\log }^{2}M}\right).$$ The main new tool is a reduction of the original problem to the question of approximate additive decomposition of the $3$-sphere in ${\mathbb{F}}_3^n$ which is the set of $\{0,1\}$ vectors with exactly three non-zero coordinates. Namely, we prove that such a set cannot have an additive basis of order two of size less than $c{n}^2$ with absolute constant $c>0$.

arXiv commentAn updated version with an essentially sharp bound. To appear in Acta Arithmetica