Complex Projective 4-Space

Breaking news: Patrick Stevens (whom you may recognise from the cp4space cipher-solving leaderboard) has published a collection of poems pertaining to Sylow’s theorems.

Anyway, on the real projective plane, there are a couple of geometric theorems worth mentioning. The thing that’s interesting about Pappus’ theorem and Desargues’ theorem is not that they apply to the real projective plane, but rather that whether or not these theorems apply to a particular projective plane can be used to deduce properties of how the plane was constructed. I’ll start by stating the theorems:

Pappus’ theorem: If we have eight of the nine concurrences shown in the diagram above, then the ninth also holds. In the complex projective plane, this follows from the Cayley-Bacharach theorem.

Desargues’ theorem: Two triangles are in perspective about a point if and only if they are in perspective about a line (see above). Equivalently, suppose we have a collection of 10 points and 10 lines, associating an ordered pair (p(V), l(V)) of a point and a line to each vertex V of the Petersen graph, where each edge is replaced with a zweibeck (pair of oppositely directed edges). We consider each directed edge X → Y to represent the point p(X) and the line l(Y). Desargues’ theorem states that if 29 of these correspond to incidences (a point lying on a line), then so does the thirtieth.

A German mathematician called Hessenberg proved that Desargues’ theorem can actually be deduced from Pappus’ theorem. In other words, all Pappian projective planes are also Desarguesian. For example, the real and complex projective planes, and the projective planes of finite order, are all Pappian, so thus Desarguesian.

The converse of Hessenberg’s theorem is not true, however. The quaternionic projective plane is Desarguesian, but not Pappian. It transpires that this is a consequence of the quaternions being non-commutative. Indeed, the following have been proved:

• Every Desarguesian plane can be constructed from a skew-field F, by working in the vector space F³, discarding the origin and identifying scalar multiples of a point. The converse is also true.
• The Pappian planes are precisely those constructed from a commutative field F.

This is quite remarkable, since non-Desarguesian planes can be really bizarre. Some correspond to this sort of construction (e.g. the octonionic projective plane, or Cayley plane), whereas others are downright pathological (e.g. the Moulton plane).

If a plane can be embedded in a three-dimensional projective space, it is automatically Desarguesian. Consequently, it is impossible tohave an octonionic 3-space , as that would imply that the Cayley plane is Desarguesian (which it isn’t). The proof of this is quite simple, and follows from letting ABC and A’B’C’ in the diagram be triangles in different planes (so A”B”C” must trivially be the line where the planes intersect), and projecting down into two dimensions.

A fascinating paper by Louis Kauffman establishes the equivalence of the four-colour theorem (the assertion that any planar graph can have its vertices coloured with one of four colours, such that neighbouring vertices have different colours) to the following seemingly unrelated combinatorial statement:

• Let n be a positive integer, and let A and B be two complete parenthesisations of the expression , where × is the three-dimensional cross product. Then we can assign each of to be either i, j or k such that the two expressions are non-zero and equal.

Moreover, the proof is not particularly complicated. Firstly, we shall examine other restatements of the four-colour theorem.

Vertex, face and edge colourings

In its simplest form, the four-colour theorem states that we can colour the vertices of a planar graph with at most four colours, such that no adjacent vertices have the same colour. For example, take the graph of the icosahedron, which is indeed planar:

Tait proved that this is equivalent to the statement that every bridgeless planar 3-regular graph can have its edges coloured with three colours, such that every vertex is incident with precisely one edge of each colour. It’s not too difficult to reconstruct the intermediate steps without ever having seen the proof, just by knowing the two propositions and by employing reasoning.

Firstly, note that Tait’s statement is about planar graphs where every vertex has degree 3. Conversely, the worst-case scenario of the original statement is where every face is a triangle (since any planar graph can be ‘triangulated’ into this form). Hence, a good idea is to form the planar dual of the worst-case scenario of the original statement:

We can colour the faces of a 3-regular plane (or spherical) graph with four colours, such that no two faces of the same colour share a common edge.

