The route, not the sheet

Each drawing has its own threshold swept the search across sizes and found where each drawing stops being settled by propagation alone. Every number in that sweep is one route through one space, and the essay said so in its own limitations: a backtracking search’s cost is a property of the pair — the sheet and the order the letters are taken in — and nothing in a fixed-seed sweep separates them.

That separation was named as the experiment to run next, and it was named before that: half the slack said the honest expectation was that a good deal of the factor of twenty-six belongs to the order.

It is more than a good deal.

Two sheets, eight routes #

The square grid’s four-period cell is the sheet where the threshold was found, so it is the one to ask.

Cut, it costs 42 to 55 nodes. Eight different branch orders, a factor of 1.3 between the best and the worst, and the middle one indistinguishable from either. A sheet below its threshold is not being searched, so the order has almost nothing to decide and the cost is the count of letters however they are taken.

Glued, the same drawing costs 69 to 24,636 — a factor of 357 — and one of the eight orders did not finish inside its budget at all. The middle order costs about 1,800, which is close to the 1,169 the fixed seed reported in the sweep, so the earlier number was a typical draw rather than an unlucky one.

At three periods, below the threshold, the two sheets behave alike again: 25 to 32 cut, 20 to 731 glued. The glued spread is already there — a factor of 37 — but the sheet is small enough that the worst route is still cheap.

What the best route costs #

The comparison that matters is not between the two middles. It is between the two bests.

The cut sheet’s cheapest order settles it in 42 nodes. The torus’s cheapest settles it in 69. That is a factor of 1.6, on the same drawing at the same size, where a single fixed order gave 26.

So gluing does make the sheet harder, and by very little. What gluing does is widen the distribution: it turns a search whose cost is the same whatever order is used into one where the order is worth three orders of magnitude, and a single measurement of such a search reports wherever the draw happened to land.

That is a different statement from the one these measurements have been carrying, and it is worth being exact about which part survives. The letters still go linearly and the search still does not. The last free letter is still worth more than all the others. What does not survive is the reading of the factor as a difficulty: twenty-six was the cost of one route through a space that has much cheaper ones in it.

The honeycomb sharpens it. Its three-period torus runs from 70 to 8,954 with three of eight orders giving up, and its cut sheet from 76 to 85 — so the glued sheet’s best route is cheaper than the cut sheet’s best route, on a sheet where a fixed order makes it fifty-five times dearer. At two periods the same thing: 30 against 37, with a band reaching 5,306 above it.

A sheet whose best route is cheaper and whose typical route is fifty-five times dearer is not a harder object. It is an object whose difficulty is concentrated in the choice of route, and gluing is what concentrates it.

Why the glued sheet’s best can beat the cut sheet’s #

That the torus is sometimes cheaper than the disc looks wrong and is not, and the reason is the same freedom count that explains the small sizes.

Gluing removes letters: it identifies a crease piece leaving one edge of the cell with the piece arriving at the opposite edge, so two letters become one. The four-period square torus has 128 free letters against the cut cell’s 144, and the honeycomb’s three-period torus 216 against 246. Fewer letters is less to decide, and a route that never has to backtrack settles the smaller sheet faster — which is exactly what the one-period sheets in the size sweep showed, where the torus was the cheapest object in the table.

So the glued sheet is both the smaller problem and the one with the dangerous space. A route that keeps propagating gets the benefit of the smaller count; a route that has to guess pays for a space where the identifications can contradict a guess made far away. The two effects are not in competition — they act on different routes — and a single measurement sees whichever one its seed lands in.

A cost that is not a number #

A quantity whose eight samples span three orders of magnitude is not usefully summarised by any one of them, and it is worth saying what it should be summarised by instead.

The minimum is what a search that restarts will find, and it is the quantity a practitioner cares about: run eight orders, keep the first that finishes, and the cost is the best of eight rather than the average. On these sheets that turns 1,800 into 69.

