Origami & Folding
what one sheet can do
Flat-folding

The order that is its own mirror

Trying a mountain first and trying a valley first are two different searches, and on a hundred and forty-two crease patterns they cost the same number of steps — not on average, not nearly, but identically, pattern for pattern. The reason is a symmetry of every condition the subject has, and it is four lines long.

Assumes The difficulty was in the coin and Why the difference is two.

19 min read 9 figures Flat is rareLocal rules, global behaviour

A search for a consistent lettering has to decide, at every branch, which of the two letters to write first. Replacing that decision with a constant removes a heavy tail entirely, which makes the constant worth recommending — and immediately raises the question of which constant.

There are two available. Try a mountain first, always; or try a valley first, always. They are genuinely different searches: they explore the tree in opposite orders, they return different letterings, and there is no obvious reason for them to agree about anything.

They agree about everything that can be counted.

Trying mountain first and trying valley first cost the sameNode counts for the same lettering search run twice on each of 5 crease patterns, once trying a mountain at every choice and once trying a valley. Every point lies on the diagonal, which is what a symmetry of the problem looks like when it is measured rather than assumed.each point is one patch, searched twice002020404060608080square · 26elongated · 32hexagonal · 39triangular · 39rhombille · 80nodes, mountain firstnodes, valley firstthe dashed line is y = x, and nothing has been fitted to anything
Fig. 1 The same search run twice on each of five crease patterns, once trying a mountain at every choice and once trying a valley. Each point is one pattern. The dashed line is the diagonal, and nothing has been fitted to anything.

Not approximately, and not on average. On the five printed patches, on ninety-six patches swept over a grid of tiling and turn angle, and on forty-six further patterns drawn from four other constructions, the two searches visit the same number of nodes, pattern for pattern, every time. A hundred and forty-two agreements and no exceptions.

The reason is that nothing here reads a letter

Take a crease pattern with a lettering on it and swap every letter at once: every mountain becomes a valley and every valley a mountain. Ask what changes.

Maekawa’s condition asks that the mountains and valleys at an interior vertex differ by exactly two. That is a statement about a difference, and swapping the two counts leaves the difference the same size. The condition is a winding argument rather than a fact about paper, and a winding number changes sign under a reflection without changing magnitude.

The big-little-big lemma forbids the two creases bounding a strictly smallest sector from carrying the same letter. Sameness is a relation between two letters, not a property of either, and it survives a swap intact.

Kawasaki’s condition reads the angles and no letters at all, so there is nothing in it to swap.

And a folded panel’s arcs reverse. The arc a crease contributes to the ordering says which of the two panels it joins lies above the other, and the letter is the only thing that points it. Swap the letter and the arrow turns round. A cycle of arrows becomes the same cycle traversed backwards, and a directed graph is acyclic exactly when its reverse is.

One node per panel: the tapered leaf, at six geometriesNodes visited against panels, for 4 crease patterns of one family searched under a constant letter order. Every point lies on or under the diagonal, which is a search that never backtracks.each point is one pattern: panels across, nodes up0010102020one node per panelnodes visitedpanels3 columns to 6 columns, and not one backtrack anywhere in the family
Fig. 2 The reason is that nothing here reads a letter: the leaf corrugation searched at four sizes, one step per panel every time. The search walks the panels and never consults which way round any crease is, so swapping them all changes nothing it does.

So every condition the subject applies to a lettering is invariant under swapping all of them. The set of admissible letterings is closed under the swap, and the swap is an involution — do it twice and nothing has happened.

Why that forces the step counts to be equal

Closure of the solution set is not by itself enough. Two searches could explore a symmetric problem asymmetrically if anything else about them broke the symmetry.

Nothing does. The rule for choosing which crease to decide next counts how many labellings a vertex has left, and the swap maps a vertex’s surviving labellings one-to-one onto the surviving labellings of the swapped state, so the count is the same and the same crease is chosen. The propagation deduces a letter exactly when every surviving labelling agrees on it, and that condition is preserved. The test for a circle in the arcs gives the same answer on a state and its swap.

