Complex Projective 4-Space

Suppose we have a particularly ravenous cat (Felis sylvestris) chasing some particularly tasty mice (Mus musculus, if I remember correctly) across the vast expanse of the real Eculidean plane R². The most interesting case is when mice and cats move at the same maximum speed, so we’ll assume this henceforth. In particular, we’ll discretise time to simplify the analysis.

The most fun way to consider this is to embed it in a game.

• Given two positive integers c and m, the ‘mouse owner’ decides some initial configuration of c cats and m mice on the Euclidean plane.
• The mouse owner and cat owner alternate taking turns to choose one of their respective animals and move it anywhere within the closed disc of radius 1 centred on its current position.
• If a cat lands on top of a mouse, the cat owner wins. If there is no time for which this occurs, it is considered to be a win for the mouse owner.

So, for what values of c and m do the mice have a winning strategy? During one Anglo-Hungarian camp, a bunch* of us demonstrated that mice can force a win whenever c = 1, irrespective of the value of m. You may want to prove it yourself. Geoff Smith extended this to the c = 2 case.

*Being a mathematician, I’m only allowed to use ‘group’ to refer to an associative algebraic structure endowed with inverses and an identity.

The case for m = 2 is also a win for the mice irrespective of the value of c:

If the abscissa (horizontal coordinate) of a cat moves to the left, then the left mouse moves left. Otherwise, the right mouse moves right. This leads to a winning strategy for the mice.

On the hyperbolic plane, this generalises to a winning strategy for the mice for all ordered pairs (m,c). For the Euclidean plane, however, it is much harder.

If we allow more types of animals, this can be made into a fair, playable game. For instance, you could have a three-player game involving animals isomorphic to ‘rock, paper, scissors’, trapped inside a bounded arena.

Lion and man of indeterminate religion

A variant of this problem is where time is continuous, but the speed is bounded below 1. It was originally phrased with a lion chasing a man (whose religion, due to reasons of political correctness, is left unspecified in academic papers) around a circular amphitheatre. It turns out that the man has a winning strategy (hint: the sum of the reciprocals of the squares converges to π²/6, but the sum of the reciprocals of the integers diverges).

With different spaces and distance metrics, things become more interesting. For example, consider R³ with the norm d² = max(x²+y²,z²), where a ball (set of points within a given radius of a point) is a cylinder. The arena itself is a ball/cylinder, by analogy with the original problem. Bela Bollobas, Imre Leader and Mark Walters contemplated this, and showed that paradoxically both the lion and man have a winning strategy.

A completely unrelated note

I donated blood today, with Tom Rychlik doing likewise for the sole purpose of preventing me from assuming the moral high ground. I told him that 11 minutes was the time to beat, and he wagered five Yorkies against a mention on cp4space that he could manage it in less time. Remarkably, rather like the counter-intuitive lion versus man problem, both competitors ‘won’ in some sense: Rychlik took a mere 7 minutes, but passed out and had to stop after an incomplete donation of 420ml. Consequently, you’re reading this whilst I get to indulge in some chocolate!

Continuing the tenuous links with cats and wagers, I just this moment received a ransom note from Ben Elliott:

“I have your cat. Unless you compute Ramsey(6,6) by 0000 UTC tomorrow, it will be placed in a box. After this point it will be both alive and dead.”

Considering that I am neither Erwin Schrödinger nor in possession of a cat, I’m intrigued to see what will happen. I imagine that he’s referring to the number of vertices n required for there to be guaranteed a monochromatic K6 subgraph within any colouring of the complete graph Kn with two colours. Upper bounds are established and proved in the third chapter of MODA, but they’re far from optimal.

A few weeks ago, arguably the greatest fan of cp4space invited me to his birthday party at the Eagle. As I mentioned in my speech, this was where Watson and Crick unveiled their proposed double-helix structure of DNA.

Interestingly, the basic idea of encoding a tape of instructions sufficient for a machine to replicate itself actually pre-dated Watson and Crick’s discovery. John von Neumann designed a mathematical model where a machine reads a tape of instructions to manipulate a ‘construction arm’, which then draws another copy of the original machine.

The first implementations were very inefficient, with tapes of over 100000 bits long. After many successive alterations, William R. Buckley and I were able to massively optimise the machine and reduce its genome length eventually down to a mere 8920 ternary digits; the start of the tape is shown on the right of the image above. The parent constructor (left) literally draws an identical copy of itself and copies its instructions.

This is a very abstract model of self-replication, but it demonstrates the complexities involved. Tim Hutton sought to make more realistic models, which better represent the processes occurring in biological life. The end result was something akin to a two-dimensional bacterium:

