Ménage primes

The Online Encyclopedia of Integer Sequences has recently celebrated its fiftieth anniversary, amassed over 250 000 sequences of varying importance, and heralded the 75th birthday of its creator Neil Sloane. It is somewhat surprising, therefore, that no-one appears to have investigated the intersection of two particularly natural integer sequences (catalogued as A000040 and A000179 in the OEIS).

In this article, I shall attempt to persuade you that investigating this new sequence of ménage primes is a good idea for several reasons. But until then, let us consider the problems that motivated this line of research.

Vortices and knots

Before the structure of the atom was properly understood, Lord Kelvin conjectured that atoms were vortex rings in a hypothetical ubiquitous fluid known as the luminiferous aether. The shape of the vortex ring writhes and undulates, but up to homotopy it remains constant throughout its lifetime. Begun was the idea that chemical elements correspond to homotopy classes of embeddings of the circle (more commonly known as knots), and classifying them would yield a mathematical explanation for the origin of the periodic table*.

* In reality, the periodic table stems from solving the Schrödinger equation for the potential effected by a point charge (the nucleus).

Realising that knots exhibit ‘unique prime factorisation’, Tait et al began enumerating the prime knots according to the minimal number of crossings when the knot is drawn as a diagram in the plane:

knot-table

Shown above are all distinct prime knots with eight or fewer crossings. With the exception of the last three, these are all alternating knots, meaning that the string passes alternately over and under the crossings.

A knot diagram can be considered to be a 4-regular plane graph, where each vertex is decorated to specify which path goes over and which goes under. We can add further structure by 2-colouring the regions and assigning a direction to the knot. For example, the second knot in the third row yields this diagram:

directed-colouring

 

Each edge can be labelled from 1 to 2n, where n is the number of crossings, according to the order in which they are traversed. We define the parity of an edge to be whether the blue region is to the left or the right of the arrow on the edge. Observe that the parity alternates between successive edges in the traversal, so this corresponds exactly to the parity of the label.

At each vertex, an odd edge and an even edge converge. This yields a bijection between the odd and even edges of the diagram. Moreover, note that in a reduced diagram (with no trivial redundant crossings), consecutive edges never point to the same vertex.

Now draw a complete bipartite graph K(n, n), where each vertex corresponds to an edge in the diagram. We have a natural matching (the bijection between the odd and even edges of the graph described above) and a natural Hamiltonian cycle (the order of traversal). These share no edges. There are two dual ways to view this as a graph-theoretic problem:

  • Counting Hamiltonian cycles of a complete bipartite graph with a perfect matching removed.
  • Counting perfect matchings of a complete bipartite graph with a Hamiltonian cycle removed.

This problem was later rediscovered by Edouard Lucas in an entirely different setting.

Formal combinatorics

At High Table, n Fellows and n guests (one for each Fellow) are seated around the perimeter of a topological disc. To maximise social interaction, the following rules are observed:

  • No two Fellows may be seated adjacent to each other.
  • No Fellow may be seated adjacent to his or her guest.

In how many ways is this possible? This is known as the ménage problem, due to an outmoded heteronormative statement of the problem involving married couples instead of ordered pairs of the form (Fellow, guest). One such arrangement for n = 7 is illustrated below and obtained from the knot diagram:

knot-and-formal

The crimson lines biject each Fellow (odd number) with his or her guest (even number); these correspond to edges converging to the same vertex in the knot diagram.

We can eliminate much redundancy in our enumeration by exploiting the vast amount of symmetry in the situation:

  • Any permutation of the n ordered pairs yields another valid arrangement (order n!).
  • Interchanging each Fellow simultaneously with his or her guest results in another valid arrangement (order 2).

Removing the symmetry is equivalent to imposing that the Fellows are initially seated in a particular arrangement. Hence, our question reduces to:

Given an initial arrangement of n Fellows occupying alternate seats, in how many ways can we seat their guests in the remaining n seats such that no Fellow is adjacent to his or her guest?

The number M(n) is called the nth ménage number. The first few ménage numbers are:

  • M(3) = 1 (the unique arrangement involving the Fellows being diametrically opposite their respective guests)
  • M(4) = 2 (two chiral solutions)
  • M(5) = 13
  • M(6) = 80
  • M(7) = 579

An explicit formula is given in the OEIS (sequence A000179).

Which ménage numbers are prime?

