The cost of proving something false

This collection ranks its answers. A search that returns a lettering has produced a witness anybody can check. A search that runs out of budget has produced nothing. Between them sits the strongest result available, and it is the only negative answer a large pattern admits: a search that exhausts, having visited every possibility its conditions permit and rejected all of them, which is a proof that nothing satisfies those conditions.

The ranking is right, and it has a hidden clause. A proof that nothing satisfies those conditions is a proof about the pattern only when the conditions are the pattern’s. When they are not, an exhausted search produces something more dangerous than a wrong answer: a confident one, arrived at by valid reasoning, with a cost that can be quoted.

This essay is what that costs.

The measurement #

Take a twist tessellation, cut a rectangle of exactly one period, and join its opposite sides so that no crease is divided. Search it for a consistent lettering using the collection’s own condition — the letters point one relation per crease, and a cycle among the relations is a contradiction.

One period: exhausted in three steps. Four periods: thirty-five. Nine periods: three thousand four hundred and fifty-five. Sixteen periods: not finished inside two hundred thousand.

Each of the first three is a closed tree. Each says there is no lettering of that pattern satisfying every vertex condition and having no cycle. Each is correct about that, and each was taken to mean the pattern does not fold.

Against the cost of the answer #

Set the two side by side and the shape is the interesting part.

At one period the proof costs three steps and the witness costs three. At four periods, thirty-five against nine. At nine periods, three thousand four hundred and fifty-five against six hundred and twenty-five. At sixteen periods the proof does not finish and the witness costs fifty-six thousand seven hundred and seventy-two.

Ratios of one, four, five and — at the last size — at least four again, with the proof’s side unfinished.

Being wrong is dearer than being right, and the gap widens. That is not a coincidence and it is not a fact about these patterns particularly. A search looking for something that exists can stop the moment it finds it; a search proving that nothing exists must close every branch, and the tree it must close is the whole admissible space.

The same on the other tilings #

The square tessellation gives the cleanest numbers and the others are more dramatic.

The triangular cell is exhausted in seven steps at one period and twelve thousand one hundred and forty-three at four, while the corrected search finds a lettering in eight and four hundred and fifty-five. The honeycomb is exhausted in seven and nine thousand six hundred and nineteen, against eight and one thousand and forty-three. The elongated triangular tiling is exhausted in three and nine thousand one hundred and twenty-three, against eleven and a hundred and sixty-two.

The rhombille at one period is exhausted in a hundred and eighty-seven and answered in twenty, and at two periods neither search finishes.

So the ratio at four periods runs from about four on the square to twenty-seven on the triangular and fifty-six on the elongated. On patterns with fewer than a hundred panels, being wrong costs between four and fifty-six times what being right costs, and the spread across tilings is itself larger than the growth with size on any one of them.

Why the wrong proof is expensive #

The reason is worth working out, because it is not obvious that a stricter condition should cost more. A stricter condition prunes more, and pruning is what makes a search cheap.

It does prune more, and it prunes the wrong things. The condition rejects a partial lettering the moment its relations contain any loop, and on a glued cell the relations wrap round in both directions, so nearly every partial lettering has one. The tree is therefore closed near its root on most branches, which is cheap per branch — and the branches it does not close are the ones with almost no letters written yet, which are the widest.

The result is a tree that is shallow and enormously broad. The search descends a little way down each of a very large number of branches, finds a loop, and comes back. Nothing is deep and nothing is settled.

A correct condition on the same pattern behaves the other way. It accepts most partial letterings, so the search goes deep quickly, and the depth is what makes progress: writing letters forces more letters, and the propagation settles the sheet. That is why the corrected search finds an answer in six hundred and twenty-five steps where the strict one closes three thousand four hundred and fifty-five and finds nothing.

The shape of the tree #

The claim in the previous section can be made concrete on the two-period cell, which is small enough to describe.

Sixteen vertices, thirty-two creases, four labellings admitted at each vertex. The propagation from any single letter is vigorous — writing one letter settles most of the sheet, because a four-entry table narrows to one entry as soon as one of its creases is known.

