Proto-Penrose tilings

A while ago, Roger Penrose famously filed a lawsuit against Kimberly Clark when his wife discovered that a roll of quilted lavatory paper was adorned with his aperiodic tiling. Although the tiling occurs naturally in quasicrystals, Penrose was probably the first person to discover and abstractly formalise the pattern. Nevertheless, there have been several historical ‘near-misses’ which came close, and indeed would have yielded isomorphic tilings if applied recursively. Since we’ve already mentioned Penrose, it seems only natural to approach this in inverse chronological order.

Kepler’s monsters

It is unknown as to exactly why Johannes Kepler investigated this particular tiling, although one sensible suggestion is that he was trying to construct a tiling of the plane involving only shapes with D10 symmetry. For example, ten regular pentagons neatly fit around a regular decagon of the same edge length, and it is possible to continue the pattern further if pentacles are also allowed:

kepler-fragment

 

Unfortunately, however, it is not possible to continue this process forever. Pretty soon one is required to have decagons overlapping, as in this particular drawing by Kepler:

Kepler’s original drawing of the Kepler’s Monsters tiling.

With the assistance of these fused decagons, termed monsters by Kepler, it is possible to create various periodic and nonperiodic tilings of the plane. Craig Kaplan explored many variations on this theme in his article, with the Keplerian problem of finding a tiling using only (finitely many distinct) shapes of D10 symmetry remaining unsolved.

Even earlier were several attempts by Albrecht Dürer, whom you may know from his Melencolia I engraving inter alia. These featured pentagons and rhombi, similar to Penrose’s original tiling but with less sophisticated matching rules incapable of enforcing aperiodicity.

Girih tiles

I was in the Persian section of the Victoria and Albert Museum during the post-Christmas weekend at the end of last year, and happened to notice various geometric designs. Some of these were periodic carvings of knotwork, not unlike similar examples in the Alhambra in Moorish Spain.

VLUU L200  / Samsung L200

Others were more exciting. One particularly ornate example features angles commensurate with the internal angles of a pentagon, and bears a striking similarity to the aforementioned tilings of Penrose, Kepler and Dürer:

VLUU L200  / Samsung L200

 

Apparently these are formed from a set of five so-called Girih tiles, and patterns of a similar nature occurred throughout the Islamic world since the Middle Ages. I’ll try to find more examples when I visit Tehran next week (thanks Alycia!). In particular, I am intrigued to see the more sophisticated Girih tilings featuring patterns on two scales, where the small-scale pattern is created by applying a set of subdivision rules to the large-scale pattern. This is analogous to the method by which Penrose tilings can be constructed, as you will know from my online demonstration:

wieringa

This surprising and fascinating connection between Islamic architecture and quasicrystalline tilings was first discovered and investigated by Paul Steinhardt and Peter Lu, the latter of whom presented an exposition on the subject at the Harvard Physics Colloquium:

If you found this interesting, there is a talk on early Islamic mathematics by Dr. Bursill-Hall at 16:00 today in Meeting Room 3 of the Centre of Mathematical Sciences.

Miscellany

Finally, I have a few late items of news. Stuart Gascoigne has just sent in the first 8192 2-adic valuations of polylogarithms. The ‘spike’ in the last row (associated with 8192) penetrates significantly deeper into the grid, with Q(3, 8181) being the first integer of the form 64n + 53:

polylog-8192

Here are some other recent highlights:

  • Eugenia Cheng has committed a third instance of gastro-mathematical marketing, namely a formula for the perfect doughnut.
  • Alex Bellos and I attended a pre-release viewing of X+Y, an action thriller following the romantic life of a British olympiad contestant. Expect a review from us next month.
  • Jeffrey Ventrella has been investigating self-similar fractal curves for a while, and recently sent me this analysis of fractal curves based on Gaussian and Eisenstein integers.

 

Posted in Uncategorized | Leave a comment

Oligomath 2: When are polylogarithms integers?

Consider the following series, where k and r are positive integers (and r is strictly greater than 1). Here Li_-is a polylogarithm.

sahl-series

 

We shall pose the following question:

For what values of k and r is Q(r, k) an integer?

 

It is possible to show that Q(r, k) is necessarily rational and that the denominator divides a power of r − 1. We do this by induction on k, expressing Li_-k as a rational function using the following recurrence relation and applying the product rule:

