Origami & Folding
what one sheet can do
Theme

Flat is rare

Almost no crease pattern folds flat. The ones that do are a vanishingly small, highly structured set, and that scarcity is what makes them worth studying.
VMMM60°90°120°90°Kawasaki60° + 120° = 180°90° + 90° = 180°both 180° — satisfiedMaekawa3 mountains, 1 valleysdifference 2exactly 2 — satisfiedangles sum to 360°which is what a flat sheet requiresmountainvalley Flat-folding

Two conditions at a point

Whether a single vertex folds flat is decided completely by two tests — one on the angles, one on the assignment. They are independent, they are easy to check, and together they settle the case entirely.

 MVMM40°foldsopposite across the small sectorMMVM40°does not foldthe same on both sidesboth satisfy Kawasaki and Maekawa — the angles and the counts are identical Flat-folding

The smallest sector decides

Two assignments can satisfy both flat-folding theorems and only one of them folds. What separates them is a condition about the smallest angle, and it is the first rule in the subject that is not about counting.

 6 interior vertices, every one satisfying both theoremswhat the local tests seeangles at each vertexassignment at each vertexwhat they cannot seewhether layer 3 passes through layer 7whether a flap has room to existwhether the order is consistent everywhereBern and Hayes, 1996: NP-hardso this pattern is checked, not proved Flat-folding

Local is not global

Every vertex can satisfy every condition and the sheet still not fold. Deciding whether a whole crease pattern folds flat is NP-hard, which means no figure will settle it and no algorithm will scale.

 MVMV123455 segments, 4 creases12345the stack, solvedassignmentsMVMVvalid stacks1decided byexhaustive searchover the orderingsthe folded positions come from the crease spacing; the assignment only decides which way each turn wraps Flat-folding

A strip is decidable

Take the same problem down one dimension and it stops being hard. The reason is not that strips are small — it is that overlaps on a line form a chain, and chains cannot contain the cycles that make the two-dimensional question intractable.

 the cut line3 straight edgesthe pattern3 skeleton arcs3 perpendiculars1 interior vertexassignments that fold30 of 646 creases in allarcs one way, perpendicularsthe other: fails Maekawaequidistance off by 1.9e-16mountainvalleyevery node sits the same distance from each edge that formed it,which is why one fold can carry several edges onto the line at once Flat-folding

One straight cut

Any drawing made of straight lines can be folded so that the whole drawing lands on a single line, and one cut releases it. The construction is a shrinking process, and it explains itself the moment the shrinking is drawn.

 2 discs53.9%r = 0.29293 discs61.0%r = 0.25434 discs78.5%r = 0.25005 discs67.3%r = 0.20716 discs66.3%r = 0.18767 discs66.9%r = 0.17448 discs72.8%r = 0.17029 discs78.5%r = 0.1667hexagonal density 90.69%every bar is the best a seeded search found, not a proved optimum —which is the honest state of the problem for all but the first few values of n Designing a base

How much paper is wasted

The efficiency of a design is the fraction of the sheet its flaps can claim, and for almost every number of flaps nobody knows the best possible value. The bars in these figures are the best a search could find, which is not the same thing.

 degree-4 vertex4 of 1625.0% · 4 creasespreliminary base112 of 25643.8% · 8 creasesmiura 2×28 of 1650.0% · 4 creasesmiura 3×232 of 12825.0% · 7 creasesmiura 3×3256 of 4,0966.3% · 12 creasesevery count enumerated, none estimatedthe share falls as the pattern grows, and the count still rises Flat-folding

How many assignments fold

The local conditions throw away most of the ways a pattern could be creased. They throw away a smaller and smaller fraction as the pattern grows, and what survives grows faster than what is discarded — which is why a strong filter is not a decision procedure.

 state 0state 1V M M V — the same pattern in both2 valid stackings, found by enumerationwhat a junction would addthree wires meeting, with the layer orders forced to disagree —which is a clause, and which is where the reduction gets its powernot drawn and not verified: nothing here decides layer order in two dimensions Flat-folding

The gadgets that make it hard

Flat-foldability is NP-hard, and the proof is a construction rather than an obstruction: a machine for turning any satisfiability problem into a sheet of paper that folds exactly when the problem has an answer.

 1 × 4161 × 5501 × 61442 × 282 × 3602 × 43203 × 31,3684 × 4300,608filled — counted here, by exhaustive search over stacking ordersopen — Lunnon's published count, quoted rather than computed What it costs to know

The oldest open problem

In how many ways can a map be folded? The question needs no notation to state, the answer is a small integer for small maps, and after sixty years there is still no formula — only a list of numbers, each one found by searching every possibility.

 creases at 0.40, 0.50 — assignment MVflat1 layerno sequence of all-layers folds finishes this pattern — the search exhausted 5 states What it costs to know

The fold a machine can make

A theorem that says a folded state exists says nothing about getting there. A machine that folds every layer at once is stopped by a strip with two creases in it — one that folds flat perfectly well, and that a pair of hands folds in about four seconds.

 6 creases, 7 segments, assignment MVMVMVDoes it fold flat?at most 5,040 orderings, and it may stop earlyyesas far as the first legal oneHow many ways?every one of them, because the last is as likely as the first15,040 orderingsWhat are they?the same search, paying a second time for what it keeps1 stackings, written out5,040 orderings, and the answer as wellCan a machine make it?a different search, over sequences of folds rather than over stackingsno1,275 statesthe four are not four difficulties of one problem — they are four problemsthe cost is work rather than time — a clock reading would differ on every build What it costs to know

