Valleys a search cannot count

Where charges settle on a sphere let equal charges push each other apart on a sphere until nothing moved, and found the arrangements they settle into: a tetrahedron for four, an octahedron for six, an icosahedron for twelve, and something other than a cube for eight and other than a dodecahedron for twenty. It noted in passing that the search behind those pictures could be trusted for small numbers of charges, because every random start ended in the same place, and that for 72 and 110 charges it could not, because different starts ended in different places.

This essay measures that change. For every number of charges from 4 to 32, and every fourth number up to 64, it starts the charges from random positions dozens of times, lets each run descend to rest, and counts the distinct arrangements — the valleys of the energy — that the runs end in. The question is where the landscape first acquires a second valley, how fast valleys multiply, how often a single run finds the deepest, and how much deeper the deepest is than the rest. The answers explain why a problem posed in 1904, whose arrangements anyone can compute in a second, has been proved for only six numbers of charges.

Descending from a random start #

The energy of $N$ charges at points $x_1, \dots, x_N$ on the unit sphere is the Coulomb energy

$$E = \sum_{i < j} \frac{1}{|x_i - x_j|},$$

and every charge is pushed by every other along the line between them. A descent moves each charge a little in the direction of the total push, keeps only the part of the move along the sphere’s surface, puts the charge back on the sphere, and repeats. The step lengths here are chosen by the Barzilai–Borwein rule, which estimates the curvature of the landscape from the last two steps, with a fallback that halves the step whenever the energy would rise. A run is counted as finished when the sideways push on every charge has fallen below a millionth; every run in this essay finished, so none had to be discarded.

A finished run is at a point where the energy cannot be lowered by any small movement of the charges — a local minimum, or valley. Two runs are counted as having found the same valley when their energies agree to seven significant figures. The energy cannot tell apart two arrangements that are rotations or reflections of each other, and it should not: those are the same arrangement, seen from elsewhere. It could in principle merge two genuinely different valleys of nearly equal energy, but at seven figures the valleys found here are well separated.

The starts are spread uniformly over the sphere, independently for each charge, and the runs are many: 60 for each number of charges up to 32, 40 above, and 200 for fifty-five charges in the last figure. The counts are therefore lower bounds. A valley that no start happened to fall into is not counted, and narrow valleys are the likeliest to be missed.

One valley up to fifteen charges #

For four to fifteen charges every start, sixty times over, ends in the same arrangement. The landscape has one valley, and a descent from anywhere finds the answer — which is why the small cases in the essay before this one could be trusted without proof. For five charges the answer is a triangular bipyramid, two charges at the poles and three round the equator, and it was proved to be the true minimum only in 2010, by Richard Schwartz, with a computer-assisted argument; the descent finds it in milliseconds, and the gap between finding and proving is the subject of this essay in miniature.

Sixteen charges have two valleys. In the hero figure both are drawn: the lowest, with energy 92.911655, and another at 92.920354. The second is a genuine valley, not a slow place on a slope; the runs that end there have no sideways force left on any charge, and any small rearrangement raises the energy. Its triangulation is visibly different, with a charge at the centre of the picture surrounded by a ring of six where the lowest has a less regular pattern. One start in five ends there.

After sixteen the pattern is irregular. Seventeen to twenty-one have one valley each, as far as sixty starts can tell; twenty-two and twenty-nine have two; thirty-two shows only one here, though a rare second valley turned up in a trial run with other starts. From forty on, every number tried except forty-four and forty-eight has at least three, and fifty-two and sixty-four have four. The count is not monotone in $N$, because the valleys come from particular ways of placing the twelve defects that every triangulation of the sphere must carry — twelve pentagons, whatever the hexagons derived that number from Euler’s formula — and how many good ways there are depends on how $N$ fits round a sphere, not only on its size.

How often a single search is right #

The count of valleys matters less than the share of starts that find the lowest one, because that is the chance a single search returns the right answer.

For twenty-two and twenty-nine charges the second valley is narrow, and 98% of starts find the lowest. For sixteen it is 80%. For forty it is 68%, for fifty-two 45%, for sixty 38%, and for fifty-six charges only 10%: six starts in sixty reach the lowest arrangement, and the other fifty-four settle in two valleys a few parts in a million higher. A search that started once and reported what it found would be wrong nine times in ten.