Which means the two searches walk mirror-image trees: node for node, in step, each one at the image of where the other is. The costs are not similar. They are the same integer, and they could not have come out otherwise.

Trying mountain first and trying valley first cost the sameNode counts for the same lettering search run twice on each of 3 crease patterns, once trying a mountain at every choice and once trying a valley. Every point lies on the diagonal, which is what a symmetry of the problem looks like when it is measured rather than assumed.each point is one patch, searched twice002020404060608080square · 26hexagonal · 39rhombille · 80nodes, mountain firstnodes, valley firstthe dashed line is y = x, and nothing has been fitted to anything
Fig. 3 The same comparison on three patches of very different sizes — forty-nine panels, seventy-seven and a hundred and fifty-seven. The equality holds at every scale, which is what an argument rather than a coincidence looks like.
One node per panel: a crumple, deepeningNodes visited against panels, for 6 crease patterns of one family searched under a constant letter order. Every point lies on or under the diagonal, which is a search that never backtracks.each point is one pattern: panels across, nodes up00202040406060one node per panelnodes visitedpanels3 folds to 8 folds, and not one backtrack anywhere in the family
Fig. 4 Why that forces the step counts to be equal, on the least structured family there is: one node per panel, whichever letter the search tries first. A crumple has no symmetry to appeal to and the two orders still cost the same.

The same symmetry, in a place the subject already knew about

The swap is not a new object. It has been sitting inside two of the collection’s oldest measurements, unnamed, doing exactly this.

A degree-four vertex admits four flat-foldable assignments, and the four are two mirror pairs. The count has been quoted since the foundation of the collection and the pairing has not, because nothing needed it: four is four however it is arranged. Under the swap it stops being an arbitrary number and becomes twice two — two genuinely different ways of folding the vertex, each available from either side of the paper.

The same is true at every degree. Maekawa’s condition is usually written as mountains minus valleys equals plus or minus two, and the two signs in it are not two cases to be handled. They are one case and its mirror. A vertex with three mountains and one valley and a vertex with three valleys and one mountain are the same vertex, drawn by somebody standing on the other side of the sheet, and the condition’s two-sidedness is a record of that.

Once the swap is named, several counts in the collection acquire a factor of two that was always in them. The number of admissible letterings of a patch is even. The number of consistent letterings is even. The number of distinct folded states is not necessarily even, because two letterings can fold to the same stack, and that gap between the two counts is exactly what the layer census measures.

The involution has no fixed points, so the counts are exactly even

“Even” is stated above as a consequence and it is worth strengthening, because the strong form is what makes the halving safe.

A lettering fixed by the swap would have to satisfy mountain equals valley on every crease, and a pattern with at least one crease has no such lettering. The swap is therefore a fixed-point-free involution on the admissible set, and a fixed-point-free involution partitions its set into pairs with nothing left over.

So the count is not merely even; it is exactly twice the number of genuinely distinct letterings, at every pattern, at every size, with no exceptional case anywhere. That is a stronger guarantee than most parity arguments give — the usual ones have to enumerate the fixed points and rule them out, and here there are none to enumerate.

Which means the two searches are one sample

The practical reading is unwelcome and worth stating, because it is the opposite of what running two constants looks like.

Two constant orders were run so that a claim about fixed value orders would not be a claim about the letter V. What the pairing shows is that the second run was never independent evidence: the valley-first search is the mountain-first search performed on the mirror of the same problem, node for node. Its agreement was guaranteed before anything was measured.

So any quantity averaged over the two constants is the quantity at one of them, and the second column adds no coverage. What it adds is the check — an assertion that nothing in the search reads a letter — which is worth having and is a different thing from a second measurement.

The same argument says how to make the search cheaper rather than merely to understand it. Since every solution comes with a swapped partner, fixing the first crease’s letter loses nothing and halves the tree. That is a free factor of two available to any lettering search in this subject, and it is available precisely because there are no fixed points to lose.

Why measure it at all

