The grid a division makes

Dividing without measuring is the first thing folding does that a ruler does not: halves come free, thirds need a construction, and one crossing and then another gives a ladder that lands on the next fraction exactly, one fold per rung, all the way down.

Everything in that ladder is closed. The positions are rational numbers with a rule for the next one, the crossings are computed as exact fractions rather than as floating-point approximations, and a division into n parts is finished when the ladder says it is.

Then divide the other way as well, and look at what is on the paper.

The construction makes a map #

An exact division into n parts puts n − 1 parallel creases across the sheet at positions 1/n, 2/n, … Doing it again at right angles puts n − 1 more the other way. What is left is a square ruled into n² cells with every rule line a crease, and that is the definition of an n × n map of stamps.

The construction that produced it is finished and exact. The object it produced is the one whose folding count nobody knows.

Eight, then one thousand three hundred and sixty-eight, then three hundred thousand six hundred and eight, then nothing. The first two are computed here — by placing the panels and searching the orderings, and independently by the classical edge rule, agreeing exactly. The third is somebody else’s arithmetic, first reached by computer in 1971. The fourth has never been computed by anybody.

So the same drawing is a solved construction and an open problem, depending on which question is asked of it. Where the creases go: closed, exact, rational. What the paper does when they are all folded: open.

Why the two questions come apart #

The construction is about positions and the folding count is about order, and nothing carries between them.

A crease at 1/3 is at 1/3 whatever else is on the sheet. The ladder’s arithmetic is a sequence of rational operations, each exact, and adding a second direction adds a second independent sequence — the crossings of the two families are just pairs of the two lists, and there is no interaction to compute.

The folding count is about which cell lies above which when all of them are stacked on one square. That is a question about arrangements of n² objects, its answer is bounded above by (n²)! and below by nothing anybody can write down, and every constraint on it comes from pairs of folds wrapping the same edge of the folded square rather than from where the creases are.

The positions do not appear in the second question at all. A map’s folding count depends only on how many cells there are in each direction; move the creases anywhere — divide by Fujimoto’s method, divide badly, divide by eye — and the count is the same, provided the topology is. That is why the construction being exact buys nothing.

The vertex the grid is made of #

Every interior vertex of an n × n grid is the same vertex, and it is the simplest interesting one in the subject.

Four creases, four right angles. The angles sum to 360°, so it is developable. The alternating sums are 180° each, so Kawasaki holds identically — not by design and not by choice of proportions, but because 90 + 90 = 90 + 90. No sector is strictly smallest, so the big-little-big lemma has nothing to say. What is left is Maekawa, which requires three of one letter and one of the other.

That gives eight admissible letterings at each vertex out of sixteen, and the grid’s count is those lists intersected over every crease two vertices share. Four cells, one vertex, eight of sixteen. Nine cells, four vertices, 256 of 4,096 — which is not 8⁴ = 4,096 divided by anything obvious, because the vertices share creases and the constraints interact.

The interaction is where a grid stops being four independent problems, and it is the same interaction that makes the folding count hard. A pattern whose vertices did not share creases would have a count that multiplied.

What the count is doing #

The jump from 1,368 to 300,608 is worth reading as a rate rather than as two numbers.

Nine cells give 1,368 and sixteen give 300,608 — a factor of two hundred and twenty for seven more cells, or about a factor of 2.1 per cell. The one-dimensional case does something similar at a lower rate: 2, 6, 16, 50, 144, 462 for two to seven stamps, a factor near three per stamp and falling.

Nothing about either sequence has a formula. There is no expression for the number of ways a strip of n stamps folds, let alone for a map, and the strip case has been open since the 1960s while the map case is older still. The subject’s oldest unsolved problem is what happens to a piece of paper somebody has just divided into thirds, which is a fact about how little the elementary constructions settle.

The letterings, and the second half of the answer #

There is a decomposition available here that the classical count does not have, and it is the useful thing for somebody holding a divided sheet.

