The machine's misses have no short list

A strip of equal stamps folded flat is a pile: the stamps read from bottom to top, with each crease an arc at one end joining two of them. The weakest folding machine in the subject makes one kind of move. It picks a line across the partly folded strip and turns everything on one side over onto the other, taking every layer the line crosses. Fourteen states are one pile found that this machine makes every pile of six stamps and misses fourteen of the 462 piles of seven, all of them one pile turned. Nine stamps have piles of their own counted nine directly — 484 misses among 4,536 piles — and found that some misses were inherited from eight stamps and some were new, among them a nine-stamp version of the seven-stamp tuck.

It ended with a question about the shape of the answer. If the machine’s misses can be described by forbidden piles, the way a flat-folding theorem forbids a local arrangement at a vertex, is the list short? At seven there was one forbidden pile, up to turning. At nine there was at least one more. Eleven would say whether the tucks were a family, one for each odd length, and whether anything else was joining them.

Twelve stamps, by the same two halves #

The method is the one the nine-stamp essay used, and it was always cheaper than that essay feared. A pile of equal stamps is a folding exactly when the creases at each end of it do not cross, and two creases at one end cross exactly when their height intervals interleave. So the foldings can be listed by building piles from the bottom up and testing each crease the moment both its stamps are placed, which keeps the listing far below the $n!$ orderings it would otherwise try. The machine is simulated on rows of cells, each cell a stack of stamps, and a fold carries every cell on one side of a boundary over onto the other side, reversing their order and turning each stack over.

Neither half reads the other. The listing gives 14,060 foldings of ten stamps, 46,310 of eleven and 146,376 of twelve, the classical stamp-folding counts that the oldest open problem is about; the machine finishes 12,040, 36,152 and 106,816 piles, and never one the listing calls impossible. Both run in seconds at twelve stamps. At thirteen the listing takes half a minute and gives 485,914 foldings, of which the machine reaches 316,332.

The first figure is what those counts say together. The machine makes every pile to six stamps. Then its share falls, by a few points at a time and then faster: 97.0 per cent at seven, 89.3 at nine, 78.1 at eleven, 73.0 at twelve, and 65.1 at thirteen.

The table carries the counts the rest of this essay reads. Missed piles: 14, 64, 484, 2,020, 10,158 and 39,560 from seven to twelve stamps. Of those, inherited from one stamp fewer: none at seven, all 64 at eight, 324 at nine, 2,008 at ten, 8,964 at eleven and 39,444 at twelve. The rest are new.

Why a reached pile stays reached when it shrinks #

The inheritance test asks whether a pile, with one of its end stamps taken off and the rest renumbered, is a pile the machine misses one size down. The nine-stamp essay noticed that the test ran one way perfectly — no reached pile of nine shrank to a missed pile of eight — and the counts here say the same at every size: from eight stamps to twelve, not one reached pile shrinks to a missed one. That is not a coincidence that might fail at the next size. It has a reason.

Take any sequence of folds that makes a pile of $n$ stamps, and delete the last stamp from every cell at every step. Until the last stamp has been folded onto something, it sits alone in a cell at one end of the row, and a fold that turns over only that cell becomes a fold that does nothing. Every other fold still takes every layer of what remains, and still lands each cell on the cell it landed on before. So the same sequence, with its do-nothing folds dropped, makes the shorter pile. The first stamp works the same way. Whatever the machine can make, it can make with an end stamp missing.

Turned round, that is a statement about misses. If a pile shrinks to a missed pile, the pile itself is missed, because otherwise its shrunk version would be reached. So every miss contains a smallest miss: take end stamps off it, one at a time, choosing at each step an end whose removal leaves a missed pile, until no end will do. What is left is a pile the machine misses although it makes both piles one stamp shorter. Those smallest misses are the forbidden piles the earlier essay was asking about, and the machine’s misses are exactly the piles that contain one.

How many forbidden piles there are #

So the size of the list is the number of new misses at each length, and the counts settle the question the earlier essay could only frame. Seven stamps add 14 smallest misses; eight add none; nine, 160; ten, 12; eleven, 1,194; twelve, 116; thirteen, counted the same way, 7,786. The odd sizes add more each time, by a factor between six and a half and eleven, and the even sizes, which add almost nothing at first, went from twelve to 116 in one step of two.

