The difficulty was in the coin

A lettering of a crease pattern is consistent when the statements it makes about which panel lies above which do not contradict one another. A circle in those statements is a proof that the pattern has no flat folded state with the letters it is carrying, and it costs one pass over the crease list to look for.

That test can be applied while the letters are being chosen rather than after they have all been chosen, and doing so turns a sampler into a search. The rhombille tessellation patch — a hundred and fifty-seven panels, two hundred and eighty-two creases, and not one consistent lettering in two thousand random draws — gave one up in five hundred and sixty-one steps to a search arranged that way.

It also gave up a number that looked like a fact about the patch. Run the same search again from a different starting seed and it costs something else entirely: eighty-six steps on a good day, two and a half thousand at the median, and past thirty thousand on a bad one, with a quarter of the runs not finishing at all.

That spread is what a hard instance looks like, and this is not one. The whole of it comes from a single line.

Two choices, and only one of them was ever examined #

A backtracking search makes two decisions at every node, and they are entirely different decisions.

The first is which variable to decide next: which crease, of the ones the conditions have not already settled, to write a letter on. There is a standard answer to that — take the vertex with the fewest labellings still available, so that a contradiction surfaces close to the decision that caused it — and the search uses it, deliberately, with a comment beside it explaining why.

The second is which value to try first: having picked a crease, whether to write a mountain on it or a valley. And that one was a coin toss.

The coin was not carelessness. It was there for a stated purpose: twenty seeds were wanted to produce twenty different letterings, so that a witness would not look like the only one the pattern had. Without randomness somewhere in the search, twenty seeds produce one lettering twenty times over, and a reader shown a single consistent lettering has no way to tell a rich solution set from a lonely one.

So a coin went into the value choice, because that is the cheapest place to put one and because nothing about it looked like it could matter. The variable order is where the literature says the cost lives. The value order is a tie-break.

What happens when the coin is replaced with a constant #

Replace it with the crudest thing available — try a valley first at every node, on every pattern, always — and the patch settles in eighty steps. Not eighty on average. Eighty on every seed, because a search with no coin in it has nothing left to vary and every run is the same run.

Eighty against a median of two hundred and fifty is a factor of three, which is worth having and is not the point. The point is the fifteen thousand eight hundred and seventy-two, and the fifteen runs of forty that did not finish at all. Those are gone. There is no tail, because there is no distribution: the search takes one path and the path is short.

The comparison is exact in a way that comparisons of search strategies usually are not. Same pattern. Same vertex conditions, computed by the same code. Same test for a circle in the arcs, applied at the same nodes. Same rule for choosing which crease to decide. The only difference is which of two letters is written first, and the whole of the spread lives there.

Why a letter can cost that much #

It is worth being clear about the mechanism, because “the value order matters” is the kind of sentence that sounds like a rule of thumb and is here a statement about one shape.

The vertex conditions propagate. Writing a letter on one crease often forces letters on several others, those force more, and a single decision can settle a quarter of the sheet before the propagation stops deciding anything. That is what makes the search cheap when it works: most creases are never chosen at all, they are deduced.

It is also what makes a wrong first letter expensive. A decision that propagates widely and is wrong does not produce a contradiction where it was taken. It produces one somewhere on the far side of everything it forced, after the search has gone on to take a dozen further decisions inside the region it has committed to — and unwinding it means unwinding all of them. On a patch whose vertices are alike, the propagation is short and local and a wrong letter costs a few steps. On the rhombille, where the side distances differ from vertex to vertex and the propagation runs further, a wrong letter can commit the search to a region with no consistent lettering in it and several thousand steps of patient exploration inside that region before it comes back out.

A coin takes that decision at random. A constant takes it the same way every time, and on this family it happens to take it the right way — not because valleys are special, but because the pattern’s own geometry makes one of the two commitments survivable and the other not.

The distribution was the instrument’s #

