Computer Science/Discrete Mathematics Seminar II

How dense can a set of integers be while containing no three-term arithmetic progressions? This is one of the classical problems of additive combinatorics, and since the theorem of Roth in 1953 that such a set must have zero density, there has been much quantitative progress in how quickly this density must decay.

In the first half of the seminar, I will give a survey of the quantitative progress on Roth's theorem on three-term arithmetic progressions, culminating in the recent work of myself and Olof Sisask, that in particular resolves the first non-trivial case of a famous conjecture of Erdős: if the sum of reciprocals diverges then A must contain three-term arithmetic progressions. I will give a high-level overview of the proof of this new result, which uses a blend of harmonic analysis and elementary combinatorial arguments.

In the second half of the seminar, I will discuss in depth one important component of our new proof: a structural result for additively non-smoothing sets. Roughly speaking, a set is additively non-smoothing when it grows under addition once, but further addition reveals no extra structure. The first structural result for such sets was proved by Bateman and Katz in their work on the cap set problem. An important part of my work with Olof Sisask was to prove a structural result of this kind for arbitrary groups (in particular for subsets of the integers). In this talk I will sketch our proof of this structural result, which uses only elementary methods, and which should have many further applications in other problems of additive combinatorics.