# Pontryagin Duality and the Fourier Transform

Jordan Bell

## 1 Introduction

We follow Rudin [3] and Terras [4], and refer to sp4comm [2] and Folland [1].

## 2 $\mathbb{Z}/n\mathbb{Z}$

Let $n$ be a positive integer.

 $\mathbb{Z}/n\mathbb{Z}=\{k+n\mathbb{Z}:k\in\mathbb{Z}\}=\{k+n\mathbb{Z}:0\leq k% \leq n-1\}$

$Z_{n}=\mathbb{Z}/n\mathbb{Z}$ is a ring. $|Z_{n}|=n$. We focus on the additive group $(Z_{n},+)$.

## 3 Haar measure

Let

 $\mathbb{C}^{Z_{n}}$

be the set of functions $Z_{n}\to\mathbb{C}$.

We use counting measure on the group $Z_{n}$ as Haar measure (which is discrete and compact) with total volume $n$, and Since $Z_{n}$ has finite Haar measure (being a compact group) and every function $Z_{n}\to\mathbb{C}$ is continuous (being a discrete group), we have

 $\mathbb{C}^{Z_{n}}=L^{1}(Z_{n})=L^{2}(Z_{n}).$

We specify function space for emphasis.

For $f,g\in L^{2}(Z_{n})$, define

 $(f,g)_{L^{2}(Z_{n})}=\sum_{x\in Z_{n}}f(x)\overline{g(x)}$

Define

 $|f|_{L^{2}(Z_{n})}=\sqrt{(f,f)_{L^{2}(Z_{n})}}=\sqrt{\sum_{x\in Z_{n}}f(x)% \overline{f(x)}}.$

Define

 $|f|_{L^{1}(Z_{n})}=\sum_{x\in Z_{n}}|f(x)|.$

## 4 $\delta_{a}$

For $a\in Z_{n}$, define $\delta_{a}:Z_{n}\to\mathbb{C}$ by

 $\delta_{a}(x)=\begin{cases}1&x=a\\ 0&x\neq a\end{cases}$

For $a,b\in Z_{n}$,

 $\displaystyle(\delta_{a},\delta_{b})_{L^{2}(Z_{n})}$ $\displaystyle=\sum_{x\in Z_{n}}\delta_{a}(x)\overline{\delta_{b}(x)}$ $\displaystyle=\sum_{x\in Z_{n}}\delta_{a}(x)\delta_{b}(x)$ \displaystyle=\begin{cases}\hidden@noalign{}\textstyle 1&a=b\\ \hidden@noalign{}\textstyle 0&a\neq b\end{cases}

For $f\in L^{2}(Z_{n})$,

 $f(x)=\sum_{a\in Z_{n}}f(a)\delta_{a}(x)=\sum_{a=0}^{n-1}f(a)\delta_{a}(x),% \qquad x\in Z_{n}.$

Indeed, $\{\delta_{0},\ldots,\delta_{n-1}\}$ is an orthonormal basis of $L^{2}(Z_{n})$.

## 5 Convolution

For $f,g\in L^{1}(Z_{n})$, define the convolution $f*g\in L^{1}(Z_{n})$ by

 $(f*g)(x)=\sum_{y\in Z_{n}}f(y)g(x-y),\qquad x\in Z_{n}.$
 $f*g=g*f,\qquad f,g\in L^{1}(Z_{n}).$
 $f*(g*h)=(f*g)*h,\qquad f,g,h\in L^{1}(Z_{n}).$

For $f\in L^{1}(Z_{n})$ and for $a\in Z_{n}$,

 $(f*\delta_{a})(x)=f(x-a),\qquad x\in Z_{n}.$

For $a,b\in Z_{n}$, and for $x\in Z_{n}$,

 $(\delta_{a}*\delta_{b})(x)=\delta_{a}(x-b)=\delta_{a+b}(x).$

### 5.1 Example

Take $n=15$. Define $f=\delta_{0}+\delta_{1}+\delta_{2}$. For $x\in Z_{15}$,

 $\displaystyle(f*f)(x)$ $\displaystyle=(\delta_{0}+\delta_{1}+\delta_{2})*(\delta_{0}+\delta_{1}+\delta% _{2})$ $\displaystyle=\delta_{0}*\delta_{0}+\delta_{1}*\delta_{1}+\delta_{2}*\delta_{2}$ $\displaystyle+2\delta_{0}*\delta_{1}+2\delta_{0}*\delta_{2}+2\delta_{1}*\delta% _{2}$ $\displaystyle=\delta_{0}+\delta_{2}+\delta_{4}$ $\displaystyle+2\delta_{1}+2\delta_{2}+2\delta_{3}$ $\displaystyle=\delta_{0}+2\delta_{1}+3\delta_{2}+2\delta_{3}+\delta_{4}$

