Functional analysis

The last chapter ended with a promise: functions can be regarded as points of a space with infinitely many dimensions. Let’s check that this isn’t a pretty metaphor but a working tool. What’s the angle between the functions $x$ and $\sin x$? The question sounds like a joke, but it has an exact answer: about $38.8^\circ$. And what’s the length of the “vector” $\left(1, \frac12, \frac13, \frac14, \dots\right)$ with infinitely many coordinates? It’s $\frac{\pi}{\sqrt6} \approx 1.2825$, and by the end of the chapter we’ll prove it with Pythagoras’ theorem.

Such questions were asked seriously at the start of the twentieth century by David Hilbert in Göttingen, Frigyes Riesz in Hungary, Maurice Fréchet in Paris, and in the 1920s and 1930s by a group of mathematicians in Lwów who preferred working not at the university but at the tables of the Scottish Café. Their questions grew into a science with an unfortunate name: functional analysis. Its subject is spaces whose points are functions, and maps between such spaces.

Let’s go there on an excursion and take along some baggage from linear algebra: everything we learned about vectors in the chapters on vectors, matrices and orthogonality. At the border of infinite dimension it will be inspected. Here’s what we’re carrying:

Which of these will be let through and which held back, we’ll find out along the way. At the end we’ll check the list.

How many lengths are there

A taxi in a city with a rectangular grid of streets drives from the crossroads $(0, 0)$ to the crossroads $(3, 4)$: three blocks east and four north, seven in all, however it weaves. A helicopter flies in a straight line and covers $\sqrt{3^2 + 4^2} = 5$. A chess king gets there in four moves: each move it shifts diagonally until it lines up in one of the coordinates. Three honest answers to “how far”, and each is good for its own purpose.

The number $p \ge 1$ chooses the way of measuring. $p = 1$ is the taxi, $p = 2$ the helicopter, and as $p \to \infty$ the formula becomes $\|x\|_\infty = \max_i |x_i|$, the chess king: the largest term in the sum starts to swamp the others. The absolute values of the coordinates to the power $p$. The larger $p$, the more weight the big coordinates get. The root restores the right dimension: if the vector is stretched twofold, the length doubles too. Example: for $x = (3, 4)$ we get $\|x\|_1 = 7$, $\|x\|_2 = 5$, $\|x\|_3 = \sqrt[3]{27 + 64} \approx 4.498$ and $\|x\|_\infty = 4$.

What do all these lengths have in common? Three properties without which the word “length” loses its meaning.

A norm is most easily seen through its unit ball, the set of vectors with $\|x\| \le 1$. For the taxi it’s a diamond, for the helicopter a disc, for the king a square. The norm of any point can be read off the ball: blow the ball up or shrink it so that its boundary passes through the point, and the scaling factor is the norm.

At $p = \frac12$ the ball turns into a four-pointed star, and the formula stops giving a norm. Check it on the vectors $e_1 = (1, 0)$ and $e_2 = (0, 1)$: both have “length” $1$, but their sum has $\|(1, 1)\|_{1/2} = (1 + 1)^2 = 4 > 1 + 1$. It’s a matter of the ball’s shape: the star has dents, and that’s the whole reason.

The trick is to shrink $u$ and $v$ to unit length, take a point on the chord between them, and then stretch it back. The ball in the drawing is deliberately lopsided: the proof works for any convex ball.

If one of the vectors is zero, say $v = 0$, both sides of the inequality equal $N(u)$, and there’s nothing to prove. Let both be non-zero, $a = N(u) > 0$ and $b = N(v) > 0$. Put $\hat u = \frac{u}{a}$ and $\hat v = \frac{v}{b}$. By homogeneity $N(\hat u) = \frac{N(u)}{a} = 1$ and likewise $N(\hat v) = 1$: both points lie on the boundary of the ball. Write the sum through them: $u + v = a\hat u + b\hat v = (a + b)\,w$, where $w = \frac{a}{a + b}\,\hat u + \frac{b}{a + b}\,\hat v$. The two coefficients are non-negative and add up to $1$, so $w$ lies on the segment between $\hat u$ and $\hat v$, on a chord of the ball. The ball is convex, and both ends of the chord belong to it. So $w$ lies in the ball too: $N(w) \le 1$. By homogeneity $N(u + v) = N\bigl((a + b)w\bigr) = (a + b)\,N(w) \le a + b = N(u) + N(v)$. In the drawing $u + v$ is $w$ stretched by the factor $a + b$, and it doesn’t leave the ball of radius $a + b$. Conversely, suppose the triangle inequality holds, $x, y \in B$ and $0 \le t \le 1$. Then $N\bigl(tx + (1 - t)y\bigr) \le N(tx) + N\bigl((1 - t)y\bigr) = tN(x) + (1 - t)N(y) \le t + (1 - t) = 1$, that is, the whole segment from $x$ to $y$ lies in $B$.

Now checking that the formula $\|x\|_p$ gives a norm for $p \ge 1$ is easy: it’s enough to make sure its ball is convex. The hardest property, the triangle inequality, is called Minkowski’s inequality: Hermann Minkowski used it in his Geometry of Numbers (1896).

