Nine stamps have piles of their own

A strip of equal stamps folded flat is a pile: the stamps read from bottom to top, each joined to the next by a crease at one end or the other. Fourteen states are one pile measured which piles a folding machine can make when every fold it makes takes all the layers the fold line crosses — the machine that cannot tuck, because it cannot open a gap in a pile and slide a stamp in.

It found three things. The machine reaches every folding of up to six stamps. At seven it misses fourteen piles, and the fourteen are one pile seen from every starting stamp: the tucked pile 0 6 1 2 3 4 5, an accordion of five with the last stamp wrapped round it and slid into the fold holding the first. And at eight stamps the sixty-four misses are exactly the piles that shrink to the tucked pile when a stamp is taken off an end — nothing new, the obstruction of seven with a stamp on.

It ended on a prediction and a caveat. The prediction was that nine stamps would again miss only what they inherit. The caveat was that the symmetry holding the misses together — turning a pile, bottom stamp to the top — had been measured on the machine’s reach from four stamps to eight and never proved.

Both fail at nine.

Counting nine without a solver #

The earlier counts listed each marked strip’s foldings with a layer solver, which is general — it takes any lengths and any creases — and refuses above eight segments, because the cost of being general grows too fast. Equal stamps do not need that generality.

A pile of equal stamps is a folding exactly when its creases do not cross. Crease $k$ joins stamps $k$ and $k+1$, and on a strip of equal stamps the creases alternate ends: crease 0 at the right-hand end of the pile, crease 1 at the left, and so on. Each crease spans the heights of the two stamps it joins, and two creases at the same end cross precisely when their height intervals interleave — one starting inside the other and finishing outside it. A pile whose same-end creases all nest or keep apart can be folded; any other cannot. Listing every ordering of nine stamps and keeping those that pass gives 4,536 foldings, the known count for nine stamps.

The machine is simulated on the same objects. A partly folded strip is a row of cells, each a stack of stamps. A fold at the boundary between two cells carries every cell on one side over onto the other: their order along the row reverses, each stack turns over, and they land on top of the cells they meet or underneath. From nine cells of one stamp each, every sequence of folds is followed until a single cell is left; every pile finished that way is a pile the machine reaches. Nine stamps give 4,052.

Neither half reads the other, and before a nine-stamp number was believed both were checked against the layer solver at every size it reaches. From four stamps to eight the direct count and the solver agree pile for pile — the same foldings and the same misses, not merely the same totals. The machine never finishes a pile the non-crossing test rejects.

324 inherited, 160 new #

At nine stamps the machine misses 484 piles. The earlier test for inheritance applies unchanged: take a stamp off either end of the strip, renumber, and ask whether what is left is one of the sixty-four piles the machine misses at eight.

324 of the 484 pass that test. 160 do not. In the other direction the rule still holds exactly: every pile of nine stamps that shrinks to a missed pile of eight is itself missed, so no reached pile hides an inherited obstruction. Inheritance is a sound account of some of the misses and not a complete one.

The simplest of the new misses is the one the tucked pile predicts by analogy. 0 8 1 2 3 4 5 6 7 is an accordion of seven stamps with stamp 8 wrapped round it from the top and slid into the fold holding stamp 0 at the bottom — the seven-stamp tuck with a longer accordion inside it. Remove stamp 8 and the rest is a plain accordion of eight, which the machine folds at once. Remove stamp 0 and the rest is the accordion with its last stamp moved to the bottom, which the machine also folds. So the nine-stamp tuck is missed at nine and shrinks to reached piles either way: a new obstruction, not an old one with a stamp added.

The two tucks are the same construction, and there is no eight-stamp tuck between them. The tucked pile at seven wraps an accordion of five; at nine, an accordion of seven. At eight the same arrangement, 0 7 1 2 3 4 5 6, is not a folding at all. Creases alternate ends along the strip, so on an even strip the crease joining the last stamp lies at the same end of the pile as the crease joining the first two, and the wrapped stamp’s crease, running from the top of the pile down to the second place, interleaves with the first crease’s and crosses it. The tuck exists only on odd strips, and the machine misses it on each of the two odd strips counted past six. Whether that continues at eleven stamps is the obvious next count.

