Origami & Folding
what one sheet can do
What it costs to know

A proof in no nodes at all

A parity refuses a sheet before any search begins. It costs one addition, it is certain, and it says nothing about why — while a search that exhausts on the same sheet costs thousands of nodes and produces a proof of the same fact. Two proofs of one thing, and the cheap one is available only where somebody has noticed the invariant.

Assumes A short reason to say no and The seam carries a sign.

19 min read 7 figures Local rules, global behaviourFlat is rare

Saying no is usually dearer than saying yes in this subject. A yes is a witness — here is the lettering, check it — and a no is the absence of one, which has to be established by looking everywhere.

Occasionally it is the other way round, and the glued sheets give the cleanest instance the collection has.

The cheap refusal

A loop of paper with three creases round it does not fold flat. The proof is one addition: three is odd, crossing a crease exchanges which face of the paper is up, and a path that comes back to its start having exchanged an odd number of times has come back the wrong way up.

That costs no search at all. Nothing is explored, nothing is enumerated, and the answer is certain.

Which bands fold, on each of the two sheetsFor a cylinder and for a Möbius band, whether a strip with that many creases across it has a flat folded state. A cylinder needs an even number and a Möbius band an odd one, and the reason is that a composition of reflections turns the paper over when there are an odd number of them while the two gluing maps differ in exactly that.which bands foldcreases across the strip123456nofoldsnofoldsnofoldsfoldsnofoldsnofoldsnocylinderMöbius bandthe gluing map of a cylinder is a slide and of a Möbius band a slide with a flipand a composition of k reflections turns the paper over exactly when k is odd
Fig. 1 Both glued bands at six crease counts. Half of the twelve entries are refused by an addition — even on a cylinder, odd on a Möbius band — and the refusal costs one arithmetic operation apiece.

The dear refusal

Now ask a search the same question.

A search over letterings does not know about the parity. It picks a crease, assigns a letter, propagates the consequences through the vertex conditions, and backs up when something contradicts. To establish that no lettering works, it has to exhaust — visit every branch and find each one dead.

On a small object that is cheap. On the collection’s glued cells it is not: running the disc’s consistency test on a glued sheet exhausts in three, thirty-five and three thousand four hundred and fifty-five nodes at one, four and nine cells, and does not finish at two hundred thousand for sixteen.

One node per panel: the orthogonal grid a box-pleated base is drawn onNodes visited against panels, for 9 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 up00100100200200one node per panelnodes visitedpanels2 by 2 to 16 by 16, and not one backtrack anywhere in the family
Fig. 2 Search cost against size for a family of patterns. Exhausting is the expensive branch of every one of these, and it is the branch a no requires.

Same fact, two proofs, and the costs are not comparable.

Both are proofs

It is worth insisting on this, because a cheap answer invites the suspicion of being a heuristic.

The parity argument is not a rule of thumb and it is not probabilistic. It establishes that no flat folded state exists, for every arrangement of that many creases, at every position and every angle. It is stronger than the search’s answer, which is about one drawing.

The search’s answer is also a proof, and it has a property the parity’s does not: it applies to a specific drawing whose creases might be at any angles at all, including ones where the parity is satisfied and the sheet still refuses.

How far each band is from closingFor every band measured, the largest disagreement between the composed reflections and the gluing map, in widths of the strip. A band that folds reads zero to rounding. The rest do not read the same number: a band with the wrong parity misses by the whole of its linear part, and one with the right parity and the wrong angles misses by a translation.how far from closing, in widths of the stripcylinder · 14.00off by 4.00 of a widthcylinder · 20.00closescylinder · 34.00off by 4.00 of a widthcylinder · 40.00closescylinder · 54.00off by 4.00 of a widthcylinder · 60.00closesMöbius · 14.00off by 4.00 of a widthMöbius · 22.00off by 2.00 of a widthMöbius · 34.00off by 4.00 of a widthMöbius · 42.00off by 2.00 of a widthMöbius · 54.00off by 4.00 of a widthMöbius · 62.00off by 2.00 of a widtha bit says which bands refuse; a distance says how badly
Fig. 3 How far each band is from closing. The bands refused by parity sit at two — a whole wrong linear part — and the bands with the right parity and the wrong angles sit at four, which no counting argument reaches.

