How little the conditions decide

Local is not global is the load-bearing sentence of this field, and it is a statement about sufficiency. Every vertex of a pattern can satisfy every condition the subject has and the sheet can still fail to fold, because the conditions do not see the layer order and the layer order is where the difficulty lives.

There is a second complaint to make about the same conditions, and it is about strength. Never mind whether they are sufficient. Ask how much they entail.

The experiment #

Take a crease pattern whose angles are fixed. Choose one crease and call it a mountain. Then apply every condition the subject has, over and over, and see what follows.

The procedure is the one a constraint problem is solved with, and it is worth writing out because the measurement is a measurement of it. At each interior vertex, enumerate the labellings of that vertex’s own creases that satisfy Maekawa’s three-to-one split and the big-little-big lemma — sixteen candidates at a four-crease vertex, of which typically four survive. Where every surviving labelling of a vertex agrees about one of its creases, that crease is settled. Settling it prunes the neighbours’ lists, which may settle more. Repeat until nothing changes.

That is propagation, and what it returns is what the conditions entail — a smaller and much steadier thing than what a search can find, because a search is allowed to guess and propagation is not.

The numbers #

On a patch of square twist tessellation with a hundred and fifty-eight creases in its interior, fixing one settles three. Sixty-six interior vertices are still holding more than one labelling when the propagation runs out.

On a six-by-four Miura with thirty-eight interior creases, fixing one settles one — itself. Fifteen vertices are still choosing.

On a four-by-four waterbomb patch with seventy-six, fixing one settles one, and twenty-five vertices are still choosing. On a Yoshimura corrugation, one of eighty-four. On the preliminary base — a pattern with a single interior vertex — one of eight, and that vertex is still holding several labellings.

Nothing spreads. That is the finding, and it is uniform across every pattern this site draws — regular and irregular, small and large, corrugations and tessellations.

It is worth stating what is not being claimed. The conditions are not weak in the sense of admitting rubbish: a random pattern fails them comprehensively, and almost every set of angles fails Kawasaki at every vertex it has. They are extremely strong as a filter. What they are not is productive: they reject a great deal and they generate almost nothing.

Why the expectation was wrong #

It is worth being clear about the intuition this contradicts, because the intuition is a good one and it works elsewhere.

In most constraint problems that people meet, fixing one variable cascades. Choose a digit in a sudoku and a dozen cells follow. Set one crease of an accordion and every crease follows, because an accordion’s vertices are so tightly constrained that one determines the next.

The intuition fails here because a four-crease vertex is loose. It has sixteen labellings; Maekawa takes it to eight; the big-little-big lemma takes it to four, or leaves it at eight if two of its sectors happen to be equal. Fixing one of the four creases leaves two labellings — and two labellings that disagree about the other three creases settle nothing about them.

So the vertex passes nothing on. The propagation stalls at the first vertex it reaches and stays stalled.

An accordion is the instructive contrast because it is the case where the intuition holds. Its vertices are degenerate — the creases are parallel and the “vertices” are the ends of segments rather than points where four creases meet — and its letters do propagate, all the way down the strip. That is why an accordion feels like the simple case: it is the one where knowing a little is knowing everything.

Two dimensions are not one dimension with more of it. The two directions of a map do not separate, and neither do the two directions of a tessellation: what looks from a distance like a row of accordions is, at each vertex, a four-crease object with four answers.

Loose is not quite the reason #

The explanation offered above is that a four-crease vertex is loose — sixteen labellings cut to four, and fixing one crease leaving two that disagree about everything else. The first half of that is right and the second is not, and working it through changes what the finding is about.

Take a vertex with a strictly smallest sector, flanked by creases one and two. Maekawa admits the eight labellings that split three-and-one; the lemma demands that creases one and two differ, which holds exactly when the odd crease out is one of that pair. Four labellings survive, and they are: crease one alone is a mountain; crease one alone is a valley; crease two alone is a mountain; crease two alone is a valley.

