The lettering nobody could draw

A crease pattern’s letters say more than which way each fold goes. Every crease also states which of the two panels it joins ends up above the other, and a circle in those statements is a proof that the pattern has no flat folded state with the letters it is carrying.

Because that proof costs one pass over the crease list, it can be run on patterns nothing else here can touch — and running it two hundred times on each of five tessellation patches produced the collection’s least satisfying number. Twenty-six of two hundred letterings agree with themselves on the smallest patch, five on the next, two on the third, and none at all on the last two.

The essay that reported it said what a nought of two hundred draws is worth, which is nothing: a nought there is a nought of two hundred draws and not a proof. It left the question open on purpose.

It has an answer, and the answer is yes.

Why two hundred draws could not settle it #

The draws are not random letters. Writing random letters on a patch this size and testing them would succeed about once in every four million attempts, because a lettering has to pass four conditions at each of a hundred and twenty-six interior vertices before it is even a candidate. What is drawn instead is a solution: propagate the vertex conditions until they stop deciding anything, branch on a crease where they have stopped, and take the branch at random. Every draw is a lettering that passes every condition everywhere, and two draws differ because the decisions differed.

That is a sampler over the admissible letterings, and it measures a density: what share of them agree with themselves. It is the right instrument for the question it was asked, and it is the wrong instrument entirely for the question it was left with, because a set can be non-empty at any density at all.

The difference is not subtle at this size. A patch of two hundred and eighty-two creases has, at the loosest count, more admissible letterings than anything in this collection has a name for; a share of one in ten thousand of that is still an enormous number of letterings, and no number of draws in the hundreds will meet one.

The triangular patch is the useful case here, because it demonstrates the failure without any argument being needed. At two hundred draws it looked exactly like the rhombille — a nought, a shrug, an open question. At two thousand it turns out to have a share of about one in four hundred, which is not rare at all; two hundred draws simply missed it, as they should be expected to about six times in ten.

So one of the two noughts was a sampling accident. The other one is not, and the sampler cannot tell them apart, which is the whole problem with using it for this.

Testing the arcs during the choice #

The change that settles it is not a cleverer sampler and not more draws. It is a rearrangement, and it turns on a fact about folded states that is easy to miss because it is so ordinary.

Where the panels go does not depend on the letters. A flat folded state places each panel by reflecting it across the creases along a path back to some fixed panel, and a reflection does not ask whether the crease it reflects across is a mountain or a valley. So the folded positions of the panels, which panel each crease joins, and which panels have ended up face down are all settled by the drawing. The letters decide one thing only: which way each arc points.

A lettering, then, is an orientation of a fixed graph, and a lettering that agrees with itself is one whose orientation has no directed circle in it.

That is what makes the test usable during a search rather than only at its end. A partial lettering orients part of the graph, and a circle among the arcs already decided can never be undone by the arcs still to come. So a search may test after every decision, and a decision that closes a circle can be taken back at once, three hundred creases before the end.

The sampler does not do this. It chooses every letter under the vertex conditions alone, arrives at a complete lettering, and only then asks whether the arcs agree. On a patch where most letterings fail, that is a machine for producing failures at full length.

Five hundred and sixty-one steps #

With the test moved inside the choice, the rhombille patch takes five hundred and sixty-one nodes — five hundred and sixty-one points at which a letter was set or taken back — and about forty milliseconds. Two hundred and forty-six of those nodes are backtracks, which is the search meeting a circle and undoing the decision that closed it.

The number is worth sitting with, because it inverts the impression the draws left. On the four smaller patches the search barely searches: twenty-six nodes, thirty-five, forty-one, forty-seven, which is roughly one node per panel and means the propagation simply walked to an answer without ever taking a letter back. The rhombille needs twenty times that, and twenty times almost nothing is still almost nothing.

Whatever made the rhombille hard for the sampler did not make it hard for the search. Those are different quantities, and this pattern is where they separate most sharply.

Checking a witness against the machinery that missed it #

