Origami & Folding
what one sheet can do
Theme

The machine is not the hand

A theorem says a folded state exists. It does not say anybody or anything can get there, and every device that folds paper — a press brake, a laminator, a diagram followed in order — makes one weak kind of move. What those moves can reach is a smaller subject than what folds flat, and a more useful one.
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.

 evenly spaced — 4 creasesany flat folding16 of 16some-layers16 of 16all-layers16 of 16one-layer2 of 16crimping only6 of 16uneven — 4 creasesany flat folding8 of 16some-layers8 of 16all-layers0 of 16one-layer2 of 16crimping only0 of 16a machine that takes fewer layers is weaker, not more patientthe paper is joined, so what it declines to hold it also cannot move What it costs to know

The patient machine is the weak one

A machine that folds one layer at a time sounds like a machine with more freedom, not less. It has less, and the reason is the most ordinary fact about paper there is: it is joined, so whatever a machine declines to hold it also cannot move.

 4 creases, assignment MVMVthe strip0.200.200.200.200.20MVMV3 availableafter crimp 10.200.200.20MV1 availableafter crimp 20.20nothing left2 crimps, each removing two creases4 creases is an even number, and that is not a coincidencethe merged segment measures outer minus middle plus outer What it costs to know

A machine that can only crimp

Change the atom and the whole picture changes. A machine whose single move folds two adjacent creases at once reaches strips no simple-fold machine reaches, is defeated by strips they handle easily, and cannot fold an odd number of creases at all — for reasons that are pure arithmetic.

 evenly spaced — 4 creasesany flat folding16 of 16some-layers16 of 16all-layers16 of 16one-layer2 of 16crimping only6 of 16one short segment — 4 creasesany flat folding4 of 16some-layers4 of 16all-layers0 of 16one-layer2 of 16crimping only4 of 16uneven — 4 creasesany flat folding8 of 16some-layers8 of 16all-layers0 of 16one-layer2 of 16crimping only0 of 16a machine that takes fewer layers is weaker, not more patientthe paper is joined, so what it declines to hold it also cannot move What it costs to know

The machine that may choose

Three restricted machines lose patterns that fold perfectly well. Give one of them a choice — any block of layers, top or bottom — and the loss vanishes: over a hundred and seventeen spacings, every flat folding of every strip became reachable. Being forced was the whole problem.

 34560%20%40%60%80%100%creases in the stripreachable by simple folds72%30%17%13%the basic symbolsa dashed line — valleya dotted line — mountainan arrow — fold it nowand what they missreverse, squash, sink,petal — every one of thema move no dashed linecan ask forevery assignment of 68 seeded spacings Who found it, and when

What a dashed line can say

Before the Yoshizawa–Randlett symbols a model could not be transmitted, and the subject was not cumulative. The basic notation says exactly one thing — fold this crease, this way, now — which is precisely a simple fold, and the share of flat foldings that simple folds reach collapses from 71% to 13% as a model grows.

 32 × 32 gridevery crease on a grid line, or at 45°which is why a 64-grid design can be folded at allmountainvalley Who found it, and when

Publishing the pattern instead of the sequence

A diagram sequence is one picture per step and a crease pattern is one picture. When designers began releasing patterns rather than diagrams, the cost of publishing a model fell by two orders of magnitude and the difficulty moved onto the reader — which is what made the complex era possible and what made most of it unfoldable.

 Miura solar array17×Space Flyer Unit, 1995airbag folding25×stored for years, opens in 30 msheart stent6×threaded through an arterystarshade11×26 m disc, 2.5 m launch tubemap fold9×the original problempackeddeployedthe ratio is what is bought; one degree of freedom is what makes it reliable Who found it, and when

From a shell to a solar array

The Miura fold was published in 1970 and flew on a satellite in 1995. The gap is not ignorance — the pattern was known, understood and available the whole time — and the same twenty-five year lag appears between every folding result and the hardware that uses it.

 00.20.40.60.811.21.402468fold angle (radians)exposed spanθ = 0.06θ = 0.75θ = 1.449 panels · one parameter · the span rises at every step, so nothing has to reverse Folding nobody designed

Opening with nothing to pull

A leaf is not opened by a hand, a hinge or a motor. It opens because it keeps growing — which puts a condition on the pattern that no folder ever has to satisfy, because a person can always push.

 geometryfreedomsdrivers neededone degree-four vertexfour assignments, one motion each11Miura, 5 × 412 interior vertices, still one freedom11parallel corrugationno interior vertex to couple1112 vertices, uncoupledwhat a pattern costs when nothing constrains it1212or a sequencerone freedom is one actuator — the count is what makes a passive deployment possible at all Folding nobody designed

No motor in the fold

An insect's wing has muscles at its base and nothing out along its length, so the pattern has to carry the deployment by itself. The condition that makes that possible is a count: one degree of freedom means one number determines every panel, which means one thing has to pull.

 nφ(n)its prime factorscompassone foldtwo at once322422542 · 2622762 · 3842 · 2962 · 31042 · 211102 · 51242 · 213122 · 2 · 31462 · 31582 · 2 · 21682 · 2 · 217162 · 2 · 2 · 21862 · 319182 · 3 · 32082 · 2 · 221122 · 2 · 322102 · 523222 · 112482 · 2 · 2the 11-gon is the first a single fold misses, and two simultaneous folds reach itthe 23-gon is the first that needs more than two, because 22 has an 11 in it Axioms and construction

Two creases at once

The seven axioms describe what one fold can do, and the restriction to one fold is a rule somebody imposed rather than a property of paper. Allow two creases to be made simultaneously and the reachable degree rises — and the hendecagon nobody could fold becomes foldable.

 the creaseno panels at all128.3° of turning4 segments8 panels128.3° of turning8 segments16 panels128.3° of turning16 segments32 panels128.3° of turningone crease, cut into flat pieceseach panel keeps its width across the crease and loses length along it as the count risesa finer approximation is a better picture and the same total kink, spread over more joints Curves and material

A curve has no panels

A rigid folding is a finite list of flat pieces joined along lines. A curved crease has no such list, and refining one does not help: the kink at each joint falls as one over the segment count, and the total of the kinks does not fall at all, because it is a constant of the curve.

 flapsfree search4×4 grid8×8 grid30.25430.2500 −1.7%0.2500 −1.7%40.25000.2500 −0.0%0.2500 −0.0%50.20710.1768 −14.6%0.1768 −14.6%60.18760.1250 −33.4%0.1398 −25.5%the 6-flap case on the finest lattice here is one of 3.25e+8 arrangements, and the bound settles all of themthe free optimum is unknown for most of these counts and the lattice optimum is known for all of thema finer lattice costs less and asks for more creases, which is the trade a designer actually makes Designing a base

What the grid settles