The 4-colouring of the vertices of the icosahedral graph, for instance, is equivalent to the following 4-colouring of the faces of the dodecahedral graph:

Now, to convert this to a 3-colouring of the edges, we want to somehow assign a colour to an edge based on the colours of the neighbouring regions, and to do this in a nicely reversible way. To do so, let the regions be coloured with elements of the Klein 4-group, and the edges be coloured by the product of the two regions. Since it’s Abelian and every element is its own inverse, we obtain a colouring of the edges with the non-identity elements of the Klein 4-group. Supposing that yellow is the identity, we get the following edge-colouring:

This establishes the equivalence of the four-colour theorem and Tait’s restatement. Not too difficult, was it? Now, we can start to see the similarity with Kauffman’s combinatorial problem. If we ignore the signs of the vectors, then the colours of these edges can be the three unit vectors i, j, k, and the vertices correspond to the cross product operation. Parenthesisations are equivalent to binary trees, so (temporarily ignoring signs) Kauffman’s combinatorial problem is just Tait’s restatement applied to the special case of graphs obtained from gluing two equally-sized trees together.

Dealing with signs

One of the subtleties is that it is not immediately obvious that we would necessarily get A = B, rather than A = −B. To overcome this, Kauffman employed an idea by Roger Penrose of assigning either i or −i (complex numbers, not quaternions or unit vectors!) to each vertex, depending on whether the colours of the three edges are arranged in clockwise or anticlockwise order. Then, Kauffman shows that the product of the vertices is 1, which is equivalent to the signs working out correctly.

Proofs of the four-colour theorem

The first correct proof of the four-colour theorem was Appel and Haken’s massive case-bash, which relied on machine-checking each of 1936 configurations for reducibility. Essentially, they proved that any counter-example to the four colour theorem could be reduced to a smaller counter-example, so by induction the theorem is true.

Recently, a proof was announced of the snark conjecture, that any snark (bridgeless 3-regular graph with no 3-edge-colouring) must contain the Petersen graph as a minor. This is clearly a generalisation of Tait’s restatement of the four-colour theorem, which is the contrapositive of ‘no snark is planar’. The Petersen graph is both the simplest snark and the first to be discovered.

The Petersen graph is also a forbidden minor for the set of linklessly embeddable graphs (those which cannot be drawn in three-dimensional space without two cycles forming a Hopf link), so it follows that any bridgeless linklessly embeddable 3-regular graph must have a 3-edge-colouring, generalising Tait’s restatement of the four-colour theorem.

The proof of the snark theorem is largely unpublished, although apparently it is another computer-assisted proof. Hence, it (unfortunately!) does not provide a counter-example to Doron Zeilberger’s ultimate fantasy of the four-colour theorem having no ‘human’ proofs.

Usually, it is very difficult to find a reasonably naturally-defined sequence which is not present on the Online Encyclopedia of Integer Sequences. The OEIS contains everything from the ubiquitous Bernoulli numbers and the fascinating Golomb self-referential sequence, to such utterly pointless trivialities as A171056 (the primes, but where every ‘7’ is replaced with a ‘9’ and vice-versa in the decimal expansions). More examples on the entire spectrum were competitively evaluated over at the Aperiodical.

Hence, I was rather surprised to see that the following sequence does not feature:

2, 6, 14, 22, 30, 34, 38, 42, 58, 66, 70, 78, 86, 94, ...

The motivation for this sequence was the observation that the numbers {2013, 2014, 2015} are each squarefree and have three prime factors. Ignoring the second condition, we can consider runs of consecutive squarefree numbers. Clearly, the longest such runs have length 3 (as in this example), since no multiple of 4 can possibly be squarefree.

• Definition: A positive integer N is described as comfortably squarefree if N − 1, N and N + 1 are all squarefree.

It is not difficult to obtain an infinite product expansion for the asymptotic density of comfortably squarefree numbers. An integer N is comfortably squarefree if and only if for every prime p, the residue of N modulo p² is not in the set {−1, 0, 1}. With a slight amount of work, this leads to the following asymptotic density:

If that 3 is replaced with a 1, it yields the density of squarefree integers, . Unfortunately, this does not appear to have a closed form. Numerically, I have evaluated δ ≈ 0.125486980906, where the final digit may be slightly off. Plugging this into Robert Munafo’s RIES doesn’t return anything, which is a shame as it is usually good at finding these sorts of things.

Even more bizarre is the fact that pairs of consecutive squarefree numbers have been investigated, mentioned at the end of the MathWorld article, and heavily featured on the OEIS. Hence, not believing that triples of consecutive squarefree numbers could possibly be a new concept, I searched this on Google (yes, this came after deriving the asymptotic density and numerically computing it!) and sure enough there was a MathOverflow question asking whether there are infinitely many examples.

Anyway, I’ll upload the sequence of comfortably squarefree numbers to the OEIS tomorrow, assuming no-one beats me to it.

In this rather popular video, Vi Hart experiments with the patterns that can be formed by connecting the vertices of a regular polygon with straight lines of equal length.

[youtube=http://www.youtube.com/watch?v=CfJzrmS9UfY]

In addition to the obvious number-theoretic interpretation, there is a nice group-theoretic interpretation that generalises well to higher dimensions. For instance, Vi Hart’s ‘square star’ composed of four squares can be thought of as a 3-tuple, namely:

• The full group G = D32 of symmetries of the star;
• A normal subgroup H = D8 of symmetries fixing each of the components;
• The quotient group G/H = C4 of cyclic permutations.

With two dimensions, these things are really easy to find, and completely classified by Vi Hart’s video. On the other hand, the multidimensional analogues are really exceptional objects. The standard five-pointed pentagram has four three-dimensional versions, the Kepler-Poinsot polyhedra, and ten four-dimensional analogues, the Schläfli-Hess polychora. One of the Kepler-Poinsot polyhedra is the small stellated dodecahedron, immortalised in card by Joseph Myers:

Of course, for the group theory to come into play non-trivially, we are interested in examples where we have a compound of polytopes, analogous to the six-pointed Star of David. Together with the restriction that both the convex hull and constituent polytopes are regular, the only possibilities are:

• Three 16-cells in four dimensions, with the same vertices as a 24-cell (quotient S3).
• Two tetrahedra in three dimensions, with the same vertices as a cube (quotient C2).

If the convex hull is not required to be regular, then other possibilities include two dual 24-cells in four dimensions, two dual simplices (in any number of dimensions), and six 16-cells in four dimensions (by combining two of the previous results).

Anyway, the unique three-dimensional example is the stella octangula, a compound of two dual tetrahedra. It appears twice in Escher’s Stars, and there’s even a variant of the Rubik’s cube based on it. As one can imagine, it has also been constructed by Joseph Myers:

The visible surface can also be obtained by gluing eight regular tetrahedra to an octahedron, in the way that occurs in the dual tiling to the rhombic dodecahedral honeycomb.

Stella octangula numbers

By analogy with triangular numbers, square numbers and tetrahedral numbers, the sequence of stella octangula numbers has been investigated. For instance, 245 is a stella octangula number, since we can fill a stella octangula with 245 spheres in a FCC arrangement:

David Eppstein has even assembled 124 magnetic balls into a stella octangula, for the Wikipedia article on stella octangula numbers.

As with all three-dimensional figurate numbers, they are values of a cubic polynomial. Hence, if we try to find stella octangula numbers which are also square, we have the standard problem of locating integer points on an elliptic curve, of which there are finitely many. It was proved that the only such numbers are 1 (trivially) and 9653449.

A similar problem is to find pyramidal numbers which are square. The single non-trivial solution to this is much more well-known: 1² + 2² + … + 24² = 70². This is intimately related to a particular construction of the Leech lattice, where one begins with a much simpler (25+1)-dimensional even unimodular lattice in Minkowski space, and chooses the 24-dimensional plane of null vectors orthogonal to the null vector (70; 1, 2, 3, …, 24).

This article can be regarded as a sequel to my 5 × 5 monotile. Since its announcement, several variants have been discovered. In particular, towards the end of this article we shall present a three-dimensional monotile with the following properties:

• Nonperiodic by the definition given in Socolar-Taylor (2010);
• No tiling has translational symmetry.

These properties have been independently achieved before (the first by the three-dimensional Socolar-Taylor tile; the second by the Schmitt-Conway-Danzer biprism and the aforementioned 5 × 5 monotile), but this appears to be the first time that a single prototile satisfies both properties. Unfortunately, the tiling still admits screw symmetry, so it is not strongly aperiodic.

Primitive and balanced monotiles

Note that the 5 × 5 monotile is completely specified by the pair (3 + 4i, 5) of Gaussian integers of equal norm. The first of these gives the period of the tile with respect to the grid of knobbles on the upper surface, and the second gives the period of the tile with respect to the grid of indentations on the lower surface.

A variant is described as primitive if (z, w) have equal norm and are coprime. The aforementioned example is not primitive, since we can take out a common factor of 1 + 2i, giving the primitive pair (1 + 2i, 1 − 2i). Since the periods are complex conjugates, we describe the monotile as being balanced.

Note that, unlike the examples where w is an integer, we’re not actually allowed to have the knobbles protruding over the edge, since that would result in the indentations also protruding (obviously impossible).

If a balanced tile is flipped over, the knobbles and indentations precisely switch positions. If, instead, we replace both the knobbles and indentations with a self-complementary shape, then the tile will have dihedral symmetry (invariant under being flipped over). This will be useful for the culmination of this article: a nonperiodic translation-free monotile.

Hexagonal variants

Warren Smith (of n-body fame) proposed a hexagonal variant, based upon the Eisenstein integers rather than the Gaussian integers. The simplest primitive balanced monotile has seven knobbles and is specified by the pair (3 + ω, 3 − ω), where ω is a primitive cube root of unity.

As described at the end of the previous section, this can be modified to give a self-complementary variant invariant under the operation of ‘flipping over’, and exhibiting a rotational symmetry group isomorphic to the dihedral group D12. (For an explicit construction, replace each knobble and indentation with a hexagonally-symmetric ring of alternating pegs and grooves.)

So far, this is no qualitatively different from the monotiles discussed earlier. However, we can then slice this hexagonal prism along its equator, separating the two halves slightly and inserting [the Cartesian product of an interval with] a Taylor-Socolar aperiodic monotile. In particular, we choose the disconnected variant from Figure 6 of the paper by Socolar and Taylor:

The problem with this is that we now have a disconnected 3D tile with the desired properties (nonperiodic and translation-free). Nevertheless, it can be converted into a connected tile (indeed, a polyhedron) by ‘skewering’ the other connected components with helical protrusions, and boring complementary helical holes in the prisms (c.f. duck genitalia, but without the problematic chirality issues).

On an infinite square lattice, the B36/S125 cellular automaton proceeds similarly to Conway’s Game of Life (B3/S23), but with different birth and survival conditions. Specifically, a dead cell becomes live if surrounded by 3 or 6 live neighbours, and a live cell survives if surrounded by 1, 2 or 5 live neighbours. As usual (c.f. question 9), each cell dies unless specified otherwise.

The dynamics are not as interesting as the Game of Life, although there is a naturally-occurring glider and related infinite-growth pattern (discovered by Nathaniel Johnston during a massive search with random initial conditions):

One of the more interesting properties of the cellular automaton is that if the universe is composed entirely of 2 × 2 blocks in a square lattice arrangement, this will be the case for all time. We can think of B36/S125 as emulating a simpler cellular automaton:

This cellular automaton is slightly unusual in that the cells are in different positions in odd generations and even generations. A spacetime diagram of this gives truncated octahedral cells in a configuration known as the body-centred cubic lattice:

For want of a better term (block cellular automaton is slightly ambiguous, and can refer to the similar — albeit distinct — concept of a Margolus neighbourhood), I shall henceforth refer to these as BCC automata. Nathaniel Johnston investigated rectangular oscillators in the BCC automaton arising from B36/S125, showing how they in turn emulate an even simpler (one-dimensional) cellular automaton, namely Wolfram’s Rule 90. It transpires that this behaviour was investigated earlier by Dean Hickerson on the notorious Usenet group, comp.theory.cell-automata.

Oscillators of periods 6 (2^3 – 2) and 14 (2^4 – 2) in the B36/S125 cellular automaton.

Emulation can go in the opposite direction. For a cellular automaton such as Life, we can arbitrarily group the cells into 2 × 2 blocks, thus enabling it to be emulated in a 16-state BCC automaton. This is used as the base case for Bill Gosper’s algorithm HashLife, which uses hashed quadtrees to simulate patterns frighteningly quickly.

In three dimensions, an aperiodic monotile is a solid capable of tiling space, but not in such a way that admits translational symmetry. The question of existence of aperiodic monotiles stems from a weaker question, which formed part of Hilbert’s eighteenth problem:

Does there exist a polyhedron capable of tiling space, but not tile-transitively?

The first example of an anisohedral tile was found in 1928 by Karl Reinhardt. An aperiodic monotile would obviously be anisohedral, although it surprisingly took 60 years before Schmitt found the first aperiodic example in 1988.

The purpose of this post is to present a new monotile I discovered a few days ago, and which seems like it could have been discovered much earlier than 1988. I also claim that its structure and proof of aperiodicity are simpler (i.e. easier to reconstruct) than any other aperiodic monotile.

Structure

The aperiodic monotile is essentially a 5 × 5 Lego brick, where the grid of knobbles on the top (but not the complementary indentations on the bottom) have been rotated by the arctangent of ¾. Five such monotiles are shown in the diagram above. Four of the knobbles overhang, although reducing their diameter could overcome that. Similarly, if you prefer polyhedra to arbitrary solids, you can replace the cylindrical knobbles with square prisms.

Its existence stems from the Pythagorean identity 3² + 4² = 5², and this construction should generalise to any primitive Pythagorean triple. Of course, this is the simplest, and therefore the most preferable. Note that in this case, the knobbles on the top are in a centred square arrangement, rather than a square (and that relies on 3 and 4 being consecutive).

Proof

The only result that we’ll use is the fact that the Gaussian integers (complex numbers with integer real and imaginary parts) form a unique factorisation domain. This isn’t any more difficult to prove than the Fundamental Theorem of Arithmetic, which is the equivalent statement over the ordinary integers.

The first part of the proof is to show that the only tilings are the ‘obvious’ ones, where the monotiles form layers, each of which is a square lattice, and each layer is rotated by the arctangent of ¾ with respect to the layer below. Each tile forces tiles to exist above and below it, and rotated by this angle. This produces some overhang, which means that surrounding tiles are forced and (by induction) the entire tiling is arranged in layers.

The next part of the proof shows that no two layers have the same orientation. This is equivalent to showing that the complex number is not a root of unity. Suppose that it is a kth root of unity, in which case we obtain the identity , which clearly violates unique factorisation. Hence, by a reductio ad absurdum argument, we win.

Consequently, if the tiling has any translational symmetry at all, it must be purely horizontal. We represent a translation by (x, y, 0) by the complex number z = x + i y. By considering the knobbles on one layer, we know that z must be a Gaussian integer (i.e. divisible by 1). By considering the knobbles on the layer above, z must also be divisible by . Considering all of these layers and using unique factorisation, we get that z is divisible by all integer powers of 2 + i, which is only the case for z = 0. So the tiling cannot have non-trivial translational symmetries, completing the proof of aperiodicity. Q. E. D.

Weakly versus strongly aperiodic

This monotile, together with Schmitt’s original monotile and the Schmitt-Conway-Danzer tile, can tile space screw-symmetrically. As such, it is described as weakly aperiodic. There are no known examples of strongly aperiodic monotiles (admitting no infinite cyclic groups of symmetries), but a step forward in this direction is the aperiodic monotile by Joan Taylor and Joshua Socolar.