A search that reasons on its own model of a problem can be confidently wrong about it, and the model here is the one piece of new machinery in this argument: the fixed skeleton of arcs, built once, oriented by each candidate lettering. If that skeleton is missing an arc, then a lettering with a contradiction in it looks clean, and the search will cheerfully return one.

It happened, in exactly that shape, on the first attempt. The skeleton matched each folded crease back to the pattern’s crease list by the vertices at its ends, which is correct only when no crease has been cut into pieces by another crease crossing it. On the preliminary base — eight half-creases meeting at a point — seven of the eight arcs failed to match and were quietly dropped, and a graph with one arc in it has no circles. The refusal is now a refusal: an arc that cannot be matched to exactly one crease stops the whole construction rather than being skipped.

That is why every witness is put back through the two instruments that did not produce it. The letters are written onto the pattern, every interior vertex is checked for developability, Kawasaki, Maekawa and the big-little-big lemma, and a folded sheet is rebuilt from scratch and walked for a circle. The rhombille’s witness passes both. So do the witnesses for the other four patches, and for every pattern this collection prints at true scale.

An assertion that has never rejected anything proves nothing, so the check is also run in the arrangement where it must fail. With the arc test switched off, the same search returns the first lettering the vertex conditions allow — and on the rhombille that lettering has a circle in it, which is asserted rather than hoped for. Two arrangements, two different answers, one line of difference between them.

Twenty seeds, twenty letterings #

One witness proves the set is not empty. It says nothing about how large it is, and the search cannot be asked directly: counting the consistent letterings of a pattern with two hundred and eighty-two creases is not a computation anybody is going to run.

What can be done cheaply is to ask again with the decisions taken in a different order. Twenty seeds produce twenty consistent letterings, and no two of them are the same — not merely different in a crease or two, but different letterings of the same patch, each verified.

Twenty is a lower bound and nothing more. It is not an estimate of anything, and dividing it by twenty would be inventing a statistic. What it does establish is that the rhombille is not a knife-edge case with one exotic solution hiding in it; the consistent letterings are there in quantity, and the sampler was walking past them.

How far away the answer was #

The witness and the pattern’s own lettering are not neighbours. The rhombille’s construction hands it a lettering that closes a circle of sixteen panels, and the witness differs from that lettering on a hundred and fifty-five of two hundred and eighty-two creases — more than half the pattern rewritten.

This is the part that explains, after the fact, why the question felt like a question about repair. Every earlier attempt on this patch was an attempt to fix the lettering it arrived with — cut a crease, flip a pair, find the smallest edit that clears the circle — and none of those attempts got anywhere. They could not have. The nearest consistent lettering is not near.

That is a fact about the pattern rather than about the attempts, and it has a name in the structure of the lettering space this collection measured earlier: a hundred and seventeen of the hundred and fifty-five creases that have to change are buried — with an interior vertex at each end — and no move that survives the vertex conditions ever changes a buried crease. The patch has two hundred and twenty-two buried creases out of two hundred and eighty-two, which is why almost any two of its letterings are unreachable from one another, and why a twist patch’s letterings fall into so many separate pieces that the number has to be written as a power.

How close the sampler came #

The two thousand draws that returned nothing on the rhombille are worth pricing, because the sampler was not far from succeeding and the arithmetic says how far.

Zero in two thousand bounds the share above: by the ordinary rule for a nought, the share is under three in two thousand, or one in six hundred and seventy, at ninety-five per cent.

Now run it forward. If the share were one in a thousand — comfortably inside that bound — the chance of seeing nothing in two thousand draws is $e^{-2} = 0.135$, and about two thousand three hundred draws would give a nine-in-ten chance of one.

So the sampler may have been within fifteen per cent of the sample size it needed, and stopped. That is a much less comfortable position than the sampler cannot answer this question: on this patch it very nearly could, and there was no way to know from inside.

And what the two instruments cost #

The comparison of effort is the sharper reading, and it is available from the essay’s own numbers.

The search settles the patch in five hundred and sixty-one nodes. Each draw of the sampler propagates the conditions over the whole pattern, which is at least the hundred and fifty-seven panels’ worth of work a single clean run takes.