In the plane all these norms resemble one another: the balls sit one inside another, like nesting dolls.

The idea: an inequality between norms is the same as the nesting of balls. The larger the norm, the smaller its unit ball. The drawing is for $n = 2$.

$\|x\|_\infty \le \|x\|_2$: the largest of the squares $x_i^2$ is one of the terms of the sum $x_1^2 + \dots + x_n^2$, and the other terms are non-negative, so $\max x_i^2 \le \sum x_i^2$; it remains to take the square root. In the drawing the disc $B_2$ lies inside the square $B_\infty$. $\|x\|_2 \le \|x\|_1$: expand the square of the sum, $(|x_1| + \dots + |x_n|)^2 = \sum x_i^2 + 2\sum_{i < j}|x_i|\,|x_j| \ge \sum x_i^2$, and take the square root again. The diamond $B_1$ lies inside the disc. $\|x\|_1 \le n\|x\|_\infty$: each of the $n$ terms $|x_i|$ is at most the largest. The square $B_\infty$ fits into the diamond blown up $n$ times. The chain of inequalities is complete. The point $x$ in the drawing shows it in numbers: whatever point you take, the three norms come in the same order, and the largest is at most twice the smallest.

In the infinite-dimensional world this idyll ends. Take a sequence of $n$ ones followed by nothing but zeros: $(1, 1, \dots, 1, 0, 0, \dots)$. Its norms are $\|\cdot\|_\infty = 1$, $\|\cdot\|_2 = \sqrt n$, $\|\cdot\|_1 = n$. For $n$ equal to a million, that’s $1$, $1000$ and a million. No constant $C$ gives $\|x\|_1 \le C\,\|x\|_\infty$ for all such vectors at once. The first item of baggage is held back: in infinite dimensions different norms describe genuinely different worlds, and whether a sequence converges depends on which norm you use.

Find $\|x\|_2$ for $x = (2, -6, 3)$. For comparison, work out $\|x\|_1$ and $\|x\|_\infty$ too.

$\|x\|_2 = \sqrt{4 + 36 + 9} = \sqrt{49} = 7$. Also $\|x\|_1 = 2 + 6 + 3 = 11$ and $\|x\|_\infty = 6$. The chain $6 \le 7 \le 11 \le 3 \cdot 6$ holds.

Functions become points

Let’s take the first step across the border: allow vectors to have infinitely many coordinates, $x = (x_1, x_2, x_3, \dots)$. They can still be added and multiplied by numbers coordinatewise. The length can also be written down by Pythagoras, $\|x\|^2 = x_1^2 + x_2^2 + \dots$, only now it’s a series, and it may diverge.

The sequence $\left(1, \frac12, \frac13, \dots\right)$ lies in $\ell^2$: the sum of squares $\sum\frac1{n^2}$ converges; that’s the Basel problem from the chapter on series. But $\left(1, \frac1{\sqrt2}, \frac1{\sqrt3}, \dots\right)$ doesn’t, though its coordinates also tend to zero: the sum of their squares is the harmonic series, which diverges. The whole definition rests on two checks. The sum of two vectors of $\ell^2$ is again in $\ell^2$, because $(a + b)^2 \le 2a^2 + 2b^2$. The series $\sum x_ny_n$ converges absolutely, because $|x_ny_n| \le \frac12(x_n^2 + y_n^2)$. The similar spaces $\ell^1$ (where $\sum|x_n|$ converges) and $\ell^\infty$ (bounded coordinates) are built the same way, but they have no inner product; the parallelogram theorem below will say why.

The same happens with functions on the segment $[-\pi, \pi]$, only a function has as many “coordinates” as the segment has points, and the sum becomes an integral. The inner product of functions $\langle f, g\rangle = \int_{-\pi}^{\pi}f(x)g(x)\,dx$ appeared back in the chapter on Fourier series. What all the examples have in common is three properties.

The proof of the Cauchy–Schwarz inequality $|\langle x, y\rangle| \le \|x\|\,\|y\|$ in the chapter on orthogonality relied only on these three properties, so it holds in any such space, and with it the triangle inequality: $\|x + y\|^2 = \|x\|^2 + 2\langle x, y\rangle + \|y\|^2 \le \|x\|^2 + 2\|x\|\,\|y\| + \|y\|^2 = (\|x\| + \|y\|)^2$. So $\sqrt{\langle x, x\rangle}$ is a norm, and the space of functions has both distances and angles.

With functions there’s one subtlety. If $f$ is non-zero at a single point only, then $\int f^2 = 0$, and the third property of the inner product breaks. The way out was suggested by the chapter on measure: functions that agree almost everywhere, that is, everywhere except on a set of measure zero, are regarded as the same point of the space.

Is there an inner product that produces the norm $\|\cdot\|_1$ or $\|\cdot\|_\infty$? There’s a simple test.

For $\|\cdot\|_p$ let’s test the law on $u = e_1$, $v = e_2$: the left side is $\|(1, 1)\|_p^2 + \|(1, -1)\|_p^2 = 2 \cdot 2^{2/p}$, the right side $4$. Equality holds only when $2^{2/p} = 2$, that is, at $p = 2$. So of all the norms $\|\cdot\|_p$ only the Euclidean one comes from an inner product, and only it has angles. In the widget above the “parallelogram” line turns green only at $p = 2$.

