A loop that goes somewhere

The cheapest true thing anybody can say about a crease pattern with letters on it is this. Each crease separates two panels, and the letter says which of them ends up above the other when the sheet is folded. That is one relation per crease, obtained by reading the pattern once, and if those relations contain a cycle — this panel above that one, that one above a third, the third above the first — then the letters describe no stacking of paper at all.

It is a genuine proof and it costs one pass over the crease list, which is why it is the only negative answer available on a pattern large enough to be interesting. Enumerating stackings gives up at a dozen panels; a cycle can be found on a pattern of two hundred.

The sentence has a hypothesis in it that has never been written down, and this collection has been applying it for its whole existence to the patterns least entitled to it.

Where the hypothesis is #

The relations are a partial order in the making. Panel a below panel b, b below c, and so on; a cycle says the order is impossible, and no cycle says the order can be completed to a stacking of all the panels from bottom to top.

“All the panels” is the hypothesis. A sheet of paper has finitely many panels because it has an edge, and a finite acyclic set of relations can always be extended to a list. Remove the edge and the panels do not stop.

A periodic pattern — a twist tessellation, a corrugation continued for ever, anything that repeats — has one panel for every panel of one period and every step of the lattice. Its relations are infinite too. What can be written down is the quotient: the panels of one period, with each relation carrying the lattice step it takes. A relation might join two panels inside the same period, or join a panel to one in the period next door.

There is a modest bookkeeping problem in writing that down, and it is worth naming because it is the only technical thing in the essay. The panels of one period are not quite the panels of a rectangle drawn on the pattern: a rectangle cuts some panels in two, and the two halves — one at the left edge, one at the right — are the same panel of the sheet. So the quotient’s panels are the rectangle’s panels with those pairs identified, and each identification records that one half sits a period away from the other. A two-period square rectangle shows twenty-five panels and the sheet has sixteen.

The identifications have to agree with each other. Two different routes from one panel to another must record the same displacement, and if they do not, the drawing was not a period of anything. On every cell here they agree to within a part in a hundred million million, which is the arithmetic saying the rectangle really does repeat.

What a cycle in the quotient is #

Follow a chain of relations round the quotient until it comes back to the panel it started from. Down in the pattern itself, that chain is a chain of relations too — but each step also moves by whatever lattice step its relation carried, so the chain ends not at the panel it started from but at the copy of that panel some number of periods away.

A closed walk in the quotient is a cycle of the pattern only if its lattice steps add to nothing.

A walk that comes back to the same panel one period to the right has not closed. It says: this panel is below the panel one cell to its right, which is below the panel two cells to its right, and so on for ever. That is not a contradiction. It is a stack with no bottom, and an infinite sheet of paper is entitled to one.

The square tessellation says it plainly #

Take the square twist tessellation, one period across and one up, and glue its edges. Four panels, eight creases, four vertices.

Apply the rule that a cycle is a contradiction and the search exhausts in three steps — not runs out of budget, exhausts: a proof that no lettering of this pattern passes. Apply the rule that only a zero-summing walk is a contradiction and a lettering turns up in three steps as well.

At two periods the numbers separate. The first rule exhausts in thirty-five steps and finds nothing. The second finds a lettering in nine. At three periods it is three thousand four hundred and fifty-five against six hundred and twenty-five, and at four the first rule does not finish inside two hundred thousand while the second returns a lettering.

Every one of those exhaustions is a proof, and every one of them is of something false.

The two proofs are different animals #

It is worth dwelling on what an exhausted search is, because the phrase does most of the work in the paragraph above.

A search that runs out of budget has learned nothing: it says the answer was not found in the time allowed. A search that exhausts has visited every possibility the conditions permit and rejected all of them, which is a proof in the ordinary mathematical sense. Thirty-five steps is not a small number of tries; it is the whole of a tree, closed.

So the first rule does not merely fail to find the lettering. It produces a certificate that the lettering does not exist, and the certificate is valid reasoning from a false premise — the premise being that a loop among these sixteen panels means what a loop among the panels of a piece of paper means.

