Surrounded twice over, and covering nothing

A search for a tiling has an obvious shape. Put down a copy of the shape. Surround it with more copies so that nothing touching it is uncovered. Surround those. Keep going, and either the plane fills or the search gets stuck.

The trouble is what “gets stuck” means. A search that has not yet failed has not yet succeeded either, and nothing decides which of the two it is heading for. What can be measured is how far it gets before it stops — and the answer is a number, one per shape, called the shape’s Heesch number.

A corona is one ring: a set of non-overlapping copies covering every cell that touches what is already down, corner contacts included. The first corona surrounds the tile; the second surrounds the first; and a shape that tiles the plane has coronas of every depth, since the tiling supplies them. So a finite Heesch number is a certificate of not tiling — and how large it can be is the question.

The number is a measurement, not an estimate #

The seven-cell shape above accepts no first corona. Others do better.

Nothing about these shapes looks different from a shape that tiles. The second one is a plain hook; the third has two notches. The difference is not visible in the outline, which is exactly the situation the neighbouring rungs are about: a boundary condition settles some of these cases and declines the rest, and declining is not evidence.

The mistake that changes the answer #

The obvious way to run the search is level by level: fill the first corona, then look for a second. That is what a person does with physical tiles on a table, and it is wrong.

Filling one corona and then asking about the next settles nothing when the answer is no. Some other completion of the first ring might have admitted a second. So a failure at depth two has to send the search back into the choices at depth one, and try them all, before it may report a no.

That is not a fine point. Run without it, the census reports no polyomino to eight cells with a Heesch number above one. Run with it, one shape reaches two — and the number of shapes settled outright falls, because the deeper search costs more and more of them exhaust their budget instead. Both numbers change, in opposite directions, and only one pair is right.

The failure is easy to miss because the wrong procedure is not obviously wrong: it produces a complete first corona, which is a real object, and then fails honestly at the second. What it has actually established is this particular ring admits no second ring, and the claim wanted is no ring admits a second. The first is a statement about one choice out of thousands. The distance between the two is the whole search, and a program that stops at the first is not doing a cheaper version of the right computation — it is doing a different one, whose answer happens to be a number in the same range. The only defence is to make the recursion own the choice: a placement that leads nowhere at depth two must be undone at depth one and the next one tried, so that a report of failure at any depth is a report about every arrangement below it.

What a search that ran out is allowed to say #

This is the anchor’s own question, and it is the reason the anchor exists.

A search that finds a corona has proved something: the patch is the proof, and it can be checked by anybody. A search that finds none has proved nothing until it has finished, and finishing is not guaranteed — the space of placements grows quickly with the depth and with the size of the shape.

So every answer here carries two things it would be easy to leave out: the number of placements the search cost, and whether the search exhausted its space or ran out of budget. The two are never merged into one word. A shape whose search was truncated is reported as surrounded at least k times, not as has Heesch number k, and the census counts the truncated ones separately.

Four of the thirty are truncated at a budget of a million and a half placements. Their Heesch numbers are unknown here. That is a smaller and duller claim than a table of thirty numbers, and it is the true one.

Why it is a bounded search at all #

The corona search is finite for a reason that is easy to miss: it is bounded by the box it is run in, not by anything about the shape.

Placements are enumerated inside a square whose half-width grows with the depth asked for. A corona needing a copy outside that box cannot be built there, and the search says so — reporting a truncation rather than a failure. That is a second way the honest answer differs from the convenient one, and it is checked the same way: the box is a stated parameter, and a shape whose answer moves when the box grows is a shape whose answer was about the box.

The wider point is the one the previous rung made about tilings and the one this rung makes about coronas. Every finite procedure here has a parameter in it — a bound on the block, a bound on the box, a budget in nodes — and the whole discipline consists of reporting which parameter each answer depended on. It is the same habit as naming the tolerance on a measurement that has one, in a setting where the parameter is a count rather than a length. A number without its bound attached is a number pretending to be a theorem.

What counts as surrounded #

The definition has to be exact or the numbers mean nothing, and there are two places it could slip.

Corner contacts count. A cell diagonally adjacent to the seed touches it at a point, and a corona that leaves such a cell uncovered has left the seed with a hole beside it that no tiling could have. So the region a corona must cover is the seed dilated by a king’s move rather than by a rook’s, and the difference is real: several of the shapes here accept a rook-move ring and not a king-move one.

The copies may be turned and reflected. A polyomino has up to eight distinct orientations, and all of them are available, since nothing about a tiling forbids a mirrored tile. Restricting to translations would be a different question with different answers — the Wang tiles next door are exactly the case where turning is forbidden, and forbidding it is what makes them a computational object rather than a jigsaw.

