Brouwer fixed point theorem

In 1886, Henri Poincaré proved a result that is equivalent to Brouwer's fixed point theorem. The three-dimensional case of the exact statement was proved in 1904 by Piers Bohl, and the general case in 1910 by Jacques Hadamard. Luitzen Egbertus Jan Brouwer proposed a new proof in 1912.

In mathematics, Brouwer's fixed point theorem is a theorem in topology, named after Luitzen Brouwer. It is one of many fixed point theorems, which state that for any continuous function f with certain properties there is a point x₀ such that f(x₀) = x₀. The simplest form of Brouwer's theorem is for continuous functions f from a disk D to itself. A more general form is for continuous functions from a convex compact subset K of Euclidean space to itself.

Among hundreds of fixed point theorems^[1], Brouwer's is particularly well known, due in part to the fact that it is used across numerous fields of mathematics. In its original field, this result is one of the key theorems characterizing the topology of Euclidean spaces, along with the Jordan curve theorem, the hairy ball theorem or the Borsuk–Ulam theorem.^[2] This gives it a place among the fundamental theorems of topology^[3]. The theorem is also used for proving deep results about differential equations and is covered in most introductory courses on differential geometry. It appears in unlikely fields such as game theory, where John Nash used it to prove the existence of a winning strategy for the game Hex.

The theorem was first studied in view of work on differential equations by the French mathematicians around Poincaré and Picard. Proving results such as the Poincaré–Bendixson theorem requires the use of topological methods. This work at the end of the 19th century opened into several successive versions of the theorem. The general case was first proved in 1910 by Hadamard, and then in 1912 by Luitzen Egbertus Jan Brouwer.

Statement

The theorem has several formulations, depending on the context in which it is used. The simplest is sometimes given as follows:

In the plane

Every continuous function f from a closed disk to itself has at least one fixed point.^[4].

This can be generalized to an arbitrary finite dimension:

In Euclidean space

Every continuous function from a closed ball of a Euclidean space to itself has a fixed point.^[5]

A slightly more general version is as follows:^[6]

Convex compact set

Every continuous function f from a convex compact subset K of a Euclidean space to K itself has a fixed point.^[7]

An even more general form is better known under a different name:

Schauder fixed point theorem

Every continuous function from a convex compact subset K of a Banach space to K itself has a fixed point.^[8]

Notes

The function f in this theorem is not required to be bijective or even surjective. Since any closed ball in Euclidean n-space is homeomorphic to the closed unit ball Dⁿ, the theorem also has equivalent formulations that only state it for Dⁿ.

Because the properties involved (continuity, being a fixed point) are invariant under homeomorphisms, the theorem is equivalent to forms in which the domain is required to be a closed unit ball Dⁿ. For the same reason it holds for every set that is homeomorphic to a closed ball (and therefore also closed, bounded, connected, without holes, etc.).

The statement of the theorem is false if formulated for the open unit disk, the set of points with distance strictly less than 1 from the origin. Consider for example the function

which maps every point of the open unit disk in R² to another point of the open unit disk slightly to the right of the given one.

Illustrations

The theorem has several "real world" illustrations. For example: take two sheets of graph paper of equal size with coordinate systems on them, lay one flat on the table and crumple up (without ripping or tearing) the other one and place it, in any fashion, on top of the first so that the crumpled paper does not reach outside the flat one. There will then be at least one point of the crumpled sheet that lies directly above its corresponding point (i.e. the point with the same coordinates) of the flat sheet. This is a consequence of the n = 2 case of Brouwer's theorem applied to the continuous map that assigns to the coordinates of every point of the crumpled sheet the coordinates of the point of the flat sheet immediately beneath it.

In three dimensions the consequence of the Brouwer fixed point theorem is that no matter how much you stir or shake a cocktail in a glass some point in the liquid will remain in the exact same place in the glass as before you took any action, assuming that the final position of each point is a continuous function of its original position, and that the liquid after stirring or shaking is contained within the space originally taken up by it.

Another consequence of the case n = 3 is given by an informational display of a map in, for example, an airport terminal. The function that sends points of the terminal to their image on the map is continuous and therefore has a fixed point, usually indicated by a cross or arrow with the text You are here. A similar display outside the terminal would violate the condition that the function is "to itself" and fail to have a fixed point. For this example, the existence of a fixed point is also a consequence of the Banach fixed point theorem, since the function mapping points in space to the display is a contraction mapping.

