Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem!

A quote from a recent post from Jordan Ellenberg‘s blog Quomodocumque:

Briefly:  it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday (GK: see also my last post) can indeed be used to give a new bound on the size of subsets of F_3^n with no three-term arithmetic progression! Such a set has size at most (2.756)^n. (There’s actually a closed form for the constant, I think, but I haven’t written it down yet.)

Here’s the preprint. It’s very short. I’ll post this to the arXiv in a day or two, assuming I (or you) don’t find anything wrong with it, so comment if you have comments!

This 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 this direction. (Fortunately for our profession, success for two conflicting statements was avoided.) Congratulations to Jordan, Ernie, Seva, and Peter!

Update: Congratulations also to Dion Gijswijt who also derived a similar solution to the cap set problem based on CLP! See this comment on Quomodocumque.


Updates: See also this post by Tao (presenting a symmetric version of the proof), this post by Gowers, this post in by Luca Trevisan, and this post by Peter Cameron, and this post by Anurag Bishnoi. See also this lovely quanta article  Set proof stuns mathematicians by Erica Klarreich. See also the post Polynomial prestidigitation on GLL. There, among other things the relation to Smolensky’s early use of the “halving degree trick” for the polynomial method is noted. (See also this comment.)

Of course, there is also plenty of more to desire: Full affine lines for q>3, higher dimensional affine subspaces for q\ge3, some application to better bounds for Roth’s theorem, Szemeredi’s theorem, (for more, see this comment by Terry Tao,)… It is all very exciting.

Noga Alon also pointed out that the solution of the cap set problem also settles affirmatively the Erdos-Szemeredi weaker version of the Erdos-Rado Delta-system conjecture (via the connections discussed in this post) and also shows that a certain direction for showing that ω=2 for matrix multiplication cannot possibly work. The Erdos-Rado sunflower conjecture is still (at least for a few days) open.

Can the affine results be applied for integers or for combinatorial setting? The geometries are quite different but still… This is of great interest here (and also for other problems like the Kakeya problem). Starting from a positive density set in Z_3^n considered as a subset of Z_{3^{100}}^m we can find there a 10^{100}-dimensional affine subspace contained in the set. Can’t we use it (or such a subspace with a few additional pleasant properties) to get just a single combinatorial line over Z_3, or, easier, just a 3-term arithmetic progression when A represent a subset of {1,2,… , 3^n }?  A bit later: These thoughts about the relevance of finite field results to questions for the integers (or reals) are not really relevant to the new discovery.  But what seems to be relevant is the possibility to transfer the new method for the cap set problem back to the question on better lower bounds for Roth’s theorem.

More updates: Eric Naslund and Will Sawin gave a direct proof based on the polynomial method for the Erdos-Szemeredi sunflower conjecture, and an even  stronger result is given by Naslund here. (Eric also has stronger quantitative bounds for Erdos-Szemeredi based on bounds for cap sets.)   Ben Green has studied the analogue of Sarkozy’s theorem in function fields (other results on function fields are mentioned by Bloom in this comment);  Variants on the CLPEG-arguments are described by Petrov and by Bishnoi over the comment threads here and here.  Here is a paper by Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans, on consequences of the cap set result for fast matrix multiplication.

More updates (May 31): New applications are mentioned in a new post on quomodocumque: sumsets and sumsets of subsets including a lovely new application by Jordan, a link to a paper  by Robert Kleinberg: A nearly tight upper bound on tri-colored sum-free sets in characteristic 2. And here is a link to a new manuscript by Fedor Petrov Many Zero Divisors in a Group Ring Imply Bounds on Progression–Free Subsets.

One more: (Quoting Arnab Bhattacharyya, June 15 2016 on GLL) Another amazing result that follows from these techniques for one of my favorite problems: http://arxiv.org/pdf/1606.01230v2.pdf. Fox and LM Lovasz improve the bounds for the arithmetic triangle removal lemma dramatically, from a tower of two’s to polynomial!

More (Early July 2016) : An interesting new post on Ellenberg’s blog.



This entry was posted in Combinatorics, Open problems, Updates and tagged , , , , , . Bookmark the permalink.

19 Responses to Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem!

  1. I just want to recall that the weak sunflower conjecture is implied by a good bound on $R_r(k)$ as well as we discussed in [1]. So instead of the strong sunflower conjecture this is a second problem that one might want to think about in this context.

    [1] https://gilkalai.wordpress.com/2016/01/31/polymath10-post-4-back-to-the-drawing-board/

  2. Perhaps it should be noted that the upper bounds obtained by both Jordan and Dion are the same. They both prove that the size of a 3-term progression free set in F_q^n is bounded above by the total number of monomials of degree at most (q – 1)n/3 in which each variable has degree at most q – 1, i.e., the number of integral solutions of, e_1 + e_2 + … + e_n <= (q – 1)n/3, 0 <= e_i <= q – 1. Since we know this now, may be we can find alternate ways of proving their result, which could shed some more light on other related problems.

    • Gil Kalai says:

      Dear Anurag, Finding alternative proofs to other applications of the polynomial method is very often not known and always quite tricky. What I am most curious about is if “the total number of monomials of degree at most (q – 1)n/3 in which each variable has degree at most q – 1,” (a) does not hide some unpleasant constants depending on q, and (b) suffices to derive a Behrend-type upper bound for Roth numbers r_3(q).

      (Namely: to (strangely) deduce a Behrend type bound for n=1 from the assymptotic result as n \to \infty.)

      Added later: Apparently, as the experts expected, the new bounds have no baring on r_3(p).

    • Gil Kalai says:

      Let me mention that one important case where an alternative method is known is the Frankl Rodl theorem (extending the Frankl-Wilson theorem which uses the polynomial method but via a different technique). At some earlier posts we related these results to some weaker versions of the cap set problem.

    • Gil Kalai says:

      There is one case of the polynomial method, namely that of the Frankl Wilson theorem where an alternative proof (with less optimal but qualitativly similar bounds) was found by Frankl and Rodl. Moreover the Frankl-Rodl bound applies in much greater generality. In some posts here in 2009 I described and discussed (part I, part II, part III) an idea to use the polynomial method for a weak version of the cap set problem and at that time applying the very general form of Frankl-Rodl (for which no proof via the polynomial methods are known) gave the best results.

  3. Seva Lev says:

    Concerning full affine lines for $q>3$: is anything at all known on it?

  4. Pingback: Polymath 10 Emergency Post 5: The Erdos-Szemeredi Sunflower Conjecture is Now Proven. | Combinatorics and more

  5. Pingback: The new bound on cap sets | Anurag's Math Blog

  6. Pingback: Polymath 10 post 6: The Erdos-Rado sunflower conjecture, and the Turan (4,3) problem: homological approaches. | Combinatorics and more

  7. I have been reading up on Davenport constants and related things recently, and it seems like the link between cap sets and the so-called Erdos-Ginzburg-Ziv constant has not been mentioned in any of the blog posts. Of course, many people might know about this already. Still, here it is. For an abelian group G, let s(G) be the smallest integer m for which every sequence of length m of elements of G contains a subsequence of length exp(G) which sums up to zero. For the case when G = \mathbb{Z}_3^n, and thus exp(G) = 3, we have that the maximal size of a cap is equal to (s(G) - 1)/2, and thus we get an upper bound on s(\mathbb{Z}_3^n). See this paper: http://imsc.uni-graz.at/geroldinger/56-zero-sum-caps.pdf, or Section 12 of this paper: https://www.mathi.uni-heidelberg.de/~yves/Papers/CapSurvey.pdf.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s