The previous section covered the case of $f \in L^2(\Omega^n, \pi^{\otimes n})$ with $|\Omega| = 2$; there, we saw it could be helpful to look at explicit Fourier bases. When $|\Omega| \geq 3$ this is often not helpful, especially if the only “operation” on the domain is equality. For example, if $f : \{\mathsf{Red}, \mathsf{Green}, \mathsf{Blue}\}^n \to {\mathbb R}$ then it’s best to just work abstractly with the orthogonal decomposition. However if there is a notion of, say, “addition” in $\Omega$ then there is a natural, canonical Fourier basis for $L^2(\Omega, \pi)$ when $\pi$ is the uniform distribution.
More precisely, suppose the domain $\Omega$ is a finite abelian group $G$, with operation $+$ and identity $0$. We will consider the domain $G$ under the uniform probability distribution $\pi$; this is quite natural because $\pi$ is translation-invariant: $\pi(X) = \pi(t + X)$ for any $X \subseteq G$, $t \in G$. In this setting it is more convenient to allow functions with range the complex numbers; thus we come to the following definition:
Definition 50 Let $G$ be a finite abelian group with operation $+$ and identity $0$. For $n \in {\mathbb N}^+$ we write $L^2(G^n)$ for the complex inner product space of functions $f : G^n \to {\mathbb C}$, with inner product \[ \langle f, g \rangle = \mathop{\bf E}_{{\boldsymbol{x}} \sim G^n}[f({\boldsymbol{x}})\overline{g({\boldsymbol{x}})}]. \] Here and throughout this section ${\boldsymbol{x}} \sim G^n$ denotes that ${\boldsymbol{x}}$ is drawn from the uniform distribution on $G^n$.
Everything we have done in this chapter for the real inner product space $L^2(\Omega^n, \pi^{\otimes n})$ generalizes easily to the case of a complex inner product; the main difference is that Plancherel’s Theorem becomes \[ \langle f, g \rangle = \sum_{\alpha \in {\mathbb N}^n_{< m}} \widehat{f}(\alpha) \overline{\widehat{g}(\alpha)} = \sum_{S \subseteq [n]} \langle f^{=S}, g^{=S} \rangle. \] See the exercises for more.
A natural Fourier basis for $L^2(G)$ comes from a natural family of functions $G \to {\mathbb C}$, namely the characters. These are defined to be the group homomorphisms from $G$ to ${\mathbb C}^\times$, where ${\mathbb C}^\times$ is the abelian group of nonzero complex numbers under multiplication.
Definition 51 A character of the (finite) group $G$ is a function $\chi : G \to {\mathbb C}^\times$ which is a homomorphism; i.e., satisfies $\chi(x + y) = \chi(x) \chi(y)$. Since $G$ is finite there is some $m \in {\mathbb N}^+$ such that $0 = x + x + \cdots + x$ ($m$ times) for each $x \in G$. Thus $1 = \chi(0) = \chi(x)^m$, meaning the range of $\chi$ is in fact contained in the $m$th roots of unity. In particular, $|\chi(x)| = 1$ for all $x \in G$.
We have the following easy facts:
Fact 52 If $\chi$ and $\phi$ are characters of $G$ then so are $\overline{\chi}$ and $\phi \cdot \chi$.
Proposition 53 Let $\chi$ be a character of $G$. Then either $\chi \equiv 1$ or $\mathop{\bf E}[\chi] = 0$.
Proof: If $\chi \not \equiv 1$, pick some $y \in G$ such that $\chi(y) \neq 1$. Since ${\boldsymbol{x}} + y$ is uniformly distributed on $G$ when ${\boldsymbol{x}} \sim G$, \[ \mathop{\bf E}_{{\boldsymbol{x}} \sim G}[\chi({\boldsymbol{x}})] = \mathop{\bf E}_{{\boldsymbol{x}} \sim G}[\chi({\boldsymbol{x}}+y)] = \mathop{\bf E}_{{\boldsymbol{x}} \sim G}[\chi({\boldsymbol{x}})\chi(y)] = \chi(y)\mathop{\bf E}_{{\boldsymbol{x}} \sim G}[\chi({\boldsymbol{x}})]. \] Since $\chi(y) \neq 1$ it follow that $\mathop{\bf E}[\chi({\boldsymbol{x}})]$ must be $0$. $\Box$
Proposition 54 The set of all characters of $G$ is orthonormal. (As a consequence, $G$ has at most $\dim(L^2(G)) = |G|$ characters.)
Proof: First, if $\chi$ is a character then $\langle \chi, \chi \rangle = \mathop{\bf E}[|\chi|^2] = 1$ because $|\chi| \equiv 1$. Next, if $\phi$ is another character distinct from $\chi$ then $\langle \phi, \chi \rangle = \mathop{\bf E}[\phi \cdot \overline{\chi}]$. But $\phi \cdot \overline{\chi}$ is a character by Fact 52, and $\phi \cdot \overline{\chi} = \phi/\chi \not \equiv 1$ because $\phi$ and $\chi$ are distinct; here we used $\overline{\chi} = 1/\chi$ because $|\chi| \equiv 1$. Thus $\langle \phi, \chi \rangle = 0$ by Proposition 53. $\Box$
As we will see next, $G$ in fact has exactly $|G|$ characters. It thus follows from Proposition 54 that the set of all characters (which includes the constant $1$ function) constitutes a Fourier basis for $L^2(G)$.
To check that each finite abelian group $G$ has $|G|$ distinct characters, we begin with the case of a cyclic group, ${\mathbb Z}_m$ for some $m$. In this case we know that every character’s range will be contained in the $m$th roots of unity.
Definition 55 Fix an integer $m \geq 2$ and write $\omega$ for the $m$th root of unity $\exp(2\pi i/m)$. For $0 \leq j < m$, we define $\chi_j : {\mathbb Z}_m \to {\mathbb C}$ by $\chi_j(x) = \omega^{jx}$. It is easy to see that these are distinct characters of ${\mathbb Z}_m$.
Thus the functions $\chi_0 \equiv 1, \chi_1, \dots, \chi_{m-1}$ form a Fourier basis for $L^2({\mathbb Z}_m)$. Furthermore, Proposition 13 tells us that we can get a Fourier basis for $L^2({\mathbb Z}_m^n)$ by taking all products of these functions.
Definition 56 Continuing Definition 55, let $n \in {\mathbb N}^+$. For $\alpha \in {\mathbb N}_{< m}^n$ we define $\chi_\alpha : {\mathbb Z}_m^n \to {\mathbb C}$ by \[ \chi_{\alpha}(x) = \prod_{j =1}^n \chi_{\alpha_j}(x_j). \] These functions are easily seen to be (all of the) characters of the group ${\mathbb Z}_m^n$, and they constitute a Fourier basis of $L^2({\mathbb Z}_m^n)$.
Most generally, by the Fundamental Theorem of Finitely Generated Abelian Groups we know that any finite abelian $G$ is a direct product of cyclic groups of prime-power order. In the exercises you are asked to check that you get all of the characters of $G$ — and hence a Fourier basis for $L^2(G)$ — by taking all products of the associated cyclic groups’ characters. In the remainder of the section we mostly stick to groups of the form ${\mathbb Z}_m^n$ for simplicity.
Returning to the characters $\chi_0, \dots, \chi_{m-1}$ from Definition 55, it is easy to see (using $\omega^m = 1$) that they satisfy $\chi_{j} \cdot \chi_{j’} = \chi_{j + j’ \pmod m}$ and also $1/\chi_{j} = \overline{\chi_j} = \chi_{-j \pmod m}$. Thus the characters themselves form a group under multiplication, isomorphic to ${\mathbb Z}_m$. As in Chapter 3.2, we index them using the notation $\widehat{{\mathbb Z}_m}$. More generally, indexing the Fourier basis/characters of $L^2({\mathbb Z}_m^n)$ by $\widehat{{\mathbb Z}_m^n}$ instead of multi-indices, we have:
Fact 57 The characters $(\chi_{\alpha})_{\alpha \in \widehat{{\mathbb Z}_m^n}}$ of ${\mathbb Z}_m^n$ form a group under multiplication:
- $\chi_{\alpha} \cdot \chi_{\beta} = \chi_{\alpha + \beta}$,
- $1/\chi_{\alpha} = \overline{\chi_{\alpha}} = \chi_{-\alpha}$.
As mentioned, the salient feature of $L^2(G)$ distinguishing it from other spaces $L^2(\Omega, \pi)$ is that there is a notion of addition on the domain. This means that convolution plays a major role in its analysis. We generalize the definition from the setting of ${\mathbb F}_2^n$:
Definition 58 Let $f, g \in L^2(G)$. Their convolution is the function $f * g \in L^2(G)$ defined by \begin{equation*} (f * g)(x) = \mathop{\bf E}_{\boldsymbol{y} \sim G}[f(\boldsymbol{y}) g(x - \boldsymbol{y})] = \mathop{\bf E}_{\boldsymbol{y} \sim G}[f(x-\boldsymbol{y})g(\boldsymbol{y})]. \end{equation*}
In the exercises you are asked to check that convolution is associative and commutative, and that the following generalization of Theorem 1.28 holds:
Theorem 59 Let $f, g \in L^2(G)$. Then $\widehat{f * g}(\alpha) = \widehat{f}(\alpha) \widehat{g}(\alpha)$.
We conclude this section by mentioning vector space domains. When doing Fourier analysis over the group ${\mathbb Z}_m^n$, it is natural for subgroups to arise. Things are simplest when the only subgroups of ${\mathbb Z}_m$ are the trivial ones, $\{0\}$ and ${\mathbb Z}_m$; in this case, all subgroups will be isomorphic to ${\mathbb Z}_m^{n’}$ for some $n’ \leq n$. Of course, this simple situation occurs if and only if $m$ is equal to some prime $p$. In that case, ${\mathbb Z}_p$ can be thought of as a field, ${\mathbb Z}_p^n$ as an $n$-dimensional vector space over this field, and its subgroups as subspaces. We use the notation ${\mathbb F}_p^n$ in this setting and write $\widehat{{\mathbb F}_p^n}$ to index the Fourier basis/characters; this generalizes the notation introduced for $p = 2$ in Chapter 3.2. Indeed, all of the notions from Chapters 3.2 and 3.3 regarding affine subspaces and restrictions thereto generalize easily to $L^2({\mathbb F}_p^n)$.
Recent comments