What the cheap proof gives up

Three things, and they are what a search buys.

It gives up the reason. Three is odd is a complete proof and it does not say which part of the paper is in trouble. A search’s failure has a location: the branch died at this crease with these letters, and here is the vertex that could not be satisfied.

It gives up generality in the other direction. The parity applies to every band with that crease count and says nothing about any particular one. A drawing whose parity is fine and whose geometry is not gets no help at all — and a Möbius band creased square across the strip has the right parity at every odd count and folds at none of them.

It gives up being findable. A search can be run on an object nobody understands. A parity has to be noticed first, and the noticing is the hard part: the collection folded and glued sheets for some time before anybody wrote down that the seam contributes a factor.

The panel cycle of a Möbius bandThe 4 panels of the band as a cycle, with a sign on every step: −1 at each crease, because crossing one turns the paper over, and −1 at the seam, because the gluing does. The product round the loop is −1, so the band has no two-colouring — and nothing in the drawing changed between the two sheets.the colouring, as a product round one loop−1−1−1−11234the product is −1, so the loop refuses4 creases at −1the seam at −1product −1so no two-colouring existsthe seam is the one step the drawing does not put a crease at, and it carries a sign anyway
Fig. 4 The four-crease Möbius band as a cycle of panels with a sign on every step. The refusal is the product coming out at minus one — which is a proof, is one multiplication, and had to be seen before it could be computed.

What a certificate is

The two proofs differ in a way that has a standard name, and borrowing it makes the comparison sharper.

A certificate is a short thing a sceptic can check. For a yes, the certificate is the lettering: hand it over, and anybody can verify it satisfies every vertex condition in time proportional to the number of vertices. For a no, there is usually no such object — the absence of a lettering is not a thing that fits on a page.

The parity is a certificate for a no. It is one integer and one sentence, and checking it is counting the creases a loop crosses. That is why the refusal is cheap in a stronger sense than the computation is fast: it is cheap to communicate, which is what makes it usable by somebody who does not trust the computation.

An exhausted search is not a certificate. Its output is a claim to have looked everywhere, and verifying that means looking everywhere again. The collection has written at length about what that costs, and the short version is that a no established by exhaustion is a claim about a computation rather than a fact about an object.

So the two proofs differ not only in what they cost to produce but in what they cost to believe.

The invariant, and where it came from

It is worth saying how a counting invariant gets found, because the answer is not by looking for one.

The parity of a glued band was not derived. It came out of a construction built for a different purpose — gluing a rectangle’s edges to ask what a boundary is worth — and the sign on the seam appeared as a factor that had to be there for the arithmetic to come out right.

That is the usual route. Maekawa’s condition is a winding argument that somebody noticed about a folded cross-section. The two-colouring is an observation about which face of the paper shows. Neither was arrived at by asking what quantity is preserved here.

Which means the supply of cheap refusals is not something that can be worked on directly. It grows when somebody builds an object that separates two things previously equal, and looks at what the arithmetic then requires.

The cost of not having one

There is a concrete number for what the parity is worth, and it is worth quoting because it is larger than the argument’s length suggests.

The collection’s glued cells are searched for a consistent lettering. On the sheets the parity refuses, the search was being run anyway, and on a nine-cell object exhausting takes three thousand four hundred and fifty-five nodes; at sixteen cells it does not finish within two hundred thousand.

So the parity saves those searches. That is the small part.

The large part is that on the sheets the parity refuses, the search’s answer was wrong rather than slow. The arc structure a lettering search explores records which panel lies over which, and on a sheet whose paper returns the other way up that relation has no consistent direction: one crease arrives as two arcs pointing opposite ways, the search sees an immediate contradiction on some sheets and not on others, and the verdicts stop being symmetric on a symmetric drawing.

