# Open question: best bounds for cap sets

23 February, 2007 in math.CO, question | Tags: additive combinatorics, cap sets, finite fields, Roth's theorem, Szemeredi's theorem

What’s new

Updates on my research and expository papers, discussion of open problems, and other maths-related topics. By Terence Tao

23 February, 2007 in math.CO, question | Tags: additive combinatorics, cap sets, finite fields, Roth's theorem, Szemeredi's theorem

gninrepoli on The parity problem obstruction… | |

Terence Tao on Finite time blowup for an aver… | |

Terence Tao on An averaged form of Chowla… | |

Anonymous on An averaged form of Chowla… | |

shaurabh aggarwal on Finite time blowup for an aver… | |

matthew miller on Finite time blowup for an aver… | |

matthew miller on Finite time blowup for an aver… | |

gninrepoli on The Riemann hypothesis in vari… | |

Terence Tao on The cubic nonlinear Schrödinge… | |

observer on Mikhail Gromov wins 2009 Abel… | |

Anonymous on The cubic nonlinear Schrödinge… | |

Terence Tao on An averaged form of Chowla… | |

Anonymous on An averaged form of Chowla… | |

Anonymous on 245B, Notes 6: Duality and the… | |

Terence Tao on 245B, Notes 6: Duality and the… |

- Gene Weingarten – Pearls before breakfast
- Isaac Asimov – The relativity of wrong
- Jonah Lehrer – Don't! – the secret of self-control
- Julianne Dalcanton – The cult of genius
- Nassim Taleb – The fourth quadrant: a map of the limits of statistics
- Paul Graham – What You'll Wish You'd Known
- Po Bronson – How not to talk to your kids
- Scott Aaronson – Ten signs a claimed mathematical proof is wrong
- Timothy Gowers – Elsevier — my part in its downfall
- Timothy Gowers – The two cultures of mathematics
- William Thurston – On proof and progress in mathematics

- Abstruse Goose
- Assembler
- BoxCar2D
- Factcheck.org
- FiveThirtyEight
- Gapminder
- Literally Unbelievable
- Planarity
- PolitiFact
- Quite Interesting
- snopes
- Strange maps
- Television tropes and idioms
- The Daily Show with Jon Stewart
- The Economist
- The Onion
- The Straight Dope
- This American Life on the financial crisis I
- This American Life on the financial crisis II
- What if? (xkcd)
- White whine
- xkcd

