Every cheap test misses a shape

A row the route cannot leave sorts every rectangular block of helices up to ten by eight on the honeycomb lattice and finds twenty that no single strand can route. Every one of them falls to a cheap test — disconnection, the colour count, a cut through one or two helices, or the forced row along an odd block’s edge — and none needs the exhaustive search to be refused. That leaves the question two ceilings had already raised: there must be a shape all of those tests pass and no route reaches, because deciding whether a route exists is hard, and a hard question is never settled by a handful of local counts. What is the smallest one?

Blocks were the wrong place to look, because they are the shapes the cheap tests were invented on. So the census below looks everywhere. It lists every connected shape of helices, size by size, on both lattices, runs every cheap test on each, and hands the shapes the tests let through to the exhaustive search — the kind of search that proves nothing exists.

The answer is not one shape but a staircase of them. Each cheap test has a smallest shape it misses, and adding a test moves that shape outward or leaves it in place. Nothing removes it.

The tests, written as a list #

Each test is a fact about a route that can be checked without finding one. A route visits every helix once, stepping only between neighbours.

The colour count. Colour the helices like a chequerboard, so that neighbours always differ. A route alternates colours, so the two counts can differ by at most one, and if they differ by one the route starts and ends on the commoner colour. A sheet that routes itself introduced it, and it is the same kind of argument as Maekawa’s count of mountains and valleys, and just as insufficient.

The ends. A helix with only one neighbour can only be where a route starts or finishes, so a shape with three such helices has no route.

The cuts. Remove one helix and count the pieces left. A route passing through that helix can serve at most two pieces, so three pieces means no route; removing two helices can leave at most three pieces, and so on. Two ceilings derived the general form.

The forced steps. Once both ends of a route are known — two helices with a single neighbour each — every other helix is passed through, using exactly two of its neighbours. A helix with only two neighbours therefore uses both, which may leave a neighbour with no spare connection, which cuts its other links, which may create another helix with two. Following those consequences either stops quietly or reaches a contradiction: a helix needing three connections, a closed loop of forced steps, or a forced chain holding both ends and not every helix. This is the argument that refuses the odd honeycomb block, written for any shape.

The colour of the ends. A helix a route must start or finish at has to be on the colour the colour count says the route’s ends are on — including helices that only become ends when the forced steps cut their other links.

Every one of these is a necessary condition: a shape with a route passes it. None is sufficient.

A test that refused too much #

The census checks that last claim rather than trusting it, and the check was needed.

The first version of the forced-step test forced both neighbours of every two-neighbour helix at once, without waiting for the ends to be known. That is correct for a closed loop, where every helix is passed through, and wrong for a path, whose two ends each use one neighbour only. A two-neighbour helix can be an end. The census catches that kind of error by searching every shape any test refuses, and requiring the search to agree; at nine helices on the square lattice it found 382 shapes the test turned away that have a route. With the test corrected — two-neighbour helices forced only once both ends are known — every refusal on both lattices, at every size listed, is confirmed by the search.

That version of the test had reported that nothing below fourteen helices fools every test on squares, and nothing up to eighteen on the honeycomb. Both numbers were artefacts of a condition that was not necessary. A cheap test is only as good as its record against the search it stands in for, and a test that is never run against that search can refuse shapes that route without anybody noticing, because a refusal looks exactly like a result.

Nine helices fool the counts and the cuts #

The second figure is the census on the square lattice: every connected shape from four helices to eleven, how many pass the colour count, the ends and the cuts, and how many of those have no route.

Up to eight helices, none. Every shape the first three tests pass has a route. At nine helices there are 9,910 connected shapes, 2,319 of them pass, and 64 have no route. At ten, 80 of 6,106. At eleven, 1,260 of 17,646.

The sixty-four at nine helices are eight shapes, each counted in the eight positions a square’s rotations and reflections put it in. The third figure draws one: a column of six helices with a column of three beside its middle.

Its colours are four and five and its two ends are the tips of the long column, so the first two tests pass; no single helix or pair splits it into too many pieces, so the cuts pass. The forced steps do not. With both ends known, the helices with two neighbours — the one next to the bottom tip, and the top and bottom of the short column — must use both. That spends both connections of the two long-column helices they reach, cuts those helices’ other links, and leaves a helix in the middle of the long column with only one neighbour. A third end, and no route.

Eleven helices fool the forced steps #

