Extremal Obstructions to Gowers Uniformity

2011-01-25T21:15:27Z

Recall the definition of the Gowers uniformity norm $\|f\|_{U^{k}(G)}$ , \begin{align} \|f\|_{U^{k}(G)} := \left( \mathbb{E}_{x,h_1,\ldots,h_k \in G} \Delta_{h_1} \ldots \Delta_{h_{k}} f(x) \right)^{2^{-k}} \, \end{align} where the operator $\Delta_h$ is a multiplicative analog of a derivative given by \begin{align} \Delta_h f(x) := f(x+h) \overline{f(x)} \,, \end{align} and $G$ is a finite abelian group. I'm specifically interested in the case $G=\mathbb{Z}_d$ of integers modulo $d$, and $k=3$. Therefore, I'll just use the shorthand notation $\|f\|_{U^{k}(\mathbb{Z}_d)} = \|f\|_{U^{k}}$ .

I'm interested in functions $f:\mathbb{Z}_d \to \mathbb{C}$ which have some fixed value of $\|f\|_2$, say 1, meaning that \begin{align} \|f\|_2^2 = \sum_{h \in \mathbb{Z}_d} f(h) \overline{f(h)} = 1\,. \end{align}

Then my question is,

What are the functions having unit 2-norm which minimize $\|f\|_{U^3}$?

I can prove a lower bound of $\|f\|^8_{U^3} \ge \frac{2}{d^{4} (d+1)}$ , so such functions cannot have arbitrarily small Gowers norm. This bound seems to be tight for all values of $d$ (via numerics) but there is no obvious function which provably saturates the bound for all $d$.

From what I can tell, it appears that such obstructions to Gowers uniformity, like the 2-norm constraint above, have been studied before. But I cannot tell if such extremal problems have been studied, or even if they are thought to be tractable.

Answer by Thomas Bloom for Extremal Obstructions to Gowers Uniformity

2011-01-26T07:00:45Z

I'm not quite sure where your lower bound comes from, but something close comes from functions such as

\[f(x)=e(x^3/d).\]

This (after rescaling by $d^{-1/2}$ to match your definition) has $L^2$ norm 1, and $U^3$ norm

\[\|f\|_{U^3}^8\leq\frac{2}{d^5}.\]

In general, these `phase functions' of degree $n$ will give functions with small $U^n$ norm (because 'differentiating' such a phase function $n-1$ times gives a sum over linear phase functions and hence a lot of a cancellation), and I suspect the extremal example will be of this sort.

Extremal Obstructions to Gowers Uniformity - MathOverflow

Extremal Obstructions to Gowers Uniformity

Answer by Thomas Bloom for Extremal Obstructions to Gowers Uniformity