Which condition does the refusing

A search for a lettering that folds has to satisfy five things at once. Four of them are the conditions at a vertex that this subject has been checking for two centuries: the angles must go all the way round, they must alternate to zero, the two letter counts must differ by two, and the two creases bounding a strictly smallest sector must carry different letters. The fifth is newer and cheaper — the arcs the letters force must have no circle in them — and it is the only one that is not local.

A search that carries all five will sometimes take a letter back. It is worth asking which of the five makes it do so, because the answer decides where the difficulty in this problem actually lives, and the answer is not the one two centuries of attention would suggest.

Nought is the sort of number that usually means a measurement has failed to happen. It does not here, and the reason it does not is worth setting out before the number is interpreted, because it is a fact about how the conditions are used rather than about how strong they are.

Propagated, not tested #

There are two ways to carry a constraint through a search, and they have completely different failure profiles.

The first is to test: choose everything, then check. A test refuses at the end, having already paid for the whole choice.

The second is to propagate: keep, for every vertex, the list of labellings of its own creases that still satisfy every condition given what has been decided. Whenever one crease’s letter is settled, strike the labellings that disagree from every vertex the crease touches; where a vertex has only one letter left for a crease, write it in and strike again. Repeat until nothing more is decided.

Propagation almost never refuses. It narrows, and narrowing is invisible: a crease whose letter was forced by three vertices agreeing about it never appears in a count of backtracks, because nothing was ever taken back.

So the four conditions are doing an enormous amount of work in these searches. They are simply not doing it in a form that produces a refusal. A vertex would have to run out of labellings entirely — every one of its options struck by the letters already fixed around it — for the propagation to fail, and on these five patches that never once happened.

What that says about the conditions #

It says they are loose, and this collection has measured the looseness twice now from other directions.

Fixing one crease of a hundred and fifty-eight settles three of the remaining hundred and fifty-seven, and no more. The conditions do not chain: knowing one letter tells a vertex almost nothing, and it tells the vertex next door nothing at all. That measurement predicted this one — a constraint system that weak will not corner a search into a dead end.

The other measurement is how many admissible letterings a pattern has. On a tessellation patch the count is a number with tens of digits in it. A search running under those four conditions alone is not really searching; it is walking down a corridor with very wide walls.

That is a strange thing to have to say about a set of conditions the subject has been organised around since the eighteen-seventies. They are not weak in the sense of being nearly satisfied by everything — a random lettering of one of these patches passes them about once in four million. They are weak in the sense that matters to a search: they leave a great many solutions, so a search under them alone never gets stuck.

Every backtrack is the fifth condition #

With the four conditions declining to refuse anything, the whole of the backtracking belongs to the circle test. Across the five patches: one backtrack, three, two, seven, and two hundred and forty-six.

The circle test’s refusals have a shape the four conditions could not produce even in principle, and the shape is the point.

A vertex condition is a statement about one point. If it refuses, there is a place on the sheet to look at, and something local to change. A circle is a statement about a closed chain of panels, which may run right across the sheet: the rhombille patch’s shortest circles are six and eight panels long, and the panels that lie on some circle number ninety-nine of the patch’s hundred and fifty-seven. When that test refuses, there is no point to look at. There is a chain, and every crease on it is equally implicated.

This is the difference between local and global made into a cost. The local conditions are cheap and never bind. The one global condition is also cheap — it is a single walk over the panels — and it is what the whole search is actually against.

The two arrangements, run side by side #

A claim of this kind needs the arrangement in which it fails, so the search is also run with the circle test switched off. Everything else is identical: the same propagation, the same vertex tables, the same seed, the same order of decisions.

With the test off, the search returns the first lettering the four conditions allow. On the rhombille patch that lettering has a circle in it — which is asserted rather than hoped for, because a run in which both arrangements happened to return the same lettering would be a run in which nothing had been shown. With the test on, the same search returns a lettering that has none.

One line of difference, two different answers, and the second one costs two hundred and forty-six backtracks that the first never pays. That is the price of the fifth condition, stated exactly.