Now fix crease one as a mountain. Two of the four survive — one alone is a mountain, and two alone is a valley — and in both of them crease two is a valley. So the propagation does not stall: fixing one crease settles its partner across the smallest sector, and creases three and four are left open. Fix crease three instead and the same thing happens the other way round: four follows, one and two stay open.

A generic degree-four vertex therefore passes a decision on. Not to all its neighbours, but to one, and one is enough to cascade — the partner crease has a far end at another vertex, which then has one crease fixed and passes it on again.

Which means the stall is about ties #

If a generic vertex propagates and the measured patterns do not, the patterns are not generic. And they are not.

A Miura’s vertex has sectors of $\alpha$, $\pi - \alpha$, $\alpha$, $\pi - \alpha$ — two sectors tie for smallest, so no sector is strictly smaller than both its neighbours and the lemma has nothing to say at all. Maekawa alone leaves eight labellings rather than four, fixing one crease leaves four, and those four disagree about every other crease. Nothing is settled and nothing is passed on.

That is the mechanism, and it accounts for the numbers as reported rather than contradicting them. The Miura settles one crease of thirty-eight because every one of its vertices is tied. The twist tessellation settles three of a hundred and fifty-eight because a handful of its vertices are not.

So the finding is sharper than the conditions are weak. The conditions are weak on the patterns anybody folds, because those patterns are built out of tied vertices, and a tie is exactly where the one condition that compares angles falls silent. A pattern drawn at angles nobody chose would propagate; a pattern drawn by halving, by tiling, or on a grid does not, because all three produce equalities.

That also says what would change the answer, and it is not a stronger condition. It is a different population. Draw the same tessellation at angles that break its ties — a Miura whose parallelogram is not symmetric about its straight crease — and the propagation should run, at no cost in machinery and a considerable cost in everything else the symmetry was buying.

What was decided before any of this #

The contrast makes the result sharper rather than softening it, and it is the reason the subject works at all.

The angles are settled completely, and they were settled before a letter was written. Developability and Kawasaki are conditions on the sector angles alone; a pattern either satisfies them everywhere or it does not, and no choice made about mountains and valleys can change the answer. The lengths of the creases are free and the angles are not, and the whole of that question is closed by the drawing.

What is left after the angles is the letters, and the letters are what the propagation cannot get at. So the subject’s two halves behave in opposite ways: the geometric half is decided and rare, and the combinatorial half is undecided and abundant.

What a search does that propagation does not #

A search finds assignments. It finds them on all of these patterns, quickly, and this site’s figures rely on it. The gap between what a search finds and what propagation entails is exactly the amount of guessing involved.

The search branches: it picks the vertex with the fewest labellings left, assumes one of them, and propagates again. On the tessellations here the branching is what does the work, and the propagation between branches contributes very little. That is a completely legitimate way to solve a problem and it produces correct answers, and it means something specific about the result: the assignment a solver returns is a choice among many rather than a consequence of the pattern.

This is the practical form of the finding. A folder handed a crease pattern with one crease marked has not been told very much. A folder handed a pattern with every crease marked has been told something the pattern itself does not contain — which is why notation records the letters and not merely the lines, and why leaving them off is not a small omission.

A second reading: how far the conditions see #

There is a way of quantifying the same thing that has a more physical feel to it.

Ask how far a decision propagates in distance rather than in count. On these patterns the answer is: to the vertex it was made at and no further. The conditions have a horizon of one vertex. A pattern is a large object made of small objects that are individually loose and that do not communicate.

That is not a contradiction of what the tessellation essays found. A patch of a repeating pattern does carry conditions that a single unit does not, because the patch contains vertices the unit does not contain. What it does not do is transmit a decision: the extra conditions are extra local demands, not a channel.

The one place it does propagate #

There is an exception, and it is small and worth having because it shows what would be needed for the rule to be otherwise.

A vertex whose sectors force it into a single labelling does pass its decision on. Such vertices exist: a four-crease vertex with a very small sector flanked by a very large one on each side is constrained hard enough by the lemma that, once one of its creases is fixed, the other three follow. Chains of them propagate.

