Discrete Fourier Analysis - Analysis of Boolean Functions

1 Discrete Fourier Analysis

Definition (Character). Let $G$ be a finite Abelian group. A character on $G$ is a homomorphism $χ : G \to 𝕋 = {z \in ℂ : | z | = 1}$ .

The trivial character takes everything to $1$ .

Remark. This definition doesn’t change if $𝕋$ is replaced by $(ℂ ∖ {0}, \times)$ (because any finite subgroup of $(ℂ ∖ {0}, \times)$ must be a subgroup of $𝕋$ ).

Observe that if $χ_{1}$ and $χ_{2}$ are characters, then so is $χ_{1} χ_{2}$ , and also that if $χ$ is a character then so is $\bar{χ} = χ^{- 1}$ . Also, $χ \bar{χ} = χ_{0}$ , $χ_{0} χ = χ$ .

Thus, the characters on $G$ form an Abelian group, called the (Pontryagin) dual $Ĝ$ of $G$ .

We will soon see that $| G | = | \hat{G} |$ .

Notation 1.1. Let $f, g : G \to ℂ$ . We write

⟨ f, g ⟩ = 𝔼_{x \in G} f (x) \bar{g (x)},

where $𝔼_{x \in G}$ means $| G |^{- 1} \sum_{x \in G}$ . Then we also write $∥ f ∥_{2} = ⟨ f, f ⟩^{\frac{1}{2}} = {(𝔼_{x} | f (x) |^{2})}^{\frac{1}{2}}$ . We also define $∥ f ∥_{p} = {(𝔼_{x} | f {(x)}^{p})}^{\frac{1}{p}}$ , $1 \leq p < \infty$ and $∥ f ∥_{\infty} = \max_{x} | f (x) |$ .

Lemma 1.2 (Orthogonality of characters). The characters on $G$ form an orthonormal set.

Proof. Let $χ_{1}, χ_{2}$ be characters and let $χ = χ_{1} \bar{χ_{2}}$ . We need to prove that $𝔼_{x} χ (x)$ is $1$ if $χ = χ_{0}$ and $0$ otherwise. If $χ = χ_{0}$ , then the result is clear. Otherwise, pick $u$ such that $χ (u) \neq 1$ . Then

𝔼_{x} χ (x) = 𝔼_{x} χ (u x) = χ (u) 𝔼_{x} χ (x) .

Since $χ (u) \neq 1$ , we get the result. □

This shows that $| \hat{G} | \leq | G |$ . To show the reverse inequality we appeal to the classification of finite Abelian groups.

Theorem. Every finite Abelian group is a product of cyclic groups.

Corollary 1.3. The characters on $G$ form an orthonormal basis of $ℂ^{G}$ .

Proof. Since they form an orthonormal set, it remains to show that they span. Let

G = ℤ ∕ m_{1} ℤ \times \dots \times ℤ ∕ m_{k} ℤ .

Given $r, x \in ℤ ∕ m_{1} ℤ \times \dots \times ℤ ∕ m_{k} ℤ$ ( $r = (r_{1}, \dots, r_{k})$ , $x = (x_{1}, \dots, x_{k})$ ). Let

χ_{r} (x) = \prod_{j = 1}^{k} e^{2 π i \frac{r_{j} x_{j}}{m_{j}}} .

It is easy to check that $χ_{r}$ is a character, and that if $r \neq s$ then $χ_{r} \neq χ_{s}$ . □

Remark. This proof also demonstrates that $G ≅ \hat{G}$ . But the isomorphism is ‘horrible’: it doesn’t only depend on $G$ , but also on how we chose to write it as a product of cyclic groups.

A very useful convention is to use the uniform probability measure on $G$ and counting measure on $\hat{G}$ . For example, if $\hat{f}, ĝ : \hat{G} \to ℂ$ , we define

⟨ \hat{f}, ĝ ⟩ = \sum_{χ} \hat{f} (χ) ĝ (χ)

and

∥ \hat{f} ∥_{p} = {(\sum_{χ} | \hat{f} (χ) |^{p})}^{\frac{1}{p}} .

Definition (Fourier transform). Let $f : G \to ℂ$ . The Fourier transform $\hat{f}$ of $f$ is the function from $Ĝ$ to $ℂ$ defined by

\hat{f} (χ) = 𝔼_{x} f (x) \bar{χ (x)} = ⟨ f, χ ⟩ .

Since the characters form an orthonormal basis, you can also think of $\hat{f} (χ)$ as the coefficient of $f$ at $χ$ with respect to the orthonormal basis of characters.

Lemma 1.4. The Fourier transform has the following properties:

(1) Plancherel / Parseval identity: $⟨ \hat{f}, \hat{g} ⟩ = ⟨ f, g ⟩$ .
(2) Convolution identity: Define $f * g$ by
$f * g (x) = 𝔼_{u + v = x} f (u) g (v) .$

(for functions $\hat{G} \to ℂ$ , we define $*$ by $\sum$ rather than $𝔼$ ) Then
$\hat{f * g} (χ) \hat{f} (χ) \hat{g} (χ) .$
(3) Inversion formula:
$f (x) = \sum_{χ} \hat{f} (χ) χ (x) .$

Proof.

