Rare is not hard

Crumple a sheet of paper, open it out, and the creases left behind are a crease pattern like any other. Its own letters never contradict themselves, at any depth, because they are a record of a folding that actually happened rather than a choice anybody made. Redraw them at random and the guarantee goes: at eight folds, only eleven of forty redrawn labellings agree with themselves.

That falling share looks like a measure of difficulty, and the temptation to read it as one is strong. A pattern where three-quarters of the candidates fail sounds like a pattern where finding a good one is work.

It is not, and the crumple is the cleanest case in this collection for seeing why.

The two columns #

At four folds the crumple has sixteen panels and twenty-four creases. Thirty-four of forty random labellings agree with themselves, and the search finds one in seventeen steps with a single backtrack.

At eight folds it has seventy-one panels and a hundred and twenty-seven creases. Eleven of forty random labellings agree, and the search finds one in seventy-two steps with two backtracks.

The share has fallen by two-thirds. The cost per panel has gone from 1.06 to 1.01.

Between them the ladder is monotonic in the first quantity and flat in the second. Six folds: thirty-five panels, fifteen of forty agreeing, thirty-four steps, no backtracks at all. Seven folds: thirty-nine panels, nineteen of forty, thirty-eight steps, no backtracks.

A search that visits one node per panel has not searched. It has made one decision per panel, propagated the consequences, and arrived. Whatever is making three-quarters of the random labellings fail at eight folds is not making the search work harder, because the search is not choosing at random.

Why the share falls #

The share falls for a reason this collection has already established and which has nothing to do with cost.

A labelling contradicts itself when the arcs its letters force close a circle, and a circle needs a closed chain of panels to run round. So the number of places a contradiction could sit is the number of independent closed chains, which is the crease count less the panel count plus one — and on this ladder it goes fifteen, twenty-two, forty-two, forty-nine, ninety-two as the folds deepen.

More chains is more chances for one of them to close. That is the same account that orders the tessellation patches and the corrugations, and it predicts the falling share here as well as it predicts theirs.

Why the cost does not rise #

The share is a property of the set of labellings — what fraction of it is good. The cost is a property of a walk — how long a directed procedure takes to reach a member of the good part.

Those are related but not the same, and the relation is loose enough to break. A set can be sparse and easy to walk into if the walk is steered by the same constraint that makes the set sparse, which is exactly what the search does: it tests the arcs at every step, so it never enters the bad region in the first place.

The sampler, by contrast, chooses letters under the vertex conditions alone and tests the arcs at the end. It walks into the bad region three times in four at eight folds and then discovers it. That is why its success rate tracks the share and the search’s cost does not.

The count that does move #

There is a third column worth putting beside the other two, because it is the one that behaves as the intuition expects and it shows what the intuition was actually tracking.

The panel count rises steadily along the ladder: sixteen, eighteen, thirty-five, thirty-nine, seventy-one. So does the crease count: twenty-four, twenty-seven, fifty-eight, sixty-five, a hundred and twenty-seven. And so does the number of independent chains.

The search’s node count rises with them, exactly, because the search does one thing per panel. What does not rise is the number of backtracks — one, one, none, none, two — and the backtracks are where a search’s difficulty lives.

So the honest decomposition is: cost equals decisions plus revisions. The decisions grow with the pattern, which is unavoidable and uninteresting. The revisions are the difficulty, and on a crumple there are essentially none at any depth.

That is also why the tessellation patches look so different in the same units. The rhombille patch’s two hundred and forty-six backtracks at one seed and thousands at others are all revision, on a pattern with a hundred and fifty-seven panels — twice the deepest crumple’s, and a hundred times the revisions.

Cost is panels plus revisions, exactly #

The decomposition the essay proposes — decisions plus revisions — is not a framing. It is an identity that the ladder’s own numbers satisfy to within one step.

At four folds: sixteen panels, one backtrack, seventeen steps. At six: thirty-five panels, no backtracks, thirty-four steps. At seven: thirty-nine panels, none, thirty-eight. At eight: seventy-one panels, two backtracks, seventy-two steps.

$$\text{steps} \;=\; \text{panels} + \text{backtracks}$$

