×

The inverse sieve problem in high dimensions. (English) Zbl 1357.11090

Summary: We show that if a big set of integer points \(S\subseteq [0,N]^d\), \(d> 1\), occupies few residue classes mod \(p\) for many primes \(p\), then it must essentially lie in the solution set of some polynomial equation of low degree. This answers a question of H. A. Helfgott and A. Venkatesh [Analytic number theory. Essays in honour of Klaus Roth on the occasion of his 80th birthday. Cambridge: Cambridge University Press, 224–234 (2009; Zbl 1217.11073)].

MSC:

11N35 Sieves
11B30 Arithmetic combinatorics; higher degree uniformity
11N69 Distribution of integers in special residue classes

Citations:

Zbl 1217.11073
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] E. Bombieri and J. Pila, The number of integral points on arcs and ovals , Duke Math. J. 59 (1989), 337-357. · Zbl 0718.11048 · doi:10.1215/S0012-7094-89-05915-2
[2] A. C. Cojocaru and M. R. Murty, An Introduction to Sieve Methods and Their Applications , London Math. Soc. Stud. Texts 66 , Cambridge Univ. Press, Cambridge, 2006. · Zbl 1121.11063
[3] E. Croot and V. F. Lev, “Open problems in additive combinatorics” in Additive Combinatorics , CRM Proc. Lecture Notes 43 , Amer. Math. Soc., Providence, 2007, 207-233. · Zbl 1183.11005
[4] P. X. Gallagher, A larger sieve , Acta Arith. 18 (1971), 77-81. · Zbl 0231.10028
[5] B. J. Green, Approximate groups and their applications: Work of Bourgain, Gamburd, Helfgott and Sarnak , preprint, [math.NT] 0911.3354v2
[6] B. J. Green, On a variant of the large sieve , preprint, [math.NT] 0807.5037v2
[7] B. J. Green and I. Z. Ruzsa, Freiman’s theorem in an arbitrary abelian group , J. Lond. Math. Soc. (2) 75 (2007), 163-175. · Zbl 1133.11058 · doi:10.1112/jlms/jdl021
[8] B. J. Green, T. Tao, and T. Ziegler, An inverse theorem for the Gowers \(U^{s+1}[N]\)-norm , to appear in Ann. of Math. (2), preprint, [math.CO] 1009.3998v3 · Zbl 1282.11007
[9] R. R. Hall, On pseudo-polynomials , Mathematika 18 (1971), 71-77. · Zbl 0226.10019 · doi:10.1112/S002557930000838X
[10] H. A. Helfgott, Growth and generation in \(\mathrm{SL}_{2}(\mathbb{Z}/p\mathbb{Z})\) , Ann. of Math. (2) 167 (2008), 601-623. · Zbl 1213.20045 · doi:10.4007/annals.2008.167.601
[11] H. A. Helfgott and A. Venkatesh, “How small must ill-distributed sets be?” in Analytic Number Theory: Essays in Honour of Klaus Roth , Cambridge Univ. Press, Cambridge, 2009, 224-234. · Zbl 1217.11073
[12] E. Kowalski, The Large Sieve and Its Applications: Arithmetic Geometry, Random Walks and Discrete Groups , Cambridge Tracts in Math. 175 , Cambridge Univ. Press, Cambridge, 2008. · Zbl 1177.11080
[13] E. Kowalski, The ubiquity of surjective reduction in random groups , unpublished notes, October 2007, .
[14] H. L. Montgomery, A note on the large sieve , J. London Math. Soc. 43 (1968), 93-98. · Zbl 0254.10043 · doi:10.1112/jlms/s1-43.1.93
[15] I. Ruzsa, Jr., On congruence preserving functions , Mat. Lapok. 22 (1971), 125-134. · Zbl 0247.10003
[16] J. Sándor, D. S. Mitrinovic, and B. Crstici, Handbook of Number Theory, I , Springer, Dordrecht, 2006.
[17] T. Tao, Freiman’s theorem for solvable groups , Contrib. Discrete Math. 5 (2010), 137-184. · Zbl 1332.11015
[18] T. Tao and V. Vu, Additive Combinatorics , Cambridge Stud. Adv. Math. 105 , Cambridge Univ. Press, Cambridge, 2006. · Zbl 1127.11002
[19] T. Tao and V. Vu, Inverse Littlewood-Offord theorems and the condition number of random matrices , Ann. of Math. (2) 169 (2009), 595-632. · Zbl 1250.60023 · doi:10.4007/annals.2009.169.595
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.