That is a more interesting kind of error than a bug. Nothing in the code is wrong; a sentence in the mathematics is missing.

Which way the loops go #

The lettering the second rule returns has loops in its quotient relations — that is why the first rule rejects it. What those loops do is travel.

On the two-period square cell the sixteen panels fall into two groups of eight. Inside one group every closed walk ends one period to the right of where it began; inside the other, one period to the left. Neither group contains a walk that ends where it started, and no walk crosses between them and comes back.

Read as paper: going one cell to the right takes the reader one layer up, for ever, in one half of the pattern, and one layer down in the other. There is no bottom sheet and no top sheet. Every panel has paper under it and paper over it, and at any particular point of the plane only finitely many panels lie over that point, so the reader looking at the folded sheet sees an ordinary finite stack everywhere and an order with no least element overall.

Why a single direction is not the certificate #

The obvious way to prove that no walk closes is to find a direction in which every walk climbs: a compass bearing such that each loop’s lattice steps, added up and measured along it, come to something strictly positive. Then no sum of loops can be zero, and there is nothing to argue about.

That is sound and it is not enough, and the smallest cell of the square tessellation is the counterexample worth keeping.

Its four panels are all reachable from each other. Among their loops there is one that steps a period to the left, one that steps a period to the right, and one that steps a period down. No direction is positive on both the first two. And there is still no walk that adds to zero — because the only way to get from the left-stepping loop to the right-stepping one and back is a walk that steps down, and nothing anywhere steps up to pay it back. The arrangement is a little like a ring of relations that a construction’s own suggested lettering forces seen from outside: what looks locally like a closed circuit is, in the sheet it belongs to, a spiral.

So the certificate is a sequence rather than a single bearing. Choose a direction on which no loop descends; every relation with room to spare under it can be discarded, because no zero-summing walk could have used it. What is left falls apart into smaller pieces, and the next direction is asked of those. Three directions empty the smallest square cell; two empty the two-period one.

The check that has nothing to do with tori #

An argument this abstract deserves a witness that owes it nothing, and there is one available: write the periodic lettering onto an ordinary square patch and hand it to the instruments that read sheets of paper with edges.

Those instruments are the four vertex conditions and a folded sheet rebuilt from the coordinates and walked for a circle. Neither has any notion of a period, a quotient or a lattice step. On patches of one, four and nine periods, on four tilings, up to fifteen hundred creases and seven hundred and twenty vertices, every vertex condition holds and no patch has a loop.

That is exactly what the theory predicts. A finite patch of an infinite acyclic structure is a finite acyclic structure, so if the loops of the periodic pattern all travel, no square cut out of it can contain a closed one. The check could have come back the other way and did not.

The counts, and the direction they run in #

Two things about the glued cell are worth setting beside each other, because they make the failure of the old rule feel inevitable rather than surprising.

The glued sheet has fewer creases than the rectangle it came from — thirty-two against forty at two periods, a hundred and twenty-eight against a hundred and forty-four at four — because the cut’s severed pairs are reunited. And it has more structure, because every panel now has neighbours on all sides. A rectangle’s rim panels have paper on one side and nothing on the other, so the relations peter out there; on the glued sheet they wrap round and keep going.

Relations that wrap round are exactly the relations that make loops. So the glued sheet has loops for the same reason it has no rim, and a rule that treats every loop as fatal was always going to reject it. What is surprising is not that the rule rejects the glued cell but that nobody had noticed the rule had a domain, and the reason nobody had noticed is that until the sheet with no rim could be built there was nothing outside the domain to try it on.

What the collection had, and what it was #

The test being corrected is not a small piece of machinery. It is the argument behind a proof that reads the crease list once, behind the loop that a construction’s own suggested lettering forces, and behind the whole distinction between letters that agree at every vertex and letters that describe a sheet — which is the difference this collection returns to most often.

None of that is wrong. Every pattern those essays are about is a finite sheet with an edge, and on a finite sheet with an edge acyclicity is exactly right, because “no cycle” and “extends to a stacking” are the same statement about a finite partial order.

