On large subsets of F_q^n with no three-term arithmetic progression

DOI10.4007/ANNALS.2017.185.1.8zbMATH Open1425.11020arXiv1605.09223OpenAlexW2963631653MaRDI QIDQ509700FDOQ509700

Authors: Jordan S. Ellenberg, Dion Gijswijt 

Publication date: 17 February 2017

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Abstract: In this note, we show that the method of Croot, Lev, and Pach can be used to bound the size of a subset of $F_q^n$ with no three terms in arithmetic progression by $c^n$ with $c<q$. For $q=3$, the problem of finding the largest subset with no three terms in arithmetic progression is called the `cap problem'. Previously the best known upper bound for the cap problem, due to Bateman and Katz, was $O(3^n/n^{1+epsilon})$.

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

Recommendations

• New bounds on cap sets
• On subsets of \(\mathbb F_q^n\) containing no \(k\)-term progressions
• Bounds on the size of progression-free sets in \(\mathbb{Z}_m^n\)
• On the maximal number of 3-term arithmetic progressions in subsets of ℤ/p ℤ
• Three-term arithmetic progressions in subsets of \(\mathbf{F}_q^\infty\) of large Fourier dimension

zbMATH Keywords

arithmetic progressionsadditive number theoryadditive combinatoricscap sets

Mathematics Subject Classification ID

Combinatorial structures in finite projective spaces (51E20) Arithmetic progressions (11B25) Arithmetic combinatorics; higher degree uniformity (11B30)

Cites Work

• Title not available (Why is that?)
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Extensions of generalized product caps
• On subsets of finite Abelian groups with no 3-term arithmetic progressions
• New bounds on cap sets
• A density version of a geometric Ramsey theorem

Cited In (only showing first 100 items - show all)

• Exponentially larger affine and projective caps
• Solving linear equations in a vector space over a finite field
• The Erdős-Ginzburg-Ziv constant and progression-free subsets
• Erdős-Ginzburg-Ziv constants by avoiding three-term arithmetic progressions
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Approximately strongly regular graphs
• A framework for constructing sets without configurations
• Title not available (Why is that?)
• Near-sunflowers and focal families
• Improved estimates for polynomial Roth type theorems in finite fields
• Exponential bounds for the Erdős-Ginzburg-Ziv constant
• Caps and progression-free sets in \(\mathbb{Z}_m^n\)
• A gap in the slice rank of \(k\)-tensors
• Bounds on affine caps
• On subsets of \(\mathbb F_q^n\) containing no \(k\)-term progressions
• On explicit constructions of designs
• The partition rank of a tensor and \(k\)-right corners in \(\mathbb{F}_q^n\)
• Occurrence of right angles in vector spaces over finite fields
• Bounds on the size of progression-free sets in \(\mathbb{Z}_m^n\)
• Sidon sets and 2-caps in \(\mathbb{F}_3^n\)
• Improved bounds for progression-free sets in \(C_8^n\)
• On the maximal number of 3-term arithmetic progressions in subsets of ℤ/p ℤ
• Extremal Problems on the Hypercube and the Codegree Turán Density of Complete $r$-Graphs
• Threshold functions for incidence properties in finite vector spaces
• New bounds on cap sets
• A Sauer-Shelah-Perles lemma for sumsets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Barriers for fast matrix multiplication from irreversibility
• UPPER BOUNDS FOR SUNFLOWER-FREE SETS
• The sum of nonsingular matrices is often nonsingular
• An asymptotically tight bound for the Davenport constant
• Maximum subsets of \(\mathbb{F}^n_q\) containing no right angles
• Improved bound in Roth's theorem on arithmetic progressions
• On the size of subsets of \(\mathbb{F}_p^n\) without \(p\) distinct elements summing to zero
• New applications of the polynomial method: The cap set conjecture and beyond
• Monochromatic equilateral triangles in the unit distance graph
• Competitive Algorithms for Generalized k -Server in Uniform Metrics
• Removal lemmas and approximate homomorphisms
• Proof of a conjecture of Kleinberg-Sawin-Speyer
• On cap sets and the group-theoretic approach to matrix multiplication
• The chromatic number of Rn$\mathbb {R}^{n}$ with multiple forbidden distances
• Improved Bounds on Sizes of Generalized Caps in $AG(n,q)$
• Large subsets of \(\mathbb{Z}_m^n\) without arithmetic progressions
• Counting SET-free sets
• On the cardinality spectrum and the number of Latin bitrades of order 3
• A DISTRIBUTION ON TRIPLES WITH MAXIMUM ENTROPY MARGINAL
• A tight bound for Green's arithmetic triangle removal lemma in vector spaces
• Subsets without \(q\)-separation and binomial products of Fibonacci numbers
• Arithmetic progressions in multiplicative groups of finite fields
• The analytic rank of tensors and its applications
• The asymptotic induced matching number of hypergraphs: balanced binary strings
• Finding solutions with distinct variables to systems of linear equations over \(\mathbb{F}_p\)
• Further Limitations of the Known Approaches for Matrix Multiplication
• Generalizations of Fourier analysis, and how to apply them
• Multicolour Sunflowers
• Demicaps in \(\mathrm{AG}(4,3)\) and maximal cap partitions
• Four‐term progression free sets with three‐term progressions in all large subsets
• A new exponential upper bound for the Erd\H{o}s-Ginzburg-Ziv constant
• Bounds on sizes of generalized caps in \(\mathrm{AG} (n,q)\) via the Croot-Lev-Pach polynomial method
• Bounds for matchings in nonabelian groups
• Sparse hypergraphs: new bounds and constructions
• A polynomial bound for the arithmetic \(k\)-cycle removal lemma in vector spaces
• An analogue of Ruzsa's conjecture for polynomials over finite fields
• Frames over finite fields: basic theory and equiangular lines in unitary geometry
• The cap set problem and standard diagrams
• Bounds on upper transversals in hypergraphs
• Two remarks on the vectorization problem
• Popular progression differences in vector spaces II
• Tensor slice rank and Cayley's first hyperdeterminant
• On the strength of general polynomials
• On generalized Erdős-Ginzburg-Ziv constants for \(\mathbb{Z}_2^d\)
• Sets Avoiding Six-Term Arithmetic Progressions in $\mathbb{Z}_6^{n}$ are Exponentially Small
• Three-term arithmetic progressions in subsets of F_q^∞ of large Fourier dimension
• A recursive Lovász theta number for simplex-avoiding sets
• Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
• A robust version of Hegedűs's lemma, with applications
• A polynomial ideal associated to any $t$-$(v,k,\lambda)$ design
• On an almost all version of the Balog-Szemeredi-Gowers theorem
• Subrank and optimal reduction of scalar multiplications to generic tensors
• Title not available (Why is that?)
• Universal points in the asymptotic spectrum of tensors
• \(G\)-stable rank of symmetric tensors and log canonical threshold
• Notions of tensor rank
• Avoiding right angles and certain Hamming distances
• The Kelley-Meka bounds for sets free of three-term arithmetic progressions
• Exposé Bourbaki 1196 : Recent progress on bounds for sets with no three terms in arithmetic progression (after Bloom and Sisask, Croot, Lev, and Pach, and Ellenberg and Gijswijt)
• A Gap in the Subrank of Tensors
• Evasive sets, covering by subspaces, and point-hyperplane incidences
• Bounds on the higher degree Erdős-Ginzburg-Ziv constants over \({\mathbb{F}}_q^n\)
• Sharp Effective Finite-Field Nullstellensatz
• Relative rank and regularization
• On the size of subsets of \(\mathbb{F}_q^n\) avoiding solutions to linear systems with repeated columns
• Popular differences for right isosceles triangles
• Using graphs and games to generate cap set bounds
• Avoiding intersections of given size in finite affine spaces \(\operatorname{AG}(n,2)\)
• Title not available (Why is that?)
• Caps and wickets
• On approximability of satisfiable k-CSPs. II

This page was built for publication: On large subsets of \(\mathbb{F}_q^n\) with no three-term arithmetic progression

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