The composition that is hard is not the full one

Twelve basins where there were two counted the local optima of an arrangement problem — which sites of a lattice to raise, so as to bind the electrons best — and found two basins on sixteen sites and twelve on thirty-six. It measured each net at one composition, chosen so that the two were comparable fractions, which leaves the obvious next question: where does the hard composition sit, and is it the half-filled one?

It is not. It is the easiest, and the reason is a symmetry rather than a count.

The curve is not monotone #

On sixteen sites at a contrast of one, the share of starts that reach the best arrangement runs 100, 100, 100, 33.5, 21.0, 67.0, 100, 100 per cent as the number of raised sites goes from one to eight. It falls into a trough between a quarter and a third full and comes back out.

On thirty-six sites at the same contrast it runs 100, 50, 45, 10, 80, 100 at two, four, six, nine, twelve and eighteen raised. The trough is at nine — a quarter — and half filling is at the top.

Nothing about that shape is what a count of arrangements would give. The arrangement a count cannot pick established the same thing about the predictor: counting unlike bonds does not decide which arrangement wins, and counting arrangements does not decide how hard it is to find the one that does. The number of ways to choose $m$ sites of $n$ rises monotonically to $m = n/2$ and is largest there by a wide margin, so a difficulty that tracked the size of the search space would rise all the way to the right-hand end of every curve.

The count of local optima says the same thing in a different currency. It peaks in the same place the hit rate troughs, and falls back to one at both ends. On thirty-six sites at a contrast of four it reaches twelve distinct optima at a third filling, which is the largest number measured in any of these landscapes, and falls to three at half filling.

The largest space is the easiest problem #

The two quantities can be put on one axis, and the comparison is the point of this essay.

Half filling on thirty-six sites has $9.08\times10^{9}$ arrangements. A quarter filling has $9.4\times10^{7}$ — a hundredth as many. The first is found by every one of twenty random starts and the second by two of them.

A search space two orders of magnitude larger is a hundred times easier to search. That is not a paradox and it is not a statement about the search; it is a statement about the surface. What makes a landscape hard is the number of arrangements that cannot be improved by a single exchange, and that number has nothing to do with how many arrangements there are.

The cost of a search does rise with the composition, and it rises monotonically, which is worth separating from the difficulty because the two are easy to conflate.

One ascent at half filling on thirty-six sites costs 2,771 energy evaluations against 1,362 at a quarter filling, because each step considers $m(n-m)$ exchanges and that is largest in the middle. So the half-filled composition is the most expensive point on every curve and the easiest. Cost and difficulty are two monotone functions running in opposite directions, and only one of them is what a budget should be set by. A budget set by the cost of one ascent would spend the most where the fewest starts are needed.

Why half filling is different #

The half-filled point is not merely an easy composition. On the larger net at a contrast of one it has exactly one local optimum, which no other composition here manages above two raised sites.

The reason is in the arrangement rather than in the search. A square net is bipartite, and at half filling the two-colouring — every raised site surrounded by lowered ones and the reverse — is the unique arrangement in which every bond is unlike. The energy this model is maximising rises with the number of unlike bonds, so that arrangement is the maximum, it is unique up to swapping the two colours, and any single exchange strictly worsens it. A landscape with one strict maximum and no others is a landscape a hill climb cannot fail on. It is the arrangement version of two structures with the same neighbours: the count of unlike bonds is a second moment of the arrangement, and at half filling on a bipartite net it has a unique maximiser, which is exactly what it lacks everywhere else.

Away from half filling there is no such arrangement. With nine raised sites of thirty-six the best possible is a compromise — some raised sites must neighbour each other, or leave lowered sites with too few unlike neighbours — and there are several ways to be an equally good compromise. The optima proliferate exactly where the symmetry that would pick one out is absent.

