The Contraction Mapping Theorem and Your New Favorite Math Tale

The contraction mapping theorem, also known as the Banach-Caccioppoli theorem, guarantees the existence of a fixed point for maps which “shrink”. In the following we’ll discuss the theorem, provide a sketch of the proof, and describe a neat application that will be sure to impress your math and non-math friends.

So I’m currently in the car on my way to Steamboat Springs for the holiday to do some skiing. I was browsing through Reddit mid trip and came across a post asking for some interesting math related facts for non-math people. My comment about an application of the contraction mapping theorem (explained below) was the intsipration for this short post.

Fixed Point Theorems and Contraction

The contraction mapping theorem is one of many fixed point theorems. Fixed point theorems guarantee a map $f$ has a fixed point $x_{0}$ , that is $f(x_{0}) = x_{0}$ , under one or a few conditions. Another widely known fixed point theorem is Brouwer’s fixed point theorem which guarantees the existence of a fixed point for any continuous function from the closed unit $n$ -dimensional ball to itself. The Lefschetz fixed point theorem, another notable one, gives a way to count the number of fixed points of certain maps rather that guarantee the existence of fixed points.

Let $X$ be a complete metric space with metric $d$ and let $f:X \to X$ be a map. What condition might we want on $f$ to guarantee that $f$ has a fixed point? We might start by noticing that since $f$ is a map from $X$ to $X$ we can apply $f$ iteratively. Then we would like $f$ to keep “shrinking” the image after successive applications, and hope that one of the points in every $\mathrm{Im}(f^{n}(X))$ for $n \ge 1$ is a fixed point. The formal notation of shrinking is called contraction. We say $f:X \to X$ is a contraction mapping if there exists $k \in [0,1)$ such that

$d(f(x),f(y)) \le kd(x,y)$

for all $x,y \in X$ . Stare at this inequality for a moment. The idea is that since $k < 1$ , the inequality says that the distance between points in the image under $f$ is less than the distance between corresponding points in the preimage. In other words, $f$ is shrinking the image in terms of the metric $d$ , or equivalently, $f$ is contracting the distances between points in $X$ .

How strong is this contraction requirement? Somewhat surprisingly, it is stronger than you might think. Contraction mappings are a specialization of more general types of maps. If we only require $k \ge 0$ then $f$ is said to be Lipschitz continuous with Lipschitz constant $k$ . So, we can think of contraction mappings as Lipschitz continuous mappings with Lipschitz constant less than $1$ . Lipschitz continuity turns out to be a strong form of continuity which implies that the contraction requirement is strong. It is a good exercise to check that Lipschitz continuous maps are uniformly continuous and in fact are absolutely continuous. This implies they are differentiable almost everywhere, that is, they are differentiable everywhere outside a set of Lebesgue measure zero. The derivative turns out to be an $L^{\infty}$ -function with the Lipschitz constant as the essential supremum. In general, Lipschitz continuous functions are not continuously differentiable.

The Contraction Mapping Theorem

The following is a precise formulation of the contraction mapping theorem:

Theorem: Let  be a complete metric space with metric  and suppose  is a contraction mapping. Then there exists a unique  such that  is a fixed point of . That is, .

The sketch of the proof is as follows. Let $x \in X$ be an arbitrary point of $X$ . Since we can iteratively apply $f$ , consider the sequence $\{f^{n}(x)\}_{n = 1}^{\infty}$ . It is not hard to see that this sequence is Cauchy from the contraction of $f$ . Here it is necessary that $k \in [0,1)$ . It follows from the completeness of $X$ that the sequence has a unique limit $x_{0} \in X$ . Now observe

$\displaystyle f(x_{0}) = f\left(\lim_{n \to \infty}f^{n}(x)\right) = \lim_{n \to \infty}f^{n+1}(x) = x_{0}$

where we are permitted to interchange $f$ and the limit since $f$ is continuous. Thus $x_{0}$ is our unique fixed point.

It’s worth mentioning that the contraction affects every $x \in X$ in the sense that every sequence $\{f^{n}(x)\}_{n = 1}^{\infty}$ is converging toward the fixed point $x_{0}$ . So we can think of successive iterations of $f$ as contracting $X$ to $x_{0}$ . Moreover, unlike Brouwe’s fixed point theorem, the contraction mapping theorem is constructive. If you are given a contraction $f$ and want to find its fixed point just pick your favorite $x \in X$ and compute $\lim_{n \to \infty}f^{n}(x)$ !

City Maps and The Contraction Mapping Theorem

Here my favorite example of the contraction mapping theorem which I usually pull out when my non-math friends ask for a fun application of mathematics (which is not all the time, but it happens!):

Let’s suppose you’ve been invited to Minneapolis, Minnesota by a friend and, being unfamiliar with the city, decide to purchase a map so that you don’t get lost. Before venturing out for the day, you humor your friend by showing them an interesting property relating to your map. Moving aside some furniture, you lay the map flat over the floor. You stand up, turn to your friend, and say “ah ha” I can guarantee you that there exists exactly one point on this map that lays directly over the corresponding point on the floor. Your friend replies “surely that can’t be possible for you to know.” With the knowledge of the contraction mapping theorem, you explain that we can treat Minneapolis as a plane and thus as a complete metric space with respect to the Euclidean distance metric. Moreover, the function $f$ that sends a point in Minneapolis to its location on your map is a contraction mapping because the map is much smaller than the city itself (otherwise your map would be a bad map)! Therefore, by the contraction mapping theorem there exists a unique fixed point which is to say there is a point on the map corresponding to the point below it on the floor! Your friend gasps, and with smile you conclude yet another enthusiastic spout of mathematics.

The Modular Perspective

Mathematics for Budding Mathematicians