Discrete Fourier Analysis - Analysis of Boolean Functions

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

Ĝ

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) |$ .

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.

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

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

χ

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}

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.

f : 𝔽_{2}^{n} \to ℂ

, then for each

r \in \hat{𝔽_{2}^{n}}

, we write

If we identify elements

x

𝔽_{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

If we take the group

{- 1, 1}^{n}

with pointwise multiplication, then the characters are the functions of the form

We shall write

\hat{f} (A)

for

\hat{f} (x_{A})

. Then

\hat{f} (A) = 𝔼_{x} f (x) 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}

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}$