The argument that closes eleven

Twenty-one vertices, eleven tilings is one of the tidiest results this collection has, and its tidiness comes from having two halves that meet exactly. The angle equation has twenty-one solutions as cyclic orderings; a parity argument refutes ten of them before anything is drawn; and the remaining eleven are all built by a grower that knows nothing of the argument. Two independent computations, no gap.

The obvious next question is what happens with two kinds of vertex — tilings by regular polygons whose vertices fall into exactly two orbits. The literature’s answer is twenty, and this collection has carried the question in its shortfall queue for four phases.

It is still there, and this essay is why. The count is not available to a search, and the argument that closes the uniform count does not survive a second species. Both halves of that are computed rather than asserted.

What the parity argument actually uses #

The argument is three sentences and worth having exactly, because the step that fails is the second.

Walk round one polygon of odd size n. At each of its corners, the two polygons flanking it are decided by the species at that corner — a vertex reading 3.4.6.4 has, at each of its corners, a determined pair of neighbours. So the ring of polygons around the odd one is a closed walk of length n in a small graph whose vertices are polygon sizes and whose edges are those flanking pairs.

A bipartite graph has no closed walk of odd length. So if that graph comes out bipartite, no such ring exists, and the species tiles nothing. Ten of the twenty-one die there — 3.7.42 because a heptagon cannot alternate triangle and forty-two-gon seven times, 5.5.10 because a pentagon cannot alternate pentagon and decagon five times.

Every step of that uses one species, and the second step uses it fatally. “The two polygons flanking a corner are decided by the species” is true when every vertex reads the same species and false the moment two are allowed. With two species the flanking pairs at a corner come from either, so the graph the walk lives in is the union of the two species’ graphs — and a union of bipartite graphs need not be bipartite.

Thirty-six pairs are in that position: the argument kills at least one member on its own and cannot kill the pair. One pair has both members individually refuted and survives as a pair — the two impossible vertex types making each other possible, which is exactly what the union of two bipartite graphs failing to be bipartite means in ordinary language.

The refutation is not weakened by a second species. It is absent. That distinction matters: a weakened argument still eliminates candidates and a search then has less to do, whereas an absent one leaves the whole field open and hands the entire question to construction.

Why the two counts feel alike and are not #

Twenty-one and eleven, two hundred and ten and twenty: the two questions look like the same question at two sizes, and treating them that way is what makes the second one seem merely harder.

They are not the same question. The uniform one asks which species tile, and a species is a finite object — a cyclic word of at most six letters — so the question is a property of a small combinatorial thing and can be settled by inspecting it. The two-uniform one asks which pairs admit a tiling with exactly two vertex orbits, and that is not a property of the pair at all: it is a property of an arrangement, and the same pair may admit an aperiodic patch, a three-uniform tiling, and a two-uniform one, or only some of those.

The clearest sign of the difference is what the grower produces. Handed a species that tiles, it produces the tiling — there is essentially one, and the choices near the seed exhaust it. Handed a pair, it produces uncountably many patches, of which the periodic ones with two orbits are a measure-zero handful. The uniform question has a finite answer space and the two-uniform question does not, and every difficulty in this essay is that sentence.

What can still be said cheaply #

One thing survives, and it is worth having because it costs two set intersections.

An edge of a tiling by regular polygons carries exactly two polygons. So a vertex of one species and a vertex of the other can sit at the two ends of an edge only if some polygon size occurs in both species — otherwise the two vertex classes could never be adjacent, and a tiling with two orbits of vertices needs them to be.

Sixty-two pairs out of two hundred and ten, for the cost of two set intersections. It is a necessary condition and not a sufficient one, and the comparison with the uniform case is the point: there, a cheap argument disposed of ten of twenty-one and construction settled the rest completely. Here a cheap argument disposes of sixty-two of two hundred and ten and construction settles nothing.

The grower, generalised #

The grower this collection uses for the uniform tilings was written for one species, and the whole of that assumption lived in a single string: a canonical form of the species, compared against at each completed vertex.

