One witness or forty

A crease pattern that folds flat usually folds flat in more than one way. The layer census counts how many, and the answer is rarely one — a pattern with a single folded state is a special object rather than a typical one, and a reader shown one folded state has been shown a sample rather than the answer.

So when a search returns a lettering, the honest next question is how much of the answer that lettering is. A search that returns one lettering, always, has told a reader that at least one exists. A search that returns a different one every time has told them something considerably stronger, and the difference between those two situations turns out to have a price attached.

Forty seeds, forty answers #

The search as it was first arranged decides which letter to try first by a coin toss. Run it forty times from forty seeds and it returns forty letterings, all distinct, all verified.

That is a substantial thing to be handed. It rules out the reading in which the pattern has essentially one consistent lettering that the search happened to find; it gives a reader forty objects to compare; and it makes the distance between a found lettering and the construction’s own into a distribution rather than a single number. Every one of those uses depends on the answers differing.

It also costs, on the one patch where the coin matters, a median of two hundred and fifty steps against eighty, a worst run of fifteen thousand eight hundred and seventy-two, and fifteen runs of forty that do not finish at all inside a budget of twenty thousand. The tail belongs to the coin and the coin is what produces the forty.

One seed, one answer, forty times #

Replace the coin with a constant and the search becomes deterministic. Every run takes the same path, visits the same eighty nodes and returns the same lettering, and forty seeds return it forty times.

There is no partial credit here. A deterministic search does not return few answers; it returns one, and the number of seeds is irrelevant because nothing in the search reads a seed. The forty runs are not forty samples with high agreement — they are one run, performed forty times, and reporting them as forty is the kind of arithmetic that makes a measurement look better than it is.

So the trade is stated plainly: three orders of magnitude of worst-case cost against thirty-nine of forty witnesses. Neither side of it is negligible and neither side is obviously the one to take.

What a witness is for, which decides how many are wanted #

Before pricing the trade it is worth asking what the extra witnesses are actually used for, because the answer is not “reassurance” and the uses are unlike one another.

The first is existence, and it needs exactly one. A single verified lettering settles whether the pattern has one, and a second adds nothing to that question. This is the use that motivated the search in the first place: two thousand random draws had produced none and the question was whether the set was empty or merely thin.

The second is structure, and it needs many. How far apart are two consistent letterings? Do they agree on the buried creases and differ on the rim, or the other way round? Is the set connected under local moves, or does it fall into pieces nothing can walk between? Every one of those is a question about the set, and a single member answers none of them.

The third is honesty about the first, and it is the awkward one. A reader shown one lettering and told a pattern has one is being asked to take the search’s word for the difference between “at least one” and “exactly one” — and those are wildly different facts about a crease pattern, with the second being far more interesting and far rarer. Forty distinct answers settle it immediately; one answer leaves it open, and leaving it open is a cost even though nothing false has been said.

The compromise that ought to work #

There is an obvious middle. Not every decision a search makes is a real decision.

A crease with an interior vertex at each end is buried: every one of its letters is entangled with the labellings of two vertices, and choosing it is a genuine commitment. A crease with an end on the boundary of the sheet, meeting no interior vertex that constrains it, is not. Its letter is free by construction — the conditions say nothing about it, the propagation never touches it, and both values are always available.

Spending the coin only on those and taking a constant everywhere else looks like the best of both. The branch decisions, where a wrong guess is expensive, become deterministic. The free creases, where a coin cannot lead the search anywhere at all, stay random. Cost should collapse to the constant’s and variety should be preserved.

Half of it works. The cost does collapse — the compromise costs exactly what the constant costs, node for node, on every patch measured.

The other half does not. Twenty runs return four distinct letterings on two of the five patches and one on the other three.

Where the variety actually was #

The reason is not subtle once the number is in front of one, and it is invisible before.

A patch’s free creases are few. Most creases on a tessellation patch run between two interior vertices, and the ones that do not are on the rim — and the rim’s creases are largely settled by propagation anyway, because a vertex just inside the boundary forces the letters of the creases leaving it. What remains genuinely free after propagation is a handful, and on three of the five patches it is none at all.

