×

Discrete spheres and arithmetic progressions in product sets. (English) Zbl 1428.11025

Summary: 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} \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 < \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 > 0\).

MSC:

11B25 Arithmetic progressions
11B30 Arithmetic combinatorics; higher degree uniformity
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] [1]E. Croot and V. Lev, Open problems in additive combinatorics, in: Additive Combinatorics, CRM Proc. Lecture Notes 43, Amer. Math. Soc., Providence, RI, 2007, 207–233. · Zbl 1183.11005
[2] [2]P. P. Pach and C. S’andor, Multiplicative bases and an Erdos problem, arXiv:1602. 06724 (2016)
[3] [3]O. Roche-Newton and D. Zhelezov, A bound on the multiplicative energy of a sum set and extremal sum-product problems, Moscow J. Combin. Number Theory 5 (2015), 52–69. · Zbl 1388.11007
[4] [4]T. Tao, The sum-product phenomenon in arbitrary rings, Contrib. Discrete Math. 4 (2009), 59–82. · Zbl 1250.11011
[5] [5]T. Tao and V. Vu, Additive Combinatorics, Cambridge Stud. Adv. Math. 105, Cambridge Univ. Press, 2006. 248D. Zhelezov
[6] [6]D. Zhelezov, On sets with small additive doubling in product sets, J. Number Theory 157 (2015), 170–183. · Zbl 1332.11016
[7] [7]D. Zhelezov, Improved bounds for arithmetic progressions in product sets, Int. J. Number Theory 11 (2015), 2295–2303. · Zbl 1388.11006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.