Sixty rotations as far apart as rotations can be

A rotation chosen at random ended by comparing grids of rotations: the twelve rotations of the tetrahedron, the twenty-four of the cube and the sixty of the icosahedron, each a finite set of orientations that a search over all orientations of a solid body might use in place of the infinite set. They are good grids, much better than the same number of rotations drawn at random, and the essay said that nothing better was known at those sizes. That statement was about how well a grid covers — how close every possible rotation comes to some grid point. This essay is about the other half of evenness, how well a grid spreads: how far apart its own rotations are from one another. For spreading there is a method that proves things, and at sixty rotations it proves that the icosahedron cannot be beaten.

The icosahedron’s sixty rotations are pairwise at least 72 degrees apart, where the distance between two rotations is the angle of the single rotation that carries one to the other. That is the smallest turn the icosahedron allows — a fifth of a turn about an axis through two opposite corners. The claim is that no sixty rotations are all more than 72 degrees apart, and that no sixty-one are all at least 72 degrees apart. The proof is one polynomial, and the hero shows what the same method says at every angle.

Rotations as points on a sphere #

The method works on points of a sphere, so rotations have to be made into points first, and the quaternions do exactly that. Every rotation of space is given by a unit quaternion $q$, a point of the three-dimensional sphere inside four-dimensional space, and by its negative $-q$, which gives the same rotation. The distance between two rotations has a clean form in these terms. If $p$ and $q$ are unit quaternions, the rotation carrying one to the other turns through the angle

$$\theta = 2 \arccos \lvert \langle p, q \rangle \rvert,$$

where $\langle p, q \rangle$ is the ordinary inner product of the two points in four dimensions. Two rotations at least $\theta$ apart therefore correspond to quaternions whose inner product lies between $-\cos(\theta/2)$ and $\cos(\theta/2)$. A set of $N$ rotations pairwise at least $\theta$ apart becomes a set of $2N$ points on the three-sphere, closed under negation, in which every inner product other than $\pm 1$ lies in the band from $-s$ to $s$, with $s = \cos(\theta/2)$.

At 72 degrees, $s = \cos 36^\circ = 0.80902$, which is half the golden ratio. The icosahedron’s sixty rotations become 120 quaternions, the icosians: the 24 units of the Hurwitz integers, together with 96 more obtained from $\tfrac12(0, 1, \varphi, 1/\varphi)$ by even permutations of the coordinates and every choice of signs. They are the vertices of the six-hundred-cell, the four-dimensional relative of the icosahedron, and the same points built the 240 directions in eight dimensions when taken twice over.

The inequality that does the work #

Philippe Delsarte found the method in 1973 for error-correcting codes, and with Jean-Marie Goethals and Johan Jacob Seidel carried it to points on spheres in 1977. It rests on a family of functions that are positive in aggregate. On the three-sphere these are

$$G_k(t) = \frac{U_k(t)}{k + 1}, \qquad k = 0, 1, 2, \ldots,$$

where $U_k$ is the Chebyshev polynomial of the second kind, and the key property is that for any finite set of points $x_1, \ldots, x_M$ on the sphere,

$$\sum_{i, j} G_k(\langle x_i, x_j \rangle) \;\ge\; 0.$$

The sum runs over all ordered pairs, a point with itself included. The inequality holds because $G_k(\langle x, y \rangle)$ can be written as an inner product of two vectors, one depending on $x$ and one on $y$ — the values at $x$ and at $y$ of a basis of the spherical harmonics of degree $k$ — so the double sum is the squared length of a single vector, and squared lengths are never negative.

Now take any polynomial $f = \sum_k f_k G_k$ with $f_0 = 1$ and every other $f_k \ge 0$, and suppose that $f(t) \le 0$ at every inner product the set can have other than 1. Add $f(\langle x_i, x_j \rangle)$ over all pairs in two ways. Pairs with $i = j$ contribute $f(1)$ each, $M$ of them, and every other pair contributes something nought or negative, so the total is at most $M f(1)$. Expanding $f$ instead, the $G_0$ term is the constant 1 and contributes $M^2$, and every other term contributes a non-negative multiple of a non-negative sum, so the total is at least $M^2$. Together, $M^2 \le M f(1)$, which is

$$M \le f(1).$$

Every admissible polynomial gives a bound, and the best bound is the least $f(1)$ over all of them. Finding it is a linear programme: the unknowns are the coefficients $f_k$, the constraints say they are non-negative and that $f$ is non-positive on the band, and the objective is $f(1) = \sum_k f_k$, since every $G_k$ equals 1 at $t = 1$. The figures solve it by the simplex method, with the constraint on $f$ imposed at 901 evenly spaced points of the band and at $-1$, for polynomials up to degree 17.

The smallest case by hand #