Adding the forced steps clears the nine- and ten-helix shapes entirely, and the smallest shape that fools four tests has eleven helices. There are 68 such placements. The fourth figure draws one, and its failure is one step past what the forced steps can see.

It has only one helix with a single neighbour, so only one end is known and the forced steps have nothing to work with: a two-neighbour helix might be the other end. The colour count passes, five to six. But the known end is on the colour with five, and a route through eleven helices of which six share a colour has to start and finish on those six. The two facts together refuse the shape; neither does alone.

That is the fifth test, the colour of the ends. It removes thirty-six of the sixty-eight — and leaves thirty-two, still at eleven helices. On the square lattice the smallest shape every test here passes has eleven helices, and the fifth figure draws it.

Why the last one fails #

The shape that survives all five tests fails for a reason that is itself cheap, which is the interesting part.

One helix, ringed in the drawing, joins a block of three at the top to everything else. Removing it leaves two pieces, which the cut condition allows. But the top piece contains no end, and a route that enters it through the ringed helix can never come back out, so the route must finish in the top piece. Its other end is the tail helix at the bottom. So the route has to cross the rest of the shape — the shaded seven helices — starting at the tail and leaving through the one helix next to the ringed one.

A stretch of seven helices has four of one colour and three of the other, and a path through all seven starts and finishes on the four. The tail is on the four; the exit helix is on the three. No route.

Every ingredient of that argument is one of the tests already in the list: a cut through one helix, the location of a route’s end, the colour count. The shape passes each of them applied to the whole shape and fails them applied to a piece. The test that refuses the smallest survivor is the colour count, applied to the stretch a cut and an end have fenced off. Adding it to the list would push the smallest survivor out again, and something else would refuse the next survivor, and so on — which is what it looks like when a hard question is approached one cheap test at a time.

How much of the gap each test closes #

The census columns can be read as a ledger, and the ledger says the cheap tests are very good right up to the size where they are not good enough.

On the square lattice at eleven helices, 17,646 shapes pass the colour count, the ends and the cuts, and 1,260 of those have no route: the three tests have let through one unroutable shape for every fourteen they pass. The forced steps refuse 1,192 of the 1,260, and the colour of the forced ends refuses 36 of the 68 left. So of the unroutable shapes the first three tests miss at eleven helices, the other two catch 97.5 per cent, and the thirty-two that remain are what the whole list of tests costs at that size.

On the honeycomb at sixteen helices the proportions are sharper still. Of 28,221 shapes passing the counts and the cuts, 1,722 have no route; the forced steps refuse all but six, and the colour of the ends refuses none of those six. At fifteen helices it had refused all twelve of the forced steps’ survivors, which is why the honeycomb’s last step moves the smallest survivor by one.

That pattern — a test that catches almost everything and misses a remnant that is exactly as large as the tests are small — is the shape a necessary condition’s record usually has, and nearly every cutting fails at one crane found it in a slit sheet of paper. There a look at each crane caught 99.64 per cent of the failures and decided a shrinking share of the rest. Here the list of tests catches nearly every unroutable shape at every size and still leaves a first survivor. A test’s catch rate and its smallest miss are different measurements, and a design that is going to rely on cheap tests needs the second.

The honeycomb holds out longer #

The honeycomb lattice — the one a double helix’s pitch prefers — was suggested as the more promising place to look for such a shape, on the grounds that its sparser rows are where local tests run out of things to say. The census says the opposite.

On the honeycomb, drawn as rows in which each helix touches the two beside it and one row above or below, the colour count, the ends and the cuts are first fooled at twelve helices, by eighteen shapes. The forced steps clear those and are first fooled at fifteen. Adding the colour of the ends clears those and is first fooled at sixteen, by six shapes. At every stage the honeycomb’s smallest survivor is larger than the square lattice’s, by three helices, then four, then five.

That is not only because honeycomb shapes are fewer. There are more than 2.5 million connected honeycomb shapes of sixteen helices, and nearly four million shapes up to that size have been searched or refused before the first one fools every test; on the square lattice the first all-test survivor turns up among the 135,268 shapes of eleven helices. Per shape examined, the honeycomb is decided by cheap tests for far longer.

The reason is the thing that made its odd blocks unroutable. A helix on the honeycomb has three neighbours at most, so shapes are full of helices with two, and once both ends are known every one of those is a forced step. Forced steps propagate: each one spends connections that force the next. On the square lattice a helix inside a shape has four neighbours, which leaves room for a shape to pass every count while hiding a contradiction the forcing never reaches. The honeycomb’s scarcity of neighbours makes routes rarer and makes the reasons they are missing easier to find.