## 6 Dual group

Let $S^{1}=\{z\in\mathbb{C}:|z|=1\}$, which is a multiplicative group.

Let $\widehat{Z_{n}}$ be the set of group homomorphisms $Z_{n}\to S^{1}$.

We use normalized counting measure on the group $\widehat{Z_{n}}$ as Haar measure (which is discrete and compact) with total volume 1.

For $a\in Z_{n}$, define $e_{a}:Z_{n}\to S^{1}$ by

 $e_{a}(x)=\exp\left(2\pi i\dfrac{ax}{n}\right),\qquad x\in Z_{n}.$

$e_{a}$ is an element of $\widehat{Z_{n}}$.

Define $\psi:Z_{n}\to\widehat{Z_{n}}$ by $\psi(a)=e_{a}$.

 $\displaystyle\widehat{Z_{n}}$ $\displaystyle=\{e_{a}:a\in Z_{n}\}$ $\displaystyle=\{\psi(a):a\in Z_{n}\}$ $\displaystyle=\psi(Z_{n})$

$\psi:Z_{n}\to\widehat{Z_{n}}$ is an isomorphism of groups.

## 7 Fourier transform

Define the Fourier transform $\mathscr{F}_{n}:L^{2}(Z_{n})\to L^{2}(\widehat{Z_{n})}$ by

 $(\mathscr{F}_{n}f)(e_{a})=\sum_{x\in Z_{n}}f(x)e_{a}(-x),\qquad e_{a}\in% \widehat{Z_{n}}.$

## 8 Pullback

We introduce the operator $F_{n}:L^{2}(Z_{n})\to L^{2}(Z_{n})$, which is defined via composition with the Fourier transform $\mathscr{F}_{n}$ and the function $\psi$ as

 $F_{n}f=(\mathscr{F}_{n}f)\circ\psi.$

We pullback $\mathscr{F}_{n}f:\widehat{Z_{n}}\to\mathbb{C}$ to a function $Z_{n}\to\mathbb{C}$.

We remind ourselves (a) that for $a\in Z_{n}$, the function $e_{a}:Z_{n}\to S^{1}$ is defined by

 $e_{a}(x)=\exp\left(2\pi i\dfrac{ax}{n}\right),\qquad x\in Z_{n},$

(b) that $\psi:Z_{n}\to\widehat{Z_{n}}$ is defined by $\psi(a)=e_{a}$,

and (c) that $\psi:Z_{n}\to\widehat{Z_{n}}$ is an isomorphism of groups, by

 $\displaystyle\widehat{Z_{n}}$ $\displaystyle=\{e_{a}:a\in Z_{n}\}$ $\displaystyle=\{\psi(a):a\in Z_{n}\}$ $\displaystyle=\psi(Z_{n})$
 $\displaystyle(\mathscr{F}_{n}f)(\psi(a))$ $\displaystyle=\sum_{x\in Z_{n}}f(x)e_{a}(-x)$ $\displaystyle=\sum_{x\in Z_{n}}f(x)\overline{e_{a}(x)}$ $\displaystyle=(f,e_{a})_{L^{2}(Z_{n})}$

Thus

 $(F_{n}f)(x)=(f,e_{x})_{L^{2}(Z_{n})},\qquad x\in Z_{n}.$

In the sequel, we use the term Fourier transform to refer both to $\mathscr{F}_{n}$ and to $F_{n}$, but preserve the distinction for calculations.

### 8.1 Example: $n=7$ and $f=\delta_{3}$

By

 $(F_{n}f)(x)=(f,e_{x})_{L^{2}(Z_{n})},\qquad x\in Z_{n}$

we have

 $(F_{7}\delta_{3})(x)=(\delta_{3},e_{x})_{L^{2}(Z_{7})},\qquad x\in Z_{7}.$

