A refinement of Cauchy-Schwarz complexity

Abstract

We introduce a notion of complexity for systems of linear forms, called 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$ that are denoted by ${\Phi }_{k,M}$ and can be viewed as $M$-dimensional arithmetic progressions of length $k$. For each $M\ge 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 concerning ergodic actions of ${\mathbb{F}}_p^{\omega }$.

arXiv comment17 pages. The main results in this paper were presented at the conference EUROCOMB 2021. Referee comments incorporated. To appear in European Journal of Combinatorics