Some knots

I have been reading up on knots recently, so here is a table of 8 knots with up to 6 crossings (plus 2 extras), along with their Conway polynomials. These are polynomials that can be associated with each knot. Different polynomials imply different knots, but sometimes different knots have the same polynomial. Some examples are shown in red below. I have also included pictures of the ten knots mentioned (not drawn by me).

Knot Conway polynomial
01 (Unknot) 1
31 (Trefoil knot) z2 + 1
41 (Figure-eight knot) 1 − z2
51 (Cinquefoil knot) z4 + 3 z2 + 1
52 (Three-twist knot) 2 z2 + 1
61 (Stevedore’s knot) 1 − 2 z2
62 (Miller Institute knot)  − z4 − z2 + 1
63 z4 + z2 + 1
946 1 − 2 z2
10132 z4 + 3 z2 + 1

The pancake theorem

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

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

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

The Borsuk–Ulam theorem

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

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

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

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

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

The Projective Plane

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

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

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

Video produced using the R animation package.

The Klein Bottle

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

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

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

Video produced using the R animation package.

The Circle of Fifths

I have often tried to visualise the circle of fifths in a way that makes sense both musically and mathematically. Above (click to zoom) is my latest attempt.

There are 12 notes in an octave (7 white piano keys and 5 black piano keys), and the diagram shows these 12 piano keys wrapped into a circle. A fifth is a step of 7 semitones (7 piano keys, counting black ones, e.g. C→D♭→D→E♭→E→F→F♯→G). The coloured spiral in the chart shows the “circle of fifths” resulting from moving up a fifth 12 times (moving left to right, and hence moving anticlockwise).

The reason that this works is that 7 and 12 have no common factor – and therefore the first multiple of 7 that is also a multiple of 12 is 7 × 12. Therefore every time you move up a fifth you get a different note, returning to the starting note only when you have moved up 12 times. In the process, you have hit every other note exactly once.

Topic Analysis on the New Testament

I have been experimenting recently with Latent Dirichlet allocation for automatic determination of topics in documents. This is a popular technique, although it works better for some kinds of document than for others. Above (click to zoom) is a topic matrix for the Greek New Testament (using the stemmed 1904 Nestle text, removing 47 common words before analysis, and specifying 14 as the number of topics in advance). The size of the coloured dots in the matrix shows the degree to which a given topic can be found in a given book. The topics (and the most important words associated with them) are:

A better set of topics can probably be obtained with a bit more experimentation. Alternatively, here (as a simpler form of analysis) are the relative frequencies of some Greek words or sets of words, scaled to the range 0 to 1 for each word set (with the bar chart showing the total number of words in each New Testament book). Not surprisingly, angels appear more frequently in Revelation than anywhere else, while love is particularly frequent in 1 John:

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

Mathematics and Art: Why can’t we be friends?

The figures of Geometry and Arithmetic by the Coëtivy Master, late 15th century (detail from Philosophy Presenting the Seven Liberal Arts to Boethius)

For most of history, mathematics and the visual arts have been friends. Art was not distinguished from what we now call “craft,” and mathematics – geometry and arithmetic – provided both a source of inspiration and a set of tools. Polykleitos, for example, in the 5th century BC, outlined a set of “ideal” proportions for use in sculpture, based on the square root of two (1.414…). Some later artists used the golden ratio (1.618…) instead.

Symmetry has also been an important part of art, as in the Navajo rug below, as well as a topic of investigation for mathematicians.

Navajo woollen rug, early 20th century (Honolulu Museum of Art)

The Renaissance saw the beginning of the modern idolisation of artists, with Giorgio Vasari’s The Lives of the Most Excellent Painters, Sculptors, and Architects. However, the friendship between mathematics and art became even closer. The theory of perspective was developed during 14th and 15th centuries, so that paintings of the time have one or more “vanishing points,” much like the photograph below.

Perspective in the Galerie des Batailles at Versailles (base image: 1890s Photochrom print, Library of Congress)

Along with the theory of perspective, there was in increasing interest in the mathematics of shape. In particular, the 13 solid shapes known as Archimedean polyhedra were rediscovered. Piero della Francesca rediscovered six, and other artists, such as Luca Pacioli rediscovered others (the last few were rediscovered by Johannes Kepler in the early 17th century). Perspective, polyhedra, and proportion also come together in the work of Albrecht Dürer. Illustrations of the Archimedean polyhedra by Leonardo da Vinci appear in Luca Pacioli’s book De Divina Proportione.

Illustration of a Cuboctahedron by Leonardo da Vinci for Luca Pacioli’s De Divina Proportione (1509)

Some modern artists have continued friendly relations with mathematics. The Dutch artist M. C. Escher (reminiscent of Dürer in some ways) sought inspirations in the diagrams of scientific publications, for example.

