The map counted from the layers

The oldest open problem in the subject is how many ways a rectangle of stamps folds flat, and this site has answered it for small rectangles since its fourth phase. The way it answered is worth restating, because it is a clever shortcut and this essay is about not taking it.

The shortcut is that a map’s layout is forced. Every cell of a folded map lands on the same square, and which way round each one lies is decided by parity: a cell is mirrored horizontally exactly when its column index is odd, and vertically when its row index is odd. Nothing is placed and nothing is solved. What is left is the stacking order, and the only condition on it is that two folds wrapping the same edge of the folded square must nest or stand clear rather than interleave.

That rule is complete, it is fast, and it reproduces Lunnon’s published counts. It is also entirely specific to maps.

The long way round #

The general machinery knows nothing about maps. Handed a crease pattern it places every panel by composing reflections, works out which pairs of panels share ground, writes down the non-crossing rules those pairs generate, and searches the orderings.

Run it on a map and it does all of that from scratch. It does not know the layout is forced; it computes each panel’s position and each panel’s orientation. It does not know the folds group by edge; it discovers that four crease images happen to lie along one line and generates the rules between them. It refuses nothing, assumes nothing, and takes about four hundred times as long.

The point is that it has no way to be right by construction. A count that comes out of it and matches a published number is a coincidence or a confirmation, and nine of them in a row is not a coincidence.

The one-row cases are the stamp-folding sequence 2, 6, 16, 50, 144. The two-row cases are 8, 60, 320. The three-by-three is 1368, which took a computer when it was first found and is the third term of a sequence whose fourth is 300,608 and whose fifth nobody knows.

A folding is a lettering and an order #

The middle column needs explaining, because the classical count has nothing corresponding to it.

The general machinery works from a lettering — which creases are mountains and which valleys — and finds the orderings that lettering admits. The classical rule works from an ordering and derives the letters from it. They are two halves of the same object: given a folded map, the order says which cell is above which, and the letters follow from comparing neighbours; given the letters, the order is constrained but not determined.

So a folding is a lettering together with an order, and the count is the sum over letterings of the orderings each one admits. On a three-by-three map, 4,096 letterings are possible, 256 satisfy the conditions at every vertex, and those 256 share 1,368 orderings between them — an average of five and a third each.

That decomposition is not available from the classical side at all, and it is the reason to have done the work twice. The count counts labels established that the classical numbers count records rather than objects; this establishes what a record is made of.

What the general machinery had to work out for itself #

It is worth listing what the long route recomputes, because each item is a place the shortcut has knowledge built in.

Where each cell lands. The parity rule — mirrored in x when the column is odd, in y when the row is odd — is a theorem about maps. The general route composes a reflection per crease along a spanning tree of the panels and gets the same answer without being told, and the disagreement between two routes to one panel is Kawasaki arriving from a direction it was not put in. On every map that disagreement is at the tenth decimal place or below.

Which pairs of panels share ground. On a map every cell lands on every other, so all pairs share ground and the answer is trivial — but the machinery tests each pair with a polygon overlap and does not know it is trivial. On a three-by-three that is thirty-six tests returning true.

Which folds are in the same place. The classical rule assigns each fold to one of four edges by parity. The general route finds that two crease images lie along the same line and overlap in more than a point, which is a geometric test on floating-point coordinates, and it recovers exactly the same four groups.

And which of two panels is higher at a crease. That comes from the letter and the orientation of the near panel, and it is the constraint the classical formulation does not have at all — because it works from orderings and reads the letters off, rather than the other way round.

The ninth size #

Eight of the nine agreed the first time. The two-by-four did not: the layer route gave 384 against a published 320, and the sixty-four extra foldings were the defect this essay is really about.

The cause was in the general machinery and it was one line. Two creases whose folded images lie along the same line are two U-turns in the same place, and the rule is that they may nest or stand clear but never interleave — unless they open to opposite sides, in which case they are nowhere near each other and are not constrained. Deciding which side a crease’s paper is on was being done with the crease’s own segment direction.

