## Extremal Obstructions to Gowers Uniformity

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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.

-

## 1 Answer

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

1
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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 17, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9328173398971558, "perplexity_flag": "head"}