Hacker News Reader

Comment by sockaddr | Hacker News Reader

> Brouwer’s fixed point theorem. The theorem says that for any continuous function, there is guaranteed to be one point that the function leaves unchanged — a fixed point, as it’s known. This is true in daily life. If you stir a glass of water, the theorem guarantees that there absolutely must be one particle of water that will end up in the same place it started from.

Wait. What if by stirring I shook the glass and at the end set it back down a foot away from its initial location. Is this author claiming that Brouwer’s theorem guarantees a particle floating somewhere where the glass used to be? Unchanged?

I can imagine an unlimited number of scenarios where I can guarantee the water particles are displaced.

This seems like a bad application of the theorem, right?

View on HN

A better example I've seen for the theorem is that if you take a paper map of a country, messily schrunch it up into a ball and drop it somewhere in the country, there will be at least one point on the map that is exactly above the corresponding real point in the country.

As others have said, it's meant for mappings of the space to itself. So stirring the water, but not moving the glass.

But anyway, the theorem works only for continiuous mappings. The moment they started mentioning "water particles", instead of some hypothetical fluid that is a continuous block, the theorem no longer applied. You could break it by mirroring the position of every particle. There's still a fixed point (the line of mirroring), but there's no obligation that there's a particle on that line.

This still doesnt make sense to me. Imagine a continuous line whose positions map to the real numbers between 0 and 1. If I "move" the line over 0.1 wrapping the end back to the beginning (i.e. x2 = (x1 + 0.1) % 1), there will be no points that are in the same position as they were in before.

EDIT: If you need a continuous function, wouldnt expanding the space to a line from -Inf to +Inf and then using x2 = x1 + 0.1 do the trick?

The theorem only applies to continuous functions.

Brouwer's fixed point theorem only applies to compact convex sets.

Infinite lines don't work, as they are not compact.