A crease’s segment has an orientation, and the orientation comes from whichever end the pattern happened to list first. On a two-by-four map, four folds wrap the right-hand edge of the folded square: two of them are drawn running up that edge and two running down. All four have their paper on the same side. Read with each crease’s own direction, two of them said “left” and two said “right”, and the machinery generated two constraints where there should have been six.

The fix is to take one direction for both creases, from the shared line rather than from either segment. Then all nine sizes agree.

Why the strips did not catch it #

There was already a check, and it passed throughout. Eighty strips of paper, folded once as a one-dimensional problem and once as a two-dimensional sheet, agreeing on both the ordering count and the state count.

They agreed before the fix and after it, and the reason is that a strip has one line to fold along. Every crease image on a folded strip lies at the same place along that line, and the segments a strip’s creases produce all run the same way across the paper, because the strip is a rectangle with parallel creases and the pattern is built one crease at a time from one end. There is no crease drawn backwards, so there was no case where the two directions disagreed.

A check built out of one family of examples can only fail on that family. The strips were a genuine check of the ordering rules, the crease rule and the state convention; they were structurally blind to how the side of a crease was decided, and no amount of running more of them would have helped.

What a published sequence is for #

This site’s habit is that every claim gets a test it could fail, and the usual test is an internal one: two routes written down side by side here, or an assertion fed input it must refuse. Those catch a great deal. What they cannot catch is a shared assumption, and both routes into a strip share the assumption that a crease has a canonical direction.

A published sequence is outside this collection. 1, 2, 6, 16, 50, 144 and 8, 60, 320 and 1368 were computed by other people, decades ago, from a formulation of the problem nothing here uses. Nothing here could have been arranged to reproduce them by accident, and a rule that is wrong in a way the internal checks cannot see has to disagree with them somewhere.

It disagreed on one size in nine. That ratio is worth carrying: a defect that shows on eleven per cent of the cases would have been missed entirely by a check that ran three of them.

Where the long route stops #

The general machinery is far slower and it gives out much sooner. Three-by-three is nine panels and 256 letterings, and it finishes in about a second. Three-by-four would be twelve panels and 4,096 letterings; four-by-four is sixteen panels, and sixteen panels is past what the ordering search will finish on any single lettering, let alone on tens of thousands.

The classical rule reaches further because it never places a panel: its search is over orderings only, its constraint check is a comparison of four integers, and it has no geometry in it at all. That is the whole value of a specialised formulation, and it is why the fourth term of the square sequence — 300,608 — was reachable by somebody in 1971 and the general machinery here will never see it.

So this is not a better way to count maps. It is a way of counting them that had to be checked, and the map is the only object in the subject with published numbers to check it against.

The letterings, which the classical route never sees #

The middle column of the table is worth one more paragraph, because it turns the sequence into two sequences.

The admitted letterings run 2, 4, 8, 16, 32 on the one-row maps — exactly 2ⁿ⁻¹, since every crease of a strip is free and the conditions at a vertex have nothing to say where there is no vertex. The two-dimensional maps are different: 8 of 16 on the two-by-two, 32 of 128 on the three-by-two, 128 of 1,024 on the four-by-two, 256 of 4,096 on the three-by-three. The share falls as the interior vertices multiply, which is the same thinning every pattern in the subject undergoes.

Divide one sequence by the other and the average number of orderings per lettering comes out at 1, 1.5, 2, 3.1, 4.5 for the strips and 1, 1.9, 2.5, 5.3 for the sheets. Both are rising, and rising is not obvious: adding paper adds constraints as well as orderings, and on the printed patterns of this site the constraints win so completely that nothing has more than two. A map is the family where they do not, and the reason is that a map’s creases all run to the edge of the paper — none of them is buried, so none of them is settled by the drawing.

Each interior vertex costs exactly half #