And a corona is required to cover, not to close. The copies of a ring have to cover every cell touching what is already down, and they have to avoid overlapping anything; they are not required to leave the outside of the ring tidy, or to touch one another, or to form a connected band. Requiring any of that would be a stronger condition and would produce smaller numbers, and it would be the wrong condition — the reason a corona is interesting is that it is exactly what a tiling would have to supply at that distance, and a tiling makes no promises about the outside of a ring either. The definition is chosen to be the weakest one under which “coronas of every depth” implies “tiles the plane”, because the whole value of a finite Heesch number is as the contrapositive of that implication.

The cost, and where it goes #

The search is a backtracking cover: take the first uncovered cell of the target region, try every placement covering it that clashes with nothing already down, and recurse. Its cost is not evenly spread.

Reaching depth zero is cheap — the seven-cell shape above was settled in a hundred and fifty-six placements, because there are few ways to start and all of them fail early. Reaching depth one is expensive: three hundred and sixty thousand placements for the hook, because every completion of the first ring has to be tried against the second. Reaching depth two costs less than depth one for the eight-cell shape, at two hundred and eighty thousand, which is a reminder that these costs are about how constrained a shape is rather than about how far it gets.

The shape of that cost is worth naming, because it explains why the census stops where it does. Each ring has to cover a region whose perimeter grows with the depth, so the number of cells to be covered grows roughly linearly and the number of ways to cover them grows roughly exponentially in that. A shape with eight cells and eight orientations offers a few dozen placements against any given uncovered cell, and the search multiplies those choices along the whole boundary before it can report anything about the ring outside. So the interesting quantity is not how long one ring takes but how much the next ring multiplies it by, and that factor is itself a property of the shape rather than a constant: a shape whose ring closes in only one or two ways is cheap at every depth, and one whose ring closes in a hundred is not.

The budget is the honest part of the procedure. It is a stated number of placements; a search that exceeds it stops and says so. Four shapes do. Raising the budget from three hundred thousand to a million and a half moved four of them from unsettled to settled and left four where they were, which is the ordinary behaviour of a bound that is doing its job: it buys some cases and never buys all of them.

Two directions, and only one of them has a certificate #

The asymmetry the anchor keeps returning to is sharpest here, because both halves of a Heesch number are produced by the same search and only one of them can be handed to somebody else.

“This shape can be surrounded twice” is witnessed by a patch. The witness is a finite list of placements — a copy, a position, an orientation for each — and checking it is mechanical: confirm that no two copies overlap, and that every cell of the seed and of the first ring has a copy on every side and corner. The check reads the list once. It does not repeat the search, it does not need the search’s budget, and it does not need to trust the program that produced it.

“This shape cannot be surrounded three times” is witnessed by nothing. The only support for it is that a search finished without finding one, and reproducing that support means running the search again. There is no short object to hand over, and none is known to exist: the statement is about the absence of an arrangement, and the space it is absent from is the thing that took the time.

So the two numbers reported for each shape in the census are not two measurements of the same kind. The lower bound is a fact with a certificate attached. The upper bound is a fact about a completed computation, and it is only as good as the claim that the enumeration was exhaustive — which is why the budget is printed beside it, and why the four truncated entries are reported as truncated rather than rounded off.

What the search does not have to look at twice #

The cost of an exhaustive corona search is dominated by placements that differ from one another by nothing that matters, and the standard economies are all of one kind: quotient before searching.

The shape’s own symmetry is the first. A polyomino with a mirror has each of its patches produced twice by the enumeration — once from each of the two orientations that give the same set of cells — and a square-symmetric shape has each patch produced eight times. Fixing a canonical orientation for the seed removes that factor exactly, and the factor is the order of the shape’s stabiliser rather than a heuristic estimate.

The patch’s own symmetry is the second and it is subtler, because it is a property of the partial arrangement rather than of the shape. Two partial coronas related by a symmetry of the seed lead to the same completions, so only one of them needs continuing — but recognising that means canonicalising a set of placed copies rather than a single tile, and the bookkeeping costs more than it saves on small shapes.

What neither economy touches is the exponent. Pruning by a constant factor moves the budget along and does not change what the budget is for: the number of arrangements grows with the depth asked for, and a shape that survives two rings has a third-ring search several orders of magnitude larger than the second. That is the reason the record numbers in the literature were reached one at a time over ninety years rather than by a sweep.

The same distinction decides what a census like the one above is allowed to publish. Thirty shapes, each with a Heesch number and a budget: the number is a pair of claims of different logical strength stapled together, and a table that printed one column would be inviting the stronger reading of both. Printing the budget is what keeps the weaker half honest, and it is the reason four rows here say at least rather than a number.

How large can it be #

Nothing here bounds the Heesch number. If some shape had an infinite one it would tile the plane, since the coronas would supply a covering — the same compactness argument that makes a square that cannot be filled a proof that the plane cannot be either — but there is no theorem saying the finite values stop anywhere.