The method is easiest to trust on a case small enough to do without a computer. Take rotations pairwise half a turn apart, the most demanding separation there is. The band shrinks to a single point, $s = \cos 90^\circ = 0$, so the quaternions must be pairwise perpendicular or opposite, and the polynomial must be nought or negative at $t = 0$ and at $t = -1$. The first two functions are $G_1(t) = t$ and $G_2(t) = (4t^2 - 1)/3$, and a short search finds

$$f(t) = 4t^2 + 4t = 1 + 4\,G_1(t) + 3\,G_2(t).$$

Its coefficients 1, 4 and 3 are all positive, it vanishes at $t = 0$ and at $t = -1$, and $f(1) = 8$. So at most eight quaternions, four rotations, can be pairwise half a turn apart. The four-group meets this: the identity and the half-turns about three perpendicular axes are the quaternions $\pm 1, \pm i, \pm j, \pm k$, eight points with every inner product nought or $-1$. Five rotations pairwise half a turn apart would be ten points of four-dimensional space with no two at an acute or obtuse angle except opposite pairs — five mutually perpendicular directions in four dimensions — which is impossible for a reason anyone can state, and the polynomial is that reason written as an inequality.

What changes at smaller angles is only that the band widens and the polynomial has to stay nought or negative over all of it, which takes more degrees of freedom and is no longer a search a person would do by hand. The arithmetic of the proof is the same at every angle: positive coefficients, non-positive values on the band, and the value at 1 is the bound.

The certificate at 72 degrees #

At 72 degrees the least value is 120 quaternions — sixty rotations — and the figure draws the polynomial that achieves it.

The polynomial lies flat against zero across most of the band and touches it at exactly the eight inner products the icosians use: $-1$, $\pm 0.809$, $\pm 0.5$, $\pm 0.309$ and $0$. That is not a coincidence of this drawing. It is forced by the argument itself. If a set of $M$ points meets the bound, so that $M = f(1)$, then both of the inequalities above must hold with equality, and the first can only be an equality if $f$ is zero at every inner product the set actually uses. A set that meets the bound is invisible to its own certificate. So once the polynomial is found with value 120 at 1, and the icosians are checked to have 120 points and to use only inner products in the band, nothing more is needed: no antipodal set of quaternions with inner products in that band has more than 120 points, and the icosahedron’s sixty rotations are as many as can be kept 72 degrees apart.

The bound changes continuously with the angle, so it also says what happens on either side. At 71.9 degrees it allows 60.2 rotations, so sixty-one rotations cannot all be even that far apart; at 72 it allows exactly sixty, and any slightly larger angle allows fewer than sixty, so no sixty rotations can all be more than 72 degrees apart. The icosahedral group sits on a corner of the curve.

The bound reached here is numerical — the computed value is 119.9998, with the constraint imposed at grid points rather than at every point of the band — and the exact statement is a theorem of Nikolai Andreev, who proved in 1999 that the six-hundred-cell is the best possible arrangement of 120 points on the three-sphere by a certificate of this kind. Henry Cohn and Abhinav Kumar proved in 2007 that it is optimal in a much stronger sense, minimising every reasonable measure of crowding at once.

Every coefficient is a sum of squares #

The second half of the certificate is its coefficients, and they are the part that cannot be faked: a negative coefficient would break the step that discarded the higher terms as non-negative.

The bars add to $f(1)$ because every $G_k$ is 1 at 1, so the bound is literally the total height of the picture. Several coefficients come out as nought. Those degrees contribute nothing to the inequality, and a set that meets the bound must have its degree-$k$ harmonic sums vanish wherever $f_k$ is positive — which is the statement that the 120 icosians are balanced against every harmonic of those degrees, a spherical design. The six-hundred-cell is a design of strength 11: averaging any polynomial of degree up to 11 over its vertices gives exactly the polynomial’s average over the whole sphere.

There is a fact hiding in the functions $G_k$ that connects this calculation to a different part of mathematics altogether. Write $t = \cos \varphi$. Then

$$G_k(\cos \varphi) = \frac{\sin\big((k + 1)\varphi\big)}{(k + 1)\sin \varphi},$$

and $\sin((k+1)\varphi)/\sin\varphi$ is the character of the irreducible representation of the unit quaternions of dimension $k + 1$ — the trace of the matrix by which a quaternion of angle $2\varphi$ acts, the function physicists call the character of spin $k/2$. The positivity that makes Delsarte’s method work is the positivity that makes character tables orthogonal. A bound on how far apart rotations can be is, underneath, a statement about how the rotation group acts on spaces of polynomials.

What the groups look like from inside #

Every rotation group looks the same from each of its own rotations — multiplying by a fixed element moves every element without changing any distance — so the distances from one rotation to all the others describe every pair.

The four groups are the four places where the curve is met or nearly met. The four-group — the identity and the three half-turns about perpendicular axes — has every distance 180 degrees, and at 180 degrees the bound is four: five rotations cannot be pairwise half a turn apart. The tetrahedron’s twelve rotations sit 120 and 180 degrees from one another, and at 120 degrees the bound is exactly 24 quaternions, twelve rotations. The icosahedron’s sixty use 72, 120, 144 and 180 degrees, and meet the bound at 72.