The argument above is four lines and it is not difficult. It is also exactly the kind of argument that is right until it is not, and the failure mode is specific: a fifth condition, somewhere, that reads a mountain differently from a valley.

Such conditions exist in the subject. The two non-crossing rules that decide whether a set of panels can actually be stacked are not letter-symmetric in any obvious way — they are statements about which panels lie between which others, and a taco constraint refers to a pair of panels folded round a crease in a particular sense. Anything that brought one of those into the lettering search would break the equality without touching the four conditions above.

So the equality is checked rather than assumed, on every pattern the collection has, as a standing assertion. If it ever fails, something has been added to the search that reads a letter, and the failure will say so on the day it happens rather than long afterwards.

One node per panel: fold-and-cut, one outline eachNodes visited against panels, for 8 crease patterns of one family searched under a constant letter order. Every point lies on or under the diagonal, which is a search that never backtracks.each point is one pattern: panels across, nodes up00224466one node per panelnodes visitedpanelstriangle to star, and not one backtrack anywhere in the family
Fig. 5 Eight fold-and-cut patterns, each searched under a constant order. These are small — seven panels, six creases — and they are in the comparison for the same reason the large ones are: an equality that holds only on the interesting cases is not an equality.

The argument came second

The equality was not predicted and then confirmed. It was noticed in a table.

Two constant orders were measured together for a reason that had nothing to do with symmetry: a single constant is an anecdote, and a claim that any fixed value order removes a search’s tail needs at least two fixed orders behind it or it is a claim about the letter V. So both were run, on everything, and the two columns came back identical — not close, identical, on the first five patterns and then on all hundred and forty-two.

Two identical columns of integers are either a symmetry or a bug. The obvious bug is that the two runs are the same run: an option not being read, a cached result served twice, a default overriding the argument. Ruling that out is the first thing to do and it is easy, because the two searches return different letterings — mirror letterings, differing on every single crease — while agreeing on every count. A caching mistake returns the same answer; this returns the opposite answer at the same price.

Only then is it worth looking for the reason, and the reason is the four lines above. The order matters because it is the order the collection’s habits prefer: a measurement that surprises, then an argument that says it could not have been otherwise, then an assertion that will fail if it ever is.

The witness is a mirror too

The symmetry is not only about cost. Take any consistent lettering and swap every letter: the result is another consistent lettering, of the same pattern, verified by the same conditions and by a folded sheet rebuilt from scratch.

That has a physical reading and it is the plainest one available. Swapping every letter is turning the sheet over. A crease that folded away from a reader folds toward them once the paper is the other way up, and the folded object is the same object seen from behind. Nothing about the model changes because nobody has walked round it.

A lettering of the hexagonal patch that agrees with itselfThe hexagonal tessellation patch, lettered by a search that tests the arcs the letters force at every step rather than after every letter is chosen. Mountain and valley are distinguished by colour and by dash. Every panel of the folded sheet can be ordered consistently with these letters, which is not true of the lettering the construction itself produces.a lettering of the patch that agrees with itselffound by testing the arcs while the letters were chosen, not after41 nodes · 2 backtracks · verified against a rebuilt folded sheet77 panels · 142 creasesits own lettering has no loop in it2 of 200 random letterings agree with themselvesthis one was found in 41 nodes and 2 backtracksit differs from the drawn lettering on 67 of 142 creasesthe drawing is the pattern; nothing here is a picture of the folded object
Fig. 6 A verified lettering of the hexagonal patch. Its mirror — every mountain a valley, every valley a mountain — is also verified, and folding both produces the same object from opposite sides.

Which means the count of distinct letterings a pattern admits is always even, and every one of them is paired. Twenty seeds returning twenty different letterings is therefore returning at most ten genuinely different folded objects, and possibly fewer, since two letterings can differ and still produce the same stack. That is a correction to an earlier count rather than a new measurement, and it is the sort of correction that only shows up once the symmetry is stated.

What it is worth, which is more than tidiness

A symmetry that only saves a measurement is a curiosity. This one does three things.

