Discrete spheres and arithmetic progressions in product sets

Dmitrii Zhelezov

Published 2015-10-19Version 1

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 $N\geq \pi(M) + M^{2/3-o(1)}$. On the other hand, there are examples for which $N< \pi(M)+ M^{2/3}$. This improves previously known bounds of the form $N = \Omega(\pi(M))$ and $N = O(\pi(M))$, respectively. The main new tool is a reduction of the original problem to the question of an 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 be contained in a sumset $A+A$ unless $|A| \gg n^2$.