How many $n$-dimensional unit cubes are needed to cover a cube with side lengths $1+\epsilon$ for some $\epsilon>0$?

For n=1, the answer is obviously two. For n=2, the drawing below shows that three unit cubes suffice, but it is impossible using only two cubes. In general, a total of $n+1$ cubes is enough, as is shown in Agol's answer, but is this the smallest number possible?

(source: folk.uio.no)

  • 3
    $\begingroup$ Why does it seem that n+1 is sufficient? This is not obvious to me even for n = 3. $\endgroup$ – user332 Dec 16 '10 at 18:47
  • 5
    $\begingroup$ Yes, $n+1$ is OK. With one unit cube, you can cover an $(n-1)$-dimensional face, just as shown in the figure. Then select one vertex $S$ of the larger cube. Use $n$ unit cubes to cover the $(n-1)$-faces attached to $S$. There remains to cover a compact set which contains only the opposite vertex, which can be covered with one unit cube. $\endgroup$ – Denis Serre Dec 16 '10 at 20:49
  • 9
    $\begingroup$ @Denis Serre: How do you cover one n-1-dimensional face with one cube? What is the largest square that will fit inside a cubical box? If you look at cross-sections of the unit n-cube that are perturbation cross-sections parallel to a face, the shape is determined by the slope, a linear function: the unit n-1-cube can be stretched by any linear function. You can't get a larger n-1 cube that way. For n=3, I see how to cover one of the n-1 faces except for a neighborhood of one of its edges. With 3 cubes, you can cover 2- faces attached to S, so 4 works. $\endgroup$ – Bill Thurston Dec 16 '10 at 21:11
  • 4
    $\begingroup$ For the n=3 case, see mathworld.wolfram.com/PrinceRupertsCube.html for how to cover a (1+epsilon) square by a single cube. After three faces of the large cube adjacent to a single vertex are covered in this way, the remaining part of the large cube can be covered by a fourth unit cube, exactly as in the n=2 case. $\endgroup$ – David Eppstein Dec 17 '10 at 0:03
  • 4
    $\begingroup$ For the n=3 case, I found the following picture useful : mathworld.wolfram.com/CubeSquareInscribing.html $\endgroup$ – François Brunault Dec 17 '10 at 23:28

I'll expand my comment into an answer. Following Serre's suggestion in the comments, to show that $n+1$ unit cubes cover an $n$-cube of side lengths $1+\epsilon$ for some $\epsilon > 0$, it suffices to show that one may fit a unit $n-1$-cube in the interior of a unit $n$-cube. If you can do this, then you can fit a $1+\epsilon$ $n-1$-cube in the interior of a unit $n$-cube for some $\epsilon$. As Serre suggests, you may then take a vertex of the $1+\epsilon$ $n$-cube, and cover each of the $n$ $n-1$-cube faces containing it by a unit $n$-cube. Then one may use another $n$-cube to cover the antipodal vertex and the rest of the cube, possibly for a smaller $\epsilon$. This case $n=2$ is in the picture given in the question. As Bill points out in the comments, one needs an explanation as to why an $n-1$-cube fits in the interior of the $n$-cube.

To see that a unit $n-1$-cube fits in the interior of an $n$-cube, one may proceed by induction. This is true for $n=1$. Let $I=[0,1]$. By induction, suppose we have an embedding $f: I^{n-1}\to int(I^n)$. Then we have an embedding $f\times Id: I^{n-1}\times I \to int(I^n)\times I$. This gives a map which touches the boundary of $I^{n+1}$ only along $f(I^{n-1})\times \{0,1\}$. Think of this as a map $f×e:I^{n−1}\times I\hookrightarrow f(I^{n−1})\times D^2\subset f(I^{n−1})\times I\times \mathbb{R}$ ($\mathbb{R}$ is just the normal bundle to $f(I^{n-1})\times I \subset I^n\times I = I^{n+1}$). Then rotate the interval $I$ in $D^2$ by a small angle $\theta$ to get a map $e_{\theta}:I\to D^2\subset I\times \mathbb{R}$. The endpoints no longer lie on $\{0,1\}\times \mathbb{R}$. Then the map $f \times e_{\theta}: I^{n-1}\times I \to f(I^{n-1})\times D^2$ will have image in $int(I^{n+1})$ for small enough $\theta$.

  • 1
    $\begingroup$ Thanks Agol, this is a nice argument! This shows that $n+1$ cubes is always enough. The question whether $n+1$ is the smallest possible number is still open. $\endgroup$ – J.C. Ottem Dec 18 '10 at 1:48
  • $\begingroup$ @Agol. It seems that the construction proposed by Denis and you implies the following : for sufficiently small $\epsilon>0$, it is possible to arrange $n$ unit hypercubes in the $(1+\epsilon)$-hypercube in such a way that the region not covered by them is arbitrarily small. Is it true? $\endgroup$ – François Brunault Dec 18 '10 at 13:09
  • 1
    $\begingroup$ @Francois: I don't think so, at least this doesn't follow from the argument. The point is that if you can cover the $n$ faces adjacent to a vertex of a $1+\epsilon$ cube with unit cubes, then they cover some $\delta$ neighborhood of those faces. So you know that there will be a $1+\epsilon-\delta$ cube left over, and by adjusting $\epsilon$, you can make sure that a unit cube can cover what is left over. $\endgroup$ – Ian Agol Dec 18 '10 at 18:52
  • $\begingroup$ @Agol : Oh, I see now, thanks... For $n=3$ at least, I got more or less convinced that 3 cubes are sufficient to cover everything but a small neighborhood of $S'$, the vertex opposite to $S$. But I wouldn't swear to it, because my 3D perception is limited... $\endgroup$ – François Brunault Dec 18 '10 at 22:18
  • $\begingroup$ Francois (forgive my limited typeset), I had a visualization difficulty too, until I cut out the rectilinear cube and saw that I just had a union of thin prisms adjacent to one vertex left to cover. It makes me wonder if I can use a "volume-greedy" cover which involves 2 rectilinear cubes and (n-2) other cubes to cover a large enough neighborhood which surrounds the uncovered ring of dimension (n-2) "edges". Gerhard "Ask Me About System Design" Paseman, 2010.12.18 $\endgroup$ – Gerhard Paseman Dec 18 '10 at 23:27

I had this very same question posted on my web page http://webhome.auburn.edu/~kuperwl/ for more than 20 years. To the best of my knowledge, the complete answer is still unknown.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.