Bound $c(n)$, the least $k$ past which an $n$-cube splits into $k$ homothetic subcubes (Erdős #769)
Statement
Let $c(n)$ be minimal such that whenever $k\geq c(n)$ the $n$-dimensional unit cube can be decomposed into exactly $k$ homothetic $n$-dimensional cubes (axis-parallel cubes of possibly different sizes that tile the unit cube with disjoint interiors). Give good bounds for $c(n)$. In particular, is it true that $$c(n)\gg n^n?$$
Acceptance. FULLY RESOLVES: a proof establishing the order of growth of $c(n)$ — in particular a proof or disproof of $c(n)\gg n^n$ (e.g. matching upper and lower bounds up to constants), or a proof of Erdős's assertion that $c(n)>n^n$ whenever $n+1$ is prime. A machine-checkable proof (Lean/Coq) is preferred, otherwise a complete written proof with all steps. ADVANCES: (a) an improved upper or lower bound on $c(n)$ valid for all $n$ that is strictly better than the best bound stated in the background, with proof; (b) the exact value of $c(n)$ for a specific small $n\geq 3$ (for instance a proof of Meier's $c(3)=48$) accompanied by a reproducible dissection catalogue and an exhaustiveness certificate showing which $k<c(n)$ fail to be realizable; (c) extend OEIS A014544 (subcube counts realizable for the $3$-cube) to a new verified range with the search code. Deliver the proof file, or the search program plus attained bound plus a reproducible exhaustiveness certificate.
Background
Posed by Erdős and studied first by Hadwiger, who proved the lower bound $c(n)\geq 2^n+2^{n-1}$. In the plane it is easy to see $c(2)=6$, and Meier conjectured $c(3)=48$. Burgess and Erdős [Er74b] proved the upper bound $c(n)\ll n^{n+1}$, and Erdős wrote that he was 'certain' $c(n)>n^n$ whenever $n+1$ is prime. Hudelson [Hu98] showed that if $\gcd(2^n-1,3^n-1)=1$ then $c(n)<6^n$, and in general $c(n)\ll (2n)^{n-1}$. Connor and Marmorino [CoMa18] proved $c(n)\geq 2^{n+1}-1$ for all $n\geq 3$, together with $c(n)\leq 1.8\,n^{n+1}$ when $n+1$ is prime and $c(n)\leq e^2 n^n$ otherwise. For $n=3$ the set of realizable subcube counts is OEIS A014544 (numbers $k$ for which a cube dissects into $k$ subcubes); its complement is finite, and $c(3)$ equals one more than the largest non-representable $k$. No cash prize is attached. Listed as open on erdosproblems.com/769 (fetched 2026-07-13, status 'open', tagged 'number theory | geometry'). The attacker's tool: exhaustive enumeration of cube dissections for small $n$ (extend A014544 and pin down $c(3)$, $c(4)$), together with number-theoretic constructions behind the $(2n)^{n-1}$ and $6^n$ upper bounds; the asymptotic $c(n)\gg n^n$ question is proof-shaped.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #769 (T. F. Bloom) | website |
| REF-02 | OEIS A014544 — numbers of subcubes a cube can be divided into | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.