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).

Skylark DuQuesne by E. E. Smith: a book review

Skylark DuQuesne by E. E. “Doc” Smith (serialised 1965)

I recently re-read E. E. “Doc” Smith’s Skylark DuQuesne, the final story of Smith’s Skylark series. Smith, of course, is famous for the Lensman series, which is a bit annoying in places, but which is still full of all kinds of interesting ideas. This book is another matter. It’s just bad. Now poor writing may forgivable in “space opera,” and age may play a factor here too – the novel was serialised beginning in June 1965, when Smith was aged 75, and was published as a book in 1966 (Smith died during the serialisation). This novel has so many flaws, in fact, that I can only mention some of them.

To begin with, the sexual titillation for teenage boys is just over the top. Is there any reason why the characters need to be naked quite so often? Or for one of them to be a stripper? It’s a trifle creepy, to be frank.

The mathematics depicted in the book is also disappointing: “‘Hold it!’ Seaton snapped, half an hour later. ‘Back up – there! This integral here. Limits zero to pi over two. You’re limiting the thing to a large but definitely limited volume of your generalized N-dimensional space. I think it should be between zero and infinity—and while we’re at it let’s scrap half of the third determinant in that no-space-no-time complex. Let’s see what happens if we substitute the gamma function here and the chi there and the xi there and the omicron down there in the corner.’” (Chapter 24: DuQuesne and Sleemet)

Smith is describing simple high-school calculus (integrating a function on a single real variable). Even by the standards of the time (never mind the future!) there was a lot more mathematics out there. Robert Heinlein had no trouble getting that fact across in 1952 in The Rolling Stones / Space Family Stone: “Their father reached up to the spindles on the wall, took down a book spool, and inserted it into his study projector. He spun the selector, stopped with a page displayed on the wall screen. It was a condensed chart of the fields of mathematics invented thus far by the human mind. ‘Let’s see you find your way around that page.’ The twins blinked at it. In the upper left-hand corner of the chart they spotted the names of subjects they had studied; the rest of the array was unknown territory; in most cases they did not even recognize the names of the subjects.” (Chapter IV: Aspects of Domestic Engineering).

And hinting at new, future, mathematics is quite possible too. Isaac Asimov did it in 1942 in the first part of Foundation: “‘Good. Add to this the known probability of Imperial assassination, viceregal revolt, the contemporary recurrence of periods of economic depression, the declining rate of planetary explorations, the…’ He proceeded. As each item was mentioned, new symbols sprang to life at his touch, and melted into the basic function which expanded and changed. Gaal stopped him only once. ‘I don’t see the validity of that set-transformation.’ Seldon repeated it more slowly. Gaal said, ‘”But that is done by way of a forbidden sociooperation.’ ‘Good. You are quick, but not yet quick enough. It is not forbidden in this connection. Let me do it by expansions.’ The procedure was much longer and at its end, Gaal said, humbly, ‘Yes, I see now.’” (Chapter 4)

In contrast, Smith’s novel seems to have the goal of making his teenage readers feel good about what they know, rather than encouraging them to grow (and that applies to both intellectual and moral growth).

A PDP-8 computer of 1965

A related problem (common to Smith’s novels, and indeed to much early science fiction) is the failure to imagine how computers might be used. The novel assumes powerful computers (“brains”) which can both sense and influence the physical world. Yet manual information processing is still the order of the day: “Tammon was poring over a computed graph, measuring its various characteristics with vernier calipers, a filar microscope, and an integrating planimeter, when Mergon and Luloy came swinging hand in hand into his laboratory” (Chapter 9: Among the Jelmi)

Finally, the antagonist Marc DuQuesne (the name is a Genesis 4:15 reference, since the surname is pronounced duːˈkeɪn) is a rather unpleasant kind of Nietzschean Übermensch, and the protagonist (Richard Seaton) is not much better. Julian May, in her excellent Saga of Pliocene Exile (and even better Galactic Milieu Series) apparently based her character Marc Remillard in part on Smith’s Marc DuQuesne. But Marc Remillard repents of his crimes, and atones for them, and is actually interesting to read about. Smith’s novel finishes with DuQuesne as arrogant, as unrepentant, and as banal as ever.