Four questions about one sheet

Deciding, counting, listing and optimising are not four difficulties of one problem. They are four problems, and folding is the subject that proves it: a ruled map is trivial to decide and unsolved to count, while a general crease pattern is the other way round.

 state 0state 1V M M V — the same pattern in both2 valid stackings, found by enumerationwhat a junction would addthree wires meeting, with the layer orders forced to disagree —which is a clause, and which is where the reduction gets its powernot drawn and not verified: nothing here decides layer order in two dimensions What it costs to know

Hardness is about the worst one

Flat-foldability is NP-hard, and every crease pattern on this site is decided in under a second. Both are true, and holding them together is the difference between using the result and repeating it: hardness is a statement about the worst instance a family contains, and nobody folds the worst one.

 mapflat foldingsand what it took2 × 284 cells, computed here2 × 3606 cells, computed here2 × 43208 cells, computed here3 × 31,3689 cells, computed here2 × 51,9800.6 s3 × 415,55254 s4 × 4300,608not reached herethe 1 × n case is the strip, and it is the only row of this table with a fast methodnobody has a formula for any entry, and nobody has proved there is none What it costs to know

The answer is bigger than the question

A twelve-square strip of stamps is twelve numbers of input and 146,376 objects of output. No algorithm writes that faster than it can be written, so 'efficient' has to be measured against the answer rather than against the question — and in folding that is the normal case.

 2468101222.22.42.62.833.23.4stampsratio to the term beforeodd terms, from aboveeven terms, from belowfilled: computed here, to 9 stamps · hollow: 10 and 11 and 12, computed once and quoted4,536 foldings at 9 stamps What it costs to know

Where the exponent comes from

The number of ways a strip of stamps folds grows exponentially, and the base of the exponential is a number nobody has proved exists. The ratio of one term to the last climbs past three and is still climbing where the computation stops — which is the only structural handle anybody has on the sequence.

 discsfoundproved bestshort by20.292880.292890.00%30.254310.254330.01%40.250000.25000matched50.207050.207110.03%60.187580.187680.05%70.174360.174460.06%80.170220.170540.19%90.166670.16667matchedworst shortfall 0.19% of the radius, at 8 discsthe search never consults the published values, so the comparison measures the searchbeyond nine discs there is nothing to compare against, because nothing has been proved What it costs to know

Getting close instead of getting it right

When the best answer is out of reach the question stops being what it is and becomes how much is lost. For packing discs into a square the loss is measurable: a seeded search in this repository comes within a fifth of a percent of the best radius anybody has proved, and proves nothing.

 degree-4 vertex, 60/90/120/90°4 of 164 creases · 25.0% surviveone degree-6 vertex8 of 646 creases · 12.5% survivethe preliminary base112 of 2568 creases · 43.8% surviveand these are only the local tests — a pattern can pass every vertexand still collide once the layers stack, which is the hard part Who found it, and when

The same vertex, found four times

A degree-four vertex with a three-to-one assignment turns up in a buckled cylinder, in a Miura fold, in a Resch tessellation and in a crumpled sheet. It is not a coincidence and it is not influence: the flat-folding conditions are restrictive enough that a small set of vertices is nearly all there is.

 246810012345units (creases, or joints)log₁₀ statesa chain, 3 states per jointa sheet, two letters per creaseat one vertex, 4 of 16 assignments survive four local conditionsthe sheet's count has a local test that removes 75% of it · the chain's has none Folding nobody designed

Two things called folding

A protein folds and a sheet folds, and the word is the same word by accident. Both have exponentially many states and that is not the difference. The difference is that one of them can be filtered by four conditions checked at a single point, and the other cannot be filtered by anything local at all.

 -3-2.5-2-1.5-1-8-6-4-20tolerance (log₁₀ radians)fraction inside it (log₁₀)1 vertex · slope 1.002 vertices · slope 2.013 vertices · slope 3.0140,000 random vertices, none of them constructed to fold and none of them folding Flat-folding

Almost every pattern fails

Kawasaki's condition is one equation for each interior vertex, and a drawing satisfies an equation with probability zero. Every pattern on this site folds because it was constructed to, and the fraction that would fold by accident can be measured.

 2345678910-0.15-0.1-0.0500.050.10.15discsshortfall of the symmetric search14.6%1.7%0.0%-0.0%5.6%0.5%10.8%10.4%4.7%symmetry: mirror · both searches at 90 restartsneither number is a proved optimum — this compares two searches Designing a base

When symmetry costs

Design software and designers both reach for symmetry, and for a good reason: it makes the search enormously easier. It is a heuristic and not a theorem, and how much it gives away can be measured — including the case where the optimum is symmetric about an axis nobody imposed.

 1.7e-6 at 1e-61e-61e-51e-41e-31e-21e-61e-51e-41e-31e-2how far each vertex of the flat pattern was moved, in panel widthslargest edge-length errorfitted slope0.9999over four decadesat a displacement ofexactly zero the erroris 6.7e-16, which iswhere the arithmeticstops and not wherethe geometry does5 × 4 panels at 50% folded, with one set of displacement directions scaled across the decadesa slope of one is the claim: the failure is first order, so no displacement is small enough to be free Rigid folding

The only pattern that moves

A rigid motion is not a generic property of a folded pattern. Move one vertex of a Miura by a thousandth of a panel and the sheet has no isometric folded position of that kind at all — and the amount by which it fails is first order in the displacement, so no move is small enough to be free.

 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 Tessellations

