Origami & Folding
what one sheet can do
Flat-folding

The lettering that was proved impossible

A search closed its whole tree on a glued square tessellation and reported that no mountain-and-valley assignment of it is consistent. Written onto ordinary patches of one, four and nine periods and handed to the four vertex theorems and a folded sheet rebuilt from scratch, the assignment it says cannot exist passes every check, on four tilings, up to fifteen hundred creases.

Assumes A loop that goes somewhere and Consistent is not foldable.

21 min read 9 figures The pattern is the objectLocal rules, global behaviour

There is a kind of result in this collection that is stronger than a measurement and weaker than a theorem: an exhausted search. A search that runs out of time has learned nothing about the pattern. A search that visits every lettering the conditions permit, rejects all of them, and stops because there is nothing left has proved something, and the proof is as good as the conditions it applied.

That last clause is where the trouble is, and this essay is about what happens when it goes wrong in the most alarming possible way: the conditions are sound individually, the search is correct, the tree really is closed, and the conclusion is false.

The proof

Take the square twist tessellation and cut a rectangle exactly two periods across and two up. Join its opposite sides so that a crease leaving one side is the crease arriving at the other, which is what the pattern already says — the drawing repeats, and the rectangle was only ever a way of writing it down. The result has sixteen panels, sixteen vertices and thirty-two creases.

Now search it. Propagate the four conditions at every vertex; wherever they stop deciding, branch; at every step ask whether the letters so far describe a possible stack of paper, using the rule this collection has used from its first essay — that a cycle among the relations the letters force is a proof of impossibility.

The search exhausts in thirty-five steps. Every branch closes. There is no lettering of this pattern that satisfies the conditions and has no cycle.

Two tests on a sheet with no edgeFor each tiling, one 2×2 glued cell searched twice. The middle column applies the collection's own rule that a cycle in the layer arcs is a contradiction, and it exhausts with nothing found. The right column asks instead whether a cycle's lattice steps add to zero, and finds a lettering.the same 2×2 glued cell, searched under two rulesa cycle is a contradictiona cycle whose steps add to zero isand what the loops dothe square gridnothing, in 359 nodesevery loop travels (2 directions)the triangular gridnothing, in 12,143455 nodesevery loop travels (2 directions)the honeycombnothing, in 9,6191,043 nodesevery loop travels (3 directions)the elongated triangular tilingnothing, in 9,123162 nodesevery loop travels (5 directions)the rhombille tilingunfinished at 200,000unfinished at 200,000—“nothing, in n” is an exhausted search: a proof that the pattern has no consistent lettering, which is false
Fig. 1 The exhaustion, on five tilings. The middle column is a search that closed its tree; the right column is the same search with one condition replaced.

Everything in that paragraph is true. The conclusion it is usually taken to support — that the pattern has no flat folded state — is not.

One period of the square twist tessellation, with its edges joinedThe crease pattern of a single repeating cell of a twist tessellation on the square grid, drawn on the rectangle it repeats in. The rings mark where a crease meets a side of the cell: each one on the left is the same crease as one on the right, and each on the bottom the same as one on the top. Joined that way the 40 pieces are 32 creases, the 25 drawn panels are 16, and all 16 vertices are interior.one period of the square grid's twist tessellationa ring is where a crease leaves and returns on the far side40 crease pieces → 32 creases25 drawn panels → 16 panels16 vertices, every one interiorV − E + F = 0mountainvalleyraw edge
Fig. 2 The pattern the search closed its tree on: two periods of the square twist tessellation, with the rings marking the eight creases that leave one side of the rectangle and return at the other.

The suspect condition

Three of the four vertex conditions are about angles and counts at a single point and have no opinion about the sheet as a whole. The fourth thing the search applies is not a vertex condition at all: it is the test for a cycle, and a cycle is a contradiction only when the panels are finitely many.

The glued sheet’s panels are not finitely many. Sixteen is the number of panels per period, and the pattern has one copy of each for every step of the lattice. A cycle written down among the sixteen may or may not be a cycle among the infinitely many, depending on whether it comes back to the panel it left or to a copy of it some distance away.

Replace the test with the one that reads the lattice step each relation carries, and the same search on the same pattern returns a lettering in nine steps.

What the search was actually doing

It is worth walking through the thirty-five steps, because the number is small enough to think about and the shape of the tree explains why nothing looked wrong.

The propagation runs first. The conditions at each of the sixteen vertices admit four labellings apiece — the twist patches are the most decided vertices in the collection — and writing one letter anywhere forces a great many others through the shared creases. On this pattern the propagation alone settles most of the sheet, which is why the tree is thirty-five nodes rather than thousands.

