A map that shrinks everything

Set a calculator to radians, type any number, and press the cosine button repeatedly. After twenty presses the display reads $0.739085$, and it does not matter at all what was typed first.

Brouwer’s theorem already promises a fixed point here, since cosine maps the unit interval into itself. What it does not promise is that there is only one, that iterating finds it, or that anything can be said about how long that takes. All three come from one extra hypothesis, and the hypothesis is visible in the picture: the graph is nowhere steep.

The hypothesis, and the three things it buys #

A map $f$ is a contraction with factor $k$ if

$$|f(x) - f(y)| \le k\,|x - y| \quad \text{for all } x, y,$$

with $k$ strictly less than one. For a differentiable map on an interval this is the same as saying that the derivative never exceeds $k$ in size — the steepest the graph ever gets. Cosine on $[0, 1]$ has derivative $-\sin x$, whose largest size there is $\sin 1 = 0.8415$, and the figure measures that on a grid rather than quoting it.

From that single condition, three conclusions:

Uniqueness. Two fixed points $p$ and $q$ would satisfy $|p - q| = |f(p) - f(q)| \le k|p-q|$, and a positive number cannot be at most $0.84$ times itself. So there is at most one.

Convergence from anywhere. Iterating from any start $x_0$, the distance to the fixed point is multiplied by at most $k$ each time, so it goes to zero geometrically. There is no basin to fall into and no bad start to avoid.

A bound, in advance. After $n$ steps the error is at most $k^n$ times the error at the start — which can be evaluated before the computation is run, and turned into the number of steps needed for a required accuracy.

The third is the one that separates this theorem from its neighbours, and it is why the right-hand panel of the figure draws a line the data are not allowed to cross. The curves are the observation; the line is the promise.

Existence, without assuming it #

The argument above needs a fixed point to exist before it can say anything about it, and the standard proof supplies existence too — from the same hypothesis, with no topology at all.

Iterating from any start gives a sequence whose consecutive gaps shrink geometrically: $|x_{n+1} - x_n| \le k^n|x_1 - x_0|$. Summing a geometric series bounds the distance between any two terms far enough along, so the sequence is Cauchy, and in a complete space a Cauchy sequence converges. Call the limit $p$; continuity of $f$ gives $f(p) = \lim f(x_n) = \lim x_{n+1} = p$.

Nothing there is two-dimensional, or even one-dimensional. The proof uses distances, the triangle inequality, completeness and continuity, and it therefore holds in every complete metric space — which is the reason this theorem is applied to spaces of functions rather than to intervals.

Attracting, repelling, and the number that decides #

The condition is a statement about a slope, and slopes on either side of one behave completely differently.

At a fixed point $p$ of a differentiable map, the local behaviour is decided by $|f'(p)|$. Below one, nearby points are pulled in and the fixed point is attracting; above one, they are pushed away. Exactly one is the undecided case, where the answer depends on higher derivatives, and it is where period doubling begins.

The contraction hypothesis is the global version of the attracting condition: not merely that the derivative is small at the fixed point, but that it is small everywhere on the set. That upgrade is what turns a local statement into a theorem with no local hypotheses, and it is the difference between this point attracts what is near it and this map has exactly one fixed point and finds it from anywhere.

The bound is a floor, not a description #

Applying the theorem to something that converges much faster than promised is instructive, because it shows what the guarantee is and is not.

The Babylonian rule halves the distance at worst, so the theorem guarantees an error under $2^{-n}$. What happens is much better: the derivative at $\sqrt{2}$ is exactly zero, so each step roughly squares the error, and six steps take a starting error of $0.4$ to below one part in $10^{12}$. Every step is a square root and the accuracy doubles at each of them.

The guarantee has not failed; it is simply weak here, and the weakness is structural. The contraction factor is the worst slope on the whole interval, and the convergence near the end is governed by the slope at the fixed point. When those two differ by a lot, the bound is honest and pessimistic — which is the right way round for a bound, and a bad way round for an estimate.

How many steps, in numbers #

The bound is worth using rather than admiring, and using it is arithmetic.

Starting from $0.05$, the distance to the cosine map’s fixed point is about $0.689$. The measured contraction factor on the interval is $0.8415$, so after $n$ presses the error is at most $0.689 \times 0.8415^{\,n}$, and requiring that to be under one part in a million gives $n \ge 78$. That number is available before pressing anything.

What actually happens is that the error falls by a factor of about $0.674$ per step rather than $0.8415$, because the relevant slope near the end is the slope at the fixed point, and thirty-four presses suffice. The ratio between the two counts — 78 promised, 34 needed — is the price of a guarantee that has to hold from every start in the interval rather than from this one.

Two habits follow. The bound is what to quote when the answer must be certified; the observed rate is what to quote when the question is how long a computation will take. And when the two are far apart, the gap is itself informative: it says the map is much flatter near its fixed point than elsewhere, which is exactly the situation in which a faster method is available.

Where it came from #

Stefan Banach stated and proved the principle in his 1922 doctoral thesis, in the general form — a complete metric space, an arbitrary contraction — and that generality is the reason his name is on it rather than anybody else’s.

The technique was older. Picard had been iterating integral operators to solve differential equations since the 1890s, and Liouville before him; each application carried its own convergence argument, tailored to the equation at hand. What Banach did was notice that every one of those arguments used the same three facts — distances shrink, gaps sum, the space is complete — and that nothing else about differential equations was involved.