A folding is a lettering together with an order. The letters say which of each pair of creases is a mountain and which a valley; the order says which cell is on top. Given a folded map, the letters can be read off by comparing neighbours; given the letters, the order is constrained but not decided.

On a three-by-three grid, 4,096 letterings are possible, 256 satisfy the conditions at every vertex, and those 256 share 1,368 orderings — an average of 5.3 each. On a two-by-two it is 16, 8 and 8, one ordering per lettering exactly.

So a folder who has divided a sheet into thirds and chosen which creases to make mountains has not finished: there are five ways on average to complete the choice, and the pattern does not record which was taken. That is a large amount of undetermined behaviour in a construction that felt closed.

Half of the open problem is closed #

The lettering counts in the table above have a closed form, and having it says exactly which half of the question is open.

An $n \times n$ grid has $2n(n-1)$ creases and $(n-1)^2$ interior vertices, and every one of those vertices is the four-right-angles vertex — where Kawasaki is an identity, the big-little-big lemma is silent, and Maekawa admits eight of sixteen letterings. Each vertex therefore removes exactly a factor of two, and the vertices’ constraints turn out to multiply cleanly despite sharing creases. So the admissible letterings number two to the crease count divided by two to the vertex count:

$$2^{\,2n(n-1) - (n-1)^2} = 2^{\,n^2 - 1}.$$

Eight at two by two, two hundred and fifty-six at three by three, thirty-two thousand seven hundred and sixty-eight at four by four — the first two are the essay’s own figures and the third follows without being computed.

So the first sieve is solved in closed form for every grid, at every size, for ever. What is open is the second: how many orderings each admissible lettering admits, summed over all of them.

Which locates the difficulty in one average #

Divide the folding count by the lettering count and the quotient is the average number of orderings per lettering. Eight over eight is 1.00 at two by two. One thousand three hundred and sixty-eight over two hundred and fifty-six is 5.34 at three by three. Three hundred thousand six hundred and eight over thirty-two thousand seven hundred and sixty-eight is 9.17 at four by four.

One, five and a third, nine and a sixth. The increments are 4.34 and 3.83, so the average is growing a little under linearly in the grid’s side — and if it continues that way the five-by-five average is somewhere near thirteen, which against sixteen million seven hundred and seventy-seven thousand letterings puts the five-by-five folding count at a little over two hundred million.

That is an extrapolation from three points and should be read as one. What is not an extrapolation is the shape of the problem it exposes. The famous sequence is a product of two factors, one of which is $2^{n^2-1}$ and known exactly at every size, and the other of which is an average that has been computed three times and grows slowly. A formula for the map counts is a formula for that average, and the average is a far better-behaved object than the count it sits inside — three figures rather than twenty-five, growing linearly rather than explosively, and with a plain meaning: how much a lettering leaves undecided.

What a grid does that a strip does not #

The one-dimensional division is the same construction in one direction, and its object is a strip of stamps. Comparing the two says where the difficulty enters.

A strip’s creases are all free. Every crease of a strip runs from one edge of the paper to the other and has no interior vertex on it, so no condition in the subject is evaluated anywhere on it and all 2ⁿ⁻¹ letterings are admitted. A strip of six stamps admits thirty-two letterings and folds 144 ways.

A grid’s creases meet. Dividing in two directions creates (n − 1)² interior vertices, every one of degree four with four right angles, and each of them cuts the letterings down. Nine cells admit 256 of 4,096 rather than all of them.

So the second direction does two things at once: it multiplies the objects to be stacked and it constrains the letters. The first effect is much larger than the second, which is why the map counts run so far ahead of the strip counts — 1,368 against 16 at the same crease count of twelve versus three.

The two counts are two different sieves #

It is worth separating the 256 from the 1,368 once more, because a reader meeting both in one table can take them for two readings of one thing.

256 is the first sieve. It is what the conditions at the four interior vertices admit, and it is the number every gate on this site measures. It is computed without folding anything: four angles, two alternating sums, a count of mountains against valleys, and an intersection over shared creases.