The difficulty does not grow steadily with $N$ either. Sixty-four charges have four valleys, more than fifty-six, yet 82% of starts find the lowest; for sixty-four the deepest valley also has by far the widest basin, while for fifty-six it has one of the narrowest. How hard a given number of charges is to solve by search depends on how its basins happen to be shaped, and that is not something the number itself reveals. A search tuned on one $N$ — enough starts to be confident at sixty-four, say — can be badly overconfident at fifty-six.

Nothing about a wrong answer marks it as wrong. A run that ends in a higher valley ends with no force on any charge, a symmetric-looking triangulation and an energy indistinguishable from the best to five significant figures. The only evidence that a better arrangement exists is another run that finds it, and the only evidence that none exists is that no run ever has. That is why the published lists of best-known arrangements are compiled by running enormous numbers of starts and keeping the lowest, and why each entry is a record, not a theorem.

Valleys a hair apart #

The valleys are extraordinarily close in depth. The second valley of sixteen charges is one part in 10,700 above the lowest; the second of twenty-two, one part in 9,000, the widest gap found. For fifty-six charges the second valley is three parts in ten million above the lowest, and for fifty-two, sixty and sixty-four the gaps are a few parts in a million.

That closeness is the reason the valleys exist at all. For large $N$ the energy is dominated by a term that depends only on $N$ — about $N^2/2$, the energy of charge smeared evenly over the sphere — and then by a correction proportional to $N^{3/2}$ that measures how well the charges form a nearly flat triangular mesh. Neither term cares where the twelve defects sit. What does care is a much smaller residue, the strain the defects cause in the mesh around them, and moving defects about changes the energy only in that residue. Different placements of the defects give different valleys, and their depths differ by the strain alone. Each defect is a shortfall of 60 degrees of angle round one charge, and seven hundred and twenty degrees of gap found those shortfalls adding to exactly 720 on any closed convex surface, which is why the twelve are compulsory and only their positions are free. The number twelve belongs to the sphere, not to the charges. Every surface is a sphere with handles sorted closed surfaces by their Euler characteristic, and a triangulation’s total shortfall is six times that number: twelve on a sphere, nothing at all on a torus. Charges on a doughnut-shaped surface can, for suitable numbers, form a perfect six-neighbour mesh with no defects to place, and the valleys that come from choosing where to put defects do not arise there. The sphere’s valleys are, in this sense, a consequence of its topology: the twelve defects have to go somewhere, there are many nearly equally good places, and each good placement is a valley. The highest point on the sphere is an eigenvalue found the opposite kind of problem on the same sphere, where a quadratic form has no false peaks and linear algebra goes straight to the answer; Coulomb’s energy has none of that structure, and its valleys are separated by almost nothing.

Two hundred starts for fifty-five charges #

With two hundred starts, fifty-five charges show six valleys, the highest only 0.027 above the lowest in an energy of 1,287.8. The lowest is reached by 48 starts, the second by 47, the third by 32, the fourth by 27, the fifth by 43 and the sixth by 3. The share of starts a valley collects — the size of its basin, in the language of the subject — says little about its depth: the fifth valley’s basin is nearly as large as the lowest’s, and the sixth, which is not the deepest, is the one most likely to be missed altogether.

Sixty starts gave the same six valleys for fifty-five charges in an earlier trial, so the count is stable at this sample size. For larger $N$ it would not be. Computations by others, with far more starts, have found the number of valleys growing roughly exponentially with $N$, into the thousands for a few hundred charges, and the share of starts finding the lowest falling correspondingly. Methods that do better than random starts — perturbing a found arrangement and descending again, or moving defects deliberately — are how the record arrangements for large $N$ were found, and they too return records, not proofs.

Downhill has no memory of where it began #