recurrence

In particular, for small values of k, we obtain the following:

polylogs

It is immediately evident that if r = 2, Q(r, k) must necessarily be an integer. On the other hand, if r ≥ 4, Q(r, k) can never be an integer. This leaves only the boundary case of r = 3, which is surprisingly non-trivial.

Which values of Q(3, k) are integers?

The answer is ‘some of them’.

Recalling that the denominator is necessarily a power of two, we can determine whether Q(3, k) is an integer by examining its 2-adic valuation and seeing whether it is positive. (The 2-adic valuation v2(n) of an integer n is defined to be the largest k such that 2^k divides n. This is extended to rationals by setting v2(p/q) = v2(p) − v2(q).)

I decided to compute v2(Q(3, k)) for all k between 0 and 2047. The results are summarised in the grid below, where non-integers are red, integers are green, and the saturation of the colour corresponds to the absolute value of the 2-adic valuation:

two-adic

There are lots of obvious patterns, but many of them seem to break eventually. In particular, one may initially have conjectured that all numbers of the form 64n + 56 are non-integers, but this pattern breaks down at the pale green square corresponding to 1528. Indeed, there appears to be a ruler sequence of spikes originating from the right-hand side of the grid, which (extrapolated in the natural way) would eventually hit every residue class and therefore break every congruence pattern.

So far, Matei Mandache and Sahl Khan established the following facts:

  • If k is a power of two, then Q(3, k) is not an integer;
  • If k is one less than a power of two (and k ≥ 3), then Q(3, k) is an integer.

Stirling numbers of the second kind

Since there seems to be no obvious pattern, we decided to investigate the expression for the polylogarithm in terms of Stirling numbers of the second kind:

stirling-sum

To compute the 2-adic valuation of a sum, it would certainly help to compute the 2-adic valuation of each term in the sum. It would then be possible to obtain either a lower bound or the exact value* of the 2-adic valuation of the sum by applying the following rules (known to anyone who’s played Gabriella Cirulli’s 2048 game):

  • If v2(a) = v2(b), then v2(a + b) > v2(a);
  • Otherwise, v2(a + b) = min(v2(a), v2(b)).

* We obtain the exact value if the number of terms of minimal v2 is odd; otherwise, we merely obtain a lower bound.

By multiplicativity, it suffices to know the 2-adic valuations of the following:

  • v2(i!) = i − (sum of binary digits of i)
  • v2(2^(i+1)) = i + 1
  • v2(S(k + 1, i + 1)) = ???

Fortunately for us, there exists a paper on arXiv entitled:

The 2-adic valuations of Stirling numbers of the second kind

Considering the fact that we want to know the 2-adic valuations of Stirling numbers of the second kind, this paper seemed rather promising. However, upon closer inspection, it is by no means exhaustive (many values are not covered by the paper), so is unlikely to answer our question definitively.

So, as usual, let the collaborations begin!

 

Posted in Oligomath | 3 Comments

Oligomath 1: Deletion and duplication

Collaborative mathematics tends to be extremely fruitful. This is epitomised by the recent ‘polymath’ projects, culminating in a nice proof of density Hales-Jewett along with the frighteningly impressive results on bounded gaps between primes. On a much smaller scale, several of us were contemplating a bunch of interesting and completely unrelated problems we devised in the downstairs kitchen of a converted house in Burrell’s Field, Trinity College, Cambridge.

We’ve made non-trivial progress on many of these, and even succeeded in solving one! It was a natural question, which grew out of a much easier problem on an IMO shortlist:

Suppose you begin with a finite graph, and are allowed to apply operations of the following form:

  • Deletion: Choose a vertex of odd degree and delete it (along with all edges incident with it).
  • Duplication: Produce an identical copy of the graph, and connect each vertex in the original graph to its corresponding vertex in the clone.

Show that, after finitely many operations, one can reach a graph containing no edges.

This is not terribly difficult. It did, however, lead us to consider several related questions (which, at the time of proposal, were all completely new and unsolved). Observe that neither of the allowed operations can decrease the number of connected components of the graph, so if the original graph G has n connected components, then it is impossible to end up with fewer than n vertices. This prompts the following question:

Is this bound tight? Specifically, given a graph G with n connected components, can we necessarily reduce it to the empty graph on n vertices?

