What a checker cannot check

Every crease pattern drawn on this site passes through one function before it reaches a page. assertFlatFoldable runs four conditions at every interior vertex and throws if any of them fails, so a generator that would emit an impossible pattern stops the build instead of reaching a reader who owns paper.

It is a filter, not a decision procedure, and the difference is the whole essay. A pattern that passes all four is not thereby known to fold.

The four conditions #

Each condition looks at one vertex and its immediate neighbourhood, and each is necessary: a pattern that folds flat satisfies all of them everywhere.

Developability. The sector angles around an interior vertex must sum to 360°. Anything else describes paper that was cut or stretched, and no folding repairs it. For a vertex drawn inside a flat sheet this holds automatically, which is why it never fires here and why it is nonetheless kept: patterns arriving from elsewhere, in the FOLD format this site exports, can carry vertices that do not close.

Kawasaki. The sectors alternate, and the two alternating groups each sum to 180°. Equivalently the alternating sum of the angles is zero, which is how it is computed. It needs an even number of creases, and an odd count is refused with a reason rather than with a meaningless number.

Maekawa. The number of mountains and valleys at the vertex differs by exactly two. It is a winding argument rather than a fact about paper, it is cheap, and it catches assignments that Kawasaki — which sees only angles — cannot.

Big-little-big. A sector strictly smaller than both its neighbours must be bounded by creases of opposite letter. Otherwise the panel between them has nowhere to go. It is the cheapest condition that catches a locally consistent assignment that still will not fold, which earns it its place.

Four independent tests, demonstrated #

A set of conditions is only worth running separately if each catches something the others miss, and that is a claim about the conditions rather than a definition of them. The figure at the top of this essay is built to make it fail if it stops being true.

Its first row has sectors of 90°, 110°, 70° and 90°, with three mountains and a valley. The angles sum to 360, so developability passes. Three mountains against one valley is a difference of two, so Maekawa passes. The 70° sector is strictly smallest and its two creases differ, so big-little-big passes. The alternating sums are 160° and 200°, so Kawasaki alone catches it.

The second row is four creases at 90° apart, all mountains. Angles fine, alternating sums both 180, no sector strictly smallest — and four mountains against no valleys, so Maekawa alone catches it.

The third has sectors of 120°, 40°, 60° and 140°, with the 40° flanked by two mountains. The alternating sums are both 180 and the letters are three to one, so big-little-big alone catches it.

The generator throws if any of those three is caught by more than one test or by the wrong one. That is not a decorative assertion: the sector-to-crease indexing is fiddly, and an off-by-one there would still produce a plausible-looking table of marks.

The pattern that passes everything #

The fourth row is a Miura. Every interior vertex satisfies every one of the four conditions, and the figure asserts that too — it refuses to draw if the filter reports any failure.

That Miura does fold flat, and this site knows it for a reason that has nothing to do with the four conditions: the tiling is generated from a single vertex whose motion is solved as a spherical linkage, and the periodic construction propagates it. The certificate came with the construction.

Take away the construction and the certificate goes with it. A pattern that passes all four conditions and arrives with no provenance is a pattern about which nothing has been established, and deciding it is the NP-hard problem.

Why the gap cannot be closed #

It is tempting to read the blind spot as an incompleteness to be fixed — a fifth condition, a sixth, until the set decides the question. That programme is impossible, and the impossibility is exactly what the hardness result says.

Any finite set of conditions, each examining a bounded neighbourhood, can be checked in time proportional to the number of vertices. A set that decided flat-foldability would therefore be a linear-time decision procedure for an NP-hard problem. So either no such set exists, or one of the largest open questions in mathematics has a surprising answer.

The gap in assertFlatFoldable is not a defect of assertFlatFoldable. It is the shape of the problem, showing through a hundred lines of code. Any checker built the same way has the same hole, and a checker built differently is not a checker but a solver, with a solver’s cost.

How strong the filter is, measured #

Saying the filter is not a decision procedure invites the question of how much it does achieve, and that has an answer wherever the family is finite.

