The cost of asking the wrong sheet

The expensive way to be wrong is to be wrong slowly and confidently, and this collection has a worked example with numbers on it.

The test #

A lettering of a crease pattern is consistent when the relations it forces — this panel lies over that one — have no cycle in them. A cycle is a contradiction: a stack of paper in which each layer is above the next and the last is above the first.

Checking for one is a single pass over the relations, it is cheap, and it is sufficient. So it is asked first at every node of a search, and almost every node it settles.

That test is correct for a sheet with an edge. On a sheet whose opposite edges are the same edge it is not, and the reason is that the relations on such a sheet carry a lattice step: a chain of relations that returns to the panel it started from, one cell over, is not a cycle at all. It is a stack of paper with no bottom layer, which is a perfectly ordinary thing for a sheet with no edge to have.

What running it costs #

Running the disc’s test on a glued sheet does not produce an error. It produces a proof.

On the square twist tessellation’s glued cell it exhausts — establishes that no consistent lettering exists — in three nodes at one cell, thirty-five at four, and three thousand four hundred and fifty-five at nine. At sixteen cells it does not finish inside a budget of two hundred thousand.

Every one of those is a completed exhaustive search whose conclusion is false.

Being wrong costs more than being right #

The comparison is the point of the essay.

Under the correct test the same cells settle in three, nine, six hundred and twenty-five and fifty-six thousand seven hundred and seventy-two nodes, each time with a witness.

Under the disc’s test they exhaust in three, thirty-five, three thousand four hundred and fifty-five, and more than two hundred thousand.

At one cell the two agree, because at one cell there is nothing to be wrong about. At four cells the wrong test costs four times the right one. At nine it costs five and a half times. At sixteen the right test finishes and the wrong one does not.

That is not a coincidence. A test that rejects too much prunes too much, and a search that prunes correctly finds a witness early and stops. A search that prunes wrongly finds no witness and has to look everywhere, which is the expensive branch by construction.

So the penalty for a wrong necessary condition is not a constant factor. It converts every instance into a worst case.

The letterings it proved impossible #

The other half of the check is what makes the conclusion safe, and it is worth doing in full.

A lettering that the correct test accepts is written back onto ordinary clipped patches of one, four and nine cells and handed to the collection’s own checkers — the ones that read vertices and look for forced loops, and that have never heard of a glued sheet.

It passes every vertex condition and forces no loop, on four tilings, up to one thousand five hundred and twelve creases and seven hundred and twenty vertices.

So the disc’s test was not merely expensive on those sheets. It was wrong, and the thing it was wrong about was available to be checked by machinery that already existed.

Why acyclicity is right on a disc #

It is worth being clear about what the disc’s test gets right, because the repair is narrow and the test is not being discarded.

On a sheet with an edge, the relation this panel lies over that one is a partial order on the panels, and a partial order has no cycles. That is not an assumption; it follows from the panels being real pieces of paper stacked in a real order, and the bottom of the stack is a panel with nothing below it, which exists because the paper has an edge for it to be at.

So on a disc, a cycle in the relations is a contradiction, and looking for one is a complete test of consistency.

On a sheet with no edge there is no bottom panel — an order with no least element is still an order — and the relations are not a partial order on the panels of the quotient. They are a partial order on the panels of the cover: infinitely many copies, arranged in a stack that goes on for ever in both directions.

A chain of relations returning to the same panel of the quotient one cell over is a chain in the cover that climbs one step and does not return. That is not a cycle upstairs and it is not a contradiction, and the disc’s test cannot tell it from one because it never had a step to read.

What the corrected test asks #

The replacement is one sentence longer and it is worth stating, since reads the lattice steps is doing a lot of work above.

Every relation on the quotient carries the lattice step it takes: the panel it points to is the same panel of the pattern, some whole number of cells across and up. A chain of relations therefore has a total step, obtained by adding.

A contradiction is a closed chain whose steps add to nothing. That is a genuine cycle: the same panel, in the same place, above itself.

A chain that closes on the quotient with a nonzero total step is not a contradiction. It is a stack that climbs, and a stack that climbs is exactly what an infinite sheet with no bottom looks like.

So the corrected test is: find a closed walk with zero total step, or prove there is none. That is more expensive than looking for any closed walk, and it is the question the object actually poses.

Where the extra cost goes #

The two-stage arrangement is worth describing because it is what keeps the corrected test affordable.

Acyclicity is asked first. It is one pass and it is sufficient: a lettering whose quotient relations have no closed walk at all certainly has no closed walk with zero step, so it is consistent and no further work is needed. That settles most nodes.

Only the letterings acyclicity rejects reach the second question, which is whether some closed walk actually adds to nothing. On a four-cell object five of nine nodes reach it; on a sixteen-cell object fifty thousand five hundred and forty-six of fifty-six thousand seven hundred and seventy-two do.

That ratio is itself informative. On the large object nearly ninety per cent of nodes reach the expensive branch, which says the cheap test is doing very little pruning there — the letterings that are nearly consistent are common, and telling them apart is the whole of the work.

The search prunes on a proof and on nothing else. A closed walk nobody can prove closes is left alone, because pruning on an unproved contradiction is how a search stops being a search and starts being a guess.

Two other places the same error could live #

Having found the shape twice, it is worth asking where else a disc’s hypothesis might be hiding, and there are two candidates in this collection.

The forced-order test. It looks for the panels with nothing below them and works upward. On a sheet with no edge there are none, and the test’s answer is no valid order rather than no bottom. That has been noticed and it is the subject of its own argument.

The face walk. Building a folded state starts at a panel and walks outward until the panels run out. On a glued sheet they do not run out; the walk is on the cover and terminates only because the cell is finite and the identification is applied afterwards. That one is correct as implemented and it is correct by construction rather than by anybody having checked the hypothesis, which is a weaker position than it sounds.

