A proof in one pass

A crease pattern that folds flat has to answer two questions, and only one of them has ever been cheap. The first is local: at each interior vertex, do the angles and the letters satisfy the conditions every folder’s textbook states? That is four arithmetic checks per vertex and it scales to any pattern anybody draws. The second is global: given that the paper lands where it lands, is there an order of the layers in which no panel passes through another? Local is not global is the whole distance between them, and the second question is NP-hard.

The machinery that answers it here is an exhaustive search over orderings, and it behaves exactly as an exhaustive search should. It settles a preliminary base in five thousand nodes, a square twist in seven and a half thousand, and a hexagon twist in half a million. At a Miura fold of twenty-four panels it does not settle at all: it visits two million nodes and reports that it does not know.

So the interesting question is not how to make that search faster. It is which failures can be seen without searching at all.

What a crease already knows #

A crease is where the paper turns over, and turning over is not symmetric. A valley brings the far panel up and across the near one; a mountain takes it underneath. Which of those a reader looking down at the folded sheet sees also depends on whether the near panel has itself been turned on the way to where it sits — so the direction is the letter multiplied by the near panel’s own orientation, and both of those are known before any layer is placed anywhere.

That is one statement per crease, of the form this panel lies below that one. It is not a preference and not a heuristic. A pattern whose order violated it would be a pattern whose paper turns the other way at that crease, which is a different crease from the one that was drawn.

Collect all of them and what comes out is a directed graph on the panels: a node for each panel, an arrow from each panel to the one that must lie above it. And a directed graph carrying a circle — a panel above a panel above a panel, coming back round to the first — is describing an impossibility. Every arrow in the circle is necessary, so no order of the panels satisfies all of them, so there is no flat folded state. Not none was found: none exists.

The cost of finding it is a depth-first walk, which is linear in the number of creases. There is no branching, no backtracking and no budget to exceed.

It is worth being precise about how little of the folded state this consults. The ordering search works from three kinds of constraint, and the crease is only the first of them. The second says that a panel may not lie between the two panels a crease joins, wherever that crease’s folded image crosses it — there is no gap in a fold to pass through. The third says that two creases whose images lie along the same line and overlap may nest or stand clear but may not interleave. Both of those are statements about overlaps, and finding the overlaps means testing every panel against every other: on a patch of a hundred and forty-five panels that is twenty-one thousand polygon tests before the search has taken a single step.

The circle needs none of that. One arrow per crease, one walk, done — which is why it can be asked of a patch whose overlap scan alone would be the expensive part of the afternoon.

The same pattern, lettered differently #

The picture above is not a property of the square twist. It is a property of that lettering of the square twist, and the pattern’s own lettering has no circle in it at all.

That distinction is the whole of what this test is about, and it is easy to lose. The conditions at a vertex are a statement about the pattern — the angles are fixed by the drawing, and a lettering either satisfies them or does not. A circle in the layer relation is a statement about the pattern and the lettering together, and a pattern can have both kinds of lettering. How many assignments fold counted how many letterings of a small pattern satisfy every vertex condition; this counts how many of those go on to contradict themselves before a single layer is placed.

What it finds on the shelf, and what it finds on a patch #

Every crease pattern this collection prints at true scale is consistent as drawn. That is not a coincidence and it is not evidence of anything: each of them was produced by a construction that returns a lettering, and a construction that returns one returns one that works, because it was written by somebody who folded the result.

The interesting number is what happens when the letters are drawn again. Independent letterings can be obtained by propagating the vertex conditions to a fixed point and, wherever propagation stalls, branching on a crease with the two letters tried in an order a stream decides. Every draw is a lettering that passes every condition at every vertex; the draws differ because the decisions differ.

The preliminary base is consistent in all two hundred draws. The square twist is consistent in a hundred and ninety-eight, the Yoshimura in a hundred and ninety, the Miura in a hundred and eighty-one. Then the patches: twenty-six of two hundred on a square tiling of forty-nine panels, two of two hundred on a hexagonal one of seventy-seven, and none at all on a rhombille of a hundred and fifty-seven.

Ordered by size the pattern is monotone and steep, and that is a fact wanting an explanation rather than a fact supplying one — the Yoshimura folds to sixty-five panels and is consistent in ninety-five per cent of its draws, which is more panels than the square patch and forty times the share. Size is doing something and it is plainly not doing all of it.

And on the rhombille the pattern’s own lettering closes a circle of sixteen panels. That patch has been drawn correctly, cut out of the plane correctly, and every one of its hundred and twenty-six interior vertices passes every condition the subject has. It has no flat folded state, and one pass over its crease list says so.

Nothing else could have said so #

The ordering search cannot be run on a hundred and fifty-seven panels. It cannot be run on fifty-two: the waterbomb tessellation is refused. The number of orders of a hundred and fifty-seven panels is past anything with a name, and no pruning changes the shape of that.

Every other refusal this collection owns is either local — the conditions at a vertex, which the rhombille patch passes — or geometric. The panels do not close is the refusal that catches a pattern whose two routes to the same panel disagree, and the patch closes to five parts in a quadrillion. The vertex the list does not have catches a pattern with two creases drawn across one another, and the clipped patches have none.

The last figure is the honest half of the claim, and it is worth more than the first. The forced order is not a decision procedure. It is a proof of failure when it fires and silence when it does not, and it can be silent about a pattern with no folded state — four of the six meshes above are exactly that. A collision is an order established that those four cannot be stacked, and it took a search over every ordering of nine panels to establish it. The letters of all four agree with themselves perfectly.

So there are two refusals here that refuse different patterns, not a fast one and a slow one. That is worth its own essay and it gets one.

Why the number can be believed #

