A test that only knows one lattice

Every cheap test misses a shape ends on an eleven-helix cluster that the colour count, the count of ends, the cut conditions, the forced steps and the colour of the forced ends all pass, and that no strand can route. It also says what refuses it, and the argument is made of the same ingredients as the tests it defeats: one helix cuts off a group of three with no end among them, so the route has to finish in that group; its other end is therefore the tail at the far side; and the stretch of seven it has to cross on the way has four helices of one colour and three of the other, with both of its required endpoints on the wrong ones.

Every step of that is a test already in the list. What is new is that each step is applied to a piece of the shape rather than to the shape, and that the piece is identified by the other steps.

So the obvious thing to do is add it and run the census again. This is that computation, and it produces one result that was expected and one that was not.

The test, written so a machine can run it #

The argument in the essay before this one is about one shape and has to be stated for any.

Find a cut. Take each helix in turn, remove it, and count the pieces left. Keep the removals that leave exactly two.

Find the piece the route must end in. A helix with a single neighbour can only be where a route starts or finishes. If one of the two pieces contains no such helix and the other does, then a route entering the first piece through the cut helix can never leave it — the cut helix is already spent — so the route must finish inside it.

Read off what that forces. The route’s other end is the single-neighbour helix in the second piece. The route starts there, covers that piece, and leaves it through the one helix adjacent to the cut. So the second piece has to be crossed by a path from a known helix to another known helix.

Count colours on the piece alone. A path through $m$ helices alternates colours, so it uses $\lceil m/2 \rceil$ of one and $\lfloor m/2 \rfloor$ of the other. If $m$ is even the path’s two endpoints are of different colours; if $m$ is odd they are both of the majority colour. Either condition can fail on the two endpoints the previous step named, and if it fails there is no route.

That is one pass over the helices for each choice of cut helix, so it costs no more than the cut conditions it is built on. It is a necessary condition in exactly the sense the others are — a shape with a route passes it — and like all of them it is not sufficient.

The census checks the first half rather than taking it on trust. Every shape any test refuses is handed to the exhaustive search anyway, and a refusal the search contradicts stops the figure. That arrangement is what caught the first version of the forced-step test turning away routable shapes, and the piece test passes it at every size on both lattices.

What it costs to know nothing cheap #

Before the result, it is worth being precise about what a cheap test is bought with, because the whole staircase is an argument about a price.

The last column is the point. Refusing an eleven-helix square survivor by search takes 477 partial routes; refusing a twelve-helix one takes between 748 and 920; refusing a sixteen-helix honeycomb one takes 818. A cheap test replaces that with a single pass over the helices. The counts are small because the shapes are small, and they grow faster than the shapes do — which is the reason the staircase matters at all, and the reason an exhaustive search is something to be pointed carefully rather than run on everything.

The other columns say what the tests are doing for their money. At twelve helices on the square lattice there are 505,861 connected shapes; the colour count, the ends and the cuts refuse all but 45,508 of them; and of those, 1,808 have no route. So the three cheapest tests, run on half a million shapes, leave a search to be run on nine per cent of them, and they let through one unroutable shape for every twenty-five they pass.

Thirty-two out of thirty-two #

The expected result comes first. On the square lattice the piece test refuses every one of the thirty-two eleven-helix shapes that survived the previous four.

Thirty-two is not thirty-two shapes. The census lists a shape once for each way it sits on the lattice, and the eleven-helix survivors are eight placements each of four arrangements — which are, on the graph, one shape: the same eleven helices joined the same way, drawn four ways round. So the test was read off the only survivor there was, and clearing all thirty-two is clearing one object.

That is worth saying plainly because it is the weakest part of the exercise. A test derived from a single witness and then shown to refuse that witness has demonstrated nothing about tests in general. What makes the result a result is the size it moves to, and what makes it interesting is what happens on the other lattice.

Twelve helices, and two shapes #

With the piece test added, the smallest square-lattice shape that every cheap test passes and no route reaches has twelve helices, and there are twelve placements of it.

Twelve placements of two shapes: eight of an arrangement with no symmetry, and four of one that is its own mirror image. That is a different situation from every earlier step of the staircase, each of which produced exactly one shape. The survivors are no longer a single object that happens to be hard; they are a small family, and a family is what a further test would have to be aimed at.

