One determinant for every kaleidoscope

Three mirrors make every solid found that every symmetry of a regular solid is produced by three mirrors through its centre, reflected in one another until nothing new appears. Which three mirrors work was settled by a single inequality. If the mirrors meet in pairs at angles $\pi/p$, $\pi/q$ and $\pi/r$, they cut the sphere into a triangle with those angles, and the triangle tiles the sphere — so the reflections close up into a finite group — exactly when its angles add to more than $\pi$:

$$\frac1p + \frac1q + \frac1r > 1.$$

The solutions are the prisms and the three kaleidoscopes of the regular solids. That essay ended by naming the result that does the same job in every dimension, Coxeter’s classification of 1934, and left it there. This essay carries it out — not by Coxeter’s argument but by brute force — and the brute force needs exactly one tool, a determinant, in place of the angle sum, which has no meaning once there are more than three mirrors.

A dot for each mirror #

Harold Scott MacDonald Coxeter’s notation does the bookkeeping. Draw a dot for each mirror. If two mirrors are perpendicular, draw nothing between their dots — perpendicular mirrors do not interact, each reflection simply commuting with the other. If they meet at $60°$, the angle $\pi/3$, draw a plain line. If they meet at $\pi/m$ for $m \ge 4$, draw a line and write $m$ on it. The angle between two mirrors of a finite kaleidoscope must be $\pi/m$ for a whole number $m$, since the two reflections generate the symmetries of an $m$-gon, so the diagram records everything.

The cube’s three mirrors, for instance, meet at $\pi/4$, $\pi/3$ and $\pi/2$: the diagram is three dots in a row, joined by a line labelled 4 and a plain line, with nothing joining the ends. The icosahedron’s is the same with 5 in place of 4. A diagram that falls into separate pieces describes a kaleidoscope that is a product of smaller ones, each acting in its own perpendicular directions, so only connected diagrams need to be classified.

The hero figure is the complete list of connected diagrams for up to eight mirrors, and it is short: four rows that continue forever, or nearly, and five that do not. The A row is a plain chain, the symmetries of the simplex — the triangle, the tetrahedron, the five-cell. The B row ends in a 4 and gives the cube and its dual in every dimension. The D row forks at one end. The E row forks one step further in, and has only three members. The rest are the hexagon’s $G_2$, the pentagon’s $H_2$, the icosahedron’s $H_3$, the four-dimensional $H_4$ of the 120-cell, and the 24-cell’s $F_4$. Every one of them came out of a search that was told nothing but a test.

Inner products instead of angle sums #

The test comes from the mirrors’ directions. Each mirror is a hyperplane through the origin and has a unit vector $e_i$ perpendicular to it, chosen to point into the kaleidoscope’s fundamental chamber. Two mirrors at angle $\pi/m$ have normals at angle $\pi - \pi/m$, so their inner product is

$$e_i \cdot e_j = -\cos\frac{\pi}{m_{ij}},$$

with $m_{ij} = 2$ giving 0 for perpendicular mirrors. Put these into a matrix, ones on the diagonal: the Gram matrix $G$ of the diagram. If the arrangement exists in Euclidean space, $G$ is the table of inner products of $n$ independent vectors, and any such table is positive definite — $x^{\mathsf T} G x$ is the squared length of $\sum x_i e_i$, which is positive unless every $x_i$ is zero. Conversely, a positive definite matrix is the table of inner products of some set of independent vectors, which one subtraction clears a direction constructs by Gram–Schmidt: subtract from each vector its shadow on the ones before. The arrangement exists, and the reflections in it generate a finite group, exactly when $G$ is positive definite. That is Coxeter’s criterion, and it is the only mathematics the search needs.

For three mirrors it reproduces the angle sum.

The determinant of the three-by-three Gram matrix is $1 - \cos^2(\pi/p) - \cos^2(\pi/q)$ when the third angle is a right angle, and its sign agrees with the angle-sum test in every cell. The positive cells are the prisms, with $p$ or $q$ equal to 2, and the regular solids’ three kaleidoscopes $(3,3)$, $(3,4)$ and $(3,5)$. The zero cells — $(3,6)$, $(4,4)$ and $(6,3)$ — are the three triangles that tile the flat plane, 30–60–90, 45–45–90 and the reverse. The negative cells are triangles with angles adding to less than $\pi$, which tile the hyperbolic plane. The determinant is doing what the angle sum did, but the determinant generalises and the angle sum does not.

The search #