Goodreads rates Smith’s novel 3.8, and some old-school science fiction fans still seem to enjoy it. It was even nominated for the Hugo Award for Best Novel, back in 1966, although it can hardly be compared to the other nominees – Dune and This Immortal (tied winners), The Squares of the City, and The Moon Is a Harsh Mistress (which was re-nominated, and won, in 1967). I give Smith’s novel just one star – but if you are nevertheless intrigued, it is now public domain in Canada and is online there.

Skylark DuQuesne by E. E. “Doc” Smith: 1 star

Infinitesimal by Amir Alexander: a book review

Infinitesimal: How a Dangerous Mathematical Theory Shaped the Modern World by Amir Alexander (2014)

I recently read Infinitesimal: How a Dangerous Mathematical Theory Shaped the Modern World by Amir Alexander. This book concentrates on the “indivisibles” of Bonaventura Cavalieri and the “infinitesimals” of John Wallis (the man who introduced the ∞ symbol). As a history of pre-calculus, that’s rather incomplete. There are also some errors, noted by Judith Grabiner in her review for the MAA.

Alexander portrays the Jesuits as the “bad guys,” suppressing the idea of “indivisibles,” even though interesting and useful mathematical results can be obtained by using them. However, Alexander does not fully explain the Jesuits’ actions. There is not a word about their struggle with the Dominicans for intellectual leadership of the Catholic Church (although this played a major part in the Galileo saga). Nor does he explain the link between defending Aristotle and defending the doctrine of Transubstantiation. And, of course, the critics of Cavalieri and Wallis were actually quite correct. “Infinitely small numbers” greater than zero do not exist, and calculus did not have a rigorous foundation until the work of Cauchy and Weierstrass in the 1800s.

I was left rather disappointed with this book. GoodReads rates it 3.83, but I’m only giving it two stars.

Infinitesimal: How a Dangerous Mathematical Theory Shaped the Modern World by Amir Alexander: 2 stars

Seven varieties of metaphysics

I was having a discussion with someone recently on metaphysics, so I thought I would blog about it. Here are seven varieties of metaphysics, describing three “layers” of reality (and yes, I am oversimplifying for brevity).

The first is Platonism. Plato believed that there was a hierarchy of Forms (Ideals), of which the highest was The One (Plato’s version of God). These Forms or Ideals were the true reality, and the physical objects we touched, saw, and tasted were only shadows of that true reality (that is the point of the allegory of the cave). The physical orange which we see and eat reflects Ideals such as “Fruit,” “Sphere,” and “Orange.” Neoplatonism continues and extends this point of view.

Saint Augustine and many later Christians held to a Christianised Platonism, in which the Ideals were thoughts in the mind of God (the Christian God, naturally). The physical objects we touched, saw, and tasted had a greater importance in Christian Platonism than they did for Plato – after all, when God created those objects, “God saw that it was good.” Much as with Platonism, the regularities that people see in the physical universe are explained by the fact that God created the universe in accordance with regularities in the Divine thoughts. However, Christian Platonism does not have the metaphysical hierarchy that Platonism or Neoplatonism have – in Christian Platonism, God makes direct contact with the physical universe.

Aristotle also reacted to Plato by increasing the importance of the bottom layer, and Aristotle’s thought was Christianised by Thomas Aquinas as Thomism. However, in Thomism the all-important bottom layer does very little except to exist, to have identity, and to have properties assigned to it. It is also not observable in any way. This can be seen in the Catholic doctrine of transubstantiation. According to the Tridentine Catechism of 1566, the bread and the wine of the Eucharist lose their bottom (“substance”) layer (“All the accidents of bread and wine we can see, but they inhere in no substance, and exist independently of any; for the substance of the bread and wine is so changed into the body and blood of our Lord that they altogether cease to be the substance of bread and wine”), while the bottom (“substance”) layer of the body and blood of Christ becomes metaphysically present instead.

Idealism denies that the physical universe exists at all. The followers of Mary Baker Eddy take this view, for example, as did George Berkeley. Only thought exists. To quote a famous movie line, “there is no spoon.” These thoughts may be independent of whatever God people believe in or, as in monistic Hinduism, they may be actually be the thoughts of God (in which case, only God exists).

The last three kinds of metaphysics deny the existence of any kind of God. In Platonist Materialism, this denial is combined with a Platonist approach to mathematics, about which I have written before. Mathematics exists independently of the physical universe, and controls the physical universe, in the sense that the physical universe follows mathematical laws. Roger Penrose is one of many scientists holding this view.

