Freddie Manners (UCSD): Iterated Cauchy--Schwarz arguments and true complexity

A key tool in modern additive combinatorics, going back to Gowers' proof of Szemeredi's theorem, is that counts of linear configurations are controlled by Gowers norms. For example, if S and T are two dense sets and $\|S-T\|_{U^{k-1}}$ is small then S and T have roughly the same number of k-term arithmetic progressions. Like many other core arguments in the field, this is proven by (k-1) applications of the Cauchy--Schwarz inequality.

Generalizations of this statement quickly become subtle. For example, linear configurations (x, x+z, x+y, x+y+z, x+2y+3z, 2x+3y+6z) are controlled by the U^2-norm (i.e., by normal Fourier analysis) but it is not at all straightforward to prove this just with Cauchy--Schwarz; whereas controlling (x, x+z, x+y, x+y+z, x+2y+3z, 13x+12y+9z) requires the U^3-norm (i.e., quadratic Fourier analysis). A conjecture of Gowers and Wolf (resolved combining work of Gowers--Wolf, Green--Tao, Hatami--Hatami--Lovett and Altman) gives a condition to determine the smallest U^k-norm required for a given configuration, but the proofs require deep structure theorems and (unlike Cauchy--Schwarz arguments) give very weak bounds.

In this talk, I will describe how it is (sometimes) possible to find the missing Cauchy--Schwarz arguments by "mining proofs". The equality cases of these inequalities correspond (it turns out) to facts about functional equations. For example, the k-term progression case states the following: if f_1,...,f_k are functions such that f_1(x)+f_2(x+h)+...+f_k(x+(k-1) h) = 0 for all x,h, then each f_i must be a polynomial of degree at most k-2. This statement is not completely obvious but has a short elementary proof.

Given such an elementary proof (at least, one of a special type), we can recover an iterated Cauchy--Schwarz proof of the corresponding inequality -- albeit a very long and complicated one that would be hard to discover by hand. This answers the Gowers--Wolf question with polynomial bounds, and hopefully other questions where the availability of complicated Cauchy--Schwarz arguments is a limiting factor.