Intuitive approach

Explanations attributed to Brouwer

The theorem is supposed to have originated from Brouwer's observation of a cup of coffee.^[9] If one stirs to dissolve a lump of sugar, it appears there is always a point without motion. He drew the conclusion that at any moment, there is a point on the surface that is not moving.^[10] The fixed point is not necessarily the point that seems to be motionless, since the centre of the turbulence moves a little bit. The result is not intuitive, since the original fixed point may become mobile when another fixed point appears.

Brouwer is said to have added: "I can formulate this splendid result different, I take a horizontal sheet, and another identical one which I crumple, flatten and place on the other. Then a point of the crumpled sheet is in the same place as on the other sheet."^[10] Brouwer "flattens" his sheet as with a flat iron, without removing the folds and wrinkles.

One-dimensional case

In one dimension, the result is intuitive and easy to prove. The continuous function f is defined on a closed interval [a, b] and takes values in the same interval. Saying that this function has a fixed point amounts to saying that its graph (black in the figure on the right) intersects that of the function defined on the same interval [a, b] which maps x to x (green).

Intuitively, any continuous line from the left edge of the square to the right edge must necessarily intersect the green diagonal.

It is not hard to give a formal proof. It suffices to consider the function g which maps x to f(x) - x. It is ≥ 0 on a and ≤ 0 on b. By the intermediate value theorem, g has a zero in [a, b]; this zero is a fixed point.

Brouwer is said to have expressed this as follows: "Instead of examining a surface, we will prove the theorem about a piece of string. Let us begin with the string in an unfolded state, then refold it. Let us flatten the refolded string. Again a point of the string has not changed its position with respect to its original position on the unfolded string."^[10]

Two-dimensional case

In the plane, an intuitive argument shows that the result is probably true. Nevertheless the proof is tricky. If K, the domain of f, has empty interior, then it is a line segment. Otherwise K is homeomorphic to a closed unit ball, i.e. there is a homeomorphism φ: D² → K from the closed unit ball to K. The equation defining the fixed point can therefore be written as h(x) = x, where h denotes the composed function .

In other words, one can assume that K is a closed unit ball. The norm can moreover be chosen arbitrarily. Choosing the maximum norm (the maximum of the absolute values of the coordinates) shows that without loss of generality K can be assumed to be the set [-1, 1]×[-1, 1].

Denoting by g the function that maps x to h(x) - x, the goal is to prove that the zero vector is in the image of g on [-1, 1]×[-1, 1]. If g_k, for k equal to 1 or 2, are the two coordinate functions of g, this amounts to proving the existence of a point x₀ such that g₁ and g₂ both have a zero at x₀.

The function g₁ goes from [-1, 1]×[-1, 1] to [-1, 1]. It can be interpreted as a map of a region which indicates the altitude of every point (see first figure on the right). In the area {-1}×[-1, 1], this altitude is ≥0 (red in the figure), while on {1}×[-1, 1] it is ≤0 (blue). This suggests that the contour line 0 is a line (green in the figure) from a point in [-1, 1]×{1} to a point in [-1, 1]×{-1}. The same reasoning applied to g₂ suggests that the contour line 0 is this time a line from somewhere in {-1}×[-1, 1] to somewhere in {1}×[-1, 1] (see yellow line in the second figure).

Intuitively, it seems obvious that these two contour lines (green and yellow) must necessarily intersect, and the point of intersection is a fixed point of foφ. Verifying this intuition is not as easy as it appears. The green zone is not necessarily a connected line, not even necessarily a line. In fact, it does not even have to contain a line!

Finite-dimensional case

The intuitive approach of the previous section generalizes to any finite dimension. To understand how, it is sufficient to look at dimension 3.

The goal is again to prove that the function g, which now has three coordinates, has a zero. The first coordinate is ≥ 0 on the left face of the cube and ≤ 0 on the right face. There is every reason to think that the set of zeros contains a sheet, shown in blue in the figure on the right. This sheet cuts the cube into two connected components, one containing part of the right face and one containing part of the left face.

Assuming that the y axis is in front-back direction, the same reasoning suggests the existence of a sheet, shown in green in the figure, which also cuts the cube into at least two connected components. The intersection of the two sheets probably contains a line, depicted in yellow, going from the upper face to the lower face.