Find the inner product $\langle x, \sin 2x\rangle$ on the segment $[-\pi, \pi]$. The answer can be written using $\pi$, for example 2pi.

Integrate by parts: $\int_{-\pi}^{\pi}x\sin 2x\,dx = \Bigl[-\frac{x\cos 2x}{2}\Bigr]_{-\pi}^{\pi} + \frac12\int_{-\pi}^{\pi}\cos 2x\,dx = -\frac{\pi}{2} - \frac{\pi}{2} + 0 = -\pi$. The angle between $x$ and $\sin 2x$ is obtuse: over most of the segment the saw and the second harmonic point in opposite directions.

Pythagoras with infinitely many legs

In chapter 39 the coordinates of a vector in an orthonormal basis were found without any systems of equations: $c_k = \langle x, e_k\rangle$. In an infinite-dimensional space a basis of finitely many vectors can’t be built, but there can be infinitely many mutually perpendicular unit vectors.

In $\ell^2$ such a system is the vectors $e_1 = (1, 0, 0, \dots)$, $e_2 = (0, 1, 0, \dots)$ and so on. In $L^2[-\pi, \pi]$ it’s the harmonics from the chapter on Fourier series, divided by their lengths:

$$\frac{1}{\sqrt{2\pi}},\quad \frac{\cos x}{\sqrt\pi},\quad \frac{\sin x}{\sqrt\pi},\quad \frac{\cos 2x}{\sqrt\pi},\quad \frac{\sin 2x}{\sqrt\pi},\quad \dots$$

Their mutual orthogonality is a theorem from chapter 33, and dividing by $\sqrt\pi$ and $\sqrt{2\pi}$ makes the lengths one. The coordinates of a function in this system differ from the coefficients $a_n$, $b_n$ only by a factor: $\langle f, \frac{\cos nx}{\sqrt\pi}\rangle = \sqrt\pi\,a_n$. A Fourier series turns out to be the expansion of a vector in a basis, the same as writing an arrow in terms of $\vec\imath$ and $\vec\jmath$, only with infinitely many axes.

The nearest point theorem from chapter 39 also used only the properties of the inner product. So the best approximation of a vector $f$ by combinations of $e_1, \dots, e_N$ is its projection $P_Nf = c_1e_1 + \dots + c_Ne_N$, and in the space of functions that’s a partial sum of the Fourier series. Hence the first estimate.

The idea: $f$, its projection and the perpendicular form a right triangle, and the leg lying in the plane splits by Pythagoras once more. The drawing is for $N = 2$ in three-dimensional space; in any other space everything is written with the same formulas.

The projection $P_Nf = c_1e_1 + \dots + c_Ne_N$ lies in the subspace $W_N$ spanned by $e_1, \dots, e_N$. In the drawing its coordinates $c_1$ and $c_2$ are marked along the axes. The difference $f - P_Nf$ is perpendicular to every $e_j$ with $j \le N$. By linearity $\langle f - P_Nf, e_j\rangle = \langle f, e_j\rangle - \sum_{k \le N}c_k\langle e_k, e_j\rangle$. In the sum only the term with $k = j$ survives, where $\langle e_j, e_j\rangle = 1$, so we get $c_j - c_j = 0$. So $f - P_Nf$ is perpendicular to any combination of $e_1, \dots, e_N$ too, including $P_Nf$ itself. Pythagoras’ theorem in an inner product space: for perpendicular $a$ and $b$ we have $\|a + b\|^2 = \|a\|^2 + 2\langle a, b\rangle + \|b\|^2 = \|a\|^2 + \|b\|^2$. With $a = P_Nf$ and $b = f - P_Nf$ we get $\|f\|^2 = \|P_Nf\|^2 + \|f - P_Nf\|^2$. Inside $W_N$ the vectors $c_ke_k$ are mutually perpendicular, and the same theorem applied $N - 1$ times gives $\|P_Nf\|^2 = c_1^2 + \dots + c_N^2$. Substituting, we get $\|f - P_Nf\|^2 = \|f\|^2 - \sum_{k \le N}c_k^2$. The left side is non-negative, so the partial sums of the series $\sum c_k^2$ don’t exceed $\|f\|^2$. A series of non-negative terms with bounded partial sums converges, and its sum is at most $\|f\|^2$ too.

Bessel’s inequality says the coordinates can’t carry away more energy than the signal has. How much they actually carry away is shown by the next widget. The strip under the graph is the squared length $\|f\|^2$ cut into the squared coordinates $c_k^2$; the hatched remainder is the squared error.

For every signal the strip fills up completely: the error goes to zero. If this happens for every vector, Bessel’s inequality becomes an equality.

The squared length of the vector; for a signal, its energy, the integral of its square. The coordinates with respect to a complete orthonormal system. The equation is Pythagoras’ theorem with infinitely many legs. The same for the trigonometric system in terms of the usual Fourier coefficients: $c_0^2 = \frac{\pi a_0^2}{2}$, and for the harmonics $c^2 = \pi a_n^2$ and $\pi b_n^2$; divide both sides by $\pi$. Example: for the saw $f(x) = x$ all $a_n = 0$, and $b_n = \frac{2(-1)^{n+1}}{n}$ (chapter 33). The left side is $\frac1\pi\cdot\frac{2\pi^3}{3} = \frac{2\pi^2}{3} \approx 6.580$, the right $4 + 1 + \frac49 + \frac14 + \dots$; the first ten terms give $6.199$.

