# Fourier representation

## General

Every Boolean function $f:\{-1,1\}^n \to \{-1,1\}$ may be uniquely written as a multivariate polynomial:

$f(x) = \sum_{S \subseteq [n]} \hat{f}_S \prod_{i \in S} x_i$,

where $\hat{f}_S$ are real numbers called the Fourier coefficients of $f$.

The set of functions $\{\underset{i\in S}{\prod}x_{i}|S\subseteq [n] \}$ is an orthonormal basis of the vector space of all boolean functions $f:\{-1,1\}^{n}\to\mathbb{R}$ with the inner product:

$\left\lt f,g\right\gt =2^{-n}\underset{x\in\{-1,1\}^{n}}{\sum}f(x)g(x)=\underset{x\sim\{-1,1\}^{n}}{\mathbb{E}}[f(x)g(x)].$

### The Fourier Weight

For $f:\{-1,1\}^{n}\to\mathbb{R}$ and $0\leq k\leq n$ the Fourier weight of $f$ at degree $k$ (or depth $k$) is:

$W^{k}[f]=\underset{S\subseteq\{1,...n\},|s|=k}{\sum\hat{f}(S)^{2}}$

### Some useful identities

Parseval's identity: $\left\lt f,f\right\gt =\underset{S\in [n]}{\sum}\hat{f}(S)^{2}$

Plancharel's identity: $\left\lt f,g\right\gt =\underset{S\in [n]}{\sum}\hat{f}(S)\hat{g}(S)$

The convolution theorem: $\widehat{f * g}(S) = \widehat{f}(S) \widehat{g}(S)$, where $(f*g)(x) = \mathbb{E}_{y}\left[f(y)g(x \circ y) \right]$ (where $\circ$ is bit-wise multiplication).

## Properties

• TODO. Start off with relation between Fourier weight and other complexity measures such as circuit size, sensitivity, decision tree depth.