Back to TGINF

Cap Sets and Rigid Matrices

Speaker: Ben
Title: Cap Sets and Rigid Matrices
Date: 29 Oct 2018 5:30pm-7:00pm
Location: Maxwell-Dworkin 123
Food: Indian

Abstract: A “cap set” is a subset of $(\mathbb{F}_3)^n$ that doesn’t contain any lines (no triples of distinct points $a, b, c$ such that $a + b + c = 0$). The cap set problem, one of the central open problems of additive combinatorics for decades, asks: how big can a cap-set be (in terms of $n$)? Specifically, are cap sets bounded above in size by $c^n$ for some $c<3$? In 2016, this question was answered in the affirmative by Ellenberg and Gijswijt, who extended an elegant version of the polynomial method devised by Croot, Lev, and Pach a few weeks earlier. I will illustrate the cap set problem in terms of the popular card game Set, prove the 2016 bound, and demonstrate an application of the proof’s key lemma to arithmetic circuit complexity—specifically, an upper bound on the rigidity of a large class of matrices (joint work with Zeev Dvir).