Progression-free sets in Z₄^n are exponentially small

DOI10.4007/ANNALS.2017.185.1.7zbMATH Open1425.11019arXiv1605.01506OpenAlexW2559529531MaRDI QIDQ509698FDOQ509698

Péter Pál Pach, Vsevolod F. Lev, Ernie Croot

Publication date: 17 February 2017

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

Abstract: We show that for integer $n>0$, any subset $Asubset{Z}_4^n$ free of three-term arithmetic progressions has size $|A|<4^{cn}$, with an absolute constant $capprox0.926$.

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

zbMATH Keywords

three-term arithmetic progressionscapsetRoth-MeshulamRoth's theorem

Mathematics Subject Classification ID

Arithmetic progressions (11B25) Additive bases, including sumsets (11B13)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On triples in arithmetic progression
• On Certain Sets of Integers
• A quantitative improvement for Roth's theorem on arithmetic progressions: Table 1.
• On Roth's theorem on progressions
• Progression-free sets in finite abelian groups.
• On subsets of finite Abelian groups with no 3-term arithmetic progressions
• Integer sets containing no arithmetic progressions
• New bounds on cap sets
• On certain other sets of integers
• Integer Sets Containing No Arithmetic Progressions
• On subsets of abelian groups with no 3-term arithmetic progression
• A density version of a geometric Ramsey theorem
• Character-free approach to progression-free sets
• Roth's theorem in \(\mathbb Z^n_4\)

Cited In (87)

• A recursive Lovász theta number for simplex-avoiding sets
• A robust version of Hegedűs's lemma, with applications
• A polynomial ideal associated to any $t$-$(v,k,\lambda)$ design
• Efficiently-verifiable strong uniquely solvable puzzles and matrix multiplication
• Notions of tensor rank
• Avoiding right angles and certain Hamming distances
• The Erdős–Moser Sum-free Set Problem
• 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\)
• Relative rank and regularization
• On the size of subsets of \(\mathbb{F}_q^n\) avoiding solutions to linear systems with repeated columns
• 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
• Interview with Larry Guth
• Interview with Yufei Zhao
• 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
• Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
• Title not available (Why is that?)
• Odd-sunflowers
• Exponentially larger affine and projective caps
• The Erdős-Ginzburg-Ziv constant and progression-free subsets
• Erdős-Ginzburg-Ziv constants by avoiding three-term arithmetic progressions
• Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• 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
• 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
• On an almost all version of the Balog-Szemeredi-Gowers theorem
• 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\)
• Threshold functions for incidence properties in finite vector spaces
• A Sauer-Shelah-Perles lemma for sumsets
• Title not available (Why is that?)
• Title not available (Why is that?)
• UPPER BOUNDS FOR SUNFLOWER-FREE SETS
• The sum of nonsingular matrices is often nonsingular
• Universal points in the asymptotic spectrum of tensors
• Maximum subsets of \(\mathbb{F}^n_q\) containing no right angles
• A remark on sets with few distances in $\mathbb {R}^{d}$
• 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
• Solvingxz=y²in Certain Subsets of Finite Groups
• New applications of the polynomial method: The cap set conjecture and beyond
• Monochromatic equilateral triangles in the unit distance graph
• 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)$
• Sharp Effective Finite-Field Nullstellensatz
• An upper bound for the size of \(s\)-distance sets in real algebraic sets
• A uniform version of a theorem by Dvir and Moran
• The \(G\)-stable rank for tensors and the cap set problem
• Popular differences for right isosceles triangles
• A DISTRIBUTION ON TRIPLES WITH MAXIMUM ENTROPY MARGINAL
• A tight bound for Green's arithmetic triangle removal lemma in vector spaces
• Arithmetic progressions in multiplicative groups of finite fields
• The analytic rank of tensors and its applications
• Exponential lower bounds on the generalized Erdős-Ginzburg-Ziv constant
• On subsets of the hypercube with prescribed Hamming distances
• Finding solutions with distinct variables to systems of linear equations over \(\mathbb{F}_p\)
• Generalizations of Fourier analysis, and how to apply them
• Multicolour Sunflowers
• 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
• On the Harborth constant of \(C_3 \oplus C_{3p}\)
• Bounds on sizes of generalized caps in \(\mathrm{AG} (n,q)\) via the Croot-Lev-Pach polynomial method
• Bounds for matchings in nonabelian groups
• A polynomial bound for the arithmetic \(k\)-cycle removal lemma in vector spaces
• On arithmetic progressions in symmetric sets in finite field model
• An analogue of Ruzsa's conjecture for polynomials over finite fields
• Frames over finite fields: basic theory and equiangular lines in unitary geometry
• Sumsets as unions of sumsets of subsets
• The cap set problem and standard diagrams
• Bounds on upper transversals in hypergraphs
• Popular progression differences in vector spaces II
• Tensor slice rank and Cayley's first hyperdeterminant
• On the strength of general polynomials
• Sets Avoiding Six-Term Arithmetic Progressions in $\mathbb{Z}_6^{n}$ are Exponentially Small

Recommendations

• Sets of integers that do not contain long arithmetic progressions 👍 👎
• A quantitative improvement for Roth's theorem on arithmetic progressions: Table 1. 👍 👎
• On subsets of finite Abelian groups with no 3-term arithmetic progressions 👍 👎
• Three-term arithmetic progressions and sumsets 👍 👎
• The Erdős-Ginzburg-Ziv constant and progression-free subsets 👍 👎
• Erdős-Ginzburg-Ziv constants by avoiding three-term arithmetic progressions 👍 👎
• Bounds on the size of progression-free sets in \(\mathbb{Z}_m^n\) 👍 👎
• Improved bounds for progression-free sets in \(C_8^n\) 👍 👎
• Solvingxz=y²in Certain Subsets of Finite Groups 👍 👎
• Roth's theorem in \(\mathbb Z^n_4\) 👍 👎

This page was built for publication: Progression-free sets in \(\mathbb{Z}_4^n\) are exponentially small

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