Two of these things are kind of the same

In november I discussed two famous proofs of the infinitude of primes, arguing that the two proofs are essentially the same. I'd like to play that game again, with a more complicated theorem.

Theorem (Brouwer in two dimensions) Any continuous map $f:D\to D$ from the disk into itself must have a fixed point.

Proof 1 (Algebraic) Assume the contrary. Let $S$ be the circle, and $h:S\to D$ be the embedding identifying $S$ with the boundary of the disk. For each $p\in D$, consider the ray starting at $f(p)$ passing through $p$ (it's unique because $p\neq f(p)$), and let $g(p)$ be the (unique by convexity (and Jordan?)) point at which this ray intersects the boundary $S$. Then $g$ acts as the identity on the boundary; i.e. the diagram

    h       g
S ----> D ----> S
 \_____________/
       id

commutes, and $g$ is continuous (exercise for the reader). But the fundamental groups for $S$ and $D$ are $\Z$ and trivial, respectively, so applying the functor which measures a (path-connected) space's fundamental group (up to isomorphism) gives the patently impossible diagram

    h       g
Z ----> 1 ----> Z
 \_____________/
       id

Contradiction, QED.

Proof 2 (Combinatoric) Instead of the circular disk previously used, consider a triangle with vertices $A = (0,0)$, $B = (1,0)$, and $C = (0,1)$. We need the following lemma:

Lemma (Sperner) Consider a large triangle $ABC$ and a triangulation (which may add points to the boundary of $ABC$, but, being a triangulation, interior triangles never meet corner-to-edge). Color the vertices of this triangulation in the following manner: color $A$ red, $B$ blue, and $C$ yellow; points on the edge $AB$ cannot be yellow, and analogously for the other two edges; interior points can be any of the three colors. Then there must be a red-blue-yellow triangle in the triangulation.

Proof of Lemma Let $ABC$ be colored as above, and for each red-yellow edge place two dots: one on either side of the edge. Then there are definitely an even number of dots in the picture. How many are outside triangle $ABC$? For a dot to be outside, it must come from some edge along $AC$, and as you move from $A$ to $C$, each dot corresponds to a parity change between $A$ and $C$; as the total number of such changes must be odd, there are an odd number of dots outside $ABC$. But an interior triangle without both red and yellow vertices will not contain any dots, and red-yellow-yellow and red-yellow-red triangles contain two dots each. So there must be an odd number of interior red-yellow-blue triangles. qed.

Now finish the proof of Brouwer. Let $f$ be a continuous map without a fixed point from triangle $ABC$ to itself, and color each point by considering the vector $v(p)$ from point $p$ to $f(p)$: If $v(p)$ points into the first quadrant or along the positive $x$- or $y$- axes, color $p$ red; if $v(p)$ is in the fourth quadrant including the negative $y$-axis but excluding the positive $x$-axis, color $p$ yellow; and if $v(p)$ is in the second of third quadrants (i.e. if the $x$-component of $v$ is strictly negative), color $p$ blue. I leave it to the reader to check that every triangulation of $ABC$ colored like this satisfies the statement of Sperner's lemma.

Now consider some triangulation of $ABC$ where every small triangle has diameter less than $1$. This must contain a red-blue-yellow subtriangle $A_1,B_1,C_1$ (labeled so that letters correspond to colors in the obvious way). Now triangulate so that every subtriangle has diameter less than $1/2$; this contains red-blue-yellow subtriangle $A_2,B_2,C_2$. Now again so that all diameters are less than a third, and find $A_3,B_3,C_3$. Continuing in this manner, we get three sequences $A_i$, $B_i$, and $C_i$, so that, for each $j$, the pairwise distances between $A_j$, $B_j$, and $C_j$ are all less than $1/j$. But the triangle is compact, so $A_i$ must have a limit point, i.e. it contains some convergent subsequence $A_{i(j)}$, converging to point $P$. But the corresponding subsequences $B_{i(j)}$ and $C_{i(j)}$ must also converge to $P$, since they get arbitrarily close to the $A_{i(j)}$s.

What color is $P$? Well, $v(A_i)$ is in the first quadrant (or on the boundary) for each $i$, so $v(P)$ must, by continuity of $f$, be in the (closure of) the first quadrant --- i.e. $P$ is a red point. But by the same argument, $v(P)$ must be in the closure of the yellow fourth quadrant, so it must be on the boundary between yellow and red --- i.e. $v(P)$ is on the $x$-axis. But yet again it must be in the closure of the blue half-plane. So the only possibility is for $v(P)$ to be the zero-vector. But we assumed that $f$ had no fixed points, contradiction, QED.



To compare and understand these two proofs, let's run them at the same time. We might as well consider both to take place in a triangle (although, for that matter, Sperner's lemma was combinatorial, and all Proof 2 needed really was that the disk is compact and convex).