(1) $\begin{array}{l} ⟨ \hat{f}, \hat{g} ⟩ & = \sum_{χ} \hat{f} (χ) \bar{\hat{g} (χ)} \\ = \sum_{χ} (𝔼_{x} f (x) \bar{χ (x)}) \bar{(𝔼_{y} g (y) \bar{χ (y)})} \\ = 𝔼_{x} 𝔼_{y} f (x) \bar{g (y)} \sum_{χ} χ (x^{- 1} y) \end{array}$
An examination of the proof of Corollary 1.3 shows straightforwardly that
$\sum_{χ} χ (u) = {\begin{matrix} | G | & u = identity \\ 0 & otherwise \end{matrix}$

So $\sum_{χ} χ (x^{- 1} y) = Δ_{x y}$ where
$Δ_{x y} = {\begin{matrix} | G | & x = y \\ 0 & x \neq y \end{matrix}$

So we get
$𝔼_{x} 𝔼_{y} f (x) \bar{g (y)} \sum_{χ} χ (x^{- 1} y) = 𝔼_{x} 𝔼_{y} f (x) \bar{g (y)} Δ_{x y} = 𝔼_{x} f (x) \bar{g (x)} .$
(2) $\begin{array}{l} \hat{f * g} (χ) & = 𝔼_{x} f * g (x) \bar{χ (x)} \\ = 𝔼_{x} 𝔼_{u v = x} f (u) g (v) \bar{χ (u v)} \\ = 𝔼_{u, v} f (u) \bar{χ (u)} g (v) \bar{χ (v)} \\ = \hat{f} (χ) \hat{g} (χ) \end{array}$
(3) $\begin{array}{l} \sum_{χ} \hat{f} (χ) χ (x) & = \sum_{χ} 𝔼_{y} f (y) \bar{χ (y)} χ (x) \\ = 𝔼_{y} f (y) \sum_{χ} χ (x y^{- 1}) \\ = 𝔼_{y} f (y) Δ_{x y} \\ = f (x) □ \end{array}$

Specialising to $𝔽_{2}^{n}$

For each $r \in 𝔽_{2}^{n}$ , we can define a character $χ_{r}$ by

χ_{r} (x) = {(- 1)}^{r \cdot x},

where $r \cdot x$ is shorthand for $\sum_{i = 1}^{n} r_{i} x_{i} mod 2$ . This gives $2^{r}$ distinct characters, so all of them.

If $f : 𝔽_{2}^{n} \to ℂ$ , then for each $r \in \hat{𝔽_{2}^{n}}$ , we write

\hat{f} (r) = 𝔼_{x} {(- 1)}^{r \cdot x} f (x) .

If we identify elements $x$ of $𝔽_{2}^{n}$ with their supports $A_{x} = {i : x_{i} = 1}$ , then $r \cdot x = | A_{r} \cap A_{x} | m o d 2$ . uso if we take the group $(P ([n]), △)$ , then given a function $f : P ([n]) \to ℂ$ , we have

\hat{f} (B) = 𝔼_{A \subset [n]} f (A) {(- 1)}^{| A \cap B |} .

If we take the group ${- 1, 1}^{n}$ with pointwise multiplication, then the characters are the functions of the form

x \mapsto \prod_{i \in A} x_{i},

where $A \subset [n]$ . Write these as $x_{A}$ .

Warning. I shall be sloppy about the distinction between the function $x_{A}$ and the value it takes.

We shall write $\hat{f} (A)$ for $\hat{f} (x_{A})$ . Then $\hat{f} (A) = 𝔼_{x} f (x) x_{A}$ .

By the inversion formula, $f (x) = \sum_{A} \hat{f} (A) x_{A}$ .

Convention: I’ll say “multilinear” for “multiaffine”. So “linear in the school sense, rather than the linear algebra sense”.

The inversion formula therefore expresses $f : {- 1, 1}^{n} \to ℝ$ as the restriction to ${- 1, 1}^{n}$ of a multilinear function on $ℝ^{n}$ .

Lemma 1.5. For every $f : {- 1, 1}^{n} \to ℝ$ , there is a unique multilinear function $μ : ℝ^{n} \to ℝ$ such that $μ |_{{- 1, 1}^{n}} = f$ .

Proof. We have shown existence (using the inversion formula). For uniqueness, it is enough to show that if $μ$ is multilinear and vanishes on ${- 1, 1}^{n}$ , then it vanishes everywhere. We show this by induction on $n$ .

If $n = 1$ , then $μ$ is linear and $μ (- 1) = μ (1) = 0$ , so $μ \equiv 0$ .

Now assume the result for $n - 1$ and let $μ : ℝ^{n} \to ℝ$ be multilinear and $0$ on ${- 1, 1}^{n}$ . Since $μ$ depends linearly on the last coordinate, we can write for all $x \in ℝ^{n - 1}$ , $t \in ℝ$ ,

μ (x, t) = α (x) t + β (x) .

Let $x \in {- 1, 1}^{n - 1}$ . Then

β (x) = \frac{1}{2} (μ (x, 1) + μ (x, - 1)) = 0 .

Also, $μ (x, 0) = β (x)$ , so $β$ is multilinear. Since it vanishes on ${- 1, 1}^{n}$ , induction hypothesis gives that $β \equiv 0$ .

So $μ (x, t) = α (x) t$ . Setting $t = 1$ gives $α (x) = μ (x, 1)$ , so $α$ is multilinear and $0$ on ${- 1, 1}^{n - 1}$ , so $α \equiv 0$ . □

Definition (Degree (of a boolean function)). Let $f : {- 1, 1}^{n} \to ℝ$ . The degree of $f$ is the degree of the multilinear polynomial $μ$ that restricts to it. Equivalently, it is $\max {| A | : \hat{f} (A) \neq 0}$ .

1 Discrete Fourier Analysis

Specialising to 𝔽2n

Specialising to $𝔽_{2}^{n}$