That reading has a check in it. At a contrast of four the half-filled point has three basins rather than one, and its hit rate falls to 80 per cent. A larger contrast makes the site energies matter more relative to the hopping, and the arrangement that maximises unlike bonds stops being the unique best; the two-colouring is still a good arrangement and is no longer the only one. So the argument predicts the direction, which is the least a mechanism should do.

There is one more thing the half-filled column says, and it is about the earlier calibration rather than about this sweep. That calibration — the composition at which the local search was checked against an exhaustive enumeration on sixteen sites — was six raised of sixteen, which is three eighths and sits on the near side of the trough. That was a good choice by accident: it is one of the two compositions on that net where the landscape has more than one basin at either contrast, so the calibration was made where there was something to calibrate. Had it been made at half filling it would have found one basin, a hundred per cent hit rate, and no information at all about how a search fails.

The hard composition moves #

Which composition is hardest is not a property of the net.

On thirty-six sites the hardest point is nine raised at a contrast of one and twelve at a contrast of four. On sixteen it is five at a contrast of one and six at a contrast of four. In every case it lies between a quarter and a third, and in every case a change of contrast moves it.

That matters for the practical use of a local search. A calculation on a hundred sites cannot enumerate anything and has to decide how many starts to spend; the earlier warning was that the number depends on the size of the net. It also depends on the composition and on the contrast, and the dependence is not monotone in either — so there is no rule of the form spend more starts on larger compositions. The only honest calibration is the one done here: measure the hit rate where the exhaustive answer exists, and carry the shape rather than a number. That is the same discipline the account of what holds a solid together needed when its predictor was checked against the cases where the answer was known.

What a missed basin costs #

The sharpest earlier finding was that missing the best basin costs almost nothing in energy and everything in structure. Across the sweep that stays true and its size varies enormously.

The gap between the best arrangement and the second spans five decades — from $1.3\times10^{-4}$ per cent to 2.3 per cent — and the smallest gaps sit at the compositions with the most optima. On thirty-six sites at a contrast of one, four raised sites gives four basins whose top two differ by $2.1\times10^{-3}$ per cent, and nine raised gives six basins whose top two differ by $1.3\times10^{-4}$ per cent.

A calculation reporting energies to four figures cannot tell those apart. It would report the same number for two different structures and would have no indication that a choice had been made.

The gaps are largest, in relative terms, where the landscape is simplest — 2.3 per cent at half filling on the larger net at a contrast of four, where there are only three basins and the second is plainly worse than the first. So the two quantities a search can get wrong move together in the helpful direction: where there are many optima the choice between them is nearly free in energy, and where the choice is expensive there are few of them. That is a comfort about the energy and not about the structure, and the structure is the answer that matters.

What was computed, and how #

The energy is a tight-binding one. A net of $n$ sites carries $m$ raised sites at a site energy $\Delta$ above the rest, the matrix is diagonalised exactly, the levels are filled with one electron per site, and the total is the binding energy per site. Nothing is fitted and there is no repulsion term, which is this collection’s standing caution about a band.

A steepest ascent starts from a random composition and repeatedly makes the single exchange — one raised site swapped for one lowered — that raises the energy most, until no exchange raises it. Two hundred ascents are run at each composition on sixteen sites and twenty on thirty-six, from the same seeded generator, and the distinct optima are counted by their energies to nine figures.

The hit rate is the share of starts arriving at the best optimum found, and the number of starts for a ninety-nine per cent chance follows from it as $\lceil\ln 0.01/\ln(1-p)\rceil$.

Three things are checked and one of them is a refusal of the whole reading. The half-filled point must have a higher hit rate and no more optima than the hardest point of its own sweep. The hardest point must lie between a seventh and a half full, which is what says the trough is where it is claimed and not at an end. And the smallest composition must return exactly one basin at a hundred per cent, which is the control: with two raised sites of thirty-six there is nothing to get wrong, so a census reporting several optima there would be reporting its own noise rather than the landscape.

