# §8.1: Fourier bases for product spaces

We will now begin to discuss functions on (finite) product probability spaces.

Definition 1 Let $(\Omega, \pi)$ be a finite probability space and assume $\pi$ has full support. For $n \in {\mathbb N}^+$ we write $L^2(\Omega^n, \pi^{\otimes n})$ for the (real) inner product space of functions $f : \Omega^n \to {\mathbb R}$, with inner product $\langle f, g \rangle = \mathop{\bf E}_{{\boldsymbol{x}} \sim \pi^{\otimes n}}[f({\boldsymbol{x}})g({\boldsymbol{x}})].$ Here $\pi^{\otimes n}$ denotes the product probability distribution on $\Omega^n$.

Example 2 A simple example to keep in mind is $\Omega = \{a,b,c\}$ with $\pi(a) = \pi(b) = \pi(c) = 1/3$. Here $a$, $b$, and $c$ are simply abstract set elements.

We can (and will) generalize to non-discrete probability spaces, and to complex inner product spaces. However we will keep to the above definition for now.

Notation 3 We will write $\pi_{1/2}$ for the uniform probability distribution on $\{-1,1\}$. Thus so far in this book we have been studying functions in $L^2(\{-1,1\}^n, \pi_{1/2}^{\otimes n})$. For simplicity, we will write this as $L^2(\{-1,1\}^n)$.

Notation 4 Much of the notation we used for $L^2(\{-1,1\}^n)$ extends naturally to the case of $L^2(\Omega^n, \pi^{\otimes n})$: e.g., $\|f\|_p = \mathop{\bf E}_{{\boldsymbol{x}} \sim \pi^{\otimes n}}[|f({\boldsymbol{x}})|^p]^{1/p}$, or the restriction notation from Chapter 3.3.

As we described in Chapter 1.4, the essence of boolean Fourier analysis is in deriving combinatorial properties of a boolean function $f : \{-1,1\}^n \to {\mathbb R}$ from its coefficients over a particular basis of $L^2(\{-1,1\}^n)$, the basis of parity functions. We would like to achieve the same thing more generally for functions in $L^2(\Omega^n, \pi^{\otimes n})$. We begin by considering vector space bases more generally.

Definition 5 Let $|\Omega| = m$. The indicator basis (or standard basis) for $L^2(\Omega, \pi)$ is just the set of $m$ indicator functions $(1_{x})_{x \in \Omega}$, where $1_{x}(y) = \begin{cases} 1 & \text{if } y = x, \\ 0 & \text{if } y \neq x. \end{cases}$

Fact 6 The indicator basis is indeed a basis for $L^2(\Omega,\pi)$ since the functions $(1_{x})_{x \in \Omega}$ are nonzero, spanning, and orthogonal. Hence $\dim(L^2(\Omega,\pi)) = m$.

We will usually fix $\Omega$ and $\pi$ and then consider $L^2(\Omega^n, \pi^{\otimes n})$ for $n \in {\mathbb N}^+$. Applying the above definition gives us an indicator basis $(1_{x})_{x \in \Omega^n}$ for the $m^n$-dimensional space $L^2(\Omega^n, \pi^{\otimes n})$. The representation of $f \in L^2(\Omega,\pi)$ in this basis is just $f = \sum_{x \in \Omega} f(x)1_{x}$. This is not very interesting; the coefficients are just the values of $f$ so they don’t tell us anything new about the function. We would like a different basis that will generate useful “Fourier formulas” as in Chapter 1.4.

For inspiration, let’s look critically at the familiar case of $L^2(\{-1,1\}^n)$. Here we used the basis of all parity functions, $\chi_S(x) = \prod_{i\in S} x_i$. It will be helpful to think of the basis function $\chi_S : \{-1,1\}^n \to {\mathbb R}$ as follows: identify $S$ with its $0$-$1$ indicator vector and write \begin{gather*} \chi_S(x) = \prod_{i=1}^n \phi_{S_i}(x_i), \qquad \text{where} \quad \phi_0 \equiv 1, \quad \phi_1 = \textit{id}. \end{gather*} (Here $\textit{id}$ is just the identity map $\textit{id}(b) = b$.) We will identify three properties of this basis which we’d like to generalize.

First, the parity basis is a product basis. We can break down its “product structure” as follows: For each coordinate $i \in [n]$ of the product domain $\{-1,1\}^n$, the set $\{1, \textit{id}\}$ is a basis for the $2$-dimensional space $L^2(\{-1,1\}, \pi_{1/2})$. We then get a basis for the $2^n$-dimensional product space $L^2(\{-1,1\}^n)$ by taking all possible $n$-fold products. More generally, suppose we are given an inner product space $L^2(\Omega, \pi)$ with $|\Omega| = m$. Let $\phi_0, \dots, \phi_{m-1}$ be any basis for this space. Then the set of all products $\phi_{i_1} \phi_{i_2} \cdots \phi_{i_n}$ ($0 \leq i_j < m$) forms a basis for the space $L^2(\Omega^n, \pi^{\otimes n})$.