The two are not hard in the same way, and one of them is not hard at all in the sense the test is about. The piece test is vacuous on the second shape. It has exactly one helix whose removal splits it, and the split is ten helices against one — the one being the shape’s single degree-one helix. So the piece with no end in it is the block of ten, the route must finish there, and the stretch it has to cross first is a single helix: a path of one, whose start and finish are the same helix and whose colour count cannot fail. The test runs, finds its cut, and has nothing to count.

The first shape does give the test something to do. It has two cut helices, both of degree four. One of them splits it one against ten and is vacuous in the same way. The other splits it eight against three, the three have no end among them, and the eight are four of each colour — so the route must cross an even stretch, its two endpoints must be of different colours, and they are. The test is applicable, it is applied, and the shape passes it honestly.

So the twelve-helix row of the census is really two rows. One shape defeats the piece test by satisfying it and the other by not offering it a question, and a sixth test aimed at the first would leave the second exactly where it is. A family of survivors is not a single obstruction, and the staircase’s earlier steps, each of which produced one shape, had made it look like one.

There is a detail in the twelve-helix row worth reading, and it is not about the new test at all. At eleven helices the colour of the forced ends refused thirty-six of sixty-eight survivors — more than half. At twelve it refuses none: seventy-six shapes pass the forced steps and seventy-six pass the colour of the ends. A test that was the difference between sixty-eight and thirty-two one size down does nothing one size up.

That is not an anomaly to be explained away, and the mechanism is exact. The colour of the ends can refuse a shape two ways. If the two colour counts differ by one, a route must start and finish on the commoner colour, so any known end on the rarer one refuses the shape — which is how thirty-six of the sixty-eight eleven-helix survivors fell, all of them shapes with five helices of one colour and six of the other. If the counts are equal, a route’s two ends must be of different colours, which can only be checked when both ends are known.

Every one of the twelve-helix survivors has six helices of each colour and exactly one helix of degree one. The first fact disables the unequal-counts branch; the second disables the equal-counts branch, because the second end is not known. The test does not weaken at twelve helices; it is presented with a set of shapes on which neither of its two conditions is applicable, and it says nothing because there is nothing it is entitled to say.

That is worth separating from the usual reading. A test’s catch rate at one size predicts nothing about its catch rate at the next — the same lesson the crane census reached from the opposite direction, where a test that caught 99.64 per cent of failures decided a shrinking share of what was left. But a rate falling to zero is not the same event as a rate falling, and here it is the survivors that changed rather than the test. The shapes that survive the forcing at twelve are shapes selected for having nothing the colour of the ends can grip, because the forcing refuses everything else.

And nothing at all on the honeycomb #

The unexpected result is the other lattice.

The piece test refuses none of the six sixteen-helix survivors, and none of anything else on that lattice either. The fourth and fifth columns of the honeycomb census are the same column. The smallest shape every cheap test passes is sixteen helices before the test is added and sixteen after, and the staircase’s fourth step, which is a step on the square lattice, is flat here.

That is not because the ingredients are missing. Every one of the six survivors has exactly one helix with a single neighbour, exactly one helix whose removal splits it into two pieces, and the piece without an end in it is there to be found. The test runs; it finds its cut; it counts the colours of the stretch; and the count passes.

The six are one shape, drawn six ways. Its colours are eight and eight — perfectly balanced, so the counting argument these essays opened with has nothing to say and neither does the colour of its ends, for the same reason the square lattice’s twelve-helix survivors escape it. It has a single helix of degree one, so the forced steps have only one end to work from and stop almost immediately. And its degree profile is the honeycomb’s characteristic one: one helix with a single neighbour, twelve with two, three with three. A shape made almost entirely of degree-two helices is a shape made of corridors, which is precisely what the forced-row argument was invented for and precisely what it fails to catch when the corridors are arranged so that following them never reaches a contradiction.

Why a test carries a lattice #

The two results together say something the staircase’s shape had concealed for two essays.

A cheap test is written as a statement about routes, so it looks like a statement about graphs, and a statement about graphs ought to be indifferent to which lattice the graph was drawn on. In practice a test is derived, and it is derived by looking at a witness — a particular shape that the current list fails to refuse — and asking what is true of that shape that the list does not see. The answer is a fact about that shape’s structure, and the structure is the lattice’s.