This is worth being blunt about, because the collection has a measurement standing on the other side of it. The tail was fitted, priced and reasoned about: stopping early and starting again costs five hundred and twelve steps in expectation against sixteen thousand for patience, and the curve rises monotonically with no interior optimum. Every one of those numbers is right.

They are right about a distribution the search manufactured. A run-time distribution requires runs that differ, runs differ only if the search has a coin in it, and the coin was in the one place where it changes everything. Take it out and there is no distribution to fit — one run, one cost, no variance to price a strategy against.

There is a sharper way to say it. A restart strategy reseeds a search that has taken a bad first decision. A search with no seed in it cannot be restarted — restarting it produces the identical run — so the strategy is not merely unnecessary here, it is undefined. The cure and the disease arrive in the same package, and the package was borrowed whole from somewhere else.

The tail had no mean #

The distribution the coin manufactured is worth characterising rather than described, because the character explains why the restart analysis was the right medicine for a self-inflicted illness.

Forty runs, a median of about two thousand five hundred steps, and fifteen of the forty — 37.5 per cent — still going at twenty thousand. Fit the simplest heavy-tailed form, $P(T > t) \propto t^{-\alpha}$, to those two points: halving at 2,500 and surviving to 20,000 at 0.375 gives

$$8^{-\alpha} = 0.75 \quad\Longrightarrow\quad \alpha \approx 0.14$$

That number is rough — forty runs, fifteen censored — and the conclusion it supports is not. For the mean to exist at all, $\alpha$ must exceed one, which would require the survival to fall from a half at 2,500 to an eighth at 20,000. It falls to three quarters.

So the expected running time of the randomised search does not exist. Not “is large”: is undefined, in the sense that averaging more runs makes the average grow rather than settle.

Which makes two of the reported numbers incomparable #

That has a consequence for how the earlier measurement should be read, and it is sharper than the essay’s own correction.

A median of 2,500 and an expected cost of 16,000 for patience are not two summaries of one quantity. The median is a real statistic of the distribution; the expectation is an artefact of the twenty-thousand-step cutoff, and moving the cutoff moves it without bound. Quoting them side by side invites a comparison the distribution cannot support.

It also explains why the restart strategy came out so far ahead. Cutting a heavy-tailed search off and restarting is the textbook remedy for exactly $\alpha < 1$ — it converts a distribution with no mean into a geometric one, which has a mean by construction. The analysis was correct, the remedy was the right remedy, and both were addressed to an illness the search had given itself in its value-ordering line.

So the three numbers survive in different conditions. The 512 is right as an answer about restarts under this distribution. The 16,000 is a truncation artefact. And the whole distribution is an instrument reading, which is what the constant order proves by having none: eighty steps, every time, a point mass with a mean and a median that agree because there is nothing else for them to be.

What the coin was buying, which was not nothing #

A constant order is cheaper and it is also poorer, and the second half is easy to leave out of a comparison that only measures cost.

Forty seeds under the coin returned forty distinct letterings. Forty seeds under a constant returned one, forty times. That is the trade, stated as a trade: three orders of magnitude of worst-case cost against every witness but one.

The obvious compromise does not work. Spending the seed only on the creases that no vertex constrains — creases genuinely free by construction, where a coin cannot lead the search anywhere — costs exactly what the constant costs and returns four distinct letterings of twenty on two of the five patches and one on the other three. The diversity is not sitting in the free creases. It is in the branch decisions, which is precisely where it is expensive, and there is no arrangement here that has both.

A collection that wants many witnesses and a cheap search has to ask for them separately: run the constant order once to establish that the pattern has a lettering at all, and then, knowing the answer is yes, spend a randomised budget on collecting different ones.

The order does not matter anywhere else #

The natural worry about a finding like this is that it is about one pattern, and it very nearly is.

Across the grids, the crumples, the leaf patterns, the fold-and-cut patterns and the four corrugation families, a constant order costs one step per panel and no backtracking at all. The coin costs one step per panel and a handful. Neither arrangement has a tail on any of them and there is nothing to choose between the two.

