×

zbMATH — the first resource for mathematics

New bounds on cap sets. (English) Zbl 1262.11010
A set \(A\subseteq \mathbb F^n_3\) is called a cap set if it contains no solutions of the equation \(x+ y+ 7= 0\), \(x,y,7\in A\), \(x\neq y\neq 7\). These sets correspond to arithmetic progressions of the length three in \(\mathbb Z\). Improving a result of R. Meshulom the authors prove that any cap set has size less than \(O({3^n\over n^{1+\varepsilon}})\), where \(\varepsilon> 0\) is an absolute (but small) constant. It corresponds to the famous conjecture of Erdős and Turán on sets without arithmetic progressions. The proof based on new structural results about sets with a nontrivial lower bounds for the additive energy as well as new statements on the spetrum of cap sets.

MSC:
11B30 Arithmetic combinatorics; higher degree uniformity
11T99 Finite fields and commutative rings (number-theoretic aspects)
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
11B75 Other combinatorial number theory
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Ernie Croot and Olof Sisask, A probabilistic technique for finding almost-periods of convolutions, Geom. Funct. Anal. 20 (2010), no. 6, 1367 – 1396. · Zbl 1234.11013
[2] T. Gowers, What is difficult about the cap set problem?, http://gowers.wordpress.com/ 2011/01/11/what-is-difficult-about-the-cap-set-problem/.
[3] (M. Bateman and) N.H. Katz, http://gowers.wordpress.com/2011/01/11/what-is-difficult-about-the-cap-set-problem/# comment-10533.
[4] (M. Bateman and) N.H. Katz, http://gowers.wordpress.com/2011/01/11/what-is-difficult-about-the-cap-set-problem/# comment-10540.
[5] Nets Hawk Katz and Paul Koester, On additive doubling and energy, SIAM J. Discrete Math. 24 (2010), no. 4, 1684 – 1693. · Zbl 1226.05247
[6] Roy Meshulam, On subsets of finite abelian groups with no 3-term arithmetic progressions, J. Combin. Theory Ser. A 71 (1995), no. 1, 168 – 172. · Zbl 0832.11006
[7] Polymath on wikipedia, http://en.wikipedia.org/wiki/Polymath_project#Polymath _Project.
[8] Polymath 6: Improving the bounds for Roth’s theorem, http://polymathprojects.org/ 2011/02/05/polymath6-improving-the-bounds-for-roths-theorem/.
[9] Imre Z. Ruzsa, An analog of Freiman’s theorem in groups, Astérisque 258 (1999), xv, 323 – 326 (English, with English and French summaries). Structure theory of set addition. · Zbl 0946.11007
[10] T. Sanders, A note on Freĭman’s theorem in vector spaces, Combin. Probab. Comput. 17 (2008), no. 2, 297 – 305. · Zbl 1151.15003
[11] T. Sanders, Structure in Sets with Logarithmic Doubling, Arxiv 1002.1552. · Zbl 1310.11013
[12] T. Sanders, On Roth’s Theorem on Progressions, Arxiv 1011.0104. · Zbl 1264.11004
[13] Tomasz Schoen, Near optimal bounds in Freiman’s theorem, Duke Math. J. 158 (2011), no. 1, 1 – 12. · Zbl 1242.11074
[14] I. D. Shkredov, On sets of large trigonometric sums, Izv. Ross. Akad. Nauk Ser. Mat. 72 (2008), no. 1, 161 – 182 (Russian, with Russian summary); English transl., Izv. Math. 72 (2008), no. 1, 149 – 168. · Zbl 1148.11040
[15] Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. · Zbl 1127.11002
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.