Then, at each node, the cycle test. And on a glued cell it fires almost immediately, because the relations wrap: a panel at one edge of the rectangle is joined to a panel at the other, so the chains of this above that have nowhere to run out. Nearly every partial lettering of a glued cell has a loop in its relations somewhere, and the test rejects every one.

The tree closes not because the pattern is over-constrained in any interesting way but because one of the four tests answers no to almost everything it is shown. That is what a wrong test looks like from the inside, and from the inside it looks exactly like a right test on a hard pattern.

Which is right

Two searches, two answers, and the disagreement is about a rule rather than about arithmetic. That is exactly the situation in which an argument from first principles is least convincing and a witness is most convincing, so the lettering is taken out of the setting it was found in and handed to instruments that know nothing about it.

The instruments are the ones this collection uses on a sheet of paper. The first reads a crease pattern and checks developability, Kawasaki, Maekawa and the big-little-big lemma at every interior vertex. The second builds a folded state from the coordinates by reflecting panel after panel, and walks the relations for a circle. Neither has any notion of a period, a lattice or a quotient; both are the ordinary machinery for an ordinary patch.

The letters are written onto ordinary patches by reduction. Every crease of a patch is moved by whole periods until it lands inside the fundamental rectangle, where it coincides with exactly one crease piece, and it takes that piece’s letter. Nothing is chosen: a crease the reduction cannot place would be counted and reported rather than given a default, because a letter supplied by the transfer rather than by the periodic solution is the one thing that could make this check pass for the wrong reason. Across every patch here the count of unplaced creases is zero.

The lettering that was proved impossible, checked on paper with an edgeEach bar is one clipped patch carrying the periodic lettering, its length the number of creases. Every patch passes all four vertex conditions and has no forced loop in its layer order, on 4 tilings and at 3 sizes.the impossible lettering, on ordinary patchessquare ×140 creases16 vertices · every condition holds · no forced loopsquare ×2144 creases64 vertices · every condition holds · no forced loopsquare ×3312 creases144 vertices · every condition holds · no forced looptriangular ×1116 creases48 vertices · every condition holds · no forced looptriangular ×2424 creases192 vertices · every condition holds · no forced loophexagonal ×1116 creases48 vertices · every condition holds · no forced loophexagonal ×2424 creases192 vertices · every condition holds · no forced loophexagonal ×3924 creases432 vertices · every condition holds · no forced loopelongated ×1184 creases80 vertices · every condition holds · no forced loopelongated ×2688 creases320 vertices · every condition holds · no forced loopthe bar is the crease count; the note is what the ordinary checks said
Fig. 3 The lettering the search proved impossible, on twelve ordinary clipped patches. Every vertex condition holds and no patch has a forced loop.

The answer

Every check passes, everywhere.

On the square tessellation: forty creases and sixteen vertices at one period, a hundred and forty-four and sixty-four at two, three hundred and twelve and a hundred and forty-four at three. All conditions hold. No forced loop.

On the triangular tessellation: a hundred and sixteen creases and forty-eight vertices, four hundred and twenty-four and a hundred and ninety-two, nine hundred and twenty-four and four hundred and thirty-two. The same answer.

On the honeycomb and on the elongated triangular tiling: the same, up to fifteen hundred and twelve creases and seven hundred and twenty vertices.

A lettering that a closed search tree says does not exist is, on every finite piece of paper it has been written onto, an entirely ordinary lettering.

What the numbers do as the patch grows

There is a second reading of the twelve rows that is worth taking separately from the first.

The counts triple and then double: forty creases, then a hundred and forty-four, then three hundred and twelve on the square; a hundred and sixteen, four hundred and twenty-four, nine hundred and twenty-four on the triangular. The number of vertices at which something could go wrong runs from sixteen to seven hundred and twenty across the twelve patches, and the number of relations that could close a circle runs with it.

If the periodic lettering were wrong in any local way — a letter attached to the wrong crease by the reduction, a period slightly mis-measured, a vertex whose sectors are not quite what they are supposed to be — the number of opportunities for that to show grows with every row and the probability of it hiding falls. Twelve rows on four tilings at three sizes is a reasonably searching test of a claim that is, in the end, one claim about one lettering.

And the rows are not merely consistent with each other; they are consistent with the argument’s prediction, which is stronger. The argument says no patch has a loop at any size. A rule of thumb that happened to work at one period and started failing at three would be a different situation entirely, and it is the situation the check exists to rule out.

Why the check is the right one

It would be a poor check if it could not have failed, so it is worth saying exactly what would have made it fail and why the outcome was not guaranteed.

