# Alan Turing and the Countability of Computable Numbers

Turing’s methodology was unique: he imagined hypothetical machines that could perform complicated mathematical tasks in a deterministic manner, in the way computers do today. In this way, he inadvertently kickstarted the entire field of modern computer science…

University of Puget Sound

Alan Turing may be the most-influential-yet-least-read figure in 20th Century mathematics. His landmark paper, “On computable numbers, with an application to the Entscheidungsproblem”, was published in the Proceedings of the London Mathematical Society in late 1936. This is the paper that spun computer science off of mathematics, into the distinct field that we know today. Yet, if you ask mathematicians and computer scientists alike if they have read this paper, the answer is frequently “No.” It is so long and amazingly dense that even experts often have a very hard time parsing his arguments. This column aims to rectify this slightly, by explaining one small part of Turing’s paper: the set of computable numbers, and its place within the real numbers.

The Entscheidungsproblem (German for “decision problem”) is the problem of developing an algorithm that can determine whether a statement of first-order logic is universally valid. However, Turing did not know that American mathematician Alonzo Church had already proven that such an algorithm is impossible a few months previously. Even so, Turing’s methodology was unique: he imagined hypothetical machines that could perform complicated mathematical tasks in a deterministic manner, in the way computers do today. In this way, he inadvertently kickstarted the entire field of modern computer science (which has made some modest improvements since 1936). As part of his proof, he developed the concept of computable numbers. Turing used his imaginary machines (that have since come to be called “Turing machines” in his honor) for the process of calculating numbers in this set. It contains any number that can be calculated to within an arbitrary precision in a finite amount of time. This set includes all rational and algebraic numbers (e.g. $$\sqrt{2}$$), as well as many transcendental numbers such as $$\pi$$ and $$e$$. Interestingly, Turing created a very natural extension to Georg Cantor’s set theory, when he proved that the set of computable numbers is countably infinite!

Most mathematicians are familiar with the idea of countability. That is, the notion developed by Cantor in the 1870s that not all infinite sets have the same cardinality. A set that is countably infinite is one for which there exists some one-to-one correspondence between each of its elements and the set of natural numbers $$\mathbb{N}$$. For example, the set of integers $$\mathbb{Z}$$ (“Z” for “Zahlen”, meaning “numbers” in German) can be easily shown to be countably infinite. Cantor himself developed a well-known proof that the set of rational numbers $$\mathbb{Q}$$ (for “quotient”) is also countably infinite. Thus, in a very real sense $$\mathbb{N}$$, $$\mathbb{Z}$$, and $$\mathbb{Q}$$ all have the same cardinality, even though $$\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q}$$.

Conversely, an infinite set for which there is no one-to-one correspondence with $$\mathbb{N}$$ is said to be “uncountably infinite”, or just “uncountable”. $$\mathbb{R}$$, the set of real numbers, is one such set. Cantor’s “diagonalization proof” showed that no infinite enumeration of real numbers could possibly contain them all. Of course, there are many irrational real numbers that are useful in common computations ($$\pi$$, $$e$$, $$\phi$$, $$\sqrt{2}$$, and $$\log~2$$, just to name a few). A common misconception is that a set of all such useful numbers (including infinitely many transcendental numbers) is somehow “too complicated” to be merely countably infinite. Turing’s paper proved this intuition to be incorrect.

The rest of this column is laid out as follows. First, we repeat Cantor’s proofs showing that $$\mathbb{Z}$$ and $$\mathbb{Q}$$ are countable and $$\mathbb{R}$$ is uncountable. Then we will show how Turing extended Cantor’s work, by proving the countability of the set of computable numbers. We will call this set $$\mathbb{K}$$, to better fit in with the other sets of numbers. However, we will reprove Turing’s ideas using Python rather than his original Turing machines. The ideas behind the proofs will remain unchanged, while making it much more easily understood to a modern audience.

### The sets of integers and rationals are both countably infinite

Intuitively, one might think of the set of integers $$\mathbb{Z}$$ as being “bigger” than the set of the natural numbers $$\mathbb{N}$$. After all, $$\mathbb{Z}$$ is a proper superset of $$\mathbb{N}$$! However, by rearranging the integers to start with $$0$$ and count up in magnitude alternating between positive and negative, we can create an infinite list of all the integers, with a definite starting point. This rearrangement allows a bijective function between $$\mathbb{N}$$ and $$\mathbb{Z}$$. This means the function gives a one-to-one and onto correspondence between the two sets, so the function is invertible.

Here’s a proof. Rearrange $$\mathbb{Z}$$ to the order $$\{0, 1, -1, 2, -2, 3, -3, …\}$$. Then map them to the elements of $$\mathbb{N}$$ in their standard order, so that $$0\rightarrow 0$$, $$1\rightarrow 1$$, $$-1\rightarrow 2$$, and so on. This is injective (“one-to-one”) , since no two different integers will ever map to the same natural number. And it is surjective (“onto”), because there exists an integer to map to every natural number. Therefore the relationship is a bijection, and thus the integers are a countable set.

Proving that the set of rational numbers is countable is more difficult, given that there are two “degrees of freedom” in a rational number: the numerator and the denominator. It seems difficult to rearrange $$\mathbb{Q}$$ into a list the same way we did with $$\mathbb{Z}$$. (That is, one with a definite starting point, that extends infinitely forward in a single dimension.) One cannot simply list all the rational numbers with numerator 1, then all with numerator 2, etc., because there are an infinite number of them in each subset. If we started out by listing all the rationals with numerator 1 (for example), we’d never get to the others!

Instead, Cantor thought to traverse the set in an alternating “zig-zag” fashion, as shown here. We start by only considering the positive rational numbers $$\mathbb{Q}^+$$. We’ll extend to the complete set later. This zig-zag pattern lets us get to any given positive rational number, eventually.

Let’s prove that the rational numbers are countable. We start by showing a bijection between the positive rationals $$\mathbb{Q}^+$$ and $$\mathbb{N}$$. Lay out the elements of $$\mathbb{Q}^+$$ as shown in the figure above, so that the first row consists of all numbers with a $$1$$ numerator in order of increasing denominator ($$\frac{1}{1}$$, $$\frac{1}{2}$$, $$\frac{1}{3}$$, $$\ldots$$), the second row has all those with a $$2$$ demoninator in the same order, and so on. Then, traverse them as shown in the figure, moving diagonally while weaving back and forth. We skip any fractions not in lowest terms, so that no rational number appears twice. In this way, we can arrange the set $$\mathbb{Q}^+$$ into the order $$\{\frac{1}{1}, \frac{2}{1}, \frac{1}{2}, \frac{1}{3}, \frac{3}{1}, \ldots\}$$. When mapping them to the natural numbers in this order, the mapping function is an injection because no two different elements of $$\mathbb{Q}^+$$ map to the same member of $$\mathbb{N}$$, and it is a surjection because there exists a member of $$\mathbb{Q}^+$$ for every member of $$\mathbb{N}$$. Thus it is a bijection, and $$\mathbb{Q}^+$$ is countable.

To show that the set of all rational numbers $$\mathbb{Q}$$ is countable, use the reordering strategy employed to prove that $$\mathbb{Z}$$ is countable. Reorder $$\mathbb{Q}$$ to start with $$0$$, and then proceed through the rationals in the order shown in the figure, alternativing positive and negative. Thus $$\mathbb{Q}$$ will be ordered $$\{\frac{0}{1}, \frac{1}{1}, -\frac{1}{1}, \frac{2}{1}, -\frac{2}{1}, \frac{1}{2}, -\frac{1}{2}, \frac{1}{3}, -\frac{1}{3}, \frac{3}{1}, -\frac{3}{1}, \ldots\}$$. These elements can be mapped to the elements of $$\mathbb{N}$$ in its usual order, and this is a bijection for the same reasons as given above.

### The set of reals is uncountably infinite

However, real numbers are inherently uncountable. A rephrasing of Cantor’s original proof follows, using a trick that has come to be known as “diagonalization.” No matter what infinite list of real numbers is given, we can generate a new number $$x$$ that cannot possibly be in that list.

To prove the real numbers are uncountable, let’s assume they are not. Then there would exist some one-to-one correspondence between the real numbers $$\mathbb{R}$$ and the natural numbers $$\mathbb{N}$$. If that were the case, then it would be possible to enumerate all the real numbers in some order, such as that illustrated in the table shown. However, we can construct a real number $$x$$ that cannot possibly be in the list, which means that it’s not a complete list. We do this by taking one digit from each number in the list, and changing it. (In the table shown, the change is effected by adding 1 to the digit, but skipping 9 and 0 so as to avoid numbers such as $$0.0999\ldots$$ and $$0.1000\ldots$$ that are equal, even though their digits are different.) This way, $$x$$ differs from every single number in the list in at least one of its digits. The real number $$x$$ has no corresponding element in the natural numbers, and therefore the original assumption must be false. $$\mathbb{R}$$ must be uncountable.

