Date: Fri, 26 Sep 2003 13:24:09 -0400 (EDT)
From: Dan Hoey <Hoey@aic.nrl.navy.mil>
To: Jud McCranie <judmccr@bellsouth.net>
Subject: Re: [math-fun] Kissing number (again).
cc: math-fun <math-fun@mailman.xmission.com>

> My 4-D intuition is certainly no good, so I was wondering if what seems
> would work in 3D would carry over to 4D (about whether or not it is
> sufficiently general for a ball to touch the maximum number of other
> balls).  But let me ask this about the "continuum", and I'll use the 3D
> analogy.

> Suppose you've got a few balls touching the central one and you're
> finding the places where you can add another one.  The simplest
> approach would be to find all of the places where it touches the
> central ball and two others, but that isn't sufficiently general.

No, it isn't.  Your problem is not geometry, it's logic.  You can't
assume that the new ball will touch more than one of the previously
placed balls (and you can't even assume _that_ just by saying so, you
have to prove it--see below).

>  Consider the new ball touching the center ball and is in contact
>  with ball A.

You can't assume that.  It might be in touch with just one of the
previously-placed balls, and you can't even guarantee which one.

> Swing it one way (staying in contact with ball A and the central
> ball) until it touches ball B.

But your "swinging" it is not general, because it might interfere with
the further placement of other balls.  If you interfere with future
placements, your solution is not general, even in two dimensions.

The way you can guarantee that each ball touches at least two others,
one of them previously placed, is this way:

  Hypothesize a complete kissing arrangement of N>2 spheres.  I will
  prove there is a connected kissing arrangement in which every ball
  touches at least two others, by modifying the given arrangement:

      1.  If the arrangement is not connected, you can move one
             connected component as a unit until it touches another
             ball.

      2.  If ball A touches only ball B, then ball B must touch
             some ball C (otherwise case 1 would hold).  You can swing
             ball  A  around  B  until  A  hits some other ball--
             perhaps not  C,  but some ball.

  This modification increases the number of adjacencies by 1, so if
  you repeat it as long as there is a ball touching fewer than two
  others, it will terminate in at most (n-1)(n-2)/2 + 2 steps, because
  with that many adjacencies every ball must touch at least two
  others, QED.

This _allows_ you to search for arrangements by placing each new ball
so it touches one previous ball somewhere.  If you further restrict
your choice. you invalidate the entire effort, since you might not
find an arrangement even if one exists.

I looked at trying to modify this for four dimensions, and I find that
you can prove that every ball must touch at least two others.  Same in
K   dimensions: every ball must touch at least two others.  You might
have all  N  balls in a loop, so you have to guess each ball but the
first, second, and last with  K-1  degrees of freedom.

You can't do better with "geometric intuition".  John was right, of
course.

Dan