Similarly a circle would not work as it is not convex (you're close with your example, you just need to glue together the endpoints to turn it into a circle and make the map continuous).

The line example is what I thought and then I looked the theorem up in Wikipedia. Thanks for pointing this out.

Another practical example is that you're guaranteed to have an annoying spot on your head where the hair sticks straight out and you can't brush it down.

That's actually the one that helped me visualize the theorem. If you look at your scalp from above, you can divide all the hairs into "points left" or "points right" and draw a boundary between them of hairs that point neither left or right. Then you can do the same thing with "points up" and "points down." Where the two kinds of boundaries cross, you have a hair that doesn't point up, down, left, or right - it points straight out of your scalp.

It only applies when you're mapping a space onto itself (plus a couple other qualifications), so you have to put the glass back in the same place.

I think of it as a generalization of the intermediate value theorem - some things are going left, some things are going right, one thing must be sitting still in between.

And: it has to be ‘continuous’. E.g. in ‘real’ water, the molecule of H2O ‘colloquially’ known as ‘number 12345678998776165441’ which sat next to molecule known as ‘number 1’, still has to sit next to it. All be it in a different location. I think something like mayonaise would have been a better example, as water molecules that are ‘next’ to each other can in reality split up quite easily by itself. While something like mayonaise would not.

*off course, quantum mechanics and all that suggesting that it would be impossible to label the individual molecules.

QM doesn't say that it's impossible to label the individual moleccules. However, hydrogens are labile, it makes more sense to identify the unique oxygens.

Are you trying to say that for every point P there exists a neighborhood U around it for which the each transformed point T(P) is contained in the neighborhood T(U)?

What's the conceptual difference between this and the hairy ball theorem?

Loosely, Hairy ball theorem is about the derivative of a mapping at a single point in time. (Imagine slowly deforming/mixing the input configuration t to obtain the output configuration. Brouwer's theorem can be thought of as being about the integral of a continuous family of hairy balls over a time interval.

It's not exactly the same because the assumptions about differentiability are different.

Interesting, thanks!

They left off some qualifiers. According to wikipedia, it's applicable to a continuous function mapping a nonempty compact convex set to itself. Which ends up making a lot more sense to me.

So is it just a fancy way of saying "every transformation has an axis or origin"?

This is also how I interpreted it, which I take it is probably incorrect and would like to know why.

One of the pre-conditions of the theorem is that the domain and codomain are the same. So that's one way to satisfy the theorem. But it's not really intuitive. If you gently swirl a bottle of water, somewhere in the bottle, some water molecule did not move. It's not necessarily in the center of anything. The fixed point could be anywhere. The theorem is about existence only, not construction.

(I am not a professional mathematician, I might also be wrong.)

No, you are on point.

That's not the best way to view it. You can prove it by showing that for an n-dimensional disc, there is no contraction to its boundary; which I think is a bit more illustrative of what this FPT is doing

Well, some continuous functions are simple and it's highly intuitive why this applies to them. Others are very weird and it's not intuitive at all that they should have such a point.

And of course, some functions/transformations are not continuous, and those may not have such an "axis of origin" at all.

I don't quite know what you mean by that, but consider that this is not true for e.g. a torus or a sphere (take the function mapping every point to its antipodal point).

The fact that the underlying space is contractible is very important here.

Isn't a container of water actually a good example? Maybe swirling gently (laminar flow) is a better mental image than shaking vigorously (possibly discontinuous).

Shaking a container is a good example I think, assuming the glass is convex.

Shaking has to be continuous, the particles move quickly and erratically, but they trace continuous paths.

Erratic movement only occurs if the container isn't filled completely. If it is filled completely and the shaking doesn't include any turning/twisting motion, not much happens.

Even then. The required mapping is 'onto' (otherwise, a discontinuous counterexample would be trivial). The air particles are equivalent to the water.

The paths are continuous, but if they move two neighbouring molecules away from each other, the final transformation won't be continuous, will it?

It’s difficult to discuss this physical example because particles are discrete.

In an ideal system with points instead of particles, shaking would be continuous.

And then, we would not call it shaking but bending and twisting, would we?

Think of the 1D variant. If you shuffle a deck of cards, but require that to be ‘continuous’, few shuffles remain (I think only the identity mapping and ‘flipping the deck upside down’). I doubt anybody would restricting the possible permutations that much stil call shuffling.

I don’t think that analogy works because an idealized fluid is point particles, but an idealized deck of cards isn’t.

They both have a concept of neighbors but the deck of cards is simpler, it’s a good illustration, no?

I think point particles are different because there are infinitely many of them. They are more continuous than cards. This means shaking isn’t necessarily discontinuous even if two particles that were “right next to each other” wind up far apart, there should be more particles in between that ended up closer.

It doesn't make sense to me because a glass of water is a discrete set. If we only had two molecules you could just interchange them (with a 180 degree rotation), without any fixed points.

I'd guess the example of the glass of water was made as an afterthought, or as a vivid example of the potential complexity of the theorem. As your example shows, it simply cannot be true. If you think of a vase with marbles, it is also clear. Or if you think of an (ideal) gas in a closed system: would there be at least one particle that always(!) stays in the same place?

Show me a mathematical continuum in the real-world. And this is just the domain, nothing said about the mapping yet (the continuous function). Every analogy has its limits.

The space represented in a flat piece of paper.

The space is continuous even if we can only measure down to the Planck length.

Key here: "represented"

I'm only a mathematician, no physicist. But I think to remember, that the concept of a continuous physical space becomes quite muddled at this scale.

"The space represented by the water in a convex container"

If you get to assume continuous paper, then I get assumed continuous paper.

If you don't want to assume continuity, then you get it back by rephrasing your theorems as "within a margin of error equal to the distance between discrete objects".

The theorem assumes the function has identical domain and codomain. Eg f(x) = x^3 maps [0, 1] to itself.

So that's why they gave the glass stirring example, the domain here is the whole volume of water. So as long as it ends up in the same volume of water, the process of stirring is assumed to be continuous and therefore this theorem applies. Your example changes where it ends up (ie not back to the same domain) and so it cannot be applied.

I'm misunderstanding the theorem. Take f(x) = x + 1. That is a continuous function. But there does not exist an x where f(x) ~ x holds. What am I missing?

That's because there is also a precondition for the domain to be bounded, and since the real numbers are not bounded, the theorem does not apply here (or for any function R -> R).

You can just do the same thing in the integers modulo any value greater than 1, creating a bounded domain without creating a fixed point. I imagine this runs afoul of a different precondition which I haven't identified, though -- it's obviously way more likely than that the entire field has managed to miss something this obvious.

Edit: Actually it's obviously just that this set is not convex, or even continuous.

It must be a compact convex set. The entire reals is not compact.

I do not understand this comment. In what world does "stirring" fluid in a cup imply any sort of dispacement of the cup itself?

You are not just stirring, then

> If you stir a glass of water, the theorem guarantees that there absolutely must be one particle of water that will end up in the same place it started from.

Wait what? If you stir a glass long enough, any configuration of particles should be possible. For instance you can imagine "cutting" the water like a deck of cards.

The full theorem is a continuous mapping back on itself. So, only the water in the glass mapped back to the glass. Pour it out to another glass, and you no longer mapped back to the glass. Pour it back into original glass, and you are back to having a fixed point possible. And, obviously, only with respect to the mapping in the glass.

I wonder how this really applies, since IEEE 754 floating points are not continuous.

As James Bond would say,

https://en.wikipedia.org/wiki/Shaken,_not_stirred

That function is from a compact convex set to itself.

i remember the example of "you can't comb the hair on a coconut without a whorl".

That's a different fixed point theorem.

https://en.m.wikipedia.org/wiki/Brouwer_fixed-point_theorem

Thanks

Reply on news.ycombinator.com