- 0xDE
- A Mind for Madness
- A Portion of the Book
- Absolutely useless
- Alex Sisto
- AMS blogs
- AMS Graduate Student Blog
- Analysis & PDE
- Analysis & PDE Conferences
- Annoying Precision
- Area 777
- Ars Mathematica
- ATLAS of Finite Group Representations
- Automorphic forum
- Avzel's journal
- Blog on Math Blogs
- Blog On Mathematical Journals
- blogderbeweise
- Bubbles Bad; Ripples Good
- Cédric Villani
- Climbing Mount Bourbaki
- Coloquio Oleis
- Combinatorics and more
- Compressed sensing resources
- Computational Complexity
- Concrete nonsense
- David Mumford's blog
- Delta epsilons
- DispersiveWiki
- Disquisitiones Mathematicae
- Embûches tissues
- Emmanuel Kowalski’s blog
- Encyclopedia of Mathematics
- Equatorial Mathematics
- fff
- Floer Homology
- Frank Morgan’s blog
- Gérard Besson's Blog
- Gödel’s Lost Letter and P=NP
- Geometric Group Theory
- Geometry and the imagination
- Geometry Bulletin Board
- Girl's Angle
- God Plays Dice
- Good Math, Bad Math
- Graduated Understanding
- Hydrobates
- I Woke Up In A Strange Place
- Igor Pak's blog
- Images des mathématiques
- In theory
- James Colliander's Blog
- Jérôme Buzzi’s Mathematical Ramblings
- Joel David Hamkins
- Journal of the American Mathematical Society
- Kill Math
- Le Petit Chercheur Illustré
- Lemma Meringue
- Lewko's blog
- Libres pensées d’un mathématicien ordinaire
- LMFDB – L-functions and modular forms database
- LMS blogs page
- London number theory
- Low Dimensional Topology
- M-Phi
- MAA MinuteMath
- Math Overflow
- Mathbabe
- Mathblogging
- Mathematical musings
- Mathematics Illuminated
- Mathematics in Australia
- Mathematics Jobs Wiki
- Mathematics Stack Exchange
- Mathematics under the Microscope
- Mathlog
- MathOnline
- Mathtube
- Matt Baker's Math Blog
- Mixedmath
- Motivic stuff
- Much ado about nothing
- Multiple Choice Quiz Wiki
- neverendingbooks
- nLab
- Noncommutative geometry blog
- Nonlocal equations wiki
- Not "Not Even Wrong"
- Nuit-blanche
- Number theory web
- outofprintmath
- PDE blog
- Pengfei Zhang's blog
- Peter Cameron's Blog
- Phillipe LeFloch's blog
- ProofWiki
- Quomodocumque
- Random Math
- Reasonable Deviations
- Regularize
- Rigorous Trivialities
- Roots of unity
- Secret Blogging Seminar
- Selected Papers Network
- Sergei Denisov's blog
- Shtetl-Optimized
- Shuanglin's Blog
- Since it is not…
- Sketches of topology
- Soft questions
- Stacks Project Blog
- SymOmega
- tcs math
- TeX, LaTeX, and friends
- The accidental mathematician
- The Cost of Knowledge
- The Everything Seminar
- The Geomblog
- The Mathematics Literature Project
- The n-Category Café
- The n-geometry cafe
- The On-Line Blog of Integer Sequences
- The polylogblog
- The polymath blog
- The polymath wiki
- The Tricki
- The twofold gaze
- The Unapologetic Mathematician
- The value of the variable
- The World Digital Mathematical Library
- Theoretical Computer Science – StackExchange
- Tim Gowers’ blog
- Tim Gowers’ mathematical discussions
- Todd and Vishal’s blog
- Van Vu's blog
- Vaughn Climenhaga
- Vieux Girondin
- Visual Insight
- Vivatsgasse 7
- Williams College Math/Stat Blog
- Windows on Theory
- Wiskundemeisjes
- XOR’s hammer
- Zhenghe's Blog

- A cheap version of nonstandard analysis
- A review of probability theory
- American Academy of Arts and Sciences speech
- Amplification, arbitrage, and the tensor power trick
- An airport-inspired puzzle
- Benford's law, Zipf's law, and the Pareto distribution
- Compressed sensing and single-pixel cameras
- Einstein’s derivation of E=mc^2
- On multiple choice questions in mathematics
- Quantum mechanics and Tomb Raider
- Real analysis problem solving strategies
- Sailing into the wind, or faster than the wind
- Simons lectures on structure and randomness
- Small samples, and the margin of error
- Soft analysis, hard analysis, and the finite convergence principle
- The blue-eyed islanders puzzle
- The cosmic distance ladder
- The federal budget, rescaled
- Ultrafilters, non-standard analysis, and epsilon management
- What is a gauge?
- What is good mathematics?
- Why global regularity for Navier-Stokes is hard

- Career advice
- The Euler-Maclaurin formula, Bernoulli numbers, the zeta function, and real-variable analytic continuation
- Does one have to be a genius to do maths?
- An averaged form of Chowla's conjecture
- On writing
- Books
- Mikhail Gromov wins 2009 Abel prize
- There’s more to mathematics than rigour and proofs
- The blue-eyed islanders puzzle
- The cubic nonlinear Schrödinger equation in two dimensions with radial data

