Consistent is not foldable

A crease pattern is handed to this collection’s machinery three times over, and each time a different question is asked of it.

The first is local and cheap: at every interior vertex, do the angles and the letters satisfy developability, Kawasaki, Maekawa and the big-little-big lemma? The second is a single pass over the crease list: each crease says which of its two panels lies above the other, and do those statements contradict themselves? The third is a search: given that they do not, is there an order of the panels in which no paper passes through any other?

Three sieves, each strictly finer than the last, because a labelling with a folded state satisfies every condition and a labelling whose letters contradict themselves is never asked for an order. What is worth measuring is how much each of them catches, and that requires enumerating a pattern’s labellings rather than sampling them.

Four of the two hundred and forty-eight failures are caught by the letters. Two hundred and forty-four are not.

What the middle sieve is worth here #

One and a half per cent, on this pattern. The one-pass test finds four of the two hundred and forty-eight labellings that satisfy every vertex condition and nevertheless cannot be folded, and stays silent on the rest.

That is a poor showing and the honest way to state it. All four it catches lie inside one group — the thirty-two labellings whose central ring reads as one letter, which is the labelling a designer draws — and the lettering that folds nowhere singled that group out before anything here existed, by enumerating orderings of nine panels. The cheap test now proves four of those thirty-two in one pass instead of seven and a half thousand search nodes, which is a real improvement in cost and a small one in coverage: the other twenty-eight have letters that agree with themselves perfectly and no folded state.

It is also worth noticing what the first sieve did. Four thousand and ninety-six labellings go in and two hundred and fifty-six come out — the vertex conditions remove ninety-four per cent of everything, which is a great deal — and then the two later sieves remove ninety-seven per cent of what is left. How many assignments fold measured the first of those numbers across a family of patterns and found it falling fast with size. The second number is what this essay is about, and it does not fall with size at all in any simple way.

The same measurement on two other patterns #

The ratio is not a constant, and the two other printed patterns small enough to enumerate come out in opposite directions.

The preliminary base has one interior vertex of degree eight, no circuits at all, and every one of its hundred and twelve admissible labellings has a folded state. Neither the letters nor the search removes anything. That is what a pattern with nothing to go wrong looks like, and it is the reason the base is what beginners are handed.

The triangle is the informative one. Twelve of its thirty admissible labellings have no folded state, and the letters catch none of them. Its skeleton is a tree, so it has no circuit for a contradiction to sit on, and every one of those twelve failures is the non-crossing rules refusing every order of seven panels.

So across three patterns the cheap test’s share of the failures is nought per cent, one and a half per cent, and nought again. It is not that it usually works and sometimes does not. It usually does not.

The pattern across the three is not size. The triangle has six creases and catches nothing; the square twist has twelve and catches four; the preliminary base has eight and there is nothing to catch. What separates them is whether the pattern has a closed circuit of creases in it: the twist has one, the ring round its central polygon, and that ring is where all four of its caught failures sit. The other two patterns are trees of creases radiating from their vertices, and a circle in the letters needs a circuit to sit on.

So the middle sieve’s coverage is not a percentage that can be improved by trying harder. It is a structural property of the pattern, and on a pattern with no circuits it is exactly nought.

The first sieve is Maekawa and nothing else #

Before reading what the later sieves catch, it is worth noticing what the first one is actually doing on these three patterns, because the three numbers are all one formula.

At a vertex of degree $d$ whose sectors are equal or come in equal pairs, Kawasaki holds identically and the smallest-sector lemma has no strictly smallest sector to act on. So the only condition doing anything is Maekawa, which admits the letterings with $d/2 + 1$ of one letter or $d/2 - 1$:

$$\binom{d}{\tfrac{d}{2}+1} + \binom{d}{\tfrac{d}{2}-1}$$

The preliminary base is one vertex of degree eight, and that formula gives $56 + 56 = 112$ — the census’s number exactly. The fold-and-cut triangle is one vertex of degree six: $15 + 15 = 30$, again exactly. The square twist is four vertices of degree four, each halving, so $2^{12}/2^{4} = 256$.

