More than one way to lie flat

There is a phrase everybody in the subject uses, this site included, and it hides an assumption. The folded state. The definite article does a great deal of work.

A crease pattern with its mountains and valleys marked settles where every piece of paper lands. It does not settle which piece lies over which, and where there is a choice about that, there is more than one folded object with a claim to the same drawing.

In one dimension the choices can be counted exactly, and the count is usually not one.

What a marked crease pattern actually names #

The division is worth restating precisely, because everything here depends on it.

The crease positions fix the footprint. Fold along a line and everything on one side reflects; repeat, and there is a map from the flat strip to the line which never consults a letter. The assignment fixes, at each crease, which way that U-turn wraps — whether the paper turning back goes over or under the paper it is turning away from.

Neither of those says anything about two pieces of paper that overlap without sharing a crease. On an evenly creased strip every segment lands on every other one, so most overlapping pairs are of exactly that kind: they are stacked together with nothing local relating them. Their order is settled — if it is settled at all — only by whether the choice can be made consistently with every other choice.

Two folds at the same place may nest or stand clear, and may not interleave. A flat layer may pass outside a fold and may not pass through it. Those two rules — the taco-taco and taco-tortilla conditions — are the whole of what constrains the ordering, and constraining is not deciding. A set of constraints can admit many orderings, or exactly one, or none.

The three piles in the first figure are therefore identical in every measurement a folded state is usually described by. They occupy the same interval, they are four layers deep everywhere, and the shrink and the mean depth multiply to the sheet by the same arithmetic in all three. Anything computed from the footprint cannot tell them apart, because the footprint is precisely the part they share.

Eight ways to mark three creases #

Three creases have eight assignments. Running every one of them past the layer solver gives a census, and the census is the essay.

The counts, in order, are 3, 2, 1, 2, 2, 1, 2, 3. Not one of the eight is unfoldable — even spacing lets every assignment through, which is the one-dimensional result this site has already established from the other direction. And only two of the eight name a single object. For those two the phrase the folded state is correct. For the other six it is simply wrong.

Nothing in the drawing distinguishes the cases. VMV and MMV differ in one letter; the first names a folded object and the second names two of them.

That figure demonstrates the habit this essay argues against. It is a picture of a folded strip, and it is a picture of one of three, and the only reason the second sentence is visible is that the count happens to be printed in the corner.

That single stacking is the plain accordion, and its uniqueness is the exception rather than the rule. It is also the reason the mistake survives: the accordion is the folded strip everybody pictures, and it is one of the two cases in eight where picturing one object is right.

Counted by objects rather than by markings #

The census reads 3, 2, 1, 2, 2, 1, 2, 3, and two things about that list are worth extracting before moving on.

It is a palindrome, and it is unchanged by swapping every letter — MMM against VVV at three apiece, MVM against VMV at one. Neither is a coincidence: reversing the strip end for end and turning it over are both symmetries of the object, so a count that failed either would be a count of the implementation rather than of the paper.

And the eight numbers sum to sixteen. Three creases admit eight markings and sixteen distinct folded objects, a mean of two apiece.

Which makes the error larger than it looks #

That total changes the size of the claim. Counted by markings, two of eight name a single object, so the definite article is right a quarter of the time.

Counted by objects, only those same two are unambiguously named, and the other fourteen each share their drawing with at least one sibling. Seven eighths of the folded strips that exist here are objects no crease pattern picks out.

The second figure is the honest one, because a reader meets folded objects rather than markings — and it says that a picture of a folded strip captioned with its crease pattern is, seven times in eight, a picture of one of several things the caption equally describes.

The count is not the number of assignments that fold #

The two quantities are easily confused, because both are counts about the same drawing, and they answer different questions.

How many assignments fold asks how many of the ways of marking a set of creases admit any folded state whatever. The census here asks, for one marking, how many folded states there are. The first is a count over drawings; the second is a count over objects behind a single drawing.

