How much room a hard question needs

Nothing decides whether a set of tiles tiles the plane, and the argument is not about the size of the search: a set of Wang tiles can encode the running of a machine, so deciding tiling would decide halting. What can be done is two half-searches, each of which answers one way and never the other — hunt for a periodic block, which proves the plane is covered, and hunt for a square that cannot be covered at all, which proves it is not.

That essay measures what the pair of searches leaves behind on tile sets drawn at random. It cannot answer the question this rung is about, because a sample says nothing about a universe it did not exhaust. How much room does the undecidable residue actually need?

The universes small enough to exhaust are very small, and they are complete answers rather than estimates.

Sixteen tiles, and everything made from them #

A Wang tile is a unit square with a colour on each edge. Tiles are laid edge to edge with matching colours, never turned and never reflected. With two colours there are two choices on each of four edges, so there are exactly sixteen tiles, and every set of three is one of five hundred and sixty subsets.

Not all five hundred and sixty are different questions. Nothing anywhere in the tiling condition reads a colour except by comparing it with another, so relabelling the colours changes no answer — and the horizontal colours and the vertical ones may be relabelled independently, because the condition on a vertical edge never meets the condition on a horizontal one. Dividing that out leaves one hundred and forty genuinely distinct sets of three.

Every one of the one hundred and forty is then handed to both searches at a small bound: a torus of up to four by four for a periodic certificate, and squares of up to four by four for an obstruction. One hundred and fourteen tile the plane, twenty-six cannot, and none is left over.

The same holds at one, two and four tiles, and with three colours as far as the enumeration has been pushed: eighty-five thousand subsets of three tiles reduce to two thousand four hundred and fifty-five distinct sets, and every one of them is decided. In a small world there is no hard case.

Why the empty column is the result #

An empty column is an odd thing to build an essay around, so it is worth being precise about what it says.

The two searches decide a set unless it does two things at once: tiles the plane, and admits no periodic tiling whatever. Such a set is called aperiodic, and on one the periodic search runs for ever because there is no certificate to find, while the obstruction search runs for ever because there is no obstruction to find. The undecidability theorem does not say that some particular set defeats every algorithm — it says no single algorithm decides them all, and the sets where the two half-searches are no help are exactly the aperiodic ones and their neighbours.

So the undecided column counts aperiodic sets and the sets whose verdict lies beyond the bound. At two colours and four tiles the column is empty, which says something specific and complete: there is no aperiodic set of that size, and no set of that size whose behaviour is even slow to establish.

That is the shape of the answer. Aperiodicity is not rare in the sense of being delicate — the hat shows a single shape can manage it — it is rare in the sense of needing room. The smallest aperiodic Wang set is known: eleven tiles and four colours, established by Jeandel and Rao in 2015 by an exhaustive search over a space some twenty orders of magnitude larger than the one above, and their search also proved that no set of ten tiles or of three colours can be aperiodic. That number is quoted here rather than reproduced, and the reason is arithmetic: three colours give eighty-one tiles and four give two hundred and fifty-six, and the sets of eleven from two hundred and fifty-six are more numerous than the atoms in a small planet.

What the bound is worth, and where it stops being worth anything #

The census above uses a bound of four, and a bound is a promise about nothing outside itself. Two things keep it honest.

The first is that the bound is reported with every verdict. A set that is not decided is recorded as unknown at this bound, never as cannot — the error this collection’s account of undecidability exists to make impossible, and the one a table with three columns makes very easy.

The second is that raising the bound is a measurement in its own right. The largest periodic certificate any two-colour set of three tiles needs is a three-by-three torus; at four tiles it is smaller still. So the bound of four is not close to binding, and the empty column is not an artefact of a search that was stopped early.

The contrast between the two figures is the point of putting them together. On randomly generated sets with sixteen tiles and five colours, raising the bound keeps moving sets out of the unknown column and never empties it. On the complete enumeration of a small world, the column was empty from the start.

The obstruction, when there is one #