The share of consistent letterings is a sampled number, and the sampler is not uniform. What is randomised is the search — the branch order of a constraint propagation — so each draw is a solution of the same constraint problem rather than a point drawn evenly out of the set of solutions. A share computed that way is a share of what the sampler found and nothing more, and the temptation is to divide it by something and call it a probability.

The check is available on three of the eight printed patterns, because three of them have few enough creases to enumerate every lettering.

The square twist has 4,096 letterings, of which 256 pass every vertex condition and 252 have no circle. That is 98.4 per cent exhaustively; the sampler says 98.75 per cent over four hundred draws. The preliminary base and the fold-and-cut triangle are 100 per cent both ways. Three agreements are not a proof that the sampler is unbiased on a patch of two hundred and eighty-two creases, and the essays that use these numbers say so. They are the difference between a number with a check behind it and a number with nothing behind it.

What the calibration actually rules out #

Three agreements are not a proof, as the section above says, and it is worth putting a size on how much they are — because “the two numbers differ by at most a third of a point” reads as a tight agreement and the right question is tight against what.

The square twist’s share is 252 of 256, or 98.44 per cent, and the sampler reports 98.75 over four hundred draws. With a share that high and four hundred draws, the standard error on the sampled figure is $\sqrt{p(1-p)/n}$, which is 0.62 percentage points.

So the observed discrepancy of 0.31 points is half a standard error. The two numbers agree, and they would have agreed just as well if the sampler carried a bias of half a point in either direction, because four hundred draws cannot see one.

Which sets the size of the claim #

Running that backwards says what the calibration establishes, which is a narrower and more useful statement than “it checks out”.

At two standard errors, four hundred draws detect a bias of about 1.3 percentage points and nothing finer. So the check rules out a sampler that is wrong by more than about a point and a half on this pattern, and is silent about anything smaller.

That is the right amount of confidence for the use the number is put to. The shares this essay reports range from 100 per cent down to nothing, and the differences that carry its argument — ninety-five per cent against thirteen, thirteen against zero — are two orders of magnitude larger than the bound. A bias the calibration cannot see is a bias too small to change any sentence here.

Where it would matter is a comparison between two patterns a point or two apart, and this essay makes none. The one place the temptation arises is the printed shelf, where the square twist at 98.75 and the Yoshimura at 95 sit close enough that the ordering could in principle be a sampler artefact — and that comparison is not load-bearing anywhere, which is worth saying rather than leaving for a reader to worry about.

The general form is worth carrying, because a sampled share against an exhaustive one is a check this collection makes in several places. An agreement is only as strong as the sample’s resolution, and reporting the agreement without the resolution invites the reader to believe a precision that four hundred draws does not contain.

What the circle is not #

Three things it would be easy to read into this and each is wrong.

It is not a statement about the drawing. Two creases drawn across one another is a defect in the ink, and reading a pattern that way is a separate instrument with separate findings. A patch can be perfectly drawn, with no crossing anywhere, and still carry a circle. The clipped patches are exactly that case.

It is not the same as the panels failing to close. Closure is about where the paper lands: compose the reflections round a loop of panels and see whether the composition is the identity. That is a question about geometry and it is answered before any letter is consulted. The circle is about the letters and is answered after the geometry has already succeeded — a pattern whose panels do not close has no folded state to order, and the test refuses it rather than reporting on it.

And it is not a sufficient condition for anything. No circle means the letters are consistent among themselves. It says nothing about whether two panels can be got past one another, which is what the non-crossing rules are for, and what a checker cannot check is the standing account of how much room is left.

The shape of a cheap refusal #

There is a pattern in which tests are worth having, and it is not the pattern intuition suggests. A test that decides everything is worth a great deal and there is not one. A test that decides nothing is worth nothing. In between sit tests that are sound in one direction — they never say no folded state about a pattern that has one — and the useful ones are the sound tests that are also cheap enough to run on inputs the complete test cannot be run on at all.

The order the refusals come in ranked five of them by cost and by what each says no to first, and this one belongs in that ladder near the bottom: cheaper than everything but the crossing sweep, and firing on patterns the vertex conditions pass in silence. It also has a property none of the others has. When it fires it hands back the reason — a named list of panels, each of which must lie below the next — and a reason is something a person can look at and act on.

It also sits at a particular place among the populations this collection tests its machinery on, and the place is unflattering.

Not one member of any of the four is refused by its own letters. Every one of them was drawn by a construction that produces a lettering, and the letterings those constructions produce are consistent — so a test set assembled entirely out of constructed patterns is a test set on which this refusal can never fire. That is not a criticism of the test; it is a criticism of the population, and it is the reason the numbers above are taken over letterings drawn again rather than over the patterns as they stand.

That last part turns out to matter more than the cost. A patch that fails a vertex condition can be repaired at the vertex; there is somewhere to go. A patch that carries a circle has a fault distributed over a region, and the circle the search reports is the smallest visible corner of it. How large the fault really is, and what would have to change to remove it, is the next thing to measure.

Where this leaves the patches #

Four tessellation patches that this collection can draw, print and hand to a reader place perfectly, satisfy every condition at every vertex, and have no flat folded state with the letters they carry. That is a stronger verdict than the one they had, and a more useful one: the drawing was the fault before, and a drawing can be redrawn, but the letters are what is wrong now and the letters are chosen rather than constructed.

Which means the question has moved to one about choice. Twenty-six letterings of two hundred work on the square patch, none of two hundred on the rhombille, and the difference between those two numbers is the subject of the essays that follow. So is the reason the printed patterns almost never fail this test while the patches almost always do — which turns out not to be a matter of size at all, and to be settled by a theorem two centuries older than anything else in this collection.