All three of the first sieve’s outputs are Maekawa arithmetic, and on none of the three does any other condition remove a single labelling. That is worth saying because the first sieve is routinely credited with removing ninety-four per cent of everything, and on these patterns it is one theorem from 1980 doing all of it.

One panel more than a cone #

The triangle then poses a puzzle worth resolving, because it looks like it contradicts a result stated elsewhere here.

A cone — a single interior vertex with creases radiating from it and nothing else — is completely decided by the local conditions: there is no second vertex, so there is no room for an ordering to go wrong. The triangle has one interior vertex of degree six, and twelve of its thirty admissible labellings have no folded state.

The resolution is in the panel count. Six creases at one vertex cut the sheet into six sectors, and the triangle has seven panels. One of its creases does not pass through the centre — it is a perpendicular dropped to an edge — and that one extra crease is enough to make the pattern something other than a cone.

Seven panels instead of six costs the completeness guarantee, and it costs forty per cent of the labellings. That is a sharper statement of where the local conditions stop than “the conditions decide one vertex”: they decide a cone, and a cone plus one crease is already outside them.

It also explains why the letters catch none of the twelve. A cone plus a perpendicular is still a tree of creases — nothing closes — so there is no circuit for a contradiction to run round, and every one of the twelve failures is the non-crossing rules refusing all 5,040 orderings of seven panels.

Which is the right way round #

That sounds like an argument against the test and it is the opposite. A cheap test whose job is to be sound is being asked the wrong question when it is asked how much it catches.

What matters about it is the shape of what it catches, and the shape is: patterns whose failure is combinatorial and global, on inputs too large for anything else to be run on at all. The square twist and the triangle are enumerable, so the exhaustive answer is available and the cheap test is redundant on them. A rhombille tessellation patch of a hundred and fifty-seven panels is not enumerable, is not searchable, and is refused by its own letters in milliseconds.

A test that catches one and a half per cent of the failures on the cases already decidable, and a hundred per cent of the answers obtainable on the cases that are not, is worth having. The percentage is measured in the wrong place because it is the only place it can be measured.

Where the other two hundred and forty-four go #

It is worth being concrete about what refuses them, since “the non-crossing rules” is doing a lot of work in the sentence above.

Two rules, beyond the one the letters encode. A panel may not lie between the two panels a crease joins, wherever that crease’s folded image crosses that panel’s interior — the crease is where the paper turns and there is no gap in it. And two creases whose folded images lie along the same line and overlap are two turns in the same place: they may nest, or stand clear, but they may not interleave.

Both of those are statements about where the paper lands, and neither can be read off a crease list. They require the folded state to have been computed — every panel placed by composing reflections — and then every panel tested against every other for shared ground. On the square twist that is thirty-six pairs; on a patch of a hundred and forty-five panels it is twenty-one thousand polygon tests before the search takes a step.

The letters, by contrast, are free. That asymmetry is the whole reason to have both, and it is also why the two refuse different patterns rather than the same patterns at different speeds.

What multiplicity has to do with it #

This anchor is about how many folded states a marking has, and the three sieves give that question an unexpectedly sharp form.

More than one way to lie flat established that a crease pattern with its letters written on it is not one object: the square twist’s eight foldable labellings are eight different patterns, and a single labelling can itself admit several orderings of its panels. One marking, many objects is the same point from the reader’s side — a printed sheet does not determine what a folder ends up holding.

The middle sieve draws a line inside that. A labelling whose letters contradict themselves has zero folded states and can be known to have zero without any of the multiplicity machinery being run. A labelling that passes it has an unknown number, from zero upwards, and finding out costs a search. So the cheap test partitions the admissible labellings into provably none and unknown, which is a coarser partition than the one the anchor wants and is the only one available at scale.

The census that answered a question it had not asked #

The numbers above are exhaustive, and an exhaustive count is only worth what its enumeration is worth. This one had a defect and it is worth recording, because it is the kind that does not announce itself.

