MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Posted also to CSTheory: – Joseph O'Rourke May 12 '11 at 18:59
Try thinking about the expectation of the $2^k$th power of the norm. – gowers May 13 '11 at 9:13

Your Answer


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

Browse other questions tagged or ask your own question.