Fenced at both ends

The twist angle of a tessellation looks like a free dial, and it is fenced twice. Turn too far and the pleats have no paper left. Turn too little and something stranger happens: every angle condition in the subject goes on holding and the pattern loses its mountain-valley assignment entirely.

 folded 8 times, then unfolded33 interior vertices, all of degree 433 of 33 satisfy Kawasakithe folding is the reason, not the drawing45 creases drawn at random485 interior vertices, all of degree 40 of 485 satisfy Kawasakisame count, same sheet, nothing folded Curves and material

The creases a sheet gives itself

A crease pattern drawn at random satisfies the flat-folding condition at essentially none of its vertices. A sheet crumpled at random satisfies it at every single one, on every seed, at every size — and the reason is a tautology that is very easy to miss.

 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 What it costs to know

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.

 0.5°1%1°2%2°3%5°8%10°16%20°33%how far each sector would have to moveshare that would fold40,000 random four-crease verticesthe median vertex is 31.31° per sector from folding, the mean 33.91°none of them folds, and almost none of them nearly does either Flat-folding

A near miss is nearly as rare

Flat-foldability is a coincidence of measure zero, which is usually where the argument stops. Measure how far a random vertex is from folding rather than whether it does, and the answer is thirty-one degrees a sector — so the tolerance real paper has does not buy back anything at all, and a pattern that nearly folds had to start near one that did.

 1 × 4161 × 5501 × 61442 × 282 × 3602 × 43203 × 31,3684 × 4300,608filled — counted here, by exhaustive search over stacking ordersopen — Lunnon's published count, quoted rather than computed What it costs to know

Two directions that will not separate

A map has rows and columns, and a strip of stamps is a map with one row. The obvious hope is that the two-dimensional count is built from the one-dimensional one — fold the rows, then fold the columns. It is not: a two-by-three map folds 60 ways against a product of 12, and the discrepancy grows from a factor of two to a factor of thirty-eight over the counts anybody has.

 102°60°78°120°one smallest sectorthe lemma constrains one pair4 foldable assignmentsof the 16 markings120°60°60°120°two smallest sectors equalthe lemma constrains nothing8 foldable assignmentsof the 16 markings Flat-folding

Where the lemma says nothing

The big-little-big lemma asks for a sector strictly smaller than both its neighbours, and the word doing the work is strictly. At a vertex whose two smallest sectors are equal the lemma has no opinion at all — and those are the vertices origami actually uses. The count of markings the conditions admit doubles, discontinuously, at exactly the angles everybody folds.

 what the vertex conditions settle once one crease is chosenpatternsettled, against what is therepreliminary base1 of 81 vertices still choosingmiura 6×41 of 3815 vertices still choosingwaterbomb 4×41 of 7625 vertices still choosingyoshimura 6×51 of 8422 vertices still choosingsquare twist grid3 of 14464 vertices still choosingtriangular twist grid2 of 236104 vertices still choosingKawasaki was settled by the angles before a letter was written; the letters are what is left, and they are nearly all left Flat-folding

How little the conditions decide

Local is not global is a statement about sufficiency: every vertex can pass and the sheet still fail. There is a sharper complaint available, and it is about strength. Fix one crease of a tessellation and propagate every condition the subject has to a fixed point: three creases out of a hundred and fifty-eight follow, and sixty-six vertices are still holding more than one answer.

 the waterbomb tessellation's odd vertexdegree six, and this site prints nine of them on one sheetevery assignment64passes all four conditions30has a flat folded state1812 labellings satisfy every condition the subject has and have no flat folded state Flat-folding

Crimp it away and ask again

Four conditions decide whether a vertex folds flat, and they decide it exactly at a vertex whose sectors are all different sizes. Everywhere else they over-count: two markings of every tied four-crease vertex, twelve of the degree-six vertex this site prints nine of on one sheet. What decides the case is not a fifth condition but a procedure — fold the smallest sector away and ask the smaller vertex.

 degreevertices visited per letteringcrimps needed48 of 16 fold32630 of 64 fold1038112 of 256 fold41410420 of 1024 fold2065121584 of 4096 fold12376The work grows by a factor of about 6.0 for every two creases added; the necessity grows by one. Flat-folding

A tie is not a decision

The crimp reduction decides a vertex by folding its smallest sector away, and where two sectors tie for smallest it has no forced move and must try each of them. That search is not rare — on the vertex at the centre of the first base anybody folds it happens for fourteen of the sixteen letterings — and it has never once changed the answer.

 populationpassfoldhave a gapbranchcut twice at random51 vertices, 13 kinds9.68.020%0%whole multiples of 45°60 vertices, 1 kinds30.019.3100%69%whole multiples of 30°60 vertices, 13 kinds19.713.177%26%a named vertex, jittered60 vertices, 4 kinds8.08.00%0% What it costs to know

Which vertices are the random ones

Every measurement on this site that begins 'over 373 random degree-four vertices' is a statement about a population nobody declared. There is no canonical way to pick a crease pattern at random, four defensible ways of doing it disagree about the same three questions by factors rather than by margins, and the disagreement reaches a sentence this site has published as though it were general.

 8 letterings fold · 1 piece under any two creasesflip two creases anywhere round the vertex, which is the smallest change Maekawa allowsMMVVVVMMMMVVMVVVMVMVMMMVVMVVVMVMMMVMVVVVMMVVMMMMsectors 43° · 110° · 121° · 57° · 16° · 13°one piece: every folding is reachableevery crease at once: stays inside its own piece Flat-folding