They move independently, and on even spacing they move in opposite directions. Even spacing lets every assignment through, so the strip scores perfectly on the first count — and it is exactly the spacing on which the second count is largest, because every segment lands on every other one and the constraints have the most room to be satisfied in several ways at once.

What grows, and what does not #

Push the crease count up on an evenly spaced strip and both quantities can be computed exhaustively.

The assignments go 2, 4, 8, 16, 32, 64, which is what doubling looks like and is entirely uninteresting. The stackings go 2, 6, 16, 50, 144, 462. At six creases the busiest single assignment admits eleven piles on its own.

Since every assignment of an evenly creased strip folds, the entire difference between those two sequences is the thing the marked pattern failed to say. Six creases carry six bits of assignment and need rather more than six bits to name what the drawing is a picture of.

This is where the surprise sits, and it took the check to notice it.

The stamp-folding numbers are the sum over assignments of the stacking counts. That is not how map folding is usually defined. The classical question asks in how many ways a strip of stamps can be folded into a pile, and it is posed entirely in terms of which edges wrap round which — there is no crease pattern in it and no mountain or valley anywhere. Coming at the same integers from the other end, by fixing a marking, counting piles, and adding up over markings, is a different computation that shares no code with the first and lands on 2, 6, 16, 50, 144, 462 exactly.

It also explains why the multiplicity has never had a name. The quantity these counts sum into is one of the oldest open problems the subject has, and the tradition around it counts total foldings and has no reason to partition them by marking. From that side the per-assignment counts are an implementation detail of somebody else’s sum. From the folding side they are the answer to the question a folder actually has, which is what a particular drawing is a picture of.

Which count was checked, and how #

The claim being made is a count, and a count is the easiest kind of measurement to get quietly wrong, because a search that misses cases returns a smaller number rather than an error.

So the layer solver is never trusted on its own. Its total, summed over every assignment of an evenly creased strip, is compared term by term against the map-folding enumerator, which counts stackings of a strip of stamps directly from the wrapping edges. The two share no line of code, and the figure refuses to draw if any term disagrees. It also refuses if the totals ever fall as the crease count rises, because a non-monotone sequence would mean the search was giving up somewhere rather than exhausting.

The census figure asserts something narrower and more specific: that the set of assignments it draws contains at least one admitting more than a single stacking and at least one admitting exactly one. That is the figure’s whole claim, and a set in which every assignment behaved the same way would illustrate nothing while looking convincing. Given creases where that fails, the generator stops and prints what each assignment came to.

There is a third check, and it is what makes each drawn pile legible. Beside every stacking the figure names the rule that the nearest illegal pile breaks — the one reached by swapping two neighbouring layers. A picture of a legal pile and a picture of an illegal one look identical, so what is printed is the constraint holding this one in place. Two of the three piles in the first figure are held there by taco-taco.

The counting here is brute force, and deliberately so #

The layer solver used throughout is an exhaustive search over orderings of the segments. At four segments that is twenty-four orderings, at seven it is five thousand and forty, and at these sizes the honest description is that the machine tries everything.

That is a choice, not a limitation being hidden. Deciding whether a one-dimensional pattern folds has a linear-time algorithm in the literature, and it is a genuinely different object: it constructs a folded state rather than filtering candidates, and it answers the decision question without ever producing a count. Enumeration is not decision run repeatedly, and the cost of enumerating a set is a question about algorithms rather than about paper — a subject with its own results, which this site quotes and does not develop.

The ceiling is close, and it is worth being blunt about where it sits. Seven creases means eight segments, forty thousand orderings per assignment and a hundred and twenty-eight assignments, which is several seconds of a page build for one more term. Six is where the figures stop — not because the search fails there, but because these figures are drawn every time a page is built. That the sequence keeps going, and keeps going at a rate whose base nobody has proved exists, is a separate matter.

What matters is that at three, four, five and six creases the counts are complete rather than sampled, and that they agree with a second method. A number arrived at twice is worth more than a number arrived at quickly.

Where the model stops #

Three limits deserve naming, and the second is the one the figures cannot show.

