Generator

What a witness costs, against how rare one is

A generator in the flat-folding library, called 103 times across 27 essays. Below: what it draws at its defaults and at the arguments the essays give it, what it checked while drawing, and everywhere it is used.

lettering-search is one function. Everything below came out of it during this build, at arguments 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.

At its defaults

`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 by running this generator with a listener on the assertions, not written here. The count is how many separate times this build put that claim 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
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
stopping at 100 nodes and starting again costs 512 nodes in expectation, against 5697 for running to 5000 ×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 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
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 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
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
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 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

Changing this generator changes every figure on this list, which is what makes the list worth publishing rather than keeping in a check script.

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 population nobody chose

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

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.

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 this collection has 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.

Every generator · The flat-folding field · The patterns a reader can fold