The loop is not the tangle

A crease pattern’s letters can contradict themselves, and the contradiction is found by walking the arrows the letters force until the walk arrives somewhere it has already been. What comes back is a circle of panels — a list, each of which must lie below the next, closing on itself.

On a square tessellation patch of forty-nine panels the circles that come back are eight to twenty-four panels long, and eight is much the commonest. On a rhombille patch of a hundred and fifty-seven they run from six to fifty. Those numbers invite a reading, and the reading is wrong: that somewhere in the patch a handful of panels have got themselves into a knot, and the rest of the sheet is fine.

What a search returns is not what is wrong #

A depth-first walk stops at the first back edge it meets. Which one that is depends on where the walk started and in what order it took the arrows leaving each panel, and neither of those has anything to do with the pattern. Start the same walk at a different panel and a different circle comes back; the graph has not changed.

So the reported circle is a witness — an existence proof, exhibiting one thing that cannot be ordered — and a witness is not a measurement. The measurement wanted is a different question: which panels lie on some circle?

That question has an exact answer and it is not found by walking. Two panels lie on a common circle exactly when each can be reached from the other by following arrows, and the sets of panels for which that holds are the graph’s strongly connected parts. Panels in a part of size one are on no circle at all; every part larger than one is a region in which every panel is above and below every other, by some route.

Thirty-five panels of forty-nine. Seventy-one per cent of the sheet is in a region where the layer relation has no consistent reading at all, and the search reported eight.

Two readings of one graph #

There is an obvious hazard in measuring a graph two ways and reporting the more alarming number, so the two are required to agree before either is published.

The walk looks for a back edge. The decomposition sorts the panels into parts by mutual reachability. They share no line of code and they are not the same algorithm in different clothes. What must hold, on every lettering drawn from every pattern, is this: where the walk finds a circle, every panel of that circle lies inside one part larger than one; and where the walk finds nothing, no part larger than one exists at all. Both directions are checked, on letterings drawn again rather than on the patterns’ own, because a pattern’s own lettering is consistent and a check that only ever sees the passing case is not a check.

They agree everywhere they have been asked. That is the whole warrant for the shaded figure above, and it is worth being explicit that the warrant is agreement between instruments rather than confidence in either.

The rhombille is instructive for a second reason. Its tangles are three, not one — the contradiction is not even connected — and the largest holds fifty-five panels while the search reported a circle of sixteen. A repair aimed at the reported circle would leave two other tangles untouched and would not have been told they were there.

Because these are letterings drawn again rather than the patch’s own, the right thing to report is a range and not a figure. Over twelve contradictory letterings of each of five patches, the tangle covers between ten and eighty-four per cent of the panels, with a mean between forty-seven per cent on the elongated patch and sixty-seven on the rhombille. The smallest tangles are the ones near the rare consistent letterings; the typical one is half the sheet. What does not vary is the relation between the tangle and the circle the search reports: on no patch, in no draw, was the reported circle as much as the whole tangle once the patch had more than nine panels in it.

How much of the graph is inside #

A third number falls out of the same decomposition and it is the one a repair has to reckon with. Every arrow whose two ends lie in the same tangle is a statement that a repair would have to reach; every arrow with an end outside is already fine. On the square patch that is fifty-two arrows of eighty-four; on the elongated, fifty-nine of a hundred and six; on the hexagonal, seventy-two of a hundred and thirty; on the rhombille, a hundred and forty-six of two hundred and eighty-two.

Between forty and sixty-two per cent of everything the letters say is inside the fault. That is a very different picture from a circle of eight, and it is the picture that decides what any repair costs.

It also puts a floor under the size of a redraw. The pieces the letterings fall into are named by the letters on the creases no local change can reach — the ones with an interior vertex at each end — and on the square patch that is sixty of the eighty-four creases. Fifty-two arrows inside the tangle and sixty creases a local move cannot touch is not a coincidence of two large numbers; it is the same fact from two sides. The letters that are wrong are mostly letters that nothing short of starting again can change.

Which is why nothing small repairs it #

The practical consequence arrives immediately, and it is the reason this measurement is worth making rather than merely interesting.

The smallest change that can remove an arrow from the layer relation looks, at first, like a cut along an existing crease. It removes no paper: the two panels that met along it are still there and still the same size, and the only thing that has changed is that they are no longer joined. One arrow, deleted, at the cost of a knife.

Try every one of them.

Four hundred and seventy-four cuts and sixteen surviving sheets, which is a smaller number than it looks and for a reason that is not about tangles at all. A cut gives the paper a freedom: the two panels the crease joined are no longer held together by a fold, so the composition of reflections that decides where every panel goes stops deciding where that one goes, and the patch no longer has a single folded state. There is nothing left to order.

So the cut does not weaken the contradiction. It dissolves the question, and it is worth its own essay. What can be said here is the part that survives: on the sixteen sheets that do still place, the contradiction is untouched, and every one of those sixteen is a cut at a crease reaching the sheet’s edge. Not one cut of a crease with an interior vertex at each end leaves a sheet that places at all — and those are the creases the contradiction runs through.

The contrast with what a cut buys elsewhere is stark. A cut is a licence counted what one buys in letterings and found it substantial — cutting a crease with an interior vertex at each end releases two vertices from every condition in the subject and halves the number of pieces the folding set breaks into. Against a tangle, the same operation costs the patch its folded state.

The tangle is not where the paper runs out #

The obvious guess about where a fault of this kind would sit is the rim. A tessellation patch is mostly rim — at the periods this collection draws, between forty and sixty per cent of the twist polygons touch the sheet’s edge — and the rim is where the last repair to these patches was needed, because the way the pattern was cut out of the plane put creases across one another there.