Walking between two foldings

The letterings a vertex folds in are always counted and never navigated. Counting says a generic degree-six vertex has eight of them; navigating says that changing any two creases turns any one into any other, and that changing two neighbouring creases does not — and that the vertices which come apart are the ones with no coincidences in them, which is the opposite of what every other measurement here would suggest.

 sectorsletterings that branchdecided by the choice22.5° 22.5° 157.5° 157.5°4/16022.5° 45° 157.5° 135°0/16022.5° 67.5° 157.5° 112.5°0/16022.5° 90° 157.5° 90°0/16045° 45° 135° 135°4/16045° 67.5° 135° 112.5°0/16045° 90° 135° 90°0/16067.5° 67.5° 112.5° 112.5°4/16067.5° 90° 112.5° 90°0/16090° 90° 90° 90°14/160 Designing a base

The other grid

Box pleating is drawn at forty-five degrees, and the twenty-two-and-a-half-degree grid is usually described as the same thing done finer. It is not a refinement, it is a different alphabet: five kinds of vertex become fifty-six, and the share of letterings whose decision needs a search falls from 60 per cent to 22. A finer grid is a larger vocabulary and a less ambiguous one.

 each row is an exhaustive count over the patterns that construction producedon the edgedeepest piletimes smallercrease densitythe printed patterns8 patterns62%19.415.5×7.9twist tessellations12 patterns52%10.02.7×12.9quadrilateral meshes6 patterns67%8.74.8×5.2fold-and-cut patterns7 patterns86%10.41.2×2.2 What it costs to know

Four ways to draw a pattern

Every sentence here of the form over some crease patterns is a statement about a construction nobody declared, and it is worse than the same problem at a vertex because a pattern has a shape as well as angles. Four ways of producing a pattern that satisfies every condition disagree about how far it shrinks by a factor of twelve, about how much creasing it costs by a factor of six, and about how much of it is edge by a factor of two.

 the four cheap tests are polynomial in the drawing; the fifth is notreading across a row is one pattern put to all fivecrease pairsverticespanelscreasessearch nodesthe square twist6649127,565the Miura fold703152438refusedthe waterbomb sheet2,850255276refusedthe Yoshimura3,655226586refuseda square patch3,486364984refuseda rhombille patch39,621126157282refuseda refused search is a pattern about which the expensive test says nothing at all, at full price What it costs to know

The cost is in the coincidences

How big an instance is, is what a hardness statement is about, and it is the weaker predictor of what deciding one costs. Hold the degree fixed and vary only how many of a vertex's sectors are equal: the work of deciding it rises by a factor of nearly three, against a factor of two for doubling the number of creases. The expensive instances are the ones a designer draws on a grid.

 The preliminary base: 8 symmetries, 112 letteringsthe bar is the share of letterings the symmetry carries to themselvesa quarter turnnone of 112 — this symmetry cannot be foldeda half turnnone of 112 — this symmetry cannot be foldedthree quarters of a turnnone of 112 — this symmetry cannot be foldeda mirror across the sheet12 of 112a mirror up the sheet12 of 112a mirror in one diagonal12 of 112a mirror in the other diagonal12 of 112 Designing a base

The symmetry the letters cannot keep

Every pattern in this subject is drawn symmetric and the symmetry is always quoted of the drawing. A folded object is a drawing and a lettering together, so a symmetry survives only if the letters keep it — and the preliminary base loses every rotation while the square twist, drawn with the same eight, loses the other half.

 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 Flat-folding

The lettering that folds nowhere

The conditions at a vertex admit 256 letterings of the square twist. Eight of them have a folded state. The other 248 satisfy developability, Kawasaki, Maekawa and the big-little-big lemma at every vertex of the pattern and cannot be folded by anyone — and this site printed one of them for years, at true scale, with instructions to fold it first.

 the bar is the average number of distinct folded statesevery printed pattern on this site has exactly one, and none of its swaps is legal2 folds1.1724 of 24 measured · 2 of 71 swaps legal3 folds1.3824 of 24 measured · 2 of 164 swaps legal4 folds2.1619 of 24 measured · 6 of 335 swaps legal5 folds2.336 of 24 measured · 0 of 121 swaps legala refused row is a sheet with too many panels to search, and refusals are counted rather than dropped Curves and material

The crumple keeps its options

Every crease pattern this site prints has exactly one folded state and not one of its thirty-nine available rearrangements is legal. A sheet creased by folding it at random four times has an average of 2.16 folded states, one of them has nine, and six of three hundred and thirty-five rearrangements are legal. The sheet nobody designed is the one with room left in it.

 the bar is the share of the population with a folded stateevery pattern in all four passes every condition at every interior vertexthe printed patterns4 of 80 cannot be placed · 0 cannot be ordered · 4 undecidedtwist tessellations2 of 125 cannot be placed · 2 cannot be ordered · 3 undecidedquadrilateral meshes2 of 60 cannot be placed · 4 cannot be ordered · 0 undecidedfold-and-cut patterns5 of 70 cannot be placed · 0 cannot be ordered · 2 undecidedundecided is a real answer here and is not rounded toward either side What it costs to know

The patterns a checker is tested on