Classes that are missed in part #

The other new thing is structural. At seven and eight stamps the machine’s misses were a union of whole classes: a class is a pile together with its turns — bottom stamp moved to the top, again and again — and each of those read downward, $2n$ piles for $n$ stamps. The foldings are closed under turning, and the machine’s reach was too.

At nine stamps the foldings still fall into 252 classes of exactly eighteen, the count the earlier essay gave in advance. The machine’s misses do not. Twenty-four classes are missed whole, and eight are missed only in part — four of them missing eight piles of eighteen, two missing six and two missing four. Fifty-two missed piles lie in classes where the machine reaches the rest.

So turning a pile is not a symmetry of the machine at nine stamps. It is still a symmetry of foldings — turning a folding gives a folding of a different marking — but the machine’s reach is no longer carried onto itself.

The first pile drawn is one the machine folds. Turn it once — bottom stamp to the top — and it becomes a folding of another marking that the machine cannot produce. Turn it again and the machine can fold the result. Fifty-two reached piles turn into missed ones this way. Nothing like it happens at any size below nine: to eight stamps, every turn of a reached pile is reached.

Every marking still folds #

A miss is a pile the machine cannot finish, and it is worth being exact about what that does and does not cost a folder, because the distinction is the one deciding is not making drew for this whole family of machines.

Every pile is a folding of exactly one marking — one assignment of mountain and valley to the strip’s creases — and a strip of nine stamps has 256 markings. The first question anybody asks of a machine, the one the fold a machine can make asked of an unevenly creased strip, is whether it can fold a marked strip flat at all.

It always can. On every marking of six, seven, eight and nine stamps at least one of the marking’s foldings is a pile the machine reaches, so the all-layers machine flattens every marked strip of equal stamps it is handed. What it loses is choice. At seven stamps, fourteen of the sixty-four markings have a folding the machine cannot produce — one each, the fourteen turns of the tucked pile. At eight, forty of a hundred and twenty-eight. At nine, a hundred and fifty-two of two hundred and fifty-six: on most markings of nine stamps, the machine can fold the strip flat and cannot fold it into every flat state the marking has.

That is the shape where the machine catches up first measured from the other side, when it found this machine reaching every one of a six-stamp strip’s states — a machine that looked complete because the strips were short. The easiest strips in the subject, equal stamps with every marking foldable, are the ones on which the weakest machine seemed to lose nothing, and the easiest strip needs the deepest reach already suspected that the ease was a property of the size. Nine stamps is the size at which the suspicion is measured: the deciding question stays trivial and the making question stops being.

What the counts are counts of #

The numbers of foldings — 16, 50, 144, 462, 1,392, 4,536 — are the classical stamp-folding counts, and the oldest open problem is where they enter the subject: nobody has a formula for them, and every value is an enumeration. The misses have that character too. Fourteen at seven, sixty-four at eight and 484 at nine are a sequence with no known rule, and the split of the 484 into 324 inherited and 160 new says the sequence is not generated by any single operation on the one before it.

It also says something about the classes. The foldings divide into classes of $2n$ because turning and reversal act on them with no fixed point, which is why each count is $n$ times a semimeander count. The machine’s misses divided the same way at seven and eight, so the misses could be counted in classes — one at seven, four at eight. At nine the natural count is no longer a count of classes. The misses are 24 whole classes and 52 loose piles, and a sequence of misses counted in classes would stop being a sequence of whole numbers at exactly the size where it would have been most interesting.

Why the symmetry held as long as it did #

The symmetry of the foldings is simple, and the earlier essay gives it in three sentences. The bottom stamp’s crease at each end of the pile is an arc from the bottom to some height, and every other arc at that end lies wholly below that height or wholly above it. Moving the stamp to the top turns its arc into one from that height to the top, which puts the arcs that were below it outside and the arcs that were above it inside — still crossing nothing — so a folding turns into a folding. The machine’s reach has no argument like that behind it. A sequence of whole-pile folds that makes one pile can be expected to be rewritten into a sequence that makes the turned pile only if every fold in it can be rewritten, and nothing guarantees that.

