Origami & Folding
what one sheet can do
Concept

Rediscovery — where it appears

The same object or result arrived at more than once, independently. It is common in this subject because the flat-folding conditions leave very few options, so a small solution space produces repeated arrivals that look like influence and are not.

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

each mark is one claim: right of the line means dated earlier than its evidencethe vertical line is agreement between the claim and the record0paper itselfwhen and where the material was made, which is archaeologymedian 0 · spread 204a thing people dida fold, a ceremony, a toy, a lesson — something with no first daymedian 347 · spread 979a thing somebody proved or designeda statement with a paper, a date and an authormedian -14 · spread 131

Two kinds of claim

This site has published a median overrun of two centuries and a mean of twenty-two years in the opposite direction, and both are right. Split the record by what each claim is about and the reason appears: every claim about a practice is dated earlier than its evidence, most claims about a result are dated later, and the two scatter by 979 years and 131.

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

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.

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

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.

history · Rediscovery 3 creases on a Möbius bandthe panels take two coloursseamthe same seam123the right edge onto the left, turned over3 creases, 3 panelsinterior vertices: 0two-coloursthe reflections closeand turn the paper the right waymountainvalleyraw edge

Found by people not folding paper

The shortest strip that makes a Möbius band has a literature, and it is in differential geometry rather than in origami. The two subjects have the same number, they reached it by completely different routes, and neither of them cites the other — which is the fourth time this collection has found that shape.

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

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.

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

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.

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

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.

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

Named alongside it

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

Search costRestartAttributionRandomised algorithmDocumentary recordHeuristicWorst-case analysisIndependent discoverySearchBacktrackingCertificateClosure

All concepts