- March 2015 (2)
- February 2015 (4)
- January 2015 (4)
- December 2014 (6)
- November 2014 (5)
- October 2014 (4)
- September 2014 (3)
- August 2014 (4)
- July 2014 (5)
- June 2014 (5)
- May 2014 (5)
- April 2014 (2)
- March 2014 (4)
- February 2014 (5)
- January 2014 (4)
- December 2013 (4)
- November 2013 (5)
- October 2013 (4)
- September 2013 (5)
- August 2013 (1)
- July 2013 (7)
- June 2013 (12)
- May 2013 (4)
- April 2013 (2)
- March 2013 (2)
- February 2013 (6)
- January 2013 (1)
- December 2012 (4)
- November 2012 (7)
- October 2012 (6)
- September 2012 (4)
- August 2012 (3)
- July 2012 (4)
- June 2012 (3)
- May 2012 (3)
- April 2012 (4)
- March 2012 (5)
- February 2012 (5)
- January 2012 (4)
- December 2011 (8)
- November 2011 (8)
- October 2011 (7)
- September 2011 (6)
- August 2011 (8)
- July 2011 (9)
- June 2011 (8)
- May 2011 (11)
- April 2011 (3)
- March 2011 (10)
- February 2011 (3)
- January 2011 (5)
- December 2010 (5)
- November 2010 (6)
- October 2010 (9)
- September 2010 (9)
- August 2010 (3)
- July 2010 (4)
- June 2010 (8)
- May 2010 (8)
- April 2010 (8)
- March 2010 (8)
- February 2010 (10)
- January 2010 (12)
- December 2009 (11)
- November 2009 (8)
- October 2009 (15)
- September 2009 (6)
- August 2009 (13)
- July 2009 (10)
- June 2009 (11)
- May 2009 (9)
- April 2009 (11)
- March 2009 (14)
- February 2009 (13)
- January 2009 (18)
- December 2008 (8)
- November 2008 (9)
- October 2008 (10)
- September 2008 (5)
- August 2008 (6)
- July 2008 (7)
- June 2008 (8)
- May 2008 (11)
- April 2008 (12)
- March 2008 (12)
- February 2008 (13)
- January 2008 (17)
- December 2007 (10)
- November 2007 (9)
- October 2007 (9)
- September 2007 (7)
- August 2007 (9)
- July 2007 (9)
- June 2007 (6)
- May 2007 (10)
- April 2007 (11)
- March 2007 (9)
- February 2007 (4)

- expository (214)
- tricks (8)

- guest blog (9)
- Mathematics (605)
- math.AC (5)
- math.AG (37)
- math.AP (82)
- math.AT (15)
- math.CA (117)
- math.CO (142)
- math.CT (6)
- math.CV (12)
- math.DG (32)
- math.DS (62)
- math.FA (22)
- math.GM (9)
- math.GN (21)
- math.GR (76)
- math.GT (12)
- math.HO (9)
- math.IT (8)
- math.LO (46)
- math.MG (34)
- math.MP (25)
- math.NA (12)
- math.NT (113)
- math.OA (17)
- math.PR (77)
- math.QA (5)
- math.RA (23)
- math.RT (21)
- math.SG (4)
- math.SP (42)
- math.ST (4)

- non-technical (119)
- admin (41)
- advertising (16)
- diversions (4)
- media (11)
- journals (2)

- obituary (8)

- opinion (27)
- paper (154)
- question (95)
- polymath (68)

- talk (62)
- DLS (19)

- teaching (141)
- 245A – Real analysis (11)
- 245B – Real analysis (19)
- 245C – Real analysis (6)
- 254A – analytic prime number theory (15)
- 254A – ergodic theory (18)
- 254A – Hilbert's fifth problem (12)
- 254A – random matrices (14)
- 254B – expansion in groups (8)
- 254B – Higher order Fourier analysis (9)
- 285G – poincare conjecture (20)
- Logic reading seminar (8)

- travel (25)
- Uncategorized (2)

- An error has occurred; the feed is probably down. Try again later.

additive combinatorics
almost orthogonality
approximate groups
arithmetic progressions
Ben Green
Cauchy-Schwarz
Cayley graphs
characters
circular law
compactness
compressed sensing
concentration compactness
correspondence principle
eigenvalues
Elias Stein
Emmanuel Breuillard
entropy
equidistribution
ergodic theory
expander graphs
exponential sums
finite fields
Fourier transform
Four Moment Theorem
Freiman's theorem
Gowers uniformity norms
gradient shrinking solitons
graph theory
Gromov's theorem
GUE
Hilbert's fifth problem
hypergraphs
inverse conjecture
Kakeya conjecture
Lie algebras
Lie groups
Littlewood-Offord problem
Mobius function
multiple recurrence
Navier-Stokes equations
nilpotent groups
NLS
nonstandard analysis
parity problem
politics
polymath1
polymath8
polynomial method
polynomials
prime numbers
prime number theorem
project heatwave
random matrices
randomness
random walks
Ratner's theorem
regularity lemma
Ricci flow
Riemann zeta function
Schrodinger equation
Selberg sieve
sieve theory
spectral theorem
structure
Szemeredi's theorem
szemeredi regularity lemma
Tamar Ziegler
ultrafilters
ultraproducts
universality
Van Vu
wave maps
Weil conjectures
Wigner matrices
Yitang Zhang

