How many assignments fold

A crease pattern is a set of lines. Creasing it means choosing, for each line, whether the paper turns one way or the other — a mountain or a valley — and a pattern with $E$ creases therefore has $2^E$ possible assignments. Most of them are nonsense. The interesting question is how many are not, and the answer is more revealing than it first appears.

Two numbers come out of that census, and they point in opposite directions. The share that survives falls as the pattern grows: a single vertex keeps a quarter of its assignments, a nine-panel Miura keeps a sixteenth. The count that survives rises: four assignments become two hundred and fifty-six. Both are consequences of the same arithmetic, and holding both in mind at once is the whole content of this essay.

What is being counted #

The conditions are the local ones, and they are exactly the conditions of the two theorems at a point plus the one that came after them.

At every interior vertex, the sectors must sum to a full turn — that is developability, and it is a property of the pattern rather than of the assignment, so it is settled before any counting starts. Alternating sectors must sum to a straight angle: Kawasaki, again a property of the angles alone. Then the two conditions that do depend on the assignment: the difference between mountains and valleys must be exactly two, and a strictly smallest sector must not be flanked by two creases of the same letter.

So the census counts assignments passing Maekawa and big-little-big at every vertex simultaneously. Nothing else. In particular it does not ask whether the sheet folds.

The enumeration is exhaustive up to about twenty creases, which is where $2^E$ stops fitting in a reasonable amount of work. Every count in the figure is produced by generating each assignment in turn and testing it, so there is no approximation anywhere and no sampling: the numbers are the numbers.

The share falls, and why #

Start with one degree-four vertex. Sixteen assignments; Maekawa allows the three-and-one splits in either direction, which is $\binom{4}{1} + \binom{4}{3} = 8$; big-little-big removes half of those, leaving four. A quarter survives.

Now put two such vertices side by side, sharing a crease. Each has four valid assignments of its own four creases. If the two vertices were independent, there would be sixteen ways to combine them. They are not independent — the shared crease has to carry the same letter in both — so the count is smaller, and the exact figure depends on how the two vertices’ valid sets happen to overlap on that crease.

That is the mechanism in miniature. Every additional vertex multiplies the space of assignments by $2^{\text{new creases}}$ and multiplies the surviving set by something smaller, because each vertex’s conditions constrain creases its neighbours have already constrained. The share therefore falls geometrically in the number of vertices.

A nine-panel Miura has twelve interior creases and four interior vertices, and keeps $256$ of $4096$: one in sixteen. Extrapolating the same rate, a modest tessellation with fifty vertices keeps something in the region of one in $10^{15}$.

The count rises anyway #

Here is the part that undoes the comfort of the previous paragraph. One in $10^{15}$ of a very large number is still a very large number.

Take the two figures together. The share falls by a factor of four from the single vertex to the nine-panel Miura; the count rises by a factor of sixty-four. A filter that discards fifteen sixteenths of its input while its input grows by $2^{12}$ has not narrowed anything in the sense that matters to somebody who has to check the survivors one at a time.

This is the shape of every strong necessary condition in a combinatorial subject, and it is worth naming rather than discovering repeatedly. A test that removes a constant fraction at each step leaves an exponentially large remainder. To get down to a manageable set, a test has to remove a growing fraction — and the local conditions do not, because each vertex sees only its own creases and there are only so many ways to be wrong about four of them.

Two conditions doing different work #

It is worth separating the two assignment-dependent conditions, because they fail differently and a census that lumped them together would hide it.

Maekawa is arithmetic. It counts letters and compares the counts, and it knows nothing at all about where the creases are. Applied to a degree-four vertex it accepts eight of sixteen, and applied to a degree-eight vertex it accepts a hundred and twelve of two hundred and fifty-six — in both cases a little under half, because the binomial coefficients near the middle of a row are where most of the mass sits. Maekawa’s rejection rate is therefore roughly constant as the vertex degree grows, which means that on its own it is a weak filter and gets weaker.