The first hint to the proofs' similarity is that both care about the line connecting $p$ with $f(p)$. Sure, the first one uses the ray from $f(p)$ to $p$, the second the vector in the other direction, but by taking negations we might as well care about the vector from $f(p)$ to $p$. And in the second proof we don't care how long the vector $v(p)$ is; we might as well normalize to get $w(p)$ on the unit circle. Of course, $g(p)$ (from the first proof) and $w(p)$ are patently different functions, but letting them act on the boundary $S$ gives two loops in the circle that are, at least, homotopically equivalent. (Intuitively, $g$ asks where the ray meets the unit circle; $w$ asks where it will meet the circle of infinite radius.)

Sperner's lemma hides a lot in Proof 2. To elucidate it, I'll make some small perturbations in the proof and the statement. First, in the proof: instead of placing two dots by each red-yellow edge, I could have placed a $+$ and a $-$, so that, aligning the edge with yellow at the "north" and red at the "south", $+$ is on the "east" side and $-$ is on the "west". Then, summing the pluses and minuses, each region (including the infinite one outside the triangle) has some weight, and the total weight of all the regions is zero. As before, pluses and minuses correspond to changes between red and yellow: traveling counterclockwise around the perimeter, a plus is a move from red to yellow, a minus from yellow to red. So the outside region has total weight $-1$. But the only interior triangles with non-zero weight are the red-blue-yellow (in the counterclockwise direction) triangles with weight $+1$ and the red-yellow-blue triangles with weight $-1$. So there must be exactly one more of the former than the latter.

I can perturb even more: instead of focusing only on triangulations, I can write a "Sperner's lemma" for any partition of the big triangle into (non-overlapping polygonal) cells. If I place pluses and minuses as above, then the entire plane has total weight zero, but the exterior has weight $-1$. But the cool thing about these weights is what happens when you combine two adjacent cells: the weights exactly add. And a cell can only have non-zero weight if it has all three colors along its edges.