Meanwhile the branch decisions are numerous and each one changes the lettering everywhere downstream of it. A single different choice at a branch propagates into dozens of different letters, which is why forty seeds produce forty very different letterings rather than forty near-copies. The variety is not distributed evenly across the search’s choices. It is concentrated entirely in the ones that cost.

That is a general shape and it is worth naming, because the intuition it defeats is a common one. The decisions a search can afford to randomise are exactly the decisions that do not matter, and decisions that do not matter do not produce different answers. A coin bought variety here because it was placed where the search could be misled, and there is no way to keep the variety without keeping the risk.

There is a tidy way to state the general form. A search’s decisions can be sorted by how much of the answer each one determines, and randomising a decision buys variety in proportion to how much it determines while costing risk in the same proportion. The two are the same quantity read twice. So there is no free variety anywhere in a search — the only decisions that are safe to randomise are the ones whose randomisation nobody would notice.

That is a slightly bleak reading and it has an escape, which is that the cost and the benefit are only tied together within one run. Across runs they come apart completely, and the next section is about how.

Forty with no repeat bounds the set at a thousand #

The forty distinct letterings are worth more than a count of forty, and the extra comes from a fact the essay records without using: no two of them were the same.

Draw $k$ members at random from a set of size $N$ and the chance of no collision is about $e^{-k^{2}/2N}$. Forty draws with no repeat, at even odds, requires

$$N \gtrsim \frac{k^{2}}{2\ln 2} \approx 1{,}150$$

So the absence of a single repeat in forty runs is evidence that the pattern has on the order of a thousand consistent letterings, not forty — and after halving for mirror pairs, some hundreds of genuinely different foldings.

That is a considerably stronger statement than the lower bound of forty the count supplies, and it costs nothing: the same forty runs, read for what did not happen.

Which changes what the variety was worth #

It also reprices the trade, in the direction of the coin.

Under a restart strategy a witness costs about five hundred and twelve steps, against eighty for the deterministic run that settles existence. Forty witnesses is therefore twenty thousand steps — two hundred and fifty times the cost of the existence question.

What that bought is not forty objects. It is an order-of-magnitude estimate of the size of a set with a thousand members in it, which no amount of running the deterministic search would have produced at any cost, because a deterministic search returns the same lettering however long it is run.

So the coin’s product is not a handful of examples but a measurement of a set, and the measurement’s precision improves as the square of the number of draws. Eighty draws with no repeat would push the bound to four and a half thousand; a hundred and sixty, to eighteen thousand.

And it says when to stop drawing #

The same arithmetic gives a stopping rule, which the essay leaves open.

Draws are worth taking until a repeat appears, because until then each one raises the lower bound quadratically and confirms the sampler is still finding new territory. The first collision is the signal: it converts the lower bound into an estimate, since $N \approx k^{2}/2$ at the draw where a repeat first occurs.

At a thousand members that is expected around the forty-fifth draw. So the forty runs stopped almost exactly where the information was about to change character — which is luck rather than design, and a good argument for running sixty.

Two ways to get both, and what each costs #

The trade is unavoidable in one run. It is entirely avoidable across two.

The first way is to ask the questions separately. Run the constant order once to establish that a lettering exists at all — eighty steps, deterministic, no tail — and then, knowing the answer is yes, spend a randomised budget on collecting different ones. The randomised runs no longer have to worry about not finishing, because the existence question is already answered and a run that hits its budget can simply be discarded. The heavy tail is still there; it has stopped mattering.

The second is to enumerate rather than sample. The search can be asked for every lettering rather than one, and on a small pattern that is the right answer: the layer census does exactly this and returns an exact count instead of a sample. On a patch of two hundred and eighty-two creases it is not available — the admissible letterings are more numerous than anything in this collection has a name for — which is why sampling exists in the first place.

There is a third route which is worth mentioning and rejecting. A deterministic search can be made to produce different answers by perturbing the pattern rather than the search — nudging a sector angle, moving a boundary — and collecting the letterings of the neighbours. That works and it answers a different question: it reports the letterings of a family of patterns rather than of one, and on a family whose members can lose their letterings entirely as one sector crosses sixty degrees the two are not interchangeable. A collection that wanted forty letterings and got forty nearly-the-same-pattern letterings would have quietly changed its object.

