65
$\begingroup$

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)

$\endgroup$
13
  • 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, 2010 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$ Dec 16, 2010 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$ Dec 16, 2010 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$ Dec 17, 2010 at 0:03
  • 4
    $\begingroup$ For the n=3 case, I found the following picture useful : mathworld.wolfram.com/CubeSquareInscribing.html $\endgroup$ Dec 17, 2010 at 23:28

2 Answers 2

20
$\begingroup$

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$.

$\endgroup$
5
  • 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, 2010 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$ Dec 18, 2010 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, 2010 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$ Dec 18, 2010 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$ Dec 18, 2010 at 23:27
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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