It halves the space a search has to consider, in principle. Every branch on a crease that no earlier decision has touched has a mirror branch that will produce a mirror answer, so committing the first free crease to a mountain loses nothing: whatever the valley branch would have found, its mirror is in the mountain branch. That is exactly what a constant value order is doing, and it explains why a constant is not merely one arbitrary choice among two — it is the removal of a redundancy.

It makes one measurement stand for two. Every table in this collection that reports a search cost under one constant order is reporting the other one too, and does not have to say so twice. That matters more than it sounds: a column that has to be duplicated is a column that will eventually be duplicated wrongly.

And it puts a floor under a claim that would otherwise be a preference. Recommending “try a valley first” without the symmetry is recommending a superstition — there is no reason paper should prefer valleys, and a reader is right to distrust a rule that reads like one. With the symmetry the recommendation is different in kind: fix the value choice, either way, because the two are the same search and the coin between them is the thing that costs.

Trying mountain first and trying valley first cost the sameNode counts for the same lettering search run twice on each of 3 crease patterns, once trying a mountain at every choice and once trying a valley. Every point lies on the diagonal, which is what a symmetry of the problem looks like when it is measured rather than assumed.each point is one patch, searched twice001010202030304040square · 26elongated · 32triangular · 39nodes, mountain firstnodes, valley firstthe dashed line is y = x, and nothing has been fitted to anything
Fig. 7 Three more patches under the same comparison. A symmetry that held on five patterns and failed on the sixth would be a symmetry with a condition on it, and there is no sixth.

What the symmetry does not do

It does not say the two searches return the same lettering. They return mirror letterings, which differ on every crease.

It does not say anything about a search that is not symmetric. Spending a coin on the value choice breaks the symmetry immediately: a seeded run under one arrangement has no counterpart under the other, and the costs are then two samples from one distribution rather than two names for one number.

And it does not extend to the ordering search. Asking whether the panels of a lettered pattern can actually be stacked is a different question with different constraints, and the meshes that fold at no lettering are the standing reminder that the two questions come apart. The swap maps a lettering to a lettering; whether it maps a stacking to a stacking is a separate claim, and it is true for the same reason — reversing every arc reverses the whole order — but it is true by its own argument rather than by inheritance.

Where it holds and where it stops, measured rather than argued

The four conditions are the whole of what the lettering search applies, so the symmetry covers exactly the lettering search and stops at its edge. Two figures mark the two sides of that edge.

What the coin was buyingThe number of distinct letterings returned by the same search under three orders, on one tessellation patch. A coin at every choice returns a different lettering nearly every run; a constant returns the same one every time, which is what the cheaper cost is paid for.the bar is how many DIFFERENT letterings 20 runs returneda coin at every choice2020 of 20 runs found onea constant, with the coin only on the creases no vertex constrains420 of 20 runs found onea constant at every choice120 of 20 runs found oneon the triangular patch, 83 panels and 142 creases
Fig. 8 Twenty runs under three orders on the triangular patch. The two constant orders are one bar because they are one measurement; the coin’s is a different bar because a coin has no mirror partner to be equal to.

Inside the edge, the equality is exact and the count of distinct witnesses is the only thing that separates the orders. Outside it — as soon as a question is asked that reads which panels lie between which — the swap is no longer obviously harmless, and the collection has a standing example of a question that behaves differently.

Refused at one lettering is not refusedSix developable quadrilateral meshes, each with every labelling of its creases enumerated and every consistent one put to a search over orderings of its nine panels. Two of the meshes fold at no labelling whatever. Two others were refused at the labelling they were built with and fold at others.the bar is how many letterings of the mesh can have their panels stackedout of every labelling of its twelve creases, enumeratedmesh 3016 pass every vertex · 16 agree with themselves · arrived refusedmesh 5032 pass every vertex · 32 agree with themselves · arrived refusedmesh 8832 pass every vertex · 32 agree with themselves · arrived refusedmesh 11832 pass every vertex · 32 agree with themselves · arrived foldablemesh 141416 pass every vertex · 14 agree with themselves · arrived foldablemesh 19416 pass every vertex · 16 agree with themselves · arrived refusedtwo of the meshes have none at all, and two more were refused only at the lettering they came with
Fig. 9 The six quadrilateral meshes, asked whether their letters agree and whether their panels can be stacked. The first question is symmetric under the swap. The second is a different question, and four of the six answer it the other way.