So the tree the search walks is not wide because the pattern is unconstrained. It is wide because the search keeps arriving at a fully propagated lettering, being told by the loop test that it is impossible, and going back to try a different early choice. Thirty-five steps on a pattern with, at most, a handful of genuine branch points.

The correct search on the same pattern takes nine, and five of those nine are the ones where the loop test objects and the fuller decision has to be consulted. The other four are ordinary propagation. Nine steps is what the pattern costs; thirty-five is what the wrong question costs.

What a closed tree is worth #

The ranking this collection uses is not wrong and it is worth restating carefully, because a reader could take the wrong lesson.

An exhausted search is the strongest result available, and it remains so. What the ranking does not say — and never said out loud — is what the result is a proof of. It is a proof that no assignment satisfies the conditions applied. Whether that is a statement about the pattern depends on whether those conditions are necessary for the pattern to fold, and necessity is established outside the search, in the mathematics.

Three of the four conditions here are about a single vertex and are unimpeachable. The fourth is about the sheet, and it is a condition for a disc. Applying it to a sheet with no edge is not a bug; it is an unexamined hypothesis, and the search cannot examine it because the search’s job is to apply conditions rather than to justify them.

Where this sits among the collection’s negatives #

It is worth placing this result against the other negatives here, because they are not all of one kind and the differences matter.

A genuine hard negative: nine patches over a grid of construction parameters have no consistent lettering at all, and proving it takes fifteen steps under one branching rule and half a million under another. That is a real property of those patterns, established against conditions that are all necessary.

A negative that is really a budget: a search that stops at two hundred thousand steps has said nothing, and is reported as unfinished. The rhombille at two periods is in this category under both conditions.

A negative against a condition that is too strong: this essay. The tree is genuinely closed, the reasoning is valid, and the conclusion is false because one of the conditions is not necessary for the pattern in question.

The three are easy to tell apart once the possibility of the third is admitted. What made it invisible for so long is that nothing in the collection had ever produced one, because every pattern it searched was a disc and on a disc all four conditions are necessary.

The cost was itself the warning #

There is a reading of these numbers that would have raised the question earlier, and it is worth recording as a habit rather than as a reproach.

Three steps, thirty-five, three thousand four hundred and fifty-five. That is a growth rate of roughly a hundredfold per size, on a pattern whose panel count is going as four, sixteen, thirty-six. A search whose cost grows that much faster than its object is a search doing something structurally different from reading — and on every other pattern in this collection the same search reads.

The clipped patch of the same rectangle costs five, thirteen and thirty steps at those sizes. Sixty per cent of a step per panel, at every size, on every tiling. So the same drawing gave one search a linear cost and another a hundredfold growth, and the difference was a boundary.

That is not proof of anything on its own — some patterns are genuinely hard, and hardness is about the worst instance rather than the typical one — but it is the shape that ought to prompt the question what exactly is this search proving, and the question turned out to have an answer.

A negative is worth two positives, and costs more than both #

The asymmetry between proving and finding is a familiar one here, and this is the sharpest instance of it.

A no costs more than a yes because a yes needs one branch and a no needs all of them. The cost of a negative is two to the power of how many free choices sit above the contradiction, which is why two branching rules can differ by five orders of magnitude on the same twelve patterns.

Both of those are about honest negatives. What this essay adds is that the asymmetry applies to dishonest ones too, and applies harder: a condition that is too strong closes branches that should have stayed open, which means the tree it closes is a tree the pattern never had, and its size is set by the wrong condition rather than by the pattern’s own structure.

So the price of an over-strong condition is paid twice. Once in the wrong answer, and once in the work done to reach it.

Why the spread across tilings is so wide #

Four on the square and fifty-six on the elongated is a large disagreement for four objects built by one construction, and it has an explanation worth having.

The two costs are governed by different things. The witness cost is governed by how much the propagation settles, which is much the same on all five tilings because their vertices all admit four labellings. The proof cost is governed by how many branches the loop test closes before the propagation has done anything, which depends on how the relations wrap — and that depends on the shape of the period.

The elongated tiling’s period is a rectangle nearly four times as tall as it is wide, so its relations wrap much more readily in one direction than the other, and the loop test fires very early on almost every branch. The square’s period is square, and the two directions are balanced.

