The pancake theorem

A previous post mentioned the Borsuk–Ulam theorem. A corollary (for the case of a circle) is the pancake theorem: given two plane regions, there is a cut (line) which divides both in half by area.

The example shows a cut dividing both South America and Africa in half (the theorem doesn’t tell us how to find the cut; I used simulated annealing).

The corollary for the 2-sphere is the ham sandwich theorem: given three 3-dimensional objects, there is a cut (plane) which divides all three in half by volume.


The Borsuk–Ulam theorem

The mathematical tidbit for today is the Borsuk–Ulam theorem, which states that every continuous function f from the n-dimensional sphere to n-dimensional space must satisfy f(p) = f(−p) for some point p.

In particular, every continuous function f from a 2-dimensional sphere (say, the Earth’s surface) to the plane must satisfy f(p) = f(q) for some antipodal pair of points p and q.

Thus, if we can describe weather by a pair of numbers (say, temperature and rainfall), there must be an antipodal pair of points p and q with the same weather (because two numbers specify a point in the plane).

The maps above (for average maximum temperature) and below (for rainfall) show July weather at various places on Earth, and a pair of points with the same weather is highlighted.

It’s a miracle that it works in this case, of course, because the maps only define temperature and rainfall on the land; I would not have been able to recognise a suitable antipodal pair of points if one or both were at sea.


The Projective Plane

I have been thinking some more about the famous Möbius strip (see also my post on the Klein bottle). The so-called “Sudanese Möbius Band” in the video above is a Möbius strip stretched so as to make the boundary perfectly circular (it is not named after the country, but after the topologists Sue E. Goodman and Daniel Asimov, and you can purchase a plastic one here).

If we glue two of these Möbius strips together (not actually possible in 3 dimensions), we get a Klein bottle. If we glue one to a disc (also not possible in 3 dimensions), we get a projective plane.

Just for fun, the video below shows a Game of Life glider on the projective plane. The top and bottom of the square are considered to be joined, as are the left and right sides. In both cases, there is a reversal of orientation (a manoeuvre not really possible in 3 dimensions). The glider changes colour as it changes orientation.

Video produced using the R animation package.


The Klein Bottle

I have been thinking about the famous Klein bottle (above). To quote a limerick by Leo Moser:

A mathematician named Klein
Thought the Möbius band was divine.
Said he: “If you glue
The edges of two,
You’ll get a weird bottle like mine.”

Just for fun, here is a Game of Life glider on a Klein bottle. The top and bottom of the square are considered to be joined, so as to form a tube. The ends of the tube (vertical sides of the square) are also joined, but with a reversal of orientation (a manoeuvre not really possible in three dimensions). The glider changes colour as it changes orientation.

Video produced using the R animation package.


All about fixed points

In mathematics, a fixed point of a function f is a value x such that f(x) = x. For example, Wolfram notes that cos(0.7390851332) = 0.7390851332. There need not be such a fixed point, of course, but it is interesting when there is.

Unique fixed points

The Banach fixed-point theorem applies to complete metric spaces – sets where there is a concept of distance and where convergent sequences have a limit.

If f is a function that shrinks things – if, say, the distance between f(x) and f(y) is at most 50%, or 90%, or 99.99999% of the distance between x and y – then the function f will not only have a fixed point, but that fixed point will be unique.

Intuitively, this is clear. You apply the function f to the whole set an infinite number of times, and everything shrinks down to a single point satisfying f(x) = x.


Comic 688 by xkcd, with the fixed point highlighted in pink

It follows that if you stand inside a country, city, or home holding (horizontally) a map of that country, city, or home, then exactly one point in the country, city, or home is exactly underneath the corresponding point on the map. More usefully, this theorem has been used to assign meaning to recursive type expressions in computer science.

Iterated function systems

Iterated function systems are one way of defining fractals. An iterated function system is a family of functions, each of which shrinks things (i.e. is contractive). This family of functions defines a Hutchinson operator on sets of points, and that operator is in turn contractive for a certain definition of distance between sets (see Hutchinson, 1981).

Consequently, that operator has a unique “fixed point,” which is in fact a set of points, like the famous Barnsley fern. The set of points can be (approximately) generated by an iterative process (see code example here):

Least fixed points

As another example of fixed points in action, the Kleene fixed-point theorem assigns meaning to recursively defined computer programs, like these:

  • x = x, a circular definition which is satisfied by infinitely many things, defines x = ⊥, the least defined of all those things
  • z = 0 ⊙ (1 + z), where “” means putting a number in front of a list, defines the infinite list z = 0, 1, 2, 3, 4, 5, …
  • g = function (x) { if (x = 0) then 1 else x * g(x − 1) }, defines g to be the factorial function

Computer programs are modelled by Scott-continuous functions on a partial order where ⊥ is the least element (⊥ means “no information” and is the meaning of any computer program stuck in an infinite loop). Scott-continuous functions may have more than one fixed point, but they have a unique least fixed point, which is the limit of the sequence ⊥ ⊑ f(⊥) ⊑ f(f(⊥)) ⊑ …

This sequence corresponds to what actually happens when the computer attempts to execute recursive definitions like the three in red above.

Brouwer’s fixed point theorem

Even more interesting is Brouwer’s fixed-point theorem. Any continuous function mapping a compact convex set to itself has at least one fixed point.

This is hard to prove in general, though easy to see in the case that the set is simply the interval [0, 1]. We have f(0) − 0 ≥ 0 and f(1) − 1 ≤ 0, so that f(x) − x = 0 for at least one x in the range 0 to 1:

An implication is that, when I stir my cup of coffee, at least one speck of liquid winds up exactly where it started.

Fixed points and dynamics

If the function f represents a state transition function, then a fixed point corresponds to a state that remains the same over time. For example, the logistic mapx (1 − x) has fixed points 0 and 0.75. However, these are both unstable – if you start out close to them, repeated application of the function takes you further away:

  • 0.000001, 0.000004, 0.000016, 0.000064, 0.000256, 0.001024, 0.00409, 0.016295, 0.064117, 0.240023, 0.729649, 0.789046, 0.66581, 0.890028, 0.391511, 0.952921, 0.179452, 0.588995, 0.96832, 0.122706, 0.430598, …
  • 0.749999, 0.750002, 0.749996, 0.750008, 0.749984, 0.750032, 0.749936, 0.750128, 0.749744, 0.750512, 0.748975, 0.752045, 0.745893, 0.758147, 0.733441, 0.782021, 0.681856, 0.867713, 0.459147, 0.993324, 0.026525, …

On the other hand, the logistic map 2.5 x (1 − x) has a stable fixed point (an attractor) at 0.6. Starting at, say, 0.5, repeatedly applying the function gets you closer and closer to 0.6:

  • 0.5, 0.625, 0.585938, 0.606537, 0.596625, 0.601659, 0.599164, 0.600416, 0.599791, 0.600104, 0.599948, 0.600026, 0.599987, 0.600007, 0.599997, 0.600002, 0.599999, 0.6, 0.6, 0.6, 0.6, …

Fixed points are everywhere! Not only that, but the concept is a fruitful one in a diverse collection of fields. For more on fixed points, see this book (available electronically here).


Four worlds

The picture above shows four possible worlds: a (slightly oblate) sphere, a torus, a disc, and a Klein bottle (images © Anthony Dekker). The darkened end of the Klein bottle is shifted through the fourth dimension to connect with the other end, making it a one-sided surface (like the Möbius strip). How do we know which world we live in?