The inner product $(\delta_{3},e_{x})_{L^{2}(Z_{7})}$ is given by

 $\displaystyle(\delta_{3},e_{x})_{L^{2}(Z_{7})}$ $\displaystyle=\sum_{y\in Z_{7}}\delta_{3}(y)\overline{e_{x}(y)}$ $\displaystyle=\sum_{y=0}^{6}\delta_{3}(y)\overline{\exp\left(2\pi i\frac{xy}{7% }\right)}.$

Since $\delta_{3}(y)=1$ only when $y=3$ and $0$ otherwise, the sum collapses to a single term:

 $\displaystyle(\delta_{3},e_{x})_{L^{2}(Z_{7})}$ $\displaystyle=\overline{\exp\left(2\pi i\frac{3x}{7}\right)}$ $\displaystyle=\exp\left(-2\pi i\frac{3x}{7}\right)$ $\displaystyle=e_{-3}(x)$

Thus,

 $(F_{7}\delta_{3})(x)=e_{-3}(x),\qquad x\in Z_{7},$

namely,

 $F_{7}\delta_{3}=e_{-3}.$

## 9 $\widehat{Z_{n}}$

$\widehat{Z_{n}}$ is the set of group homomorphisms $Z_{n}\to S^{1}$.

$\widehat{Z_{n}}$ is a group using pointwise multiplication of functions $Z_{n}\to S^{1}$, the Pontryagin dual group of $Z_{n}$.

For $a\in Z_{n}$, define $e_{a}\in\widehat{Z_{n}}$ by

 $e_{a}(x)=\exp\left(2\pi i\dfrac{ax}{n}\right),\qquad x\in Z_{n},$

Define $\psi:Z_{n}\to\widehat{Z_{n}}$ by

 $\psi(a)=e_{a},\qquad a\in Z_{n}.$

We have

 $\displaystyle\widehat{Z_{n}}$ $\displaystyle=\{e_{a}:a\in Z_{n}\}$ $\displaystyle=\{\psi(a):a\in Z_{n}\}$ $\displaystyle=\psi(Z_{n})$

Thus, $\psi:Z_{n}\to\widehat{Z_{n}}$ is an isomorphism of groups.

## 10 Haar measure

Let $G$ be a locally compact abelian group.

$\widehat{G}$ is the set of continuous group homomorphisms $G\to S^{1}$. It is a group with operation $(\phi_{1}\phi_{2})(x)=\phi_{1}(x)\phi_{2}(x)$, $\phi_{1},\phi_{2}\in\widehat{G}$, $x\in G$ (namely, pointwise multiplication).

We assign $\widehat{G}$ the coarsest topology such that for each $x\in G$, the map $\phi\mapsto\phi(x)$ is continuous $\widehat{G}\to S^{1}$ (namely, the final topology on $\widehat{G}$).

One proves that $\widehat{G}$ is a locally compact abelian group.

If $G$ is a discrete LCA group, then $\widehat{G}$ is a compact LCA group.

### 10.1 Finite LCA groups

Let $G$ be a finite locally compact abelian group. $G$ must have the discrete topology. Hence the Borel $\sigma$-algebra of $G$ is equal to the power set of $G$, denoted $\mathscr{P}(G)$.

Because $G$ has the discrete topology, $\widehat{G}$ is equal to the set of group homomorphisms $G\to S^{1}$.

Assign $G$ the Haar measure $m_{G}$ defined by $m_{G}(A)=|A|$ for $A\in\mathscr{P}(G)$. One checks that $m_{G}$ indeed is a Haar measure. (Counting measure.)

Assign $\widehat{G}$ the Haar measure $m_{\widehat{G}}$ defined by $m_{\widehat{G}}(A)=\frac{1}{|\widehat{G}|}\cdot|A|$ for $A\in\mathscr{P}(\widehat{G})$. (Normalized counting measure.)

$L^{2}(G)$ is equal to the set of functions $G\to\mathbb{C}$ and $L^{2}(\widehat{G})$ is equal to the set of functions $\widehat{G}\to\mathbb{C}$.

## 11 $L^{2}(Z_{n})$

For $f,g\in L^{2}(Z_{n})$, define

 $(f,g)_{L^{2}(Z_{n})}=\sum_{x\in Z_{n}}f(x)\overline{g(x)}$

Define

 $|f|_{L^{2}(Z_{n})}=\sqrt{(f,f)_{L^{2}(Z_{n})}}=\sqrt{\sum_{x\in Z_{n}}f(x)% \overline{f(x)}}.$