In what I am calling Extreme Materialism, the existence of an independent mathematical world is also denied, i.e. there is an empiricist approach to mathematics (mathematics simply describes observed regularities in nature). This view seems to be increasing in popularity among non-religious people, although it causes philosophical problems for mathematics.

Finally, the concept of the Mathematical Universe holds that the so-called “physical universe” is itself composed only of mathematical objects – only mathematics exists (which makes this, in fact, a kind of Idealism).

The Oikoumene of Ptolemy

I was reading recently about the Geographia of Ptolemy (written around 150 AD). This classic book applied Greek mathematical skills to mapping and map projection – and if there was one thing the Greeks were good at, it was mathematics. According to Neugebauer, Ptolemy believed the Oikoumene, the inhabited portion of the world, to range from Thule (63° North) to 16°25′ South, and 90 degrees East and West of Syene in Egypt.

The map above illustrates this Oikoumene, with a modern population overlay in red (data from SEDAC). Ptolemy was not too far wrong – today this region holds 80.6% of the world’s population, and the percentage would have been greater in antiquity.

Also shown on the map are some of the many cities listed in the Geographia. Open circles show Ptolemy’s coordinates (from here, adjusted to a Syene meridian), and filled circles show true positions. Ptolemy had reasonably good latitude values (an average error of 1.2° for the sample shown on the map), but much worse longitude values (an average error of 6.8°). The longitude error is mostly systemic – Ptolemy’s estimate of 18,000 miles or 29,000 km for the circumference of the earth was only 72% of the true value (several centuries earlier, Eratosthenes had come up with a much better estimate). If Ptolemy’s longitudes are adjusted for this, the average error is only 1.5°.

However, Ptolemy’s book deserves considerable respect – it is not surprising that it was used for more than a thousand years.

A Medieval Calendar

The beautiful image above (click to zoom) represents the month of September in the Très Riches Heures du Duc de Berry, a book of hours from the 1400s. In the background of the main picture is the Château de Saumur, with its height exaggerated (almost doubled). For comparison, below is a modern photograph of the château (by Kamel15) stretched vertically ×2:

The foreground of the main picture shows the grape harvest. At the top is a complex calendar. On the inner track, around the chariot of the sun, in red and black numerals, are the days of the month. On the outer track, in red and blue numerals, is a zodiacal calendar, showing the last days of Virgo and the beginning of Libra. Adjacent to the inner track are blue letters which relate to the 19-year Metonic cycle. Combining those letters with an appropriate table will show the phases of the moon for a given year.

The manuscript uses the Hindu-Arabic numerals first introduced to Europe by Fibonacci in his Liber Abaci of 1202. They are not quite the same as the ones we use today:

It is interesting to compare those digits with the ones in this German manuscript of 1459 by Hans Talhoffer (although Talhoffer actually mixes two different styles of 5). Then again, the letters of the alphabet have also changed since that time.

Something is going on with the primes…

The chart below illustrates the Erdős–Kac theorem. This relates to the number of distinct prime factors of large numbers (integer sequence A001221 in the On-Line Encyclopedia):

Number No. of prime factors No. of distinct prime factors
1 0 0
2 (prime) 1 1
3 (prime) 1 1
4 = 2×2 2 1
5 (prime) 1 1
6 = 2×3 2 2
7 (prime) 1 1
8 = 2×2×2 3 1
9 = 3×3 2 1
10 = 2×5 2 2
11 (prime) 1 1
12 = 2×2×3 3 2
13 (prime) 1 1
14 = 2×7 2 2
15 = 3×5 2 2
16 = 2×2×2×2 4 1

The Erdős–Kac theorem says that, for large numbers n, the number of distinct prime factors of numbers near n approaches a normal distribution with mean and variance log(log(n)), where the logarithms are to the base e. That seems to be saying that prime numbers are (in some sense) randomly distributed, which is very odd indeed.

In the chart, the observed mean of 3.32 is close to log(log(109)) = 3.03, although the observed variance of 1.36 is smaller. The sample in the chart includes 17 numbers with 8 distinct factors, including 1,000,081,530 = 2×3×3×5×7×19×29×43×67 (9 factors, 8 of which are distinct).

The Erdős–Kac theorem led to an episode where, following the death of Paul Erdős in 1996, Carl Pomerance spoke about the theorem at a conference session in honour of Erdős in 1997. Quoting Albert Einstein (“God does not play dice with the universe”), Pomerance went on to say that he would like to think that Erdős and [Mark] Kac replied “Maybe so, but something is going on with the primes.” The quote is now widely misattributed to Erdős himself.