Box pleating is usually defended as a trade: give up efficiency, buy creases that land where they should. There is a second thing it buys and nobody quotes it — on a lattice the best possible packing is a finite question with an answer, while off the lattice nobody knows the best packing of six circles in a square and probably never will.

 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.

 the bare sheet4 references · 4 linesnothing has been foldedafter 1 fold9 references · 12 lineshalves, and nothing elseafter 2 folds565 references · 92 lineshalves, thirds, fifths — and worsea fold is an alignment, and an alignment needs something already on the paper to align565 references after 2 folds, and the count is finite however many folds are allowed Axioms and construction

Cheap where it reaches

Two folds from a bare square put marks at a half, a third, a quarter, a fifth, a sixth, an eighth and a twelfth — and at no seventh, ninth or eleventh at all. A rule that reaches every fraction takes n folds to reach one nth. The systematic route and the short one disagree everywhere, and neither of them knows about the other.

 distinct fold lines this axiom specifies and no other doesaxiomafter 4 pointsafter 9 pointsafter 565 pointsA1 — through two points08121054A2 — one point onto another08142649A3 — one line onto another4564994A4 — perpendicular through a point001661distinct lines in all1292274300the four operations name 38 folds at the first round and draw 12 lines with them Axioms and construction

What each axiom is worth

The list of seven folds is complete, and the proof of that says nothing at all about whether its members are independent or equal. Measured on a bare square, one of the four elementary axioms supplies every fold the others cannot and the other three supply nothing. Two rounds later the ranking has inverted, and the one that carried the first round is the least productive of the four.

 the degree of the equation, and what it is made ofnumberdegreemade ofwhere it comes from½11a fold in half√222^1the diagonal of the squareφ22^1the silver rectangle's cousin∛233^1doubling the cube2 cos(2π/7)33^1the regular heptagon∜242^2a square root of a square root∛2 · √262^1 · 3^1a product of two of them2^(1/5)5not twos and threesa fifth root2 cos(2π/11)5not twos and threesthe regular hendecagonchecked by exhaustion: no number here satisfies a rational equation of lower degree with coefficients up to 6 Axioms and construction

The numbers a fold reaches

Folding solves cubics, which is one fact about one fold. The reason the subject has a theory rather than a bag of tricks is a second fact about all of them: the lengths a folder can mark are closed under addition, subtraction, multiplication, division, square roots and cube roots. Constructions can therefore be built out of constructions — and no tower of them ever arrives at a fifth root.

 how many ways each map foldsa strip of five50of 120a plus120= 5! — every stackinga tee120= 5! — every stackinga two-by-three60of 720a two-by-three, one gone40of 120one corner gone848of 40320the middle gone8016of 40320the full square1368of 362880 What it costs to know

The map that is not a rectangle

Take one square out of a three-by-three map and the number of ways it folds does not go down by an eighth. It goes up — to 848 if the square came from a corner, and to 8,016 if it came from the middle. Two maps of eight squares in the same box, differing by nearly a factor of ten, and no function of the box tells them apart.

 the same count, with more than one fold made at a timefreedomsoperationsalignments at onceone fold272two at once4224three at once6506four at once8958five at once1016110the second column is what the algebra gains; the third is what a pair of hands has to hold Axioms and construction

Seven, and then twenty-two

The seven axioms are not seven useful folds somebody collected; they are the number of ways to spend a fold line's two degrees of freedom, and the count can be derived. Run the same derivation for two folds made at once and it gives twenty-two, for three fifty, for five a hundred and sixty-one — while the number of coincidences a pair of hands has to achieve in the same instant goes two, four, six, ten.

 4681012141600.10.20.30.40.50.60.7parts the strip is divided intohow far the crease lands out, mmthe exact ladderFujimotothey cross at 4 Axioms and construction

Exact is not accurate

There are two ways of dividing a strip into equal parts: a ladder that lands on the fraction as a rational number, and Fujimoto's method, which never arrives. Read as mathematics that settles it. Read as instructions for somebody with a sheet of paper it settles nothing, and past four parts the method that never arrives is the one whose crease lands nearer the mark.

 the height is the worst amplification anywhere on the sheetone line per crease; the horizontal axis is the driven crease's own fold angle3.010.32.5fold angle of the driven creasea mesh with no two vertices alike6 of 6 creases are worst near the flat sheet0 steps refused as branch changes Rigid folding

The hardest instant

Driving one crease of a quadrilateral mesh settles every other one, and an error in the driven crease arrives elsewhere multiplied. That multiplier was measured once, at one fold angle. Followed along the whole motion it is worst at the flat sheet on twenty of twenty-four creases — and on the Miura the measurement has to refuse to answer.

 the pale bar is every folded state; the dark one is the states the machine reachescounted over every marking of the strip that folds at all3 equal stamps12 of 12 reached4 equal stamps32 of 32 reached5 equal stamps100 of 100 reached6 equal stamps288 of 288 reachedcreases at .13 .31 .62 .780 of 24 reached — 24 missedcreases at .08 .24 .28 .35 .720 of 48 reached — 48 missed What it costs to know

Where the machine catches up

The weakest machine in the subject folds every layer at once and is stopped by a strip with two creases in it. On a strip of equal stamps it is stopped by almost nothing: every one of the 288 folded states a six-stamp strip has is reachable by a sequence of all-layers folds, and on every unevenly creased strip tried it reaches none of them. At seven stamps the completeness ends, and finding out where it ended is what checking it past six was for.

 the bar is the letterings with a folded statethe row is how many times the letter changes going round the central polygonthe ring reads as one letter032 pass every vertex · 28 have no order2 changes round the ring8192 pass every vertex · 184 have no order4 changes round the ring032 pass every vertex · 32 have no ordera twist looks like a twist when the ring reads as one letter, which is why this was never checked Who found it, and when

Taught with a wrong reason

Four mountains and four valleys is what the preliminary base's symmetry suggests and Maekawa forbids it; a twist looks like a twist when its central ring reads as one letter, and no such lettering folds; a tessellation is verified because its unit is, and a forty-nine-panel patch of one had no folded state at all. In each case the conclusion taught is right and the reason offered for it is not, and the site that repeats them is this one.

 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 how many letterings pass every condition at every vertexand the note is how many of those close a loop in the arcs2 by 122 panels · 2 letterings pass every vertex · 0 close a loop3 by 143 panels · 4 letterings pass every vertex · 0 close a loop4 by 184 panels · 8 letterings pass every vertex · 0 close a loop5 by 1165 panels · 16 letterings pass every vertex · 0 close a loop2 by 284 panels · 8 letterings pass every vertex · 0 close a loop3 by 2326 panels · 32 letterings pass every vertex · 0 close a loop4 by 21288 panels · 128 letterings pass every vertex · 0 close a loop3 by 32569 panels · 256 letterings pass every vertex · 4 close a loopa map's difficulty is not here — it is in the rules about which panels may lie between which What it costs to know

