Gowers uniformity norm ($U^k$ norm)

The Gowers uniformity norm measures the average multiplicative derivative of a function around affine cubes. The $U^k$ norm detects polynomial phases of degree below $k$.

A product that cancels constant phases and lowers the degree of a polynomial phase. For $f(x)=e(\alpha x^2)$, it is $e(2\alpha hx+\alpha h^2)$. Some conventions conjugate the entire expression and reverse the frequency signs. The Gowers uniformity norm derivative identity relates a higher norm to the average of lower norms of these derivatives.

For a function on a finite abelian group,

Let $|f|\le 1$ on ${\mathbb{Z}}_N$ and put $g(x)=f(x){\omega }^{-x^2}$. If $\Vert g{\Vert }_{U^2}^4\ge c$, then the Parseval identity givesConsequently $f$ correlates with a quadratic phase: for some $r\in {\mathbb{Z}}_N$,

The third Gowers norm is the eighth root of the conjugated product around a three-dimensional affine cube:

A subset $A$ of a finite abelian group $G$ with subset density $\eta =|A|/|G|$ is quadratically $\alpha$-uniform, in the norm convention, if its balanced subset indicator $g=1_A-\eta$ has Gowers U3 norm at most $\alpha$. This controls correlations on additive three-dimensional cubes after the subset density contribution is removed. If a convention instead bounds the eighth power of the norm by $\alpha$, its parameter corresponds to the norm parameter ${\alpha }^{1/8}$. The convention must therefore be stated when giving quantitative thresholds.

Balance the indicator by its density on the interval, and extend it by zero to a cyclic group of order greater than twelve times the interval length and coprime to six. An eighth-power interval cube bound $\alpha$ bounds every four-term counting error by ${\alpha }^{1/8}$ through three Cauchy–Schwarz steps. The density contribution is bounded below by a constant times ${\delta }^4$, and the diagonal contribution tends to zero with interval length. A sufficiently small constant times ${\delta }^{32}$ therefore guarantees a nonconstant four-term progression. Stating the cube normalization distinguishes this parameter from the norm convention.

For $A\subseteq {\mathbb{Z}}_N$, $N\ge 16$, put $\eta =|A|/N$, $M=\lfloor N/16\rfloor$, $J=\{0,\dots ,M-1\}$, and $w=1_J\ast 1_J$ using normalized convolution on a finite group. The weights $w(x)w(d-M)$ are supported where $0\le x\le 2M-2$ and $M\le d\le 3M-2$, so $x,x+d,x+2d,x+3d$ are distinct integer points below $N$. If $t=M/N$, then $\mathbb{E}w=t^2$ and the sum of absolute values of its Fourier coefficients is $t$, by Parseval identity on a finite group. Expanding the four indicators around their subset density leaves four terms with one balanced factor. Expand both weights in Fourier series and absorb each character $e(rx+sd)$ into the factors at $x$ and $x+d$. Character multiplication preserves the Gowers U3 norm, and the cyclic four-term progression bound with torsion factors bounds every error by $6^{1/8}\alpha$. Thus the weighted count is at least ${\eta }^4{t}^4-4\cdot 6^{1/8}\alpha t^2$. Since $t\ge 1/32$, positivity follows from $\alpha <{\eta }^4/(4096\cdot 6^{1/8})$.

For functions bounded by one on a cyclic group of prime order greater than three, three applications of Cauchy-Schwarz bound the four-term arithmetic progression average by the smallest Gowers U3 norm of its factors. Zero extension yields the corresponding interval bound with an absolute factor. This makes Gowers U3 norm a measure of uniformity relevant to four-term arithmetic progression counts.

For a finite abelian group $G$, put $t_j=|\{x\in G:jx=0\}|$. If $|f_i|\le 1$, then $|{\mathbb{E}}_{x,d}{\prod }_{i=0}^3{f}_i(x+id)|\le (t_2{t}_3{)}^{1/8}{\min }_i\Vert f_i{\Vert }_{U^3}$. Three applications of Cauchy-Schwarz, eliminating the factors at slopes $3,2,1$, bound the eighth power by ${\mathbb{E}}_{h,k}|{\mathbb{E}}_x{\Delta }_{-3h}{\Delta }_{-2k}{f}_0(x){|}^2$, where ${\Delta }_{h}f(x)=f(x)\overline{f(x+h)}$. The integrand is nonnegative; averaging over $3G$ and $2G$ costs at most their indices $t_3$ and $t_2$ compared with the unrestricted average defining $\Vert f_0{\Vert }_{U^3}^8$. Reversal treats slope three. For slope one, elimination at slopes $3,0,2$ produces increments $-2h,k,-r$, costing only $t_2$; reversal treats slope two. In a cyclic group, $t_2\le 2,t_3\le 3$, so the constant is at most $6^{1/8}$ independently of group size.

A bound tending to zero with one factor's Gowers U3 norm, uniformly over all finite abelian groups, is false. On $G={\mathbb{F}}_2^m$, choose a random independent sign at each point. A cube with eight distinct vertices has sign product of expectation zero. The probability of a collision among its vertices is at most $\left(\genfrac{}{}{0ex}{}{8}{2}\right)/|G|$, since each equality of distinct vertices imposes a nonzero linear equation in the increments. Thus some sign function $f$ has $\Vert f{\Vert }_{U^3}^8\le 28/|G|$. But the four-term arithmetic progression is $(x,x+d,x,x+d)$, so choosing factors $(f,1,f,1)$ gives correlation identically one. As $m\to \infty$, the norm tends to zero. Bounded torsion, as in cyclic groups, avoids this obstruction.

Normalize the conjugated cube average by the number of integer cubes whose vertices all lie in the interval. Equivalently, extend $f$ by zero to a cyclic group of order greater than $8N$ and divide its Gowers U3 norm by that of the interval's indicator function. A quadratic phase then has norm one. Omitting the denominator gives a different but uniformly equivalent interval normalization.

For the multiplicative derivative ${\partial }_{a}f(x)=f(x+a)\overline{f(x)}$,

For functions indexed by $ϵ\in \{0,1{\}}^k$, the Gowers inner product iswhere $\mathcal{C}$ denotes complex conjugation.

Repeated Cauchy-Schwarz inequality gives

A quadratic phase on ${\mathbb{F}}_p^n$ is a function $x\mapsto e_p(q(x))$, where $q$ is a quadratic form and $e_p(t)=e^{2\pi it/p}$. Its third multiplicative derivative is one, so its $U^3$ norm is one.

For fixed prime $p$, a one-bounded function on ${\mathbb{F}}_p^n$ with $U^3$ norm at least $\delta$ has correlation bounded below in terms of $p$ and $\delta$ with a quadratic phase, with the usual nonclassical formulation in small characteristic.

If $\Vert f{\Vert }_{U^3}^8\ge c$ and $\Vert f{\Vert }_{\infty }\le 1$, select for many $a$ a frequency $\varphi (a)$ at which $\widehat{{\partial }_{a}f}$ is large. A box-norm inequality shows that the graph $\{(a,\varphi (a))\}$ has at least $(c/2{)}^8|G{|}^3$ additive quadruples. Additive-combinatorial structure in this graph is the first step toward recovering a quadratic phase.

If a dense set has too few four-term arithmetic progressions, its balanced function has large $U^3$ norm. A Frequency graph extracted from a large Gowers U3 norm, followed by the Balog-Szemerédi-Gowers theorem and a Freiman theorem, yields correlation with a quadratic phase. Restricting to a suitable level set gives a density increment, and iteration proves the Finite-field Szemerédi theorem for four-term arithmetic progressions.