For $a\in Z_{n}$, define $\delta_{a}:Z_{n}\to\mathbb{C}$ by

 $\delta_{a}(x)=\begin{cases}1&x=a\\ 0&x\neq a\end{cases}$

For $a,b\in Z_{n}$,

 $\displaystyle(\delta_{a},\delta_{b})_{L^{2}(Z_{n})}$ $\displaystyle=\sum_{x\in Z_{n}}\delta_{a}(x)\overline{\delta_{b}(x)}$ $\displaystyle=\sum_{x\in Z_{n}}\delta_{a}(x)\delta_{b}(x)$ \displaystyle=\begin{cases}\hidden@noalign{}\textstyle 1&a=b\\ \hidden@noalign{}\textstyle 0&a\neq b\end{cases}

For $f\in L^{2}(Z_{n})$,

 $f(x)=\sum_{a\in Z_{n}}f(a)\delta_{a}(x)=\sum_{a=0}^{n-1}f(a)\delta_{a}(x),% \qquad x\in Z_{n}.$

## 12 Fourier transform

Define the Fourier transform $\mathscr{F}_{n}:L^{2}(Z_{n})\to L^{2}(\widehat{Z_{n})}$ by

 $(\mathscr{F}_{n}f)(e_{a})=\sum_{x\in Z_{n}}f(x)\overline{e_{a}(x)}=\sum_{x\in Z% _{n}}f(x)e_{a}(-x),\qquad e_{a}\in\widehat{Z_{n}}.$

## 13 Pullback

We introduce the operator $F_{n}:L^{2}(Z_{n})\to L^{2}(Z_{n})$, which is defined via composition with the Fourier transform $\mathscr{F}_{n}$ and the function $\psi$ as

 $F_{n}f=(\mathscr{F}_{n}f)\circ\psi.$

That is, for $a\in Z_{n}$,

 $(F_{n}f)(a)=(\mathscr{F}_{n}f)(e_{a}).$

We pullback $\mathscr{F}_{n}f:\widehat{Z_{n}}\to\mathbb{C}$ to a function $F_{n}f:Z_{n}\to\mathbb{C}$.

We have

 $\displaystyle(\mathscr{F}_{n}f)(\psi(a))$ $\displaystyle=\sum_{x\in Z_{n}}f(x)e_{a}(-x)$ $\displaystyle=\sum_{x\in Z_{n}}f(x)\overline{e_{a}(x)}$ $\displaystyle=(f,e_{a})_{L^{2}(Z_{n})}$

Thus

 $(F_{n}f)(x)=(f,e_{x})_{L^{2}(Z_{n})},\qquad x\in Z_{n}.$

## 14 Inverse Fourier transform

Define the Haar measure $m_{\widehat{Z_{n}}}$ on $\widehat{Z_{n}}$ by $m_{\widehat{Z_{n}}}(A)=\frac{1}{n}\cdot|A|$ for $A\in\mathscr{P}(\widehat{Z_{n}})$.

Let $f\in L^{2}(Z_{n})$ and let $x\in Z_{n}$.

 $\displaystyle\int_{\widehat{Z_{n}}}(\mathscr{F}_{n}f)(\gamma)\gamma(x)dm_{% \widehat{Z_{n}}}(\gamma)$ $\displaystyle=\frac{1}{n}\sum_{\gamma\in\widehat{Z_{n}}}(\mathscr{F}_{n}f)(% \gamma)\gamma(x)$ $\displaystyle=\frac{1}{n}\sum_{a\in Z_{n}}(\mathscr{F}_{n}f)(e_{a})e_{a}(x)$ $\displaystyle=\frac{1}{n}\sum_{a\in Z_{n}}\left(\sum_{y\in Z_{n}}f(y)\overline% {e_{a}(y)}\right)e_{a}(x)$ $\displaystyle=\frac{1}{n}\sum_{a\in Z_{n}}\sum_{y\in Z_{n}}f(y)\overline{e_{a}% (y)}e_{a}(x)$ $\displaystyle=\frac{1}{n}\sum_{y\in Z_{n}}f(y)\left(\sum_{a\in Z_{n}}e_{a}(x)% \overline{e_{a}(y)}\right)$

We use the orthogonality relations for characters of finite abelian groups. For $a,b\in Z_{n}$ we have $e_{a},e_{b}\in\widehat{Z_{n}}$, and

 $\sum_{x\in Z_{n}}e_{a}(x)\overline{e_{b}(x)}=n\delta_{a,b}.$