A short list would have shown itself as a run of zeros. Eight looked like the start of one: every miss of eight stamps is inherited from seven, which is what made the earlier essay suspect a single forbidden pile. Ten breaks that at once, with twelve misses no miss of nine explains, and every size since has added more than the one two before it. The list does not close on any size counted, and its growth says it is not about to.

The difference between odd and even lengths is the most striking thing in the figure and it is not explained here. One part of it is visible in the drawings: the tuck, the simplest forbidden pile, exists only on odd strips, because on an even strip the crease joining the last stamp falls at the same end of the pile as the crease joining the first two and the wrap would cross it. Whether the whole of the odd sizes’ excess comes from constructions that need an odd length is a question about thousands of piles, not one.

The tuck at eleven #

The specific prediction checks out. 0 10 1 2 3 4 5 6 7 8 9 is an accordion of nine stamps with stamp 10 wrapped round it from the top and slid into the fold that holds stamp 0 at the bottom. The machine cannot make it. Take stamp 10 off and the rest is a plain accordion of ten stamps; take stamp 0 off and the rest is the accordion with its last stamp moved to the bottom. The machine makes both. So the eleven-stamp tuck is a smallest miss, as the seven- and nine-stamp tucks are, and the thirteen-stamp tuck is one too.

The tucks are a family, one at every odd length counted. That alone makes the list of forbidden piles infinite if the family continues, since no tuck contains a smaller one: removing either end stamp from a tuck leaves a pile the machine makes. Whether every odd tuck is missed is not proved here. What is shown is that it holds at seven, nine, eleven and thirteen, and that each tuck’s two shrunk piles are accordions the machine folds by doing the obvious thing.

The comparison worth making is with the oldest machine-characterisation result in computing. Knuth showed in 1968 that the orderings a single stack can sort are exactly those avoiding one pattern of three, so a machine with one kind of move was described completely by one forbidden configuration. The all-layers folding machine is also a machine with one kind of move, and the closure under removing an end stamp is the same kind of property that made Knuth’s description possible. Its list of forbidden piles is the opposite of his: not one pattern but thousands by thirteen stamps, still growing.

Classes broken in part, at every size since nine #

The other symmetry the earlier essays measured is the turn: move a pile’s bottom stamp to the top and a folding becomes a folding of another marking. At seven and eight stamps the machine’s misses were whole classes under turning, and at nine that broke, with eight classes missed only in part and 52 reached piles turning into missed ones.

It has broken further at every size since. At ten stamps 36 classes are missed in part and 236 reached piles turn into missed ones; at eleven, 170 classes and 1,168 piles; at twelve, 620 classes and 4,340 piles. At eleven the picture is the one drawn here: of 569 classes the machine misses anything from, 399 are missed whole and 170 in part, the partial ones missing anywhere from four to twelve of their twenty-two piles. Turning is a symmetry of the foldings and has stopped being anything like a symmetry of the machine.

Every marking still folds, and fewer fold every way #

None of this means the machine fails to fold a marked strip. Every pile is a folding of exactly one marking, and on every marking of every strip counted at least one of its foldings is a pile the machine makes. That part is a theorem: Arkin, Bender, Demaine and colleagues proved in 2004 that a one-dimensional pattern that folds flat can always be folded flat by a sequence of simple folds, and deciding is not making draws the line between that question and the one asked here.

What the machine loses is choice, and it loses more of it with every stamp: the share of markings on which some folding is out of reach is 22 per cent at seven stamps, 59 at nine, 82 at eleven and 87 per cent at twelve. On the worst marking of twelve stamps the machine can make fewer than a quarter of the marking’s foldings. The deciding question stays trivial; the making question gets steadily harder.

Where the share is going #

The machine’s reach grows by a nearly constant factor: 3.05, 2.97, 3.00 and 2.95 for the steps to nine, ten, eleven and twelve stamps, and 2.96 and 2.93 from twelve to fourteen, where the simulation alone was run to 927,400 piles. The foldings grow by 3.26, 3.10, 3.29 and 3.16 over the same steps, alternating because odd and even strips differ, and the stamp-folding counts are known from long series to settle at a rate of about three and a half. If both rates hold, the share of foldings the machine can make falls toward zero geometrically, losing roughly a tenth of what it has with every stamp.

That is a measurement, not a proof. Nothing here bounds the machine’s growth rate from above, and a reach growing by just under three a stamp at fourteen could in principle speed up later. What the counts rule out is the opposite reading of the earlier essays — that the machine’s misses were a small, exotic set at the edge of its reach. By twelve stamps more than a quarter of the foldings are out of reach, and the fraction is still growing.