The test that never fires on a map

The cheapest refusal of a folded state reads a crease list once and reports that no arrangement of the layers exists. Enumerate every labelling of every map from two panels to nine and it fires on four of the four hundred and fifty-four — all four on the largest map, none at all below it. On the oldest open problem in the subject, the cheap test has essentially nothing to say.

 the bar is how many nodes the search visitedone sheet crumpled deeper and deeper, its letters rechosen each time4 folds1716 panels · 34 of 40 random letterings agree · 1 backtracks5 folds1918 panels · 34 of 40 random letterings agree · 1 backtracks6 folds3435 panels · 15 of 40 random letterings agree · 0 backtracks7 folds3839 panels · 19 of 40 random letterings agree · 0 backtracks8 folds7271 panels · 11 of 40 random letterings agree · 2 backtracksthe share that agrees falls by more than half along this ladder; the search's cost tracks the panels and nothing else Curves and material

Rare is not hard

Crumple a sheet deeper and the share of its labellings that agree with themselves falls from thirty-four in forty to eleven. The number of steps a search needs to find one of them does not move at all: it stays at about one per panel, with no backtracking, the whole way down. How often an answer turns up at random and how much work it takes to find one are different quantities, and a crumpled sheet is where they come apart.

 the bar is the largest gap between anywhere on the sheet and a referencea third fold specifies more folds than can be listed, so a sample of them is taken insteadnone of them0.089565 references, from two folds50 of them0.0763,498 references · 0.02% of the round100 of them0.0508,056 references · 0.04% of the round200 of them0.04723,480 references · 0.07% of the round400 of them0.02274,694 references · 0.15% of the round800 of them0.014270,882 references · 0.29% of the roundevery row is a lower bound on what the whole round would buy, because leaving folds out can only make the gap larger Axioms and construction

The third fold cannot be listed

Two folds from a bare square reach five hundred and sixty-five reference points. The third round specifies three hundred and seventy-eight thousand folds, of which two hundred and seventy-four thousand are distinct — and the crossings of those with each other run to the tens of billions. The closure stops being computable at exactly the depth a folder starts working at, and what can be said instead is a bound rather than a list.

 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 Who found it, and when

The tail was named somewhere else

The search for a mountain-valley labelling of a tessellation patch costs eighty-four steps at best and does not finish at all two runs in five, and the cure is to stop and start again rather than to wait. None of that was discovered here. The distribution was described in the study of satisfiability solvers in the nineteen-nineties, the restart arithmetic is older still, and what a crease pattern contributes is one more instance.

 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.

 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 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 measured for so long 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 up00202040406060one node per panelnodes visitedpanels3 folds to 8 folds, and not one backtrack anywhere in the family Curves and material

A crumple has no tail

The least structured crease pattern this collection can produce is a sheet folded at random and flattened. Its consistent letterings get rarer as it deepens — thirty-four of forty down to eleven — and finding one costs one step per panel from beginning to end, with no wrong guess anywhere. Disorder and difficulty turn out to be unrelated quantities.

 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

A search with nothing to reorder

One search on a crease pattern costs eighty steps or fifteen thousand depending on the order it takes its decisions in. The other search on the same crease pattern costs 1,188,571 steps whatever order it is given — twelve permutations of the panels, twelve identical counts. The difference between them is one line of code that neither has and one has.

 12% folded42% folded72% folded95% foldedno face bends anywhere in the motion — which is what makes it a mechanism rather than a fold Rigid folding

The motion has no letters to choose

A flat-folding search picks a letter for every crease and can pick badly. A rigid folding does not pick anything: the fold angles are real numbers, determined by the panels through equations that have a solution or do not. Replacing a discrete choice with a continuous solve removes every ordering question at once, and introduces a failure of its own.

 Paper is made in ChinaPaper reaches JapanPaper is made in EuropeFolded paper is used ceremonially in Japan400 yrPaper is folded for amusement in Japan980 yrThe thousand cranes897 yrThe pajarita is folded in Spain293 yrPaper folding is taught as geometryOne fold solves a cubicThe diamond pattern in a crushed cylinderThe conditions at a flat-foldable vertexThe dashed-and-dotted diagram notationThe Miura foldA five-pointed star from one straight cutAny straight-line drawing, from one straight cutyear of the source500100015002000the date generally giventhe oldest source that says somedian overrun 201.5 years Who found it, and when

The cure was named first

A heavy-tailed search runtime, the arithmetic for cutting it off and restarting, and the reason restarts work at all were established in the study of search between 1993 and 1998. This collection imported all three, and inherited with them the phenomenon they answer — which is that randomising a search's choices is what makes the tail.

 proving the glued square cell has no lettering1×1, 4 panels3proved there is none · the other test found one in 32×2, 16 panels35proved there is none · the other test found one in 93×3, 36 panels3,455proved there is none · the other test found one in 6254×4, 64 panels200,000still running at the budgeta bar at the budget is a search still running, not a proof What it costs to know

Pruning on proofs alone

A search that discards a branch it cannot prove wrong is not a search. Deciding whether a periodic pattern's layer relations really contradict themselves is far dearer than the disc's one-pass test, so the cheap test is asked first — it is sufficient, so it settles almost everything — and the expensive one runs only on what the cheap one rejects. Five of nine steps on a small cell, fifty thousand of fifty-seven on a large one.

 proving the glued square cell has no lettering1×1, 4 panels3proved there is none · the other test found one in 32×2, 16 panels35proved there is none · the other test found one in 93×3, 36 panels3,455proved there is none · the other test found one in 6254×4, 64 panels200,000still running at the budgeta bar at the budget is a search still running, not a proof What it costs to know

The cost of proving something false

A search closing its whole tree is the strongest result this collection can produce, and on a glued tessellation it produces one that is wrong. What it costs to reach is three steps at one period, thirty-five at four, three thousand four hundred and fifty-five at nine, and more than two hundred thousand at sixteen — growing far faster than the cost of finding the lettering it says does not exist.

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

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.

 the pieces that are one panelleft and right edges identified — 9 pieces, 6 panels9 pieces on the drawing6 panels on the sheet10 creases, 4 verticeskeeps the sidetwo pieces of one shade are one piece of paper, a cell apart What it costs to know

The tube a map makes

