Eight points that refuse the cube

In 1930 the Dutch botanist Pieter Tammes was studying the pores on grains of pollen. They seemed to spread themselves evenly over each grain, and a grain with many pores had them spaced in a characteristic way. It occurred to him to ask how many points could be placed on a sphere, keeping a certain minimum distance. The geometry question has outlived the pollen. Put $N$ points on a sphere so that the closest pair is as far apart as possible. For six points the answer is the octahedron, and for twelve it is the icosahedron. Anyone would guess that eight is a cube and twenty a dodecahedron.

That guess is wrong. The cube is not even a good arrangement of eight points, and the picture below shows why in a moment. The problem looks easy, since it is a matter of pushing points apart on a ball, and it has been solved only for $N \le 14$ and $N = 24$. A related energy problem, in where charges settle on a sphere and valleys a search cannot count, was found to have shapes that depend strongly on how charges repel. This one cares only about the single worst pair, and the difference matters.

Why a cube is bad #

A cube has corners that are nearest along its twelve edges, at 70.53°. The trouble is visible from the top: every corner of the top square is directly above a corner of the bottom square. Those vertical edges use up space, while the diagonal of each side face has spare room. Turn the top square through 45°. Now each top corner sits over a gap between two bottom corners, and everything is further apart than it needs to be. So the two squares can be moved towards each other, while the points within each square get further apart, until the two kinds of distance balance. That is the square antiprism, with its closest pair at 74.86°, an improvement of more than four degrees. The antiprism is what the search finds, starting from eight random points, and it is reached with no hint that a cube exists. Why should the regular solid fail? Because the cube’s faces are squares. A face is a ring of points with a hole inside, and a square has more slack in it than a triangle. A locally rigid arrangement on a sphere wants triangles.

This one observation explains most of what follows. The three solids made entirely of triangles, the tetrahedron, octahedron and icosahedron, are optimal. The cube and dodecahedron, with faces of four and five sides, are not. Twenty points in a dodecahedron have a closest pair at 41.81°, while the best twenty points are known to reach 47.43°. Why only five solids lists regular shapes by symmetry, and the sphere does not care about symmetry for its own sake.

A search for each number of points #

The method used here treats the points as particles repelling each other with a force of $1/d^{s}$. With a low power $s$ this gives a smooth landscape, and with a high power, only the closest pairs feel anything, and that is the Tammes objective. So a run starts from random points with small $s$, raises it in stages, and finally polishes by moving only the points in near-closest pairs, keeping a move only if the closest pair improves. It is then repeated from many random starts.

The search values are within 0.107° of the best quoted in the literature at every $N$ up to 24, and it is short by more than 0.02° only at 15, 19, 21, 22 and 23. Up to 14, it comes within a tenth of a degree of the proved values. That is what can be expected of a search, as these are lower bounds, each an actual arrangement of points. They cannot by themselves show that nothing better exists. Quoted values are from Neil Sloane’s tables and the published proofs.

The dashed curve has a very simple source. László Fejes Tóth found in 1943 that if $N$ points on a sphere have closest angle $\theta$, drawing a spherical triangle between neighbouring points gives a tiling whose triangles each have area at least that of an equilateral triangle of side $\theta$. Adding up the areas gives his bound:

$$\theta \le \arccos\!\left(\frac{\cot^2 \omega - 1}{2}\right), \qquad \omega = \frac{\pi N}{6(N - 2)}.$$

Equality would require the entire sphere to be tiled by equal equilateral triangles. That happens at $N = 3$, $4$, $6$ and $12$, and only then. So at 4, 6 and 12 the arrangement is not just best, it is proved so by one short calculation. It is also why the bound is a little loose elsewhere, where the sphere cannot be tiled evenly. The formula is good: at $N = 24$ it gives 44.7°, against the true 43.69°.

A point fewer, no more room #

One of the odd features of this problem is that removing a point sometimes does not help.

