The oldest open problem

A road map is ruled into rectangles by its fold lines. It arrives folded one particular way, and there are others. How many others?

The question is sixty years old, has no notation in it, and is unsolved. That combination is rarer than it sounds. Most problems that are easy to state and hard to solve are hard because they are about something infinite — primes, or the digits of a number. This one is about a finite object with a finite answer, and the answer is simply not known past a few small cases.

What counts as a folding #

The rules have to be pinned down before any number means anything, and the pinning-down is where most of the subject’s early confusion lived.

The map is a rectangle ruled into $m \times n$ unit squares. Every rule line is a crease, and every crease must be folded — a folding that leaves a crease flat is a folding of a different map. The result must be a single pile the size of one square, with all $mn$ squares stacked on top of one another. Two foldings are the same if they produce the same stacking order of the squares, and different otherwise.

Nothing else is prescribed. The mountain-and-valley assignment is not given; it is whatever the stacking implies. Which square ends up on top is not prescribed either, so the count includes every rotation and reflection of the pile as a separate folding, which is the convention the published sequences use.

With those rules, a $1 \times 2$ map folds two ways, a $2 \times 2$ map folds eight, and a $3 \times 3$ map folds one thousand three hundred and sixty-eight.

The geometry is forced; only the order is free #

The first useful observation is that almost nothing about the folded state is a choice.

When the map is folded flat, every square lies on the same unit square of the plane. Which way round each one lies is not free: a square gets mirrored horizontally exactly when its column index is odd, and vertically exactly when its row index is odd, because crossing a crease reflects everything past it. So the layout is completely determined by the map’s dimensions, and the only unknown is the vertical order of the stack.

That is why the problem is a counting problem over permutations. There are $(mn)!$ orders, most of them impossible, and the question is how many survive.

The condition, and why it is the whole problem #

A fold connecting two neighbouring squares wraps around an edge of the folded pile. Which edge is determined by the same parity argument: a fold between horizontally adjacent squares wraps the right edge when the left-hand square sits in an even column and the left edge when it sits in an odd one.

Two folds that wrap the same edge are two hoops in the same place, and two hoops in the same place cannot interlock. In the stacking order they must nest or be disjoint; they may not interleave. Folds that wrap different edges are nowhere near each other and are free to do anything.

That is the entire condition. It is short, it is local in the sense that it involves two folds at a time, and it is completely unlike the conditions at a vertex — it says nothing about angles and everything about order.

Applied in one dimension, where “the same edge” means “the same end of the strip”, it reproduces the stamp-folding numbers exactly: 1, 2, 6, 16, 50, 144, 462 for strips of one to seven stamps. That agreement is the first check on the rule, and it is a real check, because it is a different implementation arriving at numbers computed decades ago by other means.

What the search costs #

Every number in the figure at the top was produced by an exhaustive search that places squares one at a time and abandons a partial stack as soon as two folds in it interlock. The pruning is sound — adding more squares on top cannot separate two that already interlock — and it is what makes the $3 \times 3$ case reachable at all.

The costs are worth quoting, because they are the reason the sequence stops. A $2 \times 4$ map takes a few hundredths of a second. A $3 \times 3$ map takes about a tenth. A $2 \times 6$ map takes twelve seconds, and a $3 \times 4$ map about eighteen. A $4 \times 4$ map — three hundred thousand foldings — is out of reach of a build and was computed by W. F. Lunnon in 1971 with a great deal more patience.

The next term, $4 \times 5$, is not known. Not “not known to a formula”: not computed.

Why the second dimension is a different problem #

A reader who has seen the strip solved might reasonably expect the rectangle to be the strip with more bookkeeping. It is not, and the reason is specific.

On a strip, the folds that can interfere with a given fold are the ones wrapping the same end, and there are two ends. Every fold is therefore in one of two groups, and the non-interleaving condition within a group is a well-understood constraint — it is the condition for a set of arcs on a line to be non-crossing, which is what Catalan numbers count and what makes the one-dimensional problem tractable.