It is not the rim this time. Panels with a raw edge of the sheet on them are under-represented in the tangle on every one of the five patches: between twenty-six and forty-two per cent of a tangle’s panels have a raw edge, against thirty-eight to fifty-two per cent of the patch as a whole. The contradiction lives where the paper is crowded, not where it runs out.

That is a reversal worth noticing rather than a detail. A rim panel is joined to fewer other panels — the sheet ends, so some of its sides are raw edges carrying no arrow at all — and a panel with fewer arrows is on fewer circles. The middle of a patch is where every panel has its full complement of neighbours, and that is exactly where the letters have the most to agree about.

The measurement that would have been made instead #

There is a simpler quantity that suggests itself and it was tried first: count the circles. A graph with more circles through it is worse tangled, and the number of independent circles in a graph is its arrows minus its nodes plus one, which is arithmetic rather than an algorithm.

It is the wrong quantity here and the reason is worth stating, because the same trap is available in several places in this subject. That count is over the whole graph, including every arrow outside the tangle, and it counts undirected circuits — chains that close up — rather than circles in which the arrows all agree. A tessellation patch has hundreds of undirected circuits by construction; that is what a tessellation is. What decides whether the letters contradict themselves is whether any of those circuits has been oriented all the way round, and the arithmetic cannot see orientation at all.

The strongly connected parts can, and that is the whole reason to pay for them. Every arrow inside such a part is on a circle whose arrows agree; no arrow outside one is. The count of arrows inside the parts — fifty-two of eighty-four on the square patch, a hundred and forty-six of two hundred and eighty-two on the rhombille — is therefore the number of statements a repair would have to reach, and it is between forty and sixty per cent of everything the letters say.

What the length of a circle is worth #

Given all this, the length the search reports is close to meaningless as a measure of severity, and it is worth asking what it does measure.

It measures the girth of the tangle, roughly — how short the shortest circle through the region the walk happened to enter is. On these patches that is almost always six or eight, which is a fact about the pattern’s geometry rather than about the fault: six is the shortest circle a chain of panels can make once a single vertex is ruled out, and a twist tessellation has six-panel circuits all over it wherever two twist polygons share a pleat.

So a short circle is not good news and a long one is not bad news. The rhombille produced circles of fifty in some draws and six in others from tangles of comparable size, and the difference between those two runs is which panel the walk started from.

A nine-panel twist is where the intuition about circle length comes from, and it is the one size at which the intuition is right. The circle is eight of the nine panels, so the witness is the fault. Every patch large enough to be interesting is not like that.

That last point is what makes the tangle worth drawing at all. The patch’s previous fault was visible in the ink once anybody thought to look — two creases across one another, at a printed size of a sixth of a millimetre, but there on the page. This one is not in the ink. Two patches with identical drawings and different letters are one perfectly foldable object and one with half its panels in a tangle, and no amount of looking at the picture separates them.

The instrument, and where it refuses #

Two things about how this is computed are worth recording, because both were mistakes before they were features.

The decomposition is written iteratively rather than as the recursion the textbook states. A patch of a hundred and fifty-seven panels with two hundred and eighty-two arrows is deep enough for a recursive walk to matter, and a checker that runs out of stack reports a crash rather than a verdict — which is the worst of both, since a crash inside a check is indistinguishable from a check that was never run.

And the shading is drawn on the lettering the tangle was measured on. That sounds too obvious to mention and it was the first version’s defect: the measurement was made on a drawn lettering, the lettering was then put back so as not to disturb the pattern, and the patch was drawn at its own letters with the other lettering’s tangle shaded onto it. Two pictures pretending to be one. The same slip in the cutting measurement was worse — with the pattern’s own consistent letters restored there is no circle to clear, so every one of the eighty-four cuts “cleared” it, and the figure reported a hundred per cent success at repairing a fault that was not there.

That is the shape of error this collection is most exposed to and it does not announce itself: a check quietly handed the passing case returns a beautiful number. The patterns a checker is tested on is the standing account of the same hazard one level up, where the test set rather than the test is the thing that has been handed the easy case. The repair is the one that always applies — make the object being measured travel with the measurement, rather than being reconstructed near it.

What is left to say about the patches #

The four repaired patches have, at this point, a fully characterised failure. They place; they satisfy every vertex condition; their letters contradict themselves over most of their panels; and no single-crease repair touches it.

Which leaves exactly one direction open, and it is the one the numbers have been pointing at from the start. On the square patch twenty-six letterings in two hundred have no contradiction anywhere. Those exist; they are not repairs to a bad lettering but different letterings altogether, and there is no path of small changes from one to the other. A patch is not mended. It is relettered, or it is not fixed.

The rhombille has none in two hundred draws, which is a different situation and an honest one to be uncertain about. Zero of two hundred is not zero: it is a statement about what the sampler found, on a pattern with two hundred and eighty-two creases and a solution set nobody can count. What can be said is that its own construction’s lettering closes a circle of sixteen, that two hundred independent attempts did no better, and that the tangle in every one of them covers most of the sheet.

Whether a consistent lettering of the rhombille exists at all is the sort of question this collection is careful not to answer by exhaustion, since the general problem is NP-hard and a patch of two hundred and eighty-two creases is not a small instance of it. What has changed is that the question is now well posed. Before, a patch that failed was a patch about which something unspecified had gone wrong. Now it is a patch with a named tangle covering a measured fraction of it, produced by letters that are chosen rather than constructed, and the thing to look for is a choice rather than a repair.