## Extremal Obstructions to Gowers Uniformity

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.

-

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.

-
Thanks Thomas! I guess this upper bound only works in prime dimensions, though, right? Unfortunately, these functions don't look anything like the ones which are actual extreme points, so I don't see how to get there from here. The ones which minimize don't ever seem to have a constant absolute value like the phase function you've proposed. It's maddeningly close to the lower bound, though. – Steve Flammia Jan 31 2011 at 2:54
Yes, sorry; I think you do need $d$ prime here. Could you give examples of functions you've found with extreme points? e.g. could they be constructed from such phase functions with sums and/or dilates? – Thomas Bloom Jan 31 2011 at 9:35
Since the solutions are numerical, they don't really have a useful form. An analytic solution for d=2 is: $f(0)=\sqrt{3+\sqrt{3}}$ , and $f(1) = \sqrt{3-\sqrt{3}} e(1/8)$. I can email you a few other examples for larger d if you want. I haven't checked if they can be formed from sums over polynomial phase functions, because I don't know how to check this when the phase functions are nonlinear. Is there a way to get a "nonlinear Fourier decomposition" of a function? – Steve Flammia Jan 31 2011 at 23:34
I'd be interested in seeing your results; my email is on my webpage on my profile, thanks. I don't think there's a canonical way to decompose a function into nonlinear phase functions like the Fourier transform, since they no longer form a canonical basis of the dual space. – Thomas Bloom Feb 1 2011 at 9:58