The test that never fires on a map

A map is a rectangle of paper scored on a grid, and the question is how many ways it folds into a single stack. It is the oldest open problem in this subject: no formula is known for the number of ways an m by n map folds, and none is known for the strip case either beyond what enumeration provides.

This collection has a cheap refusal that fires on patterns nothing else can touch. Every crease says which of the two panels it joins ends up above the other, and a circle in those statements is a proof that no folded state exists — read in one pass over the crease list, on patterns whose orderings could never be enumerated.

Pointing it at the maps is the obvious thing to do, and the result is a table of noughts.

The enumeration #

A map’s creases are the grid lines that are not the sheet’s edge. A three-by-three map has twelve of them, so four thousand and ninety-six labellings; two hundred and fifty-six of those satisfy every condition at every interior vertex.

Take those two hundred and fifty-six, build the folded sheet from each, collect one arrow per crease, and look for a circle. Four of the two hundred and fifty-six have one.

Every smaller map has none. The strips — two, three, four and five panels in a row — have between two and sixteen admissible labellings each and no circle anywhere. The two-by-two has eight and no circle. The three-by-two has thirty-two, the four-by-two a hundred and twenty-eight, and neither produces one.

Four hundred and fifty-four admissible labellings across nine maps, of which four close a circle, and all four of them on the last map in the list.

Why the strips can never do it #

For the one-dimensional maps the nought is a theorem rather than a measurement, and the argument is two sentences.

A strip of n panels has its panels in a row: panel one joined to panel two, two to three, and so on. That is a path, and a path contains no closed chain of panels at all. A circle in the arcs needs a closed chain to run round, so a strip cannot have one however it is labelled.

The same reasoning covers any pattern whose panel graph is a tree, which is why a fold-and-cut outline’s letters never contradict themselves either: a straight skeleton has no circuit in it.

So the interesting cases begin where the map becomes two-dimensional and its panels start enclosing things.

Why the two-dimensional maps almost never do it #

A two-by-two map has four panels round one interior vertex, and that is a closed chain — so the geometric obstacle is gone. It still produces no circle, and the reason is the reason it is always missing at a single vertex.

Orienting the four panels round one point requires the letters to alternate strictly, and an alternation has equal counts of mountain and valley while the counting theorem demands a difference of two. Every admissible labelling is therefore safe at every vertex, at every degree, in every pattern.

A two-by-two map has exactly one interior vertex, so its only closed chain is the one that can never be closed. A three-by-two has two interior vertices; a four-by-two has three. Those maps have longer chains available — round two adjacent vertices, six panels — but a chain of six needs six creases to conspire, and on a map with seven or ten creases there is not much room to conspire in.

The three-by-three map is the first with four interior vertices in a square arrangement, and four of its two hundred and fifty-six labellings manage it. That is one and a half per cent.

The counting the enumeration also gives #

The same enumeration that produces the noughts produces something else, and it is worth reading off because it is the quantity the open problem is about.

Every map size here has its admissible labellings counted: two for the two-panel strip, four for three panels, eight for four, sixteen for five. That doubling is exact and easy to see — a strip’s creases are independent as far as the vertex conditions go, because a strip has no interior vertex at all, so every labelling of its creases is admissible.

The two-dimensional maps behave differently. A two-by-two has four creases and eight admissible labellings rather than sixteen, because its single interior vertex refuses half of them. A three-by-two has seven creases and thirty-two rather than a hundred and twenty-eight; a four-by-two, ten creases and a hundred and twenty-eight rather than a thousand and twenty-four; a three-by-three, twelve creases and two hundred and fifty-six rather than four thousand and ninety-six.

Each interior vertex costs a factor of two. That is the counting theorem at a degree-four vertex: of the sixteen labellings of four creases, eight satisfy it, and the smallest-sector lemma has nothing to say at a map vertex because its four sectors are all right angles and none is strictly smallest.

So a map’s admissible labellings number two to the creases divided by two to the interior vertices, exactly, at every size here. It is a rare case in this subject where a count comes out as a closed form and stays that way.

One bit per panel, less one #

The closed form the previous section arrives at can be tidied further, and the tidy version is worth having because it covers the strips and the rectangles in one statement.

