Two directions that will not separate

The oldest open problem is easy to state and has no formula: in how many ways can a map be folded along its creases into a single pile? The counts are known for small maps because somebody enumerated them, and the sequence stops where the enumeration stops.

Alongside it sits an easier problem with the same character. A strip of stamps is a map with one row, its counts are the stamp-folding numbers — 2, 6, 16, 50, 144, 462 — and they too are known term by term with no formula. Their growth rate is a number nobody has proved exists.

The natural hope is that the two are related in the obvious way.

The hope, stated exactly #

Folding a map feels like two independent operations. Fold it along the vertical creases as though it were a strip of n stamps; then fold the resulting strip along the horizontal creases as though it were a strip of m. Each choice in the first is compatible with each choice in the second, so the count ought to be the product.

That predicts a 2 × 2 map folds in 2 × 2 = 4 ways; a 2 × 3 in 2 × 6 = 12; a 2 × 4 in 2 × 16 = 32; a 2 × 5 in 2 × 50 = 100; and a 3 × 3 in 6 × 6 = 36.

The actual counts are 8, 60, 320, 1980 and 1368.

The discrepancy, and its shape #

The ratios are 2, 5, 10, 19.8 and 38.

Two things about that sequence matter. The first is that it is never one, so the product is never right — the directions interact at the smallest map there is. The second is the more interesting: the ratio grows. It roughly doubles from one column to the next along the two-row family, and the three-by-three case at 38 is far past anything in the two-row list.

So the failure to factor is not a small correction that could be patched with a constant. It is the dominant behaviour, and the product accounts for a shrinking fraction of the answer as the map grows.

One more comparison sharpens it. The 3 × 3 map has nine panels and folds 1,368 ways; a strip of nine stamps folds 4,536 ways. So the two-dimensional object with nine panels has fewer foldings than the one-dimensional object with the same number — the extra creases in the second direction are, on balance, a constraint — while at the same time having far more than its own product predicts. Both statements are true at once and they are about different comparisons.

Where the interaction comes from #

The reason is worth having and it is a statement about layers rather than about creases.

Folding the strip in one direction produces a stack, and the stack has an order. Folding that stack in the other direction now has to move layers that are already piled up, and which layer ends up where depends on the order the first folding produced. So the second folding’s choices are not made against a strip; they are made against a strip whose panels are already stacked several deep, and different stackings admit different second foldings.

Put the other way round: the product formula assumes the second fold cannot see the first. It can. The two directions share the same physical sheet and the same layers, and every constraint about paper passing through paper couples them.

The coupling therefore runs in the direction that increases the count rather than decreasing it, which is the part that is genuinely surprising. Adding a constraint would be expected to remove options. What happens instead is that the two-dimensional problem has folded states with no one-dimensional decomposition at all — stackings that no sequence of “fold all the rows, then all the columns” ever produces — and those extras outnumber the product very quickly.

What the extra foldings are #

It is worth being concrete about the states the product misses, since “the directions interact” is a description of an arithmetic gap rather than of an object.

Take the 2 × 2 map: four panels in a square, one horizontal crease and one vertical. The product says four foldings — two ways to fold the strip of two horizontally, times two vertically. There are eight.

The four extras are the foldings in which the two directions are interleaved — more than one way to lie flat, in the sense that essay makes precise: fold part of the sheet one way, fold across it, then complete the first direction. The result is a legal pile of four panels that no “all the rows, then all the columns” procedure produces, because by the time the columns are folded the rows are already committed to an order that forbids it.

At 2 × 2 the extras are as numerous as the product’s foldings. At 3 × 3 they outnumber them thirty-seven to one, which is what the growing ratio is counting.

What this does to the search for a formula #

The subject has stamp-folding numbers with no formula and map-folding numbers with no formula, and it would be a considerable prize if the second followed from the first.

The measurement above says it does not, in a specific and useful way. A formula for the map counts cannot be a function of the strip counts alone. Whatever it is, it has to know something the one-dimensional problem does not record — and what it has to know is about layer orders, since that is the only thing the two directions share.