The sixteen-helix honeycomb survivor, drawn in the last figure, does not fall to the piece argument that refuses the square lattice’s eleven. What does refuse it, short of the search, the census does not say.

Where the hardness comes from #

The staircase is what a known result predicts, and the prediction is sharper than it looks.

In 1982 Alon Itai, Christos Papadimitriou and Jayme Szwarcfiter proved that deciding whether a shape drawn on a square grid has a route through every cell — a Hamiltonian path in a grid graph — is NP-complete. If any list of cheap tests decided every shape, the question would be easy, and it almost certainly is not. So every finite list of tests that each look at a bounded amount of the shape must miss something, at some size, and the staircase is the census watching that happen.

The same proof uses shapes with holes in them, and holes matter. For closed routes — cycles that return to their start — through shapes with no holes, Christopher Umans and William Lenhart gave a polynomial method in 1997. None of the survivors drawn here has a hole. The smallest shapes that defeat cheap tests are ordinary solid clusters of helices, the kind a design might actually use, which says that the hardness a design meets is not confined to exotic shapes.

Paper folding has the same structure, and has had it for longer. Maekawa’s and Kawasaki’s conditions are cheap tests at a vertex, and local is not global is the finding that a crease pattern can pass them everywhere and still not fold. The counterexamples there are also smallest objects that fool every local look, and they are also refused by something that is local once the right piece of the pattern is known — a layer order along one strip, a loop of forced relations. Folding flat and routing a strand fail cheap tests in the same way, because both are hard questions asked of objects whose parts are simple — a likeness two things called folding otherwise finds thin.

What the census cannot show #

It stops at eleven helices on squares and sixteen on the honeycomb. Past those sizes the list of shapes grows by about three times per helix on the honeycomb and nearly four on squares, and the census says nothing about where later tests would be fooled or whether the gap between the lattices keeps widening.

It counts shapes as drawn on the lattice, not as designed. Every connected set of helices is a shape here, and a real design draws only some of them — compact cross-sections, usually, with no one-helix tails. Whether the survivors or anything like them turn up in a design is not something a list of all shapes can say, and the tails that make the square lattice’s survivors fail are exactly the features a designer tends to avoid.

A route here is a path and nothing else. One strand visits every helix once, stepping between neighbours, with no attention to where along a helix the crossover sits or which face of the helix it uses. The helix chooses the lattice found that those constraints decide the lattice itself, and a route that exists in the graph may be one no real strand can take.

And the honeycomb is drawn one way: rows with alternating steps up and down. The shapes counted are the shapes of that drawing, which is the honeycomb exactly, and the census runs every shape in both of the drawing’s alignments so that nothing depends on where a shape’s first helix sits.

How the census was run #

Every connected shape of each size is listed once, growing shapes a helix at a time in a fixed order so that none is produced twice. The square lattice’s totals — 9,910 shapes of nine helices, 36,446 of ten, 135,268 of eleven — are the known counts of such shapes, which is a check on the listing.

The cheap tests run first, the colour count and the ends before the cuts, because they are cheapest and refuse most shapes. Every shape they let through is searched exhaustively for a route.

And every refusal is searched too. A shape turned away by any test that the search can nonetheless route would mean the test is wrong. That comparison is what caught the first forced-step test turning away routable shapes, and with the corrected test it holds on every shape of every size listed.

Still open: the next step of the staircase #

The eleven-helix square survivor is refused by the colour count applied to a piece a cut has fenced off. Adding that test — cut the shape at each helix, locate the ends, and count colours on the stretch between them — moves the smallest survivor somewhere larger, and where it lands, and what refuses the next one, is the next computation. It needs the census carried past eleven helices, where the list of shapes on the square lattice reaches half a million at twelve and nearly two million at thirteen.

The honeycomb’s sixteen-helix survivors have no reason given here at all. Finding the cheapest argument that refuses them — or showing there is none of bounded size — would say whether the honeycomb’s longer resistance to cheap tests comes from its forced chains running further, or from something about three-neighbour lattices that a different test would capture.

The habit worth carrying is about necessary conditions in a hard problem. Expect every list of them to miss something, and look for the smallest thing it misses. The smallest miss is usually refused by the same tests applied to a part of the object, which says both what to add next and why adding things never ends.