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