Jordan S. Ellenberg (University of Wisconsin-Madison)
Abstract: An arithmetic progression is an absolutely elementary object: a sequence of three numbers a,b,c such that the difference between c and b is the same as the difference between b and a. It might then be surprising to learn that the study of arithmetic progressions is actually an active research topic in pure and applied math, with much more unknown than known. Especially central seems to be the question: how large can a subset of the integers be if no three of its terms form an arithmetic progression? I will mostly talk about new results from spring 2016 about the “cap set problem,” otherwise known as “how many cards need to be on the table in an n-dimensional version of the card game Set before you can guarantee there’s a legal play?” (This is joint work with Dion Gijswijt.) If there’s time (or if people want to chat after!) I’ll also talk about some recent work in machine learning where sets with no arithmetic progressions provide a sharp bound on the error rate for the “triplet comparison” problem. (This is joint work with Lalit Jain.)
Relevant reading:
Terry Tao on the cap set problem, 2007
Some coverage on the new results, from Quanta magazine
Some info on triplet comparisons (from Project NEXT at the UW electrical engineering department)