A descent is a rule for walking downhill, and every such rule shares one property: it ends wherever the slope runs out, and it cannot know whether lower ground exists beyond a ridge. The landscape nobody is looking at met the same structure in a congestion game, where every improving move by a player lowers one hidden potential and so every sequence of improvements must stop — at an equilibrium, but not necessarily the best one. Every site in the middle of its own cell met it in Lloyd’s method for spreading points evenly, which also only ever improves and also stops at whichever balanced arrangement is nearest. The charges here are a third instance, and the cleanest, because the energy is a single explicit formula and nothing about it is random except the start.

What the walk preserves is the basin: the set of starting arrangements that flow into a given valley. The charges’ sixteen-point starting positions fill a space of 29 dimensions after rotations are removed, and the measurement says that about four-fifths of it drains into the lowest valley and one-fifth into the other. Those shares are volumes of regions bounded by ridges in a 29-dimensional landscape, and the only practical way to measure them is the one used here, sampling starts and counting where they go.

The symmetry of the answer gives no help either. Why the list of perfect solids stops at five found that only five arrangements on a sphere are perfectly regular, and the essay before this one found that even two of those five are not where charges settle. Sixteen admits no regular arrangement at all, so there is no symmetric candidate to check first, and both of its valleys are irregular in different ways.

Why proofs stop at six #

The valleys explain the state of the proofs. A proof that an arrangement is the minimum has to rule out every other arrangement of $N$ points on a sphere, a space of $2N - 3$ dimensions once rotations are set aside. When the landscape has one valley, a proof can sometimes be built by showing that the energy cannot be low anywhere far from the known arrangement, and then checking the neighbourhood carefully — the shape of Schwartz’s proof for five charges, which divided the space into many small boxes and bounded the energy in each. With two valleys a hair apart, the bounds have to be sharp enough to separate depths that differ by one part in ten thousand, everywhere in a space of dozens of dimensions.

So the proven cases are two, three, four, five, six and twelve charges — and twelve only because the icosahedron is so symmetric that a different kind of argument, about designs and linear programming, reaches it. Sixteen, the first number with a second valley, is also the first at which nothing like the existing proofs is in sight. Steve Smale’s list of problems for this century includes finding nearly optimal arrangements efficiently for a logarithmic version of the energy; even the logarithmic version, whose landscape is somewhat kinder, is open.

What the counts assume #

The counts depend on the descent. A different method of descending — smaller steps, or steps that use second derivatives — could in principle settle some starts into different valleys, since which basin a start belongs to is defined by the true downhill flow, and a numerical method only approximates it. The valleys themselves do not depend on the method: each is a point where the force vanishes and the energy rises in every direction, and the energies found here match the published best values wherever those are known, to the six decimal places shown. The share of starts reaching each valley does depend on the method and on how starts are drawn, and should be read as a property of this search, not of the landscape alone.

Some valleys might also be very shallow — places where the energy rises in every direction but barely — and a numerical search could treat a nearly flat place as a valley when it is in fact a saddle with a tiny downhill direction. Each valley counted here was reached by several independent starts with no force left, which makes that unlikely but does not exclude it.

Still open: the lowest valley for most numbers of charges #

For which numbers of charges can the lowest arrangement be proved? Only for the six listed above. For every other number, including sixteen, the best known arrangement is the best that searches have found, and the landscape measured here is the reason: the valleys multiply with $N$, the deepest is often not the one most starts find, and the depths differ by parts in a million.

A second open question concerns the valleys themselves. Their number grows roughly exponentially in $N$ according to every count so far, but no theorem says so, and nothing predicts which numbers of charges have a single valley — the measurements here find single valleys at forty-four and forty-eight after several numbers with more. Whether the number of valleys is related in a precise way to the number of distinct ways to place twelve defects on a triangulated sphere, as the mechanism above suggests, is not known.

A landscape with many floors #

Up to fifteen charges, every random start settles in the same arrangement; sixteen is the first number with two, and after that the valleys multiply irregularly with $N$. For fifty-six charges only one start in ten finds the lowest, and the other valleys sit three parts in ten million above it. The valleys differ only in where the twelve unavoidable defects sit, which barely moves the energy, and an arrangement reached by descent carries no sign of whether it is the deepest. That is why the minimum is known with proof for six numbers of charges and found by search for all the rest.