Twelve basins where there were two

An exhaustive census enumerated every arrangement of a given composition on a wrapped net of sixteen sites and asked whether the one that binds best is always the one with the most unlike neighbours. At a small contrast it is, at every composition. At a large one it is not, and what decides there is how the low sites are joined to one another rather than how many unlike edges there are.

That result is exhaustive and it is about sixteen sites. Twelve raised sites among thirty-six is 1,251,677,700 arrangements, and there is no version of this calculation that visits them. So every question of this kind past about twenty sites has to be asked of a local search — start somewhere, improve until nothing improves — and a local search returns whatever basin it happened to land in.

The obvious thing to do about that is to measure it: run the local search on the net where the exhaustive answer exists, see how often it agrees, and carry that figure to the net where nothing can check it. The figure does not carry.

The search, and why it is the strong version #

The move is the smallest one that keeps the composition fixed: take a raised site and a lowered one and exchange them. Every such exchange is evaluated — for twelve raised among thirty-six that is two hundred and eighty-eight diagonalisations — and the best improving one is taken. When no exchange improves the binding, the arrangement is a local optimum by definition rather than by any convergence criterion.

Taking the best improving move rather than the first is deliberate and costs a factor of a few hundred. A first-improvement rule is what anybody in a hurry writes, and it finds worse optima, so the weakness measured below would then be partly the search’s own. Using the strong version means what is measured is the landscape.

Each start is a random composition drawn from the file’s own generator, so the whole census repeats exactly. Two hundred starts on sixteen sites, twenty on thirty-six, which is where the arithmetic puts the two runs at comparable cost — one ascent on sixteen sites uses about a hundred and eighty diagonalisations and one on thirty-six uses about fifteen hundred.

On sixteen sites the search is almost exact #

The calibration is the point of having a net small enough to enumerate.

The best of two hundred ascents is the best of all 8,008 arrangements, at both contrasts, to nine figures. The landscape has exactly two local optima. Sixty-seven per cent of random starts reach the better one at a contrast of one and fifty-nine per cent at a contrast of four, which means five starts give a ninety-nine per cent chance of the global answer and six starts give it at the harder contrast.

That is a very good instrument. If the number carried, a search of a few dozen starts would be a near-certainty on any net, and the whole difficulty of these problems would be the cost of one ascent.

On thirty-six it does not #

The same search, the same contrasts, the same move set, on a wrapped square net of thirty-six.

At a contrast of one, four basins from twenty starts and eighty per cent of them reach the best. Still a good instrument, slightly worse.

At a contrast of four: twelve distinct local optima out of twenty starts, and two of the twenty reach the best of them. A ten per cent hit rate means forty-four starts for a ninety-nine per cent chance — and that arithmetic is only available because the hit rate was measured, which required the starts. On a net where nobody has run twenty ascents, nobody knows whether they need five or forty-five.

The two contrasts differ in exactly the way the census predicts they should. At a small contrast the electrons see the whole net and the binding is close to a smooth function of how many unlike bonds there are, which is a landscape with one hill in it. At a large contrast the electrons live on the low sites alone, the binding is about how those sites are connected, and that is a combinatorial quantity with many nearly-equal arrangements — the same reason the count stops predicting, seen as a property of the search rather than of the winner.

The easy contrast is a different problem, not an easier one #

It is worth looking at the small-contrast landscape on the enumerable net, because it explains why the search does so well there and why that says nothing about the other case.

At a contrast of one the binding is nearly a linear function of the unlike-bond count, which is a sum over bonds and therefore has one maximum and a wide slope leading up to it. Exchanging any pair of sites moves the count by a definite amount and moves the energy with it, so almost any starting point walks uphill to the same place.

At a contrast of four the count is no longer what the energy is a function of, and the quantity that replaces it — how the low sites are connected to one another — is a property of a subgraph rather than of an edge count. Two structures can agree on every count and differ in what they bind, which is exactly the situation that produces many arrangements of nearly equal energy and no smooth slope between them.

So the two contrasts are not the same problem at two difficulties. One is an optimisation over a nearly additive quantity and the other is not, and only the second is what an alloy at a real contrast poses.

Missing costs nothing in energy and everything in arrangement #

The twelve basins are extremely close together. The second is 0.0068 per cent below the first; on sixteen sites at the same contrast the second was 0.096 per cent below, and at the small contrast it was 1.8 per cent below.

So the situation gets worse in the only sense that matters here. A search that stops in the wrong basin on the large net returns a binding energy that is right to four figures and an arrangement that is a different structure. Anybody quoting the energy is fine. Anybody quoting the arrangement — which is what a question about ordering in an alloy is — has a wrong answer that no internal check can see, because the energy it comes with is indistinguishable from the right one.

This is the shape a localisation search met from the other end, where a search over cage descriptions had basins in two groups with a gap between them, and the gap was what made count the large basins and stop a defensible rule. There is no gap here. The twelve run continuously from 2.230468 down to 2.227320 with nothing separating them, so the same rule is unavailable and the honest report is a list rather than a winner.

The clever seed is beaten #

There is one obvious way to do better than a random start, and it is the census’s own result: begin from an arrangement with the most unlike bonds and improve it. On a net with no odd cycle that arrangement is a subset of one colour class, so it is free to construct at any size.

On sixteen sites at both contrasts, and on thirty-six at the small contrast, the count-based seed climbs straight to the best arrangement found. On thirty-six at the large contrast it reaches 2.22569848 and a random start reaches 2.23046805 — and the winner has twenty-four unlike bonds against the seed’s twenty-eight.

Fewer unlike bonds and more binding. That is the census’s failure mode arriving in the one place it cannot be checked exhaustively, and arriving as a practical failure rather than a conceptual one: the natural clever starting point is worse than a random one there, and the only evidence for that is a search that could itself be wrong.