Thus, integers and rational numbers are both countable sets, while real numbers are uncountable. Cantor also proved that the algebraic numbers ($$\mathbb{A}$$) are also a countable set. (These are the roots of polynomials with rational coefficients.) For his insight, Cantor was allegedly called an “apostate” (“Abtrünnigen” in German) and a “corrupter of youth” (“Verderber der Jugend”), among other colorful names. Many of his contemporaries felt that the nature of infinity was beyond human mathematics, being the realm of God. It was not until David Hilbert began to champion his ideas that they became more widely accepted in the early 1900s. Today, they are part of a standard undergraduate curriculum.

### Defining computable numbers

We will now move on to Turing’s work on computable numbers, which he defined in his famous paper. We use $$\mathbb{K}$$ to represent this set. ($$\mathbb{C}$$ is taken, as it usually refers to the set of complex numbers.) Turing defined a computable number as one that can be calculated to within an arbitrary precision, within a finite amount of time. These days, the easiest way to do that is often with a computer program—though any algorithmic approach will do.

First, let us show that all rational numbers are computable. When represented as a decimal, a rational number either terminates, or eventually begins to infinitely repeat the same set of digits. Thus, given enough time, a program could be written to display any rational number to the desired precision.

The figure here shows a non-terminating Python program, similar in spirit to the machines Turing laid out in his paper. This one outputs the never-ending decimal representation of one third. It first prints out “0.”, and then loops forever printing the digit “3” until the user gets tired and pulls the plug. In this way, it “calculates” the number to as accurate a degree as the user wishes.

It may come as a surprise that in his seminal paper, Turing preferred Turing machines that never terminated their calculations. Today, Turing machines are often associated with the “halting problem”, which is the impossible task of proving whether or not an arbitrary program will eventually terminate. However, Turing used his machines to calculate numbers to ever-increasing precisions. In fact, he referred to his machines as “unsatisfactory” if they ever stopped, and “satisfactory” if they kept on going forever. Although Turing’s paper touches on concepts similar to the halting problem, this would not be posed as we know it today until the 1950s.

The procedure to calculate a computable number does not need to be in code form (though any of the below approaches may be programmed, if needed). For example, $$\pi$$ is also a computable number, and to show this we only need to express it as an infinite sum, like this one:

$$\pi = \frac{4}{1} – \frac{4}{3} + \frac{4}{5} – \frac{4}{7} + \frac{4}{9} – \ldots$$

This is not as “computery” as the above code, but it is algorithmic all the same. One may continue adding further terms until the approximation is as accurate as needed. There are other well-known infinite series to calculate other irrational numbers like $$e$$ and $$\phi$$. So long as there exists a mechanical way to approximate a number to ever-increasing precision, within finite time, the number is computable.

Writing an efficient Python program to calculate $$\pi$$ is a little more difficult. The program shown in this figure uses a “streaming” method developed by J. Gibbons and implemented by D. Bau. It is not as easily comprehensible as the above infinite series, but is more in the spirit of Turing’s paper. It is able to continue printing further digits of $$\pi,$$ only needing to maintain six variables between each print statement (rather than reviewing all the digits it has already output), making for a very efficient calculation.

Some other numbers such as $$\sqrt{2}$$ and $$\log~2$$ also have infinite sums, products, or fractions that can be used to calculate them. However, it’s often more efficient to compute them via successive approximations. For example, let us approximate $$\sqrt{2}$$ with a number $$r$$. We know that $$r$$ is a positive number such that $$r^2 = 2$$. Since $$1 < r^2 < 4$$, that means that $$1 < r < 2$$. We can then successively approximate $$r$$ as $$1.5$$, $$1.25$$, $$1.375$$, $$1.4375$$, $$1.40625$$, and so on, each time adding or subtracting the next smaller power of two, depending on whether the current approximation’s square is greater than or less than 2. We stop when the power added or subtracted is less than half the desired maximum error.

There is one flaw with calculating irrational numbers like these on a modern computer: any computer has only a finite amount of memory, and eventually that memory will be exhausted. This is one key difference between Turing machines and real computers: Turing assumed that his machines had inexhaustible memory. Thus, it is fair to do likewise when proving that the set of computable numbers is countable. However, one could also slightly redefine a computable number to be one that can be calculated to within an arbitrary precision in a finite amount of time and with a finite amount of resources. This is equivalent to Turing’s original definition, since if a calculation required unbounded memory, it would need unbounded time to access that memory.

In general, any number with a well-defined value, or well-defined method to calculate its value, may be said to be an element of $$\mathbb{K}$$. If you can write a program to calculate a number (to within some arbitrary precision, in a finite amount of time), it’s computable. This includes many well-known non-algebraic real numbers. In fact, it’s very difficult to come up with a number that’s not computable.

### Gödel numbers

Now that we’ve defined our set $$\mathbb{K}$$, we need to show that it is countable. The proof relies on the concept of a Gödel number. Gödel numbers were developed by Kurt Gödel himself, in order to prove his “incompleteness theorems.” (If you are new to German, Gödel’s name is pronounced similarly to the English word “girdle”, but without the “r” sound.)

Definition: Gödel Number
A Gödel number is a natural number that is a unique representation of a particular member of a set $$S$$. The Gödel number is calculated with a function $$\mathrm{g}$$ whose domain is $$S$$ and whose codomain is $$\mathbb{N}$$.

Note that $$\mathrm{g}$$ is an injective function, so that if $$\mathrm{g}(s) = \mathrm{g}(s’)$$, it must be the case that $$s = s’$$. However some integers may not be valid Gödel numbers for members of $$S$$, so the function $$\mathrm{g}$$ is frequently not a bijection between $$S$$ and $$\mathbb{N}$$.

If a set $$S$$ is infinite, and there exists a function $$\mathrm{g}$$ to calculate a valid Gödel number for every member $$s$$, then $$S$$ must be countably infinite. To prove this, we must show that $$S$$ has a one-to-one correspondence with $$\mathbb{N}$$. Since the Gödel number of each set element $$s$$ is unique, one of them must have the least value. Let this element of $$S$$ correspond to $$0$$. Then, the one with the second-least Gödel number will correspond to $$1$$, the next one to $$2$$, and so on. Since both sets are infinite, the correspondence can continue infinitely. Hence there exists a bijection between $$S$$ and $$\mathbb{N}$$, and therefore $$S$$ is countable.

### Bringing it together

It remains to show that a Gödel number function $$\mathrm{g}$$ exists for $$\mathbb{K}$$. The trick is to calculate a Gödel number from the program that generates a computable number, rather than from the number itself. Recall that a program consists of a finite block of text. Most computers use the ASCII code or Unicode to represent a text file, in which every valid character is a encoded as a number between 1 and 127. (A 0 would represent a null character, which isn’t used in text files.) Thus, the source code itself may be represented as a base-128 number with no 0s, and as many digits as there are characters in the file. We will simply translate this base-128 number into a common base-10 one. For example, in the case of the tiny program above that prints one third, the computation is:
$$112\cdot128^0 + 114\cdot128^1 + 105\cdot128^2 + \ldots + 10\cdot128^{50}$$
Here, the $$112$$, $$114$$, and $$105$$ represent the characters p, r, and i respectively: the first three characters in the program. The fifty-first character at the end is a newline, which is represented by $$10$$. The resulting sum is the number:

23, 674, 419, 604, 088, 055, 738, 162, 829, 936, 727, 249, 274, 729, 959, 756, 590, 023, 485, 007, 031, 946, 824, 166, 916, 359, 320, 099, 837, 891, 922, 699, 574, 436, 329, 840.

The other program, to calculate $$\pi$$, results in a Gödel number that is approximately $$1.77\times10^{654}$$. These numbers are unwieldy, but remember that they encode entire programs. Because one can recover the complete program from its number, it must be the case that the function $$\mathrm{g}$$ is injective.

This is similar to Turing’s approach: he created Turing machines to compute numbers, and then represented each machine as a large table of states. This let him systematically create a unique “description number” for each possible machine. (The term “Gödel number” was not yet in common use.) The number was a large positive integer that described every aspect of the machine, and no two different machines could ever have the same number. Thus, as in our case, Turing showed that there exists a valid Gödel function $$\mathrm{g}$$, and used this to show that $$\mathbb{K}$$ is countable.

It may be argued that any given computable number has an infinite number of programs that can calculate it, and hence infinite Gödel numbers associated with it. We need the function $$\mathrm{g}$$ to map each computable number to one Gödel number. Therefore, we choose the number with the least magnitude, which corresponds to the shortest program that produces the computable number in question. A critic may argue that finding this shortest program is not always possible, and so the Gödel function $$\mathrm{g}$$ cannot be executed. However, for our purposes it does not matter if the function is practical. All that matters, to prove that the set of computable numbers is countable, is that each one can be shown to have an associated Gödel number.

Here’s the final proof, bringing this all together. The computable numbers are an infinite set. We have provided an injective function $$\mathrm{g}$$ that maps every computable number to a single natural number: a Gödel number. Any set with such a function is countable, and therefore computable numbers are countable.

### A counter proof?

Some readers may wonder why we cannot use the same diaganolization trick that Cantor used, and so prove that the computable numbers are uncountable. Let’s try to do it, and we will see where it fails.