- Two polymath (of a sort) proposed projects 20 January, 2014
- Polymath9: P=NP? (The Discretized Borel Determinacy Approach) 4 November, 2013
- Polymath8 – A Success ! 20 September, 2013
- Polymath7 research thread 5: the hot spots conjecture 9 August, 2013
- Polymath proposal: bounded gaps between primes 4 June, 2013
- Polymath proposal (Tim Gowers): Randomized Parallel Sorting Algorithm 2 March, 2013
- Next Polymath Project(s): What, When, Where? 14 February, 2013
- Polymath7 research threads 4: the Hot Spots Conjecture 10 September, 2012
- Minipolymath4 project, second research thread 13 July, 2012
- Minipolymath4 project: IMO 2012 Q3 12 July, 2012

- Save pure mathematics at the VU University of Amsterdam 30 April, 2011
- ERA results for mathematical sciences in Australia 15 February, 2011
- Junior positions at ANU 8 November, 2010
- AustMS now on twitter 10 October, 2010
- Research not bad, but not stellar 9 May, 2010
- L’Oréal Australia For Women In Science Fellowships 11 April, 2010
- Postdoctoral position (Level A) in mathematics at Australian National University 18 January, 2010
- Cheryl Praeger named as 2009 Western Australian Scientist of the Year 2 December, 2009
- Positions at Australian National University 4 November, 2009
- Mathematics skills out for the count 26 October, 2009

To enter in LaTeX in comments, use $latex *<Your LaTeX code>*$ (without the < and > signs, of course; in fact, these signs should be avoided as they can cause formatting errors). See the about page for details and for other commenting policy.

%d bloggers like this:

## 25 comments

Comments feed for this article

24 February, 2007 at 2:06 pm

TomAbout your postscriptum: apparently there’s an easy way to add some LaTeX in blogger, see:

http://wolverinex02.googlepages.com/emoticonsforblogger2

24 February, 2007 at 6:10 pm

Kate SandersteadA word of warning: your math images are going to be very unstable – they rely on a script running at forkosh.com. If this goes offline for some reason all the formulae in your posts will disappear!

Seeing as this blog is only just starting, I suggest you move to wordpress.com, which seems to have (very recently) acquired LaTeX support without any hacks:

http://faq.wordpress.com/2007/02/18/can-i-put-math-or-equations-in-my-posts/

All the best,

Kate

27 February, 2007 at 9:32 am

AnonymousThe size of the largest cap sets for F_3^n for n=1,2,3 and 4 are 2,4,9 and 20 right?

Just checking if my second year math project (on the mathematics of Set) is actually related to this.

9 March, 2007 at 12:45 am

Gil KalaiIndeed this is a great problem. The Roth-Meshulam argument says something like:

If the density of a set A is t then there is a co-dimension one subspace where the density is f(t).

To get f(t) you have to balance between two scenarios: if there is a large Fourier coefficient (for the characteristic function of A) then this gives you a subspace with higher density right a way. If there is not, a little computation based on Parseval’s theorem tells you that you will get the desired improvement “on average”.

And now you iterate and get the theorem. Because if the density is larger than 2/3 you certainly have a line there. (What is beautiful about Meshulam’s argument is that various difficulties in the method in other cases vanish and we get “right to the point”.)

In this problem, as in other combinatorial problems, gradually increasing the density (by moving to a co-dimension one subspace) is the only known method to get anything non-trivial. It looks that we already reached the limit of what this method gives. As far as I know there is no known way to jump directly to low-dimensional subspaces and get better density improvements.

9 March, 2007 at 4:44 am

GilCorrection: I oversimplified the argument a bit: Either you get close to