Recreational mathematics

The wolf, the goat, and the cabbages

Dancing alongside the more serious practitioners of mainstream mathematics are the purveyors of mathematical puzzles and problems. These go back at least as far as Diophantus (c. 200–284), the Alexandrian “father of algebra.” Alcuin of York (c. 735–804) produced a collection of problems that included the the wolf, the goat, and the cabbages (above); the three men who need to cross a river with their sisters; and problems similar to the bird puzzle published by Fibonacci a few centuries later. In more modern times, Martin Gardner (1914–2010) has done more than anyone else to popularise this offshoot of mathematics. It is often called “recreational mathematics,” because people do it for fun (in part because they are not told that it is mathematics).

Particularly popular in recent times have been Sudoku (which is really a network colouring problem in disguise) and the Rubik’s Cube (which illustrates many concepts of group theory, although it was not invented with that in mind). Sudoku puzzles have been printed in more than 600 newspapers worldwide, and more than 20 million copies of Sudoku books have been sold. The Rubik’s Cube has been even more popular: more than 350 million have been sold.

A Soma cube, assembled

Recreational puzzles may be based on networks, as in Hashi (“Bridges”). They may be based on fitting two-dimensional or three-dimensional shapes together, as in pentominoes or the Soma cube. They may be based on transformations, as in the Rubik’s Cube. They may even be based on arithmetic, as in Fibonacci’s problem of the birds, or the various barrel problems, which go back at least as far as the Middle Ages.

In one barrel problem, two men acquire an 8-gallon barrel of wine, which they wish to divide exactly in half. They have an empty 5-gallon barrel and an empty 3-gallon barrel to assist with this. How can this be done? It is impossible to accurately gauge how much wine is inside a barrel, so that all that the men can do is pour wine from one barrel to another, stopping when one barrel is empty, or the other is full [highlight to show solution → (8, 0, 0) → (3, 5, 0) → (3, 2, 3) → (6, 2, 0) → (6, 0, 2) → (1, 5, 2) → (1, 4, 3) → (4, 4, 0)]. There is a similar problem where the barrel sizes are 10, 7, and 3.

The barrels

Apart from being fun, puzzles of this kind have an educational benefit, training people to think. For this reason, Alcuin called his collection of problems Propositiones ad Acuendos Juvenes (Problems to Sharpen the Young). Problems like these may also benefit the elderly – the Alzheimer’s Association in the United States suggests that they may slow the onset of dementia. This is plausible, in that thinking hard boosts blood flow to the brain, and research supports the idea (playing board games and playing musical instruments are even better).

The three men and their sisters

The medieval Propositiones ad Acuendos Juvenes (“Problems to Sharpen the Young”) is attributed to Alcuin of York (735–804), a leading figure in the “Carolingian Renaissance.” He is the middle person in the image above.

Along with the more famous problem of the wolf, the goat, and the cabbage, Propositiones ad Acuendos Juvenes contains the problem of the three men and their sisters. Three men, each accompanied by a sister, wish to cross a river in a boat that holds only two people. To protect each woman’s honour, no woman can be left with another man unless her brother is also present (and if that seems strange, remember that Alcuin was writing more than 1,200 years ago). In Latin, the problem is:

“Tres fratres erant qui singulas sorores habebant, et fluvium transire debebant (erat enim unicuique illorum concupiscientia in sorore proximi sui), qui venientes ad fluvium non invenerunt nisi parvam naviculam, in qua non potuerunt amplius nisi duo ex illis transire. Dicat, qui potest, qualiter fluvium transierunt, ne una quidem earum ex ipsis maculata sit?”

The diagram below (click to zoom) shows the state graph for this problem. The solution is left (per tradition) as an exercise for the reader (but to see Alcuin’s solution, highlight the white text below the diagram).

Miss A and Mr A cross
Mr A returns (leaving Miss A on the far side)
Miss B and Miss C cross
Miss A returns (leaving Misses B and C on the far side)
Mr B and Mr C cross
Mr B and Miss B return (leaving Miss C and Mr C on the far side)
Mr A and Mr B cross
Miss C returns (leaving 3 men on the far side)
Miss A and Miss C cross
Mr B returns (leaving the A’s and C’s on the far side)
Mr B and Miss B cross