Let us say that we have an allegedly complete (though infinite) enumeration of every computable number. We will now attempt to use diagonalization in order to produce a new computable number $$x$$, that could not possibly be in our list. First we calculate the tenths place digit of the first computable number, and assign $$x$$’s tenths place digit to be something else. Then we calculate the hundredths place digit of the second computable number, and assign $$x$$’s corresponding digit to be another one. We proceed as before, until we have computed a number that could not possibly be in the enumeration. Thus, it appears that we have a contradiction, and so $$\mathbb{K}$$ appears uncountable.

The problem with this “proof” is that we never showed that the number $$x$$ is itself computable. When Cantor used diagonalization to prove $$\mathbb{R}$$ uncountable, the resulting $$x$$ was obviously a real number, even though it’s not in the “complete” list. Hence he had a contradiction. But proving that a number is computable is more difficult, because we would need to show that the computation to some arbitrary accuracy can be done in finite time. Since we haven’t done this (and in fact we cannot do it), the alleged proof falls apart.

It might seem straightforward at first to prove that $$x$$ is computable, since the diagonalization technique appears to give an algorithm to calculate it. However the algorithm is flawed, and will enter an infinite loop from which it cannot recover. Remember that it calculates $$x$$ by using each computable number in turn, which would include $$x$$ itself. Let us say that $$x$$ happens to be the $$i$$th number in the list. Then, in order to calculate $$x$$ to the $$i$$th digit, one must first calculate $$x$$ to the $$i$$th digit. The algorithm enters an infinite regress from which it cannot recover. Thus the computation fails: $$x$$ is not computable, there is no contradiction, and diagonalization technique did not work.

### Conclusions

What does it mean that the set of computable numbers is countable, but the set of real numbers is not? In a very true sense, the set $$\mathbb{K}$$ contains all the numbers that are knowable. Real numbers that aren’t computable can’t be calculated, or even thought about except in the most abstract manner (such as $$x$$ from the last section, the uncalculable result of using the diagonalization process on $$\mathbb{K}$$). Yet, since $$\mathbb{R}$$ is uncountable, the vast majority of real numbers must be unknowable. They are the infinite streams of digits, with absolutely no rhyme or reason to their sequences. Any real number used in day-to-day life is part of the computable set $$\mathbb{K}$$.

Others have gone on to describe other incomputable numbers. For example, in 1949 the Swiss mathematician Ernst Specker found a monotonically increasing, bounded, computable sequence of rational numbers whose least upper bound is not computable. Computability theory originated with Turing’s paper as a branch of mathematics in its own right. It attempts to classify noncomputable functions into a hierarchy, based on their degrees of noncomputability. It is of interest to both mathematicians and computer scientists.

Fortunately for Alan Turing, his Turing machines were thought to be innovative enought that his paper found publication, despite not being the first to prove that the Entscheidungsproblem is not solvable. In fact, his paper served as his introduction to Alonzo Church, the very man who had scooped him. Church would go on to supervise Turing’s doctoral work at Princeton, from which he graduated in 1938 at the age of 26! The two would go on to lay much of the groundwork for modern computer science, including the Church-Turing thesis (which roughly states that human computation, machine computation, and Church’s lambda calculus are all equivalent).

Turing’s paper doesn’t mention complex numbers, but an extension of his work is straightforward. A complex computable number would be a complex number whose real portion is a computable number, and whose imaginary portion is another computable number times $$i$$ $$(\sqrt{-1})$$. Such a number is computable to within an arbitrary precision in a finite amount of time, so long as the program that calculates it alternates regularly between calculating the real portion and the imaginary portion (perhaps outputting the two numbers via separate streams or into separate files). Since such a complex number can be calculated using a program, the same proof of countability applies.

Charles Petzold’s “The Annotated Turing” is an excellent source for those who wish to know more about Turing and his proof that the Entscheidungsproblem is impossible. It reproduces Turing’s entire paper one small piece at a time, interspersed with copious explanatory detail and context. If you wish to know more about Turing’s seminal work, this is without a doubt the best place to start. Those more interested in Turing’s personal life should read Andrew Hodges’ “Alan Turing: the Enigma”. This covers his whole life in great detail, from his early childhood, through his codebreaking efforts during the war years, and ending with his tragic persecution and death just shy of his 42nd birthday.

Turing’s idea of computable numbers form a logical and intuitive extension to Cantor’s original work on countability. His work is a unique bridge between mathematics and computer science, that is still relevant today.

### Acknowledgements

Thank you to David Bau for permission to use his implementation of the $$\pi$$ spigot algorithm. Thank you also to Ursula Whitcher for encouragement and assistance with one of the proofs.

### References

• D. Bau. A dabbler’s weblog: Python pi.py spigot. http://davidbau.com/archives/2010/03/14/python_pipy_spigot.html, March 2010.
• G. Cantor. Über eine Eigenschaft des Inbegriffs aller reellen algebraischen Zahlen (On a property of the collection of all real algebraic numbers). Journal für die reine und angewandte Mathematik, 77:258–262, 1874.
• G. Cantor. Über eine elementare Frage der Mannigfaltigkeitslehre (On an elementary question concerning the theory of manifolds). Jahresbericht der Deutschen Mathematiker-Vereinigung, 1, 1892.
• A. Church. A note on the Entscheidungsproblem. The Journal of Symbolic Logic, 1(01):40–41, 1936.
• J. Gibbons. Unbounded spigot algorithms for the digits of pi. The American Mathematical Monthly, 113(4):pp. 318–328, 2006.
• K. Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I (On formally undecidable propositions of Principia Mathematica and related systems I). Monatshefte für Mathematik und Physik, 38(1):173–198, 1931.
• A. Hodges. Alan Turing: the Enigma. Burnett Books, London, 1983.
• C. Petzold. The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine. Wiley Publishing, 2008.
• E. Specker. Nicht konstruktiv beweisbare Sätze der Analysis (Theorems of analysis that cannot be proven constructively). The Journal of Symbolic Logic, 14:145–158, 1949.
• A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42, 1936.
• A. M. Turing. Systems of logic based on ordinals. PhD thesis, Princeton University, 1938.

# The Battle of Numbers

Our topic is the game called rithmomachia or rithmomachy—literally, the battle of numbers…

Ursula Whitcher
AMS | Mathematical Reviews, Ann Arbor, Michigan

This month, we’re going to explore a very old—indeed, medieval—educational game and correct a mathematical error in a sixteenth-century game manual. But before we delve into the past, let me remind you that the Feature Column is seeking new columnists. If you’re interested in sharing your writing about intriguing mathematical ideas, please get in touch!

### Pleasant Utility and Useful Pleasantness

Our topic is the game called rithmomachia or rithmomachy—literally, the battle of numbers. The game is played with pieces shaped like geometric figures and labeled with different numbers, on a board like a double chessboard.

A rithmomachia set. Photo by Justin du Coeur.

The twelfth-century scholar Fortolfus described the experience of rithmomachia as the pinnacle of educated leisure:

Indeed, in this art, which you will admire in two ways, is pleasant utility and useful pleasantness. Not only does it not cause tedium, but rather it removes it; it usefully occupies one uselessly idle, and usefully un-occupies the person uselessly busy.

The game’s rules are elaborate. Their importance, and their draw for medieval intellectuals, lies in their connection to the quadrivium. Arithmetic, geometry, astronomy, and music were the four advanced arts in the medieval liberal arts curriculum. All four required an understanding of ratios and sequences. Playing rithmomachia allowed medieval people to practice their math skills and show off their erudition.

Some rithmomachia proponents even claimed the game made you a better person. They often quoted the late Roman philosopher Boethius’ “demonstration of how every inequality proceeds from equality,” which makes grand claims:

Now it remains for us to treat of a certain very profound discipline which pertains with sublime logic to every force of nature and to the very integrity of things. There is a great fruitfulness in this knowledge, if one does not neglect it, because it is goodness itself defined which thus comes to knowable form, imitable by the mind.

Boethius describes a specific procedure for creating different types of sequences and ratios, beginning with the same number:

Let there be put down for us three equal terms, that is three unities, or three twos, or however many you want to put down. Whatever happens in one, happens in the others.

Now these are the three rules: that you make the first number equal to the first, then put down a number equal to the first and the second, finally one equal to the first, twice the second, and the third.

For example, if we begin with $1, 1, 1$ we obtain $1, 2, 4$.

This is the beginning of a geometric sequence where the numbers double at each step: in Boethius’s language, it is a duplex. Applying the same rule to the new list of numbers will create a list with more complicated relationships.

### Rithmomachia Pieces

Every rithmomachia piece has its own number (or, in some cases, a stack of numbers):

A 1556 illustration of a rithmomachia board from Claude de Boissière’s book Le tres excellent et ancien jeu pythagorique, dict Rythmomachie

The choice of numbers is not arbitrary; they are generated by rules similar to Boethius’ rules for creating inequality from equality. Traditionally, the white gamepieces are considered the “evens” team and the black pieces are considered the “odds” team, though as we will see, this split between even and odd only applies to the circles.

#### Circles

Each side has eight circle pieces, given by the first four even or odd numbers and their perfect squares. (The odd numbers skip 1, which is a more mystical “unity” in the Boethian scheme.)

Evens

 2 4 6 8 4 16 36 64

Odds

 3 5 7 9 9 25 49 81

#### Triangles