Join one pair of a map's edges and the result is a tube — a real object, foldable in the hand, and neither the strip's problem nor the torus's. It has one loop that cannot be shrunk instead of two, it keeps its bottom layer because it keeps half its rim, and half its sizes are refused by a parity the flat map does not have.

 degree is how far out the number is; height is what the construction costsnumberdegreesteps in the towerwhat the steps are½10 stepsa fold in half√221 stepthe diagonal of the squareφ21 stepthe silver rectangle's cousin∛231 stepdoubling the cube2 cos(2π/7)31 stepthe regular heptagon∜242 stepsa square root of a square root∛2 · √262 stepsa product of two of them2^(1/5)5no tower reaches ita fifth root2 cos(2π/11)5no tower reaches itthe regular hendecagon2^(1/8)83 stepsthree square roots2^(1/9)92 stepstwo cube roots2^(1/12)123 stepstwo squares and a cube2^(1/16)164 stepsfour square roots1 pairs invert: 2^(1/9) is of degree 9 and 2 steps, 2^(1/8) of degree 8 and 3a degree 2^a · 3^b is a steps of square root and b of cube root, so the height is a + b and nothing else Axioms and construction

Reachable is not cheap

The closure is what makes folding a theory rather than a bag of tricks: constructions can be built out of constructions. What that also means is that constructions have lengths and the lengths compose, so every reachable number has a height as well as a degree — the number of extension steps the shortest tower to it must take. The two orderings disagree, and a ninth root is a shorter tower than an eighth.

 the count that was made, and the count that was notboth are floors: neither enumeration tracks which fold an alignment attaches tofreedomspaper onlywith simultaneous creasesneeding oneone fold277—two at once4228664three at once650296246four at once895791696five at once1016117921631at two folds the omission is 64 operations of 86 — 74% of them, and none can be described without naming the other creasea pair of hands cannot make a condition between two creases it is making; a jig holding two lines can Axioms and construction

Twenty-two is a floor

The enumeration that gives seven single-fold axioms spends each fold line's two degrees of freedom on alignments to points and lines already on the paper, and its own account says what it leaves out — an alignment may refer to a crease being made in the same instant. Adding those back leaves the single-fold count at seven and takes the two-fold count from twenty-two to eighty-six, of which sixty-four cannot be stated in terms of the paper at all.

 the same fold, on five sheetsa corner brought to the midpoint of the far edge, and what comes outsheetleft edgeright edgethe crossingwhat happenedsquare1.000 × 1.0003/87/82/3a third, exactlyA series, tall1.000 × 1.4147/1611/162/7a number, and not a thirdA series, wide1.414 × 1.000—1.2500—the crease leaves the paper3 : 2, tall1.000 × 1.5004/92/31/4a number, and not a third3 : 2, wide1.500 × 1.000—1.3438—the crease leaves the paper2 sheets answer and are wrong; 2 refuse — and the difference between the two is a right anglethe alignment does not know what shape the paper is, and neither does the folder following it Axioms and construction

A construction assumes its sheet

Haga's fold gives exactly two thirds on a square. Run the same alignment on an A-series sheet held tall and it gives exactly two sevenths, with the crease meeting the vertical edges at seven sixteenths and eleven sixteenths — every one of them a clean fraction, none of them what the recipe promised. Turn the same rectangle through a right angle and the crease leaves the paper instead, which is the loud failure rather than the quiet one.

 what a paper and a sheet size leave between themthe largest layer count both ceilings allow, and which one decided itpaper105 mm148 mm210 mm297 mm420 mm594 mmhands over atnewsprint65 µm46464646464646 mmcopier paper100 µm30303030303030 mmkami70 µm42424242424243 mmwashi40 µm75757575757575 mmfoil-backed tissue26 µm105115115115115115115 mmunryu tissue18 µm105148166166166166167 mmstack tolerance 3 mm, finest crease 1.0 mm · stack: L < feature ⁄ t · grid: L < sheet ⁄ cell · crossing at cell × feature ⁄ t Who found it, and when

Which ceiling is binding

Two constraints hold a design's layer count down and both are ceilings on the same number. The stack gets better as the paper thins; the grid gets better as the sheet grows, because piling layers needs divisions and a division cannot be finer than a folder can place it. They cross at a sheet size that rises as the paper thins — so on the papers a classical folder had, the substrate really is the limit, and only at tissue weights does the hand take over.

 the bar is what the whole job costs in expectation, in nodeson the rhombille patch, over the same 120 measured runs as the fixed cutoffsbest fixed, 100512chosen after seeing the runsunit 132226.30 times the best fixedunit 228545.58 times the best fixedunit 525424.97 times the best fixedunit 1021524.20 times the best fixedunit 2017623.44 times the best fixedunit 508481.66 times the best fixedunit 1005511.08 times the best fixedunit 2006381.25 times the best fixeda unit of one assumes nothing about the runs; every larger unit is a guess at their scale Who found it, and when

What the hindsight was worth

The best restart cutoff for the one tessellation search with a heavy tail was read off a hundred and twenty measured runs, which nobody running the search could have done in advance. The universal schedule needs no such knowledge, and on the same runs it costs 3,222 nodes in expectation against 512 for the cutoff chosen by looking — a factor of 6.3, which is close to the base-two logarithm of that cutoff, as the theory of the schedule says it should be. A larger unit brings the schedule within a few per cent of the hindsight, and choosing the unit is choosing the scale the schedule was meant not to need.

 three enumerations of the same thinga fold line has two freedoms, so m of them have 2m — the question is whether the budget is one pool or m pursesfolds at oncepaper onlypooled, with crossingseach alignment attachedthe ratio1777× 1.022286105× 1.23502963042× 10.3495791145,211× 183.6516117929,782,771× 5459.1the last column is what tracking which fold an alignment names is worth, and it grows because the naming itself grows Axioms and construction

Each fold needs its own two

The enumeration that gives seven axioms spends a fold line's two degrees of freedom on alignments; run for m folds it spends 2m from one pool, and a pool can be spent three on one line and one on the other, which determines neither. Attaching every alignment to the fold it constrains repairs that, and two other things — and the two-fold count goes from twenty-two to a hundred and five, of which only twenty-eight have to be made at one instant.

 first pointsecond pointthe sixth axiom, at its full countthe first foldthe second foldthe third foldthree folds, each carrying one point onto one line and the other point onto the other — the most any single fold can offer Axioms and construction

Counting operations is not counting power

The catalogue of simultaneous-fold operations runs from seven to nearly ten million between one fold and five. What a construction can reach does not: each fold admits at most three lines, because two parabolas have three proper common tangents and not four, so m folds admit at most three to the m — and the largest polynomial degree they actually settle is smaller again, at twice m plus one. Three counts of the same subject, growing at three speeds.

 throughthroughlands on the other creaseand so does this onea cyclic operation, solvedeach crease is described in terms of the other, so neither can be made first and no order exists Axioms and construction

A crease that does not exist yet