The icosahedron’s closest angle is 63.43°. Take one point away, and there is a hole. Intuitively, the five neighbours ought to move into it, and everything would relax. But it does not work. The rest of the arrangement is still held in place by triangles, so that the five points around the hole cannot move outward while the remaining six hold firm. The best eleven have the same 63.43°, and Ludwig Danzer proved this in 1963. The same thing happens for five and six points, both 90°. Six points are the octahedron, and five can be three on an equator, or four on a band with a point at the pole, with several points free to move: that is a rattler, a point that is not held in place by any contact, and the best arrangement is not unique. The energy problem has no such feature, because every point there feels all the others. This is what is so unusual about the Tammes problem, where some of the points may be doing nothing at all.

Counting the contacts gives a test for rigidity. Each point has two degrees of freedom, and rotating the whole sphere takes away three, so a rigid configuration with no rattlers needs at least $2N - 3$ contacts, or more depending on how it is held. Twelve points have 30, and the eleven have 25, more than the 19 required. Arrangements found by a search can be checked this way, as a sign of their being genuinely jammed, and this is how a numerical result might be used as a starting point for a proof.

Spacing and energy disagree #

The search also ran the energy problem from the earlier essay, in which charges repel by $1/d$.

The bars are the difference between the two solutions’ closest pairs. They agree at 4, 5, 6 and 12, and they disagree everywhere else, by as much as 5.87° at 7 and 4.89° at 11. At eight points, the energy minimum’s closest pair is 71.69°, which is hardly better than the cube, even though its shape is also an antiprism. It simply is not spaced for the closest pair’s benefit. The two problems are the ends of one family, with energy $\sum 1/d^s$. As $s$ grows, the worst pair comes to dominate, and at infinity it is all that matters. So the optimal shape typically moves as $s$ changes. It is a remarkable property that it does not always. Henry Cohn and Abhinav Kumar showed in 2007 that some configurations are universally optimal, minimising a whole class of repulsive energies at once. On the ordinary sphere these are just the regular triangle, tetrahedron, octahedron and icosahedron, and in higher dimensions the same property holds for special sets such as the 240 directions of $E_8$.

So only the solids made of triangles are immune. Everything else has to choose. A virus capsid, a golf ball’s dimples and a set of pollen pores are all answers to related but different versions of the same problem, and the winner at a given $N$ depends on which distance matters most. Experiments on charged colloidal particles and hollow shells show that defects and non-uniformities arrive on a schedule of their own, and they may have nothing to do with what either energy would predict.

Why thirteen is the number that matters #

The most famous case is not one of the pictures. How many balls of radius one can touch one central ball of radius one? This is the kissing number, and Isaac Newton and David Gregory disagreed about it in 1694. Gregory thought thirteen might be possible, and Newton said twelve. The icosahedron leaves spare room, as twelve balls can touch the central one with gaps all around them. In fact the gaps can be moved about. But can a thirteenth be squeezed in?

Two balls touching a central ball, and not overlapping each other, have centres at an angle of at least 60° as seen from the centre. So thirteen kissing balls are precisely thirteen points on a sphere with closest angle at least 60°. The search’s value for thirteen is 57.135°, and the proved value is 57.1367°. It is a hair short of what is needed. Newton was right, and this was finally proved in 1953 by Kurt Schütte and Bartel van der Waerden, who also gave the value’s first bound. Oleg Musin and Alexey Tarasov proved the exact value of 57.1367° only in 2012, using a computer enumeration of every possible graph of contacts, each one needing to be ruled out or confirmed. Their approach was extended to fourteen points in 2015, and nothing beyond that is proved except $N = 24$, where Raphael Robinson proved in 1961 that the snub cube is the best arrangement.

The snub cube is another of the surprises. It is one of the Archimedean solids, with 24 vertices, and it comes in left-handed and right-handed versions that are not mirror images of themselves. So the best 24 points on a sphere have no mirror symmetry at all. A problem with perfect symmetry has a solution that has to choose a hand, and the sphere offers no reason for either. This is one of the very few values above 14 that has a proof, and it comes from a similar kind of area argument.

The same problem in other clothes #

