Tuesday, November 13, 2012

Brouwer's Fixed-Point Theorem: A Proof in the Works

Brouwer's fixed-point theorem goes thusly: if you hold two equal-sized sheets of paper, one above the other, and then crumpled the top sheet into a ball (while still keeping it above the bottom sheet), there will be one point on the top sheet that is still directly above the same point on the bottom sheet. It's a little bit difficult to wrap one's mind around, so I tried to find an image that would illustrate the idea.

The above image uses circular planes instead of rectangular ones, so I hope you can cope with that. But besides that, it's quite nice. Function f is the act of crumbling the paper, and, as you can see, point a remains unchanged. The location of a depends on how exactly you choose to crumple the paper, but it will always exist somewhere. Or so goes the theorem. We decided to prove it.

So, first, we decided to head back into two dimensions, where we felt more at home. In the second dimension, we must imagine two lines above one another, rather than two planes, but the concept is the same: transform the top plane, and one point on it will always remain at the same x coordinate once all the changes are made.

Here is our starting point. Now, let's make some transformations. First, we can translate.

If the line is six units long, the top line has been moved two units to the right. But we can't be done here, because the top line is no longer fully above the second one. So we must transform again.

Now, the top line is fully above the bottom, and every point has been moved at least once. The top line is officially 'crumpled', albeit simply. So, let's take a closer look. Is there a point on the top line that is aligned with its partner on the bottom? 

Well, if there is, it is obviously between point 4 and point 6, as everything else has been shifted to the left. All the points between 4 and 6 were shifted to left in step one as well, but they were then folded back to the right in step two, which, you'll remember, was necessary in order to balance out the offsetting of the translation. So, among the points between 4 and 6, it cannot be below 5, because the points between 4 and 5 on the top line do not overlap whatsoever with the points between 4 and 5 on the bottom. Just by looking at it, we can surmise that the point, is somewhere just above 5 - in a perfect world, we could approximate it to an infinitely accurate degree by counting points on both lines. Now, onto the cool bit: how do we prove this?

The answer lies in these two principles: the numbers we chose to mark units on the lines are completely arbitrary, and we can eliminate possible points based on our markers. Armed with these two facts, we can narrow down the possible locations of this point until we reach one remaining conclusion. For example, in our above example, the only conclusion we were able to reach was that the point lies somewhere just above 5 - not a very satisfying result. But what if we had decided to make the line 12 units long rather than 6, putting another marker between 5 and 6 (which would then be 10 and 12). Well, that would give us some more information (i.e., it can't be between 11 and 12, because the points between 11 and 12 on the top line do not overlap whatsoever with the same points on the bottom line). And you see if we added more markers, that would give us even more information as to where it cannot be, and we can do this to an infinite degree.

This is about where we are so far. There were a few more stray ideas out there, but this is the meat of it. This example illustrates that translating must be counteracted in some way so as to keep it from misaligning the two planes, and that counteraction can be measured in terms of knowable markers. I would hope the ideas carry over into 3D, but there is much we haven't accounted for (such as other forms of transformation), and there is much work to be done. So, I'll turn this one over to you guys.

Problem Solving by Jack E., Vikram A., William S., and Justin L.

Writeup by Jack E.

No comments:

Post a Comment