On a rectangle there are four edges, but that is not the difficulty. The difficulty is that folds in the same group come from different rows and columns of the map, and the map’s connectivity ties them together in ways a single arc diagram cannot express. Two folds in distant rows still wrap the same edge of the same pile and still constrain one another, while also being constrained by the folds along their own rows. The result is a constraint graph rather than a nesting structure, and nesting structures are what has closed-form counts.

What a square is worth, by dimension #

The published counts carry a comparison nobody makes with them, and making it puts a number on the claim that the second dimension is a different problem.

Take the growth per square rather than per row or per column, so that objects of different shapes can be set beside one another.

A strip grows by about 3.2 per stamp — the ratios of consecutive stamp numbers run 3.00, 2.67, 3.13, 2.88, 3.21 and are climbing toward something a little above three. Two-row maps grow by 7.5, 5.33 and 6.19 per column, and a column is two squares, so each square is worth about 2.5. And from the three-by-three to the four-by-four, seven extra squares multiply the count by 220, which is 2.16 per square.

Every square added to a wider map is worth less than every square added to a narrower one, and the sequence 3.2, 2.5, 2.16 falls monotonically as the object becomes more two-dimensional.

The second dimension takes away #

That is the opposite of what the shape of the problem suggests. More squares in more directions ought to mean more ways to arrange them, and a map is a strip with extra freedom in it.

Compare directly. A two-by-five map has ten squares and folds 1,980 ways. A strip of ten stamps also has ten squares and folds 14,060 ways — seven times as many. At four squares the ratio is two; at six, 2.4; at eight, 4.4; at ten, 7.1.

So the second row does not add possibilities. It removes them, and the shortfall against the equivalent strip grows steadily with size.

The reason is in the essay’s own condition. A fold on a strip is constrained only by the folds wrapping the same end, and there are two ends. A fold on a map is constrained by the folds wrapping the same edge — and those now come from every row and column rather than from one line — so each new square arrives carrying more constraints than freedoms.

The rectangle is not the strip with more room; it is the strip with more rules. That is a sharper statement of the essay’s point than the structural argument alone, and it comes out of numbers Lunnon published in 1971.

It also says something uncomfortable about the missing terms. If the per-square factor keeps falling, the four-by-five map is somewhere near thirty million rather than the sixty million a constant rate would give — and a bound that depends on an extrapolated falling exponent is exactly the kind that has no business being quoted. What the trend does license is a direction: the sequence grows more slowly than the strip’s, and the gap widens.

What is known about the strip, and why it is not enough #

The one-dimensional case is not merely computed. It is understood, and the contrast with the rectangle is instructive.

For a strip, flat-foldability is decidable in linear time by a rule that reads the crease positions and the letters and never searches. The counting question is harder than the decision question but still has structure: the foldings of a strip of $n$ stamps are in bijection with certain meandering curves, and the meander problem has been attacked with transfer matrices, with generating functions and with statistical-mechanics methods that give the asymptotic growth rate even where the exact terms run out.

None of that machinery survives the move to two dimensions, and the reason is the one given above: a meander is a curve crossing a line, and a line has an inside and an outside. The folds of a rectangle wrap four edges, and the objects they form are not curves crossing a line.

So the strip is not a small case of the rectangle in the way that a small map is a small case of a large one. It is a different problem that happens to agree with the rectangle when the rectangle is one square wide.

What a folding is, once the squares are stacked #

Reducing a folding to a permutation is what makes the problem countable and also what makes it strange. Ordinary flat-folding questions mix geometry and combinatorics: which layer goes on top depends on how long the flaps are and where their creases sit. Map folding removes all of that. Every square is congruent to every other, every fold wraps a full edge, and nothing is left except the order.

That ought to be the easy end of the subject. It is where the subject’s oldest unanswered question lives, and the two facts are related: with no geometry to exploit, there is nothing to compute with. An algorithm for flat-foldability on a general pattern can prune by comparing flap lengths. A map-folding enumerator has nothing to compare.

Which theorem was checked, and how #

Nothing here is a theorem. What is checked is an enumerator, and it is checked against numbers it did not produce.