The classification can now be reduced to a computation. A connected diagram with $k+1$ dots that passes the test contains a connected diagram with $k$ dots that passes it — remove an end dot of a longest path, and what remains is connected and its Gram matrix is a principal submatrix of a positive definite matrix, hence positive definite. So every passing diagram is found by starting from the passing diagrams one size smaller and trying every way of adding one dot: each possible label, 2 to 6, on the line to each existing dot. Each candidate is tested for positive definiteness by attempting a Cholesky factorisation, which succeeds exactly when the matrix is positive definite, and the survivors are compared by a canonical form so that each diagram is counted once.

Labels larger than 6 need separate handling. Two mirrors at any angle $\pi/m$ form a finite kaleidoscope, the symmetries of an $m$-gon, so the two-dot diagrams are an infinite family; but a dot labelled 7 or more never survives the addition of a third, because the three-dot chain with labels $m$ and 3 is not positive definite for any $m \ge 6$. The search checks that directly for every $m$ up to 30. With labels up to 6 it is therefore complete.

The search tried 1,950,452 candidate diagrams of up to nine mirrors in all, most of them at the largest size, where each of four surviving eight-dot diagrams had 390,624 ways to receive a ninth. The counts come out as 1, 4, 3, 5, 3, 4, 4, 4 for one to eight mirrors, and every survivor is one of the diagrams in the hero figure. The search ran to nine mirrors and found three: the chains $A_9$ and $B_9$ and the fork $D_9$. No $E_9$, and nothing exceptional.

Why the diagrams are trees #

Every diagram in the hero figure is a tree — no loops — and every one has at most one fork. Neither fact was put into the search, and the first has a one-line reason that the search confirms rather than relies on.

Take a diagram with a loop of $k$ dots, every consecutive pair joined, and evaluate $x^{\mathsf T} G x$ at the vector with a 1 at each dot of the loop and 0 elsewhere. The diagonal contributes $k$. Each of the $k$ lines of the loop contributes $-2\cos(\pi/m)$, which is at most $-1$ since $m \ge 3$. Any other lines between dots of the loop only subtract more. So

$$x^{\mathsf T} G x \le k - k = 0,$$

and a positive definite matrix cannot give zero or less on a non-zero vector. A loop of mirrors all at $60°$ to their neighbours sits exactly on the boundary — the loop of three at $60°$ is the equilateral triangle that tiles the flat plane — and anything more acute is beyond it. Every finite kaleidoscope’s diagram is therefore a tree, and the search’s loops all turn up where the count figure puts them: in the flat column and the hyperbolic one.

A similar argument, with weights other than 1, shows that a finite diagram has at most one fork, at most one label above 3, and never both; and a third, with the weights chosen along the arms of a fork, gives the inequality $\frac1p + \frac1q + \frac1r > 1$ on the arm lengths $p, q, r$ that is the angle-sum test of three mirrors reappearing one level up. Its solutions are the forks $(2, 2, n)$, which are the D family, and $(2, 3, 3)$, $(2, 3, 4)$, $(2, 3, 5)$, which are $E_6$, $E_7$ and $E_8$. That is Coxeter’s own route to the list; the search reached the same list without it.

Why the fork stops at eight #

The E diagrams are a chain with one dot hanging from its third dot. With six, seven and eight dots they pass the test; with nine they fail. The determinant says why.

For the plain chains the determinant, scaled by $2^k$, is $k + 1$ and grows; for B it is constantly 2; for D constantly 4. None of them ever reaches zero, and that is why those three families run through every dimension. For E it is $9 - k$: 3 at six mirrors, 2 at seven, 1 at eight, and then 0 at nine. A positive definite matrix has a positive determinant, so at nine mirrors the E arrangement has stopped being a finite kaleidoscope. It has not stopped existing. Its Gram matrix at nine mirrors is positive semi-definite, with a single direction of length zero, and that is the signature of a kaleidoscope that tiles flat space instead of closing up on a sphere — the mirrors of the $E_8$ lattice’s symmetries, which two hundred and forty directions built from the quaternions. At ten mirrors the determinant is negative, and the arrangement lives in hyperbolic space.

That is why there are exactly three E diagrams, and it is the clearest case of something six in four dimensions, and three forever after found for regular polytopes: exceptions are exceptions because a number that decides existence crosses a threshold at a small dimension and never comes back. There the number was a solid angle; here it is a determinant, and $9 - k$ is about as plain as such a number can be.

Three kinds of arrangement #

Every connected diagram falls into one of three kinds by its Gram matrix: positive definite, a finite kaleidoscope on a sphere; positive semi-definite with determinant zero, a kaleidoscope tiling flat space; and the rest. Among the rest, the ones whose every smaller sub-diagram is finite bound a compact simplex in hyperbolic space, and their reflections tile that space with copies of a bounded cell.