What a propagation actually decides #

It is possible to watch the narrowing rather than infer it, and the numbers make the corridor concrete.

Take the rhombille patch at the moment the search begins. Nothing has been decided, so every vertex holds its full table: a degree-six vertex has thirty labellings that pass all four conditions, a degree-three vertex on the tiling’s other class has none of its own to speak of because the pattern’s creases meet there in fours and sixes rather than threes. Propagating from an empty state decides nothing at all — with no letter fixed, no table can be narrowed — so the search’s first act is always a guess.

After that guess the narrowing begins, and it is local and short-ranged. The crease just fixed appears in two vertices’ tables; striking the disagreeing entries usually leaves both vertices with several options still, and only occasionally does a vertex end up agreeing about some other crease, which then gets written in and propagated one step further. The chains of forced letters this produces are two or three creases long. They are never a hundred.

That is the same three-in-a-hundred-and-fifty-eight, seen from inside the search rather than from outside it. And it is why the vertex tables cannot empty: a table only empties when the letters around it have been pinned by something, and nothing here pins anything for long enough.

The grid is a useful control here because it is the case where the four conditions are at their most uniform: every interior vertex is degree four with four right angles, every table is the same eight labellings, and the pattern is as regular as a pattern gets. The narrowing behaves exactly as it does on the patches, and the search behaves exactly as it does on the patches. What changes with size is the number of places a circle could sit, and nothing else.

Why the printed patterns never backtrack #

The shelf is the control, and it comes out clean in a way that is worth explaining rather than merely noting. On all eight printed patterns the search visits exactly one node per panel and takes nothing back.

The reason is not that those patterns are small. The Yoshimura folds to sixty-five panels, which is more than three of the five patches. The reason is that they have few independent closed chains of panels — the quantity that decides how many places a circle could sit — and a pattern with few chains gives the circle test almost nothing to refuse.

A corrugation agrees with itself established that count as the thing that predicts consistency, and it predicts search cost the same way. The Miura has fifteen chains, the Yoshimura twenty-two, a fold-and-cut outline one to three. The patches have between thirty-six and a hundred and twenty-six.

So the pattern is not: small is easy, large is hard. It is: few circuits is easy, and a tessellation patch is circuits all the way across because that is what a tessellation is.

The conditions have radii, and there is a gap at two #

The observation that the circle test is vacuous at one vertex can be turned into a measure, and the measure exposes a hole in the subject’s toolkit.

Give each condition a radius: the number of vertices its statement involves. Developability, the alternating sum, the letter count and the smallest-sector lemma all have radius one — each is evaluated at a single point with no reference to anywhere else.

The circle test has no fixed radius at all. Its statement is about a closed chain of panels, which may enclose any number of vertices, and its smallest non-vacuous case encloses two — six panels, the chain running from one vertex across a shared crease to its neighbour and back.

So the subject’s conditions sit at radius one and at radius unbounded, and there is nothing at radius two. No condition in this collection, and none in the literature it draws on, is stated about a pair of adjacent vertices.

Which is where the commonest failure lives #

That gap matters because of where the circles actually are.

Across every population measured here, the circles that turn up run from six panels to fifty, and six and eight are by far the commonest — six being two adjacent vertices and eight being two or three. The failures are overwhelmingly at the smallest scale the test can speak at, which is exactly the scale nothing else covers.

So a condition at radius two would catch most of what the unbounded test catches, and it would be local: a sweep over adjacent vertex pairs, linear in the pattern, with the same character as the four that already exist. On a patch with a hundred and twenty-six vertices that is a few hundred pairs rather than a walk over every chain.

Nobody has written it, and the reason is visible in the history. The four conditions were found by people asking what a vertex must satisfy, which is a question with an obvious scale attached; the circle test was found by asking what a whole lettering must satisfy, which has no scale at all. Nothing prompted the question in between.

That also predicts what such a condition would be worth. It would not decide the problem — chains of ten, twelve and more exist and would escape it — but it would fire on the majority of failures at a cost the four conditions already pay, and it would restore the property this essay finds missing: a refusal with a place attached, which a chain of fifty panels does not have.

