Origami & Folding
what one sheet can do
Concept

Certificate — where it appears

A short piece of evidence that can be checked without redoing the work. A folded state certifies that a pattern folds; a refusal is harder to certify, which is why the two answers are not symmetric.

Named by 8 essays across 4 fields — each of them below, with the objects they name alongside it.

0°30°60°90°0.250.400.550.700.85how much of the room between two vertices the twists takeno paper leftno assignment existstwist angleboth curves are measured rather than plotted from a formula

A no costs more than a yes

When a folding question comes back yes, it comes back with an object: a labelling, a stacking, a folded state that anybody can check in one pass. When it comes back no, it comes back with nothing but the assurance that a search looked everywhere — and that assurance is the first thing to break.

complexity · Hardness of folding every condition holds here6 creases4 creasesevery condition holds at the vertex on the paper — and one crimp later the smallest sector has the same letter on both sidesthe four conditions all hold · a stacking does not exist

A short reason to say no

When a folding question comes back yes it brings an object anybody can check. When it comes back no it usually brings nothing but the assurance that a search looked everywhere. At one vertex that is false: a refusal comes with a witness one or two steps long, out of a search space of a hundred and twelve, and the witness is a vertex the crease pattern does not contain.

complexity · Hardness of folding 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

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.

tessellation · Miura 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

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.

complexity · Search order 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

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.

complexity · Hardness of folding ruling out the square cell's loops, one direction at a timewhat is left splits248 arcs go, 24 remaindirection (1, 0)102 arcs go, 10 remainwhat is left splits010 arcs go, 0 remaindirection (-1, 0)102 arcs go, 10 remainwhat is left splits010 arcs go, 0 remainthe bar is how many arcs are still in play after the step

The arc that arrived twice

Which of two panels a crease calls its near one is decided by the order a face walk happened to number them, and the mirrored record is the same relation. Except on one sheet, where it is not — and that sheet turned out to be the one whose folded state comes back the other way up, which is how a duplicate in a graph became a diagnosis.

flat-folding · Layer multiplicity 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

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.

history · Rediscovery 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

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.

complexity · Search order

Named alongside it

The objects these essays reach for when they reach for this one.

Search costBacktrackingThe decision problemGluingNecessary conditionAssignmentConstraint propagationExhaustive searchLayer orderParitySearchCombinatorial explosion

All concepts