If the loops in the glued pattern’s relations really did close — if some chain of this above that came back to where it started — then a large enough patch would contain the whole chain, and the folded sheet built from that patch would have a circle in it. The circle would be found by the same one-pass reader that finds every other one. So the check is a genuine test of the claim, with a definite prediction: at some patch size a loop appears, or no patch has one.

The reason it comes out the way it does is a short argument about orders rather than about paper. A finite piece of an acyclic structure is acyclic; there is nothing to inherit. So if the loops of the infinite pattern all travel, no square cut out of it can hold a closed one, at any size. The patches confirm the argument rather than substituting for it, and they confirm it in the direction that could have gone wrong.

The certificate for the square cell's loopsEach row is one step of the argument that no closed walk in this lettering's layer arcs has its lattice steps adding to zero. A direction on which no loop descends removes every arc with slack to spare; what remains splits into smaller strongly connected pieces and the next direction is asked of those. 2 directions empty it.ruling out the square cell's loops, one direction at a timewhat is left splits248 arcs go, 24 remaindirection (1, 0)102 arcs go, 10 remainwhat is left splits010 arcs go, 0 remaindirection (-1, 0)102 arcs go, 10 remainwhat is left splits010 arcs go, 0 remainthe bar is how many arcs are still in play after the step
Fig. 4 Why the loops travel: each direction removes the relations no zero-summing walk could use, and what remains splits into pieces that climb opposite ways.
One node per panel is a table sizeEach dot is one crease pattern: across, how many labellings the conditions at a vertex leave on average; up, how many search nodes it costs per panel. The dashed line at one is where the grid, the leaf, the Miura and the crumple sit exactly. The twist patches, whose vertices keep four labellings, are at half of it; the Yoshimura as it is normally drawn keeps thirty and is just below one.labellings a vertex keeps, against nodes a panel costs0.000.250.500.751.00481530the box-pleating gridthe tapered leafa crumple, deepeningthe waterbombthe Yoshimura, as drawnthe Yoshimura, tiltedthe twist patcheslabellings the conditions leave at a vertexthe dashed line is one node a panel, which four of these families sit on exactly
Fig. 5 Where these patterns sit among everything else here: the twist patches keep four labellings at a vertex, which is why the propagation settles so much of a glued cell before any branch is taken.

The one tiling that will not say

Four tilings give the same answer and the fifth declines to give one.

The rhombille tessellation is the only one here whose vertices are not all alike — six rhombi meet at a lattice point and three at a triangle’s centre — and it has been the exception to nearly every measurement in this thread. Its glued cell at one period behaves like the others: the old rule exhausts in a hundred and eighty-seven steps and the new one finds a lettering in twenty. At two periods neither search finishes inside two hundred thousand steps, so there is no witness to put back on a patch and nothing to report.

That is recorded as an absence rather than smoothed over. The claim of this essay is about the letterings that were produced, on the tilings that produced them, and the rhombille at two periods is simply unknown.

What the vertex conditions were doing all along

There is a detail here worth separating, because it is easy to read this essay as saying the conditions were wrong.

They were not. Every lettering the exhausted search rejected satisfies developability, Kawasaki, Maekawa and the big-little-big lemma at every vertex, including the one the second search returns. The vertex conditions never distinguished between the two answers, and could not have, because they are statements about one point at a time and the disagreement is about the sheet.

That is the same division of labour the collection has drawn since the essay on the two conditions at a point: the local conditions decide what a vertex may carry, and something else entirely decides whether the sheet can be stacked — the same split that makes a lettering agreeing with itself a weaker thing than a folded sheet. What is new is that the second half turns out to have a hypothesis about the sheet’s shape which the first half does not.

Which theorem was checked, and how

Every claim above is made by a different piece of machinery from the one that produced it, which is the only arrangement in which a witness means anything.

The lettering is produced by a search on the glued pattern. It is verified by the pattern reader that computes sector angles from coordinates and applies the four conditions, and by a folded state built by composing reflections outward from a seed panel. The folded state’s own consistency is checked before anything else: two routes to the same panel must agree about where it is, and on these patches they agree to within about one part in ten thousand million million. A pattern that failed that would be refused rather than reported.

The reduction that carries the letters from the period onto a patch is checked by counting: every crease of every patch is placed, and a patch with an unplaced crease appears in the figure as a failure rather than being quietly completed.

And the whole thing is checked once more by size. If the transfer were subtly wrong — a letter mapped to the wrong crease somewhere — the error would be local, and a larger patch has more places for it to show. Three sizes on four tilings is twelve opportunities for a systematic mistake to appear, and none does.