An $m$ by $n$ map has $m(n-1) + n(m-1) = 2mn - m - n$ creases and $(m-1)(n-1)$ interior vertices. Each vertex costs a factor of two, so the exponent is the difference:

$$\big(2mn - m - n\big) - \big(mn - m - n + 1\big) = mn - 1$$

So a map’s admissible labellings number two to the power of its panel count less one, whatever its proportions. Nine sizes bear it out with nothing left over: two, four, eight and sixteen for the strips of two, three, four and five panels; eight for the two-by-two; thirty-two for the three-by-two; a hundred and twenty-eight for the four-by-two; two hundred and fifty-six for the three-by-three.

It also explains why the strip looked like a separate case and is not. A strip of $n$ panels has $mn - 1 = n - 1$, which is its whole crease count, because it has no interior vertex to spend a factor on. The strips are not exempt from the rule; they are the rule with nothing subtracted.

The reading is that a map has exactly one binary choice per panel, minus one for the panel it starts from — which is a suspiciously clean statement for a subject where almost nothing is clean, and which holds only because a map’s vertices are four right angles and the smallest-sector lemma is therefore silent at every one of them.

The transition, worked out #

The essay’s closing question — where the cheap test stops being silent — can be given a prediction, and a prediction is more useful than a note saying nobody has looked.

Model each of the $(m-1)(n-1)$ chains as closing with some small probability $\varepsilon$, independently of the others. The share of labellings with no contradiction anywhere is then $(1-\varepsilon)^{V}$, and the three-by-three map fixes $\varepsilon$: four contradictions in two hundred and fifty-six labellings over four chains gives $\varepsilon \approx 0.0039$.

Half the labellings would then contradict themselves at $V \approx \ln 2 / \varepsilon \approx 177$ chains, which is a grid about fourteen panels on a side. On that model the test stays nearly silent until the map is large enough that nobody could enumerate it anyway — which would be a discouraging answer, and it appears to be the wrong one.

The sampled six-by-six grid has twenty-five chains, and the independent model puts its contradictory share at nine per cent. The sample says a quarter. Three times too many is not a sampling wobble.

So the chains are not independent: a contradiction on one makes a contradiction on its neighbour more likely, which is what one would expect of chains sharing creases. The transition is therefore sooner and sharper than the model, and locating it is an enumeration of the four-by-four and four-by-three maps — thirty-two thousand admissible labellings for the first, which is an afternoon rather than a research programme.

Where the difficulty actually is #

If the cheap test is silent on maps, something else must be making them hard, and this collection has the something else measured.

A folding is a labelling together with an ordering of the panels, and the ordering is constrained by two rules the arcs know nothing about. A panel may not lie between a crease’s own two panels when the crease’s image runs through it; and two folds wrapping the same edge of the folded stack may not interleave. Both are statements about overlaps in the folded plane, and they cannot be read off the crease list at all — the folded state has to be computed first.

Those two rules are where a map’s count comes from. Counting the foldings by placing panels and searching every ordering reproduces the published numbers for nine map sizes, and every refusal in that search is one of the two non-crossing rules. The arcs contribute four refusals across the whole enumeration.

So the ranking of the refusals on a map is: the vertex conditions do a great deal, the non-crossing rules do the rest, and the cheap test does one and a half per cent of one size.

What that says about the cheap test #

It would be easy to read this as a disappointing result about the test, and it is not — it is a result about where the test’s strength lies, and the strength is real.

The test is a proof of failure that costs one pass. Where it fires, nothing else needs to be run, and it fires on patterns whose orderings are unreachable: a tessellation patch of a hundred and fifty-seven panels has more orderings than atoms and the test settles it in microseconds.

What decides whether it fires is not size but how many independent closed chains of panels a pattern has, and a map has almost none. A three-by-three map has four interior vertices, so four chains; a tessellation patch has a hundred and twenty-six. The test is looking for a conspiracy among chains, and a map does not have enough of them to conspire.

That is the honest summary: the test is powerful on patterns dense with circuits and silent on patterns without them, and a map is the second kind. Its four interior vertices are the same four interior vertices whether the map is three by three or a metre square, because a larger map is a larger grid with proportionally more of them — but the circuits stay short and local, and short local circuits are exactly the ones the counting theorem has closed.

