The arc that arrived twice

A folded state’s layer relations are a graph: an arc from one panel to another means the second lies over the first. The search that looks for a consistent lettering explores that graph, and the graph is derived from the drawing by walking its faces.

One crease of a glued sheet was contributing two arcs, on half the objects measured, and the duplicate turned out to be a diagnosis rather than a defect.

Where an arc comes from #

Take a glued cell. Its panels have been identified in pairs — a panel at the left edge and its partner at the right are one panel of the sheet — and its creases likewise.

For each crease, the two panels either side of it are found, mapped to their classes on the glued sheet, and an arc is recorded: near panel, far panel, the crease, and the lattice step between them.

A crease appears in the drawing as several pieces, one per place it crosses the cell. Each piece produces the same arc, so the arcs are deduplicated: the same crease class between the same panel classes with the same step is recorded once.

The duplicate #

Which panel is near and which is far is decided by the order the face walk numbered them, and the face walk numbers them arbitrarily.

So the same relation can be recorded two ways: near-to-far with a step, or far-to-near with the opposite step. Those are one arc written twice, and the deduplication was keying on the direction, so both survived.

On the square twist the arc count equalled the crease count exactly. On the triangular, hexagonal, elongated and rhombille tilings it exceeded it, by amounts from one to six.

Why it was harmless #

The two records of one arc are equivalent on most sheets, and it is worth seeing why, because the reason is what makes the exception interesting.

An arc’s direction depends on the letter and on whether the near panel is face-up. The two panels either side of a crease always have opposite orientation — crossing a crease turns the paper over — so the mirrored record has the opposite near panel and therefore the opposite orientation flag.

Those two differences cancel. Both records give the same arc, pointing the same way, for every letter.

So a duplicate is a redundancy: the graph has one edge listed twice, acyclicity is unaffected, and no verdict moves. Removing the duplicates changed no published number.

Where it was not #

On one family the two records did not have opposite orientation flags. They had the same flag, so they gave arcs pointing in opposite directions — an immediate two-cycle for every letter, and a search that exhausts on every lettering.

That family was the grid, glued at an odd number of periods.

The reason is what the whole thing was diagnosing. The orientation flag on a panel is well defined only when the panel graph is bipartite — when the paper’s two faces can be consistently assigned. On a sheet where a loop returns the paper the other way up, the two panels being identified have the same flag rather than opposite ones, because the identification joined a face-up piece to a face-down one.

So the duplicate arcs pointing opposite ways were the sheet’s non-orientability, showing up in the last place anybody would look for it.

The three steps of derivation #

The gap between the symptom and the cause is worth laying out, because it explains why the diagnosis was slow.

Step one: the drawing. A rectangle of pattern, with creases in it, cut so that its edges miss every vertex. Nothing here is wrong at any point in the story.

Step two: the folded state. The panels are given motions by composing reflections along a spanning tree of the face graph. Each panel gets an orientation flag — whether its motion turns the paper over — and that flag is well defined because the panel graph of a flat-foldable drawing is bipartite.

Step three: the identification. Panels at opposite edges are joined. Here is where it goes wrong: the identification can join a panel whose flag says face-up to one whose flag says face-down, and when it does, the flag stops being a property of the glued sheet’s panels.

Step four: the arcs. Built from the flags. If the flags are inconsistent, the arcs are.

So the failure is at step three and the symptom is at step four, and steps three and four are in different functions written months apart. That is a very ordinary distance for a cause and a symptom to be separated by, and it is why the first instinct — fix the arcs — was so natural.

What a two-cycle means #

The concrete failure was a pair of arcs pointing opposite ways between the same two panels, which is a two-cycle in the relation graph.

A cycle in the layer relations is a contradiction: panel A is under B, B is under A, and no arrangement of paper satisfies both. A search finding one prunes that branch.

A two-cycle is the smallest possible one and it is present for every letter, since the two arcs’ directions both flip together when a letter changes. So the search prunes every branch immediately and exhausts in a handful of nodes, reporting that no consistent lettering exists.

