New bounds on cap sets

DOI10.1090/S0894-0347-2011-00725-XzbMATH Open1262.11010arXiv1101.5851WikidataQ60568643 ScholiaQ60568643MaRDI QIDQ2879894FDOQ2879894

Authors: Michael Bateman, Nets Hawk Katz 

Publication date: 5 April 2012

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

Abstract: We provide an improvement over Meshulam's bound on cap sets in $F_3^N$. We show that there exist universal $epsilon>0$ and $C>0$ so that any cap set in $F_3^N$ has size at most $C{3}^{N}over{N}^{1+epsilon}$. We do this by obtaining quite strong information about the additive combinatorial properties of the large spectrum.

Full work available at URL: https://arxiv.org/abs/1101.5851

Recommendations

• Bounds on affine caps
• Exponentially larger affine and projective caps
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• Using graphs and games to generate cap set bounds
• Improved bounds on sizes of generalized caps in \(AG(n,q)\)

Mathematics Subject Classification ID

Other combinatorial number theory (11B75) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Arithmetic combinatorics; higher degree uniformity (11B30) Finite fields and commutative rings (number-theoretic aspects) (11T99)

Cites Work

• Additive combinatorics
• On additive doubling and energy
• On Roth's theorem on progressions
• On subsets of finite Abelian groups with no 3-term arithmetic progressions
• On sets of large trigonometric sums
• A Note on Freĭman's Theorem in Vector Spaces
• Title not available (Why is that?)
• A probabilistic technique for finding almost-periods of convolutions
• Near optimal bounds in Freiman's theorem
• Structure in sets with logarithmic doubling

Cited In (42)

• Exponentially larger affine and projective caps
• Logarithmic bounds for Roth's theorem via almost-periodicity
• \textsc{Superset}: A (super)natural variant of the card game \textsc{Set}
• Growth polynomials for additive quadruples and \((h,k)\)-tuples
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Sunflowers and testing triangle-freeness of functions
• A quantitative improvement for Roth's theorem on arithmetic progressions: Table 1.
• A subexponential upper bound for van der Waerden numbers \(W(3,k)\)
• Caps and progression-free sets in \(\mathbb{Z}_m^n\)
• Bounds on affine caps
• Energies and structure of additive sets
• Finite field models in arithmetic combinatorics -- ten years on
• Bounds on the size of progression-free sets in \(\mathbb{Z}_m^n\)
• Some properties of lower level-sets of convolutions
• Improved bounds for progression-free sets in \(C_8^n\)
• A new construction of caps
• Improved bound in Roth's theorem on arithmetic progressions
• The Kelley-Meka bounds for sets free of three-term arithmetic progressions
• Additive dimension and a theorem of Sanders
• On the missing log in upper tail estimates
• The cap set problem
• The \(G\)-stable rank for tensors and the cap set problem
• Using graphs and games to generate cap set bounds
• Roth's theorem for four variables and additive structures in sums of sparse sets
• A new upper bound for sets with no square differences
• Arithmetic progressions in sets of small doubling
• On sunflowers and matrix multiplication
• The analytic rank of tensors and its applications
• Multi-wise and constrained fully weighted Davenport constants and interactions with coding theory
• The NOF multiparty communication complexity of composed functions
• Caps and wickets
• On approximability of satisfiable k-CSPs. II
• Some new results on higher energies
• Improved bounds on sizes of generalized caps in \(AG(n,q)\)
• Finding solutions with distinct variables to systems of linear equations over \(\mathbb{F}_p\)
• Progression-free sets
• On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression
• Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small
• Bounds on sizes of generalized caps in \(\mathrm{AG} (n,q)\) via the Croot-Lev-Pach polynomial method
• Mixing for progressions in nonabelian groups.
• New applications of the polynomial method: the cap set conjecture and beyond
• The cap set problem and standard diagrams

This page was built for publication: New bounds on cap sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2879894)