Simultaneous folding is usually described as a problem of dexterity — several coincidences to be achieved in the same instant. The reference graph says otherwise: of the hundred and five two-fold operations, twenty-eight need no simultaneity and forty-nine can be done in an order, leaving twenty-eight whose folds each name the other. Those are not hard to hold. They are hard to know, and a loop that guesses and re-solves finds them at eight per cent of the error a pass.

 0123400.010.020.030.040.05gearing between the two creasesradians of errormoved at the firstleft at the secondworst at a gearing of onetwo actuators disagreeing by 0.05 radians, equal stiffness · the sheet settles where the stored energy is least Rigid folding

Two drivers and one freedom

Two actuators on a sheet with one degree of freedom are two commands for one number, and if they disagree by a hundredth of a radian the sheet cannot satisfy both. Where it settles is decided by the gearing between the two creases: a strongly geared pair absorbs the disagreement and leaves a quarter of it standing, while a weakly geared pair keeps ninety per cent. The loosest coupling is the expensive one, which is the opposite of what coupling usually means.

 what a finer pattern costs in confidenceeach hinge working 0.999 of the time, against a target of 99 per cent for the whole deploymenthingesthe system openseach hinge needssuccesses to show itand the article itself899.2%0.9987442,385cannot be tested2497.6%0.9995817,154cannot be tested6094.2%0.99983317,885cannot be tested12088.7%0.99991635,769cannot be tested30074.1%0.99996689,422cannot be testedr consecutive successes put a 95 per cent lower bound of 0.05^(1⁄r) on a hinge, and a flight article deploys once Rigid folding

The crease count is a reliability budget

A deployment that needs every hinge to work is the hinge reliability raised to the crease count, so the fineness that buys compaction spends the probability of getting it. At a thousandth of a chance of a hinge failing, sixty hinges give a 94 per cent deployment and three hundred give 74. The fold count that maximises expected compaction is well below the one that maximises compaction — and demonstrating the result takes tens of thousands of successful tests on an article that itself deploys once.

 the pale bar is every folded state the strip has; the dark one is what the machine reachesthree machines on the same strips, and none of them is the flat-folding theorem3 equal stamps · takes every layerall 123 equal stamps · takes one layer4 of 123 equal stamps · takes any block reaching an edgeall 124 equal stamps · takes every layerall 324 equal stamps · takes one layer4 of 324 equal stamps · takes any block reaching an edgeall 325 equal stamps · takes every layerall 1005 equal stamps · takes one layer4 of 1005 equal stamps · takes any block reaching an edgeall 1006 equal stamps · takes every layerall 2886 equal stamps · takes one layer4 of 2886 equal stamps · takes any block reaching an edgeall 288counted over every marking of the strip that folds flat at all What it costs to know

Deciding is not making

Four earlier essays here ask which machines can flatten a strip at all, and the answer sorts them into a lattice with one column full and three with holes in it. Asked instead what each machine can produce, the three sort completely differently: the machine that may choose its block reaches every folded state of every strip tried, the machine that takes one layer reaches exactly four whatever the strip is and however long, and the machine that takes the whole pile is the only one whose answer depends on the spacing at all.

 how deep into the pile the machine has to be allowed to reach before it reaches every stateone layer is the patient machine and the full depth is the machine that may choose3 equal stamps22 of a possible 3 · 12 states4 equal stamps33 of a possible 4 · 32 states5 equal stamps44 of a possible 5 · 100 states6 equal stamps55 of a possible 6 · 288 statescreases at .20 .55 .7022 of a possible 4 · 8 statescreases at .15 .40 .50 .8522 of a possible 5 · 16 statescreases at .13 .31 .62 .7844 of a possible 5 · 24 statescreases at .40 .50 .62 .7233 of a possible 5 · 12 statescreases at .08 .24 .28 .35 .7255 of a possible 6 · 48 statesthe even strips are the ones that need the most, and they are the ones the machine that takes everything does best on What it costs to know

The easiest strip needs the deepest reach

The patient machine and the machine that may choose are the two ends of one number: how many layers of the pile a machine is allowed to hold. At one it reaches four states whatever the strip; at the pile's full depth it reaches everything. In between it is a machine nobody has defined, and measuring where completeness arrives inverts these essays' own ordering — the evenly creased strip, which the machine that takes everything folds perfectly, needs the deepest reach of all, and one uneven strip is complete at two.

 the shortest sequence of folds to each state, for the machine that may choose its blockfewest, mean and most over every state of every marking; the last column compares the machine that takes everythingstripstatescreasesfewestmeanmostall layers4 equal stamps32322.753the same5 equal stamps100433.404the same6 equal stamps288534.045the samecreases at .20 .55 .708333.003reaches nonecreases at .15 .40 .50 .8516444.004reaches nonecreases at .13 .31 .62 .7824444.004reaches nonecreases at .40 .50 .62 .7212444.004reaches nonecreases at .08 .24 .28 .35 .7248555.005reaches nonea fold uses at least one crease, so no sequence is longer than the crease count What it costs to know

A shallow machine pays in states, not folds

A machine allowed to take only a few layers of the pile at a time reaches fewer folded states, and the natural fear is that it also reaches the ones it does by much longer sequences. Walked breadth first, so that every state's shortest sequence is found, it does not. On unevenly creased strips every state takes exactly one fold per crease at every depth, because no two creases ever lie on one line. On strips of equal stamps a shallower machine needs one fold more for a minority of states and two more for eight of the 924 states at seven stamps — and never more than the crease count, which no machine can exceed.

 the pile 0 6 1 2 3 4 5 and its turns, which the all-layers machine cannot foldMVMVMMVVMVMMMMVMVMVVVMVMVMMMVMVMVVVMVMVMMM What it costs to know

Fourteen states are one pile

A machine that folds every layer at once reaches every folded state of a strip of six equal stamps and misses fourteen piles at seven. The fourteen are not fourteen things. Taking a pile's bottom stamp and putting it on top maps foldings to foldings, so the 462 piles of seven stamps fall into 33 classes of exactly fourteen, and the missed piles are one whole class: the pile 0 6 1 2 3 4 5 — an accordion of five stamps with the last stamp wrapped round it and slid into the fold that holds the first — seen from each of its seven stamps. At eight stamps the machine misses 64 piles, and they are exactly the piles that leave that one when an end stamp is removed.

 the expected cost of the whole job under rules that learn from their own failures, in nodeson the rhombille patch, over the same 120 measured runs; the dark bar borrows its unit from other patchesbest fixed, 100512chosen after seeing the runsdouble after every failure1820at least 3.56 times the best fixeddouble after every failure, from sixteen1805at least 3.53 times the best fixedgrow by half after each failure1204at least 2.35 times the best fixeduniversal, unit of one32226.30 times the best fixeduniversal, unit from other patches8721.70 times the best fixeda rule that reads only its own failures cannot beat the best fixed cutoff, and cannot know which that is Who found it, and when

