Dion Gijswijt (TU Delft)

Cap sets and new applications of the polynomial method

In a beautiful paper (March 2002 issue of ‘Het Nieuw Archief voor Wiskunde’), N.G. de Bruijn explains that the popular card game SET is actually finite geometry in disguise. The cards correspond to points in a four-dimensional space over a field of three elements and the ‘SETs’ are lines in this space. Geometrically, the players are looking for lines contained in subsets of points.

A collections of cards (more generally: a subset of \(GF(p)^n\)) with no three point of a line is called a ‘cap’ or ‘cap set’. Studying the size and structure of caps is one of the main problems in finite geometry. The ‘cap set problem’ is concerned with the maximum size of cap sets as the dimension of the space increases. The central question (raised by Frankl, Graham and Rödl in 1986) is: “Do cap sets have exponentially small density?”

In 2016, the ‘cap set problem’ was (very unexpectedly) resolved using the polynomial method. The proof is surprisingly short and simple. In this talk, I will explain the main ideas of the proof and discuss generalisations and connections to closely related problems such as ‘fast matrix multiplication’.