"Allan C. Wechsler" <acw@alum.mit.edu> wrote (of Jud McCranie's conceptual program in four dimensions):

The central problem is the size of the configuration space that must be explored: 24 or 25 spheres jostling around, each contributing 3 degrees of freedom to the configuration space. JM proposed, if I read him right, to prune this space by considering only configurations of a certain special kind, in which the configuration may be built by adding each new sphere in the 'socket' formed by three previously-placed spheres. (This is hard to visualize, but in four-space, you need three other spheres to form a well-defined socket with no degrees of freedom.) Enumerating such configurations would be much easier than searching an enormous 75-dimensional configuration space.

It may be that Jud made such a proposal, but I am sure he no longer believes it to be proved correct. In fact, I suspect he may have proposed a somewhat less dubious proposal that was misunderstood. The problem arises from confusion over whether we are counting the original unit 3-sphere (in which case we would say four hyperspheres are required to form a socket in R^4) and over whether we are talking about packing in R^3 (using ordinary 2-spheres) or in R^4 (with 3-spheres). (In addition, I think there is some confusion about this nomenclature--I understand the surface of a ball in R^4 to be called a "3-sphere", but Allan calls them 4-spheres, so we can be sure confusion abounds.) I know that some of my respnoses were based on confusion over whether a given description includes the original unit sphere. At any rate, I believe we will do better to pack _points_ on the unit k-1-sphere (in R^k) with a prescribed lower bound r on the distance between points. This translates directly into the packing of kissing k-1-spheres of radius r/(2-r), if I've done my algebra correctly. At any rate, I would like to mention a modification to the approach I outlined on Friday. In this approach we place points in k-cells of side epsilon that intersect the given k-1-sphere. I will assign a point a "nominal location" of the center of its cell. However, since the point may differ from that location by epsilon.sqrt(k)/2, we must enforce a separation of points by r + epsilon.sqrt(k). In addition, since we require that each point be at the minimum distance to at least two neighbors, we count those points within r - epsilon.sqrt(k) of the given point toward the count of required near neighbors. Now, searching for these points with approximately n(k-1)-k(k-1)/2 degrees of freedom may be fairly intractible, but we may get some relief from the minimum and maximum spacings where the packing is tight. I was concerned that this relief might happen too far down the search tree to be helpful, and I would like to share an idea that might help make the relief more generally available. The idea is basically to start with a large epsilon, and to go to epsilon/2 by cutting all the cells in 2^k pieces. Most of the pieces go away (because they no longer intersect the k-1-sphere), and the reduced epsilon should also prune the cases. As epsilon is reduced, the configuration becomes more and more constrained, and we may be able to identify places where the constraints are loose. I imagine the looser spheres might in fact not need to have their cells cut as much after a certain point. This leads to a sort of quad-tree approach to the search space. I'm curious about how this approach might work (or how it may have worked already, since it's a fairly standard approach to geometrical searching). I remark that it not could not only tell us which (n,k,r) are not feasible, but it could provide witnesses for which (n,k,r-epsilon.sqrt(k)) are feasible. Dan