An order with no least element

Two panels of a folded sheet that lie over the same piece of table have to be in some order, and which order is a question with an enormous answer. The machinery for it here enumerates: place a panel that has nothing below it, then a panel whose everything-below is already placed, and repeat until every panel is in a list. It is the expensive half of the pair of instruments this collection points at a folded sheet, and it is the only one that gives a complete answer.

That procedure has a starting condition buried in its first word. It needs a panel with nothing below it, and it needs one at every step of the way down.

On a sheet with an edge there is always one. On the pattern that sheet was cut from there is none.

What the enumeration finds on a patch #

The smallest patch of the square twist tessellation is one period across: nine panels, thirty-six pairs of them lying over one another, thirty-six constraints of the kind that say a panel cannot sit between the two halves of a fold.

Enumerating its stackings takes eleven thousand and eighty-seven steps and returns exactly one.

One flat folded state. Not one of many; the whole answer. That is a striking result on its own for a pattern this collection has drawn hundreds of times — the twist tessellation, at its smallest, admits precisely one way of arranging its paper.

Where the enumeration stops #

Two periods across is twenty-five panels, and the enumeration refuses: a sheet’s orderings grow faster than anything can walk, and the machinery declines at eighteen panels rather than running for ever.

So the largest thing whose stackings can be counted here is a one-period patch, and that is not a limitation of this essay. It is the standing limitation of the whole subject: a cycle in the forced relations can be found on a pattern of two hundred panels in one pass, and an enumeration of orderings gives up at a dozen.

The one-pass test and the enumeration are the collection’s two refusals, and they refuse differently — one cheaply and necessarily, the other expensively and completely. Everything below is about what the second of them assumes.

The assumption #

An enumeration builds a list from the bottom. Formally it is finding the linear extensions of a partial order, and the standard way is to repeatedly take a minimal element — something with nothing below it — put it next, and remove it.

On a finite order there is always a minimal element, because a chain going down has to stop. On an infinite one it need not, and the periodic twist tessellation’s does not.

Its relations have loops in them, and every loop travels: a chain of this above that comes back not to the panel it left but to the copy of that panel one cell over. Follow such a chain downward and it never terminates. Every panel has paper under it, for ever.

So there is no minimal element, and there is nothing for the enumeration to place first.

Two things the enumeration needs, and the second is the one that fails #

It is worth separating the two requirements, because only one of them is about infinity.

The first is that the relations be acyclic. If some chain of this above that comes back to where it started, no order exists and no procedure will find one. That requirement is met here: the periodic pattern’s relations are acyclic, which is what took the whole of a separate argument to establish and is the harder half.

The second is that the order have minimal elements, so that the list can be started. That is automatic for a finite order and false for this one.

The distinction matters because the two failures mean opposite things. A cyclic order means the pattern does not fold. An order with no minimum means the pattern folds and cannot be described by a list — which is a limitation of the description rather than of the paper.

Nothing in the collection’s machinery distinguished them, because on a disc the second never arises.

Not a contradiction #

The temptation is to read no bottom layer as no folded state, and that is exactly the mistake this thread exists to correct.

An order with no least element is a perfectly ordinary order. The integers have none; nothing about them is impossible. What matters for paper is that no two panels are each below the other and that no chain comes back to itself, and neither happens here: the relations are acyclic, the sheet is stacked, and any two panels lying over the same point have a definite order between them.

The reader looking at the folded sheet sees, at every point, a finite stack of paper from bottom to top. It is only the order over the whole pattern that has no floor, and that is not something a reader can look at.

The list-building procedure is what fails, and it fails because it is a procedure for finite objects being applied to an infinite one — which is the same shape of error as the cycle test’s, one level up.

What replaces the question #

If which panel is at the bottom has no answer, something has to take its place, and the replacement is the question this thread has been circling.

In which direction do the layers climb?

The relations of the periodic pattern fall into strongly connected groups, and within each group every closed chain travels the same way: one cell to the right is one layer up, or one cell to the left, or one cell down. The two-period square cell’s sixteen panels fall into two groups of eight climbing in opposite directions.

That is a complete description of the order’s structure at the scale the enumeration was trying to work at, and it is cheap: two or three directions settle every cell here. It says how the sheet is arranged without listing anything, which is the only kind of answer available for an object with infinitely many panels.

Where the patch’s bottom came from #

The patch has a bottom and the pattern does not, and the panels that make up the patch’s are worth locating precisely, because they say what a cut does to an order.

They are at the rim. On the square patch there are one, two and three of them at one, four and nine periods, and every one touches the paper’s edge; on the triangular, honeycomb and elongated patches the counts are two to seven and the answer is the same. Across twelve patches holding between twenty-five and seven hundred and ninety-three panels, not one minimal panel is in the interior.

A panel in a patch’s interior has all the neighbours it has on the pattern, so it inherits everything below it. A panel at the rim has lost some of them to the cut. So the bottom of a patch’s stack is made entirely of panels whose below was cut away, and it is a fact about the edge rather than about the pattern.

The finite pieces are ordinary #

There is a reassuring consequence worth drawing out, because it explains why nobody ever noticed.

Take any bounded region of the folded pattern — any patch, at any size, anywhere. The panels covering it are finitely many, their relations are the pattern’s relations restricted to them, and a finite restriction of an acyclic relation is acyclic. So the region has a bottom layer, has finitely many stackings, and behaves in every way like an ordinary folded sheet.

The pattern is therefore locally an ordinary folded sheet everywhere and globally not one, which is a shape mathematics is used to and paper is not.

And it explains the whole history. Every measurement here has been on a bounded region, every bounded region behaves, and the only way to notice was to build the unbounded object and ask it a question it could not answer.