This site keeps four populations of crease patterns and runs its checkers over them, which is what makes a claim about typical instances measurable rather than rhetorical. Asked whether the members actually fold, the populations answer: thirteen of thirty-three do, six place and cannot be ordered, five cannot be placed at all, and nine are past what the search will finish.

 the vertex nobody listedthe two lines meet at 22.9°sectors 157.1° 22.9° 157.1° 22.9°alternating sums 314.2° and 45.8°Kawasaki fails — it holds only at a right angle2 mountain and 2 valleyMaekawa fails — a crossing can only be 4–0, 2–2 or 0–4mountainvalleyraw edge Flat-folding

Two creases that cross

A crossing is four creases at a point, so the four conditions of the subject apply to it — and three of them can be satisfied. It is developable at every angle, it satisfies the big-little-big lemma whenever its two lines carry different letters, and it satisfies Kawasaki's condition when the lines meet squarely. Maekawa's refuses it always, at every angle and under every lettering, because a crossing's four spokes belong to two creases and can only be four and none, two and two, or none and four.

 the bar is how many of the 33 patterns each refusal is the first to catchtwo creases cross5one sweep over pairs of creasesa vertex condition fails0one pass over the verticesthe panels do not place0one walk over the panelsthe letters force a loop0one pass over the crease listno ordering exists6every ordering of the panels22 of the 33 are refused by none of these and are folded, undecided, or waiting on a search too large to run What it costs to know

The order the refusals come in

This collection can say no to a crease pattern in five ways, and they cost wildly different amounts: a sweep over pairs of creases, a pass over the vertices, a walk over the panels, a pass over the crease list, and an enumeration of every ordering of the panels. Run all five over the thirty-three patterns in the four test populations and the cheapest refuses five, the most expensive refuses six, and the three in between refuse nothing at all.

 the bar is the share of random drawings with at least one crossing in them2 segments23.1%0.23 crossings on average3 segments51.2%0.69 crossings on average4 segments73.5%1.36 crossings on average6 segments95.2%3.48 crossings on average8 segments99.4%6.53 crossings on average12 segments100.0%15.30 crossings on average20 segments100.0%43.76 crossings on averageevery crease pattern in this collection has none, and none of them was drawn at random What it costs to know

Drawn by the same hand

Two straight segments dropped on a square cross about 23% of the time; four of them cross 74% of the time; twelve cross with certainty, about fifteen times over. Every crease pattern in this collection's four test populations has none — not because the checkers were catching them, but because the same rules that drew the patterns were incapable of producing one, and nothing looked until a construction finally did.

 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 Flat-folding

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.

 the bar is the share of draws that agree with themselvesthe rows are ordered by panel count, which is the only thing changing along them49 panels26 of 200square · 84 creases · 26 of 20062 panels5 of 200elongated · 106 creases · 5 of 20077 panels2 of 200hexagonal · 142 creases · 2 of 20083 panels0 of 200triangular · 142 creases · 0 of 200157 panels0 of 200rhombille · 282 creases · 0 of 200a zero is a zero of the draws taken and not a proof that no consistent lettering exists Tessellations

Letters that agree get rarer

Two hundred letterings drawn independently from a square twist tessellation patch, and twenty-six of them have letters that do not contradict themselves. On the next patch up it is five, then two, then none, then none. What the share falls with is not the size of the patch and not the angle of its twist: it is the number of independent closed chains its panels form, which is Euler's relation on the drawing and is fixed before a single letter is chosen.

 every curve is one construction grown, and the axis is the same for all threethe Miura, grownthe Yoshimura, growntwist patches00.2500.5000.7501255075100125independent closed chains of panelsshare of letterings that agree with themselvesthe horizontal axis is read off the drawing before any letter is chosen, and it is the number of interior vertices Tessellations

A corrugation agrees with itself

A Miura fold of forty-eight panels and a twist tessellation patch of forty-nine have almost exactly the same number of independent closed chains for their letters to contradict themselves round — thirty-five against thirty-six. Sixty-four per cent of the Miura's drawn letterings are consistent and thirteen per cent of the patch's. A Yoshimura at thirty-three chains manages ninety-three. The room to fail sets the scale; the construction decides where in it a pattern lands.

 the bar is how many of the 38 patterns each refusal is the first to catchtwo creases cross5one sweep over pairs of creasesa vertex condition fails0one pass over the verticesthe panels do not place0one walk over the panelsthe letters force a loop1one pass over the crease listno ordering exists6every ordering of the panels26 of the 38 are refused by none of these and are folded, undecided, or waiting on a search too large to run What it costs to know

The refusal that reads the list once

There are five ways of saying no to a crease pattern here, and their costs are two hundred and eighty-two, a hundred and twenty-six, a hundred and fifty-seven, thirty-nine thousand six hundred and twenty-one — and a search that is refused outright. On the largest patch the four cheap tests together do less work than one of them looks like it should, and the fifth cannot be started. A refusal that reads the crease list once is the only kind that scales.

 a lettering of the patch that agrees with itselffound by testing the arcs while the letters were chosen, not after561 nodes · 246 backtracks · verified against a rebuilt folded sheet157 panels · 282 creasesits own lettering sends its panels round in a circle0 of 200 random letterings agree with themselvesthis one was found in 561 nodes and 246 backtracksit differs from the drawn lettering on 155 of 282 creasesthe drawing is the pattern; nothing here is a picture of the folded object Flat-folding

The lettering nobody could draw