the “right number of lines” (calculated for the case that your set is random?) OR you have a subspace with larger density f(t).

11 March, 2007 at 5:59 pm

Greg KuperbergI thought about this a bit and I do not quite understand the finite field heuristic in combinatorics. For instance, we can also define a line in as a triple that sums to 0. If so, then is a terrible approximation to , because the latter has sets of positive density without such triples.

The lines in are an example of a Steiner triple system, or otherwise they may be viewed as just a collection of triples of points, where . I have a heuristic calculation that suggests that if the collection is unstructured, then you can only expect triple-free sets of size . This suggests that the structure of the lines in and the arithmetic progressions in are unusually favorable for the existence of large triple-free sets. Granted, Ben Green and others have much more experience with these problems than I do. Can someone say why these two collections of triples are considered to be comparably favorable?

Does the empirical data have something to do with it? The maximum cap set cardinality is sequence A090245 in Sloane’s Encyclopedia of Integer Sequences. The known terms are 2,4,9,20,45, and (according to a review article by Davis and Maclagan) the next term is between 112 and 114. Well, this small amount of data does suggest that Meshulam’s bound is not far from the truth. What about subsets of that do not have triples in arithmetic progression?

11 March, 2007 at 9:35 pm

Terence TaoDear Greg,

It does seem on first glance that there should not be much difference between lines and triples summing to zero , but the theory for these two patterns very different (though of course they are the same for the characteristic 3 setting of ). The reason is the following: any dense set will necessarily contain a large number of

triviallines , but there is no corresponding notion of a “trivial” triple summing to zero that all dense sets will contain lots of (except in characteristic 3). Because of this, we do not expect dense sets to necessarily contain triples summing to zero in general, whereas we do expect dense sets to contain lines (or more precisely arithmetic progressions of length three).There appears to be a deep fact, not well understood at present, that if a “low-complexity object” (such as a set) necessarily contains many “trivial” examples of a “high-complexity object” (such as a line), then it must also contain many non-trivial examples of that high-complexity object as well. It is not always true, of course; it seems to require a certain amount of “symmetry” or “homogeneity” present in the problem. (It also requires the trivial solutions to be arranged in a suitably “transverse” manner, which I won’t define here.) Nevertheless, this deep fact seems to be rather important; it explains, for instance, we can find infinitely many arithmetic progressions in the primes, or even polynomial progressions where all the integer polynomials have zero constant coefficient, but we cannot currently find infinitely many twin primes .

There is a family of results with names such as the “hypergraph removal lemma” which attempt to make this type of intuition precise, and which have led to a number of deep consequences in property testing. Many recurrence theorems in ergodic theory (e.g. the Poincare recurrence theorem) have this flavour also, since a set can trivially recur to itself if you allow to iterate 0 times rather than a positive number of times.

One well-known place where this deep fact manifests itself is Ramsey theory. One formulation of Ramsey’s theorem is that if there is a symmetric binary relation between sufficiently many people, then one can find (say) 100 people between which the relation is always true or always false. Note that the claim is trivial if you allow the 100 people to be the same. On the other hand, the claim fails if you drop the symmetry assumption.

To address your final comment, I think the number of empirical data points we have is too small to meaningfully extract any convincing conclusion; the above phenomenon seems to be an asymptotic one only.

p.s. Regarding the “finite field heuristic”, one caveat is that the characteristic of the finite field should be large enough to avoid various local obstructions; for instance, Roth’s theorem is rather silly in characteristic 2. It turns out that characteristic 3 seems to enough to model arithmetic progressions of length three properly, whereas to model triples summing to zero one needs characteristic 5 at least.

23 June, 2008 at 2:40 pm

Michael Nowak2WIsbw Blogs rating, add your blog to be rated for free:

http://blogsrate.net

28 September, 2008 at 2:32 pm

Gil KalaiWhile Roth theorem indeed does not make much sense for characteristic 2, the central ingredient of its wonderful proof is quite important also in characteristic 2 in the context of “linearity testing” in TCS.

30 September, 2008 at 9:45 am

Terence TaoDear Gil,

