2
$\begingroup$

This is from my research in computer science where the Fourier transform over $GF(2)^n$ is a tool to study functions on the Boolean hypercube.

For example, the majority function on 3 variables is defined to be $MAJ(x_1,x_2,x_3) = +1$ if and only if at least two of its inputs are +1, and -1 otherwise. It is a boolean function $MAJ:\{-1,+1\}^3\to \mathbb R$ and can be written uniquely in Fourier basis. In fact, it can be written as $$MAJ(x_1,x_2,x_3) = {\frac 1 2}x_1 + {\frac 1 2}x_2 + {\frac 1 2}x_3 -{\frac 1 2}x_1x_2x_3$$ and we can see it has four non-zero Fourier coefficients.


In my research, I have a boolean function $f(\mathbf x) = {\mathbf x}^T{\mathbf A}{\mathbf x}$ where $\mathbf x$ is a column vector of size $n$ whose entries are either 1 or -1, and $\mathbf A$ is an $n\times n$ positive semi-definite matrix. Clearly, I have $$f:\{-1,+1\}^n \to {\mathbb R}^+ \cup \{0\}.$$

I'm wondering whether all the Fourier transform coefficients of $f(\mathbf x)$ are non-zero. My intuition is based on the fact that I may regard it as a highly simplified version of Bochner's Theorem which characterizes the Fourier transform of a positive finite Borel measure on the real line.

Are all the Fourier coefficients non-negative? How can I prove it?

$\endgroup$
  • 4
    $\begingroup$ Just expand the inner products. You can read off the coefficients: $x_ix_j$ has coefficient $2a_{ij}$; 1 has coefficient $\sum a_{ii}^2$ (because $x_ix_i$ is 1). If $A$ is the matrix $\left(\begin{smallmatrix}2&-1\\-1&2\end{smallmatrix}\right)$, it's easy to see you have negative coefficients. $\endgroup$ – Anthony Quas Mar 9 '14 at 19:35

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.