The question recurs wherever objects must be kept apart in a curved space. One dimension up, it asks for points on a three-dimensional sphere, and since rotations of space correspond to such points, spreading points there is the same as spreading rotations as far apart as possible, the problem solved at twelve and at sixty in sixty rotations as far apart as rotations can be. In a hundred or more dimensions, the same arrangements are called spherical codes, and they are used to build signals that stay distinguishable under noise, by the same reasoning that gives balls that tile the space of binary words. There the points are the signals and the angle is a safety margin. Nothing in the engineering version needs the exact optimum, and a good lower bound is what is wanted. A wholly different use arises in the design of experiments, where points on a sphere are directions in which to measure and even spread keeps errors from concentrating in any one direction. Those methods also take their starting points from the tables that Sloane has kept, up to many hundreds of points, in which almost every entry has only ever been found by searches of the kind described here.

How often a random start succeeds #

The search’s success varies dramatically. At twelve points, 22 of 24 starts reach the best. At eight, 18 of 24. At thirteen, only 1 of 500 starts gets there, and earlier runs of this search, with 22 and with 70 starts, both missed it, reporting values such as 56.73° with no sign of anything wrong. That is a striking number, and it is the reason for the large gap between finding and proving. A shape reached one time in 500 might have a cousin that is reached one time in a million, and nothing about the search would hint that this is so. The sets at 16, 20 and 24 are reached by 3, 17 and 8 of 70 starts, so that it does not get harder steadily. The difficulty depends on the shape of the landscape at each $N$.

What a sphere of dots conceals #

Any search result is a lower bound. Above $N = 14$, except at 24, everybody’s numbers are of that kind, including those in Sloane’s tables, and the bound is just the best that has been found. The contact counts, and the claim of being locked in place, rest on a tolerance of a quarter of a degree in picking which pairs are in contact, so that they would change if the arrangement were not well converged. The bar chart’s differences have been computed with results of only moderate accuracy, and a tenth of a degree at larger $N$ can be accounted for by the shortfall of the search. And a projected picture of a sphere gives very little sense of whether an arrangement is really uniform, so that the figures show less than a table of its angles would.

What was computed and what was quoted #

The cube’s and antiprism’s angles are exact to rounding, and the antiprism’s height was found by a one-dimensional search. The numerical arrangements come from seeded random starts, 24 starts for $N \le 12$, 500 at 13 and 14, and 70 above that. The energy minima come from 20 starts each. The search at 12 was checked against the known energy 49.165253 for the icosahedron, and the bound at 4, 6 and 12 was checked against its exact values.

Quoted: the values in the comparison from Sloane’s tables and the proofs, the historical attributions to Tammes, Fejes Tóth, Schütte and van der Waerden, Danzer, Robinson, and Musin and Tarasov, and Cohn and Kumar’s universal optimality. The dates and details of the Newton and Gregory exchange are the standard account, which is a story with more legend in it than record.

Still open: fifteen points #

What is the exact Tammes value for $N = 15$? The best known arrangement gives about 53.66°. Musin and Tarasov’s method enumerates all possible contact graphs and rules them out one by one, and the number of graphs grows very quickly with $N$, so that the next case is a much harder computation than the last. There is no reason to think that the known arrangements are wrong, but no proof exists.

For large $N$, the leading behaviour is known exactly: the angle is about $\sqrt{8\pi/(\sqrt 3 N)}$, corresponding to the hexagonal packing of the plane, with the sphere’s curvature forcing at least twelve defects, wherever pentagons have to go. How the correction term behaves, and how those defects should be arranged, is open. It is also unknown what happens for intermediate $N$ between the magic values at which the icosahedral arrangements fit, and there may be no clean description. On a higher-dimensional sphere the corresponding problem is the theory of spherical codes, whose best values are known in very few cases, and only for a handful of magic sizes. Those exact values depend on a linear programming bound that for most sizes simply is not tight.

Triangles win #

The best arrangements of points on a sphere want every face to be a triangle, so the three triangle-faced solids are optimal and the cube and dodecahedron are not. Turning one face of a cube by 45° and moving the faces closer gains over four degrees. The optimal value does not even strictly change as points are removed, at five and at eleven, and it falls short of the number needed for a thirteenth kissing ball by less than three degrees.

Most of the problem remains out of reach. The searches here reproduce every known value within about a tenth of a degree, and yet at thirteen points they did so only by running five hundred times and getting lucky once. The distance between finding a good arrangement and being sure it is the best is what is left, and it is exactly what took until 2012 for thirteen points.