Pruning on proofs alone

A backtracking search has one rule it may not break. When it abandons a branch it must be certain the branch contains nothing, because everything it says afterwards — including this pattern has no consistent lettering, which is the most valuable thing it can say — rests on having looked everywhere it did not prove empty.

That rule is easy to keep when the test at each node is cheap and exact. Ask whether the letters so far contain a contradiction; if they do, the branch is empty and closing it is sound. This collection has done exactly that from its first search: the letters point one relation per crease, a cycle among those relations is a contradiction, and finding one costs a single pass — which is what makes it the only negative answer available on a pattern of any size.

On a sheet with no edge the test is no longer exact, and keeping the rule takes an arrangement.

What went wrong with the cheap test #

The relations a lettering forces are a partial order in the making, and a cycle in them means the order is impossible — for a sheet with finitely many panels. A periodic pattern has infinitely many, arranged in copies of one period, and what can be written down is a quotient in which each relation carries the lattice step it takes. A closed walk in that quotient is a contradiction only if its steps add to nothing, and a walk that ends one cell over is a stack with no bottom rather than an impossibility.

So on a glued cell the one-pass test rejects letterings that are perfectly good. Used as a prune it breaks the rule above, and the consequence is exactly the one the rule exists to prevent: the search closes a tree that had an answer in it and reports a proof that there is none.

That happens in thirty-five steps on the two-period square cell, and the lettering it proves impossible turns out to fold on every finite patch it is written onto.

The two tests #

The correct test asks whether some closed walk’s lattice steps add to zero, and it is much dearer than one pass.

There is no single direction that settles it. The relations have to be taken apart: choose a direction in which no walk descends, discard the relations with room to spare under it — none of them can be part of a zero-summing walk — and ask the next direction of what is left, which has by then split into smaller pieces. Two or three directions empty every cell here, and each direction needs a shortest-path computation over the whole relation graph.

But the cheap test is sufficient. A lettering with no loop at all in its quotient has no loop in the pattern either, because a loop upstairs projects to a closed walk down here. So acyclic implies consistent, and only the converse fails.

That is the shape that makes the arrangement possible. Ask the cheap question first; if it says yes, the branch is fine and nothing more is needed. If it says no, the branch might still be fine, and the expensive question has to be asked.

What is actually pruned #

The search discards a branch only when a closed walk with zero net step has been found — an explicit chain of relations returning to the panel it left, in the same copy of the period.

Anything else is kept. A lettering with loops that all travel is kept because it is fine. A lettering with loops that nothing proves either way is also kept, which is the conservative choice and the one that preserves the rule: pruning on an unproved contradiction would make the search incomplete again, in the other direction and for a subtler reason. It is the same discipline that makes an exhausted search worth more than a search that stopped, and that the order proving nothing exists depends on entirely.

So the prune is sound by construction. Every branch closed contains nothing, and a search that exhausts really has proved something.

What the arrangement costs #

The expensive test runs only on what the cheap one rejects, and the proportion is worth reporting because it is not small.

On the one-period square cell, three steps and the expensive test is reached at all three. On the two-period cell, nine steps and five. On the three-period cell, six hundred and twenty-five steps and five hundred and sixty. On the four-period cell, fifty-six thousand seven hundred and seventy-two steps and fifty thousand five hundred and forty-six.

Eighty-nine per cent at four periods, and rising. The reason is structural: on a glued cell the relations wrap round, so almost every partial lettering has a loop somewhere, and the cheap test’s yes becomes rare as the cell grows.

The four numbers are worth reading as a curve rather than as four measurements. The fraction of steps needing the expensive test runs 100%, 56%, 90%, 89% — noisy at the smallest sizes, where three steps and nine steps are too few to mean much, and settling near nine-tenths.

Nine-tenths is a statement about glued cells and not about the arrangement, and it is the honest cost of being right on this object. A cell whose relations wrap is a cell most of whose partial letterings have a loop, and there is no cheap sound test that can tell those loops apart — which is why the expensive one exists.

Why the cheap test is worth asking anyway #