Then, as $e_{a}(x)=e_{x}(a)$ and $e_{a}(y)=e_{y}(a)$,

 $\displaystyle\frac{1}{n}\sum_{y\in Z_{n}}f(y)\left(\sum_{a\in Z_{n}}e_{a}(x)% \overline{e_{a}(y)}\right)$ $\displaystyle=\frac{1}{n}\sum_{y\in Z_{n}}f(y)\left(\sum_{a\in Z_{n}}e_{x}(a)% \overline{e_{y}(a)}\right)$ $\displaystyle=\frac{1}{n}\sum_{y\in Z_{n}}f(y)\cdot n\delta_{x,y}$ $\displaystyle=\sum_{y\in Z_{n}}f(y)\delta_{x,y}$ $\displaystyle=\sum_{y\in Z_{n}}f(y)\delta_{x}(y)$ $\displaystyle=f(x).$

We have established that for $f\in L^{2}(Z_{n})$ and for $x\in Z_{n}$,

 $\int_{\widehat{Z_{n}}}(\mathscr{F}_{n}f)(\gamma)\gamma(x)dm_{\widehat{Z_{n}}}(% \gamma)=\frac{1}{n}\sum_{a\in Z_{n}}(\mathscr{F}_{n}f)(e_{a})e_{a}(x)=f(x).$

Also,

 $\frac{1}{n}\sum_{a\in Z_{n}}(F_{n}f)(a)e_{a}(x)=\frac{1}{n}\sum_{a\in Z_{n}}(% \mathscr{F}_{n}f)(e_{a})e_{a}(x)=f(x).$

We have established the Fourier inversion formula for $f\in L^{2}(Z_{n})$:

 $f(x)=\frac{1}{n}\sum_{a\in Z_{n}}(F_{n}f)(a)e_{a}(x),\qquad x\in Z_{n}.$

## 15 $\ell^{1}(\mathbb{Z})$

Let $\mathbb{C}^{\mathbb{Z}}$ be the set of functions $\mathbb{Z}\to\mathbb{C}$.

Let $x\in\ell^{1}(\mathbb{Z})$ be the set of those $x\in\mathbb{C}^{\mathbb{Z}}$ such that

 $\sum_{n\in\mathbb{Z}}|x[n]|<\infty$

and define

 $|x|_{\ell^{1}(\mathbb{Z})}=\sum_{n\in\mathbb{Z}}|x[n]|.$

Let $\ell^{2}(\mathbb{Z})$ be the set of those $x\in\mathbb{C}^{\mathbb{Z}}$ such that

 $\sum_{n\in\mathbb{Z}}|x[n]|^{2}<\infty.$

## 16 $\ell^{2}(\mathbb{Z})$

For $x\in\ell^{2}(\mathbb{Z})$, define

 $|x|_{\ell^{2}(\mathbb{Z})}=\sqrt{\sum_{n\in\mathbb{Z}}|x[n]|^{2}},$

and for $x,y\in\ell^{2}(\mathbb{Z})$, define

 $(x,y)_{\ell^{2}(\mathbb{Z})}=\sum_{n\in\mathbb{Z}}x[n]\overline{y[n]}.$

For $k\in\mathbb{Z}$, define $T_{k}:\mathbb{C}^{\mathbb{Z}}\to\mathbb{C}^{\mathbb{Z}}$ by

 $(T_{k}x)[n]=x[n-k],\qquad n\in\mathbb{Z}.$

## References

• [1] G. B. Folland (2015) A course in abstract harmonic analysis. 2nd updated edition edition, Textbooks in Mathematics, CRC Press, Boca Raton, FL (English). External Links: ISBN 978-1-4987-2713-6; 978-1-4987-2715-0, Document Cited by: §1.
• [2] P. Prandoni and M. Vetterli (2008) Signal processing for communications. EPFL Press. Cited by: §1.
• [3] W. Rudin (1962) Fourier analysis on groups. Interscience Tracts in Pure and Applied Mathematics, Interscience Publishers, New York (English). Cited by: §1.
• [4] A. Terras (1999) Fourier analysis on finite groups and applications. London Mathematical Society Student Texts, Vol. 43, Cambridge University Press, Cambridge (English). External Links: ISSN 0963-1631, ISBN 0-521-45718-1; 0-521-45108-6 Cited by: §1.