The order the refusals come in

Saying that a crease pattern folds is expensive and saying that it does not is sometimes cheap. A no can be a short reason — one condition failing at one vertex, one loop in a list of letters — where a yes has to exhibit a folded state and defend it against everything.

This collection has accumulated five different ways of saying no, three of them recently, and they have never been put in one place and ranked. The ranking turns out to be the interesting part, because the order they fire in is not the order anybody would design.

The five, and what each costs #

A crossing. Two creases drawn across one another with no vertex there. Finding one is a comparison of two segments — a few arithmetic operations — asked of every pair of creases in the pattern. No letters are read, nothing is folded, and the answer does not depend on the assignment. It refuses outright: a crossing has no flat folded state at any angle under any lettering.

A vertex condition. Developability, Kawasaki, Maekawa or the big-little-big lemma failing at one interior vertex. One pass over the vertices, reading the angles and letters at each. This is the subject’s oldest test and the one every figure here is gated on.

The panels not placing. Fold the panels flat by composing reflections and check that the two routes to a panel agree. One walk over the panel graph, after the pattern has been subdivided and its faces found. When it fails the paper cannot be put down at all, which is a stronger statement than any vertex condition makes.

A loop in the forced order. The letters force some panels above others, and if those forcings contain a cycle no ordering exists. One pass over the crease list, on a pattern whose orderings could never be enumerated.

No ordering at all. Enumerate the orderings of the panels and check every non-crossing rule against each. This is the only one of the five that can also say yes, and it is refused outright past about eighteen panels because the orderings of n panels are n factorial.

What each of them actually caught #

Thirty-three patterns, four populations, each put through the five in order and recorded against the first that refuses it.

The crossing sweep caught five. All five are twist tessellations assembled unit by unit — a triangular grid at two twist angles and a rhombille at three — and the counts on them are not marginal: 32, 32, 54, 76 and 78 crossings each.

The vertex conditions caught none. That is by construction rather than by luck: every pattern in every one of these populations was built by a generator that gates on those conditions, so a pattern failing them never reaches a population at all.

The placement test caught none — and it would have caught exactly the five the crossing sweep caught, because a patch fails to place if and only if it has a crossing on everything measured here. It fired second and found nothing left to find.

The loop test caught none. Every pattern that got as far as it had letters that do not contradict themselves.

The ordering search caught six — two twists and four quadrilateral meshes — and it is the only test that reached them.

Twenty-two were refused by none of the five. Thirteen of those are known to fold; nine are undecided, because their panels are past what the search will finish.

Where the five came from #

They did not arrive together, and the order they arrived in is nearly the reverse of the order they cost.

The vertex conditions came first, with the collection itself: four statements about the creases at one point, each of them a nineteenth- or twentieth-century theorem, all of them cheap and all of them local. Everything drawn here has been gated on them since the beginning.

The ordering search came next, and it is the expensive one — built to answer which layer goes on top on a strip and then extended to a sheet, where the layers are ordered over a region rather than along a line.

The placement test arrived sideways, from a question about a sheet that is not a disc: compose the reflections around a loop of panels and ask whether they come back to the identity. It was written to price a hole and turned out to be a general refusal.

The loop test came from a failure — a tessellation patch drawn here for years whose letters forced a cycle of twenty-eight panels, so that no ordering of it existed and one pass over its crease list said so.

The crossing sweep is the newest and the cheapest, and it came from the same place: a construction producing patterns that every existing test passed. Two of the five arrived from defects in this collection’s own drawings, which is the ordinary way a test gets written.

The cheap test is not screening for the expensive one #

The obvious reading of a ladder like this is that the cheap tests exist to save the expensive one some work — a filter in front of a solver, catching the easy cases so the hard machinery runs less often.

That reading is wrong here, and the way it is wrong is the point of the rung. Every pattern the crossing sweep refused has far more panels than the ordering search will ever accept. The rhombille patches have between 125 and 157 panels; the search is refused past eighteen. Had the crossing sweep not existed, those five would not have been decided later and more expensively. They would have been reported undecided, permanently, from now on.

So the cheap test is not a screen. It is the only instrument that reaches those patterns at all, and it reaches them because its cost does not grow with the thing that makes them hard. The search’s cost explodes with the number of panels; the sweep’s grows with the square of the number of creases, which on the largest patch here is twenty-one thousand comparisons and a few milliseconds.

Two of the five are one test #

The ladder treats the crossing sweep and the placement test as separate rungs, and they are not independent — the first is the opening move of the second.

Placing the panels requires the pattern to be subdivided: every crease split wherever it meets another, so that the faces can be walked and each panel reflected in turn. Finding those meeting points is exactly what the crossing sweep does. So a run of the placement test performs the crossing sweep on its way in, and cannot get past it without having done so.

That reframes the census’s second null. The placement test caught nothing not because it is redundant against some other rung but because its own first step had already fired: the five patterns it would have refused were removed by a computation it was about to perform anyway. Running it after the sweep and reporting zero is a tautology rather than a measurement.

Which makes the honest ladder four rungs rather than five: subdivide and place — with the crossing sweep as its cheap early exit — then the vertex conditions, then the forced loop, then the search. The first rung has two outputs and it is one pass.

And which of the four is genuinely untested #

With the accounting corrected, one test has never fired rather than two, and it is the loop.

That matters for what the population is missing. The placement test’s other failure mode — a sheet that has no crossings and still cannot be put down, which is what a ring of paper with three creases does — is untested here too, but it is untested as a branch of a rung that ran, not as a rung that never ran. The loop test is a whole rung that has been executed on thirty-three patterns and refused none of them.