Big-little-big is geometry. It looks at which sector is strictly the smallest and asks what flanks it, and its bite depends entirely on the angles. At a degree-four vertex with sectors of 40°, 110°, 140° and 70°, one sector is strictly smallest and the condition halves what Maekawa left. At a vertex with four equal sectors nothing is strictly smallest, the condition has no subject, and it removes nothing whatever.

That is a real asymmetry and it explains the shape of the census. The patterns whose share falls fastest are the irregular ones, where many vertices have a strictly smallest sector and big-little-big fires at each of them. The patterns whose share falls slowest are the symmetric ones — and the symmetric ones are the ones anybody wants to fold.

There is a converse worth stating too. A vertex whose sectors are all distinct is a vertex where the conditions are strongest, so a designer who wants a pattern whose valid assignments are few and findable should avoid symmetry. That is the opposite of what the aesthetics of the subject suggest, and it is the sort of thing a census makes visible and a proof does not.

The per-vertex factor, read off the census #

The claim that symmetric patterns lose their share most slowly has an exact size in the figure’s own numbers, and extracting it is worth a paragraph because it puts a factor on the asymmetry between the two conditions.

A single degree-four vertex keeps four of sixteen: a factor of four per vertex. The nine-panel Miura has four interior vertices and twelve creases, and keeps two hundred and fifty-six of four thousand and ninety-six — which is two to the twelfth over two to the fourth, a factor of two per vertex.

So the Miura’s vertices cost half of what the generic vertex costs, and the reason is the one the essay gives: a Miura’s sectors come in two equal pairs, so no sector is strictly smallest, and the big-little-big lemma has nothing to act on. Maekawa alone halves; the lemma would have halved again.

A generic pattern loses a factor of four per vertex and a Miura loses two, and the difference compounds. Four vertices at the generic rate would leave one assignment in two hundred and fifty-six; the Miura leaves one in sixteen.

Which the extrapolation quietly assumes #

That also says how to read the essay’s own forecast. Fifty vertices keeping something like one in $10^{15}$ is two to the minus fifty — the symmetric rate, carried out fifty times.

At the generic rate, fifty vertices would keep one in $10^{30}$, which is a different number by fifteen orders of magnitude. So the extrapolation is the optimistic one, and it is optimistic in the direction that matters: it is the rate for the patterns anybody folds.

The two rates bracket what a real pattern does, and which end it sits at is decided by how many of its vertices have a strictly smallest sector. That is a property a designer can read off a drawing with a protractor — count the vertices where three sectors differ and one is smallest — and it predicts, to within a factor of two per vertex, how hard the pattern’s assignments will be to sift.

Where the counting stops being the point #

The preliminary base makes the limitation concrete. Eight creases meet at its centre in equal sectors, so no sector is strictly smallest and big-little-big has nothing to forbid. Maekawa alone survives, and it allows $\binom{8}{3} + \binom{8}{5} = 112$ of $256$ — nearly half.

One hundred and twelve assignments pass every local test. One of them is the preliminary base. The others are, for the most part, sheets that cannot be folded at all — the paper collides with itself somewhere away from the vertex, which is a fact about the whole sheet and invisible at the point where the counting happened.

Equal sectors are not a pathological case chosen to embarrass the method. They are what a symmetric pattern looks like, and symmetric patterns are what the traditional repertoire is made of. The conditions are weakest exactly where the interesting patterns live.

Which theorem was checked, and how #

The counts in the figure come from an enumerator which builds every assignment in turn and calls the same checker every generator on this site calls before it is allowed to draw. There is no separate implementation for counting, which matters: if the counting used a looser test than the drawing, the census would be reporting on something other than what the site verifies.

The figure asserts two things before it draws anything. Every case must reject at least one assignment — a condition that accepted everything would be worth nothing and the figure should not be able to claim otherwise. And the last case must have both a smaller share and a larger count than the first, because that conjunction is the argument; a figure that showed the share falling and the count falling too would be showing a decision procedure, and this is not one.

The check that would catch a lie here is the second one. It fails loudly if the cases are ever reordered or replaced in a way that breaks the pattern, which is exactly the edit somebody would make without noticing what it cost.