Two thousand draws is therefore something over three hundred thousand nodes’ equivalent, against the search’s five hundred and sixty-one.

The sampler spent five hundred times the search’s effort and returned nothing, and the difference is one line: whether the arc test runs during the choice or after it.

The witness is as far away as chance #

One more number sharpens the essay’s closing observation about distance.

The witness differs from the construction’s lettering on a hundred and fifty-five of two hundred and eighty-two creases. Two unrelated letterings of the same pattern would be expected to differ on about half of them — a hundred and forty-one — with a spread of eight or so.

A hundred and fifty-five is under two standard deviations from that.

So the found lettering is statistically indistinguishable from an unrelated one. It is not merely not near the drawn lettering; it is as far away as a lettering chosen with no reference to it at all, which is the strongest form of the essay’s point about repair. There was never a small edit to find, because the two solutions share nothing.

What the answer is not #

The arcs are a necessary condition. Nothing else.

A lettering with no circle in its arcs is a lettering whose statements about which panel lies above which can all be satisfied at once. It is not a lettering that folds. The two non-crossing rules — a panel may not lie between a crease’s own two panels, and two folds wrapping the same edge may not interleave — are statements about overlaps, they cannot be read off the crease list, and they can refuse every ordering that the arcs permit.

Four of six quadrilateral meshes are exactly that: their letters agree perfectly and no arrangement of their nine panels avoids passing through itself. The rhombille’s witness is in the same position, and stronger claims about it are not available here. Whether it folds is the general question, and the general question is NP-hard.

The size of that gap is known where it can be counted. On the square twist — nine panels, small enough to enumerate — two hundred and fifty-two of two hundred and fifty-six admissible letterings agree with themselves and eight fold. The arcs account for four of the two hundred and forty-eight failures. Everything else is the non-crossing rules, and nothing cheap sees any of it.

So what has been established is precise and limited. The patch has a lettering whose letters do not contradict one another; that lettering is one of many; it is a long way from the one the construction produces; and finding it costs forty milliseconds, which is less than the collection has spent on any other question about this patch.

The correction this makes to the collection’s own record #

Three sentences elsewhere in this collection now read differently, and they are worth naming because each was written carefully and each was still misleading.

The rhombille patch has no lettering that works was never written; what was written was that two hundred draws found none. Correct, and read by everybody — including whoever wrote the next essay — as though it meant the first thing. The distinction between a measurement and its natural paraphrase does not survive being repeated.

The honest description of that patch is not “it does not fold” but “it folds for one lettering in eight” was written about the square patch and is exactly right. It should have been the model for the others, and the reason it was not is that the square patch’s share is measurable and the rhombille’s is not. A quantity that cannot be measured tends to get replaced by a verdict.

Whether one exists is exactly the question the general problem makes hard is the one that was actually wrong, and it is instructive. The general problem is hard; this question is not the general problem. Deciding whether a lettering exists whose arcs are acyclic is a constraint problem over a fixed graph, and the fixed graph is what makes it cheap. Reaching for the hardness result was reaching past a question that had an easy answer.

There is a general lesson under the particular one, and it is not about paper. The vertex conditions constrain a lettering far less than they appear to — fixing one crease of a hundred and fifty-eight settles three of the rest — so the admissible set is vast and a density measured over it is a poor guide to anything one wants to know. What a search does is ignore the size of the set entirely and walk to a member of it. Where the constraints are loose, that is the cheaper of the two, and the sampler’s difficulty was the loose constraints rather than the pattern.

Where the ladder goes next #

Two things follow immediately, and both are measured in the essays this one leads to.

The first is that the search’s cost is not a property of the pattern alone. Five hundred and sixty-one nodes is what one seed cost; another seed costs eighty-four and another twenty-nine thousand, on the same pattern with the same code, and the distribution has a tail long enough that the right response is to stop and start again rather than to wait.

The second is the question of what the search is actually backtracking on. Two hundred and forty-six of the rhombille’s five hundred and sixty-one nodes were undone, and it is worth knowing which condition did the undoing — because the answer is the same on every patch here, and it is not the condition anybody checks.