These are strips. In one dimension the overlaps form a chain, and chains have no cycles, which is exactly why the question is decidable here. In two dimensions the constraint graph can contain cycles, the count is not obtainable this way at any interesting size, and the decision question alone is NP-hard. Everything above is a fact about one dimension, and the multiplicity in two dimensions is real but is not this number.

An ordering is a folded state only when everything overlaps, and this is the limit that turned out to be a defect rather than a caveat. The obvious way to count the stackings of a strip is to enumerate total orders of its segments and keep the legal ones. That is exactly right on an evenly creased strip, where every segment lands on every other one, and it is what the layer solver behind these figures did for its whole life — because every strip anybody had asked it about was even.

Move the creases apart and it stops being right. Two segments that never lie over one another are not stacked in any sense a reader could check: swapping them leaves every layer of paper exactly where it was. Two total orders differing only there are one folded state, and counting them as two inflates the answer.

The distinction cost nothing anywhere else, and that is worth stating precisely rather than waving at. On evenly spaced creases every pair of segments overlaps, so no pair’s order is unobservable and the two counts are equal — which is exactly why the published stamp-folding numbers were the right thing to check the solver against, and why the sequence above survives the correction untouched. The site’s own fold check now asserts both halves: that the counts agree on every even strip up to five creases, and that they do not agree on an uneven one.

So the even case is the one the numbers in this essay are quoted from, and it is also the classical one — the strip of stamps, where the folded state is a permutation because every stamp lands on every other. And the uneven case remains exactly right about zero: eight of those sixteen assignments have no legal stacking whatever, and no distinction between orderings and states rescues them.

A pile is not a folding sequence. A folded state that exists need not be reachable by any procedure a person or a machine would use.

There is a fourth idealisation, quieter than the others. The paper has no thickness. The piles in every figure are drawn with their layers separated so they can be told apart; in the model they are all at the same place, and the loops at the folds are bulges for legibility rather than radii. On real paper the three piles in the first figure differ in how hard they are to press, which is not a distinction this arithmetic contains.

Who noticed it, and when #

The counting question for strips of stamps is much older than the folding conditions and arrived from recreational mathematics rather than from paper. Stanislaw Ulam raised it in the 1960s, W. F. Lunnon computed the first values in 1968 and 1971, and the sequence has been in the standard integer-sequence tables ever since — with, notably, no closed form and no proof that there is none.

The layer conditions came from the other side. Jacques Justin set out the local conditions in 1986, the two forbidden crossings among them, and Marshall Bern and Barry Hayes’s 1996 paper turned the layer-ordering constraints into the source of the general problem’s hardness. Between those two lines of work sits the observation this essay makes, which is small enough that nobody appears to have written it down as a result: that summing the second over all markings recovers the first.

What is genuinely absent from the practice of the subject is the habit of quoting the number. A published crease pattern gives creases and letters. It does not say “this admits three folded states”, and the folder who works out which one was intended does so from a photograph, from a sequence, or by trying. The notation records the easy half and there has never been a convention for the other, which is a notation problem rather than a mathematical one and is no less real for that.

The diagram tradition solved the same problem by not having it. A dashed line and an arrow specify an action, and a sequence of actions arrives at one object with no ambiguity to resolve, because each step says which paper moves and therefore which paper ends up above. That is the trade between the two documents: a sequence is unambiguous and specific to one model, a crease pattern is compact and general and does not finish the job.

Where the ladder goes next #

The obvious continuation is the second dimension, where the count exists and cannot be had. That is where the ordering becomes a constraint problem with cycles in it, and where the difference between a hard decision and a hard count is the whole subject.

The other direction is back toward the drawing. If a marked pattern does not name a folded object, something has to, and the candidates are all worse than they look: a folding sequence is long and specific to one model, a photograph is not a specification, and a full layer ordering is a permutation nobody would print. What a crease pattern would have to carry is open in the useful sense that no convention has won.

And there is a smaller neighbour worth reading beside it. If the letters do not determine the folded state, and the crease lengths do not determine whether one exists, then a drawing says less about the object in the photograph next to it than it appears to from either direction.