Advanced Analysis

Discrete Fourier Analysis

1. Defining Characters

Let \(G\) be a finite abelian group (the canonical example will be \({\mathbb Z}_n\), the group of integers mod \(n\)). We say that a function \(e \ : \ G \rightarrow {\mathbb C} \setminus \{0\}\) is a character of the group \(G\) when
\[ e (a+b) = e(a) e(b) \]
for all \(a,b \in G\).
Proposition (Basic facts about characters)
Let \(G\) be a finite abelian group with identity element \(0\).
  • For any character \(e\), \(e(0) = 1\).
  • For any character \(e\) and any \(a \in G\), \(e(a)^{\#G}=1\). In particular, \(e(a)\) is always a root of unity and has modulus \(1\).
Proof
Meta (Key Ideas)
  • Use the formula \(e(0) = e(0+0) = e(0)e(0)\) and recall that characters are not allowed to vanish.
  • By Lagrange's Theorem, the order of \(a \in G\) must divide \(\#G\), i.e., there must be some \(n\) dividing \(\#G\) such that the \(n\)-fold sum of \(a\) with itself is the identity. By the character formula,
    \[ 1 = (e(a))^n \]
when \(n\) is the order of \(a\).

2. Writing Down All Characters

In \({\mathbb Z}_n\), we know that multiples of \(1\) generate all of \({\mathbb Z}_n\), and so
\[ e(m) = (e(1))^m \]
for each positive integer \(m\). Now the order of \(1\) in \(G\) is \(n\), meaning that the \(n\)-fold sum of \(1\) with itself is zero. In this case, this means that \(1 = (e(1))^n\), or that \(e(1)\) must be an \(n\)-th root of unity. But it's also easy to check that
\[ e_k (m) := e^{2 \pi i \frac{k}{n} m}\]
defines a character on \({\mathbb Z}_m\) for each \(k=0,\ldots,n-1\). Because \({\mathbb Z}_n\) is generated by \(1\), these must be the only characters on \({\mathbb Z}_n\) (since for each \(n\)-th root of unity \(\omega\), there is a \(k \in \{0,\ldots,n-1\}\) with \(e_k(1) = \omega\)). By similar reasoning, one can see that on \({\mathbb Z}_{n_1} \times \cdots \times {\mathbb Z}_{n_\ell}\), there are characters
\[ e_{(k_1,\ldots,k_\ell)}(m_1,\ldots,m_\ell) := e^{2 \pi i \sum_{j=1}^\ell \frac{k_j m_j}{n_j}}\]
and that when each \(k_j\) ranges over \(\{0,\ldots,n_j-1\}\), this must capture every possible character.

3. The Character Group

If \(e\) and \(e'\) are two characters on \(G\), then the product of \(e\) and \(e'\) must also be a character, because
\[{}e(a+b) e'(a+b){}\]
\[{}= e(a) e(b) e'(a) e'(b){}\]
\[{}= (e(a) e'(a)) (e(b) e'(b)).{}\]
Thus we may consider the set of all characters \(\widehat{G}\) of the group \(G\) to be an abelian group itself, called the character group. It's also true that the complex conjugate of a character must be a character.

We can check from our analysis above that the character group of any finite abelian group is isomorphic to the group itself (the formula we wrote down explicitly describes one isomorphism).
Proposition
Consider the following inner product on complex-valued functions \(f, g \ : \ G \rightarrow {\mathbb C}\):
\[ \left<f,g\right> := \frac{1}{\#G}\sum_{a \in G} f(a) \overline{g(a)}. \]
The characters of \(G\) are orthonormal with respect to this inner product.
Proof
Meta (Main Idea)
Consider the sum
\[{}\sum_{a \in G} e(a){}\]
We can always write this sum as equal to
\[{}\sum_{a \in G} e(a+b){}\]
for any fixed \(b \in G\) because the map \(a \mapsto a + b\) is a bijection of \(G\). Thus
\[{}\sum_{a \in G} e(a){}\]
\[{}= \sum_{a \in G} e(a+b){}\]
\[{}= \sum_{a \in G} e(a) e(b){}\]
\[{}= e(b) \sum_{a \in G} e(a).{}\]
So for any character \(e\), it must either be the case that \(e(b) = 1\) for all \(b\) (making it the so-called trivial character) or the sum must equal zero. As a consequence,
\[{}\sum_{a \in G} e(a) \overline{e'(a)} = \begin{cases} \#G & e = e' \\ 0 & \text{otherwise} \end{cases}{}\]
since \(e \overline{e'}\) is a character itself and is only trivial when \(e' = e\) since \(e \overline{e'} = 1\) means \(e' = (e \overline{e'})e' = e\) because \(e'\) has modulus \(1\).
Lemma (A Useful for Lemma for Later)
For each \(m \in G\), there are positive integers \(n_1,n_2\) with \(n_1 n_2 = \#G\) such that
\[ \prod_{e \in \widehat{G}} (1 - z e(m)) = (1 - z^{n_1})^{n_2}\]
for all \(z \in {\mathbb C}\).
Proof
As polynomials in \(z\), both sides are equal when \(z=0\) and both sides have the same degree. So it suffices to show that \(n_1\) and \(n_2\) can be chosen so that the roots in \({\mathbb C}\) of both sides are equal. But the roots in \({\mathbb C}\) are exactly the values of \(\overline{e(m)}\) counted with multiplicity as \(e\) ranges over \(\widehat{G}\). By examining the root \(z=1\), This forces \(n_2\) to equal the number of characters \(e\) for which \(e(m) = 1\). That collection of characters defines a subgroup \(H\) of \(G\), so its order always divides the order of \(G\), so we must have \(n_2 = \#H\) and \(n_1 = [G : H]\). In this case, the root \(z = 1\) will have multiplicity \(n_2\) for both polynomials. But in fact, for any \(\omega\) such that \(e(m) = \omega\) for some character \(e\), the number of \(e'\) having \(e'(m)\) must also equal \(n_2\), simply because the characters \(\{e^{-1} e'\}_{e'(m)=\omega}\) will be distinct and belong to \(H\). Finally, the values of \(e(m)\) are themselves a finite multiplicative subgroup of the complex unit circle. All such subgroups are cyclic, so the values \(\omega\) for which \(e(m) = \omega\) must be exactly \(k\)-th roots of unity for some \(k\). Counting total roots requires that \(k = n_1\).

4. Discrete Fourier Analysis

Definition
Given a function \(f : G \rightarrow {\mathbb C}\), let \(\widehat{f} : \widehat{G} \rightarrow {\mathbb C}\) be the function on \(\widehat{G}\) such that
\[ \widehat{f}(e) := \frac{1}{\sqrt{\#G}} \sum_{a \in G} f(a) \overline{e(a)}\]
(Note, \(\widehat{f}(e) = \left<f,e\right> \sqrt{\#G}\) the notation of the previous proposition.)
Meta (Translation and Modulation)
The thing that makes Fourier analysis “Fourier” is the relationship between translation and modulation. For example, if we define \(\tau_b f\) to be the function \(a \mapsto f(a - b)\) (translation by \(b\)), then
\[ \widehat{\tau_b f}(e) = e(-b) \widehat{f}(e) \]
for each \(f\) and each \(e \in \widehat{G}\), i.e., translation by \(b\) is converted via the Fourier transform into modulation (i.e., mutiplication) by \(e(-b)\). In the discrete case, this is the same as saying that all translation operators on the group are simultaneously diagonalized in the Fourier basis.

Similarly, for any character \(e\),
\[ \widehat{ e' f}(e) = \widehat{f}(e e'^{-1}) \]
i.e., multiplication by \(e'\) becomes its own kind of translation by \(e'\) on the side of the character group.
Theorem
If \(G\) is a finite abelian group, every \(f : G \rightarrow {\mathbb C}\) satisfies
\[ f = \frac{1}{\sqrt{\#G}} \sum_{e \in \widehat{G}} \widehat{f}(e) e \]
and
\[ \sum_{a \in G} |f(a)|^2 = \sum_{e \in \widehat{G}} |\widehat{f}(e)|^2. \]
Proof
Meta (Key Idea)
On a finite abelian group, the number of characters equals the order of the group and is also the dimension of the vector space of complex functions on \(G\). Since the characters are orthonormal with respect to the inner product defined above, they must be an orthonormal basis. We use factors of \(1/\sqrt{\#G}\) just to make everything more symmetric.