Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Recall the definition of the Gowers uniformity norm $\|f\|_{U^{k}(G)}$, $$ \|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}} \, $$ where the operator $\Delta_h$ is a multiplicative analog of a derivative given by $$ \Delta_h f(x) := f(x+h) \overline{f(x)} \,, $$ 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 $$ \|f\|_2^2 = \sum_{h \in \mathbb{Z}_d} f(h) \overline{f(h)} = 1\,. $$

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.

share|improve this question
unrelated... what interest do you - a physicist - have in Gowers norms? –  john mangual Jun 2 at 19:12

1 Answer 1

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.

share|improve this answer
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 '11 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 '11 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 '11 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 '11 at 9:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.