The Complexity of Multilinear Averages

A central question in additive combinatorics is to determine what class of structured functions is enough to determine multilinear averages such as

$\mathbb{E}_{x,a} f_1(x) f_2(x+a) f_3(x+2a) f_4(x+3a)$.

In ergodic theory the analogous question is to determine the correct characteristic factor. Determining the exact structure is hard, but a weaker question is to ask whether two systems have the same class of structured functions / characteristic factor. An example is the "true complexity" problem of Gowers and Wolf. Sometimes these questions have elementary solutions, e.g. by repeated application of the Cauchy--Schwarz inequality; at other times, such proofs are not known.

We will discuss this phenomenon, and in particular describe a method for obtaining "elementary" proofs that are too complicated to describe by hand.