The triangles in a rithmomachia set appear in pairs that demonstrate superparticular proportions. These are ratios of the form $n+1:n$, such as $3:2$ or $4:3$. Practically speaking, one can lay out the triangle and circle pieces in a table. The numbers for the first row of triangles are obtained by adding the two circle numbers above that number, in the same column. One may find the numbers for the second row of triangles using ratios. In each column, the ratio of the number in the first triangles row to the number in the last circles row and the ratio of the number in the second triangles row to the number in the first triangles row are the same.

I’ll start with partially completed tables, in case you want to try finding the values yourself:

Evens

 Circles I 2 4 6 8 Circles II 4 16 36 64 Triangles I 6 20 Triangles II 9 Ratio 3:2

Odds

 Circles I 3 5 7 9 Circles II 9 25 49 81 Triangles I Triangles II Ratio

In medieval and Renaissance music, different ratios were used to create different musical scales and analyze the differences between musical notes within those scales. For example, the Pythagorean temperament is based on the ratio $3:2$, which appears when finding the first Team Evens triangle values.

Here are all the triangle values:

Evens

 Circles I 2 4 6 8 Circles II 4 16 36 64 Triangles I 6 20 42 72 Triangles II 9 25 49 81 Ratio 3:2 5:4 7:6 9:8

Odds

 Circles I 3 5 7 9 Circles II 9 25 49 81 Triangles I 12 30 56 90 Triangles II 16 36 64 100 Ratio 4:3 6:5 8:7 10:9

#### Squares

The triangular rithmomachia gamepieces used ratios of the form $n+1:n$. The squares use ratios of the form $n+(n-1):n$, which we may simplify to the less evocative form $2n-1:n$. This is a special case of the more general superpartient proportions. A superpartient proportion is any ratio of the form $n+a:n$ where $a$ is an integer greater than 1 and $a$ and $n$ are relatively prime (that is, their greatest common divisor is 1).

The numbers for the square pieces may be found by repeating the method for finding the numbers for triangular pieces, but now shifted two rows down. The numbers for the first row of squares are obtained by adding the two triangle numbers above above that number, in the same column. One may find the numbers for the second row of squares using ratios. In each column, the ratio of the number in the first squares row to the number in the last triangles row and the ratio of the number in the second squares row to the number in the first squares row are the same.

Evens

 Circles I 2 4 6 8 Circles II 4 16 36 64 Triangles I 6 20 42 72 Triangles II 9 25 49 81 Squares I 15 45 91 (pyramid) 153 Squares II 25 81 169 289 Ratio 5:3 9:5 13:7 17:9

Odds

 Circles I 3 5 7 9 Circles II 9 25 49 81 Triangles I 12 30 56 90 Triangles II 16 36 64 100 Squares I 28 66 120 190 (pyramid) Squares II 49 121 225 361 Ratio 7:4 11:6 15:8 19:10

#### Pyramids

The pyramids or kings are sums of perfect squares. Ideally, they should be built out of spare pieces of the appropriate color with these values. The
Even team’s pyramid has the value $1 + 4 + 9 + 16 + 25 + 36 = 91$. The Odd team’s pyramid has the value $16 + 25 + 36 + 49 + 64 = 190$.

### Moving Pieces

We have already seen the starting board layout, in the illustration from Claude de Boissière’s manual. Black (Team Odds) always moves first. Each shape of piece follows a different movement rule. The following guidelines are based on the 1563 English rithmomachia manual by Lever and Fulke, which was in turn based on de Boissière’s book in French.

• The circles move one space diagonally.
• The triangles move two spaces horizontally or vertically. If not taking a piece, they may also make a chess knight’s move (“flying”).
• The squares move three spaces horizontally or vertically. If not taking a piece, they may also make a “flying” knight-like move that crosses four squares total. This may be either three vertical squares followed by one horizontal square, or three vertical squares followed by one vertical square.
• The pyramids may move in the same way as any of the circles, triangles, or squares.

Lever and Fulke give the following diagram illustrating potential moves:

Diagram from Lever and Fulke, 1563

They illustrate the square’s knight-like move by pointing out a square may move from P to Y or T in their diagram.

### Capturing Pieces

When a player takes a piece, they change its color to their team’s color (ideally, rithmomachia pieces are two-sided!) The transformed piece moves to the row of the board closest to the player, and may now be used like other pieces. There are many ways to take pieces, using different mathematical properties. Lever and Fulke mention Equality, Obsidion (in some editions, Oblivion), Addition, Subtraction, Multiplication, and Division, as well as an optional Proportion rule.

The simplest capture method is Equality. If a piece could move to another piece with the same number, it takes that piece. The Obsidion capture is a trap: if four pieces prevent another piece from moving horizontally or vertically, it is taken.

If two pieces from one team can each move to the same piece of the other team, and those two pieces can add, subtract, multiply, or divide to make the number on the opposing piece, they capture that piece. Whether one of the two attacking pieces has to move into the space they are attacking depends on when the possible capture appears. If a player moves a piece on their turn, bringing it into position for an addition, subtraction, multiplication, or division capture, then they immediately take the other player’s piece without having to move their piece again. On the other hand, if a player notices a possible capture at the start of their turn, before they have moved a piece, they must place one of their attacking pieces in the captured piece’s space in order to take a piece by addition, subtraction, multiplication, or division.

Pyramids may not be taken by equality. They may be taken by obsidion, by addition, subtraction, multiplication, or division, by the optional proportion capture if this is in play, or by taking the pieces with square numbers that make up the pyramid one by one.

### Capture by Proportion

What is the optional rule for taking pieces by proportion? Lever and Fulke refer to arithmetic, geometric, and musical or harmonic proportion, so this optional rule has three sub-rules.

Capture by arithmetic proportion is similar to capture by addition: if two pieces may move into the space of a third and the numbers on all three pieces fit into a partial arithmetic sequence of the form $n, n+a, n+2a$, then the third piece is captured. Three pieces may also capture a fourth by arithmetic proportion. Capture by geometric proportion uses the same idea, but using partial geometric sequences of the form $n, an, a^2n$ or $n, an, a^2n, a^3n$.

Musical proportion only applies to three-term sequences. Lever and Fulke give a “definition” of musical proportion:

Musicall proportion is when the differences of the first and last from the middes, are the same, that is betwene the first and the last, as .3.4.6., betwene .3. and .4. is .1. betwene .4. and .6. is .2. the whole difference is .3. which is the difference betwene .6. and .3. the first and the last.

Unfortunately, this “definition” of musical proportion would apply to any three numbers $a, b, c$. We are comparing $(b-a) + (c-b)$ with $c-a$, but these values are the same! The correct definition of musical proportion (perhaps better known as harmonic proportion) uses ratios. Three numbers $a,b,c$ with $a < b < c$ are in harmonic proportion if $c:a = (c-b):(b-a)$. For example, $4,6,12$ is a musical proportion, because $12:4 = 3:1$ and $(12-6):(6-4) = 6:2 = 3:1$. We can now say that capture by musical proportion happens when two pieces may move into the space of a third and all three pieces fit into a harmonic proportion.

### Victory Conditions

Even figuring out how to take pieces in rithmomachia is complex! Thus, players may agree on any of several victory conditions. These are divided into “common” victories, which are based on capturing enough pieces by some measure, and “proper” victories (also known as triumphs) which involve capturing the enemy’s pyramid and then arranging three or four of one’s one pieces to create an arithmetic, geometric, or harmonic proportion.

Here are the common victories.

• Victory of bodies: The first player to take a certain number of pieces wins.
• Victory of goods: The first player to take pieces adding to at least a certain number wins.
• Victory of quarrel: The first player to take pieces adding to at least a certain number and using a certain total number of digits wins. (This prevents a player from winning by taking a single very high value piece, as might be possible in the victory of goods.)
• Victory of honor: The first player to take a specified number of pieces adding to at least a certain number wins.

Let us quote Lever and Fulke on how to complete a proper victory or triumph:

When the king is taken, the triumph must be prepared to be set in the adversaries campe. The adversaries campe is called al the space, that is betweene the first front of his men, as they were first placed, unto the neither ende of the table, conteyning .40. spaces or as some wil .48. When you entend to make a triumph you must proclaime it, admonishing your adversarie, that he medle not with anye man to take hym, whiche you have placed for youre triumphe. Furthermore, you must bryng all your men that serve for the triumph in their direct motions, and not in theyr flying draughtes.

To triumphe therefore, is to place three or foure men within the adversaries campe, in proportion Arithmeticall, Geometricall, or Musicall, as wel of your owne men, as of your enemyes men that be taken, standing in a right lyne, direct or crosse, as in .D.A.B. or els .5.1.3. if it consist of three numbers, but if it stande of foure numbers, they maye be set lyke a square two agaynst two.

Anyone who attained a proper victory would indeed feel triumphant!

• Rafe Lever and William Fulke, The Philosophers Game, posted by Justin du Coeur.
• Michael Masi, Boethian Number Theory: A Translation of the De Institutione Arithmetica (Rodopi, 1996)
• Ann E. Moyer, The Philosophers’ Game: Rithmomachia in Medieval and Renaissance Europe (Ann Arbor: University of Michigan Press, 2001).

# The Once and Future Feature Column