An arithmetic check that costs nothing and prevents a wrong answer is not an optimisation, and calling it one is how it ends up being skipped.

Yes and no, and which is dear

The general position in this subject is that a yes is cheap to check and dear to find, and a no is dear both ways. The glued sheets rearrange that.

A yes still needs a search and still comes with a certificate.

A no by parity is cheap to find and cheap to check — cheaper than the yes in both directions.

A no by geometry — the closure condition failing — is cheap to find and cheap to check as well, since it is a comparison of six numbers, and it catches cases the parity misses.

A no by exhaustion is what is left, and on these sheets it is left with very little: a drawing whose parity is fine, whose closure condition holds round every loop, and which still has no lettering.

That last category is not empty, and on sheets with interior vertices it is the whole of the problem. On a band it is empty, because a band has one loop and no vertices, and the closure condition round that loop is the whole question.

The pattern this belongs to

The collection has a small collection of cheap refusals and they have a shape in common.

Maekawa’s condition refuses a vertex in one subtraction: the letters differ by two or the vertex does not fold. Developability refuses in one addition. A pattern with an odd number of creases at a vertex refuses in a glance.

Each of them is a counting invariant: a quantity preserved by any folded state, computed from the drawing, taking finitely many values. Where the drawing’s value is not one a folded state could have, the refusal is immediate.

And each of them shares the same limitation, which is that a counting invariant discards the continuous data. Every counting condition in this subject has a family of counter-examples built out of what it forgot, and knowing which is which is most of what it means to use them properly.

Four conditions with nowhere to holdThe four vertex conditions this subject checks, evaluated on a band of paper. Each reads the creases meeting at one interior point, and a band has no interior point where creases meet, so all four hold on every band at every crease count — including the 6 of 12 measured here that have no flat folded state at all.four conditions with nowhere to holddevelopabilityholds, at 0 verticesKawasakiholds, at 0 verticesMaekawaholds, at 0 verticesbig-little-bigholds, at 0 vertices6 of 12 of these bands have no flat folded stateand only the panel colouring can see it
Fig. 5 The subject’s four vertex conditions, evaluated on the bands measured here. All four hold on every one of them at nought vertices, including the six that refuse — so the cheap refusals available at a vertex are of no use whatever on a sheet with none.

The arithmetic, spelled out

For completeness, since one addition is the whole claim and it deserves to be written down.

Give every step of a closed path a sign: minus one where the step exchanges the two faces of the paper, plus one where it does not. Crossing a crease always exchanges them. Crossing an ordinary point of the paper never does. Crossing a seam does exactly when the seam was glued with a flip.

Multiply the signs round the path. A flat folded state exists only if the product is plus one.

For a loop of paper with kk radial creases, that is (−1)k×(+1)(-1)^k \times (+1), which asks for kk even.

For a Möbius band with kk creases across it, it is (−1)k×(−1)(-1)^k \times (-1), which asks for kk odd.

For a rectangle of tessellation glued into a torus, there are two loops and two products, and both have to come out at plus one.

In each case the computation is: count the creases, take the parity, multiply by the seam’s sign. Three operations, and the answer is a proof.

A caution about cheap answers

The essay has been arguing for the parity and there is a way of over-reading it that leads somewhere bad.

A cheap test that refuses half the cases is very tempting to trust. It is right whenever it fires, it costs nothing, and after a while it starts to feel like the answer rather than like a first pass. That is precisely the mistake the square-creased Möbius band exists to correct: every one of them has the right parity, and none of them folds.

The failure mode is specific and it is not stupidity. A cheap test that is necessary gets used as though it were sufficient, because the cases where it fires accumulate and the cases where it passes and the object still fails are rarer and quieter. Nobody decides to treat a necessary condition as sufficient; it happens by the test being right often enough.

