The Lumenary · First-year graduate

Fourier and harmonic analysis

Name: ______________________

Date: ______________________

You will learn to

Define Fourier coefficients, the Fourier transform and convolution, and use convolution with approximate identities to prove Fejér's theorem
Prove Parseval's identity on the circle and the inversion and Plancherel theorems for the Fourier transform on $\R$
Compute Fourier transforms, including that of the Gaussian, and prove and apply the Poisson summation formula
State and prove the Heisenberg uncertainty inequality
Describe honestly what is known about pointwise convergence (Dirichlet, du Bois-Reymond, Kolmogorov, Carleson) and explain the Gibbs phenomenon
Recognise characters and Pontryagin duality as the common frame of Fourier series, transforms and finite Fourier analysis

1.
Let $f(x) = 3 + 4\cos(2x) - 2\sin(5x)$ on $\mathbb T$ . Compute $\displaystyle \sum_{n \in \Z} |\hat f(n)|^2$ , with $\hat f(n) = \frac{1}{2\pi}\int_{-\pi}^{\pi} f(x) e^{-inx}\,dx$ .
2.
Which property of an approximate identity does the Dirichlet kernel $D_N$ fail, and why does that matter?
- A. $\frac{1}{2\pi}\int |D_N|$ is not bounded in $N$ , so the argument that $f * K_N \to f$ breaks down, and indeed $S_N f$ can diverge for continuous $f$ .
- B. $\frac{1}{2\pi}\int D_N \ne 1$ .
- C. $D_N$ is not continuous.
- D.None: $D_N$ is an approximate identity, so $S_N f \to f$ uniformly for every continuous $f$ .
3.
For the square wave $f = \operatorname{sign}(\sin x)$ , what happens to $\max_x S_N f(x)$ as $N \to \infty$ ?
- A.It tends to $1 = \sup f$ .
- B.It tends to $\frac{2}{\pi}\operatorname{Si}(\pi) \approx 1.179$ .
- C.It tends to infinity, like $\log N$ .
- D.It oscillates without a limit.
4.
The function $f(x) = e^{-2\pi|x|}$ has Fourier transform $\hat f(\xi) = \dfrac{1}{\pi(1 + \xi^2)}$ , and Poisson summation holds for it. What is $\displaystyle\sum_{k \in \Z} \frac{1}{1 + k^2}$ ?
- A. $\pi \coth \pi$
- B. $\pi$
- C. $\pi^2/6$
- D. $2$
5.
In the proof of the Heisenberg inequality we reach $\int|f|^2 \le 2\left(\int x^2|f|^2\right)^{1/2}\left(\int|f'|^2\right)^{1/2}$ . Which result converts $\int |f'|^2$ into a statement about $\hat f$ ?
- A.Plancherel's theorem together with $\widehat{f'}(\xi) = 2\pi i\xi\hat f(\xi)$ .
- B.The Poisson summation formula.
- C.The Riemann–Lebesgue lemma.
- D.Fejér's theorem.
6.
Which Lean statement correctly expresses the orthogonality of the characters of $\Z/N$ as "the sum of the powers of a non-trivial $N$ -th root of unity is $0$ "?
- A.theorem t {z : ℂ} {N : ℕ} (hz : z ^ N = 1) (hz1 : z ≠ 1) : ∑ k ∈ Finset.range N, z ^ k = 0
- B.theorem t {z : ℂ} {N : ℕ} (hz : z ^ N = 1) : ∑ k ∈ Finset.range N, z ^ k = 0
- C.theorem t {z : ℂ} {N : ℕ} (hz1 : z ≠ 1) : ∑ k ∈ Finset.range N, z ^ k = 0
- D.theorem t {z : ℂ} {N : ℕ} (hz : z ^ N = 1) (hz1 : z ≠ 1) : ∑ k ∈ Finset.range N, z ^ k = 1
7.
Let $f \in L^1(\R)$ . Which statements are always true? Select all that apply.
- A. $\hat f$ is bounded, with $|\hat f(\xi)| \le \|f\|_1$ .
- B. $\hat f$ is continuous and tends to $0$ at $\pm\infty$ .
- C. $\hat f \in L^1(\R)$ .
- D. $\hat f$ has compact support whenever $f$ does.
8.
Write dft(a) returning the discrete Fourier transform $A_k = \sum_{j=0}^{N-1} a_j e^{-2\pi i jk/N}$ , $k = 0, \dots, N-1$ , of a list a of $N$ numbers (use cmath). The tests check Parseval's identity for $\Z/N$ : $\sum_k |A_k|^2 = N\sum_j |a_j|^2$ .
Computational — Practice