What are these weights really? Imagine a complete graph on three vertices $K_3$, where I've labeled the vertices Red, Blue, and Yellow. Then each cell determines a closed loop in $K_3$: as you travel around the perimeter of the cell, call off the colors you see, and I'll travel around $K_3$ by moving to whatever color you call out. Then the weight of your cell is exactly the homotopy class of my loop. Why? Because the number of times you go around a circle is exactly the same as the number of (directed) times you cross any given point (and I've given a point between Red and Yellow; in my original Proof 2 coloring, this point might as well be "the $x$-axis).

Of course, in Proof 2, I only care about the parity of the homotopy class, and now I'm using the full homotopy class, in large part because I'm trying to perturb the proof towards Proof 1, which used $\Z$. Except that it didn't really: all Proof 1 actually used was the fact that the circle has non-trivial fundamental group. The two proofs do indeed cite and prove more and different things — in this way, the truly are different proofs — but strictly as proofs of Brouwer's theorem?

I hid a lot in Proof 1, also, because I assumed that you understand fundamental groups. Which isn't really fair: I certainly don't deeply understand them, although I know how to define, calculate, and prove things about them. Perhaps this is the best possible: von Neumann says that one will never move past "I'm used to" to "I understand". But I think that, at least in this case, a careful study will get pretty close to the ideal.

The standard definition of the fundamental group of a (non-empty path-connected) space $X$ goes like this: Imagine that $X$ has some special point, which I'll call the "origin" $O$, and consider the set of all parameterized paths that start and end at the origin. I.e. all functions $f: [0,1] \to X$ that send both $0$ and $1$ to $O$. There's a natural binary operation on paths: I can concatenate by running one and then the other, at twice the speed. This operation is not associative, sadly, but it is associative up to homotopy-equivalence: two paths are homotopy-equivalent if I can continuously transform one into the other. (More formally, $f$ and $g$ are homotopy-equivalent if there's a map $h: [0,1]^2 \to X$ that sends all $(0,s)$ and $(1,s)$ to $O$, and sends $(t,0)$ to $f(t)$ and $(t,1)$ to $g(t)$. The $t$-component parameterizes the paths, and the $s$ component parameterizes the transformation.) This is, as the reader can check, an equivalence relation, and concatenation is not only associative on equivalence classes, but admits a group structure. A priori, this "fundamental" group depends on choice of origin $O$, and there is no canonical isomorphism between the fundamental group at $O$ and the one at some other point $P$. But, as $X$ is path connected, there is some path between $O$ and $P$, and going along this path, then around a loop, then back provides an isomorphism between said groups. So the fundamental group is well-defines up to isomorphism: it maps the category of path-connected topological spaces to the category of isomorphism classes of groups.

So far so good: I'm guessing that, at least if you've seen this before, the previous paragraph was completely followable. You might even have a pretty deep understanding of what the fundamental group measures. Essentially, it measures how many "holes" are in a given space. Every graph has a free fundamental group, and spaces we care about are generally graphs with disk-shaped patches glued on in weird ways; if you know where the disks are, then you can write down the fundamental group as a presentation (each glued-on disk yields a relation by traversing its perimeter). But what's really interesting for the Brouwer proof is not what fundamental groups are (we only care about the fundamental groups of the disk and the circle), but what their relationships are.

Which is to say, what's interesting is that the function measuring a fundamental group is in fact a functor (what isn't, these days?).

One can prove this in general — the image of a loop under a continuous map is again a loop, and continuous maps respect concatenation and homotopy, but continuous maps can also identify equivalence classes if the range has more ways to transform one loop into another. Even more importantly, composition of continuous maps leads to composition of homomorphisms; I'll leave this (elementary) result to the reader.

But what does this mean in the very specific context of Proof 1? Certainly, after unpacking some definitions, we don't need all the machinery of functors, categories, and commuting diagrams. We don't, for instance, need to show that the fundamental group of the disk is trivial (by convexity, I can continuously retract any loop to a point), or that the fundamental group of the circle is not ($\R$ is a covering space of $S$, and I can declare the preimage of the origin in $S$ to be the set of integers $\Z \subset \R$; each loop, then, lifts to a path starting at $0\in\R$ and ending at some integer, and, moreover, homotopy-equivalence lifts). All that really matters is that the loop traversing the perimeter of the disk is homotopic-equivalent to the trivial loop in the disk, but not in the circle.

So what's Proof 1 actually doing? It says, "Here's these two loops in $S\subset D$: one, which I'll label $S(t)$, traces $S$ (for instance, as $S(t) = e^{2\pi i t}$ if we embed everything into the complex plane); the other, which I'll label $1(t)$, sits at a point ($1(t) = 1$). These are homotopic-equivalent in the disk, but not in the circle." Expanding even more, we can write down an explicit homotopic equivalence and examine it: $h(t,s) = s*(e^{2\pi i t} - 1) + 1$. The question, now, is to ask what happens in the image of this contraction in $S$.

Remember how Proof 1 gets from $D$ to $S$. It says, "I have this continuous function $f:D\to D$ without a fixed point, so let me make a new function $g:D\to S$ that sends $p$ to the intersection of the ray through $f(p)$ and $p$ with the circle." I often like to think of functions as dynamic things: I ought to be able to watch a function change something, imagining, in this case, pushing the points of $D$ out towards the perimeter. This image makes it clear why it can't work, since, intuitively, to do this I'd need to punch a hole in the disk — this is what we're trying to prove. In this case, however, I think it will be more elucidating to think of $g$ as labeling each point in $D$ with some point in $S$. Moreover, I can make this labeling a very visual experience: identify $S$ with the color wheel, moving continuously from red to purple to blue to green to yellow to orange to red, and color each point in $D$ based on what color it ends up after hitting it with $g$.

All of a sudden this is looking more like Proof 2. When perturbing Proof 2 towards Proof 1, we started introducing more and more homotopy-ish ideas. Now we're coloring things!

By watching the colors of the gradually shrinking circle, we can tell how the corresponding loop in $S$ transforms. We start with a loop that hits all the colors in order — how do small perturbations effect this? To visualize: do the same coloring with your paths. Instead of thinking of a time-parameterized loop $Q(t)$ in $S$, think of a continuous coloring of some other circle along which $t$ varies. Perturbations of the path correspond to perturbations of the coloring. And the intuitive point, which I haven't proved (it's roughly equivalent to Brouwer, so yes, I have, a couple times, but bear with me), is that no continuous perturbation, no matter how large, of the original spectrum-coloring of the $t$-circle could ever fail to include all the colors. Think of this as an intermediate-value-theorem result: as I travel around the circle, I start at red, say; I might hit red a lot of times, but there's a first orange, and a last red before the first orange, and I certainly hit all the colors between red and orange just between that "last red before the first orange" and that "first orange"; then there's a "first yellow after the first orange" and a "last orange before that first yellow"; etc. But now go back to the disk. The colors on the shrinking loop must be the same as the colors we just explored, except that at the end we have a loop that stays right near a single color (continuity of our coloring says that a small enough ball around any given point can't include all the colors). This contradiction gives us yet another proof (strongly motivated by Proof 1, sure), or Brouwer's Fixed-Point Theorem.

What happened is that as we blithely retracted out loop, we must have passed through some snag — some "brown" point around which any arbitrarily small loop must run through the entire spectrum. If our coloring is continuous everywhere, no such brown point exists. But Sperner's lemma is a way of finding one.

Remember we ended up describing Sperner's lemma as assigning a weight to each cell in the triangulation based on how many times the colors on the perimeter of the cell move around $K_3$. We could have tried to continuously color the perimeter — for the hypotheses of the lemma, say that the outside edge between the red and blue corners takes values only in the purple range — and measured what are essentially winding numbers for each little cell. Complex analysis, it seems, would give us a proof right away. Except that we're actually begging the question: there's no reason our function need be analytic (continuous functions generally aren't), and for these values to be well-defined we need Brouwer's theorem (or something equivalent to it).