Second, it is convenient that the parity basis is orthonormal. We will later check that if a basis $\phi_0, \dots, \phi_{m-1}$ for $L^2(\Omega, \pi)$ is orthonormal, then so too is the associated product basis for $L^2(\Omega^n, \pi^{\otimes n})$. This relies on the fact that $\pi^{\otimes n}$ is the product distribution. For example, the parity basis for $L^2(\{-1,1\}^n)$ is orthonormal because the basis $\{1, \textit{id}\}$ for $L^2(\{-1,1\}, \pi_{1/2})$ is orthonormal: $\mathop{\bf E}[1^2] = \mathop{\bf E}[{\boldsymbol{x}}_i^2] = 1$, $\mathop{\bf E}[1 \cdot {\boldsymbol{x}}_i] = 0$. Orthonormality is the property that makes Parseval’s Theorem hold; in the general context, this means that if $f \in L^2(\Omega, \pi)$ has the representation $\sum_{i=0}^{m-1} c_i \phi_i$ then $\mathop{\bf E}[f^2] = \sum_{i=0}^{m-1} c_i^2$.

Finally, the parity basis contains the constant function $1$. This fact leads to several of our pleasant Fourier formulas. In particular, when you take an orthonormal basis $\phi_0, \dots, \phi_{m-1}$ for $L^2(\Omega, \pi)$ which has $\phi_0 \equiv 1$, then $0 = \langle \phi_0, \phi_i\rangle = \mathop{\bf E}_{{\boldsymbol{x}} \sim \pi} [\phi_i({\boldsymbol{x}})]$ for all $i > 0$. Hence if $f \in L^2(\Omega,\pi)$ has the expansion $f= \sum_{i=0}^{m-1} c_i \phi_i$, then $\mathop{\bf E}[f] = c_0$ and $\mathop{\bf Var}[f] = \sum_{i > 0} c_i^2$.

We encapsulate the second and third properties with a definition:

Definition 7 A Fourier basis for an inner product space $L^2(\Omega, \pi)$ is an orthonormal basis $\phi_0, \dots, \phi_{m-1}$ with $\phi_0 \equiv 1$.

Example 8 For each $n \in {\mathbb N}^+$, the $2^n$ parity functions $(\chi_S)_{S \subseteq [n]}$ form a Fourier basis for $L^2(\{-1,1\}^n, \pi_{1/2}^{\otimes n})$.

Remark 9 A Fourier basis for $L^2(\Omega, \pi)$ always exists because you can extend the set $\{1\}$ to a basis and then perform the Gram–Schmidt process. On the other hand, Fourier bases are not unique. Even in the case of $L^2(\{-1,1\}, \pi_{1/2})$ there are two possibilities: the basis $\{1, \textit{id}\}$ and the basis $\{1, -\textit{id}\}$.

Example 10 In the case of $\Omega = \{a,b,c\}$ with $\pi(a) = \pi(b) = \pi(c) = 1/3$, one possible Fourier basis (see the exercises) is $\phi_0 \equiv 1, \quad \begin{array}{l} \phi_1(a) = +\sqrt{2} \\ \phi_1(b) = -\sqrt{2}/2 \\ \phi_1(c) = -\sqrt{2}/2, \end{array} \quad \begin{array}{l} \phi_2(a) = 0 \\ \phi_2(b) = +\sqrt{6}/2, \\ \phi_2(c) = -\sqrt{6}/2. \end{array}$

As mentioned, given a Fourier basis for $L^2(\Omega, \pi)$ you can construct a Fourier basis for any $L^2(\Omega^n, \pi^{\otimes n})$ by “taking all $n$-fold products”. To make this precise we need some notation.

Definition 11 An $n$-dimensional multi-index is a tuple $\alpha \in {\mathbb N}^n$. We write $\mathrm{supp}(\alpha) = \{i : \alpha_i \neq 0\}, \quad \text{and} \quad \#\alpha = |\mathrm{supp}(\alpha)|.$ (We don’t use the notation $|\alpha|$ here as this traditionally denotes $\sum_{i=1}^n \alpha_i$.) We may write $\alpha \in {\mathbb N}_{<m}^n$ when we want to emphasize that each $\alpha_i \in \{0, 1, \dots, m-1\}$.

Definition 12 Given functions $\phi_0, \dots, \phi_{m-1} \in L^2(\Omega, \pi)$ and a multi-index $\alpha \in {\mathbb N}_{< m}^n$, we define $\phi_\alpha \in L^2(\Omega^n, \pi^{\otimes n})$ by $\phi_\alpha(x) = \prod_{i=1}^n \phi_{\alpha_i}(x_i).$

