Earlier this month, in the previous incarnation of this page, I posed a question which I thought was unsolved, and obtained the answer (in fact, it was solved 25 years ago) within a week. Now that this new version of the page has better feedback capability, I am now tempted to try again, since I have a large number of such questions which I would like to publicise. (Actually, I even have a secret web page full of these somewhere near my home page, though it will take a non-trivial amount of effort to find it!)

Perhaps my favourite open question is the problem on the maximal size of a *cap set* – a subset of ( being the finite field of three elements) which contains no lines, or equivalently no non-trivial arithmetic progressions of length three. As an upper bound, one can easily modify the proof of Roth’s theorem to show that cap sets must have size (see e.g. this paper of Meshulam). This of course is better than the trivial bound of once n is large. In the converse direction, the trivial example shows that cap sets can be as large as ; the current world record is , held by Edel. The gap between these two bounds is rather enormous; I would be very interested in either an improvement of the upper bound to , or an improvement of the lower bound to . (I believe both improvements are true, though a good friend of mine disagrees about the improvement to the lower bound.)

One reason why I find this question important is that it serves as an excellent model for the analogous question of finding large sets without progressions of length three in the interval . Here, the best upper bound of is due to Bourgain (he also has a recent, not yet published, improvement to , while the best lower bound of is an ancient result of Behrend. Using the finite field heuristic that “behaves like” , we see that the Bourgain bound should be improvable to , whereas the Edel bound should be improvable to something like . However, neither argument extends easily to the other setting. Note that a (still open) conjecture of Erdős-Turán is essentially equivalent (for progressions of length three, up to log log factors) to the problem of improving the Bourgain bound to .

The Roth bound of appears to be the natural limit of the purely Fourier-analytic approach of Roth, and so any breakthrough would be extremely interesting, as it almost certainly would need a radically new idea. The lower bound might be improvable by some sort of algebraic geometry construction, though it is not clear at all how to achieve this.

(Update, Feb 25: After some feedback and advice, and moving the entire blog to another site, I have finally gotten the math formulae to work out nicely. Thanks for all the help!)

(*Update*, Feb 27: As pointed out in the comments, one can interpret this problem in terms of the wonderful game Set, in which case the problem is to find the largest number of cards one can put on the table for which nobody has a valid move. As far as I know, the best bounds on the cap set problem in small dimensions are the ones cited in the __Edel paper mentioned above__.)

(*Update*, Mar 5: After discussions with Jordan Ellenberg, we realised that there is a variant formulation of the problem which may be a little bit more tractable. Given any , the fewest number of lines in a set of of density at least is known to be for some ; this is essentially a result of Croot. The reformulated question is then to get as strong a bound on ) as one can. For instance, the counterexample shows that , while the Roth-Meshulam argument gives .)

## 30 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 […]

13 May, 2016 at 2:52 pm

Terence TaoSo, the solution to this problem actually took nine years, rather than a week, but anyway: Jordan Ellenberg has just shown that capsets are asymptotically bounded in size by .

15 May, 2016 at 5:20 am

Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem! | Combinatorics and more[…] is amazing! The cap set problem was quite popular here on the blog, see also Tao’s 2007 post, and Jordan made also quite an effort over the years in proving the other direction before proving […]

16 May, 2016 at 2:00 pm

kodluI found your response to Greg Kuperberg illuminating. Also, the counterexample in the last paragraph of the post may have a typo; shouldn’t it be $\{0,1\}^m \times F_3^n$?

[Corrected, thanks – T.]17 May, 2016 at 2:50 pm

The new bound on cap sets | Anurag's Math Blog[…] problem in combinatorics that survived even after a lot of effort from several mathematicians (see this, this, this and this). Ultimately, just like the finite field Kakeya problem, it succumbed to the […]

18 May, 2016 at 12:13 am

A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound | What's new[…] that does not contain any lines. A basic problem in additive combinatorics (discussed in one of the very first posts on this blog) is to obtain good upper and lower bounds for the maximal size of a capset in […]