Freddie Manners


Iterated Cauchy-Schwarz arguments and true complexity

Combinatorics Seminar

22nd February 2022, 5:00 pm – 6:00 pm
Virtual (online) Zoom seminar; a link will be sent to the Bristol Combinatorics Seminar mailing list, the week before the seminar.

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.

Organisers: David Ellis, Tom Johnston

Comments are closed.