The gate requires the enumerator to reproduce every published count it can reach: 1, 2, 6, 16, 50, 144 and 462 for the strips, and 8, 60, 320, 1980 for the two-row maps, and 1368 for the three-by-three. Those are Lunnon’s numbers and the stamp-folding sequence, both from the literature. It also requires the one-dimensional case to come out right from the two-dimensional rule, which is a stronger statement than it looks: the strip counts are computed by a separate solver elsewhere on this site, and this file arrives at them by a different route.

A wrong crossing condition does not reproduce eleven published integers by chance. That is the whole of the confidence here, and it is worth more than a proof of the code would be.

What the picture cannot show #

The bars are on a logarithmic scale, and a logarithmic scale is a decision to make an explosion legible rather than dramatic. The $4 \times 4$ value is two hundred and twenty times the $3 \times 3$ value and appears about a fifth again as long.

The figure also cannot show the shape of a folding, and there is no useful way to draw one: a folding is a permutation of nine or sixteen squares, and drawing it means drawing a stack of identical squares in an order, which conveys nothing that the number does not. This is one of the rare places on this site where the object of study genuinely has no picture, and the honest response is to draw the counts.

The idealisation underneath #

Zero thickness, again, and here it is load-bearing in an unusually literal way.

A $4 \times 4$ map folded into a single square is sixteen layers of paper. The published count treats those sixteen layers as sixteen planes of no depth that can be permuted freely. A real map cannot reach most of those orders — the paper would have to pass around the outside of a fold whose radius is set by the thickness of the stack already there, and a crease has a radius that grows with the number of layers under it.

So the number of ways a physical road map folds is smaller than 300,608, and nobody knows that number either. The mathematical count is an upper bound, and the interesting thing is that it is an upper bound on a quantity a person could in principle measure with a road map and a lot of free time.

The surprising connection #

Map folding is the special case that ought to be easy. Every crease is present, every crease is folded, the geometry is a grid, and the symmetry group is large. And it is the case with no answer.

Meanwhile the general problem — an arbitrary crease pattern, arbitrary angles — is NP-hard, which sounds worse and in a sense is better: at least the difficulty has been classified. Map folding has not even been shown to be hard. As far as anybody knows there could be a polynomial algorithm for it, and there could be a formula. There is simply no proof either way, on the most symmetric object in the subject.

That is a useful corrective to the idea that symmetry makes things tractable. It makes things describable, which is not the same.

Who asked it, and when #

The stamp-folding version — a strip of stamps, in how many ways does it fold — is much older and appears in recreational mathematics through the nineteenth century. The map version was posed in its modern form by Stanislaw Ulam and appears in his 1960 Problems in Modern Mathematics; it is often called Ulam’s problem for that reason.

W. F. Lunnon computed the small cases by machine in 1968 and 1971, and his values are the ones still quoted. Jacques Touchard, Koehler, and later authors added terms to the one-dimensional sequences. The general two-dimensional question has attracted steady attention and no solution, and the entries in the Online Encyclopedia of Integer Sequences for these counts remain short.

What folders do with it #

The practical answer to “in how many ways does this fold” is that nobody needs it, and the reason is worth stating because it is the same reason the design side of the subject works at all.

A folder does not search for a folding. A folder follows a sequence, and the sequence produces a folding as it goes — which is why a base built on a grid or from a circle packing never poses the decision problem. The same is true of tessellations: a Miura is folded by collapsing rows, and the order the layers end up in is a consequence of the collapsing rather than a choice made at the end.

The counting question matters for a different reason: it is the honest measure of how much a crease pattern underdetermines. A pattern with three hundred thousand foldings is not a specification of a folded object, and treating it as one — which the phrase “the crease pattern is the model” invites — is a mistake that the number corrects.

The ladder from here #

This is the base rung of a ladder that has room for several more: the one-dimensional theory that is solved and why it solves, the connection between stamp folding and meanders, the physical count with thickness, and the question of whether map folding is hard in the technical sense — which is open, and which is the rung this ladder is really pointing at.

For now what it establishes is a fact about the subject rather than about maps: the counting questions in folding are not merely unsolved in the awkward cases. They are unsolved in the most regular case there is, and have been for sixty years.