Brouwer and his fixed point theorem

    

The Brouwer fixed-point theorem is one of my favourite mathematical theorems. It is named after the Dutch mathematician Luitzen Egbertus Jan Brouwer (above right). Brouwer is also known for his work in Intuitionism. I have mentioned the Brouwer fixed-point theorem before.

The theorem states that any continuous function f on a compact convex set (and specifically, on a disc in the plane) will have at least one fixed point – that is, there will be at least one point p such that f(p) = p. The picture below is intended to illustrate the theorem; it is explained further down.

In the case of a disc, the theorem can be proved by contradiction. Assume that f(p) ≠ p for every point p. Then the pair of f(p) and p always defines a continuous mapping g from p to the boundary of the disc, as illustrated above (left). However, such a continuous mapping is impossible (for complex reasons, but in simple terms, because it creates a hole, which continuous mappings cannot do).

So what about that picture? It shows a continuous function f from the disc to itself, combining an irregular rotation about the centre (rotating least towards the east of the disc) with a “folding” operation that leaves the centre and boundary untouched. The picture below shows a cross-section of the folding in action. The shades of blue in the picture above show how far each point p is from f(p), with lighter colours representing smaller values. Arrows show the action of the function on 6 randomly chosen points. There are two fixed points, marked with black dots: the centre and one other point where the folding and the irregular rotation cancel each other out.

The three-dimensional version of the theorem tells us that, when I stir my morning cup of coffee, at least one speck of liquid will wind up exactly where it started.

---

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 map 4 x (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).

---

Caffeine!

I love my daily shot of caffeine, preferably in the form of a good espresso. Caffeine is a stimulant and vasoconstrictor. It can increase alertness, and will sometimes alleviate headaches (although a rebound effect means that withdrawal from caffeine may temporarily cause headaches). Alfréd Rényi famously said that “A mathematician is a device for turning coffee into theorems,” and that does seem to be true. In addition, moderate coffee intake seems to have minor health benefits, including a slight protective effect against some cancers.

There are, however, good reasons to limit caffeine intake to 400 mg day (and half that for pregnant women). That leads to the limits in the table below (data from here and here). I intend to keep on enjoying my coffee responsibly, within those limits!

Drink	Volume	Caffeine	Max/day
Espresso	1 shot (30 ml)	60 mg	6
Brewed coffee	1 cup	200 mg	2
Starbucks coffee	“venti”	400 mg	1
Black tea	1 cup	40–80 mg	5–10
Green tea	1 cup	30–60 mg	6–13
Coca-Cola	1 can	35 mg	11
Red Bull	1 can	80 mg	5

The price of coffee

The price of coffee is going up, as a result of drought in Brazil and a fungal disease of coffee plants. Prices hit US$2.23 per pound last month (for Colombian Mild Arabica). Of course, droughts and disease are perennial features of the coffee industry, and prices have oscillated for decades (see the chart above, in which the dashed red line shows the “Fairtrade” floor price). Of course these prices are for “commodity” coffee – quality coffee sells at auction for twenty times the commodity price. For farmers, quality coffee is where the money is. And for lovers of coffee – really, why would we drink anything else?

Coffea arabica plant

More good news for coffee-drinkers

A recent study from Cornell University concludes that coffee may help prevent retinal damage in the eye, thanks to the antioxidant chlorogenic acid (although roasting destroys about half the chlorogenic acid present in coffee beans). See this Science Daily report or the paper for more details.

I’m off to make myself a double espresso again.

Good news for coffee-drinkers

A recent study in Nature Neuroscience reports that “post-study caffeine administration enhances memory consolidation in humans.” Apparently drinking coffee while – or just after – you study can help to store information in long-term memory. Two shots of espresso seem to be the optimal dose. See this New Scientist article for more details.

I’m off to make myself a double espresso.

What your professor never told you about science: a review of Bellwether

Bellwether by Connie Willis

I recently re-read the classic science-fiction comedy Bellwether by Connie Willis. Bellwether, which is set in a fictional research company called “Hi-Tek,” is one of those books that reminds us how science really works:

“People like to think of science as rational and reasonable, following step by step from hypothesis to experiment to conclusion. Dr. Chin, last year’s winner of the Niebnitz Grant, wrote, ‘The process of scientific discovery is the logical extension of observation by experimentation.’ Nothing could be further from the truth. The process is exactly like any other human endeavor—messy, haphazard, misdirected, and heavily influenced by chance. Look at Alexander Fleming who discovered penicillin when a spore drifted in the window of his lab and contaminated one of his cultures. Or Roentgen…”

Connie Willis keeps us laughing as she describes the ups and down of grant applications, staff interaction, chaos, confusion, recalcitrant laboratory animals, and management fads (I will always remember the ridiculous “1. Optimize potential. 2. Facilitate empowerment. 3. Implement visioning. 4. Strategize priorities. 5. Augment core structures.”).

The lead character’s own research project concerns the sociology of fads:

“Coffeehouse (1450–1554) – Middle Eastern fad that originated in Aden, then spread to Mecca and throughout Persia and Turkey. Men sat cross-legged on rugs and sipped thick, black, bitter coffee from tiny cups while listening to poets. The coffeehouses eventually became more popular than mosques and were banned by the religious authorities, who claimed they were frequented by people ‘of low costume and very little industry.’ Spread to London (1652), Paris (1669), Boston (1675), Seattle (1985).”

Bellwether contains some inaccuracies both in the discussion of chaos theory and the history of coffee. However, it is such a great comic novel that it was nominated for the Nebula Award in 1997, even though it is only science fiction in the sense that it is fiction about science, written by a science-fiction author. On the whole, a highly recommended book – one that is both funny and insightful.

Bellwether by Connie Willis: 4 stars