Eighty-nine per cent sounds like a reason to drop it, and it is not, for two reasons.

The eleven per cent it settles are settled at a hundredth of the price, so the saving is real even at that ratio. And more importantly, the proportion is a measurement of the object rather than of the arrangement: it says that a glued cell is a pattern in which nearly every partial lettering has a loop in its quotient, which is precisely why the old test was so badly wrong here.

On an ordinary patch the proportion runs the other way. A cut sheet’s relations peter out at the rim rather than wrapping, so most partial letterings are acyclic and the cheap test answers nearly everything — which is why nobody had ever needed the expensive one.

The number is therefore worth printing next to the cost rather than hidden inside it, and every figure here that reports a search on a glued cell reports it.

The window, and what it does not prove #

There is one more piece of honesty owed about the prune, and it concerns how a zero-summing walk is looked for.

The relations, lifted back to the pattern, live on the panels of every period; a walk that returns to its starting panel in its starting copy is what the prune wants. Searching all of them is searching an infinite graph, so the search inside the tree looks within a bounded window — the copies within one step of the origin in each direction — and reports a walk if it finds one there.

That is sound: a walk found in the window is a walk. It is not complete: a walk wandering further before returning would be missed, and the branch would be kept rather than pruned. Which is the right side to err on. A missed contradiction costs a branch that is explored and turns out empty; a false one costs an answer.

The verdict on a finished lettering uses a wider window and the full direction-by-direction argument, because there the answer matters and the cost does not.

The other order, and why it is wrong #

There is an obvious alternative arrangement and it fails in an instructive way: ask only the expensive test, and skip the cheap one.

It gives the same answers. It is sound, complete, and slower by whatever the cheap test would have saved — but the real objection is different. The expensive test’s answer is three-valued: a zero-summing walk found, a certificate that none exists, or neither, which is a statement about the procedure rather than about the pattern. A search whose prune sometimes returns unknown has to decide what to do with it, and every choice is bad. Treat unknown as a contradiction and the search is incomplete; treat it as fine and the search may return a lettering that does not fold.

Asking acyclicity first removes most of the occasions on which the question comes up at all, and makes the remaining ones visible as a count. That is a better arrangement than one which is simpler to describe.

The cheap test, kept honest #

There is a second reason for the ordering that has nothing to do with cost.

The cheap test is the collection’s own, unchanged. It is the same one-pass reader that proves a pattern has no folded state in one sweep and that every essay about a disc relies on. Keeping it in place, in front of the new machinery, means that on any pattern where the old reasoning is valid the search behaves exactly as it always did — the expensive test is never reached, because acyclicity never fails on a lettering that is fine.

So the arrangement is not a replacement. It is the old test with a second opinion attached, consulted only where the old test’s hypothesis does not hold, and that is the shape a correction of this kind should have.

Where the search still stops #

The arrangement makes the search correct and does not make it cheap, and two of the five tilings say so.

The triangular and honeycomb cells at three periods, and the rhombille at two, do not finish inside two hundred thousand steps under either test. The counts of expensive calls on those runs are a hundred and eighty-eight thousand, a hundred and ninety-four thousand and a hundred and eighty-six thousand — so nearly every step is paying full price, and the search is exploring rather than reading.

Those are reported as unfinished rather than as costs. A search that hits its budget has learned nothing about the pattern, and the distinction between that and an exhausted tree is the whole subject of this thread.

What a wrong prune actually looks like #

It is worth being precise about the failure this arrangement prevents, because it does not look like a failure from inside.

A search pruning on the cheap test on a glued cell does not crash, does not slow down, and does not report anything unusual. It runs quickly — thirty-five steps rather than nine — closes every branch, and returns the strongest kind of negative result the collection knows how to produce. Every intermediate state it passes through is a state some correct search could also have been in. The only thing wrong is the conclusion.

That is why the rule is a rule rather than a preference. A prune that is merely usually right produces answers that are usually right, and usually right is exactly the property an exhausted search is supposed not to have. The whole value of a closed tree is that it is not a sample.