A failure teaches a schedule nothing

The universal restart schedule costs 6.3 times the cutoff chosen by hindsight on the one folding search with a heavy tail, and the obvious repair is a schedule that learns its scale from the attempts it has already made. It cannot. A failed attempt costs exactly its cutoff and reports only that the run needed more, so every rule that chooses the next cutoff from its own failures writes down the same list whatever happens — a fixed schedule in disguise. On the measured runs, doubling after every failure costs at least 3.6 times the hindsight, and growing by half at least 2.4. What does come near is information from outside the run: the universal schedule given the longest search on four other patches as its unit costs 1.7 times the hindsight. The field that supplied the schedule reached the same conclusion, and answered it by watching runs from the inside.

 the energy two actuators store in a disagreement, pair by pairenergy k₂δ² ⁄ (1 + k₂g² ⁄ k₁); the last column is the second crease's holding stiffness, k₂ + k₁⁄g², kept when k₂ is cut to a tenthgearingbalancing k₂ ⁄ k₁equal stiffnesssecond ten times stifferten times softerstiffness kept0.31610.010.915.000.09992%0.5393.440.772.560.09780%0.7841.630.621.400.09466%0.9341.150.531.030.09258%1.0001.000.500.910.09155%1.7610.320.240.310.07632%a mesh with no two vertices alike, driven at c:0:1 · energy stored in the fight, in units of δ² times the first actuator's stiffness Rigid folding

A gearing reflects stiffness squared

Two actuators on a sheet with one freedom disagree, and the sheet settles where their stored energy is least. With unequal stiffnesses the answer depends on them only through k₂g² ⁄ k₁ — the second actuator, seen from the first crease, is a spring of stiffness k₂g², the gearing entering squared as a gear train reflects any stiffness. That settles which actuator to make compliant. On a rigid mesh's loosest pair a second actuator ten times stiffer than the first stores fifty times the fighting energy of one ten times softer, and softening it gives up only 8 per cent of how firmly that crease is held, because the first actuator already holds it ten times over through the gearing. On the tightest pair softening saves four times the energy and gives up 68 per cent of the hold. Compliance is cheap exactly where the fight is expensive.

 a 4-by-4 Miura, every crease driven in turn, at 10 angles along the motionevery consistent assignment enumerated at each crease, with both configurations found at every vertexanglecreases × states they leavethe creases that decide it0.24×1 8×2 4×4 8×8c:3:2 c:3:3 r:3:2 r:3:30.44×1 8×2 4×4 8×8c:3:2 c:3:3 r:3:2 r:3:30.64×1 8×2 4×4 8×8c:3:2 c:3:3 r:3:2 r:3:30.84×1 8×2 4×4 8×8c:3:2 c:3:3 r:3:2 r:3:31.04×1 8×2 4×4 8×8c:3:2 c:3:3 r:3:2 r:3:31.24×1 8×2 4×4 8×8c:3:2 c:3:3 r:3:2 r:3:31.64×1 8×2 4×4 8×8c:3:2 c:3:3 r:3:2 r:3:32.04×1 8×2 4×4 8×8c:3:2 c:3:3 r:3:2 r:3:32.44×1 8×2 4×4 8×8c:3:2 c:3:3 r:3:2 r:3:32.84×1 8×2 4×4 8×8c:3:2 c:3:3 r:3:2 r:3:3every row is the row above it: the census is a property of the pattern, not of how far it has folded Rigid folding

The deciding set does not move

A driven Miura leaves several folded states from most of its creases and exactly one from a few, and those few are where an actuator belongs. It was reported that the few change along the motion — four of twenty-four at 0.6 radians, fourteen at 0.8 — and that a five-by-five sheet had a crease leaving fifteen states where every other count was a power of two. Mapped at twenty angles from 0.1 to 3.0 radians on three sizes of sheet, neither survives. Every crease leaves the same number of states at every angle, every number is a power of two, and the same creases decide the sheet throughout. The changes were the vertex solver losing one of a vertex's two configurations on 138 of 8,640 solves, and the configurations it lost can be carried exactly from an angle where it finds both.

 one freedom, or severala stuck hinge or a failed actuator loses its own module and nothing elsemodulesall of it opensshare expectedat least 90%at least 75%173.3%73.3%73.3%73.3%272.6%85.2%72.6%72.6%570.4%93.2%70.4%96.0%1067.0%96.1%94.4%99.4%2060.6%97.5%98.7%100.0%5044.8%98.4%100.0%100.0%10027.1%98.7%100.0%100.0%300 hinges at 0.999 each, split evenly · each module's actuator works 0.99 of the time Rigid folding

Splitting a sheet buys area, not certainty

A folded deployable with one freedom needs every hinge and its one actuator, and three hundred hinges at 0.999 each open all the way 73 per cent of the time. Split the same hinges among ten separately driven modules and a stuck hinge costs only its own module: the share of the area expected to open rises to 96 per cent, and the chance of at least nine tenths of it rises to 94. The chance of all of it falls, to 67 per cent, because every freedom added is an actuator added. So freedoms, actuators and reliability trade in a definite way: one freedom is the best design only for a mission that is worthless without its whole area, and for any mission that can live with less, several freedoms win by a margin that no improvement in the hinges matches.

 what ten branch orders cost on the same four sheetsnodes of search; the sheets are the same drawings as the sweep abovethe square grid, 4×4, glued69 to 24636, 1 gave upthe square grid, 4×4, cut42 to 55the square grid, 3×3, glued20 to 731the square grid, 3×3, cut25 to 32each bar runs from the cheapest of 8 branch orders to the dearest, on a logarithmic scale; a dot is the middle one What it costs to know

The route, not the sheet

Every cost measured for a glued sheet has been one number from one branch order, and a backtracking search's cost belongs to the pair. Asked under eight orders instead of one, a cut cell's cost barely moves — 42 to 55 nodes — while the torus over the same drawing runs from 69 to 24,636, with one order giving up entirely. The glued sheet's best order costs less than twice the cut sheet's, so most of what a single order charged to the gluing belongs to the route through it.

 nodes per free letter, cheapest route against the middle onecheapest of eightmiddle of eight× where no route of that kind finished · periods along the bottom0.3110100×2345the square grid, glued×123the triangular grid, glued××1234the honeycomb, glued0.3110100×123the elongated triangular tiling, glued××12the rhombille tiling, glued×123the rhombille tiling, cut What it costs to know

The cheapest route crosses later

