The kissing number of a square, cube, hypercube? - MathOverflow

The kissing number of a square, cube, hypercube?

2012-12-30T02:01:38Z

How many nonoverlapping unit squares can (nonoverlappingly) touch one unit square? By "nonoverlapping" I mean: not sharing an interior point. By "touch" I mean: sharing a boundary point.

It seems the answer for a square in $\mathbb{R}^2$ should be $8$, and for a cube in $\mathbb{R}^3$, $26$.

But a 1999 paper by Larman and Zong,

"On the Kissing Numbers of Some Special Convex Bodies." Discrete Comput Geom 21:233–242 (1999). (Springer link)

says

"In this note we determine the kissing numbers of octahedra, rhombic dodecahedra and elongated octahedra. In fact, besides balls and cylinders, they are the only convex bodies whose kissing numbers are exactly known."

In that paper, they were interested in the translative kissing number and the lattice kissing number, whereas I want to consider arbitrary orientations of each square/cube. Despite the quote above, it seems this should be known...?

Update (30Dec12) The following explains (I believe) the $0.82$ in Henry Cohn's comment, leading to his proof for $\le 9$ in $\mathbb{R}^2$:

Answer by Kevin R. Vixie for The kissing number of a square, cube, hypercube?

2012-12-31T00:17:07Z

Here is an answer for the square case: Following what Henry did, using matlab/octave calculations, one gets that 8 is the maximum.

Synopsis: you can lose a bit more than 11% of the area and still have an area that divides into 8 less than 9 times. Now note that we don't lose that much area from the intersection of the tipped square and the square annulus unless the tip of the square is between approx 17 and 73 degrees. We are also guaranteed to have at least one side of the tipped square at least .5 units from a corner of the central square. (see the figure below -- the angle bounds are approximate)

Now, a bit of thought and playing around will convince you that the area red rectangle is a lower bound on the inaccessible area to other squares in the annulus, thus that area can be added back to the lost area.

(I did the calculations twice, found a simple arithmetic error that did not effect conclusion -- I am pretty sure this is right.)

Answer by Sergei Ivanov for The kissing number of a square, cube, hypercube?

2012-12-31T15:05:56Z

The square case was posed as a problem at Leningrad (now St. Petersburg) high school math olympiad in 1963. I wrote a solution of this problem for the volume "St. Petersburg mathematical olympiads 1961-1993", D.V.Fomin, K.P.Kokhas eds., Lan' Publ. 2007 (in Russian), it is Problem 63.31 in that book.

Here is the original very detailed draft of the solution from my archive (only a sketch made it into the final book). It is in Russian but the pictures and formulae might be enough to follow the proof. Up to elementary but cumbersome case chasing, the solution is the following.

Consider the boundary of the twice bigger square with the same center and parallel sides. It is a broken line of length 8. It turns out that each of the kissing squares takes away a piece of length at least 1 from this broken line. Hence there are at most 8 kissing squares (and furthermore one analyse the equality case).

_{(Snapshots of the figures added by J.O'Rourke)}

The proof of the fact that the length of the intersection is at least 1 is essentially an exhaustion of cases, each of which is trivial. It is helpful to observe that the length of the intersection is a piecewise linear function of the relative position of the squares (if the orientation is fixed), so one has to consider only "borderline" positions (i.e. those where one of the corners is on one of the lines). This leaves about 10 cases to consider.