Two hundred letterings drawn at random from the rhombille tessellation patch, and not one of them agrees with itself. Two thousand, and still not one. The patch was left as an open question — and it has an answer, found in five hundred and sixty-one steps by a search that tests the arcs while it is choosing the letters instead of after it has chosen them all.

 the bar is how many times the search took a letter backand every one of those was the arcs closing a loop, never a vertex running out of labellingsthe square patch126 nodes · 1 refused by the arcs · 0 by the vertex conditionsthe elongated patch335 nodes · 3 refused by the arcs · 0 by the vertex conditionsthe hexagonal patch241 nodes · 2 refused by the arcs · 0 by the vertex conditionsthe triangular patch747 nodes · 7 refused by the arcs · 0 by the vertex conditionsthe rhombille patch246561 nodes · 246 refused by the arcs · 0 by the vertex conditionsthe vertex conditions are propagated rather than tested, so they narrow the choice instead of refusing it Flat-folding

Which condition does the refusing

A search for a lettering carries five conditions: developability, Kawasaki, Maekawa, the big-little-big lemma, and the demand that the arcs the letters force have no circle in them. Run it on five tessellation patches and count what makes it take a letter back. The four everybody checks refuse nothing at all. Every single backtrack is the fifth.

 the bar is how many creases the found lettering writes differentlymeasured against the lettering the pattern's own construction producedthe square patch4545 of 84 creases · 31 of them buriedthe elongated patch6666 of 106 creases · 42 of them buriedthe hexagonal patch6767 of 142 creases · 45 of them buriedthe triangular patch8787 of 142 creases · 65 of them buriedthe rhombille patch155155 of 282 creases · 117 of them burieda buried crease has an interior vertex at each end, and no legal move ever changes one Flat-folding

One solution of a search nobody ran

A crease pattern arrives with its letters already on it, and they look like part of the drawing. They are not. Every construction here ends in a propagation, a propagation ends wherever its first guess took it, and the lettering that comes out differs from the one a search finds on between a half and three-fifths of the creases — on patterns whose own letters are perfectly good.

 the bar is how many rules the two tests agree aboutone reads three bits of the rule; the other folds the sheet and walks the arcsthe Miura fold64 of 6438 rules predicted to close a loop · 0 disagreementsthe tapered leaf64 of 6438 rules predicted to close a loop · 0 disagreementsthe closed form says a loop is available exactly where the columns fail to change letter and the row disagrees with them Tessellations

The loop is in the rule

Of the forty-eight repeating rules that do not fold a grid corrugation, thirty-eight send four panels round in a circle and ten merely fail the count. Which is which can be read off three of the rule's six bits, without building the pattern, folding it or walking a single arrow — and the closed form agrees with the arrows on all sixty-four rules of both grid families.

 the bar is the middle run of a hundred and twentysame pattern, same code — only the order the letters are tried in differsthe square patch2725 at best · 27 at the middle · 36 at worstthe elongated patch3432 at best · 34 at the middle · 39 at worstthe hexagonal patch4339 at best · 43 at the middle · 51 at worstthe triangular patch4539 at best · 45 at the middle · 53 at worstthe rhombille patch16684 at best · 166 at the middle · 48 of 120 unfinished at 20000an unfinished run is left out of the middle rather than counted as its budget Tessellations

Four easy patches and one that is not

Run the same search a hundred and twenty times on each of five tessellation patches, changing nothing but the order the letters are tried in. Four of them answer in between twenty-five and fifty-three steps every single time. The fifth answers in eighty-four steps at best, a hundred and sixty-six in the middle, and does not answer at all in forty-eight runs of the hundred and twenty.

 the bar is what the whole job costs if every attempt is stopped thereon the rhombille patch, read off 120 measured runsstop at 10051219% of runs finish by thenstop at 20053033% of runs finish by thenstop at 500105435% of runs finish by thenstop at 1000162442% of runs finish by thenstop at 2000263847% of runs finish by thenstop at 5000569749% of runs finish by thenstop at 100001060450% of runs finish by thenstop at 200001629160% of runs finish by thena run that never finished counts as above every cutoff, so the tail is read conservatively What it costs to know

Stopping is cheaper than finishing

A search whose cost varies by a factor of two hundred with nothing but the order of its guesses should not be waited out. Give up after a hundred steps, reseed and start again, and the whole job costs five hundred and twelve steps in expectation; run each attempt to twenty thousand and it costs sixteen thousand two hundred and ninety-one. Patience is thirty-two times more expensive than impatience.

 the bar is how many patterns the population holdseach one sampled forty times and then searched, to see whether the two methods ever disagreethe printed patterns80 never lettered by 40 draws · all 8 settled by search · worst 60 nodestwist tessellations70 never lettered by 40 draws · all 7 settled by search · worst 19 nodesquadrilateral meshes60 never lettered by 40 draws · all 6 settled by search · worst 6 nodesfold-and-cut patterns70 never lettered by 40 draws · all 7 settled by search · worst 14 nodesthey never do here — the patterns that separate them are not in any of these four What it costs to know

Four populations with nothing to separate

This collection keeps four standing populations of crease patterns to test its machinery against. Twenty-eight patterns, sampled forty times each for a lettering that agrees with itself and then searched for one — and on every single member the two methods return the same verdict in the same breath. The patterns that separate them are in none of the four, and the reason they are not is what the populations are for.

 the bar is the second-smallest sector at a typical vertexthe triangular patch at seven turns, with the same panels and the same creases at all of themturn 0.261.92°smallest sector 60.00° · next 61.92° · no lettering exists, proved by exhaustionturn 0.2160.71°smallest sector 60.00° · next 60.71° · no lettering exists, proved by exhaustionturn 0.215560.06°smallest sector 60.00° · next 60.06° · no lettering exists, proved by exhaustionturn 0.21660.00°smallest sector 60.00° · next 60.00° · a lettering existsturn 0.2260.00°smallest sector 59.52° · next 60.00° · a lettering existsturn 0.2560.00°smallest sector 56.10° · next 60.00° · a lettering existsturn 0.3560.00°smallest sector 46.15° · next 60.00° · a lettering existsthe verdict changes exactly where that sector passes sixty degrees and stops being the second smallest Flat-folding