The median is what a single measurement estimates, and it is what every cost quoted for a glued sheet before this has been.

The failure rate is a third quantity and the one with no analogue below the threshold. One of eight orders on the four-period torus did not finish within its budget; on the honeycomb’s three-period torus, four of ten did not. A sheet whose cost is unbounded for some routes is not described by any statistic of the routes that finish.

Below the threshold all three coincide, which is why the distinction has never been needed. Above it they are three different facts, and the one a fixed-seed measurement reports is the middle one.

Why the variance is the interesting part #

A search whose cost depends on the order by a factor of 357 is a search whose space has a shape, and the shape is what the order is exploiting or missing.

The reading that fits the numbers is that the torus’s space has a small number of cheap routes and a great many dear ones. A cheap route places the letters that constrain the most first — which on a glued sheet means the letters lying where the gluing identifies two creases into one, because those are the ones whose choice propagates twice. An order that reaches those early settles the sheet almost as fast as a cut one; an order that reaches them late has already made guesses that the identification will contradict.

That is a testable account and it is not tested here. What would test it is a deliberate order — letters ranked by how many vertices their choice reaches — rather than eight random ones, and whether such an order lands near the 69 or well above it.

Which choice the cost lives in found that on these patterns the whole of the cost lives in the value order rather than the variable order, which is the opposite of where the literature looks. The measurement here is about the variable order and it does not contradict that: the eight seeds randomise both, and separating them again on a glued sheet is the obvious next thing to ask.

What this does to the numbers already on the record #

Several measurements in this line of argument are single draws, and it is worth saying which and what survives of each.

What the rim was doing reported forty-eight steps for a cut rectangle against fifty-six thousand seven hundred for the same drawing glued. The forty-eight is safe: a cut sheet’s cost barely moves with the order, so one draw estimates it well. The fifty-six thousand is a median at best, and the sheet’s cheapest route is not known.

Half the slack’s three orders of magnitude for the second gluing is the same shape of number, and its own text anticipated this: it expected a good deal of the factor to belong to the order. The expectation was right and understated.

Which pair is glued is the one that needs care, because its finding is a comparison between two glued sheets — twenty-four nodes one way and eighty-five the other — and both are draws from wide distributions. Two draws differing by a factor of three and a half, from distributions spanning three orders, is not evidence that the sheets differ. The finding survives on its other evidence, which is a count of letters and panels rather than a cost, and the cost column should be read as the weakest part of it.

None of these is wrong. Each reports what it measured. What changes is that a cost on a glued sheet is now known to be a sample, and a comparison between two samples from heavy-tailed distributions needs more than one of each.

What the eight orders are #

Eight seeds of the search’s own randomisation, which reorders both which letter is taken next and which value is tried first. They are not eight hand-designed heuristics, and nothing here says what a good order looks like — only that good ones exist and are common enough to be found in eight draws.

One budget for all of them. A run that reaches it is counted as a failure rather than as a large number, because what it spent is a fact about the cutoff. Counting it as its budget would make the mean meaningless; leaving it out makes the reported maximum a lower bound.

The same skeleton, the same pruning. Everything but the order is held fixed, including the two consistency tests and the sequence they are asked in, which pruning on proofs alone settled — so the spread is attributable to the route and not to what surrounds it.

And eight is a small sample of a heavy-tailed quantity. The maximum of eight draws from a distribution with a long tail is itself highly variable, so 24,636 should be read as at least this dear sometimes rather than as a worst case.

Eight is few, and what few can still say #

A reader entitled to be suspicious of eight samples should be, and it is worth being precise about what eight can and cannot carry.

Eight draws estimate a minimum badly and a median adequately, and they establish a spread as a lower bound. The statement this distribution spans at least a factor of 357 needs only two of the eight to be far apart; the statement its minimum is 69 is a claim that eight draws found nothing cheaper, which is weaker. So the argument here rests on the shape of the finding rather than on its precision: the cut sheet’s eight draws span 1.3 and the glued sheet’s span 357, and no amount of sampling error turns one of those into the other.

