Generator

What a witness costs, against how rare one is

A generator in the flat-folding library, called 115 times across 29 essays. Below: what it draws with nothing specified and with the settings the essays give it, what it checked while drawing, and everywhere it is used.

lettering-search is one function. Everything below was drawn by it when the site was last published, at settings taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and when the generator changes, this page changes with it.

With nothing specified

`view: "populations", draws: 200`

`view: "luby", show: "sequences", kind: "rhombille", seeds: 120, budget: 20000`

`view: "luby", show: "learn", kind: "rhombille", seeds: 120, budget: 20000`

What it checked while it drew

Collected while it drew, not written by hand. The count is how many separate times that claim was put to the test.

0 of 200 letterings drawn at random from the same pattern agree with themselves, and the search reached one in 561 nodes ×4
the share of agreeing letterings falls from 100 of 100 to 1 of 100 as the grid grows ×4
every node of the straight skeleton is equidistant from each edge that defined it, so one fold serves them all — 1 checked ×3
stopping at 100 nodes and starting again costs 512 nodes in expectation, against 5697 for running to 5000 ×3
2 of 5 patches were never given a consistent lettering by 200 draws, and the search found one for every patch here ×2
2 of 6 meshes have no lettering at all whose panels can be stacked, which is a statement about the mesh ×2
48 of 120 runs were still going at 20000 nodes ×2
a larger unit helps — 100 nodes brings it to 551 — but choosing the unit is choosing a scale for the distribution, which is the knowledge the schedule was meant not to need ×2
the same search on the same pattern, 120 times, differing only in the order the letters were tried ×2
the share of random letterings that agree falls from 34 of 40 to 11 of 40 ×2
1 of 13 patterns carry creases whose letters no arc reads ×1
28 patterns across 4 standing populations, and on not one of them do sampling and searching disagree ×1
38 of 3924 candidate moves survive the conditions at a vertex, across two letterings of each patch ×1
and 2 that were refused at the lettering they arrived with fold at a different one ×1
and in those fifty nodes the vertex conditions refuse nothing on any of the 120 runs — every refusal the search makes that early is the loop test's ×1
and not one of them changes whether the lettering agrees with itself, though nothing in the move was designed to preserve that ×1
and the one schedule that beats every rule reading only its own failures — even counting theirs only up to the budget — is the one given a unit from outside the run: 872 nodes, 1.70 times the hindsight cutoff, with a unit of 53 taken from 4 other patches ×1
and the search's cost does not move with it: rarity and difficulty are different quantities ×1
at that turn 12 of the 142 creases are shorter than a hundredth of a millimetre on a 160 mm sheet, which no printer can put on paper ×1
both costs are exact expectations over the same 120 measured runs; nothing is simulated ×1
each of its four leaves closes a loop of panels on its own, with no further choice ×1
every backtrack in every one of these searches was a loop in the arcs; the four conditions at a vertex refused nothing ×1
every interior vertex of a grid has degree four, so every one of them carries the shortest loop a panel graph can have ×1
every lettering of every map up to 4 by 2 is consistent — the cheap refusal fires on none of them ×1
every one of the 120 runs takes the same six creases first, and on each the runs that end up loudest took a mountain about as often as the others did: 53% against 52%, 50% against 51%, 50% against 50%, 50% against 50%, 53% against 49%, 53% against 48% ×1
every one of the 48 runs still unfinished at 20,000 nodes holds, 8 to 27 decisions above where it has stopped, letters with a proof of no lettering, and the longest such proof is 179 nodes ×1
every one of them is shorter than a hundred-thousandth of the sheet, which is a fragment left by the clip rather than a fold ×1
every pattern the site prints at true scale is given a consistent lettering without one backtrack ×1
fitted on one half of the runs and priced on the other, the refusal policy costs 437 and 435 nodes against 541 and 579 for a fixed cutoff fitted the same way — and on one half it costs less than that half's own hindsight cutoff, 456 ×1
no move that survives the vertex conditions changes a buried crease, so a difference that lies in the buried creases is one no sequence of moves can cross ×1
no sequence of cutoffs does better than the best fixed cutoff read off the runs — at least 1820, at least 1805, at least 1204, 3222, 872 against 512, a sequence that reaches the measurement's budget still unfinished being counted only up to it — as the theory of restarts says no sequence can on a distribution that is known ×1
of the 120 runs, the 50 that the loop test has refused eight times or more by their fiftieth node include 1 that finishes within a hundred nodes and 28 that never finish within 20,000; of the 70 refused fewer times, 22 finish within a hundred ×1
on the same 120 seeds the search finishes 72 times inside 20,000 nodes when it changes the most recent decision, and 120 times, none past 462 nodes, when it changes the most recent decision a refusal names; with the jumps turned off it is the first search, node for node ×1
read at 25, 50, 75 nodes the refusal count beats the best fixed cutoff — 458 at node 25, 387 at node 50, 355 at node 75 against 483 — and read too late it has nothing left to say ×1
reading its refusals, a run costs 148 nodes on average with no restart at all, against 483 for the best fixed cutoff and 387 for watching the refusal count, and a cutoff chosen in hindsight takes it only to 148 ×1
restarting at node 50 once the loop test has refused a run 8 times, and otherwise cutting it at 151, costs 387 nodes in expectation against 483 for the best fixed cutoff, 166; a threshold too low throws away good runs and one too high keeps bad ones ×1
taken near the four creases, the proof that those letters have no lettering takes 7 nodes: 3 choices and 4 loops ×1
the 30 runs holding one relation among four creases are refused 15 to 17 times by node fifty, and none of the other 90 is refused more than 11 times ×1
the expectation is one attempt's cost over the chance that attempt is the last one needed, read off the measured runs ×1
the first map with a contradictory lettering is 3 by 3, and 4 of its 256 letterings are it ×1
the four creases all lie within 38 mm of one another on a 150 mm sheet, at its left side, so the contradiction is local ×1
the lettering drawn here was found by a search and then checked by the two tests that did not find it: the four conditions at every vertex, and a folded sheet rebuilt from scratch ×1
the panel count and the crease count are the same at every turn here, so the graph the search runs on does not change ×1
the panel graph, the arcs, the chains and the number of labellings at every vertex are identical at these turns ×1
the search visits about one node per panel — 8/8, 24/24, 9/9, 13/13, 60/65, 6/7, 28/28, 51/52 ×1
the shortest crease falls by four orders of magnitude at one turn of the hexagonal patch and at no other ×1
the universal schedule at a unit of one node costs 3222 in expectation, against 512 for the best fixed cutoff read off the runs — a factor of 6.30 ×1
the worst search anywhere in the four is 60 nodes, which is fewer than the patterns have panels ×1
what changes is which of the sectors at a vertex is the smallest, and with it which pair of creases the smallest-sector lemma forces apart ×1
what the turn changes is which labellings a vertex admits, because it decides which sector is the smallest one ×1
which is inside the guarantee of 192ℓ(log₂ℓ + 5) = 1,375,611 by two orders of magnitude, and close to log₂ of the best cutoff itself, 6.64 ×1

Where it is called

Every figure listed here is drawn by the same rule, so a mistake in the rule would be in all of them at once, and so would a correction.

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.

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.

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.

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.

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.

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.

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.

Every move leaves the verdict

The only change a folder can make to a lettering without breaking it is to push one vertex through, flipping two creases at once. Try every such move on five tessellation patches, from two different letterings each: nineteen of two thousand nine hundred and sixty-four survive the conditions, and not one of the nineteen turns a lettering that agrees with itself into one that does not, or the other way about.

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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

Twelve creases a micrometre long

A patch this collection has drawn for a long time carries a hundred and forty-two creases and a hundred and thirty arcs, and nobody had asked what the other twelve were. They are fragments left where the clip caught a pleat almost exactly at a corner — between one and nine micrometres long on a printed sheet, at one turn angle out of four, and it is the turn the collection prints.

What a grid costs in circuits

Box-pleating puts every crease on a square grid, and a square grid is the shape with the most short circuits per panel that this collection draws. On the sixteen-by-sixteen grid a designer actually works on, one mountain-valley labelling in a hundred agrees with itself. A search still finds one in two hundred and sixty-one steps.

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.

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.

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.

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.

All the figures · The flat-folding field · The patterns a reader can fold