Generalising it is smaller than it sounds. The comparison becomes membership of a set; the readings offered at a partly-built vertex are drawn from every species in the set; and nothing else changes, because everything else the grower does is about polygons meeting rather than about which species they make. An edge may carry two polygons and no more; a polygon that repeats an existing one is the same polygon; no polygon may overlap another. All of that is species-blind.

The single-species behaviour is unchanged, which is what makes it a generalisation rather than a second grower, and that is asserted rather than hoped: a set of one species grows the same number of polygons as the species did, and the check is in the refusals.

So the machinery exists and the question can be asked. It is the asking that does not work.

Why the search does not find them #

The grower is deterministic apart from one choice: which reading of the species a vertex is completed under. For the uniform tilings that choice matters at a handful of vertices near the seed, and enumerating short prefixes of the choice sequence finds every one of the eleven.

With two species the choice matters at every vertex, because every vertex may be completed as either kind. A prefix search then stays inside the corner of the space where every vertex was finished as the first species — which is a uniform tiling, reached the long way round. Measured: sixty prefix vectors at depth five found no hexagon at all in a pair containing one.

Randomising instead fixes that and does not fix the problem.

Every random vector produces a legal patch, and every one contains both species — so the generalisation works. Not one is periodic. A two-uniform tiling has to be periodic, and a random walk through the choices produces a legal aperiodic patch essentially always.

That is not a failure of effort. It is a statement about the shape of the space: the choice sequences that give a periodic tiling are themselves periodic, and a sequence sampled at random is not. Finding them by search means searching over structured sequences, which is a different search — and one whose exhaustiveness would then have to be argued rather than run.

The three ways a count can be closed #

It is worth setting out what “closing a count” means here, because this collection has now met all three ways and they are not equally available.

By exhaustion of a finite space. The angle equation has twenty-one solutions because a multiset of polygon sizes filling a turn is a finite search with a computable bound: no polygon past a forty-two-gon can appear, so the enumeration is complete by construction. This is the cheapest kind of closure and it is why the first number in the uniform story is unarguable.

By a refutation. Ten of the twenty-one die to the parity argument, which is not a search: it inspects a graph and concludes that no tiling exists, for every tiling, at once. A refutation closes a question in the direction of impossibility and costs nothing per candidate.

By construction. The eleven survivors are built, which closes the question in the other direction. Construction is expensive per candidate and it is what a grower does.

The uniform count is closed because all three are available and they meet: the first bounds the field, the second removes ten, the third produces eleven, and eleven plus ten is twenty-one. The two-uniform count has the first and the third and not the second, and the third alone can only ever establish a lower bound — because a construction that fails proves nothing about whether a better search would have succeeded.

That asymmetry is general and worth carrying out of this essay. A count is settled by a proof of impossibility together with a construction; a construction alone settles a count only when the field it runs over is finite and every member of it has been tried. Here the field is a space of choice sequences, which is not finite.

What a bounded search is entitled to say, once more #

This collection has a standing rule about searches inside bounds, stated when the one-vertex census failed to close: a search that finds n objects has established at least n, and has established n exactly only if some argument says nothing outside the bound could be new.

For the eleven uniform tilings, that argument exists and is the parity refutation. For the twenty two-uniform ones, it does not — not because nobody has looked, but because the specific argument that closes the first count is gone.

So the honest form of the two-uniform question is a search reporting “at least this many, at this bound”, and this collection would rather report nothing than report twenty. The number twenty is Krötenheerdt’s, from 1969, and it rests on an exhaustive case analysis over how the two vertex classes can be arranged around each polygon — an argument of the same kind as the parity one and very much longer. Reproducing it is a project, and it is a project this essay is the case for rather than a substitute for.

That is the shape of the whole decidability anchor arriving one level down. No procedure decides whether a set of tiles tiles the plane is a theorem about a general question; this is a specific question with a specific answer that a specific search cannot reach, and the gap between “undecidable” and “not settled by this” is where most of tiling theory actually lives.

What the generalisation is good for anyway #

The grower now takes a set of species, and the question it was generalised for is not settled — so it is worth saying what the change bought, since it was not nothing.