What was missing was the sentence saying so. The rule was imported as a cycle means no folded state rather than as a cycle in the relations among finitely many panels means no folded state, and the difference only becomes visible on an object this collection could not previously build.

What replaces it, and what it costs #

The replacement is not free, and the honest accounting is worth giving.

Deciding whether some closed walk sums to zero is much dearer than deciding whether any closed walk exists. Acyclicity is one sweep; the other question needs the walk structure taken apart direction by direction. So the search asks the cheap question first — a lettering with no loop at all in its quotient has no loop in the pattern either, so acyclicity passing is sufficient and settles nearly every step — and only what the cheap question rejects costs the expensive one.

On the two-period square cell that is five of nine steps. On the four-period cell it is fifty thousand five hundred and forty-six of fifty-six thousand seven hundred and seventy-two. The proportion rises with size, because on a larger cell almost every partial lettering has a loop in it somewhere.

The same reading on the other tilings #

The square tessellation is the easiest to describe and it is not a special case.

The triangular tessellation’s period is a rectangle one tiling unit across and $\sqrt3$ up, holding twelve panels, twenty-four creases and twelve vertices at its smallest. The first rule exhausts it in seven steps; the second finds a lettering in eight, and its loops need three directions to rule out. The honeycomb’s cell has the same counts and behaves identically. The elongated triangular tiling’s cell — twenty panels, forty creases, twenty vertices — is exhausted in three steps and lettered in eleven.

At two periods the gap opens on all of them. The triangular cell is exhausted in twelve thousand one hundred and forty-three steps and lettered in four hundred and fifty-five; the honeycomb’s in nine thousand six hundred and nineteen against one thousand and forty-three.

Five tilings, four of them settled, and on every one the same shape: the first rule proves there is nothing, and there is something.

What is still unsettled #

The two answers this gives — a lettering whose loops all travel, or a walk that genuinely closes — do not exhaust the possibilities in principle. A pattern could have loops that neither peel away nor close within any window examined, and the honest report on such a case is that it is open rather than that it is fine. Nothing here has produced one, which is a fact about the patterns tried rather than a theorem.

And the rhombille tessellation, which is the tiling whose vertices are not all alike, does not oblige at two periods: the search does not finish under either rule, so what its glued cell is remains unknown. That is the same tiling that has been the exception to every measurement in this thread, and it is not obviously a coincidence.

What a travelling loop looks like on paper #

The abstract statement has a concrete consequence a reader can check on a patch, and it is worth having because it is the only part of this essay that touches ink.

If every loop travels, no panel of the pattern has nothing below it — follow the chain downward and it never terminates. So on a patch of that pattern, the panels with nothing below them can only be the ones whose neighbours below were removed by the cut.

They are. On twelve patches over four tilings, holding between twenty-five and seven hundred and ninety-three panels, every panel with nothing under it touches the paper’s edge and none is in the interior. The count grows with the rim rather than with the sheet: one, two and three on the square patch as it goes from one period to nine.

What the picture cannot show #

A drawing of the quotient’s relations is a drawing of a graph, and the lattice step each relation carries is a label rather than a direction on the page. So a figure can show the walks and it cannot show the plane the walks are moving through, which is where the whole argument lives. The reader has to hold the picture of an infinite sheet in mind while looking at a finite one.

Nor is a stack with no bottom something a photograph of paper could ever show. Any actual sheet is finite, so any actual folded model has a bottom layer, and it sits at the edge — which is the subject of the essay that asks where the bottom layer of a patch is. The unbounded stack is a property of the idealised infinite pattern, and the idealisation is the thing every claim about a tessellation has always been about.

There is a third thing no figure here shows, and it is the reason the essay is about a test rather than about paper. Whether a set of relations with no closed walk can actually be completed to a stacking of infinitely many panels is a question about orders, not about folding, and the answer is yes for reasons that have nothing to do with creases. What a picture of a crease pattern can show is which relations there are; what it cannot show is why their acyclicity is enough, which is the same gap between a necessary condition and a sufficient one that runs through the whole subject.