Fourier Transform over Finite Abelian Groups

Here is an overview of Fourier analysis applied to finite abelian groups. It shows how to generalize a priori different computations such as the discrete Fourier transform or the Hadamard-Walsh transform.

CHARACTER

Let $G$ be a finite abelian group with additive notation. A character of $G$ is a group homomorphism $\chi : G \rightarrow \mathbb{C} - \{ 0 \}$ that is to say for all $a , b \in G$

$\displaystyle \chi ( a + b ) = \chi ( a ) \chi ( b )$

$\displaystyle \chi ( 0 ) = 1$

It is straightforward to check that the characters of $G$ form a group called the dual group, which is denoted by $\widehat{G}$.

• Group law : $( \chi_1 \chi_2 ) ( a ) = \chi_1 ( a ) \chi_2 ( a )$
• Neutral element : $\chi_0 = 1$ is called the principal character
• Inversion : $\chi^{-1} ( a ) = \chi ( a )^{-1}$

ISOMORPHISM

We consider, up to an isomorphism, that a cyclic group of order $n$ is the additive group of integers modulo $n$ denoted by $\mathbb{Z}_n$. Then, to each $[p] \in \mathbb{Z}_n$ we can associate a mapping

$\displaystyle \chi_{[p]} : \mathbb{Z}_n \rightarrow \mathbb{C} \textrm{ such that } \chi_{[p]} ( [q] ) = e^{i 2 \pi p q / n}$

This mapping is independent of the choice of the representatives since $e^{i 2 \pi p q / n}$ is n-periodic in both $p$ and $q$. In order to improve the readability we remove the squares around the representatives and write $p$ instead of $[p]$.

It is easy to check that $\chi_{p}$ are characters of $\mathbb{Z}_n$

$\displaystyle \chi_{p} ( q + q' ) = \chi_{p} ( q ) \chi_{p} ( q' )$

For similar reasons we have

$\displaystyle \chi_{p + p'} ( q ) = \chi_{p} ( q ) \chi_{p'} ( q )$

which gives the group law of $\widehat{\mathbb{Z}_n}$. This implies that the dual group is a cyclic group of order $n$. Hence the following lemma

Lemma : $\mathbb{Z}_n \simeq \widehat{\mathbb{Z}_n}$

This result can be generalized to finite abelian groups

Theorem : Let G be a finite abelian group. Then $G \simeq \widehat{G}$

Proof

It is well known from abstract algebra that a finite abelian group can be decomposed as a direct sum of cyclic groups, namely

$\displaystyle G = G_1 \oplus \cdots \oplus G_m$

The trick consists of proving an isomorphism with the group direct product

$\displaystyle \widehat{G} \simeq \widehat{G_1} \oplus \cdots \oplus \widehat{G_m}$.

Let $\chi_1 , \cdots , \chi_m$ be characters of $G_1 , \cdots , G_m$ respectively. We define the function

$\displaystyle \chi ( g_1 , \cdots , g_m ) = \chi_1 ( g_1 ) \cdots \chi_m( g_m )$

Clearly, $\chi$ is a character of $G$ and the construction of $\chi$ from $\chi_1 , \cdots , \chi_m$ is injective.

Now, consider $\chi \in \widehat{G}$. The restriction $\chi_i = \chi | G_i$ is a character of $G_i$. It follows $\chi = \chi_1 \oplus \cdots \oplus \chi_m$.

ORTHOGONALITY

Let $G$ be a finite abelian group. The functions $f : G \rightarrow \mathbb{C}$ form the Hilbert space $\ell^2(G)$. In particular, the characters are elements of $\ell^2(G)$ and satisfy the following lemma

Lemma : Suppose $\chi , \eta \in \widehat{G}$. Then

$\displaystyle \left\langle \chi , \eta \right\rangle = \begin{cases} |G| \textrm{ if } \chi = \eta \\ 0 \textrm{ otherwise} \end{cases}$

