= Solution
Put $e_N(t)=e^{2\pi it/N}$ and use normalized averages $\mathbb E_x=N^{-1}\sum_{x\in\mathbb Z/N\mathbb Z}$. Our convention for <Fourier coefficients on a finite abelian group> is
$$
\boxed{\widehat f(r)=\mathbb E_xf(x)e_N(-rx),\qquad r\in\mathbb Z/N\mathbb Z.}
$$
The underlying <orthogonality of complex exponentials> is $\mathbb E_xe_N(rx)=1$ for $r=0$ and zero otherwise. For nonzero $r$ this is the finite <geometric series> with ratio $e_N(r)\ne1$; its sum vanishes because that ratio has $N$th power one. The identical orthogonality statement holds when averaging over $r$ instead of $x$.
Using this orthogonality to sum the definition over $r$ proves <Fourier inversion on a finite group>:
$$
\sum_r\widehat f(r)e_N(rx)
=\mathbb E_yf(y)\sum_re_N(r(x-y))=f(x).
$$
Indeed $\mathbb E f\overline g=\sum_r\overline{\widehat g(r)}\mathbb E_x f(x)e_N(-rx)=\sum_r\widehat f(r)\overline{\widehat g(r)}$. This proves the <Parseval identity on a finite group> and its squared-norm case:
$$
\mathbb E_xf(x)\overline{g(x)}=\sum_r\widehat f(r)\overline{\widehat g(r)},\qquad
\sum_r|\widehat f(r)|^2=\mathbb E_x|f(x)|^2.
$$
For <normalized convolution on a finite group>, write $(f*g)(x)=\mathbb E_yf(y)g(x-y)$. Changing variables $x=y+z$ in its transform gives
$$
\widehat{f*g}(r)
=\mathbb E_{y,z}f(y)g(z)e_N(-r(y+z))
=\widehat f(r)\widehat g(r),
$$
the <convolution theorem on a finite group>. <Linearity> of the transform follows directly from its definition. <Translation> $\tau_tf(x)=f(x+t)$ gives $\widehat{\tau_tf}(r)=e_N(rt)\widehat f(r)$ by changing variables. <Complex conjugation> gives $\widehat{\overline f}(r)=\overline{\widehat f(-r)}$; for $\widetilde f(x)=\overline{f(-x)}$, the corresponding identity is $\widehat{\widetilde f}(r)=\overline{\widehat f(r)}$. Finally $\widehat f(0)=\mathbb E f$ and $|\widehat f(r)|\leq\mathbb E|f|$ by the <triangle inequality>. These identities establish the basic <normalized Fourier analysis on a finite abelian group> needed below, with all normalizations fixed.
For completeness, pointwise multiplication has the dual convolution formula $\widehat{fg}(r)=\sum_s\widehat f(s)\widehat g(r-s)$: insert the inversion formula for $g$ into the defining average and collect its frequencies. If $c\ne0$ modulo $N$, the change of variables $u=cx$ gives $\widehat{f(c\,\cdot)}(r)=\widehat f(rc^{-1})$. These also follow directly from the same <additive character> orthogonality.
Back to article page