So the honest scope is narrow and worth stating narrowly: swapping every letter is a symmetry of flat-foldability at a vertex and of consistency among the arcs, and nothing here claims it is a symmetry of the global folding problem. That it appears to be one, for the reason given at the end of the previous section, is a separate claim needing its own argument.

The idealisation, named

Everything above treats a crease pattern as a list of segments with letters on them, and a letter as a symbol with no other content. That is the right model for these theorems and it is not the whole of the object.

Real paper has a front and a back, and the two-colouring of the panels decides which side shows where. Swapping every letter turns the model over, which exchanges the two colour classes — so a design that depends on a colour change lands the other colour outward, and to a folder that is not a symmetry at all but the difference between a bird with a white head and a bird with a black one. The mathematics is indifferent and the model is not, and the honest form of the statement is that the conditions are symmetric rather than that the object is.

Paper thickness breaks it too, though less interestingly: a stack of mountains and a stack of valleys distribute their material differently at the fold, which matters to anybody working in a material with a thickness and matters to none of the theorems above.

What a folder would say about all this

There is a version of this essay that a folder would find obvious and a version they would find strange, and the two are worth separating.

The obvious version: turning a sheet over exchanges mountains and valleys. Anyone who has folded anything knows it, and no theorem was needed to establish it. A crease pattern with the letters reversed is the same pattern seen from the other side, and a folder handed one would fold the same model and hold it the other way up.

The strange version is the one the search makes: because that is true, a computer looking for a lettering may commit its very first decision arbitrarily and lose nothing. That does not feel like the same statement, and it is. The reason it feels different is that a folder never faces the decision — the paper is already the right way up, or it does not matter which way up it is — while a search faces it a hundred and twenty-six times on the rhombille patch and has no paper in front of it at all.

The gap between those two versions is most of what makes a search expensive on a problem a person finds easy. A person carries the symmetry without noticing it. A search has to be told.

Where the ladder goes next

The symmetry settles which constant to recommend, by making the question empty: either one, they cost the same, and the choice between them is a choice of which of two mirror witnesses to be handed. What it does not touch is the other decision the search makes. Which of the two choices the cost lives in takes the variable order apart, and finds that the improvement everybody reaches for first is the one that does not pay.

Where this goes next

the dot is one run's cost, ranked; the rule is the constant order1001e+31e+4nodes visited40 seeds, ranked by cost80 nodes, every seed15 unfinished at 20,000same pattern, same conditions, same test at every node — the only difference is which letter is tried first The difficulty was in the coin One tessellation patch, one search, one test at every node — and a cost that runs from eighty-six steps to fifteen thousand depending on nothing but the starting seed. The heavy tail is real, it was measured carefully, and it was made by a single line of the search that nobody had thought of as a choice at all. MVMwalk the folded edge and count the turns:each mountain turns +180°, each valley −180°the walk closes, so the total is ±360° — which forces |M − V| = 2the sheet must come back to where it started Why the difference is two Maekawa's theorem says mountains and valleys differ by exactly two at every flat-foldable vertex. The constant is not empirical — it is a full turn, and the theorem is about winding rather than about paper. 20 panels, two coloursno crease has the same colour on both sidesall 12 interior vertices carryan even number of creasesthe colour is which side of the paperthat panel shows when the sheet is foldedmountainvalleyraw edge The sheet has two sides Read a crease pattern as a set of panels rather than a set of lines and a condition appears that no vertex theorem states: the panels take two colours, no crease has the same colour on both sides, and the colour is which face of the paper each panel ends up showing.

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.

AssignmentThe big-little-big lemmaKawasaki's theoremLayer orderMaekawa's theoremParitySearchSymmetry