Observe that M(4) and M(5) are both prime, which confirms that we have successfully factored out all of the redundant symmetries. Continuing further, one discovers that the next ménage prime is M(13) = 775596313, followed a while afterwards by M(53) = 567525075138663383127158192994765939404930668817780601409606090331861.

I decided to do an overnight Mathematica run for values of n up to circa 10000. In the process, it found a spectacular 30281-digit ménage prime, M(8645). To put this into perspective, this is larger than any prime known before the discovery of 2^132049 − 1 in 1983. This suggests the following questions:

  • Are there infinitely many ménage primes?
  • If so, what is their asymptotic growth rate?

The first of these is extremely difficult, and the second is at least as hard (although we provide some heuristics in the next section). A more achievable goal is the following:

Find another ménage prime beyond the five already discovered.

If my heuristics are correct, the expected number of ménage primes between M(10^4) and M(10^5) is around 0.25, which is both low enough for me to be willing to offer the following prize and high enough that I’m slightly worried someone may win it.

Specifically, the first person to discover a new ménage prime can choose either of the following prizes:

  • A vibrant pink wig (RRP 11.00) so you can self-identify as Minaj Prime (pun definitely intended!).
  • Alternatively, the publication of a video of me performing a Minaj song of your choice whilst wearing the aforementioned vibrant pink wig:

minaj-prime

Heuristics

Although the ménage numbers are not exactly equidistributed modulo p for all p (for example, only 2/9 of them are divisible by 3), they do seem to asymptotically be prime as often as one would expect from a randomly-chosen number of a similar size. That is to say, M(n) appears to be prime with probability 1/log(M(n)).

Now we need an asymptotic formula for the ménage numbers. Since M(n) counts the number of permutations such that both σ(i) and σ(i) + 1 are derangements, we expect there to be roughly n!/e² arrangements. It can be shown that this estimate is asymptotically correct (the ratio tends to 1 as n tends to infinity), which by Stirling’s formula is in turn asymptotically equal to:

\sqrt{2 \pi n} n^n e^{-(n+2)}

The sum of the reciprocals of the logarithms of these numbers diverges, which (by Borel-Cantelli) suggests that there are infinitely many ménage primes. However, it diverges sufficiently slowly that we only expect around log(log(m)) such primes for n < m. This means that in the long run, the number of ménage primes below a given value N is expected to be around log(log(invgamma(N))), where invgamma is the inverse Gamma function.

With these heuristic estimates, the expected number of ménage primes M(n) with n between 10^4 and 10^5 is roughly 0.25. It is entirely plausible that people may attempt to search further than 10^5; increasing this upper bound to 1.5 × 10^7 (corresponding to primes of over 100 million digits, therefore eligible for the 150 000 dollar prize offered by the Electronic Frontier Foundation) gives an expected value closer to 0.64.

Anyway, good night for now — I have a couple of sequences to add to the OEIS (due to appear as A249510 and A249394).

Posted in Uncategorized | Leave a comment

Random circular mazes

In 1995, William Jockush, Peter Shor and James Propp published the statement and proof of the celebrated Arctic Circle Theorem. This roughly states that if you choose a random domino tiling of an Aztec diamond (a particular family of polyominoes), the resulting pattern is homogeneous outside a central chaotic disc-shaped region:

arctic-circle

In the diagram above, the colours indicate the orientation and parity of the dominoes. We can now state the theorem more precisely:

  • Let ε > 0 and p < 1. Then we can find n such that with probability at least p, the boundary of the disordered region in the centre of a randomly-chosen domino tiling of the order-n Aztec diamond will be contained in the annulus bounded between the concentric discs of radii (1 ± ε)r, where r is the radius of the circle inscribed in the diamond.

Firstly, it is by no means obvious how many domino tilings exist (although one could theoretically bash it with the permanent-determinant method), nor how to efficiently choose a tiling randomly such that all tilings occur with equal probability. The authors of the paper settle both of these issues simultaneously with the shuffling method illustrated below:

iteration

Each domino is given a heading (one of the four cardinal directions) according to the following rules:

  • Place a dot in the centre of the uppermost edge of the Aztec diamond.
  • Place dots on any other lattice points of the same parity as the original dot.

Then each domino has a dot in the centre of precisely one of its four edges; this determines the heading of the domino. We have used red, green, yellow and blue to represent north, east, south and west, respectively. Each iteration of the shuffling method comprises three stages:

  • Destruction: If a pair of dominoes face each other, they annihilate.
  • Sliding: All dominoes move one step according to their headings.
  • Creation: Empty cells form the disjoint union of 2-by-2 blocks. Insert two dominoes into each of these blocks in one of two ways (chosen randomly by the result of an unbiased coin toss).