Indeed, there's no particular reason that said brown point should be inside any given red-blue-yellow triangle. You can easily draw two adjacent triangles, one red-blue-yellow and the other red-blue-blue, with the brown point inside the red-blue-blue one. Or even farther away. But there is a sense in which the brown point is "close by".

To whit: I want to measure how colorful each point is, and the way I'm going to do it is by asking (i) what color is the point? (ii) where is the closest point with the color opposite the point's color on the color-wheel? (iii) What is the reciprocal of that distance? This reciprocal I'll call the "colorfulness" of the point; large numbers mean that very differently colored points are close by. When measuring "the distance to the nearest oppositely-colored point", I more properly mean the infimum of such distances, but continuity guarantees me that this infimum is never zero (as I argued in a brief parenthetical four paragraphs above: a small enough ball around any given point can't include all the colors that aren't close to the color of the point). Now here's the coup de grace: this "colorfulness" is a continuous function from the compact disk to the reals, and as such it must be bounded. Which is to say that there is some small epsilon so that any region of diameter less than epsilon cannot include all the colors.

Now it's clear how Proof 2 works. Remember how we took successively finer triangulations? Imagine a triangulation so that every subtriangle has diameter less than epsilon. This triangulation is fine enough to measure all the interesting variations in the coloring of the disk. And, if there are no brown points, then it can't contain a red-yellow-blue subtriangle, by the argument in the previous paragraph (I really ought not to ask for the distance to the nearest opposite-colored point, but to a point that is a third away around the color wheel, but no matter). And yet it has to. (Another proof of Brouwer!) In fact, we can say even more. Let's say that there are a couple brown points, but that we've placed little bubbles, little event horizons around them. Tiny little things, of radius roughly delta. And subtract them out of the disk. Now it's still compact, so the argument goes through, and we can use a fine triangulation that captures all the interesting physical features. Then the only way for a subtriangle to be all of red, blue, and yellow is if it encloses a brown point (er, encloses a point within the event horizon, so it's within delta of the brown point; then make delta, and with it epsilon, smaller). A fine enough triangulation will find your holes for you.

So really Proofs 1 and 2 are measuring much the same things, just coming at the system from slightly different points of view. Proof 1 embraces the continuum, using from the start a continuous coloring, and machinery like the intermediate value theorem and the real numbers. Proof 2 shows how to do the calculations, to whatever accuracy you desire, by using only discreet combinatorial arguments at any given stage. Proof 1 thinks that the universe really exists as a manifold, and Proof 2 counters that you have to be able to measure things. Proof 2 has been reading too much popular quantum gravity: perhaps, it suggests, it's good enough of the universe really is discreet and combinatorial.

I won't claim that Proofs 1 and 2 are really the same. Not only do the use and prove different subsidiary and auxiliary results, but the underlying philosophies are really quite different. I used to prefer Proof 1 as the more demonstrative — the idea that a continuous function can't introduce a hole, but that the circle has one, and that the way you measure "holes" is with these (rather abstract) "fundamental groups" all made sense to me. Proof 2, on the other hand, never seemed particularly elucidative; Sperner's lemma seemed like a trick pulled out of a hat. But, properly explored and explained, I've come to like Proof 2 better. It's much more elementary, eschewing such difficulties of covering spaces and categories. As generally written it's a terrible proof — it's elegant, a la Aigner and Ziegler, but it doesn't explain the underlying physics. I hope, however, that I've delved far enough into it for you to agree with me that it's ultimately more explanatory. Why can't the disk map to itself without a fixed point? Because somewhere any coloring that traverses the spectrum on the boundary must admit a whirlpool, a brown point. And we even have a device for locating and measuring the whirlpools.

No, I won't claim that the two proofs are the same, but they can be perturbed, massaged, and transformed into each other. Not the same — homotopically equivalent.