The square lattice’s eleven-helix survivor fails because it has a tail, a fenced-off group and a stretch of the wrong parity between them, and it has those because on a four-neighbour lattice a shape can be compact and still have a helix whose removal disconnects it. That is the same asymmetry the two lattices’ block census ran into from the other side, where the shapes that route trivially on squares turned out to have a corridor along one edge on the honeycomb. The honeycomb’s sixteen-helix survivor fails for something else, and what that something is remains undetermined here: it is not the colour count on the shape, not the colour count on a fenced piece, not the ends, not the cuts, not the chain of forced steps, and not the colours of the ends the chain produces. What the honeycomb’s survivor has that the square’s does not is thirteen helices of degree two or less against the square survivor’s eight, and no arrangement of them that the forcing can turn into a contradiction.

So the list of cheap tests is not one list. It is whatever the last witness was, generalised, and the next witness on the other lattice will generalise into something else. The staircase every cheap test misses a shape drew as two parallel sequences of steps is really two separate staircases that happen to be climbing the same wall, and the reason they looked parallel is that the first three tests — the colour count, the ends, the cuts — were all derived before either lattice was in view, from the abstract fact that a route is a path.

This is the routing version of what crease patterns keep finding. Local is not global is the statement that a pattern can satisfy every condition checkable at a vertex and still not fold, and the counterexamples there are also smallest objects that fool every local look. What this essay adds is that the supply of local conditions is not neutral either: each one is somebody’s generalisation of a particular counterexample, so the list of them carries the shape of whatever was looked at, and a list assembled on one kind of instance can be systematically blind on another.

What the census cannot show #

It stops at twelve helices on squares and sixteen on the honeycomb. Thirteen on the square lattice is 1.9 million shapes and fourteen is 7.5 million; the honeycomb grows by about three times a helix. Nothing here says whether the square lattice’s smallest survivor moves again at thirteen when a sixth test is added, or whether the honeycomb’s stays at sixteen for several more.

A shape is a set of cells and nothing else. There is no crossover position, no sequence and no orientation of a helix in any of it — the route is permitted to cross between neighbours anywhere along their length, which the crossover period says it cannot, and the lattice the pitch prefers is the reason the two lattices are worth comparing at all. A shape that routes in this graph may have no route a strand can actually take.

The claim that a set of placements is one shape is a claim about a certificate. Two shapes are called the same here when they have the same degree sequence and the same multiset of distances between every pair of helices. That is invariant under any relabelling, it is decisive on graphs of this size, and it is not a proof of isomorphism in general — the drawings are put side by side so the identification can be checked by eye.

And the test’s soundness is empirical. Every shape the piece test refuses is searched, and none of them has a route, at every size on both lattices. That is a check over about three million shapes rather than an argument, and the argument in the second section is the reason to believe it holds past the census.

Still open: what refuses the honeycomb’s sixteen #

The honeycomb survivor is now the only object in these essays with no cheap refusal at all, and it is a small, ordinary-looking cluster of sixteen cells.

The obvious place to look is the corridors. Thirteen of its helices have two neighbours or fewer, so the forced steps have almost everything to work with and almost nothing to work from: with only one end known, the chain cannot start. A test that reasons about a path of degree-two helices without knowing the route’s ends — a corridor must be traversed in one of two directions, and its two mouths are then the only ways in and out — would have something to say about this shape where the forcing has nothing. Whether that can be stated as a condition cheap enough to belong in this list is the next computation, and it would be the first test in the list derived from a honeycomb witness.

The other direction is the one the parity of the thing suggests. Every survivor at every stage on both lattices has exactly one or two helices of degree one, and a route’s ends are at degree-one helices or somewhere else. The whole forcing apparatus is built on knowing where the ends are, and every survivor is a shape where that knowledge is incomplete. A test that enumerated candidate ends rather than reading them off the degrees would be more expensive by a factor of the helix count and would subsume both the forcing and the colour-of-ends tests. That is the point at which a list of cheap tests stops being cheap, and finding where it is would say what the whole staircase costs to climb.

Both directions are versions of the question the chequerboard count has been raising since the first of these essays: a necessary condition is a fact that can be checked without solving the problem, and the supply of such facts is bounded by the imagination of whoever is looking for them rather than by the problem. Every test in this list is somebody noticing something about a picture.

The habit worth carrying is about where a heuristic comes from. A test derived from a counterexample inherits the counterexample’s world. It will look like a general statement, it will be a general statement, and its power will be concentrated on instances that resemble the one it was read off — so a list of tests assembled that way is a record of what somebody happened to look at, and the first thing to do with a new one is run it somewhere its author was not.