That is a small negative result and it is the kind that saves work. The most natural attack on a hard counting problem is to decompose it, and this one closes the most natural decomposition.

The extras are exponential, not a correction #

The ratios 2, 5, 10 and 19.8 are described above as roughly doubling, and the doubling is worth taking seriously because it says what kind of object the product is missing.

If the ratio doubles with each column, then the two-row count grows like $2^n$ times the strip count. Divide the measured counts by $2^n$ times the strip count and the quotients come out at 1, 1.25, 1.25 and 1.24 for widths of two, three, four and five — flat to within a per cent across the range, and exactly 1.25 at two of the four points.

That is four data points and it is not a formula, and it should not be read as one. What it does support is the shape: the foldings the product misses outnumber the ones it finds by a factor that grows exponentially in the width of the map, rather than by a constant or by anything polynomial. The interleaved states are not a correction term. They are the answer, and the product is a vanishing fraction of it.

Which puts a number on the two growth rates #

The same arithmetic says something about the growth constants, and this is where the two open problems touch.

The strip counts grow by a factor of about three per stamp — 3.0, 2.67, 3.13, 2.88, 3.21 across the terms that are known. The two-row counts grow by 7.5, 5.33 and 6.19, which averages a little over six.

So the two-row growth constant is about twice the one-row one, which is exactly what a factor of $2^n$ on top of the strip counts predicts. The doubling of the ratio and the doubling of the growth constant are the same observation counted two ways, and they agree.

That connects the failure to factor with the exponent nobody has proved exists. If the strip counts have a growth constant near 3.5 — which is the figure the one-dimensional literature circles without settling — then the two-row counts have one near seven, and the relationship between the two is a factor of two per additional row rather than a power of the first.

What that costs a formula-hunter #

The negative result the essay states is that a map formula cannot be a function of the strip counts alone. The exponential gap says how badly.

A decomposition that captured the product and treated the rest as an error term would be wrong by a factor that doubles every column, so it would be right at 2 × 2 and useless by 2 × 8. Any approach of that shape is not an approximation that degrades; it is an approximation that stops being about the same quantity.

What would be worth having instead is a count of the interleaved states directly — the ones no row-then-column procedure reaches — since those are the dominant term and the product is the small one. That inverts the natural attack: rather than counting the easy states and correcting, count the hard ones and add the easy ones as a footnote. Three data points suggest the hard ones number about $1.25 \cdot 2^n$ times the strip count, which is at least a shape to test against a fourth.

Where the model stops #

Five data points is five data points. The ratios 2, 5, 10, 19.8, 38 are all that the enumerated counts support. Whether the ratio keeps roughly doubling, settles, or does something else is not established here and would need counts nobody has — the 4 × 4 map’s count is known and quoted at 300,608, and beyond that the enumeration has not gone.

The counts are counts of labelled foldings, in the convention this site’s enumerator uses and the published tables use. Counting up to symmetry gives different numbers, the ratios change, and the failure to factor does not — but the arithmetic above should not be compared with a table using another convention without checking which.

The enumerator is this site’s own and it agrees with the published tables. The counts above — 2, 6, 16, 50, 144, 462 for the strips and 8, 60, 320, 1980, 1368 for the maps — are computed here by exhaustive search and compared afterwards with Lunnon’s published values, which the search never consults. Two independent routes to the same integers is what makes a table of this kind worth reading; a single route would be a report about a program.

Nothing here is about the cost of counting. How the enumeration’s work grows and what a better algorithm would do belong to algorithms-data-structures.com, and no complexity claim is made above. What is claimed is a relationship between two sequences of integers.

A count is not a decision. Deciding whether a marked pattern folds is a different question with a different answer, easy in one dimension and hard in general, and none of the counting above bears on it.

Why the product looks so plausible #

