I am working through Ryan O' Donnell's book on the analysis of Boolean functions. One of the exercises (1.1) is to compute the Fourier series of the `complete quadratic function' on $\mathbf{F}_2^n$

$$ CQ(x) = (-1)^{\sum_{i < j} x_i x_j} $$

Without any fancy harmonic analysis terminology, the problem asks us to calculate the expectations

$$\widehat{f}(S) = \mathbf{E}[CQ(X)(-1)^{\sum_{i \in S} x_i}]$$

for any subset $S \subset \{ 1, \dots, n \}$, where $X$ is uniformly distributed on $\mathbf{F}_2^n$, in which case we can write

$$ CQ(x) = \sum_{S \subset [n]} \widehat{f}(S) (-1)^{\sum_{i \in S} x_i}$$

An important first step to solving the problem is noticing that $CQ(x)$ depends only on the number of indices $i$ such that $x_i = 1$. That is, $CQ(x) = 1$ if and only if $n(n-1)$ is divisible by 4. However, I can't seem to get anywhere from this. This makes it easy to compute the expectation of $CQ(x)$ (though I can't seem to see a nice `general' formula, I've just broken down the analysis depending on $n$'s congruence class modulo 4). In order to calculate $\widehat{f}(S)$ in general, I've tried calculating the expectation by condition on both $(-1)^{\sum_{i \in S} x_i} = \pm 1$, and conditioning on the latter gives (assuming $S$ has $m$ elements)

$$ \mathbf{E}(CQ(X) (-1)^{\sum_{i \in S} x_i} = (1/2^n) \sum_{k = 0}^m \sum_{l = 0}^{n-m} (-1)^k {m \choose k} {n - m \choose l} r_{k+l} $$

where $r_x = 1$ if $x$ is congruent to 0 or 1 (mod 4), and $r_x = -1$ if $x$ is congruent to 2 or 3 (mod 4). But my knowledge of binomial identities is really rusty and I don't know how to reduce the sum any further. Any guidance?

  • $\begingroup$ Since the function depends only on the Hamming weight of the input, you should be getting some complicated expression involving Kravchuk polynomials, which is indeed what you're getting. I'm not sure that there is a really simple expression for the Fourier coefficients. $\endgroup$ – Yuval Filmus Feb 27 '17 at 0:52

Your Answer

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

Browse other questions tagged or ask your own question.