Penn Arts & Sciences Logo

Penn Mathematics Colloquium

Wednesday, April 10, 2019 - 3:30pm

Jordan Ellenberg

Univ. Wisconsin

Location

University of Pennsylvania

DRL A2

Tea at 3:00 in DRL 4E17

The “cap set” problem asks the following question.  Let S be a subset of an n-dimensional vector space over the field of three elements such that no three distinct elements of S are collinear.  How big can S be? 
 
This is related to classical number theory questions about sets of integers with few arithmetic progressions, and to the popular card game Set.  Progress on this popular problem was stalled for a long time until 2016, when a much-improved upper bound was obtained by me and Dion Giswijt, relying crucially on a new form of the polynomial method due to Croot, Lev, and Pach. 
 
I’ll explain how this works (the proof is very short!), explain a beautiful and currently very influential idea of Terry Tao about what this has to do with new notions of “rank” for 3-dimensional nxnxn “matrices,” and if time permits say a bit about why this all might be of interest for data science.  In particular, here is a puzzle that recently came up in a problem in computer science: let S be a subset of an NxN grid containing no isosceles triangle.  How large can S be?  I will explain why I care about this and implore the audience to tell me something about the answer might be.