Fourier Transform on Finite Abelian Groups

the main goal of this quick note is to simultaneously misrepresent the work done by Harmonic Analysts and by working under some dubious assumptions, shed some light on how we can define a Fourier transform  on finite abelian groups.

 

Suppose we are given a function f:\mathbb R \to \mathbb R that is 2 \pi periodic, and suppose further that it is a function that deserves to be integrated. Then, we know from the grapevine that we can rewrite f in terms of its “Fourier series:”

    \[f(x)=a_0+\sum_{n=1}^{\infty}[a_n \cos(nx)+b_n \sin(nx)]\]

and lest anyone is nauseated by trigonometric functions, let’s quickly generalize out of this to functions f: \mathbb R \to \mathbb C by rewriting \cos(x) and \sin(x) in terms of e^{inx}. In other words, we are now thinking about

    \[L^2(\mathbb R):=\{f:\mathbb R \to \mathbb C \mid \int_{\mathbb R} |f|^2 d \mu<\infty\}.\]

Now, we can write f:=\sum_{n=-\infty}^{\infty}a_n e^{in x}, where

    \[a_n:=\int_{\mathbb R}fe^{-in x}dx.\]

Indeed, from a slightly different point of view, L^2(\mathbb R) has the structure of a Hilbert Space, with norm induced by the inner product \langle f,g \rangle:=\int_{\mathbb R}f(x)\overline{g(x)}dx. And as one can check, \{e^{in x }\} forms an orthonormal basis for this Hilbert space.

 

 

However, we can adopt a slightly different  point of view. We can consider the action of \mathbb R on this space of functions, given by \phi_r(f(x)):=f(x+r), or the regular representation . Equivalently, we can consider functions S^1 \to \mathbb C, with S^1 acting on itself by complex multiplication. Then, the inner product is in fact induced by Haar measure, and it agrees with Lebesgue measure, so nothing changes. In particular, since S^1 is compact and abelian, we have that the representation of S^1 on L^2(S^1) is completely reducible, and all irreducible representations are one dimensional. Indeed, \chi_n(e^{i \theta}):=e^{in\theta} for each n \in \mathbb Z, and since S^1 is abelian, all functions are class functions (conjugation invariant), so we have that \frac{1}{2 \pi} \int_{[-\pi,\pi]} d \mu gives the same inner product, although it “averages” over the group, to make the characters unit length. Indeed, then the classical results in Fourier decomposition are in fact just statements about the representation theory of S^1.

 

Our goal is to now apply the same principles to finite abelian groups. In particular, the same statements hold true, for finite abelian groups, and their characters G \to S^1 form a basis for the regular representations H^1(G):=\{f:G \to \mathbb C \}, so we can also consider the “Fourier decomposition” of functions on finite Abelian groups. The only modification here, is that we take the easier inner product

    \[\langle \alpha,\beta\rangle:=\frac{1}{|G|} \sum_{g \in G} \overline{\alpha(g)} \beta(g).\]

 

Hence, we obtain a decomposition (fourier inversion formula):

    \begin{align*}f=\sum_{g \in G} \langle f,\chi_g\rangle \chi_g \end{align*}

which is exactly what we wanted.

However, we can actually rewrite this in a slightly more convenient way. First, we have to note that since G is finite, there is some n \in \mathbb N so that g^n=1 \in G. Since \chi:G \to \mathbb C^{\times} is a group homomorphism, we also have that \chi(g^n)=\chi(g)^n=1 for some n for each g \in G, we know that \chi is actually unitary, in the sense that \overline{\chi}(g)=\chi^{-1}(g), and \chi:G \to S^1 \subset \mathbb C, which is an easier way to compute the “fourier coefficients.”

 

Moreover, the characters of finite abelian groups are not too difficult to compute, by the classification of finite abelian groups:

First, suppose that G=\mathbb Z_m is finite cyclic. Then we can construct exactly m characters, by letting \omega be a primitive m^{th} root of unity, and letting g \mapsto \omega^g be an assignment of roots of unity to each group element. We then define \chi_g(h):=\omega^gh. Since there are exactly n characters here, it will suffice to check that each has norm 1 under the inner product, which is an easy verification. Similarly, \langle \chi_g,\chi_j\rangle=0 whenever g \neq j, since the inner product is just

    \[\frac{1}{m}\sum_{h \in \mathbb Z_m} \omega^{gh} \omega^{-jh},\]

but this is a sum over roots of unity, but it is also well known that this is zero, so these are orthogonal one dimensional representations. Note further that \mathbb Z_m \cong H^1(\mathbb Z_m). Furthermore, we can check that a homomorphism f:G \oplus H \to S^1 splits over direct sum by the universal property of (co)products. Hence, by the structure theorem for finite abelian groups, we have that G \cong \mathbb Z_{p_1^{e_1}} \oplus \dots \oplus \mathbb Z_{p_n^{k_n}}, so we can define \chi_\epsilon (g_1, \dots g_n)= \prod_{j=1}^{n}\chi_{\epsilon_j}(g_i), with \epsilon_j the standard basis.

 

 

So, we in fact have an orthonormal basis for the space of functions H^1(G)!