A map refuses in small pieces

The test that never fires on a map pointed this collection’s cheapest refusal at the oldest open problem in the subject. The refusal reads a crease list once: 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. Enumerated over every lettering of every map up to three by three, it fired on four of the four hundred and fifty-four letterings that pass every vertex, all four on the three-by-three map and none below it.

Sampled grids had told a different story — about a quarter of a six-by-six grid’s letterings contradict themselves — so somewhere between three and six a side the refusal goes from nothing to a substantial share. The essay predicted where to look and what the transition would look like: the number of ways chains of panels can combine grows exponentially with the map, so the transition should be sharp. Nobody had looked.

It is not sharp. The refusal is almost a local test, and it grows the way local things grow.

Four pinwheels #

The four refused letterings of the three-by-three map have a shape. Each is unchanged by a quarter turn about the middle: turn the map a quarter and every crease lands on a crease with the same letter, the letters round the central panel repeating all the way round. They come in two mirror images, a pinwheel turning one way and one turning the other, and each is lettered both ways round, mountains for valleys. Nothing else a three-by-three map allows is refused.

Where the circle can close is worth being exact about, because it says why three by three is the first map refused. A circle in the arcs is a closed walk from panel to neighbouring panel, each step a crease saying which of the two lies above the other. The shortest such walk goes round a single vertex through its four panels, and that one can never close: the vertex conditions the lettering already passed are exactly the conditions under which those four panels have a consistent order. So a circle has to enclose more than one vertex. A map two cells across has its vertices in a single row and has walks round two or three of them, and on every such map enumerated none of those walks ever closes. The first circles need vertices in two directions — the four of a three-by-three map, which the pinwheel places alike round the central panel.

That is the picture to carry into larger maps. A pinwheel is a statement about the four panels round one small square, and a larger map contains many such squares.

A map’s letterings are easy to count #

Before the refusal can be counted on larger maps, the letterings have to be. On a map every interior vertex is a right-angled crossing of two straight creases, and a vertex like that folds flat only with three creases of one letter and one of the other. So once three of a vertex’s creases are lettered, the fourth is decided: three of one letter forces the other, and two of one and one of the other forces the majority.

Taking the vertices in order and leaving each the crease it is last to reach, every map has exactly one decided crease per interior vertex. A map with $E$ creases and $V$ interior vertices has exactly $2^{E - V}$ letterings that pass every vertex: 256 for three by three, 2,048 for four by three, 32,768 for four by four. The enumeration of the earlier essay was a search through $2^E$ letterings for the admissible ones; they can be written down directly, and — the point for larger maps — drawn uniformly at random by lettering the free creases with a coin and filling in the rest.

Every small refusal is a pinwheel #

With the letterings in hand, each can be read twice: whole, by the one-pass refusal on the entire map, and window by window, by the same refusal on every three-by-three piece of it.

The table has three parts.

No map two cells across is refused at any length enumerated: two by two, four by two, six by two, none of their 2,184 letterings between them. A map two cells across has no interior panel, so it has no three-by-three window for a pinwheel to sit in, and the counts say it has nothing else either.

Up to five by three, every refused lettering contains a refused window. The four-by-three map refuses 64 of its 2,048 letterings, and every one of the 64 has a pinwheel in one of its two three-by-three windows. The five-by-three refuses 760 of 16,384, all with a pinwheel in one of its three windows. Four by four is the first map where that fails: it refuses 2,112 of 32,768, of which 2,048 contain a pinwheel and 64 do not.

And the share refused is almost exactly what independent windows would give. If each three-by-three window were refused one lettering in sixty-four, independently, a map with $w$ windows would be refused $1 - (63/64)^w$ of the time. For four by three that is 3.10 per cent against 3.13 measured; for five by three 4.61 against 4.64; for four by four 6.11 against 6.45, more than half the difference being the 64 refusals no window explains. The windows overlap and share creases, so they are not exactly independent, and the small excess on four by three and five by three is that overlap.

The first refusal no window explains #

The four-by-four map is the smallest on which the refusal has something to say that no small piece says. Its 64 non-local refusals pass every vertex and every three-by-three window, and are refused only as a whole: the circle the letters force runs through panels that no window contains together. They are a thirty-third of the four-by-four map’s refusals, and they are the first evidence that the test is not merely counting pinwheels.

They are also the reason the prediction of a sharp transition was not absurd. A test that can find circles of any size on a larger map has more ways to fire as the map grows, and the number of possible circles does grow exponentially. What the counts show is that on maps this size the long circles are rare beside the short ones: every long circle the test finds on four by four, there are thirty-two pinwheels.

Larger maps, sampled #

Past four by four the letterings number in the millions, but they can be drawn uniformly, and each drawn lettering read both ways.

A six-by-six map has sixteen three-by-three windows. Drawn fifteen hundred times, its letterings are refused 24.8 per cent of the time — the earlier sampling’s “about a quarter”, now with a reason — and 22.7 per cent have a pinwheel in some window, as in the drawing. The independent-window estimate for sixteen windows is 22.3 per cent, which the pinwheel refusals match to within the sampling; the other 2.1 points are refusals with no pinwheel anywhere.

Eight by eight, with thirty-six windows, is refused 49.2 per cent of the time; ten by ten, with sixty-four, 70.1. The independent-window curve gives 43.3 and 63.5, and the refusals a pinwheel explains are 44.3 and 65.5 — the open dots, a point or two above the curve, where overlapping windows are slightly more often refused together than apart. The solid dots, all refusals, sit a few points higher again, and the gap between them — the refusals no small piece explains — is nothing up to five by three, 0.2 of a point at four by four, 2.1 at six by six and about five at eight and ten.