The identity is named after Marc-Antoine Parseval, who wrote down a related statement about series as early as 1799, without a rigorous proof. For the trigonometric system and all functions in $L^2$ it holds, but we’ll prove it for the functions we worked with in chapter 33, piecewise smooth ones. That will be enough to get $\frac{\pi^2}{6}$ for the third time in the course.

The trick is to prove the identity first for continuous functions, where the partial sums approach uniformly, and then to replace a jump by a steep ramp. The error from this replacement is small, and the best approximation is no worse than any other. The drawing is for the saw $f(x) = x$ and $N = 6$.

The partial sum $S_Nf$ is the projection of $f$ onto the subspace spanned by $1, \cos x, \sin x, \dots, \cos Nx, \sin Nx$. By Bessel’s inequality $\|f - S_Nf\|^2 = \|f\|^2 - \pi\bigl(\frac{a_0^2}{2} + \sum_{n \le N}(a_n^2 + b_n^2)\bigr)$. So Parseval’s identity is exactly the statement $\|f - S_Nf\| \to 0$. In the drawing the gap between $f$ and $S_6f$ is shaded: the error sits mainly at the jump. Suppose first that $g$ is continuous, piecewise smooth, and $g(-\pi) = g(\pi)$. Integrate by parts on each piece of smoothness: $a_n(g) = -\frac{b_n(g')}{n}$, $b_n(g) = \frac{a_n(g')}{n}$. The terms at the boundaries of the pieces cancel: at the inner junctions because $g$ is continuous, at the ends because $g(-\pi) = g(\pi)$, $\cos(-n\pi) = \cos n\pi$ and $\sin(\pm n\pi) = 0$. So the coefficients of $g$ are $n$ times smaller than those of its derivative. For the ramp $g$ in the drawing, $b_n = \frac{2\sin n(\pi - \delta)}{\delta n^2}$. It follows that $\sum_n(|a_n| + |b_n|) < \infty$. By the Cauchy–Schwarz inequality for sequences, $\sum\frac{|a_n(g')| + |b_n(g')|}{n} \le \sqrt{\sum\frac{2}{n^2}}\,\sqrt{\sum\bigl(a_n(g')^2 + b_n(g')^2\bigr)}$ (for finite sums it’s the inequality from chapter 39; then pass to the limit). The first root is finite (chapter 30), the second by Bessel’s inequality for the piecewise continuous $g'$. By Dirichlet’s theorem (chapter 33) the series of $g$ converges to $g(x)$ at every point, so $|g(x) - S_Ng(x)| = \bigl|\sum_{n > N}(a_n\cos nx + b_n\sin nx)\bigr| \le r_N$, where $r_N = \sum_{n > N}(|a_n| + |b_n|)$ is the tail of a convergent series, $r_N \to 0$. The bound is the same for the whole period: $S_Ng$ doesn’t leave the band. Hence $\|g - S_Ng\|^2 \le 2\pi r_N^2 \to 0$. Now the saw $f$ with its jump. Replace the jump by a ramp: $g = f$ everywhere except on segments of length $\delta$ at the ends, where $g$ descends linearly to zero. The function $g$ is continuous, piecewise smooth, and $g(\pm\pi) = 0$. The difference $|f - g|$ is at most $\pi$ and non-zero on segments of total length $2\delta$, so $\|f - g\|^2 \le 2\delta\pi^2$. For any piecewise smooth function with jumps, do the same at each jump. The partial sum $S_Ng$ lies in the same subspace as $S_Nf$, and $S_Nf$ is the point of that subspace nearest to $f$. So $\|f - S_Nf\| \le \|f - S_Ng\|$, and by the triangle inequality $\|f - S_Ng\| \le \|f - g\| + \|g - S_Ng\|$. Take $\varepsilon > 0$. Choose $\delta$ so that $\|f - g\| < \frac\varepsilon2$, then $N_0$ after which $\|g - S_Ng\| < \frac\varepsilon2$ (step 3). For $N \ge N_0$ we get $\|f - S_Nf\| < \varepsilon$. So $\|f - S_Nf\| \to 0$, and by step 1 Parseval’s identity is proved.

For $f(x) = x^2$ on $[-\pi, \pi]$ the Fourier coefficients are $a_0 = \frac{2\pi^2}{3}$, $a_n = \frac{4(-1)^n}{n^2}$, $b_n = 0$ (chapter 33). Use Parseval’s identity to find the sum $\sum_{n=1}^{\infty}\frac1{n^4}$. Write the answer using $\pi$, for example pi^4/90.

