Brouwer Fixed Point Theorem

The Brouwer fixed point theorem states that any continuous function \(f\) sending a compact convex set onto itself contains at least one fixed point, i.e. a point \(x_0\) satisfying \(f(x_0)=x_0\). 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 \(R\) such that for any two points \(X,Y\) in \(R\), the segment \(XY\) lies entirely in \(R,\)

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.

Equivalently,

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 marked point, somewhere in Oklahoma, represents the same point on both copies of these maps of the U.S.

This holds for any mapping, including ones where the region is rotated. In the following mapping defined by a \(60^{\circ}\) rotation, the center of the triangle is a fixed point:

Here is another example:

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 \(L\) such that \(f(x)\) is less than or equal to \(L\) whatever might be the value of \(x\) in the domain.
• The set contains all of its limit points; i.e. if a sequence of points in the set approaches some value \(L\), the set also contains \(L\).

For instance, \(\mathbb{R}\) is not bounded, as its elements get infinitely large; it is, however, closed. The interval \((-1,1)\) is not closed, as the limit points \(-1\) and \(1\) 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 \(R\) is a compact convex set, and \(f:R \rightarrow R\) is a continuous function, then there exists a point \(x_0\) such that \(f(x_0)=x_0\). Note that all of these conditions are necessary; for instance, the function

\[f:\mathbb{R} \rightarrow \mathbb{R},\ f(x)=x+1\]

does indeed take the region \(\mathbb{R}\) to itself, but has no fixed points. Similarly, the function

\[f:(0,1) \rightarrow (0,1),\ f(x)=\frac{x+1}{2}\]

also takes the region \((0,1)\) to itself, but also has no fixed points \(\big(\)the function \(f:[0,1] \rightarrow [0,1], f(x)=\frac{x+1}{2}\), however, has a fixed point at 1\(\big).\)

In the one-dimensional case of Brouwer's theorem, the theorem states

Given a continuous function \(f:[a,b] \rightarrow [a,b]\), there exists a \(c \in [a,b]\) such that \(f(c)=c\).

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 \(n\)-simplex to be the set of all \(n\)-dimensional points whose coordinates sum to 1. The most interesting case is \(n=2\), 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 triangulation of a 2-simplex

A Sperner coloring of this triangulation is one that satisfies

• each vertex is colored with one of \(n+1\) (3 in the 2-dimensional case) colors;
• the vertices that lie on an \((n-1)\)-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).

A Sperner coloring of the above triangulation

Then Sperner's lemma states as follows:

Sperner's Lemma:

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.

The path through the only door on the boundary ends in a red-green-blue triangle, as expected.

Now we show that Sperner's lemma implies Brouwer's theorem. For each point \(P\) in a simplex, let \(f(P)\) be its image. Consider the vector \(v=f(P)-P\), which points towards some corners of the simplex and away from some. Color \(P\) 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 \(f\) from the simplex to the simplex, and since a simplex is homeomorphic to a closed ball, this demonstrates Brouwer's theorem.

• Fair Division
• Nash Equilibrium
• Homeomorphism
• Topology