A Refinement of Cauchy-Schwarz Complexity, with Applications

Pablo Candela
Diego González-Sánchez
Balázs Szegedy
24 August 2021

We introduce a notion of complexity for systems of linear forms called \emph{sequential Cauchy-Schwarz complexity}, which is parametrized by two positive integers $k,\ell$ and refines the notion of Cauchy-Schwarz complexity introduced by Green and Tao. We prove that if a system of linear forms has sequential Cauchy-Schwarz complexity at most $(k,\ell)$ then any average of 1-bounded functions over this system is controlled by the $2^{1-\ell}$-th power of the Gowers $U^{k+1}$-norms of the functions. For $\ell=1$ this agrees with Cauchy-Schwarz complexity, but for $\ell>1$ there are systems that have sequential Cauchy-Schwarz complexity at most $(k,\ell)$ whereas their Cauchy-Schwarz complexity is greater than $k$. Our main application illustrates this with systems over a prime field $\mathbb{F}p$, denoted by $\Phi{k,M}$, which can be viewed as $M$-dimensional arithmetic progressions of length $k$. For each $M\geq 2$ we prove that $\Phi_{k,M}$ has sequential Cauchy-Schwarz complexity at most $(k-2,|\Phi_{k,M}|)$ (where $|\Phi_{k,M}|$ is the number of forms in the system), whereas the Cauchy-Schwarz complexity of $\Phi_{k,M}$ can be greater than $k-2$. Thus we obtain polynomial true-complexity bounds for $\Phi_{k,M}$ with exponent $2^{-|\Phi_{k,M}|}$. A recent general theorem of Manners, proved independently with different methods, implies a similar application but with different polynomial true-complexity bounds, as explained in the paper. In separate work, we use our application to give a new proof of the inverse theorem for Gowers norms on $\mathbb{F}_p^n$, and related results on ergodic actions of $\mathbb{F}_p^{\omega}$.