The left side is $\frac1\pi\int_{-\pi}^{\pi}x^4\,dx = \frac{2\pi^4}{5}$. The right side is $\frac{a_0^2}{2} + \sum a_n^2 = \frac{2\pi^4}{9} + 16\sum\frac1{n^4}$. Hence $16\sum\frac1{n^4} = \frac{2\pi^4}{5} - \frac{2\pi^4}{9} = \frac{8\pi^4}{45}$ and $\sum\frac1{n^4} = \frac{\pi^4}{90} \approx 1.0823$: Euler’s second result from the same chapter 30.

For the saw $\|x - S_N\| \to 0$. Does it follow that $S_N(x) \to x$ at every point of the segment $[-\pi, \pi]$?

Yes, since the error tends to zero No: for example, at the point $\pi$ all the $S_N$ are zero No, at no point at all

All the sines vanish at the point $\pi$, so $S_N(\pi) = 0$ for every $N$, while $f(\pi) = \pi$ (or $-\pi$, depending on how it’s extended). Convergence in the $L^2$ norm is convergence of integrals, not of values: a single point, or indeed any set of measure zero, has no effect on it. The strongest result on pointwise convergence, Carleson’s theorem (1966), was mentioned in chapter 33.

The Scottish Café

In the summer of 1916 the Kraków mathematician Hugo Steinhaus was walking in the city’s Planty park and heard two young men on a bench mention Lebesgue. He sat down with them. One of the two was Stefan Banach, a self-taught student who never finished his engineering degree. Steinhaus offered him a problem he’d been struggling with himself, and a few days later Banach brought a solution. According to Steinhaus, Banach was his greatest mathematical discovery.

In 1920 Banach defended his thesis in Lwów; it was published in 1922. In it the spaces that now bear his name were described by axioms for the first time: a vector space, a norm, and one extra requirement, completeness. In 1932 his book Theory of Linear Operations came out, and functional analysis was learned from it for the next half-century.

The Lwów school worked in cafés. The favourite was the Scottish Café, where problems were written in pencil straight onto the marble tables, and the cleaner wiped them off every evening. So Banach’s wife bought a thick notebook, which the waiter kept and handed over on request. From 1935 to 1941 Banach, Steinhaus, Stanisław Mazur, Stanisław Ulam and their guests wrote 193 problems into the “Scottish Book”. Prizes were set for solutions, from a glass of beer to a bottle of wine. In 1936 Mazur promised a live goose for problem no. 153. It was solved in 1972 by a young Swede, Per Enflo, who came to Warsaw, and Mazur presented him with the goose. The problem was closely linked to a question from Banach’s book: does every “good enough” (separable) Banach space have a basis, a sequence of vectors in which every vector expands uniquely as a convergent series? Enflo built a space with no basis and answered both questions.

So what is completeness? In the chapter on rigorous analysis the real numbers differed from the rationals in that every Cauchy sequence, one whose terms get arbitrarily close to one another, converges. In a normed space the definition is the same, only distance is measured by the norm: a sequence $x_1, x_2, \dots$ is a Cauchy sequence if for every $\varepsilon > 0$ there’s an index after which $\|x_m - x_n\| < \varepsilon$.

Incomplete spaces are met at every step. Take the continuous functions on $[-1, 1]$ with the norm $\|f\| = \sqrt{\int f^2}$ and the sequence of “steps with a slope”: $f_n(x) = -1$ for $x \le -\frac1n$, $f_n(x) = 1$ for $x \ge \frac1n$ and $f_n(x) = nx$ in between. For $m > n$ the functions $f_m$ and $f_n$ differ only on the interval $\left(-\frac1n, \frac1n\right)$, and there by at most $1$, so $\|f_m - f_n\|^2 \le \frac2n$: the sequence is a Cauchy sequence. But it converges to the discontinuous step $\operatorname{sgn}x$: $\|f_n - \operatorname{sgn}\|^2 = 2\int_0^{1/n}(1 - nx)^2\,dx = \frac{2}{3n} \to 0$. There’s no continuous limit: it would coincide with the step almost everywhere, and a continuous function can’t equal $-1$ almost everywhere to the left of zero and $1$ almost everywhere to the right. The space of continuous functions has a hole where the step should be.

Completeness is needed for limits to work: without it, an object built by iterations may turn out to be a hole. For sequences it’s not hard to check.

The idea: first find a candidate for the limit coordinate by coordinate, using the completeness of the line, and then estimate the tails through finite sums, for which the limit carries over without fuss.

Each coordinate converges. For index $k$ we have $|x^{(m)}_k - x^{(l)}_k| \le \|x^{(m)} - x^{(l)}\|$: one term of a sum of squares is at most the whole sum. So the numbers $x^{(1)}_k, x^{(2)}_k, \dots$ form a Cauchy sequence, and by Cauchy’s criterion (chapter 53) it has a limit. Call it $x_k$ and put $x = (x_1, x_2, \dots)$. Take $\varepsilon > 0$ and an index $M$ after which $\|x^{(m)} - x^{(l)}\| < \varepsilon$. For any $K$ and any $m, l \ge M$ the finite sum $\sum_{k=1}^{K}|x^{(m)}_k - x^{(l)}_k|^2 < \varepsilon^2$. Fix $m$ and let $l$ tend to infinity: there are finitely many terms, each tends to $|x^{(m)}_k - x_k|^2$, so $\sum_{k=1}^{K}|x^{(m)}_k - x_k|^2 \le \varepsilon^2$. This holds for every $K$, so the partial sums of the series $\sum_k|x^{(m)}_k - x_k|^2$ are bounded by $\varepsilon^2$, the series converges, and its sum is at most $\varepsilon^2$. So the vector $x^{(m)} - x$ lies in $\ell^2$ and $\|x^{(m)} - x\| \le \varepsilon$ for $m \ge M$. The vector $x = x^{(m)} - (x^{(m)} - x)$ is a difference of two vectors of $\ell^2$, so it lies in $\ell^2$ itself. And $\|x^{(m)} - x\| \le \varepsilon$ for all $m \ge M$ means that $x^{(m)} \to x$ in norm.