The enumeration walks a counter from zero to two to the power of the crease count, reading each labelling out of the counter’s bits. Before it starts it compares that total against a cap and refuses anything larger. The total was computed by shifting one left by the number of creases — and a shift is taken modulo thirty-two.

So a pattern of thirty-eight creases asked for one shifted left thirty-eight places, got one shifted left six, and was told it had sixty-four labellings. Sixty-four is under the cap. Nothing refused. The enumeration then walked sixty-four of the Miura fold’s 2³⁸ labellings, with the other thirty-two creases left wherever they happened to be, and reported that the Miura has no admissible labelling at all.

Nothing on any page was wrong, because every published use of the census asks for a pattern of twelve creases or fewer. The defect was armed rather than fired. But its failure mode is a silent zero from a function whose entire purpose is to be exhaustive, which is the worst available shape: a wrong answer that looks like a finding.

It now computes the size without wrapping, and refuses past thirty-one creases outright — because past thirty-one the bit-reading is wrong whatever the cap says, so the cap was never the thing keeping it honest. Five of the eight printed patterns are now refused by name where four of them used to be answered incorrectly.

The same wrap was in the census that splits labellings by a property of themselves — the one that produced the ring figure above — and it has been repaired the same way. The ring figure is over the square twist’s twelve creases and was never affected; a placement asking the same question of the Miura would have received a table of zeros.

What is enumerable, and what that costs the argument #

Three of eight printed patterns can have every labelling counted, and the number is small because the quantity being enumerated doubles with every crease. The hexagon twist has eighteen creases and a quarter of a million labellings, which is past the cap this collection sets rather than past what a computer can do; the tapered corrugation has forty-five, which is thirty-five trillion and past everything.

There is one way to keep enumerating past that, and it is worth naming since it is used elsewhere here. Fix some of the creases and enumerate the rest: the hexagon twist with its central ring pinned is four thousand and ninety-six labellings, and that is a measurement on a stated slice rather than a sample of the whole. The ring figure above is exactly that manoeuvre. What it cannot do is answer a question about the pattern as a whole, and the slice has to be named every time or the number is a sample pretending to be a census. That is the whole basis on which any of the sampled numbers elsewhere in this collection are believed, so the narrowness is worth stating plainly rather than buried.

Three agreements do not establish that a sampler over solutions is unbiased on a pattern of two hundred and eighty-two creases. They establish that it is not obviously broken, on the only cases where the question can be settled. Every essay here that quotes a sampled share says so, and none of them divides one by anything.

Two failures that look alike and are not #

There is a distinction the three-sieve picture makes available that was hard to state before, and it matters to anybody trying to repair a pattern rather than merely to judge one.

A labelling refused by its letters is refused by a statement about pairs of panels that no rearrangement can satisfy. There is nothing to try. The only move is a different labelling, and there is no path of small changes to one — the letters that would have to change are mostly the ones with an interior vertex at each end, which no local move can reach.

A labelling refused by the non-crossing rules is refused after a search that visited every ordering and found each of them breaking one rule or another. That failure comes with a witness of a different kind: the search can say which rule the best candidate broke and where, and sometimes the answer is a single pair of panels that a small change in the geometry — a slightly different sector angle, a slightly different pleat width — would separate.

Nothing slides past anything is the standing account of how little room there usually is. The point here is only that the two refusals leave a repairer in different positions, and the cheap test tells them apart for free.

The claim this leaves #

Three sieves, and the middle one is the odd member. The first is complete for what it checks and checks something local. The third is complete for the whole question and cannot be run past about twenty panels. The second is sound, cheap, and incomplete by a wide and variable margin — nought per cent on a tree, one and a half on a twist, and everything available on a tessellation patch.

An incomplete test is usually a stepping stone toward a complete one. This one is not, and the reason is structural rather than a matter of effort: the letters are a finite list of statements about pairs of panels, and the non-crossing rules are statements about where the paper landed. No amount of reading the crease list harder recovers the second kind. Deciding the whole question is NP-hard, and a linear-time sound test for an NP-hard property is expected to be incomplete; what is not expected, and is the finding here, is how sharply its coverage depends on whether the pattern has a circuit in it.