At a single degree-four vertex the filter is enormously strong: it discards three-quarters of the assignments at these angles, and eight of sixteen when the sectors are equal. It is also, at a single vertex, complete — the four conditions together decide a single-vertex pattern, because there is no room for a layer ordering to go wrong when there is only one vertex to order around.

That is worth saying plainly, because it locates the blind spot precisely. The conditions decide one vertex and filter many. Everything this essay is about begins at the second vertex.

As the pattern grows the surviving fraction falls and the surviving count rises, which is the worst combination available: a filter that gets relatively more selective and absolutely more permissive. A strong filter leaving exponentially many candidates is still leaving exponentially many candidates.

The filter removes exactly one of the two doublings #

The combination the previous section names — relatively more selective, absolutely more permissive — has a size, and putting a number on it says how much of the problem a filter of this kind can ever take away.

Each crease is one binary choice, so a pattern with $E$ creases has $2^E$ assignments. Each interior vertex is where the conditions bite, and at a degree-four vertex they remove a factor of four when one sector is strictly smallest and a factor of two when the smallest is tied. Take the weaker of the two, which is what symmetric patterns give: the survivors number about $2^{E-V}$.

Now count creases against vertices. In a large grid every interior crease is shared by two vertices and every vertex has four creases, so $E$ approaches $2V$ as the pattern grows. Substituting, the survivors number about $2^{V}$.

So the filter converts $2^{2V}$ candidates into $2^{V}$. It removes one of the two exponentials and leaves the other standing. A solver handed the filtered set still faces a set that doubles with every vertex added, which is the same asymptotic difficulty it faced before, at half the exponent.

That is the precise sense in which a strong local filter does not approach a decision procedure. Halving an exponent is a real gain and it is not a change of kind.

Why bigger neighbourhoods do not help either #

The obvious next move is to check pairs of adjacent vertices, then triples, then every neighbourhood of radius $r$ — accepting more cost for more certainty. It fails, and the reason is more concrete than the complexity argument above.

The obstruction that local conditions cannot see is a cycle in the ordering requirements, and a cycle has no bounded size. The forty-nine-panel patch this site draws has a loop of twenty-eight panels, passing through several separate twist units, and every neighbourhood it contains is impeccable. Tile more units and the loop gets longer.

So for any radius $r$ somebody proposes, there is a pattern whose only defect is a cycle longer than $r$, and whose every radius-$r$ neighbourhood passes. The obstruction is not local at any scale, which is why widening the window is not a slower route to the same place. It is the same window.

The one test that does catch such a cycle is not a neighbourhood test at all: it walks the whole ordering graph once and reports whether it closes. That is a global reading of a global property, and it is the only shape that can work.

What the filter is for, then #

If it does not decide, it is fair to ask what it buys, and the answer is specific enough to be measured.

It catches every generator bug of a certain kind, immediately. A generator that mis-assigns a letter, computes an angle wrongly, or emits a vertex it did not intend fails the build rather than producing a figure. That has happened repeatedly here — most seriously when the Yoshimura pattern turned out to have been drawn rather than built, putting six mountains and no valleys at a degree-six vertex, and surviving a long time because it never went through the drawing routine that calls this one.

It makes the negative claims sharp. A generator whose subject is a pattern that does not fold is marked unverified and says so in its caption. The distinction between “checked” and “deliberately unchecked” is explicit rather than implied.

And it costs nothing. Four conditions at each vertex is linear in the pattern’s size. It runs on every figure of every build, on every site, and nobody notices. That matters more than it sounds: a check expensive enough to be skipped occasionally is a check that will be skipped on the build where it mattered, and the Yoshimura failure above is precisely a pattern that took a route around a function nobody had thought of as optional.

A filter with those properties is the correct instrument. The error is not in using it; it is in reading its silence as a proof.

There is a fourth thing it buys that is easy to overlook, and it is about the essays rather than the figures. Because every pattern is filtered, an essay can say this pattern satisfies Kawasaki and Maekawa at every vertex and mean it, without the sentence being an author’s assurance. The claim is made by a program that runs on every build and stops the site if it is false. What the essay may not say, and does not, is that the pattern therefore folds.

The asymmetry that makes filters worth having #

There is a general principle underneath this and it is worth stating, because it applies well beyond folding.