It is not too difficult to show that this is equivalent to the question where n = 1. In particular, every time we perform a duplication operation, we then immediately reduce any two-vertex components to single vertices by deletion. Then we can just concentrate on each component sequentially in isolation, without undoing any of our ‘previous work’. (More formally, we can induct on the value of n.)

Hence the problem reduces to:

Can every connected graph be reduced to a single vertex?

In the next few sections, we shall present a proof in the order we devised it.

Tackling the square

It was quite informative to consider some special cases. Any tree can quickly be destroyed by repeatedly removing leaves until we are left with a single vertex. We then decided to consider the square, since it’s the simplest graph which is not a tree (chromatic number is considered to be more important than size, since it cannot increase under either of the operations). After much experimentation, Matei Mandache found the following sequence of operations (which is provably optimal):

square-destruction

Using this as a lemma, we were then able to reduce any cycle, and more generally any connected graph with E \leq V + 1. This was something of a casebash, however, and clear that it would not generalise to yield a full proof. Surprisingly, this ad hoc case of reducing a square to a single vertex does turn out to be essential to our proof!

What about other graphs?

After having reduced the cube, it seemed natural to try the other Platonic solids. The tetrahedron is quite trivial (we can delete a vertex to yield a triangle, duplicate it to obtain a triangular prism, and remove two non-adjacent vertices to give a tree). The dodecahedron is slightly more convoluted, and this particular desynthesis embodies the method applicable to reducing any cycle:

dodecahedron-destruction

According to Donald Knuth, if a conjecture about all graphs seems plausible, it’s often the case that the Petersen graph is a counter-example. But in this case, the Petersen graph is really easy to reduce (it doesn’t require any duplication operations):

petersen-destruction

The hypercube and unduplication

We realised that it would be very useful if we developed a method to reduce an arbitrary hypercube, since induced hypercubes appear as the result of performing repeated duplication operations. The first step in reducing a degree-(2k) hypercube must be to duplicate it to form a degree-(2k + 1) hypercube, since the former has no vertices of odd degree. Consequently, the first thing to consider was the degree-5 hypercube (with 32 vertices). Unfortunately, these things get very messy very quickly:

pentaract

 

A more helpful way to represent this is as a ‘meta-cube’, each vertex of which is a ‘meta-vertex’ corresponding to a square of four ordinary vertices. Then we can delete an entire meta-vertex by deleting two non-adjacent vertices, followed by the other two vertices (the so-called Illingworth manoeuvre). Indeed, in any meta-graph, we can delete any meta-vertex of odd degree. And trivially we can duplicate the entire meta-graph. This has the following consequence:

The product G × C4 of a graph G with a square C4 can be reduced to a single square C4 if the graph G can be reduced to a single vertex.

And since we already know how to reduce a square to a single vertex, we obtain the following lemma:

If G can be reduced to a single vertex, then so can the product of G with a square C4.

Naturally, this can be generalised by iterated application of itself:

If G can be reduced to a single vertex, then so can the product of G with an arbitrary hypercube.

We shall think of this from an equivalent, but much more liberating, perspective:

If we grant ourselves the operation of ‘unduplication’, then the set of graphs we can reduce to a single vertex does not increase.

Henceforth, we shall thus allow unduplication.

Consequences of unduplication

Suppose we have two adjacent vertices of even degree, for example any two adjacent vertices in the octahedron. We can duplicate the graph so that these two adjacent vertices become a square of four vertices of odd degree. Then, we can remove that square by the Illingworth manoeuvre of deleting two non-adjacent vertices followed by the other two vertices. Finally, unduplicate the graph to recover the original graph minus those two vertices:

unduplication

 

So we now have a fourth operation, namely deleting two adjacent vertices of even degree. I now claim that two of our four operations can together reduce any connected graph to a single vertex:

  • Removal of a vertex of odd degree.
  • Removal of two adjacent vertices of even degree.

Suppose instead that there is a counter-example, and consider a minimal counter-example (i.e. one with the fewest vertices). This must have the following properties:

  • Every odd vertex is a cut-point (since otherwise we could remove that odd vertex without disconnecting the graph);
  • Removing any pair of adjacent even vertices must also disconnect the graph.