Its genome is divided into several genes, each of which contains a base sequence describing an enzyme to produce. These enzymes regulate the chemical reactions required for the cell to replicate itself, such as copying its DNA, invaginating and splitting into two copies of the original cell. Unfortunately, the rate of reactions is very slow, so Tim estimates a replication time of two years when running on a modern CPU.

Tim made this idea (artificial chemistry) into a public challenge, a series of puzzles ranging from propagating a signal along a wire to causing an entire cell to self-replicate. Together, we managed to implement Turing machines in this environment, proving that it is possible for these artificial life-forms to potentially be able to make decisions. One of our experiments involved a Turing machine copying a binary sequence (e.g. 100110 –> 100110100110) and splitting it down the middle to emulate binary fission. After a while, there are many copies of this information floating around:

These initially replicate exponentially, but soon the amount of space limits the growth to quadratic (even on an infinite Euclidean plane). In three dimensions, there is more space so we can reach cubic growth. Remarkably, on a hyperbolic surface, there is enough space for true exponential growth to actually be achieved.

Speaking of hyperbolic planes, I’ve dusted off my hyperbolic tiling generator to create the Diwali-themed banner for cp4space. It was suggested that I make an app for producing tilings of miscellaneous spaces with arbitrary images of your choice. Can I gauge the approximate level of interest in such a program before I attempt to give it a decent user interface?

Hunter Spink gave me an interesting problem about a beach ball inscribed in a wire tetrahedron, since its most elegant solution uses techniques explored in the tenth chapter of Mathematical Olympiad Dark Arts. Rather than give you the problem now, I’ll keep you waiting eagerly in suspenseful anticipation until MODA is finalised and publicised.

Wireframe polyhedra can do much more than merely circumscribe beach balls. Oh, yes, you can even immerse them in soapy water. When removed, the soap-bubble surface attempts to minimise its energy, and therefore its area. Because it’s easier to think in lower dimensions, consider this analogous problem:

There are plans to build a hyperspace expressway between Earth and three distant locations (assumed to be the vertices of a square of side length 1000 light-years). What is the minimum length of path possible?

Earth and three distant places, positioned at the vertices of a square.

The greedy algorithm is to simply make three edges of the square, with a total length of 3000 light-years. This is sub-optimal, as the two diagonals have a total length of 2828 light-years. Surely that’s optimal?

Actually, no. The most efficient solution (2732 light-years) involves straight line segments meeting at angles of 2π/3, as demonstrated below. You may recognise this as being intimately related to the Fermat-Torricelli point (or first isogonic centre if you’re feeling particularly poncey!) in a triangle, which minimises the sum of distances to each of the three vertices.

In the three-dimensional generalisation, we get four bubble surfaces meeting at a vertex with locally tetrahedral symmetry. I really suggest trying it with an actual wireframe polyhedron in some actual soapy water. Come on, it’ll be fun!

Essentially, soap bubbles obey partial differential equations dictating their curvature. The simplest solution is a spherical bubble, which minimises the area enclosing a given volume. A much more interesting minimal surface (I forget what it’s called — I think it’s the Schwarz P-surface, where P might actually be a different letter) is shown below:

Actually, I’ve cheated and just plotted sin(x) + sin(y) + sin(z) = 0, which is a very close but inexact approximation to the surface.

Conclusion

I can’t think of a way to conclude this post, other than by blowing your mind with the following pearl of wisdom imparted unto me by Richard Freeland last night:

• TRIANGLE is an anagram of INTEGRAL

He also gave four other (less mathematical) anagrams composed of the same eight letters. Can you find them all?

Alexander Betts (nee Luke) posed an interesting problem in combinatorial geometry for the Romanian Masters of Mathematics 2011:

We have a finite set S of n points in the plane, {A1, A2, …, An}, such that (for all i and j) the distances from Ai to all the other points are a permutation of the distances from Aj to all the other points. What possible configurations can S be?

I’ve left it as exercise 17 in chapter 10 of MODA (entitled ‘Areal coordinates’). You may want to think about it before reading on.

The obvious solutions are the vertex sets of regular polygons (which work by symmetry). Upon further consideration, a truncated regular polygon with alternating long and short sides will also work by symmetry. Individual points, lines and rectangles can be regarded as degenerate cases of these.

It turns out that these are the only possible configurations which satisfy the problem. The proof of this involves considering the sum of squares of distances from a particular point to each other point. This is independent of the vertex chosen, by the permutation property. From this and a beautiful result known as the Huygens-Steiner theorem*, we can deduce that the points are equidistant from their centroid, so all lie on a circle. A basic induction then narrows it down to the two types of configuration displayed above.