The lettering column carries an exact regularity the prose above passes over, and it is worth pulling out because it is the kind of thing that is either a theorem or a coincidence and here is plainly the first.

Count the letterings a map admits against the letterings it has. The two-by-two has sixteen and admits eight. The three-by-two has a hundred and twenty-eight and admits thirty-two. The four-by-two has a thousand and twenty-four and admits a hundred and twenty-eight. The three-by-three has four thousand and ninety-six and admits two hundred and fifty-six.

Those are divisions by two, four, eight and sixteen — and the maps have one, two, three and four interior vertices. Every interior vertex of a map removes exactly half the letterings, and no vertex removes any more or less than any other.

The per-vertex half is easy. A map’s interior vertices all have four creases meeting at four right angles. Of the sixteen ways to letter four creases, Maekawa admits the eight that split three-and-one, and the big-little-big lemma has nothing to say because no sector is strictly smallest — all four are square. Eight of sixteen: a half.

The surprising part is that the halves multiply. Interior vertices on a map share creases with each other, since a map’s creases run the whole width or height of the sheet and pass through every interior vertex on the way. Constraints on overlapping sets of variables have no general reason to behave like independent coins, and on most patterns in this collection they emphatically do not — that is the whole content of a propagation that stalls or a search that finds nothing. On a map they do, exactly, at every size measured.

What that says about a map’s letters #

Two consequences, and they point in opposite directions.

The first is that the admitted lettering count of an $m \times n$ map is settled without any search: two to the power of the crease count, divided by two to the power of $(m-1)(n-1)$. On a four-by-four map that is $2^{24}/2^{9}$, which is thirty-two thousand seven hundred and sixty-eight, and it is available for sizes the ordering search will never reach. The lettering half of the problem is not the hard half and this says by how much: it is not hard at all.

The second is that the folding count is where all the difficulty lives, and the ratio between the two columns says so more sharply the larger the map gets. Orderings per lettering run 1, 1.5, 2, 3.1, 4.5 along the strips, rising by about half again with each added crease — because the foldings roughly triple while the letterings exactly double. As long as that holds, and it is known to hold well past the sizes here, the ratio grows without bound.

So a lettering tells a reader steadily less about a folded map as the map grows. On the two-by-two it tells everything: eight letterings, eight foldings, one ordering apiece, and the letters name the object. On the three-by-three a lettering leaves five and a third orderings open, and on anything larger it leaves more. That is the same relationship a marking has to the object it names everywhere else in the subject, arriving here with an exact count attached at both ends — which is what a family with published numbers is for.

Three things this does not claim #

Not a formula. Nothing here computes a map’s folding count without enumerating. Both routes are searches, both are exponential, and the open problem is open.

Not an improvement. The classical route is faster by orders of magnitude and reaches sizes this one cannot. The general route’s only advantage is that it is general.

And not a check of the classical rule. Agreement is symmetric: it says the two do the same thing, not which of them is right. What makes it evidence is the third party — the published counts, computed by neither, and held here as somebody else’s arithmetic rather than this collection’s.

There was already a solver here that could be held against published numbers, and it works in one dimension rather than two. The newer machinery was believed only once it agreed with that one on every case both of them can reach.

The wider habit is worth naming once. Every internal check here compares two things built in one place, and two things one person built at one time share whatever that person assumed. The map is the only place in the whole subject where a number computed elsewhere, decades ago, from a different formulation, can be laid against something here — and it earned its place the first time it was used.

What a folder should take from it #

A map is the calibration weight of this subject. It is the one folded object whose count is published, independent and exact, and any general claim about layer order can be pointed at it.

Two routes are worth building even when the first one works. The classical rule was right the whole time; what the second route found was a defect in itself, and there was nowhere else it could have shown up.

And 1,368 is a small number for nine stamps. Nine cells, 362,880 orderings, 256 admitted letterings, and 1,368 ways of folding it — which is the same shape of answer everything in these essays has produced. The conditions leave a great deal; the layers take most of it back.