1,368 is the second sieve applied to the first, and it is a sum rather than a filter. For each of the 256 admissible letterings, the panels are placed and the orderings of them are searched; the counts come out at one, two, five, twelve and so on, and their total is 1,368.

So the second number is not “how many of the 256 survive” — all of them do, since every admissible lettering of a map has at least one ordering. It is “how many folded objects those 256 letterings have between them”, and the average of 5.3 is the interesting statistic. On a square twist the same average is well under one, because 248 of its 256 letterings have no ordering at all.

A map is the generous case, then, and it is generous because none of its creases is buried: every one runs to the edge of the paper, so nothing was settled when the pattern was drawn.

Where this collection stops #

Three by three is the largest grid whose folding count is computed here, and the reason is the same one every counting argument on this site runs into.

The classical edge rule reaches four by four — sixteen cells, a search over orderings with a cheap constraint test — and this collection’s own implementation of it does. The general layer machinery does not: sixteen panels is past what the ordering search will finish, and it says so rather than returning what it had found when the budget ran out.

Five by five is not reachable by anybody. Twenty-five cells is 1.55 × 10²⁵ orderings, the constraint pruning is not enough, and there is no formula to fall back on. A reader can produce the object in about two minutes with a sheet of paper and the ladder above.

Anybody can make the open problem #

The practical charm of this rung is that the object is trivially available, and it is worth saying so plainly because most open problems are not.

A sheet of paper, two exact divisions into thirds, four creases. That is a two-minute construction using no tool but the paper — folding beats the compass by exactly one degree and thirds are inside what one fold can reach. What is on the table afterwards is a nine-cell map, and the number of distinct ways it can be folded flat is 1,368, computed by machine and by nobody’s hand.

Divide into quarters instead — which is easier, since quarters are two halvings — and the object is a four-by-four map with 300,608 foldings, a number first obtained by a computer. Divide into fifths, which the ladder also reaches exactly, and the answer is not known to anybody.

The distance between “a child can make it” and “nobody can count it” is one more division. That is unusual and it is the reason map folding has stayed interesting: the object needs no apparatus, no special paper and no expertise, and it defeats everything.

Three things this does not say #

It does not say the construction is incomplete. Dividing into n parts is exactly as finished as the ladder claims: the creases are where they should be, exactly, and the arithmetic is rational throughout. The open problem is a different question about the same paper.

It does not depend on the division being exact. The folding count is a property of the grid’s topology, so a badly divided sheet has the same count as a perfectly divided one. The exactness matters to the reader and not to the enumeration.

And it does not give a formula. Nothing here computes a map’s folding count without enumerating it, and the fourth term is quoted from elsewhere rather than reproduced.

The construction that is not a grid #

One more comparison closes the ladder, and it is the case where the division is exact and the object is not a map.

Divide a strip into thirds and the result is three cells in a line — six foldings, computed in this collection since its first phase and matching the published sequence. Divide a square into thirds one way only and the result is the same object with height: still three cells, still six foldings, because a crease running the whole width of the sheet is one crease however tall the paper is.

The count changes the moment the second direction goes in, and it changes by a factor of two hundred and twenty-eight: six to 1,368. Two extra creases, and the number of ways the paper can end up is multiplied by more than two hundred.

That is worth stating as the ladder’s own result. Exact division began as an arithmetic question — which fractions can a fold reach — and this is where the arithmetic stops being the whole of it. The positions were settled in the first rung. What the sheet does with them was never in the ladder at all.

What a folder should take from it #

Dividing a sheet in two directions makes a famous object. An n × n grid of creases is a map of stamps, and the question of how many ways it folds has been open since before most of this subject’s results were found.

The exactness of the division buys nothing downstream. The count depends on the grid and not on where the lines are, so a construction that lands on the rational exactly and one that converges to it have the same answer.

And a divided sheet has more ways to fold than it looks like. Nine cells, 256 admissible letterings, and 1,368 folded states — from four creases anybody can put in with no measurement at all, and none of them settled by the conditions the subject checks.