Sphere packing

Trying to figure out how this works

As part of the clustering algorithms stuff I sometimes noodle on I’m trying to figure out how to define a toroidal-ish space which wraps around in a way corresponding to the kissing number for each number of dimensions and is straightforward and efficient to implement in software. I’m probably reinventing the wheel here, with the possible exception of keeping an eye on how to efficiently implement things in software, the details of which are probably mathematically trivial, but this is all new to me and isn’t written up anywhere in a way which I could understand so here’s my presentation of it.

(I do this under the assumption that it will result in k+1 things magically packing equidistantly and nicely colorable, a property I will simply claim happens without any justification whatsoever.)

Despite your existing familiarity with sphere packing in 2 and 3 dimensions it’s most insightful to understand those starting with 4. In 4 dimensions you start with a grid. This isn’t great because each thing is only adjacent to 8 others, but also has a similar problem to what hyperspheres do which is that points have clear antipodes, a single point most distant from them, and you’re trying to pack everything in so everything else should be about equidistant. Like with hyperspheres the fix is to glue each point to its antipode, so you add in another grid where everything is offset by 1/2 in each dimension. In 4 dimensions this results in each point having 16 diagonals (because each dimension goes up or down by 1/2) which by the Pythagorean Theorem are magically of length 1 so they’re the same distance as the other 8 for a total of 24.

Happily 24 is exactly the kissing number for 4 dimensions. This construction doesn’t quite work verbatim for less than 4 dimensions because then the diagonals wind up being less than 1 unit away. That can be fixed by stretching out exactly one of the dimensions to make the diagonals all unit length resulting in face centered packing for 3 dimensions and the standard optimal packing for 2 dimensions.

This way of viewing this is also very nice from an implementation standpoint. To find the shortest distance from the origin to a particular point, independently figure out whether to get their in the positive or negative direction for each dimension to find the closest version, then do the same thing for the point offset by one half in each dimension, and take the shorter of those two vectors.

Above 4 dimensions this construction breaks down because the diagonals are already more than a unit away from the beginning. Again it’s easiest to understand what happens next by jumping up a bit. In 8 dimensions there is the E8 group. To construct that you knock out all the points in the grid where the sum of their offsets in each dimension is odd. That leaves all the major diagonals as length square root of 2, and leaves in minor diagonals where you offset on the grid in exactly two dimensions which are also length square root of 2. That leaves total number of kissing spheres as (2^8)/2+(8*7/2)*2^2 = 240 and we’ve got the optimal solution.

This is also straightforward to implement by doing the same thing as with 4 dimensions and below, but keep track of the number of times a point was flipped to the other side and if it’s odd in the end you have to undo whichever flipping made the least gains.

Like in the earlier case the problem with doing the same thing in a lower number of dimensions is that the diagonals are too short so you have to stretch out one of the dimensions to make them the same length as the other points. In 5 dimensions this nails it again, with 16 major diagonals and 24 minor diagonals for a total of 40 which is the best known, and in 6 dimensions it likewise nails it with 32+40=72.

In 7 dimensions things break down and I get horribly confused. This construction yields 124, but the best known is 126. This is likely too small a difference to matter in practice, but it’s very strange and it would be nice if someone could explain to me where those extra 2 are from some strange other diagonal or if it’s a completely different construction or if the kissing number is improved with some much less symmetric smushing of the pieces around to squeeze in 2 more is being done.

Above 8 dimensions I’m a bit lost. Presumably you can drop everything which isn’t 0 mod 3 instead of 0 mod 2 which will result in many more minor diagonals, but that seems like it isn’t a lattice any more and is unlikely to be able to nail constructing the Leech Lattice. But at least it’s still reasonably easy to implement, albeit with a few more caveats. It seems like a crude but vaguely ballpark estimate for kissing numbers is n choose n/2 divided by n/2.

It might not matter of course. 8 is already a fairly high number of dimensions for what I’m trying to do and I haven’t even benchmarked these against hyperspheres and it seems likely that their potential benefits has already run out at that scale, or maybe falls off a cliff after the magical construction at 8.