Equal effort was counted in steps

When symmetry costs required a circle packing — the first step of the tree method, where every flap of a model claims a disc of paper — to be its own mirror image, and compared it with a free search at the same effort. The shapes the optimum has ran the same comparison count by count to eleven discs, under a mirror, a half-turn and a quarter-turn, and found the result alternating with no pattern a designer could use. It also found the constrained search sometimes ahead, and explained that by dimension: a symmetric packing has about half as many coordinates, so the same restarts and steps cover a much smaller space.

It ended with two things. One was a test of that explanation: run the census past eleven discs, where the free search’s own shortfall grows, and see whether the constrained search’s advantage grows with it. The other was a doubt about its own reading — that a smaller space and a less rugged one could not be told apart by anything it had measured, and that “distinguishing them would need a search whose restarts and steps were varied independently, which is a straightforward experiment and is not this one”.

This is that experiment, and both explanations turn out to be beside the point.

Against the best packings known #

Every comparison so far was between two searches, because the optimal packings were only listed to nine discs. They are known well beyond that. The best packings of equal circles in a square have been proved optimal case by case, by computer-assisted search, beyond twenty, and six of the values used here — eleven, twelve, fourteen, sixteen, eighteen and twenty discs — are reproduced to twelve figures by tightening one of the searches’ own packings, which is the strongest check available that the numbers are the ones they claim to be. None of the eleven is beaten by anything either search finds, and the figures stop if one ever is.

The free search, at the effort every earlier essay used, is 0.13 per cent short of the best known packing at ten discs and 6.07 per cent short at twenty, and the climb in between is steady with one exception: sixteen discs, where the best packing is the four-by-four grid and the search’s starting grid finds it at once. The best of the three symmetric searches is ahead of the free one at eight of the eleven counts, by as much as 4.18 per cent at twenty discs, where the half-turn does best.

So the prediction holds. The free search’s shortfall grows, and the symmetric searches’ advantage grows with it. The explanation the earlier essay offered is confirmed on its own terms, which is exactly the point at which it is worth asking what else the same numbers would confirm.

The lead is bounded by the miss #

There is a ceiling on any constrained search’s advantage, and it is worth drawing before anything else. A symmetric packing is still a packing, so it can never beat the optimum; its lead over the free search can therefore never be larger than the free search’s own shortfall.

The points sit below the diagonal, as they must, and two of them sit almost on it. At thirteen discs the quarter-turn search recovers nearly all of the free search’s 1.13 per cent; at eighteen the half-turn recovers nearly all of its 3.08. Elsewhere the lead is a fraction of the miss, and at ten and eleven discs it is negative — the free search is nearly at the optimum there and the optimum is not symmetric, so a symmetric search can only lose.

Read this way, a symmetric search’s lead is a measurement of the free search’s failure, filtered through whether the optimum happens to be symmetric. That is what the smaller-space account says too. What it does not say is what kind of failure the free search is having, and that is where the two readings part.

The free search had found the arrangement #

A search like these has two ways to fall short. It can settle into the wrong arrangement — a local optimum, a different packing of the same discs — or it can find the right arrangement and fail to finish tightening it, leaving every disc a little short of the contacts it was heading for. A smaller space helps the first kind: fewer places to get stuck. The second kind is about something else.

They can be told apart directly. The flap nobody holds built a procedure that takes a packing and moves its discs only until every near-contact is an exact contact: it cannot change the arrangement, only finish it. Applied to a search’s output, it returns the local optimum the search was in, so whatever shortfall survives is the wrong arrangement and whatever disappears was unfinished work.

Tightened, the free search is within 0.2 per cent of the best packing known at eight of the eleven counts, and its tightened packing is at least as good as every symmetric search’s tightened packing at nine. At twenty discs the free search’s packing, 6.07 per cent short as returned, tightens to the best known packing exactly — to twelve figures — and that packing is its own mirror image and not its own half-turn, so the half-turn search, the one that led, could never have reached it. At eleven and fourteen discs the free search’s packing also tightens onto the optimum, and neither optimum is its own mirror image across the sheet’s vertical centre line, its own half-turn or its own quarter-turn — the three symmetries searched for.