The space $L^2$ is complete too, and that’s why it was defined through the Lebesgue integral and classes of functions equal almost everywhere: the Riemann integral would have left holes. This is the Riesz–Fischer theorem (1907), and its proof is a good occasion to apply the theorems on limits under the integral sign from chapter 54.

Together with Parseval’s identity this gives a strong consequence. Each function of $L^2[-\pi, \pi]$ corresponds to the sequence of its coefficients in $\ell^2$, and conversely: whatever sequence with a finite sum of squares you take, by completeness the series $\sum c_ke_k$ converges to a function with those coefficients. Lengths and angles are preserved. The space of signals and the space of sequences are one and the same Hilbert space written in two coordinate systems. This fact will turn up in physics a few pages from now.

A map on the table

Lay on the table a map of the city you’re sitting in. The claim is that exactly one point of the map lies directly over the place in the city that it depicts. It doesn’t matter how the map is turned or where it lies, as long as it’s entirely inside the city. Check it on a toy city.

What’s going on here in the language of this chapter? Each point $x$ of the city is assigned a point $T(x)$: the place over which the image of $x$ on the small map lies. The map $T$ shrinks all distances by the same factor: the factor by which the map is smaller than the city. The pin is a point with $T(x) = x$. To talk about such maps in general, all that’s needed is distance.

Every normed space is a metric space with $d(x, y) = \|x - y\|$, but metric spaces can exist without addition too: for example, the set of all shapes in the plane, which we’ll come to shortly.

The idea: the steps of the iterations shorten in a geometric progression, so the whole remaining path fits into a disc that itself shrinks to a point. Completeness guarantees that there’s something at that point.

Write $d_0 = d(x_0, x_1)$. Since $x_{k+1} = T(x_k)$ and $x_{k+2} = T(x_{k+1})$, by the definition of a contraction $d(x_{k+1}, x_{k+2}) \le q\,d(x_k, x_{k+1})$, and by induction $d(x_k, x_{k+1}) \le q^kd_0$. In the drawing each next step of the zigzag is shorter than the one before by a factor of at least $\frac1q$. For $n > m$, by the triangle inequality $d(x_m, x_n) \le d(x_m, x_{m+1}) + \dots + d(x_{n-1}, x_n) \le (q^m + q^{m+1} + \dots)\,d_0 = \frac{q^m}{1 - q}\,d_0$, the sum of a geometric series. All the points after $x_m$ lie in the disc centred at $x_m$ with radius $\frac{q^m}{1 - q}d_0$. Call this disc $B_m$. The radii tend to zero, so the sequence is a Cauchy sequence. The discs are nested like nesting dolls: $B_{m+1} \subset B_m$, because $d(x_m, x_{m+1}) + \frac{q^{m+1}}{1 - q}d_0 \le q^md_0 + \frac{q^{m+1}}{1 - q}d_0 = \frac{q^m}{1 - q}d_0$. The space is complete, so $x_k \to x^*$ for some point $x^* \in X$. A contraction is continuous: $d(Tx_k, Tx^*) \le q\,d(x_k, x^*) \to 0$. So $x_{k+1} = Tx_k \to Tx^*$, but the same sequence converges to $x^*$, and the limit is unique. So $Tx^* = x^*$. Uniqueness. If $Ty = y$ for another point, then $d(x^*, y) = d(Tx^*, Ty) \le q\,d(x^*, y)$. With $q < 1$ this is possible only if $d(x^*, y) = 0$, that is, $y = x^*$. In the drawing any other point $y$ is moved by the map $T$. The rate estimate: in the inequality from step 2 let $n$ tend to infinity; distance is continuous, and $d(x_m, x^*) \le \frac{q^m}{1 - q}\,d(x_0, x_1)$.

The map on the table is a special case: the city with the ordinary distance in the plane is a complete space, and $T$ is a contraction by $q$, where $q$ is the ratio of the scales. The requirement “the map entirely inside the city” is needed so that $T$ maps the city into itself. If the small map hangs over the edge of the table, the theorem promises nothing, and the fixed point may go over the edge.

The point after $m$ iterations. The contraction factor. The closer it is to $1$, the slower the convergence and the larger the factor $\frac1{1 - q}$. The length of the first step: it can be measured before anything is known about $x^*$. Example: the equation $x = \cos x$ on the segment $[0, 1]$. Cosine maps the segment into $[\cos 1, 1] \subset [0, 1]$, and by the mean value theorem $|\cos x - \cos y| \le \sin 1 \cdot |x - y|$, so $q = \sin 1 \approx 0.841$. From $x_0 = 1$ we get $x_1 = \cos 1 \approx 0.540$, $d(x_0, x_1) \approx 0.460$, and the estimate guarantees accuracy $0.001$ after $47$ steps. In practice $13$ are enough: the estimate is cautious. The root is $x^* = 0.7390851\dots$