* If you don’t know it, you can prove it using either Cartesian coordinates (as I did in the competition) or physics (as Jordan did). Thankfully, the rum chocolate bars were just alcoholic enough for us to succeed with these bizarre methods!

Three-dimensional generalisation

The next natural generalisation is into three dimensions. We retain the planar solutions (polygon and truncated polygon) and obtain some more solutions (prisms, antiprisms and twisted prisms) by extending them. Twisted prisms include disphenoid tetrahedra as a special case.

As well as these boring infinite families of solutions, there are some more interesting exceptional cases. The Platonic solids work by symmetry, as do any vertex-transitive polyhedra. They include the Archimedean solids and some slightly deformed versions you can explore with my interactive demonstration:

The are also alternated versions of these, resembling snub dodecahedra, snub cubes and slightly irregular icosahedra (both chiral and achiral versions exist).

Careful consideration (involving plenty of group theory) shows that these are the only finite vertex-transitive arrangements of vertices in three-dimensional space. However, there may be other solutions to the three-dimensional Betts problem, where not all vertices are equivalent but the distances to the others are always permutations. I strongly doubt that they exist. Can you prove that the vertices (which necessarily lie on the surface of a sphere) can only take the aforementioned arrangements, or can you find any counter-examples?

It’s Guy Fawkes Night now and I’ve had to update the seasonal banner yet again. There are a few late items of news I would like to mention:

Firstly, thanks go to everyone who has sent me feedback regarding MODA; I have been making amendments and intend to publish the final version in a few weeks’ time. As such, the Acknowledgements section is gradually inflating.

Secondly, the UK MOG champion and ice skater Maria Holdcroft has successfully solved the chess cipher. She can now add cryptanalysis to her growing list of accomplishments.

Finally, I leave you with this group theory problem I devised and later solved:

Suppose F is a subgroup of G, which is in turn a subgroup of H. If F is isomorphic to H, must G be necessarily isomorphic to F and H?

Clearly, the ‘Subgroup Sandwich’ statement is trivially true for finite groups. Does it remain true for infinite groups?

The P versus NP conjecture essentially asks whether any problem whose solution can be easily verified can also be easily solved. Here, ‘easily’ technically means ‘computed in polynomial time on a Turing machine’.

If you think for a moment, it is difficult to imagine that P (easily solvable) does equal NP (easily checkable). For instance, if I asked you to factorise 2^32 + 1 into prime factors, you might be stuck for a while. However, when I tell you that it’s 641 × 6700417, you can very quickly verify that it’s correct. So, prime factorisation lies in NP, but there is no known polynomial-time algorithm for doing it*. Indeed, it could well be a counter-example to the P = NP conjecture.

* Interestingly, we can actually determine whether a number is prime in polynomial time, but this gives no clues as to its factorisation.

If any NP problem is a counter-example, then so is every problem in a broad class known as NP-complete. Contrapositively, solving a NP-complete problem in polynomial time would prove that P = NP for all such problems. Quite a lot of practical problems are known to be NP-complete, which is why there is a large prize of $1000000 for a proof in either direction.

Travelling Salesman Problem

One such example of a NP-complete problem is the Travelling Salesman Problem. This asks for the shortest route on a network which visits every point once and returns to the original location. Surprisingly, the problem of determining whether such a route (a Hamiltonian circuit) even exists is also NP-complete, so precisely as difficult.

Amazingly, there’s actually a thriller exploring the repercussions of a proof that P = NP (although it almost certainly isn’t). It’s being screened for the first time in the UK at the CMS on 20th November.

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

Even if P = NP and a valid proof is produced, it is unlikely that it would cause all these complications. For instance, it could be that the proof is non-constructive, and therefore people will still have to search for an algorithm to solve one of these NP-complete problems. Additionally, such an algorithm may still have intractably long running time: a computer program taking O(n^100) time would not really be practical, even though it’s strictly polynomial.

Beyond NP-complete

There are actually harder problems than NP-complete, and a polynomial-time algorithm wouldn’t extend to those. For example, sliding block puzzles fall into the category of PSPACE-complete, which is strictly harder than P. A popular one of these puzzles is Conway’s Century, displayed below:

Slide the blocks in the puzzle above to flip the initial configuration.

It takes 150 moves to solve this variant, if I remember correctly. Robert Hearn and Erik Demaine demonstrated that sliding-block puzzles and some other types of puzzles can simulate logic gates and thus linear-bounded automata, proving the puzzles PSPACE-complete. PSPACE-complete is the hardest type of bounded one-player puzzle possible, and is achieved even by general sliding-block puzzles composed entirely of dominos.

