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$?.

CSTheory: cstheory.stackexchange.com/q/6543/337 – Joseph O'Rourke May 12 '11 at 18:59