The defence is to keep the next test in the sequence and to run it. On these sheets the next test — comparing the composed reflections against the gluing map — is six numbers and refuses everything the parity misses, so there is no excuse.

On sheets with vertices there is no such next test, the sequence ends in a search, and the search is where the hardness lives. That is a different situation and it is the general one.

Where the sequence ends

Four tests, each complete for what it decides, none of them sufficient except the last — and the last is a search.

That is the honest shape of this subject’s decision problem and it does not improve. Flat-foldability is hard, and a stack of cheap necessary conditions does not make it easier; it makes the easy cases fast and leaves the hard ones exactly where they were.

What the cheap conditions do change is which cases are hard. Before the parity, every glued sheet was a search; after it, half of them are an addition and the other half are still a search. The boundary between the two moved and the difficulty did not.

That is worth saying because it is the standard result of finding a new necessary condition, and it is easy to mistake for progress on the hard part. It is progress on the easy part, which is worth having and is not the same thing.

Where the cheap proof is worth having anyway

Given how much it gives up, it is fair to ask why the parity is worth computing at all.

Because it refuses half the cases, correctly, for nothing. A search asked to establish a no on a sheet where the parity already says no is doing work whose answer is known, and on the objects here that work can be thousands of nodes.

More importantly, a search asked that question on such a sheet is asking the wrong question. A lettering search looks for an assignment of mountains and valleys that is consistent; on a sheet whose paper comes back the other way up there is no consistent assignment of anything, and the search explores a structure that does not represent the object. That produced a genuine wrong answer — a symmetric drawing reported as folding one way and not the other.

So the parity is not an optimisation. It is a precondition, and running the search without it is not slower but incorrect.

Two ways to ask whether a gluing turns the paper overFor each glued sheet, the number of creases a loop that cannot be shrunk crosses on the flat drawing, and beside it what the folded motions say about the same gluing. The first is a count and the second is a comparison of six numbers; they share no code and they agree everywhere.creases crossed by a loop, and what the fold says about itthe grid ×1, across11 creases, always odd · turns the paper overthe grid ×1, along11 creases, always odd · turns the paper overthe grid ×2, across22 creases, always even · keeps the sidethe grid ×2, along22 creases, always even · keeps the sidethe Miura ×1, across11 creases, always odd · turns the paper overthe Miura ×1, along42–4 creases, always even · keeps the sidethe Miura ×2, across22 creases, always even · keeps the sidethe Miura ×2, along44–8 creases, always even · keeps the sidethe Yoshimura ×1, across22 creases, always even · keeps the sidethe Yoshimura ×1, along44 creases, always even · keeps the sidethe Yoshimura ×2, across44 creases, always even · keeps the sidethe Yoshimura ×2, along88 creases, always even · keeps the sidean odd count and a folded state that comes back the other way up are the same fact
Fig. 6 The two computations that decide the parity on a glued cell, on the drawings measured here. Both are cheap; the point of having two is that a wrong sign in either would show as a disagreement rather than as a confident wrong answer.

The order to ask in

The practical arrangement that comes out of all this is a sequence of tests, cheapest first, each of them complete for what it decides.

The sheet’s shape. How many loops that cannot be shrunk, and what each of them crosses. One face walk and some arithmetic. Refuses on parity.

The vertex conditions. Four checks per interior vertex, all local. Refuses on developability, Kawasaki, Maekawa or big-little-big.

The closure condition round each loop. Six numbers per loop, and it returns a distance. Refuses on geometry the counting misses.

The search over letterings. Everything else, and the only one that can produce a witness.

Each stage is a proof of what it decides, and each is dearer than the one before by more than a constant. The last is the only one that says yes.