This converts an order-n Aztec diamond tiling into an order-(n + 1) Aztec diamond tiling. Iterating from the base case of a 2-by-2 block, we can obtain any Aztec diamond tiling in this manner. The following animation shows the expansion of a tiling by iterated application of the shuffling method:

shuffling

This is quite remarkable, as it is surprising that the result of a stochastic process on a square lattice would give rise to a perfect circle. In particular, cellular automata very rarely exhibit this feature (certain lattice gases possess this desired isotropy, but most do not), and tend to have either square or octagonal envelopes of propagation.

In the comments of the post about the permanent-determinant method, Sam Cappleman-Lynes and I discussed a bijection between domino tilings and spanning trees of the grid graph. Applying the bijection to the result of the shuffling method yields randomly-generated circular mazes which are (given appropriate boundary conditions) simply-connected:

random-maze

I’m interested in seeing the shortest path from the centre to the boundary, to roughly assess the difficulty of the maze. Now, the obvious thing to try is to run it in the old MazeSolver rule I wrote for Golly, which finds that the maze is rather poorly connected. In particular, routes tend to be pretty direct and very diagonal:

maze-solver

However, this problem only arises due to the fact that we haven’t applied any boundary conditions to the circumference of the chaotic disc. Doing this properly yields a more respectable labyrinth.

Posted in Uncategorized | Leave a comment

Cipher 71: Monoalphabetic II

As promised, the fourth season of cp4space ciphers has now commenced. Here’s a monoalphabetic substitution cipher with a nine-letter plaintext containing a man’s name. The password for the solvers’ area is the person who killed that man, entirely in lowercase:

F B' U2 R2 L2 U D'

Enjoy.

Posted in Ciphers | Leave a comment

Tweetable architecture

Quite probably the most world-renowned architect of the 21st century, Zaha Hadid, has been recently commissioned to design a new fluid dynamics exhibition in the London Science Museum. It will certainly add much more depth than its current collection of stellated polyhedra, which was the only particularly mathematical exhibit I recall from the last time I visited (8th April).

You’ll certainly want to view Alex Bellos’s gallery of the exhibition, and then read his Guardian article announcing it.

Zaha Hadid’s architecture is based upon a contemporary style known as parametricism, which rejects the ideas of straight edges and rigid forms, favouring more natural forms such as the minimal surfaces imitated by soap films and encapsulated in the forthcoming exhibition.

My personal favourite of her masterpieces, entitled Galaxy Soho and depicted above, always reminds me of the internal structure of a chloroplast, with columns of thylakoids joined by integranal lamellae.

Image courtesy of Kelvin Song.

Anyway, one of the features of parametricism is the use of mathematical formulae to design buildings. This is actually an extraordinarily good idea for at least three reasons. Firstly, from a merely engineering standpoint, optimal structures are usually described by simple equations, such as the catenary (optimal self-supporting arch). Secondly, from an aesthetic perspective, simple equations typically yield pleasing, sensual forms. Thirdly, using simple equations eliminates the need for pages upon pages of excruciatingly detailed instructions.

In fact, how simple can we get? The epitome of our modern requirement for brevity is Twitter, which limits individual posts to 140 characters in length. Would it be conceivably possible to tweet an architectural design?

Wolfram has recently released its Tweet A Program initiative, whereby one can instruct it via Twitter to execute arbitrary Mathematica programs of at most 128 characters (since “@wolframtap ” occupies the other twelve characters) in the cloud, tweeting the result back to you.

So I decided to tweet a 126-character program to plot a pair of twin towers on the chloroplast theme. And it came back with this:

tweetable-architecture

It resembles a couple of caterpillars waltzing in lime-flavoured jelly. I’m sure you can do much better; just write a Mathematica program of at most 128 characters, tweet it to @wolframtap, and retweet your parametric architecture back to me at @apgox.

Posted in Activities | 3 Comments

Tributes to cryptanalysts

Earlier on cp4space, I mentioned how there were a couple of planned tributes to Alan Turing and Bill Tutte. Subsequently, both of these projects have since been completed.

Firstly, the premiere of A Man From The Future was performed by the Pet Shop Boys at the BBC Proms. An excerpt, entitled He Dreamed Of Machines, is available on YouTube:

This single is due to appear in the forthcoming biographical film, The Imitation Game.

Similarly, the Bill Tutte memorial has now been unveiled. The main sculpture is an arrangement of panels inspired by punched card, which display an image of Tutte when viewed from the correct perspective:

This is part of a larger initiative designed to increase awareness of W. T. Tutte through various events and a local scholarship.

Posted in Uncategorized | Leave a comment

Hyperbolic Minecraft

(Firstly, this is a test to see whether WordPress is configured to automatically link to cp4space posts as tweets from apgox. Hopefully it will succeed.)

Yesterday, I received a rather interesting e-mail from Tim Hutton, lead developer of the reaction-diffusion software Ready. It was concerned with a (possibly facetious) post by Mike Stay concerned with the possibility of implementing a disproportionately popular video game in hyperbolic space. I haven’t personally encountered the aforementioned game, although one of my colleagues mentioned at a barbecue that his children were obsessed with it.

To summarise, we needed a way to construct the {4, 3, 5} honeycomb of hyperbolic space (the dual of the order-3 tiling by dodecahedra) to use as an underlying grid for Ready. Fortunately, I realised that the intersection of the honeycomb with the xy-plane is merely the bog-standard order-5 square tiling, which meant that I could reduce it to an easy two-dimensional problem. With some slight help from Mathematica’s FullSimplify routine, I prepared the following recipe:

  • Define t = (1 – sqrt(7 – 3 sqrt(5)))/3.
  • Let the `central cube’ have vertices (±t, ±t, ±t).
  • We define six `mirrors’ to be the spheres with radius sqrt(3 – sqrt(5)) and centred on one of the following six vertices: (1, 0, 0), (0, 1, 0), (0, 0, 1), (-1, 0, 0), (0, -1, 0), (0, 0, -1)
  • Sanity check: the central cube is the volume containing the origin and enclosed by the six mirrors.
  • Produce images of the central cube by `reflecting’ in the mirrors to your heart’s content. By `reflecting’, I mean this: http://en.wikipedia.org/wiki/Inversive_geometry#Circle_inversion
  • So, to reflect p about the mirror with centre q, you apply the transformation p –> q + (p – q)*(R^2/|p – q|^2) where R^2 = 3 – sqrt(5) is the squared radius of the mirrored sphere, and p and q are vectors in $\mathbb{R}^3$.
  • The result should be the {4, 3, 5} tiling of a Poincare ball of some radius I can’t be bothered to calculate.

Miraculously, this ad hoc sequence of instructions actually worked, and Tim was able to construct the first couple of shells of the hyperbolic tiling. For instance, here is the tessellation after the second shell has been added:

435_iteration2

So far, so good. However, there is the issue of avoiding duplicated blocks, which I addressed with the following (incredibly lazy) suggestion:

I would avoid duplicates by rejecting any new cubes whose centres coincide with existing cubes (by using a hashmap or something similar).

Often many problems in life reduce to the dichotomy of whether to `do maths’ or `use a hashmap’. I’ve decided to resort to the latter, by virtue of working for several weeks for a software engineering company. More diligent people actually design an elegant method of coordinatising hyperbolic space; one such mathematician is Maurice Margenstern, who wrote a paper addressing the two-dimensional analogue of this problem.

Anyway, Tim Hutton was satisfied with the hashmap solution, and this algorithm has since been incorporated into the Ready code (c.f. relevant section of the Subversion repository). As a preliminary trial, here is a Ready screenshot of an experiment with the Gray-Stott reaction-diffusion system running on the {4, 3, 5} tiling of hyperbolic space:

gray_scott_on_435_level6

 

Anyway, Tim decided to contribute an OEIS sequence containing the numbers of cubes within a distance of at most n from the central cube. Slightly more naturally, this sequence can be regarded as the partial sums of this sequence (which counts the number of cubes in each layer):

1, 6, 30, 126, 498, 1982, 7854, 31008, 120666, ...

Similar sequences have been created for two-dimensional tilings. Indeed, the order-3 heptagonal tiling has the remarkable property that the number of tiles in each layer is seven times a Fibonacci number:

Specifically, if we divide the number of tiles in each layer by seven, we obtain the sequence (1, 3, 8, 21, …), which are alternate Fibonacci numbers. Similarly, a three-dimensional honeycomb is dictated by a third-order linear recurrence relation; unlike its dual tiling, this happened to be in the OEIS.