Answer key — Fourier and harmonic analysis

1.
$f = 3 + 2e^{2ix} + 2e^{-2ix} + i e^{5ix} - i e^{-5ix}$ , so $\hat f(0) = 3$ , $\hat f(\pm 2) = 2$ , $|\hat f(\pm 5)| = 1$ , and $\sum |\hat f(n)|^2 = 9 + 4 + 4 + 1 + 1 = 19$ . Check with Parseval: $\frac{1}{2\pi}\int |f|^2 = 3^2 + \frac{4^2}{2} + \frac{2^2}{2} = 9 + 8 + 2 = 19$ (the cross terms integrate to $0$ by orthogonality).
2.
$D_N$ has integral $1$ (property 1), but it oscillates in sign and $\frac{1}{2\pi}\int |D_N| \sim \frac{4}{\pi^2}\log N \to \infty$ , so property 2 fails. (Property 3 fails too: $\int_{\delta \le |x| \le \pi}|D_N|$ also grows like $\log N$ .) The proof of uniform convergence therefore does not apply, and in fact the uniform boundedness principle shows that some continuous $f$ has $\sup_N |S_N f(0)| = \infty$ . The Fejér kernel is non-negative, so property 2 follows from property 1.
3.
With $t_j = (2j - 1)\pi/(2M)$ , $S_{2M-1} f(\pi/2M) = \frac2\pi\sum_{j=1}^M \frac\pi M \frac{\sin t_j}{t_j} \to \frac2\pi\operatorname{Si}(\pi) = 1.17898\ldots$ (one checks this point is where the maximum occurs). So the partial sums overshoot $1$ by about $0.179$ , i.e. $8.95\%$ of the jump $2$ , however large $N$ is. Convergence is pointwise but not uniform near $0$ .
4.
$\sum_n e^{-2\pi|n|} = 1 + 2\sum_{n \ge 1} e^{-2\pi n} = \frac{1 + e^{-2\pi}}{1 - e^{-2\pi}} = \coth \pi$ . Poisson summation gives $\frac1\pi\sum_k \frac{1}{1+k^2} = \coth\pi$ , so $\sum_{k \in \Z}\frac{1}{1+k^2} = \pi\coth\pi \approx 3.1533$ , slightly more than $\int \frac{dx}{1+x^2} = \pi$ . ( $f$ is not Schwartz, but it is continuous with $f$ and $\hat f$ decaying like $|x|^{-2}$ or faster, which suffices.)
5.
Since $\widehat{f'}(\xi) = 2\pi i\xi\hat f(\xi)$ (integrate by parts), Plancherel gives $\int|f'|^2 = 4\pi^2\int\xi^2|\hat f|^2$ . Substituting and squaring: $\left(\int|f|^2\right)^2 \le 16\pi^2\left(\int x^2|f|^2\right)\left(\int\xi^2|\hat f|^2\right)$ , which is the uncertainty inequality.
6.
Option (a). Both hypotheses are needed: without $z \ne 1$ the sum can be $N$ , and without $z^N = 1$ it is $(z^N - 1)/(z - 1)$ , usually non-zero. The proof: $\left(\sum_{k<N} z^k\right)(z - 1) = z^N - 1 = 0$ and $z - 1 \ne 0$ . With $z = e^{2\pi i(m - n)/N}$ it says $\sum_{k} e^{2\pi i mk/N}\overline{e^{2\pi i nk/N}} = N\delta_{mn}$ for $0 \le m, n < N$ .
7.
(a) and (b) are true; (c) and (d) are false. The indicator $\mathbf 1_{[-1/2,1/2]}$ is a counterexample to both: its transform $\frac{\sin\pi\xi}{\pi\xi}$ is not integrable and not compactly supported. In general, if $f \ne 0$ has compact support then $\hat f(\zeta) = \int f(x)e^{-2\pi ix\zeta}dx$ is entire in $\zeta \in \C$ , so its real zeros are isolated.
8.
```
import cmath

def dft(a):
    n = len(a)
    return [sum(a[m] * cmath.exp(-2j * cmath.pi * m * k / n) for m in range(n))
            for k in range(n)]
```
This costs $N^2$ operations; the FFT does it in $O(N \log N)$ . The tests are the finite Fourier theory of the lesson: the transform of a delta is constant, the transform of a constant is concentrated at $k = 0$ (orthogonality of characters, $\sum_m e^{-2\pi imk/N} = 0$ for $k \ne 0$ ), and Parseval holds with the factor $N$ coming from this unnormalised convention.