10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ unrelated... what interest do you - a physicist - have in Gowers norms? $\endgroup$ Jun 2, 2014 at 19:12

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jan 31, 2011 at 2:54
  • $\begingroup$ 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? $\endgroup$ Jan 31, 2011 at 9:35
  • 1
    $\begingroup$ 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? $\endgroup$ Jan 31, 2011 at 23:34
  • $\begingroup$ 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. $\endgroup$ Feb 1, 2011 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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