Discrete spheres and arithmetic progressions in product sets

Dmitrii Zhelezov¹

¹ Department of Mathematical Sciences Chalmers University of Technology and University of Gothenburg 41296 Göteborg, Sweden

Acta Arithmetica, Tome 178 (2017) no. 3, pp. 235-248

Résumé

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 \gt 0$, $$ \pi(M) + C \frac {M^{2/3}}{\log^2 M} \leq 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 Pách and Sándor gave an example for which $$ N \lt \pi(M)+ O\biggl(\frac {M^{2/3}}{\log^2 M} \biggr). $$ 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 \gt 0$.

Détail

DOI : 10.4064/aa8332-11-2016

Keywords: prove set positive integers cdot contains arithmetic progression length absolute frac log leq where prime counting function improves previously known bounds form omega gives bound which sharp second order term ndor gave example which biggl frac log biggr main tool reduction original problem question approximate additive decomposition sphere mathbb which set vectors exactly three non zero coordinates namely prove set cannot have additive basis order size absolute constant