And the failure is not detectable from within the search at any cost. Nothing about a branch says whether the thing that closed it was a proof; that is a property of the test, established once, outside. Which makes the argument that acyclicity implies consistency load-bearing in a way no amount of testing could replace.

What this is an instance of #

The general shape is worth naming because it recurs whenever a test is corrected rather than replaced.

An old test $A$ is cheap and sound in a restricted setting. A new test $B$ is correct everywhere and expensive. If $A$ implies $B$ — if everything $A$ accepts is genuinely fine — then $A$ can be kept as a fast path and $B$ used only where $A$ objects, and the combination is exactly as correct as $B$ and nearly as fast as $A$ wherever $A$’s setting holds.

The condition is the implication, and it has to be argued rather than hoped. Here it is one line: a loop in the pattern projects to a closed walk in the quotient, so no loops in the quotient means no loops in the pattern. If the implication had gone the other way, or neither way, the two tests would have had to be run independently and compared, which is the arrangement the collection uses where two instruments genuinely disagree.

The variable order, which is untouched #

One thing this arrangement deliberately does not change, and it is worth saying so because the two questions are easy to confuse.

A backtracking search makes two choices at every node: which crease to decide next, and which letter to try first. Both have been examined here, and the second turned out to be where a heavy tail was manufactured. Neither is what this essay is about.

The prune is a third thing entirely: given a partial lettering, is this branch empty? The two order questions decide how the tree is walked and the prune decides how much of it exists, and a change to the prune leaves both orders alone. Every number here is measured under the same fixed letter order the rest of the collection uses, precisely so that the comparison between the two prunes is a comparison of prunes.

That separation matters because the wrong prune is faster. Thirty-five steps against nine on the two-period cell, and a search that closed its tree quickly would look, on any measurement of speed alone, like the better arrangement.

Which theorem was checked, and how #

The soundness of the prune is checked by construction rather than by measurement: the only thing that closes a branch is an explicit closed walk with zero net step, found by walking the relations, and such a walk is a contradiction by definition.

The completeness is checked by the witness. A search that pruned wrongly would return a lettering that does not fold, or exhaust a tree that had one in it, and both would show on the ordinary patches the periodic lettering gets written onto: every vertex condition holds and no patch has a loop, on four tilings at three sizes — and would have shown at once, since a wrongly pruned search on a glued cell exhausts rather than returning anything at all, which is the failure mode that started this thread.

And the machinery is fed something it must refuse. Two panels with one relation each way, neither leaving its own copy of the period, is a loop that genuinely closes; the decision has to call it a contradiction, and it does. Without that, every verdict came back fine would be a statement about a function that says fine to everything.

A second thing the arrangement makes measurable #

The letterings the corrected prune lets through are worth one more question, and it is one only the finished witness can answer.

A patch of the pattern has a bottom layer — some panel with nothing under it — and the pattern itself has none, because every loop in its relations travels. So on a patch the minimal panels ought to be at the rim and nowhere else, and that is a prediction the prune’s own reasoning makes about paper.

On twelve patches over four tilings, from twenty-five panels to seven hundred and ninety-three, every panel with nothing below it touches the paper’s edge. A single one in the interior would mean either the transfer put a letter somewhere it does not belong or the loops do not all travel after all, and neither shows.

What the picture cannot show #

A count of how often the expensive test was reached is a count of calls, not of time, and the two are not proportional: an early call on a nearly-empty relation graph is much cheaper than a late one on a full one. So the eighty-nine per cent is the right number for what fraction of the search’s decisions needed the second opinion, and the wrong number for what fraction of the seconds went to it.

Nor does any figure here show a branch that was kept because nothing could prove it wrong. Those are invisible by construction — a branch the search declines to close simply continues — and the only trace they leave is a search that costs more than a bolder one would.

And no picture distinguishes a search that is correct from one that merely got the right answer. The two runs on a two-period square cell differ in nine steps against thirty-five, and the cheaper of them is the wrong one — a fact no drawing of either search would reveal, and one that only shows when the answers are taken outside and checked.