This lattice consists of the points in d-dimensional space whose coordinates are all integers. We address the following question:

Cubical Foam Problem: What is the least surface area of a bubble that partitions d-dimensional space periodically according to the integer lattice?

The Voronoi foam for the integer lattice consists of cubes of side length 1. In d dimensions, these cubes have surface area 2d. This grows linearly with the dimension, much higher than the known lower bound of . Are there more “spherical” cubes, which still tile by the integer lattice, but have surface area closer to that of a ball? This is the main question that we answer in this work.

The Cubical Foam Problem seems to have been first formally raised by Choe. 10 Choe showed that in two dimensions, the unit square whose surface area (perimeter) is 4 is not the optimal solution. Rather, the optimal solution is the isosceles hexagon shown in Figure 2, with 120° angles, side lengths and , andperimeterabout3.864.Choegave the three-dimensional version as an open problem. Prior to our work, the best known solution was simply to add depth to the Choe hexagon, transforming it into the prism shown in Figure 2, with surface area 5.864.11

The high-dimensional version of the Cubical Foam Problem was raised by Feige et al. 11 in 2007, who noted a surprising connection to a certain problem in theoretical computer science about computational hardness amplification. We shall explain the details of this connection later. A subsequent result of Raz24 on the limits of such amplification, using an idea from a related paper of Holenstein, 16 provided us with the tools to solve the high-dimensional Cubical Foam Problem.

1. 2. our results

•;We give a probabilistic construction proving the existence of a bubble that partitions d-dimensional space according to the cubic lattice and whose surface area is at most . Thus, our bubble is nearly spherical, in the sense that its surface area is larger than that of a sphere by only a constant multiplicative factor (about 3.04). The best previous constructions had surface area proportional to d (like the cube itself has). We conclude that the optimal solution to the Cubical Foam Problem has surface area proportional to the square-root of the dimension, just as in the more general Kelvin Foam Problem. Thus in high dimensions, integer-lattice til-

 

Figure 1. (Left) Four bubbles in the Kelvin Foam, formed by relaxing the voronoi cells of the body-centered cubic lattice. (Right) Seven bubbles in the Weaire–Phelan Foam, formed by relaxing the voronoi cells of the A15 Packing.

Figure 2. (Left) the Choe hexagon, Choe’s optimal solution to the Cubical Foam Problem in two dimensions. (Right) the hexagons extruded into three-dimensional prisms. the resulting three-dimensional cubical foam is not optimal; a solution with smaller average surface area is presented in this work.