Now the third component of g describes a face shown in red. It appears that this sheet must intersect the yellow line. The point of intersection is the desired fixed point.

History

The Brouwer fixed point theorem was one of the early achievements of algebraic topology, and is the basis of more general fixed point theorems which are important in functional analysis. The case n = 3 first was proved by Piers Bohl in 1904 (published in Journal für die reine und angewandte Mathematik). It was later proved by L. E. J. Brouwer in 1909. Jacques Hadamard proved the general case in 1910, and Brouwer found a different proof in 1912. Since these early proofs were all non-constructive indirect proofs, they ran contrary to Brouwer's intuitionist ideals. Methods to construct (approximations to) fixed points guaranteed by Brouwer's theorem are now known, however; see for example (Karamadian 1977) and (Istrăţescu 1981).

Prehistory

For flows in an unbounded area, or in an area with a "hole", the theorem is not applicable.

The theorem applies to any disk-shaped area, where it guarantees the existence of a fixed point.

To understand the prehistory of Brouwer's fixed point theorem one needs to pass through differential equations. At the end of the 19th century, the old problem^[11] of the stability of the solar system returned into the focus of the mathematical community.^[12] Its solution required new methods. As noted by Henri Poincaré, who worked on the three-body problem, there is no hope to find an exact solution: "Nothing is more proper to give us an idea of the hardness of the three-body problem, and generally of all problems of Dynamics where there is no uniform integral and the Bohlin series diverge."^[13] He also noted that the search for an approximate solution is no more efficient: "the more we seek to obtain precise approximations, the more the result will diverge towards an increasing imprecision."^[14].

He studied a question analogous to that of the surface movement in cup of coffee. What can we say, in general, about the trajectories on a surface animated by a constant flow?^[15] Poincaré discovered that the answer can be found in what we now call the topological properties in the area containing the trajectory. If this area is compact, i.e. both closed and bounded, then the trajectory either becomes stationary, or it approaches a limit cycle.^[16] Poincaré went further; if the area is of the same kind as a disk, as is the case for the cup of coffee, there must necessarily be a fixed point. This fixed point is invariant under all functions which associate to each point of the original surface its position after a short time interval t. If the area is a circular band, or if it is not closed^[17], then this is not necessarily the case.

To understand differential equations better, a new branch of mathematics was born. Poincaré called it analysis situs. The French Encyclopædia Universalis defines it as the branch which "treats the properties of an object that are invariant if it is deformed in any continuous way, without tearing"^[18]. In 1886, Poincaré proved a result that is equivalent to Brouwer's fixed point theorem^[19], although the connection with the subject of this article was not yet apparent^[20]. A little later, he developed one of the fundamental tools for better understanding the analysis situs, now known as the fundamental group or sometimes the Poincaré group.^[21]. This method can be used for a very compact proof of the theorem under discussion.

Poincaré's method was analogous to that of Emile Picard, a contemporary mathematician who generalized the Cauchy–Lipschitz theorem.^[22]. Picard's approach is based on a result that would later be formalised by another fixed point theorem, named after Banach. Instead of the topological properties of the domain, this theorem uses the fact that the function in question is a contraction.

First proofs

Hadamard played the role of a midwife, helping Brouwer to formalize his ideas.

At the dawn of the 20th century, the interest in analysis situs did not stay unnoticed. However, the necessity of a theorem equivalent to the one discussed in this article was not yet evident. Piers Bohl, a Latvian mathematician, applied topological methods to the study of differential equations.^[23]. In 1904 he proved the three-dimensional case of our theorem, but his publication was not noticed.^[24].

It was Brouwer, finally, who gave the theorem its first patent of nobility. His goals were different from those of Poincaré. This mathematician was inspired by the foundations of mathematics, especially mathematical logic and topology. His initial interest lay in an attempt to solve Hilbert's fifth problem.^[25] In 1909, during a voyage to Paris, he met Poincaré, Hadamard and Borel. The ensuing discussions convinced Brouwer of the importance of a better understanding of Euclidean spaces, and were the origin of a fruitful exchange of letters with Hadamard. For the next four years, he concentrated on the proof of certain great theorems on this question. In 1912 he proved the hairy ball theorem for the two-dimensional sphere, as well as the fact that every continuous map from the two-dimensional ball to itself has a fixed point.^[26]. These two results in themselves were not really new. As Hadamard observed, Poincaré had shown a theorem equivalent to the hairy ball theorem^[27]. The revolutionary aspect of Brouwer's approach was his systematic use of recently developed tools such as homotopy, the underlying concept of the Poincaré group. In the following year, Hadamard generalised the theorem under discussion to an arbitrary finite dimension, but he employed different methods. H. Freudenthal comments on the respective roles as follows: "Compared to Brouwer's revolutionary methods, those of Hadamard were very traditional, but Hadamard's participation in the birth of Brouwer's ideas resembles that of a midwife more than that of a mere spectator."^[28].

