15
$\begingroup$

This is a followup to For what natural $n$ does there exist a square composed of $n$ squares?

Consider a natural $m$. For what natural $n$ does there exist an $m$-dimensional hypercube composed of $n$ many $m$-dimensional hypercubes?

In the case of $m=2$, it is shown that $n$ can be any natural other than $2$, $3$, or $5$.

In the case of $m=3$, I managed to show that $n$ can be any natural of the form $1+7a+19b+37c$, which covers all $n\ge71$. This was derived by noting that we can split a cube into $k^3$ pieces, and that we can also group $k^3$ equal sized pieces that are within a cube of each other into one big cube. By making a $(k+1)$-cube and then merging $k^3$ of the cubes into one $k$-cube, we can get $7$, $19$, and $37$ more cubes, as the cases of $k=1,2,3$. By a bunch of testing, I couldn't seem to improve upon this any further.

In general, we can show that we can have $n$ of the form $1+\alpha_1a+\alpha_2b+\alpha_3c+\alpha_4d+\dots$, where $\alpha_k=(k+1)^m-k^m$ by the same process as above.

Since I lack good means to visualize this, studying the $m=4$ case seems to be fairly challenging. If I've done this correctly, then it is possible to make a hypercube with $5^4$ unit hypercubes, merge $3^4$ of them into one, and then $2^4-1$ groups of $2^4$ hypercubes, the $-1$ due to one of the hypercubes intersecting the already merged $3^4$ hypercube. Doing this additionally lowers the above general bound down to all $n\ge1044$.

In general this process leads to letting us take $\alpha=(5^m-1)-(3^m-1)-(2^m-1)^2$ as a coefficient.

I'm unsure if this captures all of the cases, which I would doubt, and if not, then how can I in general?

$\endgroup$
  • 1
    $\begingroup$ For $n=3$ see here. $\endgroup$ – pregunton Jan 5 at 13:53
  • 1
    $\begingroup$ Oh cool. It seems I've missed $n=49,51,54$ cases. $\endgroup$ – Simply Beautiful Art Jan 5 at 14:11
  • 2
    $\begingroup$ There is a 1997. paper Dissecting d-Cubes into Smaller d-Cubes giving some relevant results. For example, all $n\ge809$ are possible for $m=4$ (improving your current $n\ge1044$ bound). For $m=5$, all $n\ge 1891$ are possible. For general $m$, if $n$ is too small, it appears to be hard to decide if some $n$ can be dissected or not. $\endgroup$ – Vepir Jan 9 at 0:03
  • $\begingroup$ I was classifying cubes based on how they can be obtained and just noticed that you say $1+7a+19b+37c$ covers all $n\ge 59$, but that is not the case as $61,63,68,70$ are never obtained by that equation ($a,b,c\ge 0$)? Instead it should be "covers all $n\ge 71$", or am I missing something? $\endgroup$ – Vepir Jan 15 at 16:46
  • $\begingroup$ @Vepir It would appear to be the case that you are right. $\endgroup$ – Simply Beautiful Art Jan 15 at 22:59
4
+100
$\begingroup$

Not a complete answer, just my idea and thoughts on it so far.


Summary

In short, I have split the problem into $c\in\mathbb N$ subproblems. It seems your initial coefficients idea is equivalent to $c=0,1$ combined with $n=n_2+(n_1-1)$ lemma, so you are missing solutions when $c\ge 2$ is not reachable by the lemma.

This is not a complete answer. I will present an idea and I will use it to replicate finding solvable $n$ for $m\le 3$, and find nontrivial $n=49, 51, 54$ that you missed. These are indeed the only three "hard" cases for $m=3$. Having said that, solving this for general $m$ will likely remain an open problem.