Posted in Uncategorized | 3 Comments

First female Fields medallist

Tomorrow, this year’s Fields medals were awarded*. The four recipients of this prestigious quadrennial accolade have made profound advancements in their respective areas of mathematics, specifically:

  • Artur Avila has revolutionised the study of dynamical systems, proving many hitherto open conjectures in the field. This is exciting from both a pure perspective, augmenting our understanding of the ergodic theory of various systems; and from an applied point of view, giving a deeper insight into the behaviour of chaotic systems such as phase transitions.
  • Manjul Bhargava‘s research massively generalises Gauss’s composition law, as well as enabling one to enumerate rings of finite rank with a particular discriminant. This has subtle connections to the theory of algebraic curves, including new bounds on the average rank of elliptic curves.
  • Martin Hairer made extremely notable discoveries about stochastic partial differential equations, which generalise PDEs by including the effects of random noise. In doing so, he has provided solutions to many new families of SPDEs, several of which have physical interpretations.
  • Finally, Maryam Mirzakhani has contributed immensely not only to the geometry of Riemann surfaces and their moduli spaces, but also their dynamics. Incidentally, she is the first female Fields medallist (whilst several great female mathematicians flourished in the twentieth century, including Emmy Noether, Julia Robinson and Ruth Lawrence, the award remained elusive until now), and the remainder of this article is dedicated to her outstandingly brilliant accomplishments.

*International Date Line.

Maryam Mirzakhani

Her work is concerned primarily with compact Riemann surfaces of a given genus. From a merely topological perspective, these are multi-holed tori. Riemann surfaces, however, are endowed with a complex structure and therefore a natural metric, which is much deeper and more interesting.

With the exception of the trivial cases of the sphere and torus, these compact Riemann surfaces are quotients of the hyperbolic plane (c.f. Uniformisation Theorem). These quotient spaces are really exciting, and admit an intuitive classification thanks to Thurston’s beautiful theory of orbifolds. Maryam’s early work established a formula for the number of simple closed geodesics on these Riemann surfaces, together with asymptotics for their lengths.

Her next advancements were related to the moduli spaces of Riemann surfaces.

Moduli spaces

So, what’s a moduli space? It’s probably easiest to explain in the genus-one case, which is simple enough to understand, without being completely trivial. Recall that we can obtain a torus by taking a parallelogram and associating edges. Or equivalently by taking the plane and quotienting by a lattice:

freedom

In choosing the fundamental parallelogram, we have a huge amount of freedom. Both the red pair and blue pair of vectors above generate the same lattice, and therefore describe geometrically identical tori.

Now, we can consider the four-dimensional parameter space of fundamental parallelograms (i.e. the space of points (x, y, z, w), corresponding to the parallelograms generated by the vectors (x, y) and (z, w)). At the moment this is just plain old \mathbb{R}^4, but it is more geometrically meaningful to identify points that describe the same lattice. The resulting quotient space, the moduli space, is a four-dimensional manifold.

Observe that rotating and scaling the two vectors results in geometrically similar lattices (therefore geometrically similar Riemann surfaces). We can consider a further quotient of this four-dimensional space, namely a two-dimensional orbifold. You may recognise this as being the quotient of the upper half-plane by the action of the modular group, or the fundamental region of Klein’s j-function:

So, that’s basically what a moduli space is. Maryam discovered a formula for the volume of moduli spaces of a particular genus, resulting in a remarkably elegant new proof of Witten’s conjecture.

Dynamics

Not merely content with providing a marvellous insightful proof about the geometry of moduli spaces, she decided to investigate their dynamics! Firstly, she demonstrated the ergodicity of Thurston’s ‘earthquake deformation’ of hyperbolic space, which is certainly no mean feat!

Ergodic theory is largely concerned with the topological closure of orbits of points. For example, if we take a geodesic on a torus, it will either form a closed loop (e.g. a torus knot) or an irrational cable:

This is a dense subset of the torus, so its topological closure is the torus itself. On more complicated manifolds, such as the moduli spaces considered by Mirzakhani, the topological closures of geodesics can be infinitely intricate fractal structures.

In a similar vein to how holomorphic functions are much more well-behaved than real analytic ones, Mirzakhani settled a long-open conjecture and proved that closures of complex geodesics are always algebraic subvarieties (which are smooth and tame, unlike the pathological fractals that arise in the ergodic theory of real geodesics).

Posted in Uncategorized | 2 Comments