A search for a consistent lettering has a threshold: below it the letters propagate and the cost is a third of a node per crease, above it the search backtracks and the cost explodes. The threshold was measured with one branch order. Measured with eight, the cheapest route never starts searching before the typical one, and on most sheets it starts a period or two later — so part of every threshold on the record belongs to the route. And the one cut sheet past its threshold, the rhombille's, spreads across nearly three orders of magnitude of cost, which moves the spread off the gluing and onto the threshold.

 after one round from a bare square, the 80 new folds a second round offers, by what each adds alonenine references and twelve lines on the sheet; a fold adds a reference wherever it crosses a line already there, on the paper, somewhere newadds 61620 per cent of the menuadds 545 per cent of the menuadds 4810 per cent of the menuadds 3810 per cent of the menuadds 21215 per cent of the menuadds 145 per cent of the menuadds 02835 per cent of the menuthe average fold on the menu adds 2.50; 16 folds tie for the most, 6; of the 28 that add nothing, 28 never cross the paper at all Axioms and construction

A fold is worth what follows it

After one round of folds from a bare square the sheet carries nine references and twelve lines, and a second round of the four linear axioms offers eighty new folds. Made alone, the best of them adds six references and the average two and a half. Made all together they add 556 — nearly seven a fold — because a fold's yield is mostly its crossings with the folds that come after it. So the value of choosing has to be measured along an order: always making the most productive fold next reaches half the round in 28 folds where a random order takes 51, and all of it in 52, which is the fewest folds that can. The conic axiom's 305 extra folds leave the first eight choices exactly as they were.

 equal stamps to nine: what the all-layers machine misses, and where the misses come frominherited: taking an end stamp off leaves a pile missed one size down; turning moves the bottom stamp to the topstampsfoldingsreachedmissedinheritednewclasses missedturning a pile41616000—keeps the machine's reach55050000—keeps the machine's reach6144144000—keeps the machine's reach7462448140141 whole, 0 in partkeeps the machine's reach813921328646404 whole, 0 in partkeeps the machine's reach94536405248432416024 whole, 8 in part52 reached turn missedto eight stamps every miss is a whole class and every miss past seven is inherited; at nine neither holds What it costs to know

Nine stamps have piles of their own

A machine that folds every layer at once reaches every folding of six equal stamps, misses one class of fourteen piles at seven, and at eight misses exactly the piles that shrink to that class when an end stamp is taken off. The prediction was that nine would do the same. Counted directly, nine equal stamps have 4,536 foldings and the machine reaches 4,052. Of the 484 it misses, 324 are inherited from eight and 160 are new — among them the nine-stamp tucked pile. And the symmetry that made the misses whole classes breaks: at nine stamps, turning a pile's bottom stamp to the top takes 52 piles the machine reaches to piles it cannot.

 the four letterings of a three-by-three map the loop test refusesdash-dot: mountain; dashed: valley; each passes all four vertices and still has no layer orderone in sixty-four of the letterings a three-by-three map allows What it costs to know

A map refuses in small pieces

The one-pass refusal — a circle in the arcs a map's letters force — fires on four of a three-by-three map's 256 letterings and on none below it, and the question was how it grows. It grows by windows. Every lettering it refuses on a four-by-three or five-by-three map contains one of those four refused three-by-three patterns somewhere inside it, so the share refused is almost exactly one minus 63⁄64 to the power of the map's three-by-three windows. Four by four is the first map with a refusal no window explains, 64 of its 2,112. The rise is smooth, not sharp: a quarter at six by six, near half at eight, seven tenths at ten.

 the circle behind a refusal, on the smallest maps that need each onedash-dot: mountain; dashed: valley; heavy loop: the circle, each step to a panel the letters put above the last3 by 38 creases4 by 412 creases5 by 414 creases5 by 516 creases What it costs to know

The long circles go round the middle

A four-by-four map has 64 letterings the one-pass refusal catches with no three-by-three pinwheel anywhere in them, and they are not larger pinwheels. They are four shapes, sixteen versions of each, none unchanged by any turn or mirror, and every one is a circle of twelve creases running round the middle of the map. Read the same way on larger maps, every refusal is a circle round some rectangle of panels, and it needs the whole of that rectangle: one in 64 three-by-three rectangles closes one, one in 512 four-by-fours, and rectangles three cells across close nothing a pinwheel does not. Two window sizes explain all but 0.07 per cent of a twenty-by-twenty map's letterings.

 what refuses a lettering of a tube 5 panels longone bar to a circumference; the whole bar is the share refused0%25%50%75%100%2 round49.0%4 round72.9%6 round59.5%8 round52.6%10 round52.7%12 round54.7%a three-by-three windowa four-by-four windowa circle round the tubea longer circle on the sheet1,500 letterings drawn at random for each tube; each is filed under the first test that refuses it What it costs to know

A tube refuses round itself

On a flat map the cheap refusal — a circle in the arcs a lettering forces — is almost entirely local: small windows of the map explain all but a sliver of it. Glue the map's left edge to its right and the windows still refuse at exactly the rate their number predicts, counted across the seam. But a new refusal appears that no window can contain, a circle that goes once round the tube. It refuses half of every lettering of a tube two panels round, over half of one four round, a quarter at six, and it falls by about half with every two panels of circumference while the tube's length hardly matters.

 the share of a strip's foldings the all-layers machine can makeevery pile counted; a share is the piles the machine finishes over the piles that exist00.2500.5000.75014681012stampsshare of the foldings reachedfoldings: ×3.20 a stamp from nine onreached: ×2.99 a stamp from nine on7 stamps: 448 of 4628 stamps: 1328 of 13929 stamps: 4052 of 453610 stamps: 12040 of 1406011 stamps: 36152 of 4631012 stamps: 106816 of 146376the reach grows by just under three a stamp and the foldings faster; while that holds, the share keeps falling What it costs to know

The machine's misses have no short list

A machine that folds every layer at once misses fourteen piles of seven equal stamps, sixty-four of eight and 484 of nine, and the question left at nine was whether its failures could be described by a short list of forbidden piles. Counted to twelve stamps, and to thirteen by the same method, they cannot. What the machine reaches is closed under taking an end stamp away, for a reason that fits in a sentence, so every miss contains a smallest one, and the smallest ones keep arriving: 14, 0, 160, 12, 1,194, 116 and 7,786 from seven stamps to thirteen, the tucked pile among them at every odd length. Meanwhile the machine's reach grows by just under three a stamp and the foldings by more, so the share it can make falls from all of them at six stamps to under two thirds at thirteen.

 how far each search is from the best packing knownboth at 120 restarts of 6,000 steps; nothing below zero is possible02461011121314151617181920discsshort of the best packing known, per centthe free searchbest: a mirrorbest: a half-turnbest: a quarter-turn Designing a base

Equal effort was counted in steps