It is worth asking why the wrong answer is the intuitive one, because the reason is a genuine feature of folding rather than a lapse.

A map really can be folded that way. Fold the columns, then fold the rows, and a perfectly good folded state comes out — so the product’s foldings all exist. The mistake is the word only: the product counts the states reachable by that particular two-stage procedure, and the enumeration counts every state that is a valid single pile.

So the product is a lower bound and it is the count of a restricted process, which puts it in the same family as the simple-fold models the site already distinguishes. A machine that folds all the rows and then all the columns is a weaker machine than one that may fold anything at any time, and the ratios above are exactly how much weaker.

That reading is more useful than “the product is wrong”. It says which foldings the product misses: the ones that interleave the two directions, folding partly one way, then partly the other, then back. Those are precisely the foldings a person makes when they fold a map badly and cannot get it back into the glovebox.

What a folder recognises here #

There is a physical version of this result and everybody has met it.

A road map folds into its cover exactly one way, and refolding it is notoriously hard. The reason is not that the correct folding is obscure — the creases are visible and pre-made — but that the two directions have to be done in a particular interleaving, and any attempt to complete one direction before starting the other produces a pile that will not close.

That is the same coupling seen from the other side. The product’s foldings are the ones a person naively attempts; the correct one is usually not among them; and the frustration is the discovery that the second direction’s choices were foreclosed by the first.

The one place it does hold #

There is a case where the product is exact and it is worth noting because it is the degenerate one.

A 1 × n map is a strip. Its “product” is 1 × (the strip count), since a strip of one has exactly one folding, and that is the count. So the formula is right precisely when one of the directions has nothing in it.

That is not a consolation and it is a check: an enumerator that got the two-dimensional case right and the one-row case wrong would be broken, and the site’s map enumerator is required to reproduce the stamp-folding numbers on its one-row inputs by a rule that has nothing to do with strips. 2, 6, 16, 50, 144 and 462 arriving out of a two-dimensional search is the evidence that the search is counting the right objects, and it is the reason the numbers above can be trusted at the sizes they are quoted at.

The interleaving, named #

The subject has a word for what the product misses, arriving from the machine side rather than from the counting side.

The three machine models distinguish which layers a fold may take: all of them, a contiguous block, or exactly one. The row-then-column procedure is a restriction of a different kind — not about which layers, but about which creases in which order — and it is a restriction nobody had needed to name because nobody had counted what it costs.

Both restrictions produce the same shape of result: a process weaker than the geometry reaches fewer states, and the shortfall is measurable. That two independent restrictions on folding both behave this way is the general lesson, and it is the reason a folded state and a way of getting there are treated as separate objects throughout this site.

What a person actually does with a map #

The counting result has an odd relationship with the object it is about, and it is worth closing on.

Nobody folding a map wants 1,980 foldings. They want one — the one the creases were made for, which puts the cover on the outside, and a crease pattern does not record which — and the enormous count is a statement about how many ways there are to get it wrong. The subject’s interest in the number is entirely mathematical, and the physical object’s interest in it is zero.

That is a common shape in this corner of folding and it is the reverse of the usual complaint about applied mathematics. The map-folding numbers are not a model of anything anybody does; they are a question the object suggested and then declined to be relevant to. Sixty years of work on them has produced a sequence, no formula, and a considerable amount of knowledge about why the obvious approaches do not work — of which the failure to factor is one more piece.

Where the ladder goes next #

The obvious continuation is the ratio itself. Five values that look like they double is a suggestive sequence and not a result, and extending the enumeration by one column in each family would say whether the doubling is real. That is a computation with a known method and an uncertain runtime, which is the honest description of most of this corner of the subject.

The other direction is the structural question the failure raises. If the two-dimensional count is not the product, the natural next question is what the extra foldings look like: is there a characterisation of the states no row-then-column procedure reaches, and is their number the interesting quantity rather than the total? That is a question about folded states rather than about counts, and the machinery for asking it — layer orders, and the distinction between an ordering and a state — is already here.