I haven't found anything significant online except this 1997. paper Dissecting d-Cubes into Smaller d-Cubes which solves $m\le 2$ and conjectures $m=3$ solution (the problem that wasn't solved at the time was proving not-found small cases of $n$ can't be done). Paper also gives some bounds on $m=4,5$ and asymptotics for general $m$. The $m=3$ case is now claimed solved (the small not-found $n$ have been proven impossible) according to mathworld (linked in comments by pregunton). The larger cases $m\ge 4$ are an open problem as far as I know.



The $c\in\mathbb N$ subproblem idea

Lemma. First note that if $n_1,n_2$ are possible, then so is $n_1+(n_2-1)$.

Also notice that two smallest cubes we can dissect into are always $n=1,2^m$.

I wanted to do a computer search on fixed $m$ to prove and disprove solutions of $n$ up to some bound $n\le n_0$. If $n_0$ is large enough, it will be easy to show all $n\ge n_0$ are possible as well. The idea was to solve the given $m$ case computationally, but there is one (or two) problem(s) that needs to be resolved (if possible) before the idea can be efficient.

Now, my idea was to split every $m$ (dimension) case into countably many cases. That is, every dissection of a cube contains either one case of $c=0,1,2,3\dots$ many composite cubes (cubes made of unit cubes).

(When I say "cube", I think of "$m$-cube".)

That is, start with a $k$-side cube ($k^m$ many unit $m$-cubes). We will be combining those cubes into $a_1,\dots,a_c$ side cubes. This will reduce the number of cubes by $a_i^m-1,i=1,\dots,c$. The problem becomes to find all $n$ for which some $(a_1,\dots,a_c)$ dissection is possible, where $1\lt a_1,\dots,a_c\lt k$ at least, and let $k\gt 1$.

$$ n=k^m-\sum_{i=1}^c a_i^m+c $$

Considering these equations for all possible $(a_1,\dots,a_c)$, will give all possible $n$. Note that to solve some $m$, only finitely many $c$ (dissection) cases need to be considered ($c\lt n_0$).

But the problem is that for $c\ge 2$ not all $(a_1,\dots,a_c)$ are possible. We need additional conditions to secure that $a_1,\dots,a_c$ side $m$-cubes can indeed be packed into a $k$-side $m$-cube in some way.

For $c=2$ for example, if you put $a_1$ in the corner, we are left with $k-a_1$ room in all of the $m$ dimensions (directions) hence $a_2\le k-a_1$. But if you put it some distance away from all corners, we get $a_2\le k-a_1-j$ which can only be worse. Of course we want to leave the most space free for $a_2$ after placing $a_1$, hence for $c=2$ the only additional restriction is $a_1+a_2\le k$, regardless of $m$. At the end I mention we have similar conditions for $c\le 2^m$. But for larger $c$, I do not see obvious (simple) conditions.

By using $n_1+(n_2-1)$ lemma on $c\le 2$ we can reach some of the $c\gt2$ cases (without needing to think about packing conditions), but not all of them, and this is when we miss some of the solutions.

I will first consider $m=1,2,3$ examples and show how to use this idea to search for solvable $n$.



Solving $(m\le 3)$ using the idea


$(m=1)$

For completion, you can include $m=1$. That is, we have a segment.

Combining any number of unit segments yields a segment, hence all $n\in\mathbb N$ are possible. Here it was sufficient to consider $c=0$ (use only unit $1$-cubes), to show that all $n$ have at least one dissection.


$(m=2)$

This was already solved as you already mentioned. For completion, lets see how my idea applies here.

(trivial cases): First, assume $n\ge2^2=4$ since $n=1,2^m$ are possible and $2,\dots,2^m-1$ are not.

Considering $c=0$, gives that all $n=k^2=(4),9,16,25\dots$ cubes are possible.

Considering $c=1$, $n=k^m-a_1^m+1$. Trying largest $a_1=k-1$ gives $k^2-(k-1)^2+1=2k$.

