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

This was a problem that came up during a course on Analytic Combinatorics that I had taken this semester. Here's the problem:

Let $\mathbf{F}$ be the set of boolean functions, $f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2$, and let $U_k(f)$ denote the $k^{th}$ Gowers norm of $f$, which is defined as $U_k(f) = (\mathbb{E}_{x,y_1,y_2 \ldots y_k} (-1)^{\Delta_{y_1,\ldots,y_k} f(x)})^{\frac{1}{2^k}}$

Here $\Delta$ is the discrete derivative : $\Delta_{y} {f(x)} = f(x) + f(x+y)$. Give an estimate of the quantity $\mathbb{E}_{f \in \mathbf{F}} U_k(f)$, for $1 \le k \le 3$.

Intuitively, to me, it seems that this quantity should be vanishingly small (not lower-bounded by a constant which is independent of $n$) since the above expression is the Gowers norm of a random function, which cannot have a good correlation with low-degree polynomials. Is my line of thought correct, and can someone give a quantitative estimate of the above expression for $k = 1,2,3$?.

share|improve this question
    
Posted also to CSTheory: cstheory.stackexchange.com/q/6543/337 –  Joseph O'Rourke May 12 '11 at 18:59
6  
Try thinking about the expectation of the $2^k$th power of the norm. –  gowers May 13 '11 at 9:13
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.