Now we can show that products of Fourier bases are Fourier bases.

Proposition 13 Let $\phi_0, \dots, \phi_{m-1}$ be a Fourier basis for $L^2(\Omega, \pi)$. Then the collection $(\phi_\alpha)_{\alpha \in {\mathbb N}_{<m}^n}$ is a Fourier basis for $L^2(\Omega^n,\pi^{\otimes n})$ (with the understanding that $\alpha = (0, 0, \dots, 0)$ indexes the constant function $1$).

Proof: First we check orthonormality. For any multi-indices $\alpha, \beta \in {\mathbb N}_{<m}^n$ we have \begin{align*} \langle \phi_\alpha, \phi_\beta \rangle &= \mathop{\bf E}_{{\boldsymbol{x}} \sim \pi^{\otimes n}}[\phi_\alpha({\boldsymbol{x}})\cdot \phi_\beta({\boldsymbol{x}})] \\ &= \mathop{\bf E}_{{\boldsymbol{x}} \sim \pi^{\otimes n}}\Bigl[\prod_{i = 1}^n \phi_{\alpha_i}({\boldsymbol{x}}_i) \cdot \prod_{i = 1}^n \phi_{\beta_i}({\boldsymbol{x}}_i)\Bigr] \\ &= \prod_{i = 1}^n \mathop{\bf E}_{{\boldsymbol{x}}_i \sim \pi}[\phi_{\alpha_i}({\boldsymbol{x}}_i) \cdot \phi_{\beta_i}({\boldsymbol{x}}_i)] \tag{$\pi^{\otimes n}$ is a product distribution} \\ &= \prod_{i = 1}^n \boldsymbol{1}_{\{\alpha_i = \beta_i\}} \tag{$\{\phi_0, \dots, \phi_{m-1}\}$ is orthonormal} \\ &= \boldsymbol{1}_{\{\alpha = \beta\}}. \end{align*} This confirms that the collection $(\phi_\alpha)_{\alpha \in {\mathbb N}_{<m}^n}$ is orthonormal, and consequently linearly independent. It is therefore also a basis because it has cardinality $m^n$, which we know is the dimension of $L^2(\Omega^n, \pi^{\otimes n})$ (see Fact 6). $\Box$

Given a product Fourier basis as in Proposition 13, we can express any $f \in L^2(\Omega^n, \pi^{\otimes n})$ as a linear combination of basis functions. We will write $\widehat{f}(\alpha)$ for the “Fourier coefficient” on $\phi_\alpha$ in this expression.

Definition 14 Having fixed a Fourier basis $\phi_{0}, \dots, \phi_{m-1}$ for $L^2(\Omega, \pi)$, every $f \in L^2(\Omega^n, \pi^{\otimes n})$ is uniquely expressible as $f = \sum_{\alpha \in {\mathbb N}_{< m}^n} \widehat{f}(\alpha) \phi_\alpha.$ This is the Fourier expansion of $f$ with respect to the basis. The real number $\widehat{f}(\alpha)$ is called the Fourier coefficient of $f$ on $\alpha$ and it satisfies $\widehat{f}(\alpha) = \langle f, \phi_\alpha \rangle.$

Example 15 Fix the Fourier basis as in Example 10. Let $f : \{a,b,c\}^2 \to \{0,1\}$ be the function which is $1$ if and only if both inputs are $c$. Then you can check (see the exercises) that \begin{multline*} f = \tfrac19 – \tfrac{\sqrt{2}}{18} \phi_{(1,0)} – \tfrac{\sqrt{6}}{18} \phi_{(2,0)} – \tfrac{\sqrt{2}}{18} \phi_{(0,1)} – \tfrac{\sqrt{6}}{18} \phi_{(0,2)} \\
+ \tfrac{1}{18}\phi_{(1,1)} + \tfrac{\sqrt{12}}{36} \phi_{(2,1)} + \tfrac{\sqrt{12}}{36} \phi_{(1,2)} + \tfrac{1}{6}\phi_{(2,2)}. \end{multline*}

The notation $\widehat{f}(\alpha)$ may seem poorly chosen because it doesn’t show the dependence on the basis. However the Fourier formulas we develop in the next section will have the property that they are the same for every product Fourier basis. We will show a basis-independent way of developing the formulas in Section 3 of this chapter. We also give a more abstract approach to general domains in a later chapter.

### 3 comments to §8.1: Fourier bases for product spaces

• Albert Atserias

Tiny typo: In Proposition 13, “is indexes”.

• Thank you!

• Thanks! Am really studying your paper with Maneva these days, by the way.