This theorem has already been at work in the course without introducing itself. The proof of Picard’s theorem in chapter 31 built the solution of a differential equation by the iterations $y_{n+1}(t) = y_0 + \int_{t_0}^tf(s, y_n(s))\,ds$: those are iterations of a contraction in a space of continuous functions. And in chapter 38 the transition matrix contracted distributions in the norm $\|\cdot\|_1$, and the stationary distribution was found as its fixed point.

For $T(x) = \frac x2 + 1$ on the line and $x_0 = 0$: how many iterations does the rate estimate guarantee for the error to be at most $0.001$? Give the smallest such $m$.

Here $q = \frac12$, $x_1 = 1$, $d(x_0, x_1) = 1$, and the estimate is $\frac{(1/2)^m}{1/2} = 2^{1-m}$. We need $2^{1-m} \le 0.001$, that is, $2^{m-1} \ge 1000$. Since $2^9 = 512$ and $2^{10} = 1024$, we get $m - 1 = 10$, $m = 11$. The fixed point is $x^* = 2$, and the actual error $|x_m - 2| = 2^{1-m}$ coincides with the estimate: for this map it’s exact.

A fern as a fixed point

The most unexpected application of the theorem is pictures. Take several contractions of the plane $f_1, \dots, f_k$ and let them act not on points but on whole shapes: assign to a shape $A$ the shape $F(A) = f_1(A) \cup \dots \cup f_k(A)$, the union of its reduced copies. Such a collection of contractions is called an iterated function system, and a shape that coincides with the union of its copies, $F(K) = K$, is its attractor.

To apply Banach’s theorem we need a distance between shapes. It was devised by Felix Hausdorff in 1914.

The existence of the attractor also follows from Banach’s theorem: the bounded closed sets of the plane with the Hausdorff distance form a complete metric space. The proof of completeness takes a page and rests on the Bolzano–Weierstrass theorem; it can be found in Michael Barnsley’s book Fractals Everywhere (1988). Barnsley also showed how much fits into a few contractions: four affine maps, that is, 24 numbers, draw a fern.

Look at how the four contractions are built. The first squashes everything into a segment: that’s the stem. The second slightly rotates the whole frond and shrinks it to $0.85$: that gives the top, which repeats the whole. The third and fourth make the lower leaflets on the left and right. Self-similarity here isn’t decoration but the definition: the fern is the shape that equals the union of four reduced copies of itself, and such a shape is unique.

Hilbert’s hotel

Maps between infinite-dimensional spaces are called operators. A linear operator $T$ is bounded if $\|Tx\| \le C\|x\|$ for one and the same $C$ and all $x$; the smallest such $C$ is its norm $\|T\|$, the same greatest stretch as for the norm of a matrix. On $\mathbb R^n$ every linear map is bounded, but in infinite dimensions not so. The derivative $f \mapsto f'$ on smooth functions is linear, but $\|(\sin nx)'\| = n\,\|\sin nx\|$, and no $C$ will do.

The simplest operators on $\ell^2$ are shifts. The right shift $S(x_1, x_2, \dots) = (0, x_1, x_2, \dots)$ and the left shift $L(x_1, x_2, \dots) = (x_2, x_3, \dots)$. This is Hilbert’s hotel from the chapter on infinities: $S$ moves each guest to the next room and frees the first, $L$ evicts the guest from room one and moves the rest down.

In finite dimensions this can’t happen: by the rank–nullity theorem (chapter 37) a linear map $\mathbb R^n \to \mathbb R^n$ with no kernel is automatically onto, and for square matrices $AB = I$ implies $BA = I$. The fifth item of baggage is held back. Let’s see what’s become of eigenvalues.

For a matrix the eigenvalues are the roots of the characteristic polynomial, and over $\mathbb C$ there always are some. $S$ has none at all: $Sx = \lambda x$ gives $\lambda x_1 = 0$, $\lambda x_2 = x_1$, $\lambda x_3 = x_2$, and so on. If $\lambda \ne 0$, this gives in turn $x_1 = 0$, $x_2 = 0$, …; if $\lambda = 0$, then $Sx = 0$ and $x = 0$. $L$, on the contrary, has a continuum of eigenvalues: for any $|\lambda| < 1$ the vector $(1, \lambda, \lambda^2, \dots)$ lies in $\ell^2$, since $\sum|\lambda|^{2n} = \frac1{1 - |\lambda|^2}$, and $L(1, \lambda, \lambda^2, \dots) = (\lambda, \lambda^2, \dots) = \lambda\,(1, \lambda, \dots)$. To talk sensibly about the “eigenvalues” of such operators, the definition is broadened.

The word “spectrum” in this sense was introduced by Hilbert in his work on integral equations in the early 1900s. According to recollections, he was later amused that the spectra of his operators turned out to be the very spectra that physicists see in the radiation of atoms.