The count that was always even #

Naming the trade also corrects the count on the variety side, downward.

Swapping every letter on the sheet at once maps a consistent lettering to a consistent lettering, so every witness has a mirror partner and the number of them is even. Forty distinct letterings are therefore at most twenty genuinely different foldings, each available from either side of the paper — and possibly fewer still, since two letterings can differ and produce the same stack of panels.

That does not make the forty worthless. A mirror pair is two different pieces of information about the pattern’s rim, its buried creases and its distance from the construction’s own lettering, and both are needed if the distance is going to be a distribution. It does mean the honest headline is “at most twenty foldings” rather than “forty letterings”, and the collection had been quoting the second.

What it looks like on the other four patches #

The rhombille is where the trade is dramatic. On the other four printed patches it barely exists, and the reason is instructive rather than dull.

There the coin still returns twenty distinct letterings from twenty seeds, and it costs thirty-nine to forty-nine steps against the constant’s thirty-nine. The variety is free. Nobody would take the constant order on that patch for any reason at all, and the whole argument of this essay evaporates.

So the trade is not a property of the search. It is a property of the pattern the search is pointed at, and specifically of whether the pattern is one whose propagation runs far enough for a wrong guess to be expensive. Four patches say the coin is free; one says it costs three orders of magnitude; and a rule chosen from either group alone is a rule chosen from a sample of the wrong thing.

Which theorem was checked, and how #

Every lettering counted anywhere above has been put back past the two instruments that did not produce it. The four conditions at every interior vertex are checked by the pattern’s own reader, and a folded sheet is rebuilt from the coordinates and walked for a circle. A lettering the search believes and those two do not is a defect rather than a witness, and the check exists because the part of this arrangement most able to be quietly wrong is the bookkeeping that matches a folded crease to the crease it came from.

Distinctness is checked as strings of letters, which is the weakest available reading and deliberately so. Two letterings that differ on one crease count as two, even where they fold to the same stack — so every count of witnesses here is an upper bound on the number of distinct folded objects, and the essay’s argument only ever needs the bound in that direction.

What the picture cannot show #

It cannot show whether forty is a large or a small share of what exists. The number of consistent letterings of the rhombille patch is unknown and is not small; forty is a sample from it, and no figure here says whether the sample is representative or clustered. That question is exactly the one the sampler was built to answer and cannot, because measuring a share requires reaching a set whose size is unknown.

Nor does the compromise’s failure generalise beyond patterns whose free creases are few. A pattern with a large unconstrained boundary — a small patch cut out of a large sheet, or one whose interior vertices are sparse — would have room for the compromise to work, and none of the five printed patches is that. The measured statement is about these; the argument for why is about the ratio of free creases to branched ones, and that ratio is a property of a pattern rather than a law.

The habit this leaves behind #

The practical residue is a question to ask of any measurement that comes out of a randomised procedure here, and it is not the usual one about seeds and reproducibility.

The usual question is would a different seed give a different answer, and the collection already answers it by publishing every seed it uses. The question this essay adds is what is the randomness for — and the two have entirely different consequences. A seed that is published and pointless is harmless. A seed that is published and load-bearing is a measurement that will be misread the moment somebody removes it for a good reason.

Here the randomness had a purpose, the purpose was variety, and the variety was worth having. What made it a problem was that the cost was never priced against it, because nobody had noticed there was a choice being made at all. A coin toss inside a search does not announce itself as a design decision; it looks like an implementation detail, and the whole of a heavy-tailed run-time distribution came out of one.

Where the ladder goes next #

The trade is one instance of a shape that recurs: an instrument’s convenience and its cost pulling in opposite directions, with neither visible from inside the other. Restarting a search that cannot be restarted is the same pair seen from the cost side, and it is where the strategy that was priced against the coin’s tail has to be reconsidered — because a deterministic search has nothing to reseed.