Across ninety-six twist tessellation patches drawn over a grid of tiling, turn angle and pleat width, the coin costs twenty-five to fifty-six steps and the constant twenty-one to forty-seven. Again nothing.

The tail lives on the rhombille and nowhere else, and the rhombille is not an arbitrary member of the family. It is the one tiling of the five whose vertices are not all alike, which means the matching condition that gives every vertex its own side distance has something to propagate there and nothing to propagate on the others. Cutting a patch out of the plane is where that construction is set out; the consequence here is that the one family whose letters are hard to choose is the one family whose distances had to be solved rather than assumed.

Why the structure does not rescue the other choice #

If the difficulty is in the value order, the tempting move is to attack the variable order harder — to use the pattern’s structure to pick better creases to branch on rather than better letters to try.

A circle in the arcs has to run round a circuit of the panel graph, so the creases lying on many circuits are the creases most likely to be involved in a contradiction. Branching on those first is the improvement anybody would try, the structure is perfectly real, and it is computed here from a spanning tree in a few milliseconds.

It buys nothing. On the eighty-seven patches of the uniform grid that have a lettering, branching on the circuits is never cheaper than the standard rule and is worse on fifty-two of them. On the triangular patch it turns a worst case of fifty-one steps into two thousand three hundred and ninety-four. Which of the two choices the cost lives in takes that measurement apart, and the short version is that the structural rule is answering a different question from the one being asked.

Which theorem was checked, and how #

Nothing above is a claim about flat-foldability. The arcs are a necessary condition on a lettering and no more: no circle means the letters do not contradict one another, and the two non-crossing rules can still refuse every ordering of the panels afterwards. Four of six quadrilateral meshes are exactly that case — the letters agree and no stacking exists.

What is checked is the witness. Every lettering counted in any figure here has been written back onto the pattern and put past two instruments that did not find it: the four conditions at every one of the patch’s hundred and twenty-six interior vertices, and a folded sheet rebuilt from the coordinates and walked for a circle. A witness the search believes and those two do not would be a defect in the search rather than a result, and the check is there because that is the part of the arrangement most able to be quietly wrong.

What the picture cannot show #

A step is not a unit of work. Each node of the search runs the vertex conditions to a fixed point and then tests the arcs, and both of those cost more on a large pattern than on a small one — so a count of steps is a count of decisions rather than of seconds, and two patterns with the same count can differ by a factor in wall-clock time. Every comparison here is between two arrangements on the same pattern, which is what makes the step count a fair measure of the difference; comparing step counts across patterns of different sizes, as the ladder figure does, is a weaker statement and is drawn against panels for that reason.

Nor is a constant order guaranteed to be good. It is guaranteed to be deterministic, which removes the variance, and on every pattern measured here it also happens to be at least as cheap as the coin’s best run. There is no theorem behind the second half. A pattern on which trying a valley first walks into a large fruitless subtree and has to back out of it is perfectly imaginable; none has turned up, and the honest statement is that none has turned up rather than that none exists.

What this corrects in the collection’s own record #

The essay that reported the tail said the search’s cost had a heavy tail and left the mechanism open. The mechanism is now closed and it is unflattering: the instrument was producing the phenomenon it was measuring.

The three sentences that need reading differently are the ones about the rhombille’s cost being evidence of anything about the rhombille. Its cost under a randomised value order is evidence about a randomised value order. What survives is the comparison, which was always between patches measured the same way — the rhombille really is the one of the five that is different, and the difference really does show up as search cost. What does not survive is any reading in which twenty thousand steps is a property of the pattern.

Where the ladder goes next #

Two directions, and one of them turns the finding around completely. Swapping every letter on the sheet at once shows why the two constant orders cost exactly the same and cannot do otherwise, which is the only reason a single constant is safe to recommend. And the order that decides a negative is where the variable choice comes back: it does nothing for a search that finds something, and on a search that finds nothing it is worth four orders of magnitude in whichever direction the pattern happens to decide.