That report is not obviously wrong. Plenty of sheets have no consistent lettering, and the grid’s odd cells genuinely do not. What gave it away was that the same drawing glued the other way reported differently, and nothing about the drawing distinguished the two directions.

So the bug produced the right answer for the wrong reason on some sheets and the wrong answer on others, which is the least helpful combination available.

Why the twists never showed it #

Five of the ten twist patches carried duplicate arcs and none of them misbehaved, and it is worth being precise about the difference.

A twist tessellation’s cell is always orientable: a path round it crosses an even number of creases, because a twist polygon’s pleats come in pairs, one entering and one leaving.

So the identification always joins panels of opposite orientation, the flags are consistent, the mirrored records are equivalent, and the duplicates are pure redundancy.

That is why the whole gluing apparatus was built and used for a long time before the problem appeared. The family it was built on cannot exhibit it, and the families that can arrived later — because gluing anything other than a twist tessellation needed a plane drawing and a stated period, which is machinery of its own.

A construction validated on its easiest case is a construction validated on the case that cannot fail, which is a general hazard and is worth naming as one.

What the fix cost #

Both halves are small and it is worth saying so, since a finding of this kind can read as though it required a rewrite.

Deduplicating up to direction is one extra key in a set lookup. Two lines.

Refusing a non-orientable quotient is comparing the determinants of two motions per identified pair, which the code was already computing for a different purpose, and reporting the count separately from the count of rotated pairs. About ten lines, and it produced a second finding on its own, because the number it split had been reporting two different facts.

No published number moved. The twist tessellations’ costs are identical before and after — three, nine, six hundred and twenty-five and fifty-six thousand seven hundred and seventy-two on the square cells, and the same on the others — because on those sheets nothing was wrong.

What moved is that three families can now be glued correctly, and one of them refuses half its sizes for a reason that is now stated rather than being an asymmetric verdict.

The symptom and the disease #

The symptom was an asymmetric verdict: a three-period grid cell reported as having a consistent lettering when glued one way and not when glued the other, on a drawing symmetric between its two directions.

That asymmetry is impossible for the object and possible for the code, so it was a bug. What it was a bug about took longer: the arcs were the visible layer, the orientation was the cause, and the two are separated by three steps of derivation.

The repair, in two halves #

Both halves were needed and neither would have been enough.

Deduplicate up to direction. The mirrored record of an arc is the same arc, so keying the deduplication on the unordered pair and the signed step removes it. That is correct on every sheet and it removes the redundancy.

Refuse a non-orientable quotient before building arcs at all. A sheet whose identification returns the paper the other way up has no consistent notion of which panel lies over which, so its relation graph does not represent anything. Building one and searching it is asking the wrong question, and the answer it gives is not wrong so much as meaningless.

Doing only the first would have produced a tidy graph representing nothing. Doing only the second would have left a redundancy that costs nothing and looks like sloppiness.

An arc, described properly #

Since the essay is about a record in a data structure, the record deserves a description.

An arc has four parts. The near panel class and the far panel class, which are panels of the glued sheet rather than pieces of the drawing. The crease class, likewise. And the lattice step — how many cells across and up the far panel sits from the near one.

The step is the part that only exists on a glued sheet, and it is the part that makes the consistency test different: a closed chain of arcs whose steps add to nothing is a contradiction, and one whose steps add to a nonzero vector is a stack that climbs.

The orientation flag is not part of the arc. It is used to build the arc — to decide which way it points, given a letter — and then discarded. That is why the flag’s inconsistency showed up as two arcs rather than as a flag that looked wrong: by the time anything was inspected, the flag was gone and only its consequence remained.

Keeping the flag on the record would have made the diagnosis immediate. It is not kept, because on an orientable sheet it carries no information the arc does not already have.

The numbers #

For the record, since the essay’s evidence is a set of small integers.

Arc counts against crease counts, on the twist tessellations’ torus cells at one and two periods: the square gives eight against eight and thirty-two against thirty-two — no duplicates. The triangular gives twenty-four against twenty-four and ninety-eight against ninety-six — two duplicates. The hexagonal gives twenty-five against twenty-four and ninety-eight against ninety-six. The elongated gives forty-one against forty and one hundred and sixty-two against one hundred and sixty. The rhombille gives fifty-one against forty-eight and one hundred and ninety-eight against one hundred and ninety-two.