What joining the edges does to the countsOne row per glued cell: how many panels the drawing shows and how many the sheet has, how many crease pieces are drawn and how many creases those are, how many vertices there are, and Euler's number. Every one of the 12 cells gives V − E + F = 0, which is what a torus gives.gluing a cell's opposite edges, on five tilingspiecespanelsdrawncreasesverticesV−E+Fsquare ×19412840square ×225164032160square ×349368472360triangular ×123123424120triangular ×2694811696480triangular ×31391082462161080hexagonal ×123123424120hexagonal ×2694811696480hexagonal ×31391082462161080elongated ×133205240200elongated ×210580184160800elongated ×32171803963601800a torus has V − E + F = 0, and these three counts are made three different ways
Fig. 6 The glued cells the letterings come from, counted three ways. Euler’s formula for a torus is a check on the three counts rather than a summary of them.

What a folder would see

Nothing unusual, which is the point.

A reader who prints a patch of this pattern and folds it will fold an ordinary twist tessellation. The letters are the letters. Every crease is a mountain or a valley, every vertex behaves, and the sheet collapses. There is no visible trace of the fact that a search once produced a certificate saying the arrangement was impossible, because the certificate was about an object with no edge and the paper in the reader’s hands has one.

What a folder cannot see is the thing the certificate was actually about: the layers of the unbounded pattern have no bottom. Fold a patch and the bottom layer is a piece of paper at the rim; fold a larger patch and the bottom layer is a piece of paper at the larger rim, further out. Take the rim to infinity and the bottom goes with it. Every finite model has one and the pattern has none, which is a difference of the same kind as the one between a patch and the plane it was taken from, and where the bottom layer of a patch actually sits is the measurement that makes that concrete.

The error worth naming

The failure here is not a bug and it is worth being precise about its shape, because this collection is full of code that could fail the same way.

A bug is a piece of machinery that does not do what its author intended. Here the machinery did exactly what was intended: it applied a test that is correct, complete and cheap for the objects it was designed for, to an object outside that class, and it reported the answer that test gives. There is no line to fix, and no amount of testing the machinery against patterns of the kind it was written for would have found it — which is the same reason a checker’s own limits are worth an essay. The repair is a sentence — among finitely many panels — that had never been written down because nothing had ever been outside the class.

That is a defect of a kind the collection has caught before: an instrument silently narrower than the claim made on its behalf. It is the reason a witness is taken outside its own setting whenever one is available, and the reason an exhausted search is reported as this rule found nothing rather than as there is nothing.

What it costs to prove the wrong thingThe bar is how many nodes the collection's own consistency rule takes to exhaust its search of a glued cell — that is, to prove that no lettering of it is consistent. The note gives what the rule that reads each arc's lattice step cost instead, on the same cell, to find one.proving the glued square cell has no lettering1×1, 4 panels3proved there is none · the other test found one in 32×2, 16 panels35proved there is none · the other test found one in 93×3, 36 panels3,455proved there is none · the other test found one in 6254×4, 64 panels200,000still running at the budgeta bar at the budget is a search still running, not a proof
Fig. 7 The cost of the proof that turns out to be of something false, against the cost of finding the thing it says does not exist.

One more thing the patches say

There is a second reading of the twelve patches that has nothing to do with the disagreement and is worth taking on its own.

A finite patch of this lettering has a bottom layer — some panel with nothing underneath — and the pattern it is cut from does not, because every loop in its relations travels rather than closing. So the patches ought to have their bottom layers at the rim, and only at the rim.

They do, at every size on every tiling: one, two and three panels with nothing below them on the square patch at one, four and nine periods, and every one of them touching the paper’s edge. That is the same claim as this essay’s, read as a property of the paper rather than of the search.

The bottom of the stack sits at the paper's edgeFor each patch carrying a periodic lettering, the bar counts the panels with nothing below them in the order the letters force — the bottom of the stack. The note gives the panel count, how many panels touch the paper's edge, and where the minimal ones are. On all 10 patches every one of them is at the edge.panels with nothing below them, and where they aresquare ×1125 panels, 16 of them touching the edge · all 1 at the edgesquare ×2281 panels, 32 of them touching the edge · all 2 at the edgesquare ×33169 panels, 48 of them touching the edge · all 3 at the edgetriangular ×1369 panels, 39 of them touching the edge · all 3 at the edgetriangular ×25233 panels, 79 of them touching the edge · all 5 at the edgehexagonal ×1469 panels, 39 of them touching the edge · all 4 at the edgehexagonal ×27233 panels, 79 of them touching the edge · all 7 at the edgehexagonal ×310493 panels, 119 of them touching the edge · all 10 at the edgeelongated ×12105 panels, 48 of them touching the edge · all 2 at the edgeelongated ×23369 panels, 96 of them touching the edge · all 3 at the edgethe sheet these letters belong to has no such panel at all
Fig. 8 The same twelve patches, asked a different question: which of their panels have nothing below them, and where those panels are.