Half the census is sets that cannot tile at all, and those are decided by finding a square that cannot be covered. It is worth seeing what that failure looks like, because it is the only half of the question with a finite witness.

The asymmetry between the two halves is worth stating plainly. A cannot has a finite witness that can be checked in a moment by anyone. A tiles has one too, when the tiling is periodic: the torus block is a certificate, and repeating it out is a check. What has no finite witness of either kind is the third case, and that is not an accident of the searches used here but the content of Berger’s theorem.

What the decided sets look like #

The census carries more than three totals, and what is inside it says why the small worlds are easy.

Of the one hundred and fourteen three-tile sets that tile, eighty-five need no more than a single tile repeated: their certificate is a one-by-one torus, meaning some tile in the set has its north colour equal to its south and its east equal to its west, and that tile alone covers the plane. Eighteen more need a two-cell block, seven need four cells, and four need a three-by-three. The largest certificate anywhere in the census is nine cells.

The failures are smaller still. Of the twenty-six sets that cannot tile, twenty-four are refuted by a two-by-two square and the remaining two by a three-by-three. Nothing in this world takes any finding.

At four tiles the shape is the same and more pronounced: three hundred and forty-one of the four hundred and fifty-one tilers have a single self-matching tile, and the largest certificate needed drops to six cells, because a larger set is more likely to contain an easy member. Adding tiles makes tiling easier, which is why an aperiodic set — a set that tiles and does so only in complicated ways — is being asked for something that gets harder to arrange as the set grows in the obvious direction and only becomes possible when there are enough tiles to encode a constraint with.

That is the mechanism behind the empty column, stated in the census’s own numbers. With two colours there is not enough vocabulary to say anything that forces a tiling to be complicated. A tile either matches itself, in which case the plane is covered trivially, or the few ways of matching its neighbours run out within a two-by-two square.

What the small worlds have in common with the large one #

A complete census of a small universe is a satisfying object, and it is also a warning. Every count in it — 4, 36, 140, 476 distinct sets at one, two, three and four tiles — is the kind of number this collection is full of: seventeen, thirty-two, two hundred and thirty, eleven uniform tilings. Those counts are complete because the classifications behind them are theorems.

The counts here are complete in a much weaker sense. They enumerate every set and decide each one, but the deciding used two searches whose termination is not guaranteed in general, and the reason they all terminated is that there was nothing hard in the world being searched. Scale the world up and the same procedure produces a table with a fourth column that never empties.

That difference — between a classification and an enumeration that happened to finish — is the one this rung exists to make legible. The thing being counted is the same at every size. What changes is whether counting is a procedure or a piece of luck.

The one-tile world, for scale #

The smallest census of all is worth writing down because it is four rows long and every one of them is instructive.

With two colours there are sixteen tiles, and up to relabelling there are four sets consisting of one tile. Exactly one of them tiles the plane: the tile whose north colour equals its south and whose east equals its west, which repeats without any decision being made. The other three cannot tile at all, and each is refuted inside a two-by-two square — a tile whose east colour differs from its west cannot stand beside itself, and with nothing else available the plane is out of reach at the second square.

That is the whole of the one-tile theory, and it makes an instructive comparison with the polygon case. A single Wang tile is either trivial or impossible; a single polygon can be an aperiodic monotile. The difference is that a Wang tile’s matching condition is carried by four colours and nothing else, while a polygon’s is carried by its boundary, which has as much room in it as its perimeter allows — thirteen sides, in the case that works.

So the question this essay asks has a different answer in the two settings, and the reason is not depth but bandwidth. Undecidability needs room to write a constraint in, and the two settings measure room in different units.

What the two half-searches cost #

The census above runs both searches on every set, and the costs are worth comparing because they are so unequal.

The obstruction search is cheap and gets cheaper as the set gets worse. A set that cannot tile usually fails inside a two-by-two square, and the search that finds it is an exhaustive placement over four cells with a handful of tiles — a few hundred operations. The worse a set is, the sooner it fails, so the half-search that answers no is fastest exactly where it is needed.