So the ratio is measuring the geometry of the repeating cell rather than anything about how hard the pattern is, which is another way of saying that the number being quoted is a property of the mistake and not of the paper.

What to do about it #

The practical response is the arrangement described in the essay about pruning on proofs alone: keep the cheap condition where it is sound, and consult the expensive one only where the cheap one objects. That makes the search correct at a cost that is measured and printed rather than hidden.

The methodological response is smaller and more useful. An exhausted search should be reported as what it is: this rule found nothing, in this many steps. Not the pattern has no lettering. The two are the same statement when the rule is right, and only the first of them is ever established by running a search.

Every figure in this thread reports it that way now, which is why the middle column of the verdict figure says nothing, in thirty-five rather than none.

A result that was never published, and one that was #

Nothing in this collection ever printed a claim that a twist tessellation has no consistent lettering, because the object these proofs are about could not previously be built. So there is no retraction owed and no number to withdraw.

What was printed, and stands, is an open verdict on three rhombille patches at a shallow turn — patches with a rim, cut out of the plane in the ordinary way, where the same condition is necessary and the exhaustion is honest. Those three were later settled in the negative, and the settlement is as good as it ever was.

The distinction between those and these is exactly the distinction this essay is about, and it is not a matter of degree. On a disc, a cycle in the layer relations is a contradiction and an exhausted search is a theorem. On a sheet with no edge it is neither. Every negative the collection has published is of the first kind, and every negative in this essay is of the second, and the two look identical in every output either search produces.

That is the reason the reporting changed rather than the mathematics: a closed tree now says which rule closed it.

Which theorem was checked, and how #

The exhaustion is real and is checked by the search reporting the difference between running out of budget and closing its tree. A run that hits the budget is drawn and described as unfinished; a run that closes is described as a proof. The two are never conflated, and on the largest cells here the honest answer is the first.

The falsity of what is proved is established elsewhere, by a witness. The corrected search’s lettering is written onto ordinary clipped patches and handed to the four vertex conditions and a folded sheet rebuilt from scratch, and every check passes at every size on four tilings. A proof and a counterexample cannot both stand, and the counterexample is the one that survives contact with machinery that knows nothing about where it came from.

The costs are measured under a fixed letter order rather than a randomised one, so a number quoted here is the number that pattern gives every time rather than one sample from a distribution — which matters, because a randomised order manufactured a heavy tail on these very patterns and the tail was mistaken for a property of the paper.

The honeycomb, which is the other extreme #

The elongated tiling gives the widest gap between the two costs and the honeycomb gives one of the narrowest, and the pair brackets the range.

The honeycomb’s glued cell at one period is exhausted in seven steps and lettered in eight — a ratio of about one, so at that size being wrong and being right cost the same. At four periods it is nine thousand six hundred and nineteen against one thousand and forty-three, a ratio of nine. At nine periods neither search finishes.

So the penalty for the wrong question is not a constant of the mistake. It grows with the object, from nothing at the smallest size to a factor of nine at the next, and the growth is faster on tilings whose repeating cell is far from square.

Two readings follow, and the second is the useful one. The obvious reading is that a small pattern is a poor place to notice this, since at one period the two answers cost the same and only their verdicts differ. The better one is that the verdict is the thing to look at rather than the cost: at one period the honeycomb’s two searches take seven and eight steps and reach opposite conclusions, which is as clean a disagreement as this collection has ever produced and would have been visible the first day the object existed. The cost is what makes the mistake expensive; it is not what makes it detectable.

What the picture cannot show #

A bar chart of exhaustion costs is a chart of a quantity that ought not to exist. The honest picture would be empty, because the right answer at every one of those sizes is a lettering rather than a proof, and the bars measure work done in the wrong direction.

Nor does the growth rate say what the cost would be at sizes past sixteen periods. The search does not finish there under either condition, and a curve fitted to three points and an inequality is a curve fitted to three points.

And nothing here can be drawn about the patterns where the question is still open. The rhombille at two periods and above exhausts nothing and finds nothing under either condition, so there is no proof to price and no witness to check — an absence that is neither of the two columns in any figure, and the honest place for the tiling that has been the exception to every measurement in this thread.