What no pattern in ordinary use is made of is vertices like that. Halving produces equal angles, and equal angles are the case where the lemma says least; tessellations repeat one vertex, so if that vertex is loose the whole sheet is loose. The patterns that would propagate are the ones nobody draws.

What a stronger condition would have to look like #

It is worth asking what would have to be true for the propagation to work, because the answer says something about why the subject is shaped as it is.

Propagation succeeds when a vertex, given one of its creases, has only one surviving labelling. A four-crease vertex has four labellings after Maekawa and the lemma, and fixing one crease halves that to two. To get to one, a vertex would have to be constrained by something the subject does not currently have — a condition relating a vertex to its neighbours rather than to itself.

Such conditions exist. Layer ordering is one: whether two panels can be stacked depends on both of them, and the taco-taco and taco-tortilla rules are demands about pairs. They are not used in the propagation above and they could be, and a propagation that used them would settle more.

The reason they are not is the reason the whole subject is arranged as it is: the moment layer ordering enters, the question stops being decidable by any local procedure, and deciding it in general is NP-hard. The local conditions are weak because weak is what a local condition can be, and buying strength means buying the hard problem.

Where the model stops #

Propagation is not the strongest form of entailment. A cleverer inference — reasoning about pairs of vertices at once, or about the whole sheet — might settle more. What is measured is what the conditions the subject actually states entail under the standard procedure, and it is an honest lower bound rather than a theorem.

Choosing a different starting crease changes little. The measurement fixes one interior crease; starting elsewhere gives the same shape of answer on these patterns, because the reason nothing spreads is a property of the vertex rather than of the crease.

The count of vertices still choosing is not a count of assignments. Sixty-six vertices each holding two or more labellings does not mean the pattern has two to the sixty-sixth assignments: the vertices share creases and their choices are not independent. Counting the assignments exactly is a much harder question and is not attempted.

None of this decides whether the sheet folds. Every condition used is local and deciding the global question is NP-hard. Propagation settling little is a statement about the conditions, not about the paper.

Why this is the useful complaint #

The two complaints about locality sit at different distances from practice.

Not sufficient is the one the literature makes, and it is answered by pointing at the layer order and at the reductions that make the general problem hard. It is a statement about the worst case and about the outer limits of what can be decided.

Not strong is a statement about the ordinary case, and it is the one a person writing folding software runs into. A checker that applies the vertex conditions to a fully marked pattern is doing useful work: it rejects a great many wrong patterns cheaply. A tool that tries to complete a partly marked pattern from those conditions will get almost nowhere, and will have to search — and the search will find many answers rather than one, and choosing between them is not something the conditions can help with.

What it says about how patterns get made #

If the conditions entail so little, the marked patterns that exist have to have come from somewhere else, and it is worth asking where.

Three sources account for nearly all of them. Construction: a pattern built by an algorithm — a packing turned into creases, or a tiling turned into a twist — arrives with its letters already fixed by the construction rather than chosen afterwards. Folding: a pattern obtained by actually folding paper has letters supplied by the folding, which is why a sheet folded at random satisfies every condition everywhere while a sheet drawn at random satisfies them essentially nowhere. Search: a solver picks one of the many, and that is a decision the solver made.

Only the third of these is a choice among alternatives, and only the third produces an answer that could reasonably have been different. That is a useful thing to know when reading a published pattern: the letters may be a consequence, or they may be one solver’s opinion, and the pattern does not say which.

Where the ladder goes next #

The obvious continuation is the count the measurement above deliberately does not attempt: how many assignments a pattern actually admits, which needs a way of counting solutions rather than finding one. That number would say what “the letters are undetermined” is worth in each case, and it is a genuinely different piece of machinery from anything this site has.

The other direction is a comparison. If the vertex conditions entail so little, something else must be doing the work when a folder marks a pattern by eye — and the candidates are symmetry, habit, and the constraint that the model has to look like something. None of those is a theorem, and it would be worth knowing how much of a real pattern’s marking they actually fix.