Complex Projective 4-Space

Firstly, I would like to announce that today is the Ides of March.

Secondly, I was alerted on two semi-recent occasions to this beast of a puzzle, namely the regular expression crossword. Like a normal crossword, you populate the empty cells of a grid with letters such that the resulting lines agree with the corresponding clues. However, as you can see below, there are a few fundamental differences:

The clues are regular expressions, which constrain the possible strings of letters. For example, the regular expression ‘[CR]*’ uses the Kleene star to enable arbitrary strings to be formed over the alphabet {C,R}. For example, CCRRC, R, CC and the empty string all fit this regular expression, whereas the string RRGCR does not. Other symbols have different properties.

Another disparity between this and conventional crosswords is the underlying lattice. Instead of the square tiling, , the author has chosen to use a hexagonal tiling instead. Consequently, each cell lies on three lines, and the clues point in three directions.

This mention of ‘three directions’ provides a neat segue on to my third and final point. I feel compelled to draw your attention to an excellent music video published yesterday by the Three Directions, entitled ‘That Makes It Invertible’. Skip to 1:10 in the following video to listen to the song:

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

(Sorry about the recent dearth of cp4space postings; I’ve been rather busy in real Euclidean 3-space, .)

Quite a large class of self-similar geometrical objects can be expressed as iterated function systems. For instance, the Sierpinski triangle is composed of three copies of itself, each scaled by a factor of ½ and translated by a cube root of unity. More elaborate self-similar sets can be generated by applying other combinations of affine transformations, such as the Barnsley fern:

In most cases, the Hausdorff dimension is not an integer, in which case the object is referred to as a fractal. For instance, the aforementioned Sierpinski triangle has a dimension of log(3)/log(2). The Cantor ternary set, on the other hand, has a dimension of log(2)/log(3).

A rather paradoxical fractal is Antoine’s necklace. Firstly, you begin with a plain, bog-standard torus:

Then, place a circular chain of linked tori inside the torus, like so:

We can repeat this process inside each of these tori, and so on ad infinitum. Taking the intersection of the (nested) sets obtained at each stage, the result is homeomorphic to the Cantor set. However, the complement is not simply-connected, and therefore not homeomorphic to the complement of the usual embedding of the Cantor set in 3-space. More details are included here.

Antoine’s necklace can be used to construct another unusual object, Antoine’s horned sphere. This is obtained by taking a sphere, and extending a tentacle from its surface, which penetrates the initial torus in the construction of Antoine’s necklace. Inside the torus, the tentacle branches into more tentacles, which penetrate each of the sub-tori. This results in a tangled dendritic mess, which is homeomorphic to the 3-ball. However, quite alarmingly, the complement of the horned sphere is not homeomorphic to the complement of the 3-ball. Another such ‘exotic embedding’ of the 3-ball is Alexander’s horned sphere.

The determinant of a matrix can be regarded, most naturally, as the volume scaling factor of the corresponding linear map. However, one of the formulae for finding the determinant of a square matrix is to compute , where we sum over all permutations and take their signs into account.

But what if we omit the term ? We get a related notion, known as the permanent of a matrix. This is far less useful than the determinant, but it does have a few applications.

Perfect matchings

Suppose we have a bipartite graph, and want to compute the number of perfect matchings. In this case, we can express it as the permanent of the biadjacency matrix.

One special family of bipartite graphs are the crown graphs. A crown graph can be defined as a bipartite graph, the biadjacency matrix of which is the complement of the identity matrix. The permanent of a crown graph on 2n vertices is given by the closest integer to .

Crown graphs on 6, 8 and 10 vertices, respectively

The menage problem asks how many ways n couples (each containing one man and one woman; I apologise for the heteronormative nature of this) can be seated around a circular table of 2n seats, such that each person sits adjacent to neither his or her partner, nor anyone of the same same gender. It is not too difficult to see these arrangements correspond to Hamiltonian cycles of crown graphs. The solution sequence is given by A094047.

Domino tilings

Another type of bipartite graph arises when you replace each square in a polyomino with a vertex, and join adjacent vertices with edges. For example, the bipartite graph arising from the Mutilated Chessboard Problem is shown below:

Since its biadjacency matrix has 32 rows but only 30 columns, it is not square and therefore does not have a well-defined permanent. Hence, there is no way to tile the mutilated chessboard with dominoes.

It transpires that in the case of tiling polyominoes with dominoes, we can define a slightly altered biadjacency matrix, by weighting vertical edges with 1 and horizontal edges with the imaginary unit i. In that case, the determinant of the new matrix is equal to the permanent of the old one, and therefore the number of domino tilings.

This may seem like a pointless modification, but it massively accelerates computation. General determinants can be computed much more efficiently than permanents, namely in polynomial time . On the other hand, if arbitrary permanents can be calculated in polynomial time, then P = NP follows as a corollary.

For a chessboard, the determinant of the modified biadjacency matrix was proved by Kasteleyn to have the following closed form:

For m = 2, the number of tilings is the Fibonacci number F(n+1).

Spanning trees