We’re going to look back at the Column’s history, revisit some of our favorite columns, and talk about what comes next. Spoiler alert: We’re recruiting new columnists!

Ursula Whitcher
AMS | Mathematical Reviews, Ann Arbor, Michigan

The number 24 has many charming properties. For instance, it can be written as $4!$ (that is, $24 = 4 \times 3 \times 2 \times 1$), and it is one of the first nonagonal numbers (the number of dots that can be evenly arranged on the sides of a regular nine-sided polygon). This year, 24 has an even more charming feature: the Feature Column is celebrating its 24th birthday (or, if you prefer, the Feature Column is 4!)

The first three nonagonal numbers. From Eric W. Weisstein, “Nonagonal Number.” (MathWorld–A Wolfram Web Resource.)

Loyal readers of the Column may have noticed some recent changes: a new address (https://blogs.ams.org/featurecolumn/), a shiny new banner incorporating artwork by Levi Qışın, and new navigational tools. This month, we’re going to look back at the Column’s history, revisit some of our favorite columns, and talk about what comes next. Spoiler alert: We’re recruiting new columnists! Check out the last section for information about how to get involved.

### The First Feature Columns

The Feature Column was founded in 1997. Its goals were to increase public awareness of the impact of mathematics and take advantage of the functionality the then-new World Wide Web offered for sharing pictures through the internet. The Column appeared was before blogs were invented: indeed, the Oxford English Dictionary dates the very first use of the long form “weblog” for a blog-like enterprise to December 1997. By that time, the Column had been running for months.

A visualization of the 1997 internet, from opte.org. (CC BY-NC 4.0.)

Steven H. Weintraub wrote the first Feature Columns. The early columns were focused on images, including intertwined knots and pictures taken by the Pathfinder Mars rover. Weintraub also took advantage of the internet’s capability to spread news quickly: Feature Columns could be posted right away, rather than adhering to the publication schedule of the AMS Notices or the Bulletin.

Steven H. Weintraub.)

Some of the early columns had an element of adventure. Steven Weintraub recalls:

One that I remember in particular was the September 1988 Feature Column “Prize Winners at the 1998 International Congress of Mathematicians“. The column itself was a listing of the winners of the various prizes, with links to further information about them and their work. But there is a more interesting back story. In 1998 email and the internet were far less widespread than they are today. I attended the 1998 ICM in Berlin, and, feeling like an old-time reporter, as soon as the prize ceremony was over, I rushed out to a phone booth, called up Sherry O’Brien, the AMS staff member with whom I worked with on WNIM (“What’s New in Mathematics”), and told her who the winners were. She promptly posted the information on the AMS website, and that was how many people first found out the news.

Over the course of the next few years, Tony Phillips, Bill Casselman, and Joe Malkevitch took on roles as regular Feature Columnists. They explored the web’s potential for longer columns, serializing some explorations over multiple months. They were later joined by Dave Austin, and eventually by me. For much of the Column’s existence, it was ably edited by Michael Breen, the longtime AMS Public Affairs expert. I took over the editorial role in 2020.

### Some Favorite Columns

The Feature Column has always been curiosity-driven. Though individual columns may riff on current events, the underlying mathematics is enduring. Thus, individual columns have enduring popularity: some have been read and re-read for decades. Here are some of our most popular Feature Columns.

