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.