We obtained that all even numbers $n\ge 4$ are possible. Using the fact that $n_2=2^2=4$ is the smallest $2$-cube, and that we can combine cube dissections as $n_1+(n_2-1)$, we have that the smallest dissection increment is $(n_2-1)=3$. Hence, all $2k+3$ are also possible, giving all odd numbers $n\ge7$.

This leaves only nontrivial impossible case $n=5$, and all nontrivial possible cases are $n\ge 6$.

To solve $m=2$, all we used was the minimized $c=0,1$ cases and their combinations.

(It can be shown $n=5$ can't be obtained with $c\ge 2$ cases, so we are done.)


$(m=3)$

Generally, we assume $n\ge2^m$ since $n=1,2^m$ are possible and $2,\dots,2^m-1$ are not (trivial cases). The smallest dissection increment is hence $(n_2-1)=2^m-1$. In this case, we have it is $(2^3-1)=7$.

This case is solved as mentioned in the comments, so I will be going after reconstructing all claimed possible $n\le 54$ by applying a restricted search on $c$ cases. Combining those, it is easily shown all $n\ge 48$ are all possible.

$(3.1.)$ That is, we preform a solution search on $c=0,1$ for $n\le 54$, to obtain:

The $c=0$ gives $n=k^3=(8), 27, 64,\dots$

The $c=1,a_1=k-1$ gives $n=k^3-(k-1)^3+1= (8),20,38,62\dots$

The $c=1,a_1=k-2$ gives $n=k^3-(k-2)^3+1= (27),57,99\dots$

The $c=1,a_1=k-3$ or beyond gives $n\gt 54$.

Using $n_2=8$ on $(c=0,k=2)\to n_1=8$ we obtain $n=15,22,29,36,43,50,\dots$

Using $n_2=8$ on $(c=0,k=3)\to n_1=27$ we obtain $n=34,41,48,55,\dots$

Using $n_2=8$ on $(c=1,k-1=1,2)$ gives duplicates. On $(c=1,k=4)$ gives $n=45,52\dots$

Using $n_2=8$ on $(c=1,k-2=1)$ gives duplicates. On larger, gives $n\gt 54$.

We have now obtained all $n\le 54$ possible with inserting minimal $(n_2-1)$ into $c=0,1$, which are:

$$n=1, 8, 15, 20, 22, 27, 29, 34, 36, 38, 41, 43, 45, 48, 50, 52$$

We are missing $n=39,46,49,51,53,54$ to construct all claimed possible $n\le 54$.

The second smallest $(n_2-1)$ that we have (and is not a multiple of previous) is $(n_2-1)=(20-1)=19$.

Combining $19$ with $n\le 54$ we have so far yields additionally $n=39,46,53$ but not $n=49,51,54$.

Other such $(n_2-1)$ small enough are $26,33,37$, but they do not yield any additional $n\le 54$ solutions.

That is, $c=0,1$ (combined with $n_1,n_2$ lemma) gives all (claimed possible by mathworld and linked paper) $3$-cubes $n\le 54$ other than $n=49,51,54$.

$(3.2)$ We continue the $n=49,51,54$ solution search on $c= 2$ as follows:

For $c=2$ we have $n=k^3-(a_1^3+a_2^3)+2$ such that $a_1+a_2\le k$.

For $k=3$, we get $n=27-(a_1^3+a_2^3)+2\lt 49$.

For $k=4$ we get $n=64-(a_1^3+a_2^3)+2,(a_1,a_2)=(2,2)$, yielding $n=50$.

For $k\ge5$ we get $n\gt 54$.

And so on. Up to $c\le2^m=2^3=8$, we can verify there are no extra solutions. (Packing is possible if and only if we can pack the individual $m$-cubes in individual corners, which is a simple packing condition.) But for larger $c$, I do not see obvious simple packing conditions.

$(3.3)$ We continue the $n\le 54$ solution search on $c\gt 8$ as follows:

We need to search for $n=49,51,54$ in $c\gt 2^m$ cases, where I'm not sure about "if and only if" packing conditions, which makes this a problem now. (Each found $n$ with some $c$ equation needs to be proven a valid packing individually, if we do not know the "if and only if" conditions for that $c$).

To cut the story short, these three nontrivial ("hard") cases can be found as following dissections:

  • $c=13,k=6$ has a dissection $n=6^3-(9\cdot2^3+4\cdot3^3)+13=49$. That is, $$(a_1,\dots,a_{13})=(2,2,2,2,2,2,2,2,2,3,3,3,3)$$ are composite cubes used.

  • $c=10,k=6$ has a dissection $n=6^3-(5\cdot2^3+5\cdot3^3)+10=51$. That is, $$(a_1,\dots,a_{10})=(2,2,2,2,2,3,3,3,3,3)$$ are composite cubes used.

  • $c=12,k=8$ has a dissection $n=8^3-(4\cdot2^3+2\cdot3^3+6\cdot4^3)+12=54$. That is, $$(a_1,\dots,a_{12})=(2,2,2,2,3,3,4,4,4,4,4,4)$$ are composite cubes used.

To show that these packings (dissections) are possible, we fit the composite cubes in steps:

enter image description here

Where $\color{green}{green}$, $\color{blue}{blue}$, $\color{purple }{purple }$ are cubes of side lengths $2,3,4$, and $\color{orange }{orange }$ cubes are unit cubes. The number in a colored cube is how many cubes are placed there (at the bottom). Numbers in gray areas in down left corners are height of that area. Final image is filled cube.

With all of this, we have obtained all possible $n\le 54$ cubes claimed in linked paper and linked mathworld article. From $n_1+(n_2-1)$ lemma and these solvable $n\le 54$ cubes, it follows that all $n\ge 48$ cubes are possible.

It remains to prove that the not-found $n\lt 48$ cubes are not possible, to fully solve $m=3$. The mathworld link claims this was done, but I haven't found an explicit proof. To prove this with my method, we need to examine relevant $c$ cases (at worst all $c\lt 48$), but this is a problem since I haven't yet found "if and only if" packing conditions for all those cases.



Applying the idea to $(m\ge 4)$

Given any $m$, we could right now implement this idea as an algorithm and find bounds on some $n^{*}$ such that all $n\ge n^{*}$ are possible. But we will be missing some of the small (not large enough) $n\lt n^{*}$ solutions if we search only $c=0,1,2$, for example..

To find them all and prove we are not missing any solutions up to some $n^{*}$, we first need to find the packing conditions for $c\in\mathbb N$ values in general.

That is, we have the following question to overcome:

Given $m$-cubes of integer side lengths $a_1,\dots,a_c$, determine if we can fit them inside $m$-cube of integer side length $k$ or not (such that the remaining empty space can be completely filled with unit cubes)?

Of course it is not hard to start looking for necessary conditions and sufficient conditions for special cases of $c$. For example if $c\le2^m$ then packing is possible if and only if $(\forall i\ne 1)(a_i\le k-a_1)$ where $a_1$ is the largest $m$-cube (place $\le2^m$ cubes into the $2^m$ corners of the $m$-cube). But in general I'm not sure how to verify that I have all sufficient conditions or not.

Alternatively, perhaps there are algorithms to answer the posed question in general, so we can run a search on all necessary $c\in\mathbb N$ and not miss any small solutions. I haven't looked into this yet so this is where my work stops for now.

The best asymptotic on $n^{*}$ (according to linked paper) that is known is $O((2m)^{m-1})$, so we will need to check quite a lot of $c$ cases and $(a_1,\dots,a_c)$ cases, unless we can optimize this idea.

The bounds that the linked paper provides are $n^{*}\le809,1891$ for $m=4,5$.


Not a complete answer, just my idea. If I missed something so far, let me know.

$\endgroup$

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.