Consider a graph where these properties hold. We’ll distinguish two cases, namely those where every vertex is even, and those where there exists at least one odd vertex. In each case, we shall obtain a contradiction.

Case I: At least one odd vertex exists

For each odd vertex, we can define its ‘depth’ to be the minimum order of the connected components produced when that vertex is deleted. Now take a vertex v of minimum depth; the minimal connected component produced by deleting v must necessarily consist only of even vertices (since otherwise any of those odd vertices must have lower depth). So our counter-example must resemble this:

counter-example-structure

We’ll concentrate entirely in the region on the right, where everything has even degree. Matei Mandache had the idea of separating this into strata according to their distance from v.

strata

If the final stratum contains two vertices connected to each other, then we can delete those two adjacent vertices without disconnecting the graph. Hence, assume without loss of generality that the final stratum contains no edges.

Then every vertex in the final stratum must be connected to at least two vertices in the penultimate stratum. Consequently, we can remove one vertex in the final stratum and its neighbour in the penultimate stratum without disconnecting the graph (since everything in the final stratum is now connected to at least one vertex in the penultimate stratum).

This contradicts our assumption of minimality.

Case II: All vertices have even degree

This is actually amenable to the same proof technique as before. We let v be an arbitrary vertex, and again stratify the graph so that it resembles this:

other-case

Now we can use exactly the same proof as in the previous case.

The result follows.

What other questions can we ask?

We can ask the more general question as to whether, given graphs G and H, we can get from G to H using those two operations. Note that in general, we no longer have the freedom of unduplication or the removal of two adjacent vertices of even degree.

Clearly, we can get from G to H only if H is an induced subgraph of the product of G with a hypercube. Is the converse also true? Again, this is a strictly harder question than the one that we solved in the downstairs kitchen of ‘V’ House, but it should be quite fun to solve.

Let the collaborations begin! #oligomath

Posted in Oligomath | 4 Comments

Holyhedron update

A while ago, I mentioned the concept of holyhedra: polyhedra, all of whose faces are multiply-connected. The first known example had 78 585 627 faces, and was later superseded by a highly symmetric example with as few as 492 faces. This is far from optimal, though, as yesterday I received an e-mail from Nathan Ho describing a 12-faced holyhedron!

holy_angled_view

This leaves open the question of the minimum number of faces a holyhedron can possess. We know that for the deceptively similarly named golyhedra, the answer is 11 as demonstrated by Alexey Nigin’s wonderfully minimal example:

golyhedron-minimal

The corresponding lower bound of 11 can be derived from the following simple derivation:

  • By numerical considerations, the number of faces can only be 0 or 3 (modulo 4).
  • If an orthogonal polyhedron has 8 or fewer faces, then one of the three axes has at most two faces orthogonal to it. Clearly, they must point in opposite directions and have equal area, so the polyhedron cannot be a golyhedron.

Other projects

In other news, Hans Havermann has attacked the ménage prime problem with a computer search, exhausting all ménage numbers with fewer than 110 000 digits. Consequently, the expected number of ménage primes with fewer than 1000000 digits is about 0.195.

Also, I mentioned a while ago about the project to create a 31c/240 spaceship in Conway’s Game of Life. Dave Greene finally implemented my shield bug design, although changing one of the details resulted in the completed spaceship looking nothing like a shield bug whatsoever!

31c240

It’s an immense 934856 by 290486 pixels in size, making it (by area) much larger than the 17c/45 caterpillar that began the tradition of naming these large cumbersome track-laying spaceships after insects. The (23,5)c/79 and (13,1)c/31 projects appear to have been abandoned.

On an unrelated topic, a discussion with Tim Hutton and Simon Rawles in a pub in Cambridge has culminated in them investigating various embeddings of surfaces by crocheting them. Most recently Tim has produced a Chen-Gackstatter surface in this manner:

Another interesting blog by a computer scientist is that of Susan Stepney. One of her recent posts featured a video of a rendition of a particular music video in the Alexandroff Corridor of Newnham College, Cambridge, which Trinity has recently reproduced in an attempt to encourage the artist to perform at the forthcoming (149th) May Ball:

This has recently gained quite a lot of media attention across Europe, appearing in both a Spanish and a Croatian newspaper. Further bulletins as events warrant…

Posted in Uncategorized | 8 Comments

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 | 6 Comments

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 | 1 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 | 1 Comment