Neither is a known defect. They are listed because the two found so far were both found by an object arriving rather than by an audit, and an audit is cheap.

How it was noticed #

Not by the cost, which is the uncomfortable part.

A search that exhausts is doing what a search does. It is slower than one that finds a witness, and this instance is hard is the ordinary explanation for a slow search — the collection has written about instances that are genuinely hard and about the cost of proving something false, and both are real.

What noticed it was a disagreement between two verdicts on one object, at a size small enough to check by hand. The glued square cell at one period has four panels and eight creases, and its exhaustion is three nodes long. Reading those three nodes is the work of a minute, and the third one refuses a lettering for a reason that inspection does not support.

That is the general shape of finding this kind of error. A wrong test is invisible in a cost curve and visible in a small case, and it is only visible there if somebody looks at a small case for a reason.

The numbers, in one place #

Because the whole essay is a comparison of two columns, here they are.

Under the disc’s test, on the square twist’s glued cells: three nodes at one cell, thirty-five at four, three thousand four hundred and fifty-five at nine, and no answer inside two hundred thousand at sixteen. Every one of them an exhaustion, and every conclusion false.

Under the corrected test, on the same cells: three, nine, six hundred and twenty-five, and fifty-six thousand seven hundred and seventy-two — each with a witness, and each witness verified on ordinary patches by code that knows nothing about gluing.

The ratio of wrong to right is one, four, five and a half, and then unbounded. It is not a constant factor and there is no reason it should be: the two searches are answering different questions, one of which has an answer and one of which does not.

And the sixteen-cell case is the one to keep. The right test finishes in fifty-six thousand nodes; the wrong one had spent two hundred thousand and was still going, on an object where the answer is a lettering that can be written down.

A general point about necessary conditions #

The essay has a moral that is not specific to folding and is worth stating once.

Search procedures are built out of tests that reject. Each test is a claim of the form no solution has this property, and the search’s correctness depends on every one of those claims being true. Its speed depends on them rejecting a lot.

Those two pull in the same direction right up to the point where a test rejects something it should not, and then they pull apart violently. A test that is slightly too strong makes the search slightly faster on the instances where it is right and infinitely slower on the ones where it is wrong, because a wrong rejection removes the answer and the search then has to exhaust.

So the failure mode of an over-strong test is not wrong answers occasionally. It is the search stops terminating, which reads as the instances having got harder.

That is a genuinely unpleasant property, because this got slow is the symptom of a great many innocent things — a bigger instance, a worse variable order, an unlucky tie-break — and the collection has written about all three. A wrong test hides among them.

What the old numbers are worth now #

A practical question, since the collection published costs measured under the old test.

They are correct as measurements of that procedure and they are not measurements of the objects. A published number of the form this cell exhausts in three thousand four hundred and fifty-five nodes remains true and now means the disc’s test exhausts on it in three thousand four hundred and fifty-five nodes, which is a fact about a wrong procedure.

That is worth keeping rather than deleting, and it is kept: the two tests are both run and both reported, precisely because the comparison is the interesting quantity. A figure showing only the corrected costs would lose the finding.

What has to be avoided is quoting the old numbers as costs of the object, and the fix is to say which test produced them — which every figure here does, and which the essays written before the distinction existed did not, because there was only one test.

What would have caught it earlier #

Two things, and both are cheap.

A witness, checked elsewhere. Every yes this collection produces is written back onto an object built by different code and rechecked. That is what established the corrected test’s answer, and running it on the old test’s rejections would have flagged the problem the first time a glued cell was searched — since the old test rejected letterings the independent checkers accept.

A small case, read. The one-cell glued square has four panels and eight creases, and its exhaustion is three nodes. Reading three nodes takes a minute and the third one is visibly wrong.

Neither was done, and the reason is ordinary: the search agreed with itself, its costs looked like the costs of a search, and there was no external number for it to disagree with.

The collection’s habit of building two computations that share no code exists for exactly this, and it had not been applied to the consistency test because the consistency test was one line and did not look like the sort of thing that needs a second opinion.

The shape of the mistake #

A test imported without its hypothesis is the collection’s name for this and it has now happened twice.

The acyclicity test comes from the layer-ordering literature, where the sheet is a disc. The literature is not wrong; it states its results about the objects it is about. What travelled was the test, and the sentence saying which sheets it applies to did not travel with it, because on a disc that sentence says nothing.

The second instance is the closure condition, which compares a composition against the identity because on a disc the identification is trivial. Same shape, same cause, and the same repair: the constant becomes an argument.

Both were applied for a long time before an object arrived that separated the general case from the special one.

The cost of the repair #

Small, which is worth recording because a wrong test that is expensive to fix stays.

The correct test is asked only of what the cheap one rejects. Acyclicity is one pass and is sufficient — a lettering with no cycle at all in the quotient has none upstairs either — so it answers nearly every node, and only the letterings it rejects cost the second question.

Measured: five of nine nodes on a four-cell object reach the expensive branch, and fifty thousand five hundred and forty-six of fifty-six thousand seven hundred and seventy-two on a sixteen-cell one. The expensive branch is reached often and it is a small constant more expensive.

So the correct test costs about what the wrong one did per node, and the search finishes because it is finding a witness rather than exhausting.

What to take from the numbers #

Three sentences.

A test that is too strong does not produce an error, it produces a proof of something false, and the proof is as expensive as the search is.

The cost of being wrong grows faster than the cost of being right, because a wrong rejection turns every instance into an exhaustive one.

And a cost curve does not distinguish a hard instance from a wrong test, so neither will anybody reading one.