Where a sector crosses sixty

Turn the twist polygons of a tessellation patch a hundredth of a radian further and the pattern goes from having no mountain-valley labelling at all to having one immediately. Nothing about its graph changes across the transition — the same eighty-three panels, the same hundred and forty-two creases, the same four labellings at every one of its sixty vertices. What changes is which sector at a vertex is the smallest one.

 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 Rigid folding

Refused at one lettering

Four of six quadrilateral meshes here have no arrangement of their nine panels — established by searching every ordering, at the labelling each mesh arrived with. Enumerate every labelling instead and two of the four fold perfectly well at a different one. What was reported as a fact about four meshes is a fact about two meshes and two labellings.

 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 Flat-folding

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.

 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 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.

 heavier means the crease lies on more independent circuits157 panels, 282 arcs, circuit rank 126; circuits run from 4 to 26 arcs What it costs to know

Which choice the cost lives in

A backtracking search takes two decisions at every step — which thing to decide, and what to decide about it. The literature is almost entirely about the first. On these crease patterns the whole of the cost was in the second, and the structural improvement everybody reaches for first makes matters worse on fifty-two patterns out of eighty-seven.

 each cell is one patch, searched to a verdictgreen: a lettering exists · magenta: none exists, by exhaustion0.150.250.350.50.70.91.11.3turn angle, in radianssquare2626262626262626elongated1515323231313232hexagonal1515394545464545triangular1515393939373737the number in a cell is the nodes the search visited; 6 of 32 patches have no lettering at all What it costs to know

The order that proves nothing exists

Twelve crease patterns with no consistent lettering at all. Proving it takes fifteen steps under one rule and half a million under another — and on three of the twelve the two rules swap places, so neither is the good one. The cost of a negative is two to the power of how many free choices sit above the contradiction.

 the bar is how many DIFFERENT letterings 20 runs returneda coin at every choice1414 of 20 runs found onea constant, with the coin only on the creases no vertex constrains120 of 20 runs found onea constant at every choice120 of 20 runs found oneon the rhombille patch, 157 panels and 282 creases Flat-folding

One witness or forty

Taking the randomness out of a search made it three orders of magnitude cheaper in the worst case and cost it thirty-nine of its forty answers. The compromise everybody reaches for — randomise only the choices that cannot matter — recovers four of the forty on two patches and none on the other three, because the diversity was never where it looked.

 each cell is one patch, searched to a verdictgreen: a lettering exists · magenta: none exists, by exhaustion0.150.250.350.50.70.91.11.3turn angle, in radianssquare2626262626262626elongated1515323231313232hexagonal1515394545464545triangular1515393939373737the number in a cell is the nodes the search visited; 6 of 32 patches have no lettering at all Flat-folding

A region with no lettering

One turn angle at which a tessellation patch has no consistent lettering was found by sweeping a dial. Sweeping two dials finds nine patches with none, across three tilings, filling a corner of the parameter space — and never touching the square tiling, whose sectors have no sixty degrees to cross.

 each cell is one patch, searched to a verdictgreen: a lettering exists · magenta: none exists, by exhaustion0.150.250.350.50.70.91.11.3turn angle, in radianssquare2626262626262626elongated1515323231313232hexagonal1515394545464545triangular1515393939373737the number in a cell is the nodes the search visited; 6 of 32 patches have no lettering at all What it costs to know

A population nobody chose

Five crease patterns were measured over and over because somebody had drawn five. Ninety-six drawn from a stated grid of tiling, turn and pleat width say something the five could not: nine of them have no consistent lettering at all, and the phenomenon the collection had spent so long measuring belongs to the one tiling the grid leaves out.

 the curve is stop-and-restart; the rule is a constant letter order1001e+31e+41001e+31e+4563 at a cutoff of 10080 nodes, deterministic, nothing to restartexpected nodes in totalcutoff, in nodes What it costs to know

Restarting what cannot be restarted

Stopping a search early and starting it again with a fresh seed costs five hundred and twelve steps in expectation against sixteen thousand for patience. Every number in that is right. The distribution it is right about was made by the search's own coin, and taking the coin out costs eighty — with nothing left to reseed.

 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 Tessellations

A corrugation never backtracks

As a box-pleating grid goes from two divisions to sixteen, the share of random letterings that agree with themselves falls from a hundred in a hundred to one. The cost of finding one that does stays at exactly one step per panel — four, nine, sixteen, twenty-five, and two hundred and fifty-six — with not a single wrong guess anywhere in the family.

 16 × 16 gridevery crease on a grid line, or at 45°which is why a 64-grid design can be folded at allmountainvalley Designing a base

Ninety-nine in a hundred pass

A designer checks a box-pleated pattern the way every text teaches: vertex by vertex, counting mountains and valleys, watching the smallest sector. At sixteen divisions that check passes a hundred letterings in a hundred, and one of them folds. The check that separates them costs a single sweep over the crease list and is in no recipe anywhere.

 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 Flat-folding

One step per panel is a table size