A necessary condition gives certainty when it fails and nothing when it passes. Failure is a proof of impossibility; success is an absence of one particular kind of evidence. The four conditions here are all of that shape, and the whole value of running them is in the failures.

That asymmetry means a checker should be judged by what it rejects rather than by what it accepts, and this site’s gate is built on that principle: it ends by feeding the machinery input it must refuse, because an assertion that has never rejected anything proves nothing. The refusals in that gate now number in the dozens, and each is a claim that a specific wrong thing is caught.

The corresponding failure mode is a checker that has never rejected anything and is therefore untested. A green check mark from such a thing is not weak evidence — it is no evidence, and it is worse than no checker, because it looks like one.

The other checkers, and what each of them decides #

The vertex filter is one of five pieces of machinery here that answer questions about a pattern, and running them together as “the checks” hides that they answer different questions with different authority. Setting them side by side is the clearest statement of where the certainty is.

The vertex filter. Four necessary conditions, linear cost, no decision. This essay.

The stacking search decides, completely, in one dimension, by exhausting the orderings of the segments. It is the only unconditional decision procedure here and it is bought with factorial time — which is why the strips on this site are short.

The face walker verifies, by walking the plane graph and checking Euler’s formula and area conservation. It establishes that a pattern’s faces are what the construction intended, which is a different thing from establishing that they fold.

The map counter counts, for ruled rectangles, and its authority comes from agreeing with values somebody else computed.

The machine simulator decides a different predicate — whether a machine can reach a state — and hands every state it reaches to the stacking search for a second opinion.

Nothing in that list decides two-dimensional flat-foldability, and nothing could. The absence is the point of this essay stated as an inventory.

What no figure here can show #

The blind spot is an absence, and an absence has no picture.

Every figure on this page draws what the conditions do — the sectors they measure, the letters they count, the patterns they catch. None of them draws the thing that gets through, because the thing that gets through looks exactly like the thing that does not. A crease pattern whose layers cannot be stacked is a drawing of lines on a square, indistinguishable by eye from one whose layers can.

That is the deepest reason this site’s rule about verification is what it is. A wrong crease pattern is not visibly wrong. It is wrong in the reader’s hands, after an evening, which is a failure mode no amount of looking at the figure prevents.

The second thing no figure shows is the size of the gap. How many patterns pass all four conditions and fail to fold? The question is well posed for a fixed family — a fixed set of crease positions with all 2ⁿ assignments — and unanswerable in general, because “all crease patterns” is not a set anybody can put a measure on. The censuses here are all of the fixed-family kind for exactly that reason.

The idealisation, named #

The four conditions are conditions on an idealised sheet: zero thickness, no stretch, creases of no width, and a folded state in which layers may touch but not intersect.

Every one of those matters to a checker rather than merely to a folder. A real sheet with a crease of finite radius does not satisfy Kawasaki exactly, because the sector angles are measured to a line that is really a curved region. A real vertex where six layers meet may fail physically while passing every condition, because the paper runs out of room — which is a thickness constraint and not a geometric one.

So the checker is a checker of a model, and the model’s fidelity is a separate question with its own field on this site. That is not a hedge: separating the geometric obstruction from the material one is what lets either be measured, and a checker that tried to do both would do neither.

Who established this, and when #

The four conditions have four different provenances. Developability is a restatement of what it means for paper not to be cut or stretched. Kawasaki’s theorem is Toshikazu Kawasaki’s, from the 1980s, and was found independently by others. Maekawa’s is Jun Maekawa’s, from the same period, popularised by Kunihiko Kasahara. Big-little-big belongs to the systematic study of single-vertex flat-foldability rather than to any one name.

That they are jointly insufficient was made precise by Marshall Bern and Barry Hayes in 1996, and their result is why no fifth condition is being sought here. The order of events is worth noticing: the conditions were found first, used for a decade, and then proved to be as far as local reasoning goes.

Where the ladder goes next #

A checker’s limits are one kind of honesty about machinery. Another is asking what a construction costs, because a theorem that says something can always be done says nothing about how much of it there will be: the fold-and-cut construction is universal, and what it produces for a given outline is a measurable quantity that this repository can count.