Extremal Obstructions to Gowers Uniformity - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T01:24:47Z http://mathoverflow.net/feeds/question/53280 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/53280/extremal-obstructions-to-gowers-uniformity Extremal Obstructions to Gowers Uniformity Steve Flammia 2011-01-25T21:15:27Z 2011-01-26T07:00:45Z <p>Recall the definition of the Gowers uniformity norm <code>$\|f\|_{U^{k}(G)}$</code>, <code>\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}</code> 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 <code>$G=\mathbb{Z}_d$</code> of integers modulo $d$, and $k=3$. Therefore, I'll just use the shorthand notation <code>$\|f\|_{U^{k}(\mathbb{Z}_d)} = \|f\|_{U^{k}}$</code>. </p> <p>I'm interested in functions <code>$f:\mathbb{Z}_d \to \mathbb{C}$</code> which have some fixed value of $\|f\|_2$, say 1, meaning that <code>\begin{align} \|f\|_2^2 = \sum_{h \in \mathbb{Z}_d} f(h) \overline{f(h)} = 1\,. \end{align}</code></p> <p>Then my question is,</p> <blockquote> <p>What are the functions having unit 2-norm which minimize $\|f\|_{U^3}$?</p> </blockquote> <p>I can prove a lower bound of <code>$\|f\|^8_{U^3} \ge \frac{2}{d^{4} (d+1)}$</code>, 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$. </p> <p>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.</p> http://mathoverflow.net/questions/53280/extremal-obstructions-to-gowers-uniformity/53328#53328 Answer by Thomas Bloom for Extremal Obstructions to Gowers Uniformity Thomas Bloom 2011-01-26T07:00:45Z 2011-01-26T07:00:45Z <p>I'm not quite sure where your lower bound comes from, but something close comes from functions such as</p> <p><code>$f(x)=e(x^3/d).$</code></p> <p>This (after rescaling by $d^{-1/2}$ to match your definition) has $L^2$ norm 1, and $U^3$ norm</p> <p><code>$\|f\|_{U^3}^8\leq\frac{2}{d^5}.$</code></p> <p>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.</p>