The number of spanning trees of a particular graph can also be expressed as the determinant of a matrix, thanks to Kirchoff’s theorem. It is a remarkable fact that the number of domino tilings of a chessboard with one corner removed is precisely the number of spanning trees of a m by n grid graph, as mentioned here. Here are the 15 spanning trees of a particular grid graph, grouped into congruence classes:

And here are the 15 corresponding domino tilings:

I have joined pairs of tilings with an edge if they can be interconverted by rotating a single square of two dominoes. It has been proved that for any simply-connected polyomino, the resulting graph of domino tilings is connected. Of course, this is untrue for multiply-connected polyominoes (consider the two tilings of a 3 × 3 square with the centre removed).

In this case, the resulting graph of tilings is bipartite. This is true in general, as the number of horizontal dominoes (modulo 4) must alternate between 0 and 2 every time you move along an edge. Indeed, in the example shown above, the graph corresponds to a polyomino. This, however, is just a coincidence: with arbitrarily large polyominoes, we can get tilings with arbitrarily many neighbours.

The connect sum of two knots is obtained by joining them together in the obvious way. There is, however, one small detail. If you define this naïvely, then you won’t necessarily obtain an unambiguous connect sum. For instance, consider the following:

It’s difficult to show that the two above knots are non-equivalent (as usual), but it is indeed the case. The best way to avoid this problem is to consider directed knots instead of undirected knots. The knot shown below is one of the simplest ‘non-invertible knot’, i.e. one which cannot be deformed into itself such that the directions of the arrows change:

The first example can be viewed as the sum of two equally directed knots, whereas the second example is the sum of two oppositely directed knots. Now that we’ve imposed direction, the connect sum of knots is well-defined; I’ll leave proving it as a straightforward exercise for the reader.

Note that connect sum is both commutative and associative, with the unknot O (simple loop) forming an identity. The set of knots under the operation of connect sum is thus an Abelian monoid.

For this to be an Abelian group, we would need inverses. Unfortunately, this is not the case; for instance, there is no knot A that behaves as an ‘anti-trefoil’:

A simple proof of this is to note that the trefoil knot is tricolourable, whereas the unknot is not, and that the connect sum of a tricolourable knot and an arbitrary knot gives another tricolourable knot. This contradicts the above equation, so there is no anti-trefoil. Indeed, more generally, there are no two non-trivial knots A and B such that . The standard proof is the Mazur swindle:

This appears to be massively cheating. For instance, the argument could be applied to 1 and −1 to deduce that 1 = 0, which is clearly erroneous. However, it is intuitive that this reasoning works in the context of knots, since it can be realised geometrically.

Interestingly, the Abelian monoid of knots exhibits unique factorisation (Schubert’s theorem), so it suffices to categorise the ‘prime’ knots that cannot be expressed as connect sums. The knots tabulated by Rolfsen were the prime knots, the first few of which can be viewed here.

Other applications

In addition to knot theory, the principle of the Mazur swindle can be applied to other objects. For instance, we can express the free module as the direct sum of itself and something which isn’t a free module over . Without this idea, it’s pretty difficult to find modules satisfying these properties.

Some things have actually happened. A few of these are worth mentioning.

RMM 2013 results

Firstly, the results of the Romanian Master of Mathematics (RMM 2013) competition have been published. There have been two perfect scores this year (very rare for RMM), namely Ömer Cerrahoğlu (Romania) and Krachun Dmitrii (Russia). Third in line was our very own Matei Mandache, who scored an impressive 35/42, achieving a gold medal in the process. The UK team also had another gold medallist, namely Daniel Hu.

The UK team came third (beaten only by the USA and Russia), achieving two gold medals, a silver and a bronze. The two remaining contestants each had a Double Honourable Mention, which is very respectable for competitions of this difficulty.

Multicoloured ants

Tim Hutton, Ed Pegg, Georgi Gochev and Mark Jeronimus have been exploring the space of generalisation of Langton’s ant. The threshold for non-trivial examples to appear is 1 state and 2 colours; Langton’s ant lies on this boundary, as does a modification emulating binary counting.

The latest discoveries in this area include multicoloured ants that emulate Langton’s ant, but taking increasingly long amounts of time to do so. This is no longer a mystery, and can be explained by the reversibility of the original Langton’s ant. The proof of the Cohen-Kung theorem extends to show that these generalisations also settle into building a periodic highway.

For 1-state 3-colour, the 3-colour Langton Ant is beaten by a turmite that also emulates Langton’s ant, but in a very different way. Specifically, it alternates direction between forwards and backwards, and takes 18.5 million generations (as opposed to 2.67 million) before settling into a cycle of gradually increasing length. Its asymptotic growth rate is , where t is the elapsed time.

Both of these are beaten by a completely different 1-state 3-colour turmite, which takes 67 million generations to settle into a periodic highway. Here you can see the mess left behind by the turmite before escaping to the left:

There are 9 unresolved Turmites in this space, so it is possible that there are even longer periods of time before stabilisation occurs. These have all been explored for at least 10 billion generations, and show no signs of becoming predictable. One of these exhibits binary counting behaviour:

When the amphisbaenic binary counter reaches the mess to the right, it is expected to become unpredictable again. It is unknown whether, at any time, one of these binary counters is created in a position where it would expand forever. I conjecture that this turmite does eventually become predictable. Firstly, by the Law of Excluded Middle, precisely one of the following must necessarily apply:

1. The turmite is unbounded, and therefore the bounding rectangle must continually expand. This can only happen if the turmite touches the perimeter of the bounding rectangle infinitely often. Every time this occurs, there is a nonzero probability of producing a binary counter in such a position where it expands forever.
2. The turmite is bounded in a N by M box, in which case it can last for at most generations before entering a periodic cycle.

Of course, this is not guaranteed to happen, since the turmite could continually evade placing binary counters at the perimeter (similar to tossing an infinite sequence of heads on a fair coin). Alternatively, it may ultimately enter some other type of non-chaotic behaviour, such as constructing a highway (in which case it is still predictable, and therefore still satisfies my conjecture).

For 2 states and 2 colours (the subject of Ed Pegg’s turmite challenge), I mentioned how Worm Trails had been beaten twice, with the current champion lasting 240 million steps. This record has been smashed another two times. Firstly, Gochev provided one with a lifespan of 7.735 billion steps, which finishes by constructing an expanding triangular wedge:

Georgi then broke his own record rather spectacularly, giving an example with a lifespan of 3.511 trillion generations. This one eventually produces an infinite highway:

Amonst the unresolved 2-state 2-colour turmites, a few produce interesting patterns:

This one produces ephemeral orthogonal and diagonal highways in its interior:

Consider the Gaussian function . This gives the standard normal distribution, which has zero mean, unit variance, and points of inflection located at ±1. Note the scaling term , which is included so that the integral is 1 (necessary for a probability distribution). Specifically, we have:

This is not so surprising, and can readily be derived from considering a two-dimensional Gaussian distribution. Much more unusual is that this related function also has an integral of √(2π) (although suitable changes of variables should relate these integrals).

This function is much more bizarre than the normal distribution. Firstly, it is completely flat (i.e. all derivatives are zero) at its peak:

Intriguingly, it is only completely flat at a single point (unlike, say, a horizontal line segment, which is completely flat on an interval). It is quite strange for an infinitely-differentiable function to have this property, and completely impossible over the complex numbers. If we look at what happens near zero, you’ll notice some stunningly pathological behaviour:

Anyway, I digress. What I actually wanted to talk about was the ubiquity of √(2π). It also occurs in the definitions of the continuous Fourier transform and its inverse:

You may have heard the amusing arguments debating whether it’s better to use π or τ = 2π as a fundamental constant. We have had a Tau Manifesto, which was soon met with criticism in the form of the Pi Manifesto. I propose a third competing faction, namely Radical Tauism (it’s funny because ‘radical’ can mean ‘(square-)root’ as well as ‘extremism’ ;P), which insists that √(2π) is better than the other two alternatives. In order to win, I suppose I’ll systematically deconstruct the arguments of the opposition parties.

Shown above is an image from the Pi Manifesto. It shows a unit circle, which has equal area to a square whose diagonal length is … erm … √(2π). Oh, yes, I forgot to mention yet another occurrence of √(2π), namely Stirling’s asymptotic formula for the factorial function.

The main benefit, however, is that both pi and tau can be expressed as polynomials in √(2π), whereas the converse is false. Square roots are ugly (being multi-valued when extended to the complex plane), so it’s cleaner and more elegant to eliminate them completely by inventing a new symbol for √(2π). The question is, which symbol? We want something relatively simple, which excludes (for example) the Chinese ‘biang’ character:

I look forward to seeing your comments and criticisms.

Some of you may have noticed a particularly queer post on cp4space yesterday (since deleted), which was written by an impostor. Specifically, I was hosting several people (including, but by no means limited to, the daughter of Kjartan Poskitt). I happened to leave the room to acquire a bottle of Sandringham apple juice; in the interim, someone accessed my computer and left an entertaining message on cp4space. I apologise for any inconvenience or confusion caused by this complete and utter travesty.

Quite a while ago, I mentioned the hyperboloid of one sheet as an example of a doubly-ruled surface, where every point is determined by two straight lines contained by the surfaces. These are very rare. Much more common are singly-ruled surfaces, such as the cone, where we have a single straight line passing through each point on the surface in general position.

Non-singular cubics are very interesting beasts. In two dimensions, these are elliptic curves, which have a beautiful Abelian group structure with major applications in cryptography and number theory. If we add another dimension, then we obtain a cubic surface, such as this one:

It transpires that on a non-singular cubic surface, there lie a total of 27 straight lines (when considered in complex projective 3-space). They are all realised as real lines in the Clebsch cubic, described by the equations and . The first of these determines a three-dimensional subspace of projective 4-space; the second gives a cubic surface inhabiting that space. The cubic surface shown above is a visualisation of the Clebsch cubic in .

A particular Wolfram demonstration allows you to experiment with up to 24 lines on a cubic surface (the remaining three are at infinity). For certain values of the parameter, fewer lines are visible due to either singularities or the existence of non-real lines.