Most of the free search’s shortfall, in other words, was not a wrong arrangement. It was the right arrangement, unfinished. And unfinished work is not what a smaller space makes easier to avoid. It is what a larger budget of moves makes easier to finish.

What a step moves #

Both searches were given the same restarts and the same steps, and the comparison was called equal effort. A step in these searches picks one disc and nudges it. In the free search the disc is any of the $n$, and its two coordinates are moved together. In a mirror or half-turn search the step picks one of about $n/2$ generators, and the symmetric partner follows. So at equal steps, each coordinate of a mirror search is moved twice as often as each coordinate of the free search, and a quarter-turn search’s four times as often.

The search’s own schedule says how much that matters. A step’s move is drawn from a range that starts at a fifth of the sheet and shrinks as the square of the steps remaining, down to a floor of 0.0015. Finishing a packing — turning near-contacts into contacts — needs moves much smaller than a disc, and only the last fifth of a restart’s steps have a range under 0.01, about a tenth of a disc’s radius at twenty discs. At 6,000 steps a restart that fine end gives each of the free search’s twenty discs about sixty moves, most of them rejected because they would shrink the radius. It gives each of the half-turn search’s ten generators about a hundred and twenty. A packing of twenty discs settles by every disc finding its contacts with its neighbours, and a disc with sixty chances in the fine end of the schedule is far likelier to stop short than one with a hundred and twenty.

That is not a smaller space; it is a larger share of the budget for each thing being searched. And it makes a prediction the smaller-space account does not: give the free search more steps, and the lead should go away, even where the optimum is symmetric.

At twenty discs and thirty restarts, the half-turn search leads by 8.39 per cent at 3,000 steps a restart and by 4.43 at 6,000. At 12,000 steps the lead is 0.13 per cent. At 24,000 it has reversed, and the free search leads by 1.62 per cent; at 48,000 by 1.71, with the free search 0.15 per cent short of the best packing known and the half-turn search stuck near 1.9. The same sweep at seventeen discs under a mirror reverses at 12,000 steps.

Restarts were not the effort that mattered. At seventeen discs, raising the restarts from 15 to 480 at a fixed 6,000 steps shrinks the mirror search’s lead from 2.07 to 0.41 per cent, slowly, because more restarts give the free search more chances to draw a run that happens to converge. Doubling the steps does the same in one move, because it lets every run converge.

Equal effort, counted per coordinate #

The cleanest version of the comparison gives each search the same number of moves for each coordinate it has. For a mirror or a half-turn, whose generators are half as many as the free search’s discs, that means the free search gets twice the steps.

At equal steps, the better symmetric search leads by as much as 4.43 per cent. At equal moves per coordinate, no symmetric search leads by more than 0.56 per cent at any count from ten to twenty, and the free search leads at eight of the eleven. The largest remaining lead is at eighteen discs, where the best known packing is itself both a mirror image and a half-turn of itself, so the symmetric search is searching for exactly the right thing and the free search is not told it.

That is the residue a symmetry genuinely buys, and it is small: when the optimum has the symmetry imposed, the constrained search finds it a little more reliably at the same moves per coordinate. Everywhere else, the constraint costs what when symmetry costs first said it would — the arrangements it excludes — and the apparent gains were the free search being starved of moves.

The census, continued #

The count-by-count reading the earlier essay made to eleven discs is worth extending in its own terms, because a designer choosing a symmetry for a twelve- or twenty-flap model still faces it at whatever effort their software uses.

Under a half-turn at the earlier effort, the constraint matches or beats the free search at seven of eleven counts and costs more than one per cent at two. Past twelve discs the bars sit mostly below the line, and the earlier essay’s “no pattern anybody could use” has become a pattern: at the effort design software ordinarily spends, a symmetric layout is more often ahead than behind once the flaps are many. The figures above say why, and the why changes what to do about it. A designer who wants the better packing should spend more steps, not impose a symmetry, unless the symmetry is wanted for its own sake.

The two twenty-disc packings, side by side, make the point visible. The free packing at that effort is loose: the right arrangement, with discs that have not finished pushing their neighbours away. The half-turn packing is tight and wrong — a symmetric arrangement fully converged, which is a different packing from the optimum and cannot become it.

A sweep, not a step #