Every one of those duplicates was checked and every one was harmless: the two records had opposite orientation flags and gave the same arc.

On the grid, at three periods glued across, one crease class contributed two arcs with the same flag. That is the harmful case, it produced an immediate two-cycle, and the search exhausted in fifteen nodes reporting no consistent lettering — while the same drawing glued along reported a lettering in fourteen.

Two verdicts on a symmetric drawing is impossible for the object, and that is the whole of the evidence that something was wrong.

What was checked afterwards #

A finding that changes a derived structure has to be checked against everything built on it, and the check is worth reporting.

The twist tessellations’ costs were re-measured after the deduplication, on all five tilings at every size that finishes: the square cells at one, two, three and four periods, the triangular and hexagonal at one, two and three, the elongated at one, two and three.

Every node count is identical to the number published before. The square cells still cost three, nine, six hundred and twenty-five and fifty-six thousand seven hundred and seventy-two under the correct test, and three, thirty-five, three thousand four hundred and fifty-five and more than two hundred thousand under the disc’s.

Only the arc counts moved, and they moved to equal the crease counts, which is what they were supposed to be.

The check that now runs #

The situation is asserted rather than remembered, which is the collection’s usual response to a finding of this shape.

Every glued sheet built here reports how many identified panel pairs have motions differing in the sign of the determinant, and how many differ otherwise. The first count refuses the sheet before any arc is built. The second is the turn and refuses it for a different reason.

And the arc count is compared against the crease count: they have to be equal, since each crease of the glued sheet contributes one relation. A run where they differ is a run where the deduplication has missed something, and it stops the figure being drawn.

Neither check would have caught the original problem on its own — the arc count was legitimately wrong before the deduplication, and the orientation count did not exist. Together they cover both halves, which is the point of having two.

Why redundancy is not the same as being wrong #

There is a temptation, on finding a duplicate, to treat the structure as untrustworthy in general, and it is worth resisting.

A graph with an edge listed twice represents the same relation as the graph with it listed once. Acyclicity is unaffected. Reachability is unaffected. Every question the search asks of the graph has the same answer.

So the duplicate cost nothing on the sheets where it was a duplicate, and the results computed with it are results computed on the right object. Nothing has to be recomputed and nothing was.

The exception is the sheet where the two records were not the same relation — and there the problem is not that the structure had a duplicate, it is that the flag it was built from had stopped meaning anything. Calling that a duplicate is already a misdescription.

Which is the useful distinction to carry: a redundancy is harmless and a contradiction wearing the shape of a redundancy is not, and telling them apart means looking at what the two records say rather than counting them.

The general shape, once #

The collection has a phrase for this class of thing and it fits: an anomaly in a derived quantity is a message about an assumption in the derivation.

Here the derived quantity was an arc count, the assumption was that two panels either side of a crease have opposite orientation, and the assumption is true on a sheet with two sides and false on one without.

The same shape produced a test imported without its hypothesis, a closure condition compared against a constant and an enumeration that starts from a bottom layer. Four instances, all of them the same sentence going unwritten because it said nothing on the objects available.

Which suggests a habit rather than a fix: when a derived structure comes out with a count that is not the count it should be, the first question is which property of the source the derivation was relying on, and whether the source still has it.

What to take from it #

A duplicate in a derived structure has a cause, and the cause is not always the derivation.

The general lesson is about which layer to look at. An arc count exceeding a crease count is a fact about the arc-building code and it was tempting to fix it there — deduplicate harder and move on. That fix would have been correct, would have removed the symptom, and would have hidden the finding.

What made the difference was asking why the mirrored record disagreed, which is a question about orientation rather than about deduplication, and the answer was a property of the sheet that nothing else in the collection was measuring.

Every derived structure carries assumptions from the thing it was derived from. An anomaly in the structure is a message about one of them, and reading it as untidiness discards the message.