CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

The Cap Set Problem
Org: Dion Gijswijt (TU Delft)

HENRY COHN, Microsoft Research New England and MIT
On cap sets and the group-theoretic approach to matrix multiplication  [PDF]

In this talk, based on joint work with Jonah Blasiak, Thomas Church, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans, I'll describe the relationship between group-theoretic fast matrix multiplication algorithms and tricolored sum-free sets. In particular, I'll explain how to show that abelian groups of bounded exponent cannot prove that the exponent of matrix multiplication is 2, using the techniques of Croot, Lev, Pach, Ellenberg, and Gijswijt.

JORDAN S. ELLENBERG, University of Wisconsin
Sumsets as Unions of Sumsets of Subsets  [PDF]

I will talk about a modest generalization of the cap set bound which shows that sumsets $S+T$ in $F_p^n$ can be expressed “more efficiently” than one might expect; this uses the polynomial method combined with results of Meshulam on linear spaces of low-rank matrices, an interesting linear algebra problem in its own right. I’ll explain the short proof and speculate about other generalizations one might hope for in the near or long term.

A tight bound for Green's arithmetic triangle removal lemma  [PDF]

Green proved an arithmetic triangle removal lemma, which roughly says that for any three subsets of $\mathbb{F}_p^n$, if the number of triangles (triples summing to zero) between them is small, then we can delete a small number of elements and remove all triangles. Green posed the problem of improving the bounds, and asked whether a polynomial bound holds. Despite considerable attention, prior to our work, the best known bound, due to Fox, was tower type. We discuss our solution to Green's problem, proving a tight polynomial bound, using recent breakthroughs on the cap set problem.

Joint work with Jacob Fox.

ERIC NASLUND, Princeton University
The multi-slice rank method and exponential upper bounds for the Erd\"{o}s-Ginzburg-Ziv constant  [PDF]

In this talk, we introduce a more general notion of Tao's slice rank, which we call the multi-slice rank. We prove that the diagonal tensor has maximal multi-slice rank, and explain how this notion of rank gives us the additional flexibility needed to handle linear equations where each variable is required to be distinct. Using the multi-slice rank method, we give an exponential improvement to the upper bounds for the Erd\"{o}s-Ginzburg-Ziv constant of high rank abelian groups.

PÉTER P. PACH, Budapest University of Technology and Economics
Polynomials and progression-free sets  [PDF]

In this talk we will look at a new variant of the polynomial method which was first used to show that sets avoiding 3-term arithmetic progressions in groups like $\mathbb{Z}_4^n$ and $\mathbb{F}_q^n$ are exponentially small (compared to the size of the group). Since then many interesting applications of this method were shown.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology