Category Archives: Fourier analysis

Exponential sum and the equidistribution theorem

Consider the sequence x \text{ mod } 1, 2x \text{ mod } 1, 3x \text{ mod } 1,\ldots, where \text{mod } 1 gives the fractional part of a real number. The equidistribution theorem states that x is irrational iff for any sub-interval [a, b) of the unit interval, for sufficiently large N, roughly (b-a)N of the numbers x\text{ mod } 1, \ldots, Nx\text{ mod } 1 fall inside [a, b). More precisely,

(Equidistributed sequence) A sequence \{x_n\}_{n=1}^{\infty} with x_n \in \mathbb{R} is equidistributed mod 1 if for every 0 \leq a \leq b \leq 1,

    \[ \lim_{N \rightarrow \infty} \frac{\left|\{x_n : a \leq x_n \text{ mod } 1 < b \} \right|}{N}  = b - a. \]

(Equidistribution theorem) The sequence \{nx\}_{n=1}^{\infty} is equidistributed mod 1 iff x is irrational.

Let us try to understand why the sequence behaves differently depending on whether x is rational or not. If x = p/q for some integers p and q, then roughly N/q of the first N multiples of x are integers, i.e., 0 \text{ mod } 1. In fact, it is not difficult to see that for i \in \{0, 1, \ldots, q-1\}, 1/q fraction of the sequence equals i/q \text{ mod } 1. So equidistribution does not occur when x is rational.

Now for k\neq 0 \in \mathbb{Z}, consider the exponential function e_k(x):=e^{2\pi i k x}, which has period 1. As discussed above, roughly 1/q of the sequence \{e_k(nx)\}_{n=1}^{\infty} is 1, so the exponential sum \sum_{n=1}^{\infty} e_k(nx) contains an infinite number of ones. For example if q=2, the exponential sum evaluates to -1 + 1 - 1 + 1 - \ldots, which is Grandi’s series and diverges. For an arbitrary q > 1, the exponential sum is a repeating sum of all q-th roots of unity, and one can use the same technique showing that Grandi’s series diverges to establish that this exponential sum diverges too. However, the case when x is irrational differs: every nonzero integer multiple of x is an non-integer, and thus e_k(nx)\neq 1 for any n\neq 0. Writing r=e^{2\pi i x}, the exponential sum \sum_{n=1}^{\infty} e_k(nx) converges to the geometric series \sum_{n=1}^{\infty} r^n = \frac{r}{r-1}, since r\neq1.

In fact, the above intuition can be summarized into the following criterion due to Weyl:

(Weyl’s criterion) A sequence \{x_n\}_{n=1}^{\infty} is equidistributed mod 1 iff for all integers k\neq 0,

    \[ \lim_{N\rightarrow \infty} \frac{1}{N} \sum_{n=1}^N e^{2\pi i kx_n} = 0. \]

From the above discussion, Weyl’s criterion immediately implies the equidistribution theorem.

(of equidistribution theorem)
Suppose x is rational, i.e., x=p/q for some integers p and q. Without loss of generality, we assume q > 1. Then for all integer n, by Euclid’s algorithm, nx \text{ mod } 1 is in \{0, 1/q, \ldots, (q-i)/q\}. So the sequence \{nx\}_{n=1}^{\infty} is not equidistributed, e.g., no multiples of x fall inside [1/4q, 1/2q).

Now suppose x is irrational. Since r:= e^{2\pi i kx}\neq 1, we have

    \[ \frac{1}{N} \sum_{n=1}^N e^{2\pi i kx_n} = \frac{1}{N} \frac{r^{N+1} - 1}{r - 1}, \]

which tends to 0 as N \rightarrow \infty.

Before proving Weyl’s criterion, it is instructive to state the notion of equidistribution analytically. For 0\leq a \leq b \leq 1, let \chi_{[a,b)}(x)=1 iff x \text{ mod } 1 \in [a, b). Note that \chi_{[a,b)} is a periodic function on all of \mathbb{R}.

(Weyl’s criterion restated) Let \{x_n\}_{n=1}^{\infty} be a sequence in \mathbb{R}. The following two statements are equivalent:
1) For 0\leq a < b \leq 1,

    \[ \lim_{N\rightarrow \infty} \frac{1}{N} \sum_{n=1}^N \chi_{[a, b)}(x_n) = \int_0^1 \chi_{[a, b)}. \]

2) For all integers k\neq 0,

    \[ \lim_{N\rightarrow \infty} \frac{1}{N} \sum_{n=1}^N e^{2\pi i kx_n} = \int_0^1 e^{2\pi i k}. \]

Written in this form, Weyl’s criterion is asserting that if the sum of every interval function at a sequence converges to its integral, then every exponential sum converges to its integral as well, and vice versa. The reason is that both the space of interval functions and the space of exponential functions can approximate one another. More precisely, an exponential function is clearly periodic and continuous (and thus uniformly continuous), and every uniformly continuous function can be approximated by a finite sum of interval functions. For the other direction, a periodic, interval function can be approximated by a periodic, continuous function, which by Fejér’s Theorem can also be approximated by a finite sum of exponential functions. Now we have all the machinery to write down a proof.

(of Weyl’s criterion)
For the forward direction (1) => (2), fix k\neq 0 and \epsilon > 0. Since the exponential function e_k(x):=e^{2\pi i kx} continuous on the closed interval [0, 1], it is also uniformly continuous, i.e., there exists some \delta > 0 such that for every x, x', |e_k(x) - e_k(x')| < \epsilon. Let f_S be a step function where f_S(x) = e_k(m \delta) if x \in [m\delta, (m+1)\delta). By construction, f_S is a finite sum of interval functions with \norm{f_S - e_k}_{\infty} < \epsilon.

By linearity, we have

    \[ \lim_{N\rightarrow \infty}\frac{1}{N} \sum_{n=1}^N f_S(x_n) = \int_0^1 f_S. \]

By taking N sufficiently large and repeatedly applying triangle inequality, we have

    \begin{eqnarray*} \left|\frac{1}{N} \sum_{n=1}^N e_k(x_n) - \int_0^1 e_k \right| & \leq & \left|\frac{1}{N} \sum_{n=1}^N e_k(x_n) - \frac{1}{N} \sum_{n=1}^N f_S(x_n) \right| + \\ & & \left|\frac{1}{N} \sum_{n=1}^N f_S(x_n) - \int_0^1 e_k \right| \\ & \leq & \epsilon + \left|\frac{1}{N} \sum_{n=1}^N f_S(x_n) - \int_0^1 f_S \right| + \left| \int_0^1 f_S - \int_0^1 e_k \right| \\ & \leq & 3\epsilon, \end{eqnarray*}

implying that \frac{1}{N} \sum_{n=1}^N e_k(x_n) converges to \int_0^1 e_k as N\rightarrow \infty.

Now we consider the reverse direction (2) => (1). Fix 0\leq a < b \leq 1 and let \epsilon > 0. Define

    \[ f^+(x) =  \begin{cases} 1 & \text{if } x \in [a, b) \\ 1/\epsilon (x - (a - \epsilon)) & \text{if } x \in [a - \epsilon, a) \\ -1/\epsilon (x - (b - \epsilon)) + 1 & \text{if } x \in [b, b + \epsilon) \\ 0 & \text{everywhere else.} \end{cases} \]

Note that f^+ is continuous, periodic, and dominates \chi_{[a, b)}. By Fejér’s Theorem, there exists P(x) = \sum_{k=1}^d p_k e^{2\pi i kx} such that \norm{f^+ - P}_{\infty} < \epsilon. By linearity, we have

    \[ \lim_{N\rightarrow \infty}\frac{1}{N} \sum_{n=1}^N P(x_n) = \int_0^1 P. \]

By taking N sufficiently large and repeatedly applying triangle inequality, we have

    \begin{eqnarray*} \left| \abs{\sum_{n=1}^N f^+(x_n) - \int_0^1 f^+ \right| & \leq & \left| \sum_{n=1}^N f^+(x_n) - \sum_{n=1}^N P(x_n) \right| + \left| \sum_{n=1}^N P(x_n) - \int_0^1 f^+ \right| \\ & \leq & \epsilon + \left| \sum_{n=1}^N P(x_n) - \int_0^1 P \right| + \left| \int_0^1 P - \int_0^1 f^+ \right| \\ & \leq & 3\epsilon, \end{eqnarray*}

implying that

    \[ \lim_{N\rightarrow \infty}\frac{1}{N} \sum_{n=1}^N f^+(x_n) = \int_0^1 f^+. \]

Since f^+ dominates \chi_{[a, b)}, we have

    \begin{eqnarray*} \limsup_{N \rightarrow \infty}  \frac{1}{N} \sum_{n=1}^N \chi_{[a,b)}(x_n) & \leq & \limsup_{N \rightarrow \infty}  \frac{1}{N} \sum_{n=1}^N f^+(x_n) \\ & = & \int_0^1 f^+ \\ & = & \int_0^1 \chi_{[a, b)} + \epsilon. \end{eqnarray*}

One can similarly define a periodic, continuous function f^- that approximates \chi_{[a, b)} from below, showing that \liminf_{N \rightarrow \infty}  \frac{1}{N} \sum_{n=1}^N \chi_{[a,b)}(x_n) is bounded below by \int_0^1 \chi_{[a, b)} - \epsilon, which together with the proceeding argument will show that the limit of \frac{1}{N} \sum_{n=1}^N \chi_{[a,b)}(x_n) must exist and converge to \int_0^1 \chi_{[a, b)}.

The Basel problem via Fourier series

The Basel problem asks to compute the summation of the reciprocal of the natural numbers squared, and it is known that

    \[\sum_{n=1}^{\infty} \frac{1}{n^2} = \frac{\pi^2}{6}.\]

While there are numerous known proofs (our presentation resembles Proof 9 most closely), we give a self-contained one that motivates the usage of Fourier analysis for periodic functions.

Recall that a function f:\mathbb{R}\rightarrow\mathbb{C} is 2\pi-periodic if for every x \in \mathbb{R}, f(x+2\pi)=f(x). From Fourier analysis, every such function can be expressed as a series of cosines and sines. More precisely,

If f is continuous and 2\pi-periodic, then

    \[\left\Vert f - \sum_{n=-\infty}^{\infty} \hat{f}(n) e_n\right\Vert_2 = 0,\]

where e_n(x) = e^{inx}, and \hat{f}(n) is the n-th Fourier coefficient equal to \frac{1}{2\pi}\int_{-\pi}^{\pi} f(x)e^{-inx} dx.

We say that \sum_{n=-\infty}^{\infty} \hat{f}(n) e_n is the Fourier series of f. When we define the inner product of two functions to be \frac{1}{2\pi}\int_{-\pi}^{\pi} f(x) \overline{g(x)} dx, then it is easily seen that the “characters” \{e_n\} form an orthonormal system, and the n-th Fourier coefficient can be viewed as the projection of f along the n-th character. The Fourier theorem asserts that f can be approximated in L_2-norm by its Fourier series. In fact, by applying the Weierstrass M-test, we can make the following statement with a stronger convergence guarantee:

If f is continuous and 2\pi-periodic and \sum_{n=-\infty}^{\infty} \left|\hat{f}(n)\right| is convergent, then its Fourier series \sum_{n=-\infty}^{\infty} \hat{f}(n) e_n converges uniformly to f.

Furthermore, the Fourier transform \hat{f} itself encodes many of the properties of the original function f. In particular, we note that the symmetry of f is preserved in its Fourier transform.

If f is even, then for every n \in \mathbb{Z}, \hat{f}(-n) = \hat{f}(n).
If f is odd, then for every n \in \mathbb{Z}, \hat{f}(-n) = -\hat{f}(n).

Now we have the machinery to compute \sum_{n=1}^{\infty} 1/n^2.

(Of Basel) Define f:[-\pi, \pi]\rightarrow \mathbb{R} to be f(x)=|x|. We compute the Fourier coefficient of f. First note that

    \[\hat{f}(0) = \frac{1}{2\pi}\int_{-\pi}^{\pi} |x| dx = \frac{\pi}{2}.\]

For n \neq 0 \in \mathbb{Z}, we have

    \[2\pi\hat{f}(n) = \int_{0}^{-\pi}xe^{-inx} dx + \int_{0}^{\pi}xe^{-inx} dx. \]

Using integration by parts, we have for every a, b \in \mathbb{R},

    \begin{eqnarray*} \int_a^b xe^{-inx}dx & = & \frac{x e^{-inx}}{-in}\Biggr|_a^b - \int_a^b \frac{e^{-inx}}{-in}dx \\ & = & \frac{x e^{-inx}}{-in}\Biggr|_a^b + \frac{e^{-inx}}{n^2}\Biggr|_a^b. \end{eqnarray*}

Then

    \begin{eqnarray*} 2\pi\hat{f}(n) & = & \frac{-\pi(-1)^n}{-in} + \frac{(-1)^n -1 }{n^2} + \frac{\pi(-1)^n}{-in} + \frac{(-1)^n -1 }{n^2} \\ & = & \frac{2((-1)^n - 1)}{n^2}.  \end{eqnarray*}

Thus,

    \[ \hat{f}(n) =  \begin{cases} \frac{-2}{\pi n^2} & \text{if $n$ is odd,} \\ 0 & \text{if $n$ is even and nonzero,} \\ \frac{\pi}{2} & \text{if $n=0$.}  \]

From Euler’s formula, the Fourier series of f can be written as

    \[  \hat{f}(0) + \sum_{n=1}^{\infty} \left[ (\hat{f}(n) + \hat{f}(-n)) \cos(nx) + i(\hat{f}(n) - \hat{f}(-n)) \sin(nx) \right]. \]

Since f is even, by Proposition, \hat{f}(-n)=\hat{f}(n). From our calculation, the Fourier series of f is explicitly

    \[  \frac{\pi}{2} + \sum_{n\geq1, n \text{ odd}} \frac{-4}{\pi n^2} \cos(nx). \]

Note that \sum_{n=1}^{\infty} 1/n^2 is convergent from the Cauchy condensation test. Thus, by the Convergence Theorem, we conclude that

    \[ \frac{\pi}{2} + \sum_{n\geq1, n \text{ odd}} \frac{-4}{\pi n^2} \cos(nx) \longrightarrow |x|, \]

where the convergence is uniform (and in particular, pointwise). Setting x=0, we see that

    \[ \sum_{n\geq1, n \text{ odd}} \frac{1}{n^2} = \frac{\pi^2}{8}. \]

Lastly, observe that

    \begin{eqnarray*} \sum_{n=1}^{\infty} \frac{1}{n^2} & = & \sum_{n\geq1, n \text{ even}} \frac{1}{n^2} + \sum_{n\geq1, n \text{ odd}} \frac{1}{n^2} \\ & = & \frac{1}{4} \sum_{n=1}^{\infty} \frac{1}{n^2} + \frac{\pi^2}{8}, \end{eqnarray*}

finishing the proof.