# The kissing number of a square, cube, hypercube?

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$:

-
For translative kissing numbers, it's easy: for squares, all the neighbors must be contained within the figure on the right above, and there are only eight units of area for them. I don't know how to prove the general case (or even whether it's known). For squares, it's not hard to prove an upper bound of 9. Specifically, you can look at how much of that figure is covered by each neighboring square. A short calculation shows that the worst case scenario is meeting at a 45 degree angle, covering area $0.82\dots$. Since $8/0.82 < 8/0.8 = 10$, at most nine squares can fit. –  Henry Cohn Dec 30 '12 at 3:10
I bet you could rule out nine squares by a more elaborate case analysis, but I haven't done it, and this approach doesn't seem likely to lead to a pleasant proof or a generalization to higher dimensions. –  Henry Cohn Dec 30 '12 at 3:14
Looking at Figure 1 for example, one could try to cut what is too far from the red square and paste it in the lost space. Whether this can be done in a natural way I don't know. –  François Brunault Dec 30 '12 at 9:33

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.

-
That's beautiful! –  Henry Cohn Dec 31 '12 at 15:15
@Sergei: It is natural to wonder if this beautiful proof could extend to cubes in $\mathbb{R}^3$... –  Joseph O'Rourke Dec 31 '12 at 18:43
Very nice ... elegant! –  Kevin R. Vixie Dec 31 '12 at 18:54
Beautiful. And a big thank-you to Joseph for putting 7 figures into one and post it here! –  Yuichiro Fujiwara Dec 31 '12 at 19:04
I thought briefly about the bigger annulus and boundary coverage, but didn't play with that long enough to try the smaller annulus. Hardy would say I am like the bear in the zoo, not taking a good idea far enough. The story goes that he was upset with Polya, who had disappointed him by not carrying an idea far enough. He visited the zoo, observing the bear fiddling with the lock on the cage but giving up after a short while, upon which Hardy said "He is like Polya. He has excellent ideas, but he does not carry them out." Again, very nice solution Sergei! –  Kevin R. Vixie Dec 31 '12 at 19:07