Proof

The first case is easy. If $\chi = \eta$ then

$\displaystyle \left\langle \chi , \eta \right\rangle = \sum_{g \in G} \chi(g) \overline{\eta(g)} = \sum_{g \in G} | \chi(g) |^2 = \sum_{g \in G} 1 = |G|$

Note that we have used the property $| \chi(g) | = 1$ meaning that each value $\chi(g)$ is a root of unity. Indeed, the dual group being finite, all characters have finite order.

The second case is not really more difficult. Put $\sigma = \chi \eta^{-1}$ . Since $\chi \neq \eta$ the character $\sigma$ is different from $1$. Thus there exists $h$ such that $\sigma(h) \neq 1$. The inner product can be rewritten using $\sigma$ and the property $\overline{\eta} = \eta^{-1}$ (since $\eta(g)$ is a root of unity as explained before).

$\displaystyle \left\langle \chi , \eta \right\rangle = \sum_{g \in G} \sigma(g)$

We can permute the elements of $G$ by adding $h$

$\displaystyle \left\langle \chi , \eta \right\rangle = \sum_{g \in G} \sigma(h + g) = \sigma(h) \sum_{g \in G} \sigma(g) = \sigma(h) \left\langle \chi , \eta \right\rangle$

Therefore

$\displaystyle (1 - \sigma(h)) \left\langle \chi , \eta \right\rangle = 0$

Finally we deduce $\left\langle \chi , \eta \right\rangle = 0$ since $\sigma(h) \neq 1$ by definition.

FOURIER TRANSFORM

We are now ready to define the Fourier transform on finite abelian groups.

Fourier transform : Let $G$ be a finite abelian group and $f : G \rightarrow \mathbb{C}$. Then the Fourier transform of $f$ is by definition

$\displaystyle \widehat{f} : \widehat{G} \rightarrow \mathbb{C} \textrm{ with } \widehat{f} ( \chi ) = \frac{1}{\sqrt{|G|}} \left\langle f , \chi \right\rangle$

This definition is really similar to the well known discrete Fourier transform. We can illustrate on two examples.

Example : $G = \mathbb{Z}_n$

We have seen that characters of $\mathbb{Z}_n$ are given by $\chi_p ( q) = e^{i 2 \pi p q / n}$. Thus, the Fourier transform as defined on finite abelian groups is

$\displaystyle \widehat{f} ( \chi_p ) = \frac{1}{\sqrt{n}} \sum_{q \in \mathbb{Z}_n} e^{- i 2 \pi p q / n} f ( q )$

We recover the definition of the usual discrete Fourier transform.

Example : $G = \mathbb{F}_{2}^{m} = \mathbb{Z}_2 \oplus \cdots \oplus \mathbb{Z}_2$ ($m$ times)

Clearly, the characters are m-products of the characters of $\mathbb{Z}_2$ (if you do not see why then recall the proof of $G \simeq \widehat{G}$ above).

The characters of $\mathbb{Z}_2$ are easy to determine :

$\displaystyle \chi_p ( q ) = e^{i 2 \pi p q / 2} = ( - 1 )^{p q}$

As a consequence the characters of $\mathbb{F}_{2}^{m}$ are given by m-products

$\displaystyle \chi_p ( q ) = ( - 1 )^{p_1 q_1} \cdots ( - 1 )^{p_m q_m}$

where $p = (p_1 , \cdots , p_m)$ and $q = (q_1 , \cdots , q_m)$. We use the standard inner product of vectors to simplify the writing

$\displaystyle \chi_p ( q ) = ( - 1 )^{p \cdot q}$

The Fourier transform as defined on finite abelian groups is

$\displaystyle \widehat{f} ( \chi_p ) = \frac{1}{\sqrt{2^m}} \sum_{q \in \mathbb{F}_{2}^{m}} ( - 1 )^{p \cdot q} f ( q )$

We recover the definition of the usual Hadamard-Walsh transform.