Tiling by M. C. Escher on the wall of a museum in Leeuwarden (photo: Bouwe Brouwer)

Today it is possible to follow in Escher’s footsteps by studying a Bachelor of Fine Arts / Bachelor of Science double degree at some institutions. There is also a renewed interest in the beauty of mathematical objects, whether three-dimensional (such as polyhedra) or two-dimensional (such as the Mandelbrot set). The role of the artist then becomes that of bringing out the beauty of the object through rendering, colouring, choice of materials, sculptural techniques, and the like.

View of the Mandelbrot set at −0.7435669 + 0.1314023 i with width 0.0022878 (image: Wolfgang Beyer)

Artistic techniques such as these (“must we call them “craft” or “graphic design”?) are also important in the field of data visualisation, and are recognised by the “Information is Beautiful” Awards. Speaking of which, this year’s awards are now open for submissions.

Sequences, R, and the Free Monoid

An important concept in computer science is the free monoid on a set A, which essentially consists of sequencesa1an⟩ of elements drawn from A. The key operations on the free monoid are:

  • a⟩, forming a singleton sequence from a single element of A
  • xy, concatenation of the sequences x and y, which satisfies the associative law: (xy)⊕z = x⊕(yz)
  • ⟨⟩, the empty sequence, which acts as an identity for concatenation: ⟨⟩⊕x = x⊕⟨⟩ = x

The free monoid satisfies the mathematical definition of a monoid, and is free in the sense of satisfying nothing else. There are many possible implementations of the free monoid, but they are all mathematically equivalent, which justifies calling it the free monoid.

In the R language, there are four main implementations of the free monoid: vectors, lists, dataframes (considered as sequences of rows), and strings (although for strings it’s difficult to tell where elements start and stop). The key operations are:

Vectors Lists Dataframes Strings
⟨⟩, empty c() list() data.frame(n=c()) ""
a⟩, singleton implicit (single values are 1-element vectors) list(a) data.frame(n=a) as.character(a)
xy, concatenation c(x,y) c(x,y) rbind(x,y) paste0(x,y)

An arbitrary monoid on a set A is a set B equipped with:

  • a function f from A to B
  • a binary operation xy, which again satisfies the associative law: (xy)⊗z = x⊗(yz)
  • an element e which acts as an identity for the binary operator: ex = xe = x

As an example, we might have A = {2, 3, 5, …} be the prime numbers, B = {1, 2, 3, 4, 5, …} be the positive whole numbers, f(n) = n be the obvious injection function, ⊗ be multiplication, and (of course) e = 1. Then B is a monoid on A.

A homomorphism from the free monoid to B is a function h which respects the monoid-on-A structure. That is:

  • h(⟨⟩) = e
  • h(⟨a⟩) = f(a)
  • h(xy) = h(x) ⊗ h(y)

As a matter of fact, these restrictions uniquely define the homomorphism from the free monoid to B to be the function which maps the sequence ⟨a1an⟩ to f(a1) ⊗ ⋯ ⊗ f(an).

In other words, simply specifying the monoid B with its function f from A to B and its binary operator ⊗ uniquely defines the homomorphism from the free monoid on A. Furthermore, this homomorphism logically splits into two parts:

  • Map: apply the function f to every element of the input sequence ⟨a1an
  • Reduce: combine the results of mapping using the binary operator, to give f(a1) ⊗ ⋯ ⊗ f(an)

The combination of map and reduce is inherently parallel, since the binary operator ⊗ is associative. If our input sequence is spread out over a hundred computers, each can apply map and reduce to its own segment. The hundred results can then be sent to a central computer where the final 99 ⊗ operations are performed. Among other organisations, Google has made heavy use of this MapReduce paradigm, which goes back to Lisp and APL.

R also provides support for the basic map and reduce operations (albeit with some inconsistencies):

Vectors Lists Dataframes Strings
Map with f sapply(v,f), purrr::map_dbl(v,f) and related operators, or simply f(v) for vectorized functions lapply(x,f) or purrr::map(x,f) Vector operations on columns, possibly with dplyr::mutate, dplyr::transmute, purrr::pmap, or mapply Not possible, unless strsplit or tokenisation is used
Reduce with ⊗ Reduce(g,v), purrr::reduce(v,g), or specific functions like sum, prod, and min purrr::reduce(x,g) Vector operations on columns, or specific functions like colSums, with purrr::reduce2(x,y,g) useful for two-column dataframes Not possible, unless strsplit or tokenisation is used

It can be seen that it is particularly the conceptual reduce operator on dataframes that is poorly supported by the R language. Nevertheless, the map and reduce operations are both powerful mechanisms for manipulating data.

For non-associative binary operators, purrr::reduce(x,g) and similar functions remain extremely useful, but they become inherently sequential.

For more about purrr, see