What this does to the enumeration’s other results #

Nothing, and it is worth saying so clearly.

Every count of stackings this collection has published is a count on a finite pattern with an edge, and on such a pattern the enumeration is exactly right. The preliminary base’s orderings, the map-folding counts, the strip counts — all of them are about discs of paper and all of them stand.

What has changed is the scope. The enumeration was implicitly a general procedure for a folded state, and it turns out to be a procedure for a folded state of a bounded sheet. That is not a small class — it is every piece of paper anybody has ever folded — and it is not everything the collection reasons about, because a tessellation considered as a tessellation is not bounded.

What the climbing direction is worth #

The replacement question is not merely a consolation for the enumeration failing. It answers something the enumeration never could.

An enumeration on a patch gives one number — how many stackings — and a list of them. That is a complete answer about that patch and says nothing about the pattern: a bigger patch has a different count, and there is no sequence of patches whose counts converge to anything, because the enumeration cannot be run on two of them.

The climbing directions are a statement about the pattern, at any size, obtained in a few dozen steps. They say how the sheet is arranged: this half climbs one way, that half the other, and here is a certificate that no chain closes. That is a structural description rather than a census, and it is the only kind available for an object with infinitely many panels.

So the trade is a count for a shape. The count is exact and local; the shape is exact and global; and until a period could be built there was only the first.

What a folder holds #

A patch, always, and the patch has a bottom sheet at its edge.

Fold a bigger patch and the bottom moves outward with the rim. Fold a patch of a hundred periods and the bottom is still one or two pieces of paper at the very edge, with a hundred and sixty thousand panels above them and none below.

That is a peculiar physical fact about these patterns which nobody would guess from folding one. The interior of a twist tessellation interleaves: paper arrives from every direction and is stacked, and no piece of it is at the bottom because whatever is below it is the continuation of some panel from further out. The bottom exists only where the continuation stops.

The one stacking #

The measurement that opens this essay is worth returning to, because it is the strongest thing here and the one least connected to the rest.

Nine panels, one stacking, eleven thousand and eighty-seven steps to establish it. The eleven thousand is the enumeration walking a tree of possible orders and rejecting all but one, and the one is a complete answer: given those letters, there is precisely one arrangement of that paper.

That is a much stronger statement than the one-pass test can make. The cheap test says the letters do not contradict themselves; it does not say the paper can be arranged, and a lettering whose relations close no circle can still have no folded state. Here the enumeration says it can, once, and names the order.

Whether the same is true of the pattern the patch was cut from is not established. A periodic sheet with acyclic relations has an order — that is a general fact about acyclic relations — and how many it has is a question about counting linear extensions of an infinite order, which is not a question this collection has any machinery for.

Where the same shape turns up elsewhere #

The distinction between a folded state existing and a folded state being listable is not confined to this pattern, and two other places in the collection have the same flavour.

A pattern with a freedom. Cut one crease of a folded sheet and the panels no longer close: the composition of reflections stops being determined, and what was a rigid arrangement becomes a family. There the object is still finite and the description that fails is a different one.

A search that visits every prefix. The ordering search visits every partial stacking that survives, and permuting the panels twelve ways does not move its node count at all — because which prefixes survive is a property of the pattern rather than of the order they are tried in. That is the enumeration behaving as well as it can, and it is still exponential.

Both are limits of a procedure rather than of the paper, and both were found by giving the procedure something slightly outside what it was built for. The periodic sheet is the most extreme case: not an object the procedure is slow on, but one it cannot begin.

Which theorem was checked, and how #

The stacking count is produced by an enumeration over the folded state’s overlapping panels, with the two non-crossing conditions applied — a panel may not sit between the two halves of a fold, and two folds in the same place opening the same way may not interleave. It is run on a folded state built from the coordinates rather than on the crease pattern, and the folded state’s own consistency is checked first.

The absence of a minimal panel on the pattern is not asserted from the enumeration’s silence. It follows from every loop travelling, which is established by taking the relations apart direction by direction until nothing is left that a closed chain could use, and which is checked on the patches by counting minimal panels and finding them all at the rim.

And the letters on the patches come from the period rather than from a search on the patch, so the twelve patches are twelve pieces of one arrangement rather than twelve independent answers.

The claim, in three lines #

A patch of this pattern has exactly one stacking — nine panels, eleven thousand steps, one answer — and every patch has a bottom layer at its edge.

The pattern has no bottom layer, because every chain of this above that descends for ever across the lattice, and so the enumeration has nothing to start from.

Neither of those is a defect of the paper. The sheet is stacked, every point of it has an ordinary finite pile over it, and what fails is a description that assumed the panels would run out.

What the picture cannot show #

An order is not a picture. The best a figure can do is count the panels with nothing below them and say where they are, which is what the figure here does — and the interesting object, the order with no floor, is exactly the one with nothing to count.

Nor is there any way to draw the difference between a stack of paper and a stack of paper with no bottom sheet, because at every point of the folded plane they look identical. The difference is a statement about the whole sheet, and every drawing here is of a piece of one.

And the eleven thousand steps for one stacking of nine panels is a number with no successor here. Twenty-five panels is refused, and the growth between nine and twenty-five is the reason: an enumeration over orders is exponential in the panel count, and nine is already eleven thousand. So this essay’s strongest measurement is also its last one of that kind, and everything larger is reasoned about rather than counted.

Nor does anything here count how many orders the pattern has, which is the question the enumeration would have answered if it could start. Counting the linear extensions of an order with no least element is a well-posed question and not one this collection has machinery for, and the honest position is that the pattern is known to have at least one arrangement of its paper and is not known to have exactly one, as its smallest patch does.