What the reflections compose to on a Möbius bandThe 3 creases of the band, each a reflection, composed in order — and beside it the gluing map the composition has to equal. On a disc that map is the identity and the condition reads "the composition is the identity", which is the only form of it anybody states. Here the two differ by 4.00e+0 of the band's own width.the composition, and what it has to equal3 reflections, in order[ -1.000 0 ][ 0 1.000 ]+ ( 2.000, 0 )=?the gluing map of a Möbius band[ 1.000 0 ][ 0 -1.000 ]+ ( -2.000, 1.000 )they differ by 4.000 of a width, so it does notand both turn the paper the same way, so the parity is righton a disc the right-hand side is the identity, which is why nobody writes it down
Fig. 7 The third stage on a band the first stage passed: three creases square across a Möbius band, odd, coloured, and refused by comparing two matrices. No search is needed for this either, and no counting argument reaches it.

One more asymmetry

There is a last difference between the two proofs that is easy to miss and matters for how the collection is built.

The parity is computed from the drawing. It needs the creases and the sheet’s shape and nothing else — no folding, no motions, no coordinates beyond enough to count crossings.

The search is computed from the vertex tables, which are built from angles. So the search needs the geometry to be right, and a drawing whose coordinates are slightly wrong produces tables that are slightly wrong and a verdict that is confidently incorrect.

That makes the parity useful as a check on the drawing as well as on the sheet. A pattern whose parity says no and whose search says yes is a pattern where something has gone wrong upstream, and the collection has had exactly that — which is how the whole business of separating orientation from rotation was found.

Two computations that share no code and answer the same question are the collection’s standard defence, and this is one more instance of it: the cheap proof earns part of its keep by disagreeing with the expensive one when the expensive one is broken.

What the search is still for

None of this diminishes the search, and it is worth saying what remains its job.

The search is the only thing here that can produce a yes. Every cheap test above is a refusal; none of them constructs a lettering, and a sheet that passes all of them has not been shown to fold.

The search is also the only thing that handles vertices. Every glued sheet in this essay has none — the creases run from one edge to the other and meet nothing — and that is what makes the cheap tests complete for them. A tessellation glued into a torus has hundreds of vertices, and its cheap tests refuse a fraction of the cases while the rest go to the search exactly as before.

And the search is what the collection’s whole apparatus of variable orders, propagation and pruning exists for. Making a search faster is a large subject; making one unnecessary is a lucky accident that happens when an invariant is noticed. Both are worth having and only one of them can be worked on.

The sentence worth keeping

A cheap proof and an expensive one can establish the same fact, and which one is available is a question about what somebody has noticed rather than about the object.

Every counting invariant in this subject was once a fact somebody had to observe, and the objects it refuses were being refused by exhaustion before that. The parity of a glued band is the most recent one, it costs an addition, and the sheets it refuses were being searched.

Where this goes next

every condition holds here6 creases4 creasesevery condition holds at the vertex on the paper — and one crimp later the smallest sector has the same letter on both sidesthe four conditions all hold · a stacking does not exist A short reason to say no When a folding question comes back yes it brings an object anybody can check. When it comes back no it usually brings nothing but the assurance that a search looked everywhere. At one vertex that is false: a refusal comes with a witness one or two steps long, out of a search space of a hundred and twelve, and the witness is a vertex the crease pattern does not contain. 0°30°60°90°0.250.400.550.700.85how much of the room between two vertices the twists takeno paper leftno assignment existstwist angleboth curves are measured rather than plotted from a formula A no costs more than a yes When a folding question comes back yes, it comes back with an object: a labelling, a stacking, a folded state that anybody can check in one pass. When it comes back no, it comes back with nothing but the assurance that a search looked everywhere — and that assurance is the first thing to break. 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 The cost of asking the wrong sheet A test written for a sheet with an edge, run on a sheet without one, does not fail. It exhausts — proving, at three, thirty-five and three thousand four hundred and fifty-five nodes, that no lettering exists — and the letterings it proved impossible fold, on the collection's own machinery, at every size they were tried at.

Named alongside this one

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

The objects this essay names

Each one links to every other essay that touches it.

CertificateCountingThe decision problemExhaustive searchGluingNecessary conditionParitySearch cost