Quantum mechanics

In 1925 Werner Heisenberg described the atom with infinite tables of numbers, matrices, and in 1926 Erwin Schrödinger with wave functions, solutions of a differential equation. The two theories gave the same predictions, and nobody understood why. The answer was formulated by John von Neumann in his book Mathematical Foundations of Quantum Mechanics (1932): the state of a system is a unit vector of a Hilbert space, and a measurable quantity is an operator. Heisenberg’s matrices are the coordinates of operators in $\ell^2$, Schrödinger’s wave functions are vectors of $L^2$, and by the Riesz–Fischer and Parseval theorems these are one and the same space in two coordinate systems.

The possible results of a measurement are points of the operator’s spectrum. If the operator has an orthonormal basis of eigenvectors $e_k$ with eigenvalues $\lambda_k$ and the state is $\psi = \sum c_ke_k$, then the measurement gives $\lambda_k$ with probability $|c_k|^2$ (the Born rule, 1926). The probabilities add up to $\sum|c_k|^2 = \|\psi\|^2 = 1$: that’s Parseval’s identity. And a particle’s position and momentum have no eigenvectors in $L^2$ at all, like our shift $S$, and their spectrum is continuous: for such operators a notion of spectrum broader than that of eigenvalue became not a whim but a necessity.

A ball with room for everyone

The last item of baggage is the Bolzano–Weierstrass theorem (chapter 53): every bounded sequence in $\mathbb R^n$ has a convergent subsequence. The theorems on the maximum of a continuous function, on the comparability of norms and much else rest on it. Sets with this property (every sequence of points of the set has a subsequence converging to a point of the same set) are called compact; in $\mathbb R^n$ the bounded closed sets are compact, in particular the ball. In $\ell^2$ the counterexample lies on the surface: the vectors $e_1, e_2, e_3, \dots$ all have unit length, and the distance between any two of them is $\sqrt{1^2 + 1^2} = \sqrt2$. They don’t cluster anywhere.

The idea: an infinite-dimensional space has infinitely many mutually perpendicular unit vectors, and perpendicular unit vectors stand far apart.

The space is infinite-dimensional, so it has an infinite linearly independent sequence of vectors $v_1, v_2, \dots$: otherwise a finite set of independent vectors would be a basis. The Gram–Schmidt process (chapter 39) turns the first $n$ of them into orthonormal $e_1, \dots, e_n$, and at the next step just adds $e_{n+1}$ without changing those already built. We get an infinite orthonormal system $e_1, e_2, \dots$ For $i \ne j$ the vectors $e_i$ and $e_j$ are perpendicular, and by Pythagoras’ theorem $\|e_i - e_j\|^2 = \|e_i\|^2 + \|e_j\|^2 = 2$. Every two of them are at distance $\sqrt2$. Every convergent sequence is a Cauchy sequence: its terms with large indices are arbitrarily close to one another. But any two terms of any subsequence $e_{i_1}, e_{i_2}, \dots$ are $\sqrt2$ apart. The little balls of radius $\frac{\sqrt2}{2}$ around the vectors $e_i$ don’t overlap, and each contains only one term. The sequence $e_1, e_2, \dots$ has no Cauchy subsequence, and so no convergent one, even though all its terms lie in the unit ball.

The consequence is unpleasant. A continuous function on the unit ball of $\ell^2$ may fail to attain its largest value. Take $F(x) = \sum_n\left(1 - \frac1n\right)x_n^2$. For $\|x\| \le 1$, $x \ne 0$ we have $F(x) = \|x\|^2 - \sum\frac{x_n^2}{n} < 1$, while $F(e_n) = 1 - \frac1n \to 1$. The least upper bound $1$ isn’t attained. In the language of operators $F(x) = \langle Dx, x\rangle$ for the diagonal operator $D = \operatorname{diag}\left(0, \frac12, \frac23, \dots\right)$, and the number $1$ lies in its spectrum but isn’t an eigenvalue: the same story as with the shift.

A bounded sequence in $\ell^2$: $x^{(n)} = e_n + \frac1n e_1$. Does it have a convergent subsequence?

Yes, like every bounded sequence No: for $m \ne n$ the distance $\|x^{(m)} - x^{(n)}\|$ is at least $\sqrt2 - 1$ Yes, it converges to zero

$\|x^{(m)} - x^{(n)}\| \ge \|e_m - e_n\| - \bigl\|\frac1me_1 - \frac1ne_1\bigr\| \ge \sqrt2 - 1$ for $m, n \ge 2$ by the triangle inequality. The terms of any subsequence don’t get closer, and it isn’t a Cauchy sequence.

Time to check the baggage.

Where next

The Scottish Book still contains problems that remain unsolved. Usually this means that the right idea hasn’t been found. But can it be otherwise: a problem that can’t be solved in principle, not because mathematicians are weak but because the answer doesn’t follow from the axioms? An example has already flashed by in the chapter on infinities: the continuum hypothesis can be neither proved nor refuted. Can this happen to a simple statement about natural numbers that is nevertheless true? Can everything that’s true be proved? The answer was given by Kurt Gödel and Alan Turing, and it’s the subject of the next chapter.