So the transition is smooth. The share refused climbs as a geometric function of the number of windows, which grows as the square of the side, and nothing about it is sharp: there is no size at which the test switches from saying nothing to saying a great deal, only a steady accumulation of places where a pinwheel can land. The earlier essay’s instinct that the combinations would multiply was right about the circles and wrong about which circles matter.

A check that fits in a window #

The counts have a use for anyone lettering a map-like pattern by hand. Nine refusals in ten, on the sampled maps, are visible in a three-by-three window, and a pinwheel is a pattern of twelve letters that can be recognised by eye, since the whole of it is unchanged by a quarter turn about its central panel. Scanning a lettering window by window for the four pinwheels costs a fixed amount per window and finds nearly everything the one-pass refusal finds, without building the folded sheet at all.

The refusal itself is already cheap — one pass over the crease list, as the proof in one pass described — so the window check is not a faster algorithm. It is a better explanation. A refused lettering of a large map is, nine times in ten, a lettering with a small pinwheel in it somewhere, and the fault is confined to twelve creases that can be pointed at. The one refusal in ten that no window explains is the one that needs the whole map to find, and no twelve creases to blame. That tenth is where the whole-map refusal earns its keep over any window.

That split also says something about where the exponent comes from in the counts of a map’s foldings. The number of letterings is $2^{E - V}$, which grows with the area; the pinwheels remove a fixed fraction per window, which also scales with the area; so both the letterings and the refusals the cheap test sees grow at rates set by the map’s size, and neither carries the difficulty that makes the number of foldings hard to compute. The difficulty is in the letterings the cheap test passes and no folding exists for, which it cannot see by construction.

What the drawings leave out #

They show letters, not arcs. Each map is drawn as its crease pattern, mountains and valleys, and the circle that refuses it is not drawn: it is a walk through panels, and a picture of it would be a second diagram laid over the first. The pinwheels are recognisable without it, and the refusal is checked by the one-pass test rather than read off the drawing.

The sampled lettering is one of hundreds. The six-by-six drawing is the first refused lettering the seeded sampler met with a pinwheel in it; another draw would put the pinwheel somewhere else, and occasionally in two windows at once.

And the curve is a comparison, not a model. $1 - (63/64)^w$ is what independent windows would give; the windows share creases, so they are not independent, and the curve is drawn to show how close independence comes rather than as a law the shares obey.

What these counts rest on #

The refusal is the one-pass test, a circle in the arcs the letters force, and nothing more. A lettering it passes may still have no folded state; the lemma that says nothing and the lettering nobody could draw are about what lies beyond it. The counts here are of what this one cheap test sees, which is the question the earlier essay asked.

The letterings are weighted equally. Every lettering that passes every vertex counts once, whether it folds in one way or a thousand, so the shares are shares of letterings and not of foldings. The count counts labels is the reminder that a map’s foldings are counted differently.

The large maps are sampled. Six, eight and ten a side are fifteen hundred, twelve hundred and eight hundred letterings drawn uniformly with a fixed seed; the shares carry sampling error of a point or so, and the claim that the rise is smooth rests on the exact counts below four by four and the sampled ones above it together.

A window is a three-by-three piece. The pinwheel is the smallest refused pattern, and counting windows of that size is the natural first test of locality; the non-local refusals on four by four might be pinwheels of a larger kind, patterns in four-by-four windows, and they have not been classified.

Pinwheels in a row #

The six-by-six drawing has its pinwheel in one window of sixteen, and at that size a pinwheel is still an event: the expected number in a lettering is a quarter. The arithmetic changes with the area: at sixty-four windows and a chance of one in sixty-four each, the expected number of pinwheels in a lettering is one, and a lettering with none is the less usual case — 36.5 per cent of them by the curve, 34.5 by the ten-by-ten sample, which also has the few refusals without any pinwheel to account for. A large map’s typical lettering is refused because it is typical, not because anything in it is special: pinwheels are simply common once there are enough places for them.

Where the hardness is not, again #

The earlier essay concluded that map folding’s difficulty is not where the cheap test looks, and this is the other half of that conclusion. The cheap test is mostly local, and map folding is not. Nearly everything it refuses, it refuses because of four panels round one square turning the wrong way; what makes counting a map’s foldings hard — two directions that will not separate — is the interaction of rows and columns across the whole sheet, which is exactly what a pinwheel is too small to see.

It connects to results about crease patterns in general. A contradiction is even found crease patterns’ layer contradictions coming in parity-bound loops; the pinwheel is the smallest loop a map can have, and the fact that it comes in mirror pairs lettered both ways is the same even-ness showing on a grid. Local is not global is the general warning, and here it points the other way from usual: a global test turned out to be doing local work.

Still open: the long circles #

The non-local refusals are the part worth classifying. Sixty-four on four by four, a few per cent of letterings on the sampled maps: they are circles in the arcs that no three-by-three piece contains, and whether they are larger pinwheels — patterns in four-by-four windows that recur the way the small pinwheel does — or genuinely long circles running across the map would say whether the test is local at a larger scale or has a truly global part. The four-by-four ones can be read off one at a time; the answer is a census of 64 drawings.

The shares for larger maps would test the curve’s shape. If the non-local part stays a few points while the windows do the rest, the share approaches one as $1 - (63/64)^{(m-2)(n-2)}$ does, and a map of twenty a side is refused all but a sliver of the time. If the non-local part grows faster, it eventually dominates; sampling at fifteen and twenty a side would say which.

Sideways from here, the map that is not a rectangle and the glued maps of the later essays change the number of windows a sheet has without changing its area, and the window count predicts how often the cheap test fires on each.

The habit worth carrying is about growth. When a count of failures grows with a structure, count the smallest places a failure fits before counting the ways failures combine. The ways combine exponentially; the places grow as the area; and here the places were almost the whole of the answer.