The search records all three. The finite count never falls below three, because the chains A and B and the fork D are always there. The flat count is five at seven, eight and nine mirrors: each family that runs through every dimension has a flat cousin with one more mirror — the chain closes into a loop, or the end grows a second fork — and the exceptional flat ones, $\tilde G_2$, $\tilde F_4$, $\tilde E_6$, $\tilde E_7$ and $\tilde E_8$, each appear at their own size. After $\tilde E_8$ at nine mirrors there are no more exceptions, and the flat count is four ever after. The hyperbolic count does something different. With three mirrors there are 24 with labels up to 6 — and infinitely many once larger labels are allowed, since any triangle with angle sum below $\pi$ will do. With four mirrors there are nine. With five there are five. With six, seven, eight and nine there are none.

That is a theorem of Folke Lannér’s, from 1950: compact hyperbolic simplices whose reflections tile hyperbolic space exist only in dimensions two, three and four. The search found it by exhaustion, the way it found Coxeter’s list, and could not have found it any other way — it tries every candidate and none passes. In higher dimensions hyperbolic space can still be tiled by reflections, but only in cells that are not simplices, or that run off to infinity, and those were proved by Èrnest Vinberg and others in the 1980s to stop as well: no compact hyperbolic polytope generated by reflections exists in dimension thirty or more.

Counting the symmetries #

A diagram determines its group, and the size of the group can be computed from the mirrors alone.

Each count was made the same way the previous essay counted the three-dimensional groups: take the reflection matrices of the mirrors, built from the vectors the Gram matrix describes, and multiply them together in every order until no product is new. The three-mirror groups come out as 24, 48 and 120 — the tetrahedron’s, the cube’s and the icosahedron’s, which the five solids as three groups met as rotation groups of half those sizes. The four-mirror groups are 120 for the five-cell, 384 for the tesseract and its dual, 1,152 for the 24-cell and 14,400 for the 120-cell and 600-cell. The fork $D_4$, with 192, is the one group in the list that is not the full symmetry group of a regular polytope: it is half the tesseract’s, the symmetries that use an even number of a certain kind of reflection. The regular polytopes account for the chains; the forks come from somewhere else, and in eight dimensions $E_8$, with 696,729,600 symmetries, is the group of no regular polytope at all but of the densest lattice packing of spheres there is.

A determinant’s other jobs #

The test the search used, positive definiteness, turns up in many places wherever lengths and angles have to be consistent. The number that says how much room is left read a determinant as a volume, and the Gram determinant is exactly that: the squared volume of the parallelepiped spanned by the mirrors’ normals. A finite kaleidoscope needs the normals to span a genuine $n$-dimensional box, of positive volume, and the E family’s volume shrinks linearly as dots are added until at nine it is flat. More blocks than points used a Gram matrix’s determinant to prove an inequality about designs, by showing the determinant could not be zero; fifteen numbers decide every number dealt with positive definite quadratic forms in four variables, the same objects as positive definite Gram matrices, asking which whole numbers they represent. The classification of kaleidoscopes is the case where the matrix’s entries are cosines of $\pi/m$ and the question is only whether it is positive definite at all.

Still open: what the kaleidoscopes leave out #

The classification of finite reflection groups is complete, and so is the classification of the flat ones. The hyperbolic picture is not. Compact hyperbolic simplices stop at four dimensions, but reflection groups whose cell is a more complicated polytope go higher, and the highest dimension in which a compact hyperbolic reflection polytope exists is unknown: examples are known up to dimension 8, and Vinberg’s theorem rules out dimension 30 and above. Everything in between is open. For cells of finite volume that reach infinity, the known examples go up to dimension 21 and the proven limit is 995.

The previous essay’s open question remains open too. Coxeter diagrams classify the kaleidoscopes, and Wythoff’s construction turns each kaleidoscope into a family of uniform polytopes, but not every uniform polytope comes from a kaleidoscope by that construction — the grand antiprism of four dimensions is the standing example — and whether the exceptions can be organised in five and more dimensions is not known.

A test where an angle sum used to be #

The three-mirror classification needed an angle sum, and an angle sum is a fact about triangles. The classification in every dimension needs a matrix of cosines and the question whether it is positive definite, which is a fact about vectors and makes sense in any number of dimensions. Trying every diagram of up to nine mirrors against that test produced the whole of Coxeter’s list without any of Coxeter’s arguments: the chains A, B and D, whose determinants never reach zero; the fork E, whose determinant is $9 - k$ and runs out at eight; and five exceptions in three and four dimensions. The same test, read at the boundary, gave the flat tilings, and read beyond it gave hyperbolic simplices that stop at five mirrors, as Lannér proved. The list is short because positive definiteness is hard to keep as dots are added, and the determinant measures exactly how hard.