The order that proves nothing exists

A search that finds something hands over an object. A search that finds nothing hands over an assurance that it looked everywhere, and the assurance is worth exactly as much as the looking was thorough — which is why a no is a different kind of answer from a yes and not merely its opposite.

It is also a different kind of cost. A yes costs the length of one path down the tree. A no costs the whole tree, and the whole tree is not a fixed object: its size depends on the order the search takes its decisions in, and that dependence turns out to be four orders of magnitude wide.

Twelve patterns with nothing to find #

Sweeping the twist tessellation construction over a grid of tiling, turn angle and pleat width produces patches that are perfectly good crease patterns — every vertex satisfies Kawasaki, every vertex has admissible labellings, the panels close — and that admit no lettering whose arcs avoid a circle. Nine of them are on the four tilings whose vertices are all alike; three more are on the rhombille, whose vertices are not.

Every one of the twelve is at a shallow turn and a narrow pleat, and none is on the square tiling. That is not a coincidence and it is not new: the smallest sector at a vertex changes identity as one sector crosses sixty degrees, which swaps the pair of creases the big-little-big lemma forces apart, and the square patch has no sixty degrees to cross. What is new is that the phenomenon has an extent rather than a threshold — a region of the construction’s parameters rather than a point on one dial.

Proving any of it requires exhausting a search, and that is where the cost lives.

Fifteen steps, on nine of them #

Under the standard branching rule — decide the vertex with the fewest labellings left — the nine uniform patches are refused in fifteen steps each. Every one of them, at sixty-two to eighty-three panels, at a hundred and six to a hundred and forty-two creases. Fifteen.

That is cheaper than any witness anywhere in the collection. A patch with a lettering costs twenty-one to forty-seven steps to find it; a patch with none costs fifteen to prove it. The famous asymmetry runs the other way here, and the reason is that the propagation reaches the contradiction almost immediately: a few forced letters, a vertex with no surviving labelling, and the search is finished before it has really started.

Half a million, on three of them #

Under exactly the same rule, three rhombille patches at a shallow turn cost 255,999, 511,999 and 255,999 steps. Same construction, same conditions, same code, and four orders of magnitude more work to reach the same kind of answer.

Those are the three patches that an earlier reading left open, because two hundred thousand steps was not enough to settle them and a budget that runs out is neither a witness nor a proof. They are settled now, and the answer is no: the rhombille tessellation at a turn of 0.15 or 0.25 radians with narrow pleats has no lettering that agrees with itself.

Look at the numbers rather than the verdict, though, because they are shaped, and they are shaped in two different ways. Four of the exhaustions on the grid are 2,047, 16,383, 32,767 and 524,287 — which are 2¹¹ − 1, 2¹⁴ − 1, 2¹⁵ − 1 and 2¹⁹ − 1 exactly. A fifth is 879, which is not a power of two less one at all. And 255,999 and 511,999 are one short of 256,000 and 512,000, which are round numbers in base ten rather than in base two: 2¹⁸ − 1 is 262,143, and no rounding turns it into 255,999.

The cost of a no is a power of two #

A number of the form 2ⁿ − 1 is a complete binary tree of depth n, and that is precisely what the search is doing. It has found a set of decisions that do not interact — creases whose letters the propagation cannot connect to one another — and it is enumerating every combination of them before reaching the vertex that refuses.

The contradiction is somewhere in the pattern, waiting. If the branching rule reaches it early, the refusal happens at the root and costs fifteen steps. If the rule leaves nineteen independent free choices above it, the search visits every one of the 524,287 combinations of those choices and rediscovers the same contradiction at the bottom of each.

So the cost of proving a negative is not a property of the pattern and not a property of the rule. It is a property of where the rule puts the contradiction in the tree it builds, and the exponent is a count of the free decisions the rule stacks on top of it.

Three shapes, and only one of them is a proof #

Those three shapes are distinguishable, and telling them apart is worth doing before reading any of the counts as evidence.

A full binary tree. Exactly $2^{n}-1$ nodes means the search made $n$ free decisions and pruned nothing anywhere above the contradiction. Four of the counts have this shape, and for those the account in the next section holds exactly: the exponent is a count of independent free choices stacked over the refusing vertex.

A pruned tree. 879 is not $2^{n}-1$ for any $n$; the nearest is 1,023 at depth ten, so the search visited 86 per cent of a full tree of that depth and the propagation cut the other fourteen. That is the only one of the seven where a branch was closed early, and it is the interesting one rather than the anomaly — it shows the propagation can prune, which the four clean powers of two do not.

A round decimal number, less one. 255,999 and 511,999 are one below 256,000 and 512,000. Nothing about a binary search tree produces a multiple of a thousand. What does produce one is a budget expressed in round numbers, stopped one step before its limit.

Which two counts need re-deriving #

That last shape is the one to be careful with, because the two numbers carrying it are the two the essay’s headline rests on.

A count that stops one step short of a round budget is the signature of a search that ran out, and a search that runs out is the third outcome — neither a witness nor a proof. A count that is $2^{n}-1$ is the signature of a tree that was finished. The two are not hard to tell apart and they license completely different sentences.

The verdict on those three rhombille patches may well be right; the structural rule settles them in sixty-three steps apiece, and sixty-three is $2^{6}-1$, which has the shape of a completed tree. That is the count doing the work, and it is a proof on its own.

What the 255,999 and 511,999 figures should be read as is the standard rule failing to finish on patterns the structural rule finishes easily — which strengthens the essay’s actual thesis rather than weakening it, since the whole point is that the two rules swap places. A rule that runs out of budget where another rule needs sixty-three steps is a sharper illustration than a rule that took four thousand times as long and got there.

Either way the number should be re-derived under a raised budget before it is quoted as a tree size, and the shape of the number is what says so.

Neither rule is the good one #

Branching on the creases that lie on many independent circuits settles the three rhombille patches in sixty-three steps apiece, against 255,999 and 511,999 for the standard rule. Four thousand times cheaper, and it is not a lucky seed: the search is deterministic and sixty-three is what it costs.

On the nine uniform patches the same rule costs 879, 2,047, 16,383, 32,767 and 524,287 against the standard rule’s fifteen. Up to thirty-five thousand times more expensive, on patterns of the same family that are refused for the same reason.

The two rules therefore swap places, and the swap is what stops this being a recommendation. Had only the rhombille patches been measured, the structural rule would read as a decisive improvement to be adopted everywhere. Had only the uniform ones been measured, it would read as a curiosity that makes things worse. Both readings are available from real data and both are wrong, and the only thing that separates them is having asked more than one kind of pattern.

Why aiming at circuits can miss #

The structural rule aims where a circle would be, and on the nine uniform patches the contradiction is not a circle at all.

That is the mechanism, and it is worth being exact about. There are two ways this search can refuse. The vertex conditions can leave some vertex with no admissible labelling, which is a local refusal; or the arcs can close a circle, which is a global one. The distinction has its own measurement, and on the patches where the search succeeds it comes out entirely one way: the vertex conditions dead-end a search zero times and every backtrack is the arcs.

On the twelve negatives it comes out the other way. The refusal is a vertex with nothing left, reached by propagation, and a rule aimed at circuits is aiming at the wrong thing — it branches on creases far from the vertex that will refuse, and every one of those branches is a free choice stacked above the contradiction. The rule is not merely unhelpful. It is actively building the tree that the exponent counts.

On the rhombille the situation reverses, because there the propagation does not reach the refusing vertex quickly and the contradiction really is distributed across the circuits.

The same shape, in the machinery that drew the patterns #

There is a second instance of this, and it was not looked for. It turned up as a delay.

The construction that draws these patches does not state their letters — it finds them, by the same propagate-and-branch arrangement, because the assignment most people would draw for a named base cannot fold flat and a construction that asserted an assignment would be asserting the thing it was meant to establish. On every patch the collection prints, that search is instant.

On the rhombille at a shallow turn and a narrow pleat it takes six and a half minutes, for a pattern of two hundred and seventy creases. Not to search for a consistent lettering — merely to find an assignment satisfying the vertex conditions, which exists and which the search does eventually return.

The shape is the same one: a search whose contradictions sit below a stack of free decisions, on the same family, at the same end of the same parameter. The difference is that this one has no coin in it — it already tries one letter first, always — so its cost is entirely in its variable rule, which is the standard one.

The reason it stays as it is, rather than being reordered, is that the assignment it returns is the pattern — every twist tessellation figure in the collection carries the letters this search found, and a different order would return a different, equally valid assignment and redraw every one of them. A six-minute construction is a price worth paying to leave a published drawing alone.

What a negative here is worth #

A completed exhaustion is a genuine proof of absence, and it is worth restating what it is a proof of.

It proves that no assignment of mountains and valleys to that pattern’s creases satisfies Kawasaki, Maekawa and the big-little-big lemma at every interior vertex while forcing no circle in the arcs. It does not prove the pattern has no flat folded state by some other route, because there is no other route: those conditions are necessary, so a pattern failing all of them fails. It also does not prove anything about a pattern with slightly different parameters — a near miss is nearly as rare as a hit, and the grid is a grid rather than a continuum.

What makes the proof trustworthy is not the count of steps. It is that the search reports three outcomes and not two: a witness, an exhaustion, and a budget that ran out — and the third is reported as neither of the others. The three patches above sat in the third category for a long time, correctly, and moved to the second only when a rule was found that could finish.

Which theorem was checked, and how #

Every verdict here is checked under more than one order. An exhaustion visits the entire tree, so two orders that both finish must agree, and that agreement is asserted across the grid rather than assumed — an ordering rule that changed a verdict would mean the search was not exploring what it claims to explore.

The claim that survives is narrow and it is checked in both directions at once: on a pattern with a lettering the structural rule is never cheaper, and on two patterns with none the two rules swap places by more than a hundredfold each way. Either half failing would mean the account above is wrong, and both are stated as requirements rather than as observations.

Two ways of being sure, and only one of them scales #

It is worth putting this beside the other way the collection establishes an absence, because the two are unalike in a way that matters.

The sampler draws letterings that pass every vertex condition and tests each for a circle afterwards. Two thousand draws on the rhombille produced none, and the honest reading of that was a nought of two thousand draws and not a proof — because a set can be non-empty at any density, and a sampler measures density.

An exhaustion is categorical. It visits every lettering the conditions admit, so nothing is left for a larger sample to find, and its answer does not improve with more work because there is no more work.

The catch is that an exhaustion has a cost that can be a power of two, and a sampler’s cost is linear in how many draws are asked for. So the categorical instrument is the one that can fail to finish, and the approximate one is the one that always answers — which is the reverse of the usual arrangement and is why both are kept.

What the picture cannot show #

A step count is a count of decisions, not of seconds. Each node runs the vertex conditions to a fixed point and tests the arcs, and both cost more on a large pattern — so 524,287 steps on a seventy-seven panel patch and 511,999 on a hundred and fifty-five panel one are not the same amount of work despite being similar numbers.

And the twelve negatives are twelve, which is not many. They are all produced by one construction, at the shallow end of one parameter, and the confident version of the finding — proving a negative costs two to the free choices above the contradiction — is a mechanism supported by five exact powers of two rather than a law. What would test it is a family of patterns where the contradiction can be moved deliberately, and building one is straightforward and has not been done.

What it costs a reader to know this #

Very little, and the little it costs is the interesting part.

A reader who wants to know whether a tessellation patch folds flat now has a procedure that returns one of three answers rather than two, and the third answer — this was not settled inside the effort spent — is one they have to be willing to accept. That is not a weakness of the procedure. It is the honest shape of a question that is NP-hard in general, and an instrument that always returned yes or no would be an instrument that was lying about one of them.

What the reader gains is that the third answer is now rare and identifiable. Twelve of a hundred and twenty patches have no lettering; every one of the remaining hundred and eight has one, found in under ninety steps; and the only cases that ever needed a large budget were three patches on which a second branching rule finishes in sixty-three. The undecided category, on this construction, is currently empty.

Where the ladder goes next #

Two things follow. The region these twelve sit in is a region rather than the single threshold it was first found as, and its boundary is a fact about sectors rather than about searches. And the population they were found in was assembled deliberately, which is the first population here that a construction did not hand-pick — and the reason the twelve were found at all.