Four families of crease pattern search at exactly one step per panel — a grid at nine sizes, a leaf, a Miura, six crumples — and it was read as a law about patterns that fill their own sheet. It is a number: the conditions at each of their vertices admit eight labellings. Where the conditions admit four, the cost is half. Where they admit thirty, it moves again, and the same pattern at two proportions demonstrates it with everything else held still.

 the Yoshimura at 6 by 5, at nine proportionsrow height 1.257 nodes30 labellings a vertex · 0.88 nodes a panelrow height 1.557 nodes30 labellings a vertex · 0.88 nodes a panelrow height 1.757 nodes30 labellings a vertex · 0.88 nodes a panelrow height 1.732050857 nodes30 labellings a vertex · 0.88 nodes a panelrow height 1.732050919 nodes8 labellings a vertex · 0.29 nodes a panelrow height 1.7419 nodes8 labellings a vertex · 0.29 nodes a panelrow height 1.819 nodes8 labellings a vertex · 0.29 nodes a panelrow height 219 nodes8 labellings a vertex · 0.29 nodes a panelrow height 2.519 nodes8 labellings a vertex · 0.29 nodes a panelthe equilateral Yoshimura is drawn at √3 = 1.732050808, on the dear side Flat-folding

A knife edge nine decimals wide

Draw the Yoshimura with its rows 1.7320508 half-columns tall and each vertex admits thirty labellings and the pattern costs fifty-seven steps. Draw it at 1.7320509 and each admits eight and it costs nineteen. The number between them is √3, which is the proportion everybody draws — and below it the sectors are unequal and the lemma is still silent, because the small ones sit next to each other.

 sliding the cut across one period of the square tessellation36 vertices at every position, and a different set of creases divided at each0102030cut at the start of a periodone period alongnodes; the axis starts at zero, and the whole spread is inside a factor of 1.32 What it costs to know

Where you cut hardly matters

Slide the same rectangle across one whole period of the same tessellation and every position gives a different patch: different creases divided, different half-panels round the edge, panel counts from forty-nine to sixty-one. The cost of lettering them runs from twenty-five steps to thirty-three. Whether a cut is made changes the answer by three orders of magnitude; where it falls changes it by a third.

 the twist patches: nodes against panels050100150one a panel0 panels157every vertex of this family keeps 4 labellings Tessellations

The most decided vertex here

Sixteen ways to letter four creases; Maekawa allows eight; the big-little-big lemma allows four. A twist polygon's corner is one of the few vertices in this collection where the second cut applies, so it keeps four labellings where a grid, a leaf, a Miura and a crumple all keep eight — and the family the collection long called difficult turns out to be the one whose conditions decide the most.

 the composition, and what it has to equal5 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 Flat-folding

Parity is not enough

A Möbius band needs an odd number of creases round it. Give it three, square across the strip, and it does not fold — nor does five, nor seven, nor any odd number at all. The counting argument is necessary and it is not close to sufficient, and the thing it cannot see is which way the creases point.

 the angles that admit a thirdφ₁ − φ₂ + φ₃ a multiple of a straight angle30°30°60°60°90°90°120°120°150°150°60°, 120°the first crease's angle, against the secondevery other pair of angles folds nothing,at any length and any positions Flat-folding

An alternating sum of angles

Kawasaki's condition says the sectors round a vertex alternate to a straight angle. A glued band has no vertices and obeys a condition of exactly the same shape: the crease angles have to alternate to a multiple of a straight angle. Two different quantities, two different sheets, one arithmetic — and in both cases what is being said is that a product of reflections came back the right way.

 the angles that admit a thirdφ₁ − φ₂ + φ₃ a multiple of a straight angle30°30°60°60°90°90°120°120°150°150°60°, 120°the first crease's angle, against the secondevery other pair of angles folds nothing,at any length and any positions Flat-folding

How rare a band that folds is

Almost every crease pattern fails to fold flat, and the usual way of saying so is a count over discrete choices. A glued band fails for a reason that no count can reach: its crease angles have to satisfy an equation, and a set defined by an equation has no volume in the space it sits in.

 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 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.

 the grid, 2×2 cellsone drawing, four sheetscutoutgluedacrossgluedalonggluedboth waysvertices4444free letters1210108panels9664V − E + F1000the vertex row is the control: identifying edges can neither make nor destroy a vertexand Euler's number is the cheapest check that the gluing did what it says What it costs to know

One population, four sheets

A population of patterns is a way of asking what is typical, and it has always been a population of drawings. Put the same drawings on four different sheets and the verdicts move — not because the drawings changed but because the sheet did, which means a population has two halves and only one of them was ever chosen.

 how much more the folded sheet draws in one way than the otherthe ratio of the two principal factors of the collapse, fitted to the twists' positions before and after foldingas drawnshearedstretchedgeneralthe square grid1.00004.41391.00003.5417the triangular grid1.00001.00001.00001.0000the honeycomb1.00002.81795.38555.0597the rhombille tiling1.00002.81795.38555.0597the elongated triangular tiling1.00004.41391.00003.5417one is a similarity — the folded sheet is the flat one scaled and turned, with no direction preferred Tessellations

The sheet draws in crooked

Every twist tessellation measured here has collapsed by a similarity: the folded sheet is the flat one scaled and turned, the same way in every direction. The patterns that exist on sheared and stretched tilings do not. Ten of the fifteen images fold by a map with two different principal factors, up to five and a third to one — and the prediction that said which ten, made from the weights the pattern writes on its edges, is wrong in both directions.

All themes