The periodic search is cheap and gets cheaper as the set gets better. A set containing a tile that matches itself is certified by a one-by-one torus immediately; eighty-five of the hundred and fourteen tilers in the three-tile census are of that kind. The awkward cases in between — a set that tiles only with a three-by-three repeat — cost the most, and there are four of them.

So the total cost of deciding a small world is dominated by neither search but by the sets that are nearly hard, and there are very few. That is the computational shadow of the empty column: an undecidable residue would show up first as a growing population of sets that take a long time and then get decided, and the census shows no such population.

It is worth contrasting that with the polygon search of one tile, and no period, where the corresponding population is not empty. There, three shapes hit the step limit and were reported undecided, and seventeen more were only refused by the largest region searched. The Wang world at two colours is easy in a way the polykite world at eight cells is not, and the counts say so before any theory is invoked.

Where the exactness stops #

Computed here: the number of distinct two-colour sets at one, two, three and four tiles, and at three colours up to three tiles; the verdict for every one of them at a stated bound; the largest periodic certificate any of them requires; and the demonstration that relabelling the two colour alphabets is a symmetry of the question while turning a tile is not.

Quoted: that the smallest aperiodic set of Wang tiles has eleven tiles and four colours, and that no smaller set is aperiodic. That is Jeandel and Rao’s computer-assisted proof of 2015; nothing here reproduces it, and nothing here could.

And what the census cannot say. An empty unknown column at four tiles is not evidence about eleven. The whole content of the undecidability result is that the difficulty appears somewhere and cannot be extrapolated to; a census that stops at four is a census of what happens before the interesting thing starts.

Who found it, and when #

Hao Wang posed the domino problem in 1961 and conjectured that any set that tiles the plane tiles it periodically — which, had it been true, would have made the problem decidable by exactly the first of the two half-searches above. Robert Berger, his student, refuted it in 1966 with an aperiodic set of 20,426 tiles and proved the problem undecidable in the same thesis. The count fell steadily: Berger to 104, Knuth to 92, Robinson to 56 in 1971, Culik and Kari to 13 in 1996. Emmanuel Jeandel and Michaël Rao closed it at eleven in 2015, and closed the colour count at four.

Fifty-four years from the question to the smallest instance is a long time for a finite search, and the reason is the size of the space rather than the difficulty of any one case — which is the same observation this census makes at four tiles, in the direction where the answer is easy.

Where the ladder goes next #

Back, to the theorem this rung is an exercise inside. Nothing decides whether a set of tiles tiles the plane has the two half-searches, the sampled census and the argument for why no third search closes the gap.

Sideways, to local success that is not global success. Surrounded twice over, and covering nothing measures how much of a tiling a shape that tiles nothing can produce, which is the same phenomenon in the geometry of one shape rather than in the combinatorics of a set.

And to the shape that needs no set at all: one tile, and no period, where the same two searches are run on a polygon rather than on coloured squares, and the enumeration that finds it is complete for exactly the same reason this one is — the world it searches is small.

Where the empty column stops being empty #

The census’s undecided column is empty at four tiles, and the essay’s title asks how much room a hard question needs. That question has a complete answer, it was settled by exactly this kind of exhaustive search carried much further, and it is worth recording.

The smallest aperiodic set of Wang tiles has eleven tiles and four colours. It was found by Jeandel and Rao in 2015, and the same work proved it minimal in both directions at once: no set of ten or fewer tiles is aperiodic, whatever the number of colours, and no set over three colours is aperiodic, whatever the number of tiles.

Both halves are exhaustive searches of the kind this essay runs, at a scale that needed a computer and a great deal of care about the bounds — the same two-search structure, with the same discipline about what an unresolved case may be recorded as.

So the empty column stays empty up to ten tiles and has one entry at eleven, and the whole of the gap between decidable-by-exhaustion and undecidable-in-general lives in that step.

That is an unusually satisfying place for a subject with an undecidability theorem in it to arrive. The general question has no algorithm; the smallest interesting instance is nevertheless completely classified, and the classification says how much room the difficulty needs before it can exist at all.