What the picture cannot show

A figure of a patch carrying these letters is a figure of a patch. It looks like every other patch in the collection, and that is the whole content of the check — so the picture can only show that nothing is wrong, which is a weak thing for a picture to do and a strong thing for a check to report.

Nor can the check be pushed much further than it is. The largest patch measured here has fifteen hundred creases, and larger ones are refused rather than drawn, because the drawing a period was cut from covers a bounded piece of the plane and a patch asked for beyond it comes back missing creases at one corner. That refusal is deliberate: a patch with creases quietly missing would pass every check in this essay and mean nothing at all.

One period of the elongated twist tessellation, with its edges joinedThe crease pattern of a single repeating cell of a twist tessellation on the elongated triangular tiling, drawn on the rectangle it repeats in. The rings mark where a crease meets a side of the cell: each one on the left is the same crease as one on the right, and each on the bottom the same as one on the top. Joined that way the 52 pieces are 40 creases, the 33 drawn panels are 20, and all 20 vertices are interior.one period of the elongated triangular tiling's twist tessellationa ring is where a crease leaves and returns on the far side52 crease pieces → 40 creases33 drawn panels → 20 panels20 vertices, every one interiorV − E + F = 0mountainvalleyraw edge
Fig. 9 One period of the elongated triangular tiling’s twist tessellation, which is where the largest witness comes from: a rectangle one unit across and two-and-a-bit up, holding twenty panels.

And no picture can show the difference between this lettering folds and this lettering folds every finite piece of paper it is written on, which is the honest statement of what has been established. The second implies the first for the infinite sheet only through the argument about acyclic orders, and that argument is prose. A reader who does not believe it has twelve rows of evidence that every patch behaves, and no picture of the sheet the patches were cut from, because there is no such picture to draw.

Where this goes next

the same 2×2 glued cell, searched under two rulesa cycle is a contradictiona cycle whose steps add to zero isand what the loops dothe square gridnothing, in 359 nodesevery loop travels (2 directions)the triangular gridnothing, in 12,143455 nodesevery loop travels (2 directions)the honeycombnothing, in 9,6191,043 nodesevery loop travels (3 directions)the elongated triangular tilingnothing, in 9,123162 nodesevery loop travels (5 directions)the rhombille tilingunfinished at 200,000unfinished at 200,000—“nothing, in n” is an exhausted search: a proof that the pattern has no consistent lettering, which is false A loop that goes somewhere Every crease says which of its two panels lies above the other, and a loop in those statements is a proof that the pattern has no flat folded state. On a sheet with no edge that sentence is false. The loops of a periodic pattern carry a lattice step each, and a loop that ends one cell to the right is not a contradiction — it is a stack of paper with no bottom layer. the same drawing, cut out of the plane and glued upnodes, log scale, against periods across the sheet10100100010⁴10⁵1×12×23×34×4glued upcut outan open mark is a search that ran out of budget rather than a cost What the rim was doing One rectangle of a twist tessellation, cut out of the plane in the ordinary way, gives up a consistent lettering in forty-eight steps. Join its opposite edges so that no crease is divided and the same drawing, at the same vertices, under the same conditions, takes fifty-six thousand seven hundred and seventy-two. The edge of the paper was never the difficulty. It was the slack. the square twist, sieved three timesevery lettering4,0962 to the 12passes every vertex2566.3% of themletters are consistent2524 force a loop of panelshas a folded state80.20% of themthe bars are on one scale, so the last one is the size of the answer against the size of the question Consistent is not foldable The square twist has 4,096 mountain-valley labellings. Two hundred and fifty-six satisfy every condition at every vertex; two hundred and fifty-two of those have letters that do not contradict themselves; and eight have a folded state. So the cheap proof that reads the letters in one pass accounts for four of the two hundred and forty-eight failures, and the other two hundred and forty-four are refused by a search over orderings that nothing shorter replaces.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

What links here

Every essay whose body links to this one.

The objects this essay names

Each one links to every other essay that touches it.

AssignmentCrease assignmentExhaustive searchInterior vertexKawasaki's theoremLayer orderMaekawa's theoremPanelPeriodicityTessellation