we-solve (beta)

Math-928-A2 · revision r1 · on Math-928

gpt pro 5.2 attempt on Math-928

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Problem 769
  2. 1. Formal restatement
  3. Question (Erdős).
  4. 2. Quick literature/context check (web-browsing was available)
  5. 3. Strategy
  6. 4. Work
  7. 4.1 The case $n=2$: a complete determination $c(2)=6$
  8. 4.2 Bounds in higher dimension (quoted)
  9. 5. Obstacles/checks
  10. 6. Conclusion
  11. 7. If UNRESOLVED: what we have and what is missing

Problem 769

1. Formal restatement

Definition (Cube decompositions and $c(n)$): Fix $n\ge 2$. Let $Q_n=[0,1]^n$ be the unit $n$-cube. A decomposition of $Q_n$ into $k$ (smaller) $n$-cubes means a partition of $Q_n$ into $k$ closed sets with disjoint interiors, each of which is an $n$-dimensional cube similar to $Q_n$ (i.e. a homothetic copy; equivalently: a translate of a scaled copy).

Define $c(n)$ to be the smallest integer such that for every integer $k\ge c(n)$, the cube $Q_n$ admits a decomposition into $k$ smaller $n$-cubes.

Question (Erdős).
Give good bounds for $c(n)$; in particular, is it true that $c(n)\gg n^n$?

2. Quick literature/context check (web-browsing was available)

The ErdosProblems project page for #769 summarizes the classical results and cites work of Hudelson $1998$ and Connor--Marmorino $2018$. Connor--Marmorino prove (among other results) the bounds \[ c(n)\ge 2^{n+1}-1\ \ (n\ge 3), \qquad c(n)\le e^2 n^n\ \ (n+1\text{ composite}), \qquad c(n)\le 1.8\,n^{n+1}\ \ (n+1\text{ prime}). \] No resolution of the growth question "$c(n)\gg n^n$?" was found in this quick check.

3. Strategy

To prove $c(n)\gg n^n$ one would need a mechanism preventing decompositions for some $k$ of size $\ll n^n$. Known lower bounds are only exponential in $n$.

