Freddie Manners

Iterated Cauchy-Schwarz arguments and true complexity

This talk is about useful facts that can be proved by repeated application of the Cauchy-Schwarz inequality. For example, it is standard that expressions $\sum_{x,y} f(x,y) a(x) b(y)$ are controlled by the matrix norm $\sum_{x,y,x',y'} f(x,y) f(x,y') f(x',y) f(x',y')$, and an elementary proof is by applying Cauchy-Schwarz twice. Similarly in additive combinatorics, counting three-term arithmetic progressions (x,x+y,x+2y) (i.e., averages $\sum_{x,y} f_1(x) f_2(x+y) f_3(x+2y)$) is controlled by the Gowers $U^2$-norm $\sum_{x,y,x',y'} f(x+y) f(x+y') f(x'+y) f(x'+y')$: generalizations of this are the starting point of Gowers' proof of Szemeredi's theorem.

However, seemingly simple 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 (and so by 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) and this can be proved just with Cauchy-Schwarz. A conjecture of Gowers and Wolf (resolved by the joint efforts of various authors) gives a condition to determine when a configuration is controlled by the $U^k$-norm, 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 Cauchy--Schwarz inequalities correspond (it turns out) to facts about functional equations. For example, the 3-term progression case states the following: if $f_1,f_2,f_3$ are functions such that $f_1(x)+f_2(x+h)+f_3(x+2h) = 0$ for all $x,h$, then each $f_i$ must be affine-linear. This statement is not completely obvious but has a short elementary proof.

Given such an elementary proof, sometimes we can reverse the process to find an iterated Cauchy-Schwarz proof of the corresponding inequality -- albeit a very long and complicated one that would be hard to discover by hand, and requiring a proof of a very specific type. 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.