A circle-packing search required to be symmetric was found to beat a free search of the same effort, and the reason given was that a smaller space is easier to search. Past eleven discs the test gets sharp: the free search falls behind the best packings known, 0.13 per cent at ten discs and 6.07 at twenty, and a symmetric search leads it by as much as 4.18. But tighten the free search's packings to the arrangement they were heading for and most of that shortfall disappears — at twenty discs, all of it. Give the free search twice the steps and the lead reverses. The effort was equal in steps and unequal in what a step does: a symmetric search moves half as many coordinates, so each is moved twice as often.

 each run, read at node 50, against how long it turned out to bethe top band is runs still unfinished at 20,000 nodes1234048121620times the loop test has refused the run so farnodes the run takes to finish, log₁₀finishes inside the cutofffinishes laternever finishesupright line: the refusalcount that restarts a runlevel line: the cutoff Who found it, and when

A long run shows itself early

A restart schedule that learns only from failures was shown to be a fixed list in disguise, unable to beat the cutoff hindsight would choose. A run reports more than whether it has finished, though, and the search for a lettering of the rhombille patch already counts the one thing worth reading: how often its loop test has refused it. Read at node fifty, the count separates the runs. Of fifty runs refused eight times or more, one finishes within a hundred nodes; of seventy refused fewer times, twenty-two do. Restarting on that count costs 387 nodes in expectation against 483 for the best fixed cutoff — and chosen on half the runs and priced on the other half, 437 and 435 against 541 and 579, which on one half is cheaper than that half's own hindsight. The search literature's answer was right, and on a crease pattern it needs one number.

 nodes of search under drawn and built routes, sheet by sheetlogarithmic, from 10 to the budget of 20,000; a cross at the right marks searches that did not finish101001,00010,000the rhombille tiling, 2×2, glueddrawn0 of 8joined first6 of 8crossed first0 of 8the rhombille tiling, 2×2, cutdrawn7 of 8joined first7 of 8crossed first7 of 8the rhombille tiling, 1×1, glueddrawn8 of 8joined first8 of 8crossed first8 of 8 What it costs to know

The route built from the gluing

A search for a consistent lettering of a glued sheet costs a third of a node a crease on its cheap routes and thousands on its dear ones, and an account was offered of which routes are cheap: the ones that take first the creases whose choice propagates through the gluing. That account can be turned into a route rather than tested on samples, and there are two ways to read it. Built the first way, a route finishes nearly twice as many searches past the threshold as a drawn one does, and on the rhombille torus — where none of eight drawn routes finishes inside twenty thousand nodes — six of eight built routes do, the cheapest in 1,183. So the rhombille's difficulty belongs to the route. But which reading works changes with the tiling, and on the elongated tiling, where every drawn route finishes, the built ones lose searches.

 a smallest miss of 9 stamps with both ends hooked, and the piles an end stamp leavesstamp 0 dashed in one colour, the last stamp in the other; a crease holding a hooked end is heavy1 8 0 7 6 5 4 3 2missed1 0 7 6 5 4 3 2stamp 8 off: reached0 7 6 5 4 3 2 1stamp 0 off: reached What it costs to know

An odd strip can hook its own ends

A machine that folds every layer at once has smallest misses by the thousand on strips of an odd number of equal stamps and by the hundred on even ones, and the alternation had no explanation. Most of it is one arrangement. On an odd strip each end stamp's free edge faces the crease at the other end, so an end can lie inside the far end's fold with its edge pointing in: a hook. Nine in ten of the odd strips' smallest misses carry one, an even strip cannot carry one at all, and the misses without a hook — 12, 12, 82, 116, 442 and 740 from nine stamps to fourteen — stop jumping by a factor of a hundred between neighbouring lengths.

 references on the paper, fold by fold, choosing from a growing menu and from the round's ownthe bound is what k folds can make at most, whatever they are; the growing menu's curve lies on it020040060002040folds madereferences on the paperthe round, 565growing menuthe boundthe round's menuthe round's 565 references take its own menu 52 folds; a growing menu passes 565 at fold 29, and no 28 folds of any kind can Axioms and construction

Each new fold can cross every old one

A folder choosing each fold from the second round's fixed menu needs fifty-two folds for the round's 565 references, and no fewer. Let the menu grow — after every fold, every fold the references now on the paper specify — and the count obeys a bound that has nothing to do with axioms: a new line can cross each line already through the paper once, and the rim twice. After k folds that is at most 9 + k(k + 11)/2 references. The greedy folder meets the bound exactly at every one of thirty folds, passes 565 at the twenty-ninth, and no twenty-eight folds of any kind can. But of its 589 references only fifteen are the round's, and they are nearly useless: the median lies a seventieth of a millimetre from its nearest neighbour.

 what happens to the tail when a refusal is readthe most recent decision is changedthe most recent decision a refusal names is changed2340306090120the runs, each search's own sorted from quickest to longestnodes, log₁₀first search: 48 of 120 unfinished at 20,000 · second: longest run 462 nodes Who found it, and when

A trapped run is holding four letters

Thirty of the hundred and twenty searches for a lettering of the rhombille patch are refused sixteen times in their first fifty nodes, and the proposal was to find the crease that traps them. No crease can: turning every letter over turns a folded state upside down, so no single letter is ever wrong. What the thirty share is a relation among four creases, mountain, valley, mountain, valley, and the proof that it has no lettering takes seven nodes. The runs cannot find that proof, because they change their most recent decision whether or not it had anything to do with the refusal. Change instead the most recent decision the refusal names, an idea from the 1970s, and the tail is gone: all 120 finish, the longest in 462 nodes, at an average of 148 against 387 for the best restart policy, and no restart helps at all.

 searches that finish inside 5,000 nodes, of 8 on each sheetchanges the most recent decisionchanges the most recent one a refusal names101001,0005,000the rhombille tiling, 2×2, cut5 → 8the rhombille tiling, 2×2, cylinder0 → 8the rhombille tiling, 2×2, torus0 → 1the honeycomb, 3×3, cylinder7 → 7the honeycomb, 3×3, torus4 → 4the square grid, 4×4, cylinder8 → 8the square grid, 4×4, torus5 → 5the triangular grid, 3×3, torus1 → 1nodes to a lettering, on a logarithmic scale; the column on the right counts finished searches What it costs to know

The torus keeps its tail

Reading why a branch failed removes the heavy tail from the search for a lettering of a cut sheet: on the rhombille drawing at two periods five of eight searches finish becomes eight of eight, and glued along one pair of edges none of eight becomes eight of eight. Glued along both, it stays at one of eight, and it stays there when every refused loop is also remembered. Two accounts of why are refuted on the way: every refusal on every sheet is a loop, so tilings do not differ by how they fail, and a torus's refusals blame no more of the stack than a cut sheet's. What separates them is the length of the proof. Undo twenty decisions from a stopped run and the proof that the letters left are already lost takes 33 nodes on a cut sheet and about 2,400 on a torus, so a jump on a torus has nothing short to read.

All themes