Characterization of Boolean-valued functions on the discrete cube based on its Fourier coefficients.

Consider functions on the discrete cube $\{-1,1\}^n$.

We consider the Discrete Fourier Transform of such functions. Suppose we denote the parity function on a subset $S \subseteq [n]$ of co-ordinates by $\Pi_S(x)=\pi_{i \in S}(x_i)$, then the Fourier coefficient $\hat{f}_S$ is simply the expectation: $\hat{f}_S=\mathbb{E}_x[f(x)\Pi_S(x)]$; and by orthonormality of the parity functions, any $f$ may be represented as $f(x)=\sum_{S \subseteq [n]}\hat{f}_S \Pi_S(x)$ (the summation being in $\mathbb{R}$.)

I am interested in knowing the difference between boolean-valued ($\{-1,1\}^n \rightarrow \{-1,1\}$) and real-valued functions ($\{-1,1\}^n \rightarrow \mathbb{R}$). More specifically, I would like to know the difference between the Fourier spectra of either class of functions.

What properties of the Fourier spectra hold for one class but not for the other?

(As an example: It can be proved that for Boolean valued functions, if all the weight is concentrated on Fourier coefficients of size at most 1 then the function is either a constant or a dictator. This is not true for real-valued functions.)

-
I do not understand what caused the downvote... It would not hurt if the author would make explicit what exactly he means by Fourier transform, though (I imagine he looks at the domain as an abelian group and considers the corresponding Fourier analysis...) – Mariano Suárez-Alvarez Jan 12 '10 at 23:21
Thanks Mariano. Yes, the domain is interpreted as an abelian group; the fourier coefficients are just the correlations with the parity functions. I am not sure what the name for this fourier transform is. – Klingonesque Jan 12 '10 at 23:59
It's called the discrete Fourier transform, but you're going to have to specify whether you want the convolution for your first class of functions to be mod 2 or over the integers. – Qiaochu Yuan Jan 13 '10 at 2:34
Qiaochu: Thanks! I hope my edit also answers your question. – Klingonesque Jan 13 '10 at 15:41

1 Answer

This is a good question which is the subject of intensive research in mathematics and theoretical computer science. The blog (which is the serialization of a book in progress) "Analysis of Boolean Functions" by Ryan O'Donnell is a good source, and so is the Book: Lectures on noise sensitivity and percolation by Garban and Steif.

Here is some information

1) Of course, the Fourier coefficients of real functions over the discrete cube can be arbitrary. The question is therefore what restrictions apply for Boolean functions.

Boolean functions are characterized by $f^2(x)=1$ and since product translates to convolution for the Fourier transform, being Boolean is characterized by a property of the Fourier transform convolved with itself. However, this characterization by itself is not very useful.

Parseval formula asserts that for Boolean functions the sum of square of the Fourier coefficients is 1. It also give the following formula for the variance of $f$, $$\operatorname{var}(f) = \sum \{ \hat f^2(S): S \ne \emptyset \}$$

2) An important tool which gives much information is Bonami (or Bonami–Gross–Beckner) inequality. It asserts that for every function $f$, $$\|T_\epsilon (f) \|_2 \le \|f\| _{1+\epsilon^2}.$$ This implies that if $f$ has values $0$, $1$, and $-1$ and the the support of $f$ has measure $t$ then most of the Fourier spectrum of $f$ is for $S$ with $|A|> \log n/10$ (say).

3) A similar reasoning gives the so called KKL's theorem. It asserts that for a Boolean function $f$ there is an index $k$ so that $$\sum \{ \hat f^2(S): S \subset [n], i \in S \} \ge \operatorname{var}(f) \log n/n.$$

4) A theorem of Friedgut asserts that for a Boolean function $f$ if $\sum \hat f^2(S) |S|$ is bounded above by a constant $c$ then $f$ is "$\epsilon$-close" to a "Junta. " A Junta is a Boolean function depending on a bounded number $C$ of variables. ($C$ is a function of $c$ and $\epsilon$.)

5) A theorem by Green and Sanders from the paper Boolean functions with small spectral norm, asserts that a Boolean function all whose Fourier coefficients are bounded by $M$ is a linear combination of bounded number $(\le 2^{2^{O(M^4)}}$) of characteristic functions of subspaces.

6) A result by Talagrand asserts that for a Boolean functions $f_n$ if $\sum_i^n\hat f_n^2(\{i\})$ is o(1) then so is $\sum_i^n\hat f_n^2(\{i\})$. An extension of this result to higher levels was given by Benjamini, Kalai and Schramm, and a sharp quantitative version by Keller and Kindler.

7) A theorem of Bourgain asserts that for a Boolean function if the decay of the Fourier coefficients squared is larger than quadratic in $|S|$, then again $f$ is approximately a Junta.

8) There is a conjecture called the Entropy influence conjecture that asserts that $\sum \hat f^2 (S)|S|$ is bounded from below by an absolute constant times $\sum \hat f^2(S) \log (\hat f^2(S))$.

-