New bounds on cap sets

DOI10.1090/S0894-0347-2011-00725-XMaRDI QIDQ2879894zbMATH OpenWikidataFDO

Authors Michael Bateman, Nets Hawk Katz

Publication date 5 April 2012

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

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

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)

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.

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)\)

Cites work

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

Cited in

(41)

• Exponentially larger affine and projective caps
• \textsc{Superset}: A (super)natural variant of the card game \textsc{Set}
• Logarithmic bounds for Roth's theorem via almost-periodicity
• Growth polynomials for additive quadruples and (h,k)-tuples
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• 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\)
• Energies and structure of additive sets
• Bounds on affine caps
• Finite field models in arithmetic combinatorics -- ten years on
• Bounds on the size of progression-free sets in \(\mathbb{Z}_m^n\)
• Improved bounds for progression-free sets in \(C_8^n\)
• A new construction of caps
• Some properties of lower level-sets of convolutions
• 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
• Arithmetic progressions in sets of small doubling
• A new upper bound for sets with no square differences
• 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\)
• 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
• Progression-free sets
• 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)