Gowers norm

Remarks

The sum on the right is a nonnegative real number, so the root is defined. For $k \ge 2$ the map $f \mapsto \norm{f}_{U^k}$ is a norm on the space of functions $G \to \C$. For $k = 2$, with the Fourier transform $\hat f(\chi) = \abs{G}^{-1} \sum_x f(x) \overline{\chi(x)}$, one has $\norm{f}_{U^2}^4 = \sum_\chi \abs{\hat f(\chi)}^4$. For a character $\chi$ of $G$, each product $\chi(x) \overline{\chi(x + h_1)} \, \overline{\chi(x + h_2)} \, \chi(x + h_1 + h_2)$ equals $1$, so $\norm{\chi}_{U^2} = 1$. For $k = 1$ the formula gives $\norm{f}_{U^1} = \abs{\abs{G}^{-1} \sum_x f(x)}$, which is only a seminorm. A nontrivial character $\chi$ has $\norm{\chi}_{U^1} = 0$ but $\chi \ne 0$, so $U^1$ fails positive definiteness. The norms increase with $k$: $\norm{f}_{U^k} \le \norm{f}_{U^{k+1}}$.