What the picture cannot show #

The census counts assignments that pass a local test. It says nothing whatever about which of them fold.

Every survivor still has to satisfy the global condition — the layers have to stack without passing through one another — and that condition is not local, is not visible at any vertex, and is NP-hard to decide in general. The figure’s bars are upper bounds on something they do not measure.

There is a second, quieter limitation. The enumeration is exhaustive only while $2^E$ is small. Past about twenty creases the census would be a sample rather than a count, and a sample of a set this sparse is nearly useless — a uniform sample of assignments for a fifty-vertex pattern would find a valid one roughly never. Every number in the figure is a genuine count, and the reason the figure stops where it does is that the next number would not be.

What a designer does instead #

Nobody who designs a crease pattern enumerates its assignments. The census is a statement about the difficulty of a problem, not a description of a practice, and the practice is worth a paragraph because it shows what the difficulty is actually made of.

A designer builds a pattern out of pieces whose assignments are already known. A bird base is a preliminary base with two of its flaps narrowed, and the narrowing is a local operation that changes a known assignment in a known way; a box-pleated limb is a sequence of pleats whose letters alternate by construction. Designing on a grid is popular for exactly this reason: on a grid the vertices are all of a few types, each type’s valid assignments are memorised, and the design question becomes which type to put where.

That is not a shortcut around the counting problem. It is a restriction of the problem to a subclass where the answer is already known, which is what almost every practical response to an intractable problem turns out to be. The same move appears in the one-dimensional case, where restricting the sheet to a strip makes the whole question — assignment, layers and all — decidable in time proportional to the number of creases.

The census is the measurement that says why the restriction is necessary. Without it, “the local conditions are a strong filter” and “the local conditions nearly solve the problem” sound like the same sentence.

The idealisation underneath #

Counting assignments treats a crease as a binary object: mountain or valley, with no third option and no degrees.

That is the third of the four things that are not true. A real crease can be folded partway, and a real pattern can be folded with some creases left flat — which the FOLD format acknowledges with an F assignment that this census does not count. Including it would raise every total from $2^E$ to $3^E$ and would raise the surviving count too, because a pattern that cannot fold flat with every crease used can sometimes fold flat with several of them ignored.

The census is therefore a count over a restricted alphabet, and the restriction is the ordinary one: a crease pattern is a set of creases all of which are meant to be folded. It is worth naming because the restriction is invisible in the arithmetic.

The surprising connection #

The same shape turns up in a place with no paper in it at all.

A propositional formula in conjunctive normal form has $2^n$ truth assignments, and each clause removes a constant fraction — one eighth for a three-literal clause. Adding clauses shrinks the share geometrically and the surviving set stays exponentially large until the ratio of clauses to variables passes a threshold, at which point it collapses to nothing very suddenly. That transition is one of the most studied objects in the theory of computation, and it has the same two-numbers-in-opposite-directions structure as the census above.

The resemblance is not decorative. The reduction that makes flat-foldability NP-hard turns satisfiability instances into crease patterns, so the two counting problems are the same problem in different clothes. A crease pattern is a formula, once somebody has noticed how to read it as one.

Where the numbers came from #

The two conditions being counted arrived thirty years apart and from different directions. Maekawa’s is folklore attributed to Jun Maekawa and independently to Jacques Justin, published in the 1980s; Kawasaki’s condition dates from the same period, with Justin again having it early. The big-little-big lemma is later and is due to the systematic study of flat-foldability that Bern and Hayes began and that Demaine and O’Rourke set out in full.

The counting itself is not attributed to anybody, because it is arithmetic. What is attributed is the observation that the arithmetic does not settle the question — and that is the content of the hardness result, which came in 1996.

The ladder from here #

This rung establishes that the local conditions are a strong filter and not a decision. The next asks what the residual difficulty actually is, and the answer is that it is the layer ordering — which is where the hardness lives and where a whole reduction can be built.

The rung after that leaves flat-foldability behind and asks the same counting question about a different object: how many ways a ruled rectangle folds, which is not a question about assignments at all, has been open since 1968, and has no formula.