The last check is the one that would fail if the difficulty were the size of the search space: the easiest composition is required to have the larger number of arrangements, and it does, by a factor of ninety-seven.

The sweep on the larger net is six compositions rather than eighteen, and the reason is cost rather than choice. One ascent there is a few thousand diagonalisations and twenty ascents at one composition is the whole of the earlier measurement; six points a contrast is what can be added without turning the sweep into a different kind of job.

Where the model stops #

Twenty starts is not many. A hit rate of ten per cent measured over twenty starts is two starts, and its uncertainty is large — the difference between ten and fifteen per cent is not resolved here. What is resolved is the shape: the trough is a factor of five to ten deep and the half-filled point is at the top, and neither of those is inside the noise of twenty.

More seriously, the number of basins is a lower bound. Twenty ascents cannot find a basin that takes one start in a hundred, so the twelve reported at a third filling on thirty-six sites is what twenty starts saw, not what is there. That biases every number in the same direction, and it biases them most where the landscape is roughest — so the trough is at least as deep as it looks and the half-filled point at least as clean.

Only one lattice is swept. A square net is bipartite, and the argument for half filling turns entirely on that: a triangular net has no two-colouring, so its half-filled composition has no unique unlike-bond arrangement and should show none of this. That is the first thing to check and it is not checked here.

And the model has no repulsion in it. A real alloy’s arrangement is decided by electrostatics as much as by band energy, and at half filling on a bipartite net the two effects happen to want the same thing — which is the one composition where a model missing a term would be least likely to notice.

The generalisation #

The size of a search space and the difficulty of searching it are unrelated quantities, and the intuition that ties them together is wrong in both directions. What makes a landscape hard is the number of configurations from which no single move improves anything, and that count is governed by frustration — by how nearly the constraints can all be satisfied at once — rather than by how many configurations exist. The same fact appears in an ascent that misses a basin worth a ten-thousandth of a per cent and in an alloy whose properties are not the average of its ends.

And a symmetry that makes an optimum unique makes a search exact. The half-filled bipartite case is easy for the same reason a symmetry-forced degeneracy is exact: there is a statement about the arrangement that does not depend on the energetics at all. Wherever a problem has such a point, the point is a calibration and not a typical case — which is exactly how the sixteen-site enumeration was used, and is a warning about using half filling the same way.

Who found it, and when #

That antiferromagnetic and antisite orderings are unfrustrated on bipartite lattices at half filling, and frustrated away from it, is the oldest fact in lattice statistical mechanics; it is why the Ising antiferromagnet on a square net is exactly solvable and on a triangular net is not. The connection to the difficulty of a local search is standard in the optimisation literature, where the hardest instances of a constraint problem sit at intermediate constraint densities rather than at the extremes.

What is done here is to measure it on this arrangement problem, with the exhaustive answer available at one end for calibration, so that the shape is measured rather than borrowed. The finding that the easiest composition has the largest search space is the version of that fact which is most useful to somebody deciding how many starts to spend, and it is the one a count of arrangements would get exactly backwards.

Still open: the non-bipartite net, and more starts #

The obvious open question is the non-bipartite net. The whole explanation above rests on the two-colouring, and a triangular net has none — so its half-filled composition should have no unique optimum, its trough should not recover at the right-hand end, and the curve should look quite different. Triangular nets are easy to build and the census runs on them unchanged, so the test is a sweep rather than a construction, and it is the one measurement that could refute the reading rather than confirm it. A surface is not a count of broken bonds is another case where a counting argument holds on one geometry and fails on another.

The nearer question is the number of starts. Everything above is twenty ascents a point on the larger net, which bounds the basin count from below and leaves the deep trough at a hit rate measured from two successes. Running the hardest composition alone at four hundred starts would say whether the twelve basins are twelve or forty, and whether the ten per cent is ten or three — and it is one composition rather than a sweep, so it costs what one point of this sweep cost.