Not being well-versed in the area, I looked up "Kissing Number" at Mathworld. In the table, I notice that the "NL" (non lattice kissing number) values are missing for dimensions 1 thru 8. Don't we know that NL(1,2,3) = (2,6,12)? And certainly at worst NL(d) >= L(d) for d = 4 thru. I gather from our current discussion that we know 24 = L(4) <= NL(4) <= 25, and are discussing means to establish or eliminate NL(4) = 25 (though I've been following the thread only cursorily). Do we know of any lower bounds better than NL(d) for d <= 8 that we might put in the table? Also, bear with me here, I'm going to rehash some elementary stuff. In 2 dimensions, we easily see that a unit circle kissing unit circle S "uses up" pi/3 radians of the circumference of S, which cannot be used by any other kissing circle. This bounds NL(2) <= (2pi)/(pi/3) = 6. Similarly, a unit sphere kissing unit sphere S "uses up" an area A of the surface of C subsumed by a circle with a 60-degree diameter, so that NL(3) <= (4pi)/A. Does this observation generalize to higher dimensions? Does it result in an upper bound formula for NL(d)? Is there a nice bounding asymptotic? Does the formula grow relatively worse or better for increasing d? I'm sure this is textbook, but I've never seen it developed. If there is an accessible online development, that would be great.

On Fri, 26 Sep 2003, Dan Hoey wrote:

John Conway <conway@math.princeton.edu> wrote:

...

The feeling that I'd expressed too strongly my criticisms of Jud McCranie's proposed attack on the kissing number problem somehow convinced me that they were wrong, and led me to apologise....

You know, I had been about to do something like that, too. I think it was all the "wolg'ing that was so irritating. A little "wolg" goes a long way, and after two "wolg"s and an "etc" I was about to "wolg" all over my keyboard. But looking closer, I think there's something correct in Jud's idea, perhaps new or perhaps not. It might even be possible to use it to (correctly) prove bounds on the r-kissing number (how many radius-r balls can kiss a unit ball in k dimensions) for which I'm sure there are plenty of open cases.

You mean upper bounds, of course? If so, I very much doubt it. I regard it as virtually certain that Jud's method would "prove" a wrong upper bound of 23 or less for the 4-dimensional problem, and I see no way of "correcting" it so as to get the right answer of 24 or 25. But I'll read on, just in case...

First, let's try it without using symmetry or requiring any adjacencies of the balls (except, of course, to the central one). Quantitize the space of ball centers into small pieces p1,p2,...,pm. This could be done as coordinate-wise, so that each pi is the intersection of a dimension-k box with the (1+r)-sphere, or perhaps there is a better way of chopping up the space.

A pair of pieces (pi,pj) is admissible if they contain respective points (xi,xj) at a distance of at least 2r. If that's too hard to test, admissiblity standards can be loosened. For instance, we could call (pi,pj) admissible if the underlying boxes contain an appropriate pair of points.

We then exhaustively search for a set of n pieces that are pairwise admissible. If there is no such set, then the (r,k) kissing number is less than n. Of course, this doesn't prove the converse. But I think that if the kissing number is less than n, then there is a minimum overlap epsilon that will occur in any configuration of n spheres. If we require the pieces (or their boxes, in the loosened regime) to have dimension at most 2 epsilon, then the search for a pairwise adminssible subset will fail.

What would happen in the 4-dimensional case is that this method would never rule out 24, but also never find a configuration of 24. It would, of course, eventually rule out 25 (presuming that 24 is in fact the right answer), and so when supplemented by our knowledge that 24 can in fact be done, would give a proof that it were best possible. However, this "quantization" blows up the size of the investigation by a tremendous factor, and my original strong remarks basically apply to it. There's not a hope in hell of getting a program of the kind to run to completion.

This can be improved for efficiency. If n >= k I think that we can require each ball to kiss k-1 others in addition to the central one. If that's incorrect, we can at least require some adjacencies. This will allow us to require that adjacent balls be mapped to pieces that contain respective points (xi,xj) at a distance of exactly 2r. Other reductions of the search space are possible from symmetry.

I imagine this method will be intractible in the interesting cases, but at least it's correct.

No it isn't, if you include your previous paragraph. I can't see any way to prove that any ball after the second can be chosen to touch any more than ONE previous ball, and I'm confident that you can't, either. John Conway