• In 2009, David Austin made a stirring case for a key concept in applied linear algebra: We Recommend a Singular Value Decomposition. Austin illustrates the Singular Value Decomposition with clear diagrams and inviting applications, from data compression to the $\$1$million Netflix prize. • In 2016, Bill Casselman investigated The Legend of Abraham Wald. We’ve all seen the meme: a diagram of a fighter plane, with red marks for bullet holes on the wings and tail, but not the engine. The legend says that Abraham Wald identified this phenomenon as an example of survivorship bias: airplanes with damage in other places did not survive to be measured. Casselman explores what we do and do not know about the real, historical Abraham Wald. • Image by Martin Grandjean, McGeddon, and Cameron Moll. (CC 4.0.) • In 2004, Joe Malkevitch wrote about Euler’s Polyhedral Formula, describing it as one of his all-time favorite mathematical theorems and also one of the all-time most influential mathematical theorems. Joe Malkevitch’s research focuses on graph theory and discrete geometry, including the properties of polyhedra. His description showcases his expertise, enthusiasm, and long-standing interest in the history of mathematics. • In 2008, Tony Phillips described The Mathematics of Surveying. His discussion offers practical, tangible applications for key concepts in school mathematics, from similar triangles to estimated volumes. • In the summer of 2020, I (Ursula Whitcher) wrote Quantifying Injustice, describing statistical strategies for assessing predictive policing algorithms. These algorithms can both obscure and magnify police injustices: new research provides tools to identify problems and measure their impact. ### New Columnists We’re looking for mathematicians who are enthusiastic about communicating mathematics in written and visual form to join the Feature Column! The typical commitment is two columns per year, though we occasionally welcome guest columnists. We are particularly excited about involving columnists with a variety of backgrounds and experiences. Please send questions and letters of interest to uaw@ams.org. If you’re ready to apply, include a CV and a writing sample! ## In Praise of Collaboration # In Praise of Collaboration Take a look at an extraordinary collaboration in discrete geometry and related geometrical mathematics, the collaboration of Branko Grünbaum and Geoffrey Colin Shephard. Joe Malkevitch York College (CUNY) ### Introduction Point and line do many activities together—their collaborations create a rich texture for many mathematicians and geometers, as well as artists/designers/weavers, to enjoy, study and admire. But point and line are generally undefined terms in the axiom systems that are at the foundations of different types of geometry (Euclidean, projective, hyperbolic, taxicab, etc.) as a mathematical investigation. Despite this, the study of the interactions of points and lines are definitely worthy of exploration. Figure 1 (A Pappus configuration in the Euclidean plane. There are 9 points and 9 lines with three points per line and three lines passing through each point. In the Euclidean plane the line displayed in the space between the two labeled lines MUST pass through the three points indicated.) Figure 2 (The finite Fano Plane, seven points and seven lines in a finite plane where every line intersects each other line in one point and cannot be drawn with straight lines with exactly 3 points per line in the Euclidean plane. This fact is related to the Sylvester-Gallai Theorem.) Scholarly work in experimental physics is typically published with the names of a large team of scientists, often not at the same institution, who collaboratively worked together on the experimental design and the carrying out of the project involved. By comparison, mathematics is sometimes viewed as a rather solitary activity—a subject which, if one is armed with a pencil and paper, one can make major or minor original contributions to. Even before the advent of the Web and the internet, mathematics had examples, usually of pairs of people, who enriched each other’s work by a collaboration. My goal here is to make the results of one such collaboration, by Branko Grünbaum (1929-2018) and Geoffrey Shephard (1927-2016) in the area of discrete geometry more widely known. (Grünbaum and Shephard are sometimes abbreviated G&S below—shades of the great operetta collaboration of Gilbert and Sullivan!) At the same time I want to point out collaboration as a model for doing effective and important research in mathematics. ### Mathematical collaborations The list of superstar contributions to mathematics that are attached to the names of individual people date back in time within many cultures—names include: Euclid, Archimedes, Newton, Euler, Gauss, Kovalevskaya, Noether, Lagrange, Ramanujan, … These distinguished individuals, whose names belong to a list that stretches over long periods of time and in many countries/cultures, did not work in a vacuum. They were inspired by others and in turn inspired others to do important mathematics. Famously, Newton pointed out: “If I have seen further it is by standing on the shoulders of giants.” However, mathematical collaborations prior to the 20th century seem to be relatively rare. There are examples of mathematicians consulting with one another via correspondence, but this did not typically result in joint publications with the letter exchangers working together. In past eras scholars often could only communicate easily via written letters because travel between distant places (e.g. England and Germany) was costly and time consuming. One often-cited example of a productive collaboration was between Geoffrey Hardy (1887-1947) and John Edensor Littlewood (1885-1977). Hardy is perhaps most famous for his book A Mathematician’s Apology but also made significant contributions to number theory, many of these with Littlewood. Figure 3 (Photos of G.H. Hardy (left) and J. E. Littlewood (right). Courtesy of Wikipedia) Figure 4 (A photo of G. H. Hardy and J. E. Littlewood) One of the conjectures made by Hardy and Littlewood is still unsolved to this day. The conjecture states that the number of primes in the interval$(m,m+n]$(this is the interval not containing its left endpoint but containing its right endpoint) will be less than or equal to the number of primes in the interval$[2,n]$(this interval includes both its left and right endpoints). Hardy and Littlewood certainly had a successful collaboration and it seemed to survive with time. According to their contemporary Harald Bohr, they operated their collaboration using the following rules: • It didn’t matter whether what they wrote to each other was right or wrong. • There was no obligation to reply, or even to read, any letter one sent to the other. • They should not try to think about the same things. • To avoid any quarrels, all papers would be under joint name, regardless of whether one of them had contributed nothing to the work. There is considerable discussion about whether these rules are ethical, but presumably they did guide Hardy and Littlewood. Below, I would like to take a look at an extraordinary collaboration in discrete geometry and related geometrical mathematics, the collaboration of Branko Grünbaum and Geoffrey Colin Shephard. I will begin by giving some biographical information about these two distinguished mathematicians, then discuss their collaboration and some of its accomplishments. ### Brief biography of Geoffrey Colin Shephard Figure 5 (Photo of Geoffrey Shephard. Photo courtesy of the Oberwolfach photo collection.) Shephard was born in 1927. He studied mathematics at Cambridge and received his undergraduate degree in 1948. His doctorate degree was also from Cambridge University (Queens College), completed in 1954. His doctoral thesis adviser was John Todd. The title of his thesis was Regular Complex Polytopes. After working at the University of Birmingham he later moved to the University of East Anglia in 1967 and retired from there in 1984. He had at least two doctoral students—the geometer Peter McMullen (who works on problems about regular, primarily convex polyhedra in 3-dimensions and higher) and the specialist in convexity geometry, Roger Webster. You can get some idea of the mathematical topics that Shephard made scholarly contributions to from this list generated by MathSciNet: • Combinatorics • Convex and discrete geometry • Geometry • Group theory and generalizations • History and biography • Linear and multilinear algebra; matrix theory • Manifolds and cell complexes • Number theory Shephard, who was an active member of the London Mathematical Society (LMS), provided money for LMS to fund what is known as the Shephard Prize. Here is its description: "The Shephard Prize is awarded by the London Mathematical Society to a mathematician or mathematicians for making a contribution to mathematics with a strong intuitive component which can be explained to those with little or no knowledge of university mathematics, though the work itself may involve more advanced ideas." The prize has been awarded to Keith Ball and Kenneth Falconer (both of whom are fellows of the Royal Society). ### Brief biography of Branko Grünbaum Figure 6 (A photo of Branko Grünbaum, courtesy of Wikipedia.) Grünbaum was born in Osijek, in what today is known as Croatia, which at various times was part of the conglomerate country known as Yugoslavia. Though he was of Jewish background, he lived with his Catholic maternal grandmother during World War II, a period during which the Nazis occupied Yugoslavia. In high school he met his future wife, Zdenka Bienenstock, from a Jewish family, who survived the war hidden in a convent. Grünbaum began studies at the University of Zagreb but unsettled times in Yugoslavia resulted in Grünbaum and his bride-to-be emigrating to Haifa in Israel in 1949. Grünbaum found work and eventually resumed his mathematical studies at Hebrew University, earning a Master’s degree in 1954. This was also the year he married Zdenka, who trained to be a chemist. He did work for the Israeli air force in operations research while continuing his studies culminating with his doctorate in 1957. While many think of Grünbaum’s doctoral thesis adviser Areheh Dvoretsky (1916-2008) as a functional analyst, it was his budding talent as a geometer that Dvoretsky fostered. His doctoral dissertation was in Hebrew and entitled On Some Properties of Minkowski Spaces. At the completion of his military service Grünbaum came to America to do postdoctoral work at the Institute for Advanced Study with his family. By 1960 he had gone on to the University of Washington in Seattle, where the distinguished geometer Victor Klee (1925-2007) was already teaching. Eventually, after returning for a period to Israel, Grünbaum made his way back to a long career at the University of Washington where he taught until his retirement in 2001, and was part of the group of scholars there working in discrete geometry. He had 19 doctoral students and many more mathematical descendants. It was problems that he posed that I solved in my own doctoral dissertation. Grünbaum’s academic descendants include some of the most prominent discrete geometers of our time, in particular, Noga Alon and Gil Kalai. Over the years he won many prizes including the Lester R. Ford Award (1976) and the Carl B. Allendoerfer Award (2005). The list of research publication areas of Grünbaum from MathSciNet can be compared with the one earlier for Shephard: • Algebraic topology • Combinatorics • Computer science • Convex and discrete geometry • Differential geometry • Functional analysis • General • General topology • Geometry • History and biography • Manifolds and cell complexes • Mathematical logic and foundations • Ordinary differential equations • Topology ### Some of Geoffrey Shephard’s "solo" work: Before his collaboration with Grünbaum, Shephard was particularly interested in the properties of convex sets, not merely convex polyhedra. For example he did important work related to convex polytopes and geometric inequalities. He also wrote several papers about the Steiner Point. Shephard also studied the issue of when various convex sets could be written as a Minkowski sum. The idea was to see when convex sets could not be "factored" into "simpler" sets, an approached modeled on the idea of the importance of prime numbers in number theory. A convexity problem due to Shephard that is still actively being looked at concerns centrally symmetric convex closed and bounded sets$U$and$V$in$n$-dimensional Euclidean space. Suppose the volumes of the projections of$U$on a hyperplane always are smaller or equal than that of$V$. Shephard conjectured that in this case the volume of$U$is less than or equal to that of$V$. One particularly intriguing question has recently been associated with Geoffrey Shephard’s name. The problem involves an idea which is often linked to the name of Albrecht Dürer. Figure 7 (A self-portrait of Albrecht Dürer. Courtesy of Wikipedia.) Dürer (1471-1528), in his work Underweysung der Messung, explored ways to represent 3-dimensional objects in paintings in a "realistic" manner. This lead to his investigating questions about perspective and in particular perspective involving 3-dimensional polyhedra. He had noticed that one way to represent a polyhedron on a flat piece of paper was to show the polygons that make up the polyhedron as a drawing in the plane with each polygon shown by a flat region which shared one or more edges with other polygons that made up the polyhedron. Dürer produced examples of such drawings for Platonic and other solids which consisted of regular polygons. Figure 8 shows an example of the kind of diagram that interested Dürer, in this case for the regular dodecahedron, a Platonic Solid with 12 congruent regular polygons as faces. Figure 8 (The polygons shown can be assembled into a regular dodecahedron by properly gluing the edges.) Such drawings have come to be called nets but there is considerable variance in exactly what is meant by this term. It would be best to restrict this term to a collection of polygons that arises from a (strictly) convex bounded 3-dimensional polyhedron$P$(sometimes called a 3-polytope) which arises from the cutting of the edges of the vertex-edge graph of the polyhedron along edges that are connected, contain no circuit and include all of the vertices of the polyhedron (i.e., a spanning tree of the polyhedron). If the initial polyhedron had$V$vertices then the number of edges of the spanning tree whose cuts enable the unfolding of the polyhedron will be equal to$V – 1$. Since each of the edges of the cut-tree is incident to exactly 2 faces, it follows that the boundary polygon of a net will be a simple polygon with$(2V – 2)$sides. Note that while the original polyhedron may be strictly convex, the polygonal boundary of the net while a simple polygon (when the unfolding forms a net), is typically not convex and will often have pairs of edges that lie along a straight line. (See Figure 9 for all of the nets of a regular$1\times 1\times 1$3-dimensional cube.) Figure 9 (The 11 nets of the 3-dimensional cube. Courtesy of Wikipedia.) Even for some tetrahedra (4 vertices, 4 faces and 6 edges) it is known that one can cut along 3 edges of a spanning tree and "unfold" the resulting polygons so that the result overlaps in the plane. However, it turns out that no polyhedron has ever been found where cutting edges of SOME spanning tree will not result in an assemblage of polygons without overlap. The complexity of the issues involved in such folding and unfolding problems has been explored by Eric Demaine (MIT) and Joseph O’Rourke (Smith) and others. Shephard specifically looked at the question of when such an unfolding would result in a convex polygon in the plane but in light of his work on this collection of ideas I like to refer to the following still open problem as: #### Shephard’s Conjecture Every strictly convex bounded 3-dimensional polyhedron can be unfolded to a net (non-overlapping polygons one for each face of the polyhedron) by cutting edges of the polyhedron that form a spanning tree. (Often one gets different results depending on what spanning tree one cuts.) Intriguingly, experts lack consensus as to whether the result should be true or false. There are many polyhedra where nearly all spanning trees lead to overlapping unfoldings while there are some infinite classes of convex polyhedra where a net has been shown to exist. One source of confusion about the concept of a net is that if one starts with a polyhedron$P$and cuts along a spanning tree to result in the net$N$, it is possible that the net can be folded by using the boundary edges of the net to a polyhedron different from the one one started with—Alexandrov’s Theorem. Thus, to recover the polyhedron one started with one has to provide gluing instructions about which edges to glue to which other edges. There are "nets" that fold (edges glued to edges) to several non-isomorphic convex polyhedra, and there are "nets" that, when glued along boundary edges one way, give rise to a convex polyhedron but a different gluing of boundary edges yields a non-convex polyhedron. ### Some of Branko Grünbaum’s "solo work" Grünbaum’s webpage, still in place after his death in 2018, includes a list of his published works from 1955 to 2003, though he published many more additional works before his death in 2018. It is intriguing to compare the first 10 and last 10 titles in this bibliography: 1. On a theorem of Santaló. Pacific J. Math. 5(1955), 351 – 359. 2. A characterization of compact metric spaces. [In Hebrew] Riveon Lematematika 9(1955), 70 – 71. 3. A generalization of a problem of Sylvester. [In Hebrew] Riveon Lematematika 10(1956), 46 – 48. 4. A proof of Vázsonyi’s conjecture. Bull. Research Council of Israel 6A(1956), 77 – 78. 5. A simple proof of Borsuk’s conjecture in three dimensions. Proc. Cambridge Philos. Soc. 53(1957), 776 – 778. 6. Two examples in the theory of polynomial functionals. [In Hebrew] Riveon Lematematika 11(1957), 56 – 60. 7. Borsuk’s partition conjecture in Minkowski planes. Bull. Research Council of Israel 7F(1957), 25 – 30. 8. On common transversals. Archiv Math. 9(1958), 465 – 469. 9. On a theorem of Kirszbraun. Bull. Research Council of Israel 7F(1958), 129 – 132. 10. On a problem of S. Mazur. Bull. Research Council of Israel 7F(1958), 133 – 135. 1. A starshaped polyhedron with no net. Geombinatorics 11(2001), 43 – 48. 2. Isohedra with dart-shaped faces (With G. C. Shephard) Discrete Math. 241(2001), 313 – 332. 3. Convexification of polygons by flips and by flipturns. (With J. Zaks) Discrete Math. 241(2001), 333 – 342. 4. The Grunert point of pentagons. Geombinatorics 11(2002), 78 – 84. 5. Levels of orderliness: global and local symmetry. Symmetry 2000, Proc. of a symposium at the Wenner–Gren Centre, Stockholm. Hargitai and T. C. Laurent, eds. Portland Press, London 2002. Vol. I, pp. 51 – 61. 6. No-net polyhedra. Geombinatorics 11(2002), 111 – 114. 7. Connected (n4) configurations exist for almost all n – an update. Geombinatorics 12(2002), 15 – 23. 8. "New" uniform polyhedra. Discrete Geometry: In Honor of W. Kuperberg’s 60th Birthday Monographs and Textbooks in Pure and Applied Mathematics, vol. 253. Marcel Dekker, New York, 2003. Pp. 331 – 350. 9. Convex Polytopes. 2nd ed., V. Kaibel, V. Klee and G. M. Ziegler, eds. Graduate Texts in Mathematics, vol. 221. Springer, New York 2003. 10. Families of point-touching squares. Geombinatorics 12(2003), 167 – 174. Grünbaum had a particularly remarkable talent of seeing new geometry ideas "hiding in plain sight" where other geometers had not noticed these issues. A good example of this is extending the definition of what should be meant by a regular polyhedron which led to many interesting new regular polyhedra. Today these new regular polyhedra are known as the Grünbaum/Dress polyhedra because Andreas Dress noticed one example missing in Grünbaum’s initial enumeration. You can find some samples of the remarkable work of Grünbaum in this earlier Feature Column article. ### An amazing collaboration In trying to determine how Shephard and Grünbaum started their collaboration, one might look to MathSciNet for their earliest joint paper, but in the case at hand this would not return information about a joint venture they were part of. Grünbaum’s highly influential book Convex Polytopes was published in 1967 and one has to look at the table of contents and preface (or the list of Related names on MathSciNet) to realize that some of the chapters were prepared by other people. One of these people was Geoffrey Shephard. In 2005 this book won the American Mathematical Society Steele Prize for Mathematical Exposition. While their earlier research had some aspects of convexity and the properties of polyhedra in common, Grünbaum’s work in many cases had an enumerative flavor. This approach to geometry was less present in Shephard’s work. It was aspects of their common roots but non-identical styles of work that perhaps made their collaboration so fruitful. Shephard points to the fact that G&S met for the first time face-to-face in Copenhagen, Denmark in 1965 at a convexity conference. At a meeting organized by the London Mathematical Society in July of 1975 it seems G&S set in motion the idea that they work together on a 12-chapter book about geometry, with discussion of many ideas about what it might contain. They conceived the idea of starting by writing a single chapter of such a book on patterns and tilings. It turned out that 12 chapters were necessary to do justice to the these ideas. This took about 11 years to develop and swelled to about 700 pages of writing, and it was this work that became their book Tilings and Patterns. The originally planned geometry book never got to be written! There are many aspects of tiling and pattern issues that predate the work of G&S on this topic. However, many of these results are not part of the "standard" topics included in geometry curriculum in America. While many people have noticed with pleasure the multitudinous frieze patterns that they see on buildings, fabrics, and in art, they are unaware of a surprising mathematical result related to these frieze patterns. While one realizes that there are infinitely many different artistic designs that can constitute the "content" of a frieze (ranging from letters of the alphabet, stylized flowers, etc.) there is a mathematical sense in which there are only seven types of such friezes. The 7 types of patterns are shown below (Figure 10). Figure 10 (Diagrams illustrating the 7 different kinds of friezes. Image courtesy of Wikipedia.) Rather amazingly, G&S, by developing the definition of a discrete pattern, were able to breathe fresh life into this rather old topic. By using their "new" notion of a discrete pattern they were able to "refine" the sense in which there are 7 types of friezes into a finer classification under which there are 15 such "discrete frieze patterns." In Figure 11 below, using a small asymmetric triangle as a "building block" one can see how the 7 frieze patterns above can be refined into 15 patterns as pioneered by the work of G&S. The rows of the diagram show how each of the 7 types of friezes sometimes can be refined from one "frieze type" to several discrete pattern types—the letter labels are one method of giving names to these patterns). In thinking about the way the new system refines the old one, notice that in some of these patterns there is a "motif" in a single row and in some of them they can be thought of as being in two rows. The new approach of G&S involves the interaction between the symmetries of the motif and the symmetries related to the "global" pattern arising from translating along the frieze. A few more details can be found in the discussion further along. Figure 11 (15 types of discrete frieze patterns; diagram courtesy of Luke Rawlings.) The diagram shown in Figure 12 deals with some of the challenges that researchers such as Grünbaum and Shephard who were interested in the classification and enumeration of "symmetric" tilings and patterns face. Interest in symmetry has complicated roots related to work in art and fabrics and also from the science side—the study of minerals and crystals and flowers. Figure 12 (A symmetric part of a wallpaper that extends infinitely in both the horizontal and vertical directions. Image courtesy of Wikipedia.) What do we see in Figure 12? We see a portion of what is meant to be a part of an infinite object, extending what is there both in the vertical and horizontal directions. We see color and perhaps we are not sure what the foreground and background are. In Figure 13, do we have a white design on a black background or the other way around? Figure 13 (A tiling of a square using black and white regions. It is not clear if the "design" is black on white or white on black. Image courtesy of Wikipedia.) In Figure 12 it appears that the background might be the "rouge red" but one could perhaps give other interpretations. We see things that seem to be regions where the alternating rows are "separate" bands or friezes. The design that one sees in rows 2 and 4 perhaps remind one of something one might see on a Greek temple. The flower-like pattern of rows 1, 3 and 5 seems to have rotational symmetry as well as mirror or reflection symmetry. Geometers have developed a system of classifying symmetry in the Euclidean plane using distance preserving functions (mappings) which involve translations, rotations, reflections, and glide-reflections. These distance-preserving geometry transformations are known as the isometries. But in addition to such distance-preserving transformations diagrams like the ones in Figure 13, one might have color interchange transformations. There is another interesting difference between the rows that make up this symmetric pattern. The first and second rows both have translational symmetry in the horizontal direction and thus can be viewed as patterns onto themselves as friezes (band, strip) patterns. But the first row can be viewed as having a "discrete" motif which "generates" the pattern, something not true for the 2nd row. While there was a long tradition of looking at friezes and wallpapers which had a periodic structure and classifying them, rather remarkably the idea of looking at "patterns" with a motif like the one in row 1 had never been systematically discussed before Grünbaum and Shephard. Historically rather than looking at motifs, scholars had subdivided the "infinite" design in row 2 by breaking it up into a fundamental region (often there were different choices about how to do this) which was "propagated" via transformations into the periodic frieze or wallpaper. G&S discovered that whereas there was a long, if not always "accurate" tradition of classifying and thinking about polyhedra, both convex and non-convex polyhedra, the situation for tilings (and the even less studied idea of patterns) was much less developed. There was some work on tilings that were the analogues for tiles of the Platonic Solids (work by Pappus) and Archimedean solids (work by Kepler) but little else. There were questions about the rules that one should allow for a tile. Thus, most examples of tilings looked at regions that were touching edge to edge as the "legal" tiles, but did it make sense to allow a region like Figure 14 as a tile or as a motif for a pattern? Figure 14 (Is this "shape" allowed as a tile in a tiling of the plane?) When one uses tiles to fill the plane, such as the tiling by squares which meet edge to edge shown in Figure 14, one has to think about whether or not the square tile is an "open" set (does not include its boundary points) or a "closed" set (contains its boundary points). For enumerations, note that one can get infinitely many "different tilings" with squares that have tiles that don’t all meet edge to edge by sliding some finite or even an infinite number of columns in Figure 15 half the length of one of the sides of the square up or down. What G&S did was to start from scratch in their joint work to give a coherent and accurate account of the "foundations" of a theory of tiling. They also extended classic enumerations by enumerating how many different "patterns" there could be when the motif used was dots, segments or ellipses. Rather surprisingly this had not been done previously. Along the way they had to invent new words for a variety of concepts that helped organize their new theory. Figure 15 (One of the three "regular" Euclidean tilings of the plane known from ancient times. Image courtesy of Wikipedia. Figure 16 (A tiling of the plane with regular hexagons, squares and equilateral triangles. Courtesy of Wikipedia.) While the study of polyhedra has deep roots and multiple "reinventions" of various aspects of the theory, the seemingly neighboring idea of a tiling, while widely present in the art, fabrics and designs of various countries going back thousands of years, had a less obvious footprint in being investigated mathematically. Perhaps this is because mathematical tools to investigate infinite graphs, one way of conceptualizing about tilings, and to discuss symmetry involving something that was "infinite" (the idea of an isometry group) were developed only much later than the tools the Greeks found to study polyhedra. While in modern times symmetry is studied using the tools of graph theory, group theory and the ideas of geometric transformations, in the early study of polyhedra (and tilings) examining the pattern of the polygons surrounding a vertex was the fundamental approach. Thus, even the identity that today is often called Euler’s polyhedral formula, that for a convex bounded polyhedron the number of vertices, faces and edges of the polyhedron are related by $$V + F – E = 2,$$ which might well have been discovered in ancient times was "discovered" in about 1750 by Leonard Euler. This formula, which involves the 0, 1, and 2- dimensional faces of a 3-dimensional polyhedron can be generalized to$n$dimensions. G&S were able to find "rules" for fruitful definitions of tiling and pattern and this was helped by their being able to find a tiling version of the$V + F – E = 2\$ result. Being able to draw on graph theory and combinatorics was a big factor in their successful leap forward beyond prior work. They also were able to draw insights from the study of things which were "asymmetric," such as fractals.

