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 has a fixed point
, that is
, 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
-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 be a complete metric space with metric
and let
be a map. What condition might we want on
to guarantee that
has a fixed point? We might start by noticing that since
is a map from
to
we can apply
iteratively. Then we would like
to keep “shrinking” the image after successive applications, and hope that one of the points in every
for
is a fixed point. The formal notation of shrinking is called contraction. We say
is a contraction mapping if there exists
such that
for all . Stare at this inequality for a moment. The idea is that since
, the inequality says that the distance between points in the image under
is less than the distance between corresponding points in the preimage. In other words,
is shrinking the image in terms of the metric
, or equivalently,
is contracting the distances between points in
.
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 then
is said to be Lipschitz continuous with Lipschitz constant
. So, we can think of contraction mappings as Lipschitz continuous mappings with Lipschitz constant less than
. 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
-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: Letbe 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 be an arbitrary point of
. Since we can iteratively apply
, consider the sequence
. It is not hard to see that this sequence is Cauchy from the contraction of
. Here it is necessary that
. It follows from the completeness of
that the sequence has a unique limit
. Now observe
where we are permitted to interchange and the limit since
is continuous. Thus
is our unique fixed point.
It’s worth mentioning that the contraction affects every in the sense that every sequence
is converging toward the fixed point
. So we can think of successive iterations of
as contracting
to
. Moreover, unlike Brouwe’s fixed point theorem, the contraction mapping theorem is constructive. If you are given a contraction
and want to find its fixed point just pick your favorite
and compute
!
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 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.