Quadratic phase detection by the Gowers U2 norm
= Quadratic phase detection by the Gowers U2 norm
{c}
Let $|f|\leq1$ on $\mathbb Z_N$ and put $g(x)=f(x)\omega^{-x^2}$. If $\|g\|_{U^2}^4\geq c$, then the <Parseval identity> gives
$$
c\leq\sum_r|\widehat g(r)|^4
\leq\left(\max_r|\widehat g(r)|^2\right)\sum_r|\widehat g(r)|^2
\leq\max_r|\widehat g(r)|^2.
$$
Consequently $f$ correlates with a <quadratic phase>: for some $r\in\mathbb Z_N$,
$$
\left|\mathbb E_xf(x)\omega^{-rx-x^2}\right|\geq c^{1/2}.
$$