Another thread tied together by the work of G&S was where the notion of an aperiodic tiling fit in. While tilings that had translational symmetry in two different directions was the major topic that had been looked at by mathematicians and crystallographers, Roger Penrose had made the spectacular observation that there were tiles which enable one to tile the plane but these tiles did not allow a tiling that was periodic—had translational symmetry in two directions. The work of G&S clarified and laid the foundation for more discoveries related to non-periodic and aperiodic tilings. Some confusion exists about the concepts of non-periodic and aperiodic tilings. While the definitions one sees are still in flux, here is the intuitive idea. There may be a non-periodic tiling of the plane with one or more tiles, meaning that the tiling involved does not have translational symmetry but when one has a set of tiles that tile the plane aperiodically, there is no way to use the tiles to get a periodic tiling. Historically, in the attention that the mathematics community gave to infinite tilings (patterns) in the plane there was translational (shift) symmetry in two directions involved. There are tiles which are convex quadrilaterals that can tile the plane periodically (all triangles and quadrilaterals tile the plane) and also with rotational symmetry but do not tile the plane aperiodically.

#### Tilings and Patterns

For Geoffrey Shephard, MathSciNet informs us that his "Earliest Indexed Publication" was in 1952 and his "Total Publications" were 149 in number. For Grünbaum MathSciNet informs us that his "Earliest Indexed Publication" was in 1955 and his "Total Publications" were 271 in number. Many of these were joint publications, and in fact, individual and joint published works of G&S exceed these numbers. While MathSciNet lists research papers written by both Grünbaum and Shephard, perhaps their most famous collaboration was the book Tilings and Patterns. This book originally appeared in 1987 and was relatively recently reprinted and updated by Dover Publications. Remarkably the book contained many results not previously published in research papers which complement their joint work in scholarly journals. Tilings and Patterns literally rewrote the landscape of the theory of tilings. Grünbaum and Shephard’s innovation was to try to combine the local and global approaches to tilings in the past so that a more comprehensive look at the phenomenon of tilings and patterns was possible. While the word pattern is widely used in mathematics, its use in conjunction with the word tilings in mathematics is rather novel. Yes, patterns appear in many tilings, but by placing the emphasis on a discrete "motif" G&S opened many new doors.