to within a single step at every rung. Every node the search visits is either a fresh decision — one per panel — or a revision, and there is nothing else in the count.

That makes the flat curve an arithmetic consequence rather than an observation. The cost per panel cannot rise unless the backtracks do, and on this ladder the backtracks are one, one, none, none and two while the panel count more than quadruples.

Which is what a share cannot see #

Set the same identity against the rhombille patch and the comparison sharpens.

That patch has a hundred and fifty-seven panels — twice the deepest crumple’s — and backtracks two hundred and forty-six times at one seed and thousands at others. Its cost is therefore almost entirely revision, where the crumple’s is almost entirely decision.

Two patterns of comparable size, one whose steps are ninety-nine per cent panels and one whose steps are ninety-nine per cent revisions. A share of consistent labellings does not distinguish them and cannot: it is measured on the set, and the split between decision and revision is a property of the walk.

So the essay’s correction can be put arithmetically. A share predicts how often a random labelling lands in the good part of the set. The backtrack count measures how often a steered walk has to come back out of the bad part. The first is a fact about the set’s density; the second is a fact about whether the steering works, and on a crumple it works perfectly at every depth.

One caution on the chain counts quoted above. The essay derives them as the crease count less the panel count plus one, and that formula does not reproduce the numbers it is attached to — twenty-four creases and sixteen panels give nine rather than fifteen. The falling trend is not in doubt and the individual figures want re-deriving before anything is fitted to them.

What makes a crumple easy #

The crumple is at the easy end of everything this collection searches, and the reason is worth naming because it is not the reason one would guess.

It is not that a crumple is small. At eight folds it has seventy-one panels — more than three of the five tessellation patches — and a hundred and twenty-seven creases.

It is not that it has few chains. Ninety-two independent chains is more than the square patch’s thirty-six and more than the hexagonal patch’s fifty-four, both of which the search handles in about forty steps. Nor is it that a crumple’s creases are somehow gentler: a crumple’s own pattern passes every condition the subject has, so it is a crease pattern in exactly the sense a designed one is.

What makes it easy is that its chains are short and separate. A crumple’s creases run mostly edge to edge, so its panels are large and its chains enclose one or two vertices each; and the folding that made it laid its creases down in sequence, so the pattern has a layered structure rather than a woven one. A tessellation patch is the opposite: its chains are the twist polygons and the pleats between them, they interlock everywhere, and a choice made at one polygon reaches three polygons away.

That distinction is not measured here — nothing in this collection measures how much chains overlap — and it is offered as the explanation the numbers are consistent with rather than as a result.

The instrument’s own limit, met once #

One number in the ladder is not the search’s. At the deepest crumples the sampler occasionally gives up: its propagation runs past its step budget and refuses to return a labelling at all, which is a refusal rather than a verdict.

That is the right behaviour and it is worth saying why. A propagation that runs out of budget has established nothing — not that no labelling exists, not that one is hard to find, only that the procedure ran long. Reporting it as no labelling would be the exact failure this collection has spent a good deal of effort warning about, and the sampler refuses instead.

On the crumple ladder here it does not fire; every depth returns forty labellings. It fires on a tessellation patch at a shallow turn, where the propagation chains further than on anything else measured.

The same sheet, at its own letters #

There is a control sitting inside this ladder that is easy to overlook, and it is the strongest part of the comparison.

Every crumple on it is consistent as drawn. The letters the folding gave it close no circle at any depth, and that is not a measurement so much as a consequence: a lettering derived from a folding that happened has a folded state by construction, so it cannot demand an impossible order of its layers.

So the falling share is entirely a fact about redrawing. The pattern is the same object at both ends of the arrow — same creases, same panels, same chains — and the two letterings on it are a record and a guess.

That is worth holding beside the search result, because the two together say something neither says alone. A crumple has an answer for free — its own — and the search finds a different answer at about the same price, and a random draw finds one three times in four at eight folds. Three procedures, three costs, one set of labellings.

What would break the pattern #

It is worth asking what a crumple would have to look like for the cost to rise, since a flat curve is only informative if something could have bent it.