So the shopping list for the test population is one item long rather than two, and it is precise: patterns whose letters force a cycle. They exist, they are named, and they are excluded from these populations by construction — which is the one thing a deliberately built test set should not do to the one test it has never exercised.

The general form of that is worth carrying past this ladder. Ranking tests by cost is only meaningful when the tests are independent, and cheap tests are very often the early exits of expensive ones rather than alternatives to them. The right question about a cheap test is not what it costs but whether anything else would have done its work — and here, for one of the five, the answer is yes.

The two that caught nothing are not useless #

A test that never fires looks like a test to remove, and neither of these is.

The placement test would have caught the same five, and it catches them for a different reason and with a different output. The crossing sweep says there is a crossing here, at this point; the placement test says the panels disagree by 1.86 sheet widths. The second is a quantity rather than a location, and on a pattern with no crossing it can still fail — a sheet with a hole in it, a ring of paper with three creases running across it, has no crossing anywhere and does not place. It caught nothing here because no population contains such a sheet.

The loop test is the one that will fire next, and it nearly did. Every repaired tessellation patch has letters that force a loop — of fourteen panels on the triangular, thirty-six on the honeycomb, twenty on the rhombille — and those patches are not in these populations, because the populations are built the older way on purpose. A test whose targets are excluded from the test set catches nothing, and that is a fact about the test set.

Both of those are the ordinary reason a checker’s test population needs building deliberately: a population of only valid patterns tests half a test, and a population of the wrong invalid patterns tests the wrong half.

What the ordering search is for #

Six refusals out of thirty-three, at a cost that grows factorially, and the honest question is whether it earns its place.

It does, and for a reason the other four cannot supply: it is the only one that says yes. The other four are necessary conditions. Passing all of them means a pattern has not been caught, which is not the same as being foldable — and thirteen of the twenty-two survivors here are known to fold precisely because the search exhibited an ordering for each.

That asymmetry runs through the whole subject. Deciding flat-foldability of a general pattern is NP-hard, so no cheap test can ever certify a pattern; the cheap tests can only refuse. A ladder of refusals is therefore a ladder of partial answers, and the expensive step at the top is the only one that closes a case in the affirmative.

A sixth refusal, which answers a different question #

There is a further way of saying no here and it is deliberately not in the ladder, because it refuses a different claim.

A machine that folds paper makes one weak kind of move — a simple fold through the whole stack, a crimp, a fold that may choose which layers to take — and asking whether such a machine can reach a folded state is a different question from whether the state exists. A pattern can be perfectly flat-foldable and unreachable by a one-layer machine, which is what the roll a one-layer machine cannot make shows.

Putting that in the same ladder would be a category error: the five above all refuse the sentence this pattern has a flat folded state, and the machine test refuses this machine can get there. A pattern refused by the sixth may still be foldable by hand.

It is worth naming here because the ladder invites the mistake. Ranking tests by cost tempts a reader to treat them as approximations of one another — cheap ones as rough versions of expensive ones — and the ordering search is not a better crossing sweep, nor is the machine test a stricter ordering search. They answer three different questions and share a subject.

Where the cost actually goes #

Setting the five side by side in what they read is more useful than any timing, because the readings are what scale differently.

The five columns read down as a ladder of what a test has to look at: coordinates, then vertices, then faces, then the whole crease list, then every arrangement of the panels. Four of the five grow gently and one does not, and the boundary between them is exactly where a pattern stops being decidable in practice. Everything on the shelf with more than eighteen panels — the Miura, the Yoshimura, the waterbomb tessellation, the tapered corrugation — is decided by the first four or not at all.

That also says which test to add next, if one is to be added. It should not be a better search: a better search moves the boundary from eighteen panels to twenty-two and leaves everything above it untouched. It should be another test whose cost grows with the drawing rather than with the folding, and the first candidate is the one already named — a pattern whose letters force a loop is refused in a pass, and there are patterns here waiting for it.

The order to run them in #

For anyone drawing a crease pattern — by hand, by rule, or by a search — the ladder suggests a working order, and it is not the order of the theorems’ importance.

Sweep for crossings first. It costs nothing, it needs no letters, and it catches the class of fault that every other test is blind to. It also catches it in the drawing, before any effort has gone into lettering or folding.

Then the vertex conditions, because they are cheap and because a failure names a point.

Then place the panels. It needs the pattern subdivided, which is work, and in exchange it says whether the sheet exists at all — and gives a distance when it does not.

Then the forced order, one pass, which refuses a lettering rather than a drawing and therefore suggests a redraw rather than a redesign.

And only then the search, if the pattern is small enough for it, which most interesting ones are not.

Three of those five did not exist here until recently, and the collection’s own patterns were drawn without them. That is not a criticism of the earlier work; it is the reason two of the five exist.

What the ranking does not say #

It is not a benchmark. The counts are over thirty-three patterns chosen for other reasons, and they say what fires on these. A different population — random drawings, say, where crossings are almost certain — would put the first row far higher.

Cost is not time. Nothing here is timed. The column above says what each test reads and how the reading grows, which is the durable half; the wall-clock half depends on machines and on how the code was written, and would date faster than the argument.

And the counts move when the collection does. Two of the thirty-three patterns are new this time — a fold-and-cut star and an L, added when the straight skeleton learned to shrink an outline that turns back — and they moved the totals from twelve of thirty-one folding to thirteen of thirty-three. A population that grows is a population whose published numbers have to be rewritten, which is the price of keeping the measurement rather than the sentence.

And a refusal is not an error. A pattern that fails one of these five is a pattern that cannot be folded, and in a test population that is a member doing its job. Eleven of the thirty-three are refused, and they are the reason the checkers can be trusted about the rest.