What was computed, and how #

Every arrangement’s binding is the sum of the occupied levels of a real symmetric matrix — the net’s adjacency with the raised sites carrying $+\delta$ and the lowered ones $-\delta$ — divided by the number of sites, with two electrons a level and the band half filled. The eigensolver is checked against closed forms, and every eigenpair is required to satisfy $Av = xv$ before the levels are summed.

The exhaustive enumeration walks compositions in lexicographic order, which is what makes 8,008 diagonalisations a few seconds rather than a memory problem. The censuses are cached, and the cache verifies what it restores by recomputing one arrangement’s energy from its own site list rather than by trusting the key.

The calibration is the load-bearing part and is tested rather than reported: the best of two hundred ascents on sixteen sites must equal the best of all 8,008, at both contrasts. A search with a bug in its move set would still return a plausible landscape with plausible basins, and this is the only statement here that could catch it.

The refusal is the smallest composition. With one raised site every arrangement is a relabelling of every other, so every start must reach the same energy and the census must report one basin. A search reporting several there would be reporting numerical noise as structure.

Where the model stops #

It is worth saying what a basin count is and is not evidence about. A local search stopping in twelve distinct places says the energy surface has twelve local minima reachable from the starts that were tried; it does not say the surface has twelve, because a basin nothing reached is a basin nothing counted. Every number here is therefore a lower bound, and the lower bound tightens with the number of starts rather than converging on anything the model can promise.

What makes the reading safe is the direction of the claim. The claim under test is that a local ascent on this energy finds the arrangement, and a single counter-example is enough to refute that — twelve is not needed and neither is the exactness of twelve. The count matters only for the second half, which is how often a practitioner running one ascent gets the best arrangement, and that is a statement about the starts that were run rather than about the surface.

The composition is held fixed throughout, which is what makes the search a search over arrangements rather than over compositions. That is the right question here and it is not the only question: what holds a solid together at all depends on how many electrons there are as much as on where they sit, and a search allowed to change the composition would be answering something else.

Everything here is one-electron and has no repulsion in it, so nothing above is a statement about a real alloy — what actually orders a mixture has a chemical term this model does not carry, and the sign of the ordering can come from either. What is being measured is the difficulty of a search on a landscape this model produces, and a landscape with more physics in it will not be smoother.

The two nets are both wrapped, so neither has a surface, and a surface is where a real arrangement problem is hardest. A slab’s arrangement problem has a broken symmetry and more inequivalent sites, which can only add basins.

The move set is a single exchange. A search allowing two exchanges at once would see a larger neighbourhood, find fewer local optima and cost the square of the diagonalisations — and where that trade lands is a real question not answered here. What can be said is that the twelve basins reported here are twelve for this neighbourhood, and the number is a property of the pair rather than of the landscape alone.

The generalisation #

The useful statement is not that a local search is weak. It is that the strength of a local search is not transferable between sizes, and it degrades exactly where the physics gets interesting.

Both contrasts here are the same model with one number changed. At the contrast where the answer is boring — the arrangement with the most unlike bonds, as anybody would guess — the search is nearly infallible on both nets. At the contrast where the answer is not guessable, the search is nearly infallible on the small net and fails nine times in ten on the large one. A method calibrated in the easy regime and carried into the hard one would have reported confidence that is wrong by a factor of six in the number of starts required.

That is the same shape as an exponent measured over one window and quoted as a property and a constant measured on one lattice and quoted as arithmetic: a quantity is established where it can be established and then used where it cannot, and the only defence is to vary the thing the establishing did not vary. Here that thing is the size, and it is the one variable the calibration cannot hold fixed.

Who found it, and when #

Local search on a discrete arrangement energy is old and is not anybody’s in particular; what is borrowed from the literature here is only the ascent rule, which is the least a search can be. The finding is about the landscape rather than the algorithm, and a better algorithm would find the same twelve basins faster rather than find fewer of them.

The picture of a rugged energy landscape with many nearly-degenerate minima is the spin-glass literature’s, from the nineteen-seventies onward, and the specific observation that the number of local optima grows while their energies crowd is what makes those problems hard rather than merely large. The arrangement problem here is a lattice-gas problem of the kind Ising models are written for, and its hardness in the general case is a known result: deciding the ground state of a spin glass on a non-planar graph is NP-complete, from Barahona in 1982.

None of that is being demonstrated here. What is being done is much smaller and is the thing usually skipped: putting the weak instrument beside the exact one on a problem where both run, and writing down by how much the weak one is weak.

Still open: more starts, an intermediate size, and the composition #

The cheapest next measurement is the one that would say whether twelve is near the truth. Running the same ascent from ten times as many starts and watching the count stop rising is the standard way to bound a basin census, and it costs nothing here — the ascent is a few site swaps on a lattice of a few dozen. If the count is still climbing at forty thousand starts, the surface is rougher than twelve basins and the practical warning is stronger than the one stated above.

The obvious open question is the size in between. Sixteen and thirty-six are the two ends of this measurement and there is nothing between them; a wrapped net of twenty-five is enumerable at some compositions and has an odd cycle, and one of thirty-two is not square but is bipartite and is enumerable at small compositions. Two more points would say whether the hit rate falls smoothly with the number of sites or falls off a cliff somewhere, and those are very different things to carry into a calculation on a hundred sites.

The nearer question is the composition. Everything here is at one composition on each net — six of sixteen and twelve of thirty-six — chosen so that the two are comparable fractions. The census found that the count predicts at every composition below its contrast threshold, so the landscape presumably simplifies towards the ends where there are few arrangements to begin with. Where the hardest composition sits, and whether it is the half-filled one, is a sweep of the same census and it would say which part of a phase diagram a local search should not be trusted in.