True complexity and iterated Cauchy--Schwarz

Abstract

We prove a polynomial bound in the "true complexity" problem of Gowers and Wolf. The proof uses only repeated applications of the Cauchy--Schwarz inequality, answering negatively a question posed by Gowers and Wolf. To choose and reason about the sequence of Cauchy--Schwarz steps needed, we need to introduce several layers of formalism and theory. The highest level of abstraction in this framework concerns building what we term "arithmetic circuits" encoding computations in multilinear algebra. It is plausible this machinery could be used to generate arithmetic inequalities in greater generality, and we state some conjectures along these lines.

arXiv comment103 pages

References in corpus (6)

• The true complexity of a system of linear equations
• Linear forms and higher-degree uniformity for functions on ${\mathbb{F}}_p^n$
• The Green-Tao theorem: an exposition
• Concatenation theorems for anti-Gowers-uniform functions and Host-Kra characteristic factors
• An inverse theorem for Freiman multi-homomorphisms
• On a conjecture of Gowers and Wolf