What a falling share means for a press #

The all-layers machine is not an abstraction. A press brake, a laminator and a person folding a long strip by halving it repeatedly all make this move and no other, and the question the counts answer is the one anybody designing for such a machine has to ask: if a stacking is wanted, can the machine produce it?

On short strips the answer was always yes, which is the finding where the machine catches up made at six stamps and which made the machine look complete. Past six it is usually yes and then decreasingly so, and the decrease is not spread evenly. The misses are the piles containing a smallest miss, so a designer can tell in advance which stackings are at risk by looking for the forbidden shapes inside them, and the commonest of those is a stamp wrapped round an accordion and slid into the fold at its base. That is precisely the arrangement a hand makes without thinking — tucking the end of a strip into the first fold to lock it — and the machine cannot make it at any odd length measured.

The easiest strip needs the deepest reach suspected that equal stamps were easy only because they were short. The counts here make the suspicion a number: by twelve stamps a quarter of the stackings are beyond the machine, by thirteen more than a third, and the list of reasons why is already thousands long. A machine whose failures have no short description is a machine whose reach has to be computed rather than predicted, which is the practical content of the result.

Three things the counts leave unexplained #

Why odd lengths add so many more obstructions than even ones. The tuck explains one obstruction per odd length; it does not explain 1,194 at eleven against 116 at twelve.

Whether every odd tuck is missed. Measured at four odd lengths. A proof would have to say why no sequence of whole-stack folds can slide a stamp into the fold that holds the bottom of an accordion from outside it.

What a reached pile and its missed turn differ by. The 52 pairs at nine stamps, and the thousands since, are where a description of the machine in terms of the folds it lacks would come from, and they have not been read.

Equal stamps and a machine that cannot choose #

The stamps are equal. Equal stamps make every crease sit exactly at one end of the pile, which is what makes the non-crossing test exact and the cells of the simulation line up; the fold a machine can make measured unevenly creased strips, where none of this applies. A pile is a stacking read without its marking, and every count is of piles. The machine is the one that takes every layer; the machine that may choose how many layers to take reaches everything, so every miss here belongs to the lack of that choice.

Paper has no thickness, so a fold turns a stack over exactly in place. A real press would offset the layers by their thickness and change which folds are possible at all; that is not modelled.

Two halves that never read each other #

The listing and the simulation must agree with the layer solver pile for pile, at six and seven stamps in the census figure and from four to eight in the earlier essay, before any larger count is believed. The simulation must never finish a pile the listing rejects, at every size: it never does.

At every size from eight to twelve, no pile the machine reaches may shrink to a missed pile; the argument above says it cannot, and the count checks it rather than trusting it. At every odd size the tuck must be a new miss with both its shrunk piles reached, and at every size from nine on the new misses must be more than none.

Every marking must keep a reached folding, which is the published theorem checked on 4,032 markings.

Still open: a reason for the odd lengths #

The counts leave one regularity sharper than any other. Odd strips add obstructions by the thousand and even strips by the hundred, and the ratio is not settling. The tuck is the one construction known to need an odd length, and it accounts for one pile per size; a second construction with the same parity requirement, or a reason the ends of an odd strip lie at opposite ends of the pile while an even strip’s lie together, would be the start of an account. The smallest misses at eleven, 1,194 piles in classes of twenty-two, are few enough to sort by shape.

The second lead is the one the earlier essay named and this one did not reach. The partly missed classes pair a reached pile with a missed one a single turn away, and the sequence that makes the reached pile says exactly which fold the missed one would need first. Reading those pairs would describe the machine by the folds it lacks rather than the piles it cannot finish, and there are now thousands of them to read.

Sideways from here, a machine that can only crimp is weaker again, and the same two counts — reach, and smallest misses by size — would say whether its list of obstructions grows the same way or closes. Every cheap test misses a shape found the same pattern on the other side of the subject: a finite list of obstructions that looks complete on small cases and acquires new members as the cases grow.

The habit worth carrying is about characterising a machine by what it cannot do. Before looking for the short list of things a machine cannot make, check that what it can make is closed under shrinking; if it is, every failure contains a smallest one, and counting the smallest ones size by size says at once whether a short list exists. Here it said no, at the second size where the earlier essays could have asked.