The result is a theorem whose statement contains no analysis, no geometry and no particular equation, and which is therefore available to any subject with a notion of distance. That is a fair description of what abstraction is for, and this is one of the cleanest examples of it paying: a page of general nonsense replacing a chapter of special cases, and giving a better answer than any of them, since the general proof also supplies the error bound the special ones did not bother to state.

Where the hypothesis fails, and how narrowly #

The theorem is sharp, and two nearby statements that sound equivalent are false.

A slope under one at every point is not enough. On the interval $[1, \infty)$ the map $f(x) = x + 1/x$ has derivative $1 - 1/x^2$, which is strictly less than one everywhere. It has no fixed point: $f(x) = x$ would need $1/x = 0$. What fails is that the derivative approaches one as $x$ grows, so no single $k < 1$ bounds it, and the sequence of iterates marches off to infinity with steps that shrink but do not sum. The distinction between less than one at each point and at most $k$, uniformly is the whole content of the counterexample.

Completeness is not optional. On the rationals in $[1, 2]$ the Babylonian map is a perfectly good contraction and has no fixed point, because $\sqrt{2}$ is not there. The sequence still shrinks its gaps; it converges to nothing in the space it lives in. That is the hole in the rationals doing exactly what it always does, and it is why the theorem names completeness.

Both failures are the same failure as the fixed point that escapes to the boundary: the map is fine and the space is not.

What happens when it is only local #

Most maps of practical interest are contractions somewhere and not everywhere, and the difference produces the most spectacular pictures in the subject.

Newton’s iteration for a polynomial is a contraction in a neighbourhood of each simple root — the derivative there is zero, which is why it converges so fast — and is nothing of the kind globally. The result is a boundary of appalling complexity, where arbitrarily small changes in the start change which root is reached.

So the honest statement about iteration is two-part. Locally, near an attracting fixed point, contraction is the norm and gives fast, reliable convergence. Globally, the map may do anything at all, and there is no way to tell which basin a start is in short of running it.

Where it is really used #

The theorem is stated for metric spaces because its main applications are in spaces whose points are functions, and the fixed point is the solution of an equation.

The flagship case is the existence of solutions to differential equations. Rewrite $y' = F(x, y)$ with $y(x_0) = y_0$ as an integral equation, $y(x) = y_0 + \int_{x_0}^{x} F(t, y(t))\,dt$, and read the right-hand side as an operation carrying one function to another. On a short enough interval, and with a Lipschitz condition on $F$, that operation is a contraction on the space of continuous functions with the maximum-distance metric — a complete space. So it has exactly one fixed point, and a fixed point is precisely a solution of the differential equation.

That argument gives existence and uniqueness together, from a hypothesis about $F$ alone, with no formula for the solution anywhere. It also gives a procedure: iterate the integral operator from the constant function $y_0$ and watch the successive approximations converge. The mathematics is identical to pressing the cosine button; only the space has changed, and the fact that a space of functions can be treated as a space of points is the move that makes it possible.

There is a second application where the fixed point is not a number or a function but a shape. Take several contractions of the plane and apply all of them to a set at once, taking the union of the images; that operation is itself a contraction, on the space of compact sets with the distance that measures how far one set has to be fattened to swallow another. It therefore has exactly one fixed point, and that fixed point is a set equal to the union of its own shrunken copies — which is what a self-similar figure is. The fractal is not constructed and then observed to be self-similar; it is defined as the fixed point, and it exists because distances shrink.

What the picture cannot show #

The staircases converge visibly in about a dozen steps, which understates the theorem in one direction and overstates it in another. It understates it because the theorem holds for maps with no formula, no graph and no drawable domain; the picture is of the easiest possible case. It overstates it because a drawn cobweb suggests that seeing the convergence is the evidence, when the evidence is the bound — and the bound is the straight line in the right-hand panel, which no amount of iterating would reveal.

The failure cases cannot be drawn at all in their essential form. A map on the rationals looks exactly like a map on the reals; the missing point is missing invisibly. The best a figure can do is what the companion rung does — draw the set with the fixed point sitting just outside it — and even that is a picture of the conclusion rather than of the defect.

The ladder from here #

Below: the fixed-point theorem with no contraction hypothesis, which gives existence and nothing else, and Sperner’s lemma, which is what proves it. Sideways: the cobweb staircase, which is the same drawing used for a different question, and the Babylonian square root. Above: where the hypotheses fail, and the fixed points that are not points at all — a probability distribution left alone by an operation, which is what the bell curve turns out to be.

What to check before using it #

Three questions settle whether the theorem applies, and they are quick.

Does the map send the set into itself? A map that leaves the set has no fixed point in it and the iteration is meaningless; the figure checks this on a grid before drawing anything.

Is the set complete? For a closed interval of real numbers, yes; for the rationals, an interval with an endpoint removed, or a set of functions with the wrong notion of distance, no — and the failure is invisible until the limit is wanted.

Is there a single factor bounding every distance ratio? Not a slope under one at each point, which is weaker and insufficient, but one number that works everywhere on the set.

Each of the three has a counterexample above, and between them they are the whole of the hypothesis.

A hypothesis that pays for itself #

The lasting point is about the price of hypotheses. Brouwer’s theorem asks almost nothing — a continuous map of a disc into itself — and gives almost nothing: a point exists, somewhere, and no procedure will find it. Adding one inequality gives uniqueness, an algorithm, a rate and an error bound computable before the first step.

Strengthening a hypothesis until the conclusion becomes useful is the ordinary business of mathematics, and it is usually done in the wrong order — the theorem first, the hypothesis afterwards, tightened until the proof works. The contraction condition is the model of the opposite: an assumption that can be checked on the map by looking at it, and that says in advance exactly how much the conclusion will be worth.