skip to main content
Caltech
Fires burning in Greater Los Angeles area have had significant impact on the Caltech's community and surrounding areas. For information and resources for members of the Caltech community, go to https://www.caltech.edu/fire.

Caltech/UCLA/USC Joint Analysis Seminar

Tuesday, February 1, 2022
3:30pm to 4:30pm
Add to Cal
Online and In-Person Event
Iterated Cauchy--Schwarz arguments and true complexity
Frederick Manners, Department of Mathematics, UC San Diego,

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.

For more information, please contact Math Department by phone at 626-395-4335 or by email at mathinfo@caltech.edu.