Brouwer's approach yielded its fruits, and in 1912 he also found a proof that was valid for any finite dimension.^[29], as well as other key theorems such as the invariance of dimension^[30]. In the context of this work, Brouwer also generalized the Jordan curve theorem to arbitrary dimension and established the properties connected with the degree of a continuous mapping.^[31]. This branch of mathematics, originally envisioned by Poincaré and developed by Brouwer, changed its name. In the 1930s, analysis situs became algebraic topology.^[32].

Brouwer's celebrity is not exclusively due to his topological work. He was also the originator and zealous defender of a way of formalising mathematics that is known as intuitionism, which at the time made a stand against set theory.^[33]. While Brouwer preferred constructive proofs, ironically, the original proofs of his great topological theorems were not constructive^[34], and it took until 1967 for constructive proofs to be found.^[35]

Reception

John Nash used the theorem in game theory to prove the existence of a winning strategy.

The theorem proved its worth in more than one way. During the 20th century numerous fixed point theorems were developed, and even a branch of mathematics called fixed point theory.^[36] Brouwer's theorem is probably the most important.^[37] It is also among the foundational theorems on the topology of topological manifolds and is often used to prove other important results such as the Jordan curve theorem.^[38]

Besides the fixed point theorems for more or less contracting functions, there are many that have emerged directly or indirectly from the result under discussion. A continuous map from a closed ball of Euclidean space to its boundary cannot be the identity on the boundary. Similarly, the Borsuk–Ulam theorem says that a continuous map from the n-dimensional sphere to Rⁿ has a pair of antipodal points that are mapped to the same point. In the finite-dimensional case, the Lefschetz fixed point theorem provided from 1926 a method for counting fixed points. In 1930, Brouwer's fixed point theorem was generalized to Banach spaces.^[39]. This generalization is known as Schauder's fixed point theorem, a result generalized further by S. Kakutani to multivalued functions.^[40] One also meets the theorem and its variants outside topology. It can be used to prove the Hartman-Grobman theorem, which describes the qualitative behaviour of certain differential equations near certain equilibria. Similarly, Brouwer's theorem is used for the proof of the théorème de la variété centrale. The theorem can also be found in existence proofs for the solutions of certain partial differential equations.^[41]