The cube’s twenty-four rotations, at least 90 degrees apart, are the exception. At 90 degrees the bound allows 57.9 quaternions, 28.9 rotations, and raising the degree of the polynomial to 31 leaves it at 28.94. The certificate cannot vanish at all six inner products the octahedral group uses: computed at 90 degrees it is about $-0.77$ at $\langle p, q \rangle = 0.5$, an inner product the cube’s quaternions use, and a certificate that is strictly negative at a used inner product is how a bound that is not met shows itself. Whether twenty-five rotations can be pairwise at least 90 degrees apart is not decided by this method.

Chance does not find the structure #

How much of the icosahedron’s spread is structure, and how much is what any sixty rotations would give? The answer is that random rotations come nowhere near.

Sixty uniformly random rotations have, in a typical draw, two that are only 11 degrees apart; the best of four hundred draws manages 21.4 degrees. The icosahedral group manages 72. The gap is the familiar one between random and arranged points — a random set always contains some pair much closer than the average spacing, because there are many pairs and each has a small chance of being close — and it widens as $N$ grows. At four rotations the best random draw reaches 131.7 degrees against the four-group’s 180; at sixty it reaches less than a third of the icosahedron’s separation.

That is the practical reason the groups matter in the applications that need a grid of rotations: searching every orientation of a molecule against a binding site, sampling camera orientations, averaging over crystal orientations. A grid drawn at random wastes most of its points on near-duplicates. A grid from the icosahedron wastes none, and the polynomial says that at sixty points no grid could be more economical.

The same bound for points, and a famous gap #

The method does not know that the points came from rotations, and with the requirement of closure under negation dropped it is a bound on how many points can sit on the three-sphere with no two closer than a given angle. At 60 degrees that question is the kissing problem in four dimensions: how many unit spheres can touch one central unit sphere without overlapping, the touching points being exactly a set on the central sphere with no two closer than 60 degrees.

The 24 Hurwitz units, the vertices of the twenty-four-cell, are 60 degrees apart, so 24 spheres can touch. The general bound at 60 degrees is 25.56, which only proves that 26 cannot. For sets closed under negation it is exactly 24 — but the kissing problem allows any shape. The gap between 24 and 25 stood until 2003, when Oleg Musin proved the kissing number of four-dimensional space is 24 by a refinement of Delsarte’s method in which the polynomial is allowed to be positive on part of the band, at the cost of a more delicate count. In eight and twenty-four dimensions the plain bound is met exactly, by the 240 roots of $E_8$ and the 196,560 minimal vectors of the Leech lattice; dimension four is the case where structure exists and the simplest certificate cannot see it.

Bounds checked on a grid #

The bounds are computed, not derived. The constraint that the polynomial is non-positive is checked at 901 points of the band and at $-1$, and between grid points a polynomial of degree 17 could rise very slightly above zero. The exact results — the six-hundred-cell’s optimality, the kissing number 24 — are theorems with exact certificates; the curve in the hero is a numerical picture of the bound, accurate to the fourth decimal at the points where it matters.

A bound of this kind says nothing about covering. The question the random-rotation essay ended on — how close every rotation comes to the grid — is a different extremal problem, and for covering there is no comparable certificate known to be tight at these sizes. The icosahedron could be the best spread at sixty without being the best cover.

The curve between the groups is an upper bound only. At angles where no group sits, the true maximum number of rotations is below the curve by an unknown amount. The hero gives the most that the method allows, not the most that exists.

Degree 17 is a choice. Higher degrees can only lower the bound, and at 72 and 120 degrees they cannot lower it further since it is already met. At 90 degrees the bound stayed at 28.94 up to degree 31, which suggests but does not prove that the linear programme has reached its limit there.

Still open: the rotations between the groups #

Three numbers of rotations — four, twelve and sixty — are settled by the hero, because a group meets the bound. For every other number the best spread of rotations is not known. The cube’s twenty-four rotations are 90 degrees apart and the bound allows up to twenty-eight; the linear programme cannot rule out twenty-five, and no rotation group of that size or larger has a separation of 90 degrees. For numbers between the groups, such as thirty or a hundred, the best arrangements are found by numerical search and are not known to be best.

Musin’s refinement, and the semidefinite programming bounds of Christine Bachoc and Frank Vallentin that extended it in 2008, close some gaps of this kind by looking at triples of points instead of pairs. Whether those stronger methods can settle the cube’s twenty-four — whether there is a structural reason the octahedral group is the best spread of its size, as the five regular solids are the best of their kind in other senses — is a question the single polynomial of this essay is not strong enough to answer. And the dual question, the best covering by $N$ rotations, has no certificate at any size beyond the trivial ones: the best a code can be has a linear programme on its side, and the best net does not.