The known record has crept upwards for ninety years. Heesch’s own example reached one. Shapes reaching two, three and four were found by hand and by computer over the following decades; Casey Mann’s tile of 2001 reached five; Bojan Bašić published a shape reaching six in 2020. Every one of those is a construction, not a search of all shapes, and every one is a lower bound on what is possible. Whether Heesch numbers are bounded at all is open, and it matters: an upper bound would make the single-tile tiling question decidable, because a shape could be tested by surrounding it that many times and stopping.

Why nobody expects a bound is worth stating, because the expectation runs the other way from the evidence. Every shape found so far has a small Heesch number, and the record has moved by one every couple of decades — which looks like a sequence approaching a ceiling. But each of those records is a construction, built by somebody who wanted that number, and the constructions have grown more elaborate rather than running into an obstruction. Nothing in the geometry says a ring of copies can only be built so many times, and the analogy that does exist points the wrong way: the tiling question for sets of tiles is undecidable, and the standard mechanism for that is exactly a family of finite patches whose sizes grow without bound. A bound on Heesch numbers would make the single-tile question decidable, and a decidable single-tile question sitting next to an undecidable set-of-tiles question would need explaining.

Those numbers are quoted from the literature. Nothing in this essay computes them, and the tiles that achieve them are not polyominoes. What is computed here is a complete census of a small family, which is the trade this collection makes everywhere: a complete answer to a restricted question rather than a partial one to a wide one.

The shape of the whole argument #

Three questions have been asked of the same object in three essays, and they line up.

Does it tile? Undecidable for sets of tiles, unknown for single ones, and answered here by exhibiting a tiling of a torus — a certificate, one-way. The same shape of answer as a periodic block for a Wang set.

Does it tile isohedrally? Decidable, by a search over a finite list of candidate groups, because the grid’s symmetry group is ℤ² ⋊ D₄ and the translation lattice of an isohedral tiling has bounded index.

How far does it get? Measurable to a stated depth and budget, and reported with both.

The three answers are of three different logical kinds and it would be easy to print them in one table as though they were the same kind of fact. The census here prints them in three columns for exactly that reason.

And there is a fourth kind, which the neighbouring rung is about: a sufficient condition that always terminates and sometimes declines to answer. Conway’s criterion reads a tile’s boundary word, cuts it into six arcs if it can, and says tiles — or says nothing at all, which is not the same as saying does not tile. It settles four hundred and seventy of the five hundred and thirty-three shapes here and declines on the other sixty-three — of which thirty-three tile the plane perfectly well and thirty are in the corona census above.

That fourth kind is worth separating from the other three, because it is the only member of the family whose positive answer arrives with the object it is an answer about. Conway’s criterion does not report that a tiling exists; it hands over the group that makes one, and the tiling can then be generated and its covering counted cell by cell. A reader who distrusts the criterion can check the tiling instead, which is a different and much smaller thing to check. The corona search’s positive answers have the same character — a patch is a certificate — and its negative answers do not, and neither do the negative answers of any of the four. That asymmetry is not an accident of how these particular searches were written. It is what it means for a question to be about the absence of an arrangement rather than the presence of one.

What the number is good for #

A Heesch number is a curiosity until it is put beside the thing it bounds, and then it is the only quantity available.

It bounds a search. A procedure asked whether a shape tiles will, in practice, try to build a patch. If the shape’s Heesch number is two, that procedure will get two rings out and then fail — and it will have spent everything it spent on those two rings for nothing. Knowing that non-tilers reach two and no further, in a family, is knowing how deep a search has to go before its failure means something.

It is the one number that separates nearly tiles from tiles. Every other measurement of a non-tiling shape is a measurement of a failure: an area that cannot be covered, a square that cannot be filled. The Heesch number measures the success instead, and it is the only quantity in the subject that does.

And it is the quantity a bound on the question would have to bound. If Heesch numbers were known to be at most some H, then a shape could be tested by surrounding it H + 1 times: success means it tiles, failure means it does not, and the single-tile tiling question would be decidable. That nobody can bound them is the whole of why nobody can decide it, and it is why a record of six is a fact about the state of the subject rather than a curiosity about one tile.

Where the ladder goes next #

The natural direction is towards the results that are clean. Which convex polygons tile has a complete answer, and the reason is that convexity plus a small number of sides is a strong enough restriction to make the question finite. Every clean tiling result in this collection has a restriction of that kind hiding in it, and finding the restriction is usually the whole work.

The other direction is the one these three essays share. A corona is a local success; a tiling is a global one; and the gap between them is not a matter of trying harder. It is measurable, it has been measured here to eight cells, and the measurement’s own bounds are printed beside it. A tile that covers the plane and needs two orbits to do it is the same lesson from the other side: the local object is one thing everywhere and the global object is not.