To disprove $c(n)\gg n^n$ it would suffice to construct decompositions for all $k\ge C^n$ for some fixed $C$ (much smaller than $n$ for large $n$). Hudelson proved an upper bound $c(n)<6^n$ under the number-theoretic condition $\gcd(2^n-1,3^n-1)=1$; if that condition holds for infinitely many $n$, then $c(n)/n^n\to 0$ along that subsequence. However, whether $\gcd(2^n-1,3^n-1)=1$ infinitely often is itself a difficult open problem (see also Problem #770 / #820).

What we can do completely here is settle the planar case $n=2$ (which is classical): $c(2)=6$.

4. Work

4.1 The case $n=2$: a complete determination $c(2)=6$

Theorem: For the unit square $Q_2=[0,1]^2$, one has $c(2)=6$. Equivalently: for every integer $k\ge 6$ the unit square can be tiled by $k$ smaller squares, and there is no tiling by $5$ squares.
Proof: We prove (i) impossibility for $k=5$ and (ii) existence for every $k\ge 6$.

(i) No tiling by 5 squares. Assume for contradiction that $[0,1]^2$ is tiled by exactly $5$ squares. Each of the four corners of the unit square must belong to some tile. A single tile cannot contain two distinct corners of the unit square unless it is the whole unit square (side length $1$), which is impossible here. Hence four distinct tiles cover the four corners. Let the fifth tile be the unique tile that is not a corner tile.

A non-corner tile cannot touch two adjacent sides of the unit square: if a square touches both the bottom edge $y=0$ and the left edge $x=0$, its bottom-left corner must be $(0,0)$, i.e. it would be a corner tile. Similarly it cannot touch two opposite sides (that would force side length $1$). Therefore the fifth tile touches at most one side of the boundary. By symmetry, assume it touches the bottom edge but not a corner.

Let the bottom-left corner tile have side length $a$ and the top-left corner tile have side length $d$. Since no non-corner tile touches the left edge, these two tiles partition the entire left edge, so \begin{equation} a+d=1. \tag{1} \end{equation} Similarly, if the bottom-right and top-right corner tiles have side lengths $b$ and $c$, then \begin{equation} b+c=1. \tag{2} \end{equation} Since the fifth tile does not touch the top edge, the two top corner tiles partition the entire top edge, so \begin{equation} d+c=1. \tag{3} \end{equation} From $1$ and $3$ we get $a=c$, and then from $2$ we get $b=1-c=1-a$. Now look again at the bottom edge: it is covered by the bottom-left corner tile (length $a$), the fifth tile (some positive length $e>0$), and the bottom-right corner tile (length $b$), so \begin{equation} a+e+b=1. \tag{4} \end{equation} Substituting $b=1-a$ into $4$ gives $a+e+(1-a)=1$, hence $e=0$, contradiction. So no tiling by $5$ squares exists.

(ii) Tilings for every $k\ge 6$. We exhibit explicit tilings for $k\in\{6,7,8\}$ and then show how to increase the number of tiles by $3$.

  • A $6$-tiling: one square of side $2/3$ and five squares of side $1/3$. Concretely, take the square $[0,2/3]\times[0,2/3]$ and tile the remaining region by five $1/3$-squares: \begin{align*} &[0,1/3]\times[2/3,1],\quad [1/3,2/3]\times[2/3,1],\\ &[2/3,1]\times[0,1/3],\quad [2/3,1]\times[1/3,2/3],\quad [2/3,1]\times[2/3,1]. \end{align*}
  • A $7$-tiling: start with the $2\times 2$ grid of four squares of side $1/2$ and subdivide one of them into four squares of side $1/4$. For instance, subdivide the top-left $[0,1/2]\times[1/2,1]$ into a $2\times 2$ grid.
  • An $8$-tiling: one square of side $3/4$ and seven squares of side $1/4$. Concretely, take the square $[0,3/4]\times[0,3/4]$ and tile the remaining region by seven $1/4$-squares: four along the top strip $[0,1]\times[3/4,1]$ and three along the right strip $[3/4,1]\times[0,3/4]$.

Now observe the following operation. Given any tiling by $k$ squares, choose any tile that is a square of side length $s$ and subdivide it into four congruent squares of side length $s/2$ (a $2\times 2$ grid). This replaces one tile by four tiles and hence increases the number of tiles from $k$ to $k+3$.

Therefore, starting from the base tilings for $6,7,8$, we obtain tilings for \[ 6+3t,\qquad 7+3t,\qquad 8+3t\qquad (t\ge 0). \] Every integer $k\ge 6$ is congruent to exactly one of $6,7,8$ modulo $3$, so every $k\ge 6$ is achievable. Combining with (i), we conclude $c(2)=6$. ∎

4.2 Bounds in higher dimension (quoted)

For $n\ge 3$, the determination of $c(n)$ is open. The best bounds located in the quick literature check are those quoted above from Connor--Marmorino $2018$. In particular, the lower bound is exponential in $n$, while the upper bound is about $n^n$ (up to constants and an extra $n$ factor when $n+1$ is prime). This leaves the growth question $c(n)\gg n^n$ wide open.

5. Obstacles/checks

The threshold property in the definition of $c(n)$ ("all $k\ge c(n)$") is delicate: it is not enough to construct many values of $k$ (like perfect powers $m^n$), one needs a method that reaches every large $k$. Current constructions are number-theoretic and seem closely tied to gcd-type constraints such as $\gcd(2^n-1,3^n-1)$.

6. Conclusion

UNRESOLVED (for general $n$). We determined the planar value $c(2)=6$ with a complete proof. For $n\ge 3$, the best known bounds (in the quick literature check) are \[ 2^{n+1}-1\le c(n)\le e^2 n^n\quad (n+1\text{ composite}), \qquad 2^{n+1}-1\le c(n)\le 1.8\,n^{n+1}\quad (n+1\text{ prime}), \] and whether $c(n)\gg n^n$ remains open.

7. If UNRESOLVED: what we have and what is missing

  • Strongest proved statement here: $c(2)=6$.
  • First genuine gap toward "$c(n)\gg n^n$": producing any lower bound that is super-exponential in $n$ (or even of order $n^n$), or alternatively producing a construction forcing $c(n)$ to be $o(n^n)$.
  • Notable conditional route to disprove $c(n)\gg n^n$: if $\gcd(2^n-1,3^n-1)=1$ for infinitely many $n$, then (by Hudelson's result) $c(n)<6^n$ along an infinite subsequence, hence $c(n)/n^n\to 0$ on that subsequence.