What the counts to eight showed is that the rewriting happened to succeed on every pile small enough to measure. With few stamps the machine’s sequences are short, and a short sequence has little room to depend on where the pile starts. At nine stamps there are sequences long enough for the turned pile to need a fold the original did not, and the machine, which can only fold everything, cannot supply it.

That is the reading of the result worth carrying, and the counts support it without proving it: a property of a machine measured on small inputs is a property of short sequences, and it can stop being true at the first size where the sequences grow a step longer than every argument about them.

What the count assumes #

The stamps are equal. Equal stamps are what make the non-crossing description exact and the cells of the simulation line up. A strip with creases at uneven places is the other case the earlier essays measured, where the same machine is stopped on every marking; nothing here is about it.

The machine is the all-layers one. A fold takes every layer the fold line crosses, on top or underneath, from either side. The machine that may choose how many layers to take reaches the tucked pile and everything else; the misses here belong to the machine that cannot choose.

A pile is a stacking, read without its marking. Each pile is a folding of exactly one marking of the strip, and the counts are of piles. The earlier essay listed the fourteen markings of the seven-stamp misses; the nine-stamp misses carry their own, and they were not needed to count.

And the enumeration is exhaustive at nine and stops there. Every ordering of nine stamps is tried and every sequence of machine folds is followed. Ten stamps is 3.6 million orderings and a larger fold tree, well within reach of the same method, and it is not run here.

A single forbidden pile, and why there is not one #

The earlier essay raised a possibility this subject rarely has: that the machine might be characterised by one forbidden configuration, the tucked pile, the way a flat-folding theorem forbids a local pattern at a vertex. At eight stamps the evidence fitted — every miss contained the tucked pile once the right stamp was removed.

Nine stamps closes that door, at least in its simplest form. The new misses do not shrink to the seven-stamp tuck by removing end stamps, and the nine-stamp tuck is a second obstruction of the same kind rather than a consequence of the first. If the machine has forbidden configurations, it has one at seven and at least one more at nine, and the partly missed classes suggest others that are not tucks at all. A description by forbidden piles would have to be a family, one for each odd length at least, and whether it closes is exactly what a count at eleven would say.

That is the same shape of result as every cheap test misses a shape, from the other side of this subject: a finite list of obstructions that looks complete on small cases and acquires new members as the cases grow, because the thing being characterised is a global property of sequences and the obstructions are local descriptions of their failures.

Still open: eleven stamps, and the misses that are not tucks #

Eleven stamps would test the odd-length pattern directly. If the tuck of an accordion of nine with the last stamp slid into the first fold is missed there and not inherited, the tucks form a family indexed by odd lengths; if not, nine is where something else took over. Ten equal stamps have 14,060 foldings and eleven about three times as many; the orderings to try grow faster than that, and the fold tree faster still, but a count by the method here is a long computation rather than an impossible one.

The partly missed classes are the other lead. Fifty-two piles whose turns the machine reaches are the cleanest place to find what the machine lacks, because a reached pile and a missed one differ by a single turn, and the fold sequence for the reached one says exactly which fold the missed one would need. Reading the difference off those pairs would give an account of the machine in terms of the folds it cannot make rather than the piles it cannot finish.

Sideways from here, the crimping machine is weaker again and its reach on equal stamps could be grouped into the same classes; if its misses are also whole classes to some size and break at the next, the breaking size would measure how long each machine’s sequences have to be before turning stops being free.

The habit worth carrying is about symmetries measured rather than proved. A symmetry that holds on every case measured is a hypothesis with a sample size, and the sample was chosen by what was cheap to count. Turning held from four stamps to eight and was reported as holding on every strip measured, which was true; the first size a different method could reach was the first size it failed.