If we allow two-player games such as chess puzzles on arbitrarily large initial configurations (without the stupid 50-move rule, which would ruin this if included), an even harder complexity class is achieved: EXPTIME-complete. These take exponential time to solve, so there is no hope of an efficient algorithm. As such, computer programs fail miserably at playing similar games (such as Go) on large boards.

Take your favourite PSPACE-complete puzzle and extend it to an infinite board (say, an arbitrary finite configuration on an arbitrary repeating background). This is then in general undecidable, so no algorithm has any hope of solving it, not even when allowed to run ad infinitum. There’s even an algorithmic way to build an infinite sliding block puzzle which can be solved if and only if the Riemann hypothesis is false.

Feeling that Complex Projective 4-Space isn’t sufficiently seasonal, I was compelled to alter the colour scheme of the banner to reflect the fact that today, the 31st October, is All Hallows’ Eve, popularly abbreviated to Hallowe’en. Anyway, I actually prefer the new banner, so it may stay that way until the next festive holiday. Not that it’s particularly distant: we have Bonfire Night rather soon, followed shortly after by Diwali.

Adhering to the Hallowe’en theme, the cubic curve shown above is known as the Witch of Agnesi. Given that it looks nothing like a witch, why is the curve so named? Its namesake, Maria Agnesi, was certainly not a witch herself, nor even suspected of being one. It transpires that it was lost in translation — the Italian word ‘averisera’ (versine curve) greatly resembles ‘avversiera’ (witch), so the Lucasian Professor of Mathematics misinterpreted the name. This is not the only occurrence of this, either. The much more familiar Klein bottle (Flasche in German) was originally called the Klein surface (Flache). This has, in turn, led to people drawing embeddings of the surface resembling bottles:

Notice how I have managed to provide some tenuous links from Hallowe‘en to topological surfaces. This is also riddled with rather interesting parlance, such as a pair of pants (not to be confused with number theory trousers, which I’ll explain later). This refers to a very basic topological object from which many other surfaces can be derived, such as a two-holed torus (by stitching together two pants in the obvious way). I don’t think you can get a lower genus than that, though, so your attempts to make a Klein bottle out of pants will probably fail. I’d love to be proven wrong, though.

By the way, the link to the text-only chess cipher is now broken again, since pentadecathlon.com has given up the ghost.

Quite a lot of interest originated from the following puzzle of unknown origin:

Given two pieces of rope which burn in precisely 1 minute, time an interval of 45 seconds (3/4 minutes). The rope is not necessarily uniform, so you’re not allowed to measure 3/4 of the way along it.

The solution is to light three of the four ends of rope. When one rope burns completely (at t = 1/2), light the fourth end. This will take another 1/4 minute to burn.

If we allow infinitely many pieces of rope, what intervals of time can be measured? Trivially, we can measure time 0.  If we can measure time x, then we can also measure time x+1 by lighting a fuse at the end of it. Also, given two times x and y within 1 minute of each other, we can measure time (x+y+1)/2, by lighting one end of a rope at time x and the other at time y. We abbreviate this to x ~ y, where the swung dash is pronounced ‘fuse’.

The set of fusible numbers has some nice properties. For instance, it’s closed under addition (pretty trivial to prove) and well-ordered (not so easy). The latter property is more interesting, since it means there is an order-preserving map from the fusible numbers to a bunch of ordinals.

Let’s consider fusible numbers below 1. We can time 1/2 and 3/4, as in the original puzzle. Continuing this process, all numbers of the form 1 – 2^-n can be measured:

1/2, 3/4, 7/8, 15/16, …, 1.

In this instance, 1 behaves like the ordinal ω, being a limit point. We then proceed to get more limit points, such as 5/4 (2ω) and 11/8 (3ω). These all converge to a ‘double limit point’, 3/2, which we can associate with ω^2. Continuing in this manner, we get 3/2 (ω^3), 7/4 (ω^4) and so on until we reach 2 (ω^ω).

Adding 1 to a fusible number x is equivalent to raising ω to the ordinal representation of x. This means that the integer n is equivalent to the ordinal ω^ω^ω^ … ^ω (with n omegas), and we get all ordinals below epsilon-nought in this manner.

Due to well-ordering, we can ask ‘what is the smallest fusible number greater than n?’ As mentioned in this paper, we get:

• The smallest fusible number above 0 is 1/2;
• The smallest fusible number above 1 is 9/8;
• The smallest fusible number above 2 is 2 + 1/1024;
• The smallest fusible number above 3 is 3 + 2^-1541023937.

If you’ve seen fast-growing functions in combinatorics before, this should come as no surprise.