A big conjecture in combinatorics that unexpectedly got proved last week and what this has to do with matrix multiplication

There’s a popular folk question about the card game Set: how many cards can you have on the table before there’s necessarily a legal play? The answer, which is pretty tricky to work out, and which is larger than most people expect, is 20. This is one case of a famous old problem in combinatorics, the “cap set problem”: If S is a subset of (Z/3Z)^n, which has no three elements summing to 0, how large can S be? About 15 years ago it was proved by Meshulam that the size of such a set is O(3^n/n). A few years ago that was slightly improved to O(3^n / n^{1+eps}). Then suddenly last week, by a combination of work by Ernie Coot, Vsevolod Lev, Peter Pach, Dion Gijswijt, and me, that upper bound suddenly shrunk to O(2.756^n). The paper is 2 pages long and explaining the whole proof would not be enough material for a whole talk! This is another startling success of “the polynomial method,” which, starting with the 2008 theorem of Ze’ev Dvir (who just spoke here at Applied Algebra Days) has had an amazing run of providing short proofs of old problems that were thought to be hard.

I will explain how this theorem is proved, state the implications for matrix multiplication (which I haven’t understood yet but might by Thursday), philosophize about simultaneous low rank and sparsity, and talk about some related problems I think might be ripe for solution now.

My blog post:
https://quomodocumque.wordpress.com/2016/05/13/bounds-for-cap-sets/

Terry’s blog post:
https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg-gijswijt-capset-bound/

The paper relating all this to matrix multiplication:
http://math.stanford.edu/~church/BCCGU-On-cap-sets-and-the-group-theoretic-approach-to-matrix-multiplication.pdf