The condition that was never written down #

There is a habit of speech this measurement corrects, and this collection has used it as much as anyone.

The four conditions at a vertex are routinely called the local conditions on flat-foldability, with the implication that a neighbourhood has been fully interrogated. It has not. A neighbourhood could also have been asked whether the panels round this point can be stacked at all — which is a fifth local condition, and a perfectly sensible one to write down.

Nobody wrote it down because the answer is always yes, and it is always yes for a reason: the only lettering that could close the circle round a single vertex is the strict alternation, and Maekawa’s count forbids it at every degree. So the fifth condition, evaluated locally, is vacuous — and everything it has to say has to be said about chains enclosing more than one vertex.

That is exactly what the backtracks in this search are. Every one of them is the fifth condition speaking at the only scale where it has anything to say.

There is a small irony in the arrangement. The condition that produces every refusal is the one that took the least work to state — a crease says which panel is above, collect the statements, look for a circle — and it was written into this collection as an optimisation, a way of refusing a bad pattern without searching its orderings. It turns out to be the substantive constraint, and the four theorems it was added alongside turn out to be the scenery. That is not a criticism of the theorems; a vertex condition that could be violated by a pattern anybody draws would have been noticed in 1870. It is a remark about which conditions are still doing work at the sizes this collection now folds at.

What this does not license #

Two conclusions are available here and a third is not.

It is fair to say that on these patterns the four vertex conditions never dead-end a search, and that the circle test is what the search’s cost is made of. Both are counts.

It is fair to say that the four conditions are doing their work by narrowing rather than by refusing, and that this is why the count is nought rather than small. The propagation is what it is.

It is not fair to conclude that the four conditions are unimportant, and the arithmetic says why. Switch them off and the search is choosing letters at random against the circle test alone, which a random lettering passes far more often than it passes the vertex conditions. What would come back is a lettering with consistent arcs and a vertex that cannot fold — a worse answer, arrived at faster. The conditions are load-bearing precisely because they are propagated: they are the walls of the corridor, and a corridor is not noticed while one is walking down the middle of it.

What the count would look like on a pattern that could fail locally #

The nought is a measurement over five patches, and it is worth asking what would have to be true of a pattern for it to come out otherwise, because that is the difference between a finding and a coincidence.

A vertex table empties when the letters around it are all pinned and none of the surviving combinations agrees with them. For that to happen, the letters would have to be pinned from several directions at once, which needs the propagation to reach further than three creases — and it reaches three creases because the conditions are weak. So the pattern would have to be one whose vertex conditions bind tightly: high degrees, sectors arranged so that the big-little-big lemma applies at nearly every crease, and enough repetition that fixing one letter reaches across the sheet.

Nothing in this collection is like that, and it is not an accident of what has been drawn. The patterns here are corrugations, twists, packings and crumples, and all four are built out of vertices of degree four and six with sectors that make the smallest-sector lemma vacuous or nearly so. A pattern whose local conditions bind hard would be a strange object, and probably one nobody would fold.

So the honest generalisation is narrower than the number looks. On patterns of the kind this subject actually produces, the four conditions do not dead-end a search. On a pattern designed to make them do so, they presumably would, and no such pattern is measured here.

Where the ladder goes next #

The two hundred and forty-six backtracks on the rhombille patch are one seed’s worth. The same search with a different order of decisions costs eighty-four nodes, or twenty-nine thousand, and the distribution of that cost is the next thing worth measuring — because a cost that varies by a factor of three hundred with nothing but the order is a cost that should be managed rather than paid.

And there is a question this measurement leaves open on its own terms. The circle test refuses, and where it refuses there is a chain rather than a point. Whether a search could be told which chain, and use it to jump rather than to backtrack, is a real question about this machinery and one nothing here has asked. The strongly connected components of the arc graph are computed elsewhere in this collection and would answer it. Nothing here uses them for that, and the omission is deliberate rather than an oversight: it would be a different instrument, and this one had a question to settle first.