The accounting mistake here has a name in a neighbouring field. A Markov chain Monte Carlo sampler that updates one coordinate at a time is compared with another by sweeps — one update of every coordinate — rather than by single updates, because a sampler on a hundred coordinates that is given as many updates as a sampler on ten has given each coordinate a tenth of the attention. The searches here are of exactly that kind: annealed coordinate moves, one disc at a time, with a step size that shrinks on a schedule. Counted in sweeps, the free and the symmetric searches were never given equal effort.

The same caution runs through the folding searches elsewhere. A failure teaches a schedule nothing found that the unit in which a restart schedule is written decides most of what it costs, and stopping is cheaper than finishing priced a search by a cutoff in nodes. In each case the comparison is only as fair as its unit, and the unit that looks natural — a node, a restart, a step — is the one that has to be checked against what it actually does to the thing being searched.

What the earlier accounts got right #

The smaller-space account was right that the comparison was between two searches and not two optima, and right that a constrained search can win. It was right that its two explanations — a smaller volume to cover, and a less rugged landscape — could not be separated by what it had measured. Both were explanations of a search finding the wrong arrangement less often. What the tightening shows is that the free search was mostly not finding the wrong arrangement at all.

Getting close instead of getting it right made the general version of the point long before any of this: a search’s answer is a report about the search as much as about the problem. Here the report was about the search’s step budget, and it was being read as a report about symmetry.

What tightening cannot settle #

Whether a better search would close every gap. At fifteen, seventeen and nineteen discs the tightened free packing is still 0.17 to 1.22 per cent short, so at those counts the free search did sometimes settle into the wrong arrangement. More restarts, or a better search, would presumably find the optimum; nothing here shows that the gap closes rather than shrinks.

Unequal discs. Every packing here has equal discs, which is the case the optimum is known for and not the case a real design presents. With unequal flaps the optimum is not known, and the yardstick that made this experiment possible does not exist.

Whether the best packings for these counts are as published. Six of the eleven are reproduced to twelve figures from the searches’ own packings and none is beaten; the other five are taken from the literature, with the figures required to stop if anything ever beats them.

The search, named #

An annealed coordinate search. Each restart starts from random centres (the first from a grid) and makes a fixed number of steps; each step moves one disc, or one generator of a symmetric arrangement, by a random amount that shrinks as the steps run out, and keeps the move if the radius does not fall. The radius of a packing is half the closest distance between centres, limited by the walls. Tightening moves discs only to turn near-contacts into exact ones and cannot move a packing to a different arrangement.

Nothing may beat the best known #

Every packing is held to the best known one. Free, symmetric and tightened packings alike are required not to exceed the best known radius for their count, and a figure that found one exceeding it would stop rather than draw.

The lead is required to stay under the shortfall at every count, which no correct search can violate; the tightened free packing is required to be within 0.2 per cent of the best known at half the counts or more and at least as good as every symmetric search’s tightened packing at more than half; the step sweep is required to start with the symmetric search ahead by more than two per cent and end with it behind; and the equal-moves comparison is required to show the lead above three per cent at equal steps and under one per cent everywhere at equal moves per coordinate.

Still open: what a symmetry is for #

With the step budget accounted for, the case for imposing a symmetry on a packing is no longer about search. It is about the design. The symmetry the letters cannot keep found that a symmetric drawing does not guarantee a symmetric folded object, and the symmetry a gluing adds found a symmetry that comes free with a periodic sheet. A symmetric packing is worth its price only if the model’s symmetry survives every later stage — the crease pattern built from the packing, its lettering, its folded layers — and that chain has not been followed for a single packing.

The other open question is the residue. At eighteen discs, where the optimum has the symmetry imposed, the symmetric search kept a lead of about half a per cent at equal moves per coordinate. Whether that is a smaller landscape genuinely being easier, or one more accounting effect not yet found, is the experiment the earlier essay wanted, now with the step budget out of the way: hold the moves per coordinate fixed, vary the restarts, and see whether the symmetric search’s success rate per restart is higher where the optimum is symmetric.

The habit worth carrying is about effort. Before comparing two searches at equal effort, count what one unit of effort does in each. A step was the same unit in both searches and moved twice as much of one of them, and every lead the comparison reported past eleven discs was that factor of two, read as a fact about the space being searched.