The search’s cost is decisions plus revisions, and a revision happens when a partial labelling closes a circle. For that to become common, the chains would have to interlock: a decision on one crease would have to reach, through the propagation, into several chains at once, so that a choice made early forces a contradiction later.

That is exactly what a tessellation patch does and what a crumple does not. A crumple’s creases are laid down in sequence and its panels are large, so a decision’s consequences stay local; a patch’s twist polygons share pleats with their neighbours in every direction, and a decision at one polygon constrains three polygons away.

So the flat curve is a statement about a kind of pattern rather than about crumples in particular, and the kind is characterised by how much its chains overlap. Nothing here measures that quantity, which is why the sentence above is an explanation rather than a result.

What a folder would notice #

There is a version of this available to anyone with a sheet of paper, and it is worth stating because it is one of the few places where the combinatorics and the hands agree exactly.

Crumple a sheet, open it, and fold it flat again along the same creases, choosing which way each one goes as it is reached. It works, easily, and it works whatever the early choices were — the paper accommodates. That is the search: local decisions, propagated, no backtracking.

Now decide the whole thing in advance instead — mark every crease mountain or valley on the flat sheet, then collapse. At eight folds that is wrong three times in four, and the failure does not appear until the sheet is nearly closed. That is the sampler.

The paper is the same paper. The difference is entirely in when the decisions are checked, and it is the same difference the node counts measure.

The control that makes the comparison mean something #

A ladder that only ever behaves one way is a ladder that has shown nothing, so it is worth naming what the crumple is being compared against and why the comparison is fair.

The crumples and the tessellation patches are measured by the same instrument, with the same node definition, the same propagation and the same seeded stream deciding the branches. The only difference is the pattern handed in.

They are also comparable in size. The deepest crumple has seventy-one panels; the hexagonal patch has seventy-seven and the triangular eighty-three. So when the crumple is searched in seventy-two steps with two backtracks and the rhombille patch takes a hundred and sixty-six steps at the middle run and does not finish at all in two runs of five, that is not a comparison between a small pattern and a large one.

And the crumples span a range of consistency shares that overlaps the patches’. Eleven of forty is about twenty-eight per cent; the square patch is thirteen per cent and the elongated two and a half. So the crumple ladder is not confined to the easy end of the share axis either — it reaches down into the region where the patches sit, and its search cost does not follow.

Both halves are needed. If the crumples were tiny, or if their shares never fell, the ladder would be measuring nothing.

What this changes about reading a share #

Every share this collection reports about a pattern’s labellings is a measurement of one thing: how much of the admissible set survives the arcs. It is a real quantity and it orders patterns sensibly.

What it is not is a measure of difficulty, and three of this collection’s own essays come close to reading it as one. A share of two in two hundred sounds worse than a share of twenty-six in two hundred, and by the only measure that matters to a search — how long until an answer — the two patterns are separated by fifteen steps.

The corrected reading is short. A share says how a random labelling behaves. A node count says how a procedure behaves. Neither predicts the other, and where the collection wants to say a pattern is difficult, the node count is the number to quote.

The one place the two do coincide is the case that motivated all of this: a patch where the share is nought at two thousand draws and the search still finds an answer in five hundred and sixty-one steps. There the share is not merely a poor guide to difficulty; it is not even a guide to existence.

And there is one case where a share of nothing really does mean nothing exists — a patch at a shallow turn whose vertices cannot be satisfied jointly at all — which no share could have distinguished from the first case. Three patterns, three noughts, three completely different situations underneath: a set that is large and rarely sampled, a set that is small and reachable, and an empty set. A share reports the same digit for all three.

Where the ladder goes next #

The obvious continuation is deeper crumples, and it is limited by the sheet rather than by the search. A crumple past about nine folds has panels smaller than a crease is wide, and a crease has a width — so the pattern stops being a description of paper before it stops being computable.

The more interesting question is the one raised by the explanation offered above and not tested. If short, separate chains are what makes a pattern easy to search, then a measure of how much a pattern’s chains overlap ought to predict search cost across families — crumples at one end, tessellation patches at the other, corrugations in between. The machinery to compute chain overlap exists in this collection, pointed at a different question, and nothing has turned it this way.