The one and a half per cent #

The four labellings that do produce a circle on the three-by-three map are worth a sentence, because they are the smallest instance of the phenomenon this collection has found anywhere.

They close a circle of six panels — the shortest available once the four-panel case is excluded — running round two adjacent interior vertices. Their letters satisfy every condition at every one of the four vertices, so nothing local objects; the contradiction is in the chain that encloses two of them.

That makes the three-by-three map the cheapest possible demonstration of the whole account. It has twelve creases, so its labellings can be written down in full; four thousand and ninety-six of them, of which two hundred and fifty-six pass the vertex conditions, of which four contradict themselves in the layers, and each of the three numbers can be checked by hand in an afternoon.

The strip, which is decided, and the map, which is not #

There is a contrast in this subject that this measurement sharpens, and it is worth setting out because the cheap test’s silence is part of it.

A one-dimensional map — a strip — is decidable in linear time: there is an algorithm that says whether a given labelling of a strip folds, and it runs in a single pass. A two-dimensional map has no such algorithm known, and the general problem for arbitrary crease patterns is NP-hard.

The gap between those two facts is where all the interest lies, and the arcs do not live in it. A strip’s panel graph is a path, so the cheap test is vacuous there by the argument above; a map’s is a grid, and the test fires on four labellings out of four hundred and fifty-four. Neither end of the contrast is where the test has anything to say.

What separates them is the non-crossing rules, and specifically how many panels can overlap. On a strip every panel lies on the same line, so the constraints are about intervals and can be processed in order. On a map the panels overlap in two directions at once, and the two directions do not separate — a folding of a map is not a folding of its rows composed with a folding of its columns, which is the natural conjecture and is false.

What is not claimed #

Three things this measurement does not establish, and the second is the one worth being careful about.

It does not say that map folding is easy. The counting problem is open, the decision problem for a general crease pattern is NP-hard, and nothing about a cheap test being silent bears on either.

It does not say the cheap test is never useful on a map. Maps larger than three by three have not been enumerated here — the labelling count doubles with every crease, and a four-by-four map has twenty-four of them — so the share of contradictory labellings at larger sizes is unmeasured. The sampled grids suggest it rises: a six-by-six grid’s labellings agree with themselves in seventy-three draws of a hundred, which means a quarter of them do not. Whether those are the same phenomenon at larger scale, or something the enumeration would have shown differently, is not settled by a sample.

And it does not say the four labellings are unimportant. They are four proofs of impossibility obtained for the price of a single pass, on a problem where every other refusal requires the folded state. Four cheap proofs are four cheap proofs.

The check the enumeration doubles as #

There is a secondary use for a table of noughts, and it is the reason this measurement is worth keeping in the collection’s checks rather than only in an essay.

A test that never fires is indistinguishable, from the outside, from a test that has stopped working. If the arc walk were broken — a sign reversed, an arc dropped, a panel pair mismatched — it would also report nought on every map, and nothing about the output would say which had happened.

The four labellings on the three-by-three map are what tells the two apart. They are a case the test must catch, small enough to verify by hand, and they sit at the end of a ladder of eight sizes on which it must report nothing. A run that reports noughts all the way including the last row is a run in which the instrument has failed; a run that reports eight noughts and a four is a run in which it has worked.

That is the shape every check in this collection is written to: a claim that could fail, with a case that must pass and a case that must not. A ladder of noughts on its own would be worthless.

Where the ladder goes next #

The obvious continuation is upward: enumerate the four-by-three and four-by-four maps and see whether the share of contradictory labellings grows the way the sampled grids suggest. Sixteen million labellings for a four-by-four is not a large enumeration by modern standards, and the vertex conditions cut it to a manageable number before any panel is placed.

The more interesting direction is the one the sampled grids point at. If a quarter of a six-by-six grid’s labellings contradict themselves in the layers, then somewhere between a three-by-three map and a six-by-six one the cheap test goes from doing essentially nothing to refusing a substantial fraction — and where that happens, and what it is a function of, is a question this collection has the machinery to answer and has not asked. The chain count grows as the square of the grid’s side, and the number of ways chains can combine grows as two to that power, so the transition should be sharp. Nobody has looked.