Nearly spherical cubes

Abstract:

What is the least surface area of a shape that tiles d-dimensional space when shifted by all vectors in the integer lattice? A unit cube is such a shape, and has surface area 2d. On the other hand, any such shape must have volume 1 and hence surface area at least that of the volume-1 ball, namely about sqrt(2 pi e) sqrt(d). We nearly close the gap, using a randomized construction to show that there exists a tiler with surface area at most 4 pi sqrt(d). The problem was originally motivated by questions in computational complexity theory; our construction generalizes a discretized solution given by Raz in the complexity-theory setting.