This was an assignment problem in a course on analytics combinatorics that I had taken this semester. Here is the problem:

Let $\mathbf{F}$ be the set of boolean functions, $f: \{0,1\}^n \rightarrow \{0,1\}$, 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 \in \mathbb{F}_2^n} (-1)^{\Delta_{y_1,y_2 \ldots y_k} f(x)})^\frac{1}{2^k} \text.$$

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 is correct, and can someone can give a quantitative estimate of the above expression for $k = 1,2,3$.

  • 3
    $\begingroup$ Is the homework done ? We wouldn't want to give you the answer :) $\endgroup$ May 12 '11 at 4:50
  • $\begingroup$ Yes, this was about a month and a half back. The semester's over, and I've already given it my best shot. $\endgroup$
    – user1694
    May 12 '11 at 5:11
  • 1
    $\begingroup$ that seems fair enough. Btw I think there's a typo in your definition of the discrete derivative - there should be a subtraction instead of the implied multiplication, right ? $\endgroup$ May 12 '11 at 5:11
  • $\begingroup$ Sorry for the mistake...$F$ contains boolean functions, and the earlier statement didn't make sense, since the Gowers norm is defined for real valued functions. Thus, by considering $(-1)^{f(x)}$, we are viewing $\mathbf{F}$ as a family of functions from $\mathbb{F}_2^n$ to $\{-1,1\} \in \mathbb{R}$. It should make sense now. $\endgroup$
    – user1694
    May 12 '11 at 6:06
  • 2
    $\begingroup$ Hint: Use convexity (Jensen's inequality) to get rid of 1/2^k on the inside and get it out. Then the expression becomes easy to evaluate. $\endgroup$
    – Srikanth
    Aug 3 '11 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy