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

Definition 1Let $(\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 2A 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 3We 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 4Much 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 5Let $|\Omega| = m$. Theindicator basis(orstandard 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 6The 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 7AFourier basisfor an inner product space $L^2(\Omega, \pi)$ is an orthonormal basis $\phi_0, \dots, \phi_{m-1}$ with $\phi_0 \equiv 1$.

Example 8For 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 9A 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 10In 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 11An $n$-dimensionalmulti-indexis 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 12Given 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 13Let $\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 14Havingfixeda 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 theFourier expansionof $f$ with respect to the basis. The real number $\widehat{f}(\alpha)$ is called theFourier coefficient of $f$ on $\alpha$and it satisfies \[ \widehat{f}(\alpha) = \langle f, \phi_\alpha \rangle. \]

Example 15Fix 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.

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

Thank you!

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