The Brouwer fixed point theorem states that any continuous function sending a compact convex set onto itself contains at least one fixed point, i.e. a point satisfying . For example, given two similar maps of a country of different sizes resting on top of each other, there always exists a point that represents the same place on both maps.
The simplest examples of a compact convex set are
- a closed interval in the real numbers
- a closed disk (the region enclosed by a circle)
- any convex region in the plane, i.e. a region such that for any two points in , the segment lies entirely in
and thus Brouwer's fixed point theorem applies to all these examples.
Brouwer's fixed point theorem is useful in a surprisingly wide context, with applications ranging from topology (where it is essentially a fundamental theorem) to game theory (as in Nash equilibrium) to cake cutting.
There are a number of real-world examples that illustrate Brouwer's theorem, though they are somewhat counterintuitive. The most famous is the following:
Consider a map of a country. If that map is placed anywhere in that country, there will always be a point on the map that represents that exact point in the country.
Given two similar maps of a country of different sizes resting on top of each other, there always exists a point that represents the same place on both maps.
This holds for any mapping, including ones where the region is rotated. In the following mapping defined by a rotation, the center of the triangle is a fixed point:
Here is another example:
Which of the following best describes the probability that at a given time, there are two antipodes (points that are directly across from each other on the earth) with the same temperature and the same humidity?
Image Credit: Wikimedia Commons.
The result of this is an application of the Borsuk-Ulam theorem. The Borsuk-Ulam theorem implies the Brouwer fixed point theorem.
A compact set is one that is both bounded and closed, meaning the following:
- All points lie within a fixed distance of another (intuitively, nothing gets infinitely large). There exists a number such that is less than or equal to whatever might be the value of in the domain.
- The set contains all of its limit points; i.e. if a sequence of points in the set approaches some value , the set also contains .
For instance, is not bounded, as its elements get infinitely large; it is, however, closed. The interval is not closed, as the limit points and are not part of the interval, though the interval is bounded (all points are within 2 of each other).
A convex set was previously defined above.
Brouwer's theorem states that if is a compact convex set, and is a continuous function, then there exists a point such that . Note that all of these conditions are necessary; for instance, the function
does indeed take the region to itself, but has no fixed points. Similarly, the function
also takes the region to itself, but also has no fixed points the function , however, has a fixed point at 1
In the one-dimensional case of Brouwer's theorem, the theorem states
Given a continuous function , there exists a such that .
In fact, this statement is an immediate consequence of the intermediate value theorem, and also has a very intuitive graphical interpretation:
Here, the statement is equivalent to
Any continuous path (dark green in the picture) from the left side to the right side must intersect the green line at some point.
which is intuitively clear.
Brouwer's theorem is notoriously difficult to prove, but there is a remarkably visual and easy-to-follow (if somewhat unmotivated) proof available based on Sperner's lemma.
Define the -simplex to be the set of all -dimensional points whose coordinates sum to 1. The most interesting case is , as higher dimensions follow via induction (and are much harder to visualize); in this case, the 2-simplex is simply a triangle. A triangulation of this triangle is a division into smaller triangles:
A Sperner coloring of this triangulation is one that satisfies
- each vertex is colored with one of (3 in the 2-dimensional case) colors;
- the vertices that lie on an -face of the simplex (the edges of the large triangle in the 2-dimensional case) are colored only with the colors on the corners of that face (the vertices of the large triangle in the 2-dimensional case).
Then Sperner's lemma states as follows:
For any Sperner coloring of a triangulation of a simplex, there exists an element of the triangulation (a small triangle) whose corners all have different colors.
Indeed, the above Sperner coloring does contain such a triangle (in the lower right).
Now consider the coloring as a "house" with "doors" at every edge whose endpoints are red and green. It is necessary first to show that the boundary has an odd number of doors. But only one side of the large triangle can contain doors, since points are colored the same as one of the two main vertices, and there are clearly an odd number of them as each door denotes an alternation of colors (and at the end, the colors have alternated).
Now consider a path through the triangle starting at some point outside the triangle and walking only through doors. This path ends by either
- walking outside the triangle, or
- entering a red-green-blue triangle (since there is nowhere to go from there).
Furthermore, once the triangle is entered, the path is completely determined, as no triangle has 3 red-green edges. This means that no two paths meet in a single small triangle.
Now the key point: a path that ends outside the triangle determines two doors on the boundary of the large triangle, while entering a red-green-blue triangle determines only one. But there are an odd number of doors on the boundary of the large triangle, so some path must have entered a red-green-blue triangle, so a red-green-blue triangle must exist! This proves Sperner's lemma.
Now we show that Sperner's lemma implies Brouwer's theorem. For each point in a simplex, let be its image. Consider the vector , which points towards some corners of the simplex and away from some. Color with the color of the vertex it points most away from (choosing arbitrarily in the case of a tie).
It is relatively easy to see that this satisfies the Sperner coloring constraints: any point on an edge will point most away from one of the two vertices defining that edge, so it will be colored with one of those two colors. Thus, by Sperner's lemma there exists a small triangle whose vertices all have different colors. Repeating this process on the points inside this triangle infinitely gives a point that should be all three colors at the same time, which is possible only if that point is a fixed point (as the resulting vector is then not pointing towards any vertex). This demonstrates a fixed point exists for any continuous from the simplex to the simplex, and since a simplex is homeomorphic to a closed ball, this demonstrates Brouwer's theorem.