The collaborative work of Branko Grünbaum and Geoffrey Shepherd has catapulted the areas of discrete geometry involving tilings and patterns to a much broader audience and resulted in many new discoveries based on their ideas. More importantly, their collaboration should be an inspiration to the mathematics community that collaboration is exciting and personally rewarding and can result in giant leaps forward for progress in mathematics and its applications.

### Dedication

I would like to dedicate this column to the memory of the remarkable geometers Branko Grünbaum and Geoffrey Shephard. It was my very good fortune to have had interactions with them both!

#### References

Note: No attempt has been made to give a complete set of the joint papers of Grünbaum and Shephard but several particularly important and interesting examples of their collaborative efforts are listed.

• Brinkmann, G. and P. Goetschalckx, S. Schein, Comparing the constructions of Goldberg, Fuller, Caspar, Klug and Coxeter, and a general approach to local symmetry-preserving operations. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 473 (2017), 20170267.
• Conway, J. and H. Burgiel, C. Goodman-Strauss, The Symmetry of Things, A.K. Peters, Wesley, MA., 2008.
• Delgado, O. and D. Huson, E. Zamorzaeva, The classification of 2-isohedral tilings of the plane, Geometriae Dedicata 42 (1992) 43-117.
• Delgado, O. and D. Huson, 4-regular vertex-transitive tilings of E3. Discrete & Computational Geometry, 24 (2000) 279-292.
• Demaine, E. and J. O’Rourke, Geometric Folding Algorithms, Cambridge University Press, NY, 2007.
Dress, A., A combinatorial theory of Grünbaum’s new regular polyhedra, Part I: Grünbaum’s new regular polyhedra and their automorphism group, Aequationes Mathematicae. 23 (1981) 252-65.

• Dress, A., A combinatorial theory of Grünbaum’s new regular polyhedra, Part II: Complete enumeration, Aequationes Mathematicae 29(1985) 222-243.
• Escher, Maurits C., and D. Schattschneider, Visions of symmetry. Thames & Hudson, 2004.
• Friedrichs, O. Delgado and D. Huson, Tiling space by platonic solids, I. Discrete & Computational Geometry 21, (1999) 299-315.
• Grünbaum, B., Convex Polytopes, John Wiley, New York, 1967. (Parts of this book were developed by V. Klee, M. Perles, and G. C. Shephard.)
• Grünbaum, B., Convex Polytopes, Second Edition, Springer, New York, 2003. (This includes work from the first edition by V. Klee, M. Perles, and G. Shephard and addition input for V. Kaibel, V. Klee and G. Ziegler.)
• Grünbaum, B. Arrangements and Spreads, American Mathematical Society, for Conference Board of the Mathematical Sciences, Providence, 1972.
• Grünbaum, B., The angle-side reciprocity of quadrangles. Geombinatorics, 4 (1995) 115-118.
• Grünbaum, B., Configurations of Points and Lines, American Mathematical Society, Providence, 2009.
• Grünbaum, B.,Side-angle reciprocity – a survey. Geombinatorics, 2 (2011) 55-62.
• Grünbaum, B. and G.C. Shephard, The eight-one types of isohedral tilings in the plane, Math. Proc. Cambridge Phil. Soc. 82(1977) 177-196.
• Grünbaum, B. and G.C. Shephard, Tilings and patterns, Freeman, 1987. (A second updated edition appeared in 2016, published by Dover Press, NY. Errors from the first edition were corrected and notes were added to indicate progress in understanding tilings and patterns.) There also exists a shorter version of the original published by Freeman in 1989, with only the first seven chapters of the original version.)
• Grünbaum, B. and G.C. Shephard, Interlace patterns in Islamic and Moorish art, Leonardo 25 (1992) 331-339.
• Huson, D., The generation and classification of tile-k-transitive tilings of the euclidean plane, the sphere and the hyperbolic plane, Geometriae Dedicata 47 (1993) 269-296.
• McMullen and G.C. Shephard, Convex Polytopes and the Upper Bound Conjecture, London Math. Society, Cambridge U. Press, Cambridge, 1971.
• O’Rourke, J. How to Fold It, Cambridge University Press, NY 2011.
• Rawlings, L., Grünbaum and Shephard’s classification of Escher-like patterns with applications to abstract algebra, Doctoral thesis, Mathematics Education, Teachers College, 2016.
• Roelofs, H. The Discovery of a New Series of Uniform Polyhedra, Doctoral dissertation, 2020.
• Schattschneider, D., The plane symmetry groups: their recognition and notation. American Mathematical Monthly 85 (1978) 439-450.
• Schattschneider, D., The mathematical side of MC Escher, Notices of the AMS 57 (2010) 706-718.
• Shephard, G.C., Convex polytopes with convex, nets, Math. Proc. Camb. Phil. Soc., 78 (1975) 389-403.
• Shephard, G.C., My work with Branko Grünbaum , Geombinatorics, 9(1999) 42-48. (Note the whole Volume 9, Number 2, October 1999 issue of Geombinatorics is a special issue in honor of the 70th birthday of Branko Grünbaum.)
• Stevens, P., Handbook of regular patterns: An introduction to symmetry in two dimensions, MIT Press, Cambridge, 1981.
• Washburn D. and D.W.Crowe, Symmetries of culture: Theory and practice of plane pattern analysis. University of Washington Press, 1988. (Reprinted 2021 by Dover Publications.)
• Washburn D, and D.W. Crowe, editors, Symmetry comes of age: the role of pattern in culture, University of Washington Press, 2004.

Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society’s MathSciNet can be used to get additional bibliographic information and reviews of some of these materials. Some of the items above can be found via the ACM Digital Library, which also provides bibliographic services.