Other areas are also touched. In game theory, John Nash used the theorem to prove that in the game of Hex there is a winning strategy for white.^[42]. In economy, P. Bich explains that certain generalizations of the theorem show that its use is helpful for certain classical problems in game theory and generally for equilibria (Hotelling's law), financial equilibria and incomplete markets.^[43]

Proof outlines

A full proof of the theorem would be too long to reproduce here, but the following outlines a proof omitting the most difficult part. The proof uses the observation that the boundary of Dⁿ is S^n − 1, the (n − 1)-sphere.

Illustration of the retraction F

The argument proceeds by contradiction, supposing that a continuous function f : Dⁿ → Dⁿ has no fixed point, and then attempting to derive an inconsistency, which proves that the function must in fact have a fixed point. For each x in Dⁿ, there is only one straight line that passes through f(x) and x, because it must be the case that f(x) and x are distinct by hypothesis (recall that f having no fixed points means that f(x) ≠ x). Following this line from f(x) through x leads to a point on S^n − 1, denoted by F(x). This defines a continuous function F : Dⁿ → S^n − 1, which is a special type of continuous function known as a retraction: every point of the codomain (in this case S^n − 1) is a fixed point of the function.

Intuitively it seems unlikely that there could be a retraction of Dⁿ onto S^n − 1, and in the case n = 1 it is obviously impossible because S⁰ (i.e., the endpoints of the closed interval D¹) is not even connected. The case n = 2 is less obvious, but can be proven by using basic arguments involving the fundamental groups of the respective spaces: the retraction would induce an injective group homomorphism from the fundamental group of S¹ to that of D², but the first group is isomorphic to Z while the latter group is trivial, so this is impossible. The case n = 2 can also be proven by contradiction based on a theorem about non-vanishing vector fields.

For n > 2, however, proving the impossibility of the retraction is more difficult. One way is to make use of homology groups: it can be shown that the homology H_n − 1(Dⁿ) is trivial, while H_n − 1(S ^n − 1) is infinite cyclic. This shows that the retraction is impossible, because again the retraction would induce an injective group homomorphism from the latter to the former group.

There is also a more elementary combinatorial proof, whose main step consists in establishing Sperner's lemma in n dimensions.

There is also a quick proof, by Morris Hirsch, based on the impossibility of a differentiable retraction. The indirect proof starts by noting that the map f can be approximated by a smooth map retaining the property of not fixing a point; this can be done by using the Weierstrass approximation theorem, for example. One then defines a retraction as above which must now be differentiable. Such a retraction must have a non-singular value, by Sard's theorem, which is also non-singular for the restriction to the boundary (which is just the identity). Thus the inverse image would be a 1-manifold with boundary. The boundary would have to contain at least two end points, both of which would have to lie on the boundary of the original ball—which is impossible in a retraction.

A quite different proof given by David Gale is based on the game of Hex. The basic theorem about Hex is that no game can end in a draw. This is equivalent to the Brouwer fixed point theorem for dimension 2. By considering n-dimensional versions of Hex, one can prove in general that Brouwer's theorem is equivalent to the determinacy theorem for Hex. ^[44]

Generalizations

The Brouwer fixed point theorem forms the starting point of a number of more general fixed point theorems.

The straightforward generalization to infinite dimensions, i.e. using the unit ball of an arbitrary Hilbert space instead of Euclidean space, is not true. The main problem here is that the unit balls of infinite-dimensional Hilbert spaces are not compact. For example, in the Hilbert space ℓ² of square-summable real (or complex) sequences, consider the map f : ℓ² → ℓ² which sends a sequence (x_n) from the closed unit ball of ℓ² to the sequence (y_n) defined by

It is not difficult to check that this map is continuous, has its image in the unit sphere of ℓ², but does not have a fixed point.

The generalizations of the Brouwer fixed point theorem to infinite dimensional spaces therefore all include a compactness assumption of some sort, and in addition also often an assumption of convexity. See fixed point theorems in infinite-dimensional spaces for a discussion of these theorems.

The Kakutani fixed point theorem generalizes the Brouwer fixed point theorem in a different direction: it stays in Rⁿ, but considers upper semi-continuous correspondences (functions that assign to each point of the set a subset of the set). It also requires compactness and convexity of the set.

By using forcing to collapse cardinals, the Brouwer fixed point theorem can be generalized to arbitrary cardinality: if L is a compact, connected order topology, then any continuous function from Lⁿ to itself has a fixed point. Note that if we require L to be separable, this is precisely the Brouwer fixed point theorem.

The Lefschetz fixed-point theorem applies to (almost) arbitrary compact topological spaces, and gives a condition in terms of singular homology that guarantees the existence of fixed points; this condition is trivially satisfied for any map in the case of Dⁿ.

See also

• Tucker's lemma
• Topological combinatorics

Notes

References

• Sobolev, V. I. (2001), "Brouwer theorem", in Hazewinkel, Michiel, Encyclopaedia of Mathematics, Kluwer Academic Publishers, ISBN 978-1556080104, http://eom.springer.de/B/b017670.htm 
• Gale, D. (1979). "The Game of Hex and Brouwer Fixed-Point Theorem". The American Mathematical Monthly 86: 818–827. doi:10.2307/2320146. 
• Morris W. Hirsch, "Differential Topology", Springer, 1980 (see p. 72-73 for Hirsch's proof utilizing non-existence of a differentiable retraction)
• S. Karamadian (ed.), Fixed points. Algorithms and applications, Academic Press, 1977
• V.I. Istrăţescu, Fixed point theory, Reidel, 1981

External links

• Brouwer's Fixed Point Theorem for Triangles at cut-the-knot
• Brouwer theorem, from PlanetMath with attached proof.
• Reconstructing Brouwer at MathPages