The one number that would move with more sampling is the one the essay leans on hardest — the glued sheet’s best, and therefore the factor of 1.6 against the cut sheet’s best. More draws can only lower it, so 1.6 is an upper bound on how much harder the glued sheet is at its best, which is the direction the argument needs.

The failure rate is the quantity eight draws describe worst. Three of eight is consistent with anything between one in ten and two in three, and nothing here pins it down.

What this does not settle #

It does not say the glued sheet is easy. Its best route is 1.6 times the cut sheet’s best, and finding that route took eight attempts. A method that had to commit to one order in advance would, on these numbers, usually do much worse.

It does not give a restart policy. The right number of attempts before abandoning one and starting another is decided by the shape of the distribution’s lower tail, and eight samples do not fix it.

It does not extend past the sizes measured. The four-period torus is the largest sheet that admits eight runs in a few seconds. Whether the best route stays within a small factor of the cut sheet’s at five periods, where the fixed order costs 2,927, is exactly the question this method is too slow to answer.

And it says nothing about the letterings found. Eight orders that finish may find eight different letterings or the same one; nothing here compares them, and on a sheet with many consistent letterings the cheap routes may be finding a different kind of answer from the dear ones.

The failure that has no mean #

The third quantity deserves its own paragraph because it is the one with no counterpart below a threshold.

Three of eight orders on the honeycomb’s three-period torus did not finish inside ten thousand nodes. One of eight did not finish on the square grid’s four-period torus inside twelve thousand. Those runs have no cost — they have a cutoff, which is a number chosen here.

A distribution in which some fraction of draws is unbounded is not summarised by any statistic of the bounded ones, and the honest reporting is the pair: the best of eight was 70, and three of eight did not arrive. The order that proves nothing exists is the essay about the other kind of unbounded cost — proving a negative, where the search must exhaust rather than find — and the two are different situations that look identical from outside a budget. A run that reaches its cutoff has not shown there is no lettering; on these sheets there certainly is one, since other orders found it.

That distinction is the reason a budget is reported rather than absorbed. A table that filled in a failed run with its budget would make a search that gave up look like a search that worked hard, and the two say opposite things about the sheet.

Still open: the order built rather than drawn #

The measurement replaces a number with a distribution and leaves the obvious question standing.

If cheap routes exist and are common, they can be constructed rather than sampled. The account above says which letters a cheap route takes first — those whose choice propagates through an identification — and that is a property of the glued skeleton computable before the search starts. Building the order from it and measuring where it lands in the distribution is a single experiment with three possible outcomes, all informative: at the bottom, and the account is right and the search is fixed; in the middle, and the account is wrong; below the bottom, and there are routes the sampling never found.

The second thing worth doing is to run the same eight orders across the size sweep rather than at two sizes. What that would give is the threshold of the best route as against the threshold of a typical one, and those two need not be the same size at all. A sheet whose typical order crosses at four periods and whose best order crosses at six is a sheet whose difficulty is an artefact of method up to six.

Sideways from here, this changes how every cost on this line of argument should be read. Half the slack’s three orders of magnitude, the sweep’s factor of forty-two, the rhombille’s 13,834 — all are single draws from distributions nobody has looked at. The cheap ones to re-run are the cheap ones, and the rhombille’s two-period cut sheet is the most interesting of them, because a cut sheet whose cost varies with the order would be a new thing entirely. The population the earlier work assembled for this purpose — the first one here a construction did not hand-pick — is the right place to run it at scale, since a distribution needs many objects as well as many draws.

The habit worth carrying is about measurements of algorithms. A cost that a random choice can move by a factor of three hundred is not a measurement of the problem, and the way to find out whether a number is one is to vary the thing that was seeded and look at the spread rather than the mean.