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|Uk-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 U2-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 U3-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 Uk-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 f1,…,fk are functions such that f1(x)+f2(x+h)+…+fk(x+(k-1)h) = 0 for all x,h, then each fi 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.
This video is part of the Webinar in Additive Combinatorics series, and this is their YouTube channel.
