How many mutually touching cylinders can be arranged in 3D?

An old problem, restated by Martin Gardner in 1959, asked if six cigarettes that can be placed so that each touches the other. Gardner was surprised by fifteen readers discovering that actually seven cigarettes can be arranged with that condition ¹.

Some years later, in 1968, Littlewood ² raised the question if it possible in 3-space for seven infinite circular cylinders of unit radius each to touch all the others. Almost forty years later, in 2005, Bezdek ³ gave an upper bound of 24 for the number of mutually touching congruent infinite cylinders. In a very recent paper, Bozóki et al. ⁴ settle Littlewood’s problem describing two sets of seven mutually touching infinite cylinders.

Without loss of generality, the radius of the cylinders can be set to one. Thus, two cylinders being mutually touching is equivalent to their axes being at distance two. The authors exclude the case of parallel cylinders (with parallel axes), for which the maximum number of mutually touching cylinders is four.

The approach by Bozóki et al. is algebraic. First, they obtain a system of polynomial equations which describe the position of the axes of the cylinders. For a line , consider the parametric representation . The well-known formula for the distance of two skew lines in 3D states that

.

The requirement that these distances have to be two leads to the system

,

where the squares are taken in order to avoid square roots.

Introducing coordinates for the points and the vectors and using the well-known formula for the dot product of a vector and a cross product, the authors get a system of polynomial equations, each of degree 6 in 12 variables.

In order to simplify the system, Bozóki et al. observe that any arrangement of seven lines can be translated and rotated to a position in which one of the lines, say , is horizontal passing through in the direction of . Furthermore, it can also be assumed that goes through the point , so that the touching point of the first two cylinders is the origin and the only degree of freedom for the first two cylinders is the direction of the second one.

Further choosing this direction to be (hence orthogonal to the first one), reduces the problem to finding five lines , such that the distances between them, as well as their 10 distances to and are two. In this way, the system is reduced to 20 equations.

But there are still six unknowns for each line, corresponding to its point and direction vector, for a total of 30 unknowns. In order to reduce this number to 20, Bozóki et al. consider two further simplifications.

First, they observe that none of the sought five lines can be horizontal, since it would be parallel to and . Hence, for any value of all of them pass through the plane . In particular, this holds for , so the third coordinate of each can be settled to zero. This prunes out five unknowns. Second, the direction vectors are normalized so that their three coordinates sum up to one, which gets rid of five more unknowns.

In this way, Bozóki et al. come up to a system of 20 multivariate polynomial equations, of degree 6, with 20 unknowns.

The next step is showing the existence of solutions for this system. In order to do so, Bozóki et al. use symbolic and numerical computational techniques. They start by the polyhedral homotopy continuation method by Huber and Sturmfels ⁵, implemented in software HOM4PS-2.0 ⁶. Using the software MixedVol-2.0 ⁷, a total of 180,734 intermediate instances are obtained, which provide more than 120,000 million homotopy curves to be tracked.

These are processed in parallel by 12 cores in 2 Intel Xeon X5650 2.66 GHz CPUs, which is able to manage 20 million curves per month. The first solution showed up after processing 80 million curves and the second solution after another 25 million curves.

In order to verify correctness of the solutions, Bozóki et al. point up that the software HOM4PS-2.0 provides solutions up to 50 digits, of which the first 12 are ensured to be correct. This can be then used as a starting point for a floating-point arithmetic solver, like fsolve in Maple 13, which allowed the authors to check the results up to 10,000 digits.

However, since a large number of correct digits is still not mathematical correctness, they have applied two exact verifications methods: alphaCertified ⁸ and the interval Krawczyk method⁹.

This work leaves the open question of whether seven is the maximum number of mutually touching infinite cylinders. The authors note that applying the same ideas to the case of eight cylinders leads to a polynomial system of 25 variables and 27 equations, for which they are still seeking a solution.