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

• A course on large deviations with an introduction to Gibbs measures
• 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)

• \textsc{Superset}: A (super)natural variant of the card game \textsc{Set}
• 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
• On the maximal number of 3-term arithmetic progressions in subsets of ℤ/p ℤ
• 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)
• Some bounds arising from a polynomial ideal associated to any \(t\)-design
• A Gap in the Subrank of Tensors
• Three-term arithmetic progressions in subsets of \(\mathbf{F}_q^\infty\) of large Fourier dimension
• 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
• On an almost all version of the Balog-Szemerédi-Gowers theorem
• 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)\)
• Caps and wickets
• On approximability of satisfiable k-CSPs. II
• Interview with Yufei Zhao
• On subsets of the hypercube with prescribed Hamming distances
• How many cards should you lay out in a game of \textit{EvenQuads}: a detailed study of caps in \(\mathrm{AG}(n, 2)\)
• Transcendence of polynomial canonical heights
• Weighted slice rank and a minimax correspondence to Strassen's spectra
• Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
• Title not available (Why is that?)
• Almost every matroid has an \(M(K_4)\)- or a \(\mathcal{W}^3\)-minor
• On the Harborth constant of \(C_3 \oplus C_{3p}\)
• Mathematical reasoning and the computer
• Odd-sunflowers
• What is the point of computers? A question for pure mathematicians
• On arithmetic progressions in symmetric sets in finite field model
• Sumsets as unions of sumsets of subsets
• Partial Degeneration of Tensors
• 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
• 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\)
• Further limitations of the known approaches for matrix multiplication
• 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?)
• Barriers for fast matrix multiplication from irreversibility
• UPPER BOUNDS FOR SUNFLOWER-FREE SETS
• The sum of nonsingular matrices is often nonsingular
• Multicolour sunflowers
• Maximum subsets of \(\mathbb{F}^n_q\) containing no right angles
• Sets avoiding six-term arithmetic progressions in \(\mathbb{Z}_6^n\) are exponentially small
• 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
• 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 the communication complexity of high-dimensional permutations
• On cap sets and the group-theoretic approach to matrix multiplication
• The chromatic number of Rn$\mathbb {R}^{n}$ with multiple forbidden distances
• 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 tight bound for Green's arithmetic triangle removal lemma in vector spaces
• Sunflowers and quasi-sunflowers from randomness extractors
• 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
• Extremal problems on the hypercube and the codegree Turán density of complete \(r\)-graphs
• The asymptotic induced matching number of hypergraphs: balanced binary strings
• An asymptotically tight bound for the Davenport constant
• 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\)
• Generalizations of Fourier analysis, and how to apply them
• 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

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)