The Polynomial Method and the Cap SET Problem

Thursday, October 26, 2017 - 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Pritish Kamath

Affiliation

CSAIL

Abstract

If you have played the popular card game, SET, you have probably wondered about what is the largest number of cards that one could have that does not contain a SET. This number was shown to be 20 in the classic game of SET. But one could ask the same question when there are more attributes per card.

 

More formally, the question is as follows: Let C_m denote the cyclic group Z/mZ. What is the largest subset of (C_m)^n having no three distinct elements in arithmetic progression? Before May 2016, the best known upper bounds were barely better than the trivial upper bound of m^n, even for the case of m=3, when the question is known as the "Cap Set" problem. The breakthrough work (from last year) by Croot-Lev-Pach, and follow up works of Ellenberg and Gijswijt have shown an upper bound of (0.95 m)^n for all m >= 3. The proof is unbelievably simple and short!

 

The main technique used in the proof is the polynomial method. In this talk, I will describe the polynomial method, give some intuition about why it was challenging to use the polynomial method for this problem, and also give the entire proof.

 

References:

SET game (Wikipedia): https://en.wikipedia.org/wiki/Set_%28game%29

Quanta magazine article about the breakthrough: https://www.quantamagazine.org/20160531-set-proof-stuns-mathematicians/

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

Croot-Lev-Pach: https://arxiv.org/abs/1605.01506

Ellenberg-Gijswijt: https://arxiv.org/abs/1605.09223

Biography