While on the topic of characteristic 2, it is interesting to note that Sanders has recently managed to improve the upper bound for capsets for the space instead of , precisely by exploiting a certain degeneracy of length three progressions in this setting; see

http://arxiv.org/abs/0807.5101

1 February, 2009 at 3:03 pm

Mathematics, Science, and Blogs « Combinatorics and more[…] (There is a famous problem regarding the density needed.) This problem is reviwed by Terry Tao here. I am not sure if the regularity lemma approach works for this problem; Hillel and Izzy proved […]

7 February, 2009 at 9:45 am

Upper and lower bounds for the density Hales-Jewett problem « What’s new[…] lines, defined as a triple where ; such sets are known as capsets. Clearly . As noted my previous blog post, the best asymptotic bounds […]

7 February, 2009 at 10:45 am

Frankl-Rodl’s Theorem and Variations on the Cap Set Problem: A Recent Research Project with Roy Meshulam (A) « Combinatorics and more[…] upper bound for is more than . The gap is huge! What is the true value? Terry Tao wrote a lovely post on this problem. A set in without a 3-term arithmetic progression (or alternatively not […]

25 March, 2009 at 12:13 am

An Open Discussion and Polls: Around Roth’s Theorem « Combinatorics and more[…] closely related problem can be asked in . It is called the cap set problem. A subset of is called a cap set if it contains no arithmetic progression of size three or, […]

11 May, 2009 at 10:14 pm

Around the Cap-Set problem (B) « Combinatorics and more[…] with Roy Meshulam. (The first post is here. For information on the cap set problem itself look here. ) I will use here a different notation than in part A to make it compatible with various posts […]

17 May, 2009 at 10:05 pm

The Cap-Set Problem and Frankl-Rodl Theorem (C) « Combinatorics and more[…] that the maximum size of a cap set in is . Here is an obvious fact: The maximum size of a set in with the property that every […]

12 July, 2010 at 7:46 am

Hyper-optimistic conjecture retrospective – Part 1 « Paul Delhanty[…] problem, that is the maximal size of a subset of that does not contain an affine line, are by Terence Tao and Gil Kalai. Don’t worry that Tao uses the notation instead of . When k is a prime number […]

23 November, 2010 at 1:05 pm

Roth’s Theorem: Tom Sanders Reaches the Logarithmic Barrier | Combinatorics and more[…] me mention that a closely related problem can be asked in . It is called the cap set problem. A subset of is called a cap set if it contains no arithmetic progression of size three or, […]

11 January, 2011 at 7:11 am

What is difficult about the cap-set problem? « Gowers's Weblog[…] you Google “cap set problem” you will find other blog posts about it, including Terence Tao’s first (I think) blog post and various posts by Gil Kalai, of which this is a good introductory […]

9 February, 2011 at 9:00 am

Polymath6: thoughts on empirically testing the finite-field heuristic for very low ‘n’ « Paul Delhanty[…] instead of , it is known that AG(n,q) and PG(n,q) have the same aymptotic behaviour. So even if regarding AG(n,3) as of a Steiner system is too specific, it may be worth considering it in the context of design theory rather than as a […]

1 December, 2011 at 9:52 pm

Set is not the only version of Set « Quomodocumque[…] Terry Tao explains why this is one of his favorite open problems. […]

9 December, 2011 at 7:04 am

Cup Sets, Sunflowers, and Matrix Multiplication | Combinatorics and more[…] The cap set problem asks for the maximum number of elements in a subset of which contains no arithmetic progression […]

10 September, 2012 at 2:02 pm

Combinatorial problems related to matrix multiplication (guest post by Chris Umans) « Speedup in Computational Complexity[…] is true or false, but one thing that we do know is that it is a popular blog topic (see here, here, here, and the end of this […]

21 May, 2013 at 4:30 pm

Multiple recurrence and convergence results associated to $F_{p}^{omega}$-actions | What's new[…] (based on Behrend set constructions) do not seem to be present in the finite field setting (cf. this previous blog post on the cap set problem). In particular, we are able to largely settle the question of when one has […]

14 June, 2014 at 12:08 pm

Influence, Threshold, and Noise | Combinatorics and more[…] the cap set problem see e.g. here, here and here. There is some similarity between problem and techniques between additive […]