It bought the ability to exhibit a two-species patch, which is the figure above and is not a small thing: before it, this collection could draw the eleven uniform tilings and nothing between them and a random arrangement of polygons. A legal patch with two kinds of vertex is the object the whole question is about, and having one to look at is the difference between a question stated and a question shown.

It bought the measurement that the tilings are rare among choice sequences rather than among patches, which is the actual obstacle and which nobody could have asserted without running it.

And it bought the pair machinery — the local condition, the union parity test — which are the two cheap statements available about a pair. Both are necessary conditions, both are computed over all two hundred and ten pairs, and together they leave ninety-one pairs about which nothing whatever is known. That ninety-one is the honest size of the remaining question, and it is a number this collection did not have before.

What it refuses #

The third is the one that makes the rest trustworthy. A generalisation that changed the single-species answers would have invalidated the eleven and their groups as a side effect of asking a new question, and the change would have been invisible: the uniform tilings would still have grown, still have been periodic, and still have had groups — only different ones. So it is checked as an identity of outputs rather than as an intention.

The first is the one that keeps the grower honest about its input. Handed a pair with no shared polygon size, it must not complete a vertex at all, because completing one would mean it had accepted a species it was not given.

Who asked it first, and what they did instead #

Krötenheerdt enumerated the two-uniform tilings in 1969, and the shape of his argument is worth describing because it is the shape this essay says is needed.

He did not search choice sequences. He argued over the arrangement of the two vertex classes around each polygon — for each polygon size, which sequences of vertex types can appear around it, given that the two classes must both occur and that each is a fixed species. That is a finite case analysis of exactly the kind the parity argument is, and very much longer: the parity argument asks one question of one graph, and Krötenheerdt’s asks a family of questions about rings.

The same programme has been carried further since — three-uniform, four-uniform, and on — and the counts grow (61, 151, 332 …) with no formula and no pattern anybody has found. Each is an enumeration by case analysis, checked by construction, and each is a paper.

That is the honest position of this question in this collection. It is not open in the sense of unsolved; it is closed in the literature by an argument this collection has not reproduced, and it does not print counts it has not produced. The distinction is the whole of the site’s rule about enumerating rather than quoting, applied to a case where the enumeration is hard, and it is worth applying there rather than only where it is easy.

Where the exactness stops #

Computed here: the twenty-one species and the two hundred and ten unordered pairs; which pairs share a polygon size; the parity graph of each odd polygon size for each species and for each pair’s union, with the bipartite test on all three; the tally of pairs the argument kills, the pairs it does not, and the pairs it once killed and no longer does; and, for one pair, forty growths from random choice vectors with the legality, the species content and the periodicity of each.

The parity test is a test on a graph, not on a tiling. A non-bipartite union says the odd walk is not forbidden, which is not the same as saying it occurs. Every pair the argument fails to kill is a pair about which nothing has been established in either direction — that is what “the refutation is absent” means, and it is why the number of surviving pairs is not a count of anything.

Forty growths is forty growths. That none is periodic is a measurement of this search at this radius from this seed, and it establishes that a random search does not find these tilings rather than that no search does. The stronger claim — that they are rare among choice sequences in a way that no sampling reaches — is an explanation offered for the measurement and not a theorem.

And the twenty is not here. This essay does not enumerate the two-uniform tilings, does not claim a number for them, and does not claim that twenty is wrong. What it establishes is why the count is not available by the route that produced the eleven, which is a smaller and firmer thing.

Where the ladder goes next #

Back, to the count this one cannot repeat: twenty-one vertices, eleven tilings, where the parity argument does its work and the grower confirms it, and eleven tilings, five groups, where the eleven are handed to the detector.

Sideways, to the other place a search meets its limit: no procedure decides a tiling, where the general question is undecidable, and surrounded, and still not a tiling, where a bounded search establishes a bound and not a fact.

Onward, to the census that closed and the census that did not, in a different subject entirely: every net with one vertex, where the two-edge family closes in a line and the three-edge family does not — the same distinction between a family a proof shuts and a family an enumeration only reports on.