Erdős Problem #769

Problem 769 (Round 2)

1. ROUND-2 OBJECTIVE

Path (C): prove a fatal structural obstruction to one major proof strategy and replace the vague Round-1 relation with Problem 770 by a precise theorem.

Round 1 left the central question \[ c(n)\gg n^n \ ? \] open, and only noted informally that the condition $\gcd(2^n-1,3^n-1)=1$ can force unexpectedly small values of $c(n)$. The most promising Round-2 move is therefore to turn that heuristic relation into a clean inequality relating $c(n)$ to the function $h(n)$ from Problem 770.

2. Round-1 FOUNDATION USED

I use the following Round-1 material.

1. The definition of $c(n)$.
2. The Round-1 observation that cube refinements add increments of the form $m^n-1$.
3. For the final corollaries only: the fixed Round-1 definition of $h(n)$ from Problem 770.

No other Round-1 lemma is reused here.

3. NEW INSIGHT / TOOL (ROUND 2)

The new tool is an elementary numerical-semigroup lemma.

If a tiling with $k$ cubes exists, then refining one cube into an $m\times\cdots\times m$ grid produces a tiling with \[ k+(m^n-1) \] cubes. Thus the set of attainable tile counts contains translates of the numerical semigroup generated by the increments $m^n-1$.

When $m$ runs from $2$ up to $h(n)$, those increments have gcd $1$ by definition of $h(n)$. An elementary Frobenius-type bound then gives an explicit upper bound for $c(n)$ in terms of $h(n)$.

4. ATTACK PLAN (ROUND 2)

The exact Round-1 gap was: there was no theorem translating information about common divisors of \[ 2^n-1,3^n-1,\dots \] into an actual upper bound for $c(n)$.

I now prove:

Main Round-2 theorem. Let $h(n)$ be the function from Problem 770. Then \[ c(n)\le 2^n+(2^n-2)\left(h(n)^n-1\right)<2^n h(n)^n. \tag{4.1} \]

This has two immediate consequences.

1. If $h(n)$ is bounded on an infinite subsequence, then $c(n)/n^n\to 0$ on an infinite subsequence.
2. Therefore any positive answer to \[ c(n)\gg n^n \] would force \[ h(n)\ge \left(\frac12-o(1)\right)n, \] so in particular $\liminf h(n)=\infty$.

Thus Problem 769 is much more tightly linked to Problem 770 than Round 1 showed.

5. WORK (ROUND 2)

Let $D(n)$ denote the set of all integers $k$ for which the unit $n$-cube admits a decomposition into exactly $k$ smaller homothetic $n$-cubes.

Lemma 1 (basic refinement).

If $k\in D(n)$ and $m\ge 2$, then \[ k+(m^n-1)\in D(n). \]

Proof.

Take a decomposition of the unit cube into $k$ smaller cubes, choose one tile $C$, and subdivide $C$ by an $m\times\cdots\times m$ grid into $m^n$ congruent smaller cubes. All other tiles are left unchanged. One tile has been replaced by $m^n$ tiles, so the total number increases by $m^n-1$. $\square$

Lemma 2 (elementary Frobenius bound).

Let \[ 1<b_1<b_2<\cdots<b_t \] be positive integers with \[ \gcd(b_1,\dots,b_t)=1. \] Then every integer \[ N\ge (b_1-1)b_t \] can be written in the form \[ N=x_1b_1+\cdots+x_t b_t \qquad (x_1,\dots,x_t\in \mathbb Z_{\ge 0}). \] Equivalently, the Frobenius number is at most $(b_1-1)b_t-1$.

Proof.

Work modulo $b_1$. Because $\gcd(b_1,\dots,b_t)=1$, the residue classes of $b_2,\dots,b_t$ generate the whole additive group $\mathbb Z/b_1\mathbb Z$. Hence for every residue class $r\in \mathbb Z/b_1\mathbb Z$ there exists a nonnegative combination \[ s_r=x_2b_2+\cdots+x_t b_t \] with \[ s_r\equiv r \pmod{b_1}. \] Among all such representations of $r$, choose one minimizing \[ \ell_r:=x_2+\cdots+x_t. \]

I claim that \[ \ell_r\le b_1-1. \] Indeed, if $\ell_r\ge b_1$, write $s_r$ as a sum of $\ell_r$ terms, each term equal to one of $b_2,\dots,b_t$. Consider the $\ell_r+1$ partial sums modulo $b_1$. Since $\ell_r+1\ge b_1+1$, two partial sums are equal modulo $b_1$. Their difference is a nonempty subcollection of the summands whose total is $0$ modulo $b_1$. Removing this subcollection gives another nonnegative representation of the same residue class $r$ with strictly fewer than $\ell_r$ summands, contradiction. So $\ell_r\le b_1-1$.

Because every summand is at most $b_t$, we have \[ s_r\le \ell_r b_t\le (b_1-1)b_t. \] Now let $N\ge (b_1-1)b_t$. Choose $r\equiv N\pmod{b_1}$ and the corresponding $s_r$. Then \[ 0\le s_r\le (b_1-1)b_t\le N \] and \[ N-s_r\equiv 0\pmod{b_1}. \] Hence \[ N=s_r+q b_1 \] for some integer $q\ge 0$, which is the desired representation. $\square$

Theorem 3 (explicit upper bound for $c(n)$ in terms of $h(n)$).

For every $n\ge 2$, \[ c(n)\le 2^n+(2^n-2)\left(h(n)^n-1\right)<2^n h(n)^n. \]

Proof.

Set \[ m:=h(n). \] By definition of $h(n)$, \[ \gcd(2^n-1,3^n-1,\dots,m^n-1)=1. \] Start with the obvious $2^n$-grid decomposition of the unit cube, so $2^n\in D(n)$.

By Lemma 1, from any tiling we may add any increment $j^n-1$ with $2\le j\le m$. Hence \[ 2^n+S\subseteq D(n), \] where $S$ is the numerical semigroup generated by \[ 2^n-1,\ 3^n-1,\ \dots,\ m^n-1. \]

Apply Lemma 2 with \[ b_1=2^n-1,\qquad b_t=m^n-1. \] Every integer \[ N\ge (2^n-2)(m^n-1) \] lies in $S$. Therefore every integer \[ k\ge 2^n+(2^n-2)(m^n-1) \] lies in $D(n)$. By definition of $c(n)$, \[ c(n)\le 2^n+(2^n-2)(m^n-1). \] Finally, \[ 2^n+(2^n-2)(m^n-1) = (2^n-2)m^n+2 < 2^n m^n. \] $\square$

Corollary 4 (bounded $h(n)$ forces small $c(n)$ on a subsequence).

Suppose there exists $H\ge 2$ and infinitely many $n$ with $h(n)\le H$. Then for infinitely many $n$, \[ c(n)<(2H)^n. \] Consequently \[ \frac{c(n)}{n^n}\to 0 \] along an infinite subsequence.

Proof.

The theorem gives \[ c(n)<2^n h(n)^n\le (2H)^n \] for those $n$. Since $(2H)^n/n^n=(2H/n)^n\to 0$, the ratio $c(n)/n^n$ tends to $0$ along that subsequence. $\square$

Corollary 5 (a positive solution to Problem 769 would force linear growth of $h(n)$).

Assume that there exists a constant $\kappa>0$ such that \[ c(n)\ge \kappa n^n \] for all sufficiently large $n$. Then \[ h(n)\ge \frac{\kappa^{1/n}}{2}\,n = \left(\frac12-o(1)\right)n. \] In particular, \[ c(n)\gg n^n \qquad\Longrightarrow\qquad \liminf_{n\to\infty} h(n)=\infty, \] and in fact $h(n)$ would have to be asymptotically linear.

Proof.

Combine \[ \kappa n^n\le c(n)<2^n h(n)^n. \] Then \[ h(n)>\frac{\kappa^{1/n}}{2}\,n. \] Since $\kappa^{1/n}\to 1$, the stated asymptotic follows. $\square$

A check against the classical conditional case.

If $h(n)=3$, then Theorem 3 gives \[ c(n)\le 2^n+(2^n-2)(3^n-1)=6^n-2\cdot 3^n+2<6^n. \] So the classical condition $\gcd(2^n-1,3^n-1)=1$ fits perfectly into the new general framework.

6. ADVERSARIAL VERIFICATION

The new work has three possible weak points.

1. Does Lemma 1 really preserve the class of tilings? Yes. A homothetic cube can always be subdivided by an $m\times\cdots\times m$ grid into $m^n$ smaller homothetic cubes with disjoint interiors.

2. Does Lemma 2 require pairwise coprimeness? No. The proof only uses the single hypothesis $\gcd(b_1,\dots,b_t)=1$. The residue-class argument modulo $b_1$ and the partial-sum pigeonhole step are completely elementary and do not assume any pairwise gcd condition.

3. Is the final implication genuinely stronger than Round 1? Yes. Round 1 only remarked that the special case $h(n)=3$ (equivalently $\gcd(2^n-1,3^n-1)=1$) would force $c(n)<6^n$. Round 2 proves the general bound \[ c(n)<2^n h(n)^n \] for every $n$, and deduces the new implication \[ c(n)\gg n^n \Longrightarrow h(n)\ge \left(\frac12-o(1)\right)n. \]

So the Round-2 argument is gap-free and strictly stronger than the Round-1 conditional remark.

7. FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The original question about the true growth of $c(n)$ remains open. However, Round 2 proves a new structural theorem: \[ c(n)<2^n h(n)^n, \] where $h(n)$ is the Problem-770 cutoff for the gcd condition. This shows that any proof of \[ c(n)\gg n^n \] would automatically force \[ h(n)\ge \left(\frac12-o(1)\right)n, \] which is a much stronger consequence than anything extracted in Round 1.

8. COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 46%

9. REFERENCES

• T. F. Bloom, Erdős Problem #769, ErdosProblems.com, accessed 2026-03-07.
• P. Connor and P. Marmorino, Decomposing cubes into smaller cubes, Journal of Geometry 109 $2018$, Art. 19; checked for the currently recorded general upper and lower bounds.
• T. F. Bloom, Erdős Problem #770, ErdosProblems.com, accessed 2026-03-07.

Problem 769 (Round 2)

1. ROUND-2 OBJECTIVE

Path (C): prove a fatal structural obstruction to one major proof strategy and replace the vague Round-1 relation with Problem 770 by a precise theorem.

Round 1 left the central question \[ c(n)\gg n^n \ ? \] open, and only noted informally that the condition $\gcd(2^n-1,3^n-1)=1$ can force unexpectedly small values of $c(n)$. The most promising Round-2 move is therefore to turn that heuristic relation into a clean inequality relating $c(n)$ to the function $h(n)$ from Problem 770.

2. Round-1 FOUNDATION USED

I use the following Round-1 material.

1. The definition of $c(n)$.
2. The Round-1 observation that cube refinements add increments of the form $m^n-1$.
3. For the final corollaries only: the fixed Round-1 definition of $h(n)$ from Problem 770.

No other Round-1 lemma is reused here.

3. NEW INSIGHT / TOOL (ROUND 2)

The new tool is an elementary numerical-semigroup lemma.

If a tiling with $k$ cubes exists, then refining one cube into an $m\times\cdots\times m$ grid produces a tiling with \[ k+(m^n-1) \] cubes. Thus the set of attainable tile counts contains translates of the numerical semigroup generated by the increments $m^n-1$.

When $m$ runs from $2$ up to $h(n)$, those increments have gcd $1$ by definition of $h(n)$. An elementary Frobenius-type bound then gives an explicit upper bound for $c(n)$ in terms of $h(n)$.

4. ATTACK PLAN (ROUND 2)

The exact Round-1 gap was: there was no theorem translating information about common divisors of \[ 2^n-1,3^n-1,\dots \] into an actual upper bound for $c(n)$.

I now prove:

Main Round-2 theorem. Let $h(n)$ be the function from Problem 770. Then \[ c(n)\le 2^n+(2^n-2)\left(h(n)^n-1\right)<2^n h(n)^n. \tag{4.1} \]

This has two immediate consequences.

1. If $h(n)$ is bounded on an infinite subsequence, then $c(n)/n^n\to 0$ on an infinite subsequence.
2. Therefore any positive answer to \[ c(n)\gg n^n \] would force \[ h(n)\ge \left(\frac12-o(1)\right)n, \] so in particular $\liminf h(n)=\infty$.

Thus Problem 769 is much more tightly linked to Problem 770 than Round 1 showed.

5. WORK (ROUND 2)

Let $D(n)$ denote the set of all integers $k$ for which the unit $n$-cube admits a decomposition into exactly $k$ smaller homothetic $n$-cubes.

Lemma 1 (basic refinement).

If $k\in D(n)$ and $m\ge 2$, then \[ k+(m^n-1)\in D(n). \]

Proof.

Take a decomposition of the unit cube into $k$ smaller cubes, choose one tile $C$, and subdivide $C$ by an $m\times\cdots\times m$ grid into $m^n$ congruent smaller cubes. All other tiles are left unchanged. One tile has been replaced by $m^n$ tiles, so the total number increases by $m^n-1$. $\square$

Lemma 2 (elementary Frobenius bound).

Let \[ 1<b_1<b_2<\cdots<b_t \] be positive integers with \[ \gcd(b_1,\dots,b_t)=1. \] Then every integer \[ N\ge (b_1-1)b_t \] can be written in the form \[ N=x_1b_1+\cdots+x_t b_t \qquad (x_1,\dots,x_t\in \mathbb Z_{\ge 0}). \] Equivalently, the Frobenius number is at most $(b_1-1)b_t-1$.

Proof.

Work modulo $b_1$. Because $\gcd(b_1,\dots,b_t)=1$, the residue classes of $b_2,\dots,b_t$ generate the whole additive group $\mathbb Z/b_1\mathbb Z$. Hence for every residue class $r\in \mathbb Z/b_1\mathbb Z$ there exists a nonnegative combination \[ s_r=x_2b_2+\cdots+x_t b_t \] with \[ s_r\equiv r \pmod{b_1}. \] Among all such representations of $r$, choose one minimizing \[ \ell_r:=x_2+\cdots+x_t. \]

I claim that \[ \ell_r\le b_1-1. \] Indeed, if $\ell_r\ge b_1$, write $s_r$ as a sum of $\ell_r$ terms, each term equal to one of $b_2,\dots,b_t$. Consider the $\ell_r+1$ partial sums modulo $b_1$. Since $\ell_r+1\ge b_1+1$, two partial sums are equal modulo $b_1$. Their difference is a nonempty subcollection of the summands whose total is $0$ modulo $b_1$. Removing this subcollection gives another nonnegative representation of the same residue class $r$ with strictly fewer than $\ell_r$ summands, contradiction. So $\ell_r\le b_1-1$.

Because every summand is at most $b_t$, we have \[ s_r\le \ell_r b_t\le (b_1-1)b_t. \] Now let $N\ge (b_1-1)b_t$. Choose $r\equiv N\pmod{b_1}$ and the corresponding $s_r$. Then \[ 0\le s_r\le (b_1-1)b_t\le N \] and \[ N-s_r\equiv 0\pmod{b_1}. \] Hence \[ N=s_r+q b_1 \] for some integer $q\ge 0$, which is the desired representation. $\square$

Theorem 3 (explicit upper bound for $c(n)$ in terms of $h(n)$).

For every $n\ge 2$, \[ c(n)\le 2^n+(2^n-2)\left(h(n)^n-1\right)<2^n h(n)^n. \]

Proof.

Set \[ m:=h(n). \] By definition of $h(n)$, \[ \gcd(2^n-1,3^n-1,\dots,m^n-1)=1. \] Start with the obvious $2^n$-grid decomposition of the unit cube, so $2^n\in D(n)$.

By Lemma 1, from any tiling we may add any increment $j^n-1$ with $2\le j\le m$. Hence \[ 2^n+S\subseteq D(n), \] where $S$ is the numerical semigroup generated by \[ 2^n-1,\ 3^n-1,\ \dots,\ m^n-1. \]

Apply Lemma 2 with \[ b_1=2^n-1,\qquad b_t=m^n-1. \] Every integer \[ N\ge (2^n-2)(m^n-1) \] lies in $S$. Therefore every integer \[ k\ge 2^n+(2^n-2)(m^n-1) \] lies in $D(n)$. By definition of $c(n)$, \[ c(n)\le 2^n+(2^n-2)(m^n-1). \] Finally, \[ 2^n+(2^n-2)(m^n-1) = (2^n-2)m^n+2 < 2^n m^n. \] $\square$

Corollary 4 (bounded $h(n)$ forces small $c(n)$ on a subsequence).

Suppose there exists $H\ge 2$ and infinitely many $n$ with $h(n)\le H$. Then for infinitely many $n$, \[ c(n)<(2H)^n. \] Consequently \[ \frac{c(n)}{n^n}\to 0 \] along an infinite subsequence.

Proof.

The theorem gives \[ c(n)<2^n h(n)^n\le (2H)^n \] for those $n$. Since $(2H)^n/n^n=(2H/n)^n\to 0$, the ratio $c(n)/n^n$ tends to $0$ along that subsequence. $\square$

Corollary 5 (a positive solution to Problem 769 would force linear growth of $h(n)$).

Assume that there exists a constant $\kappa>0$ such that \[ c(n)\ge \kappa n^n \] for all sufficiently large $n$. Then \[ h(n)\ge \frac{\kappa^{1/n}}{2}\,n = \left(\frac12-o(1)\right)n. \] In particular, \[ c(n)\gg n^n \qquad\Longrightarrow\qquad \liminf_{n\to\infty} h(n)=\infty, \] and in fact $h(n)$ would have to be asymptotically linear.

Proof.

Combine \[ \kappa n^n\le c(n)<2^n h(n)^n. \] Then \[ h(n)>\frac{\kappa^{1/n}}{2}\,n. \] Since $\kappa^{1/n}\to 1$, the stated asymptotic follows. $\square$

A check against the classical conditional case.

If $h(n)=3$, then Theorem 3 gives \[ c(n)\le 2^n+(2^n-2)(3^n-1)=6^n-2\cdot 3^n+2<6^n. \] So the classical condition $\gcd(2^n-1,3^n-1)=1$ fits perfectly into the new general framework.

6. ADVERSARIAL VERIFICATION

The new work has three possible weak points.

1. Does Lemma 1 really preserve the class of tilings? Yes. A homothetic cube can always be subdivided by an $m\times\cdots\times m$ grid into $m^n$ smaller homothetic cubes with disjoint interiors.

2. Does Lemma 2 require pairwise coprimeness? No. The proof only uses the single hypothesis $\gcd(b_1,\dots,b_t)=1$. The residue-class argument modulo $b_1$ and the partial-sum pigeonhole step are completely elementary and do not assume any pairwise gcd condition.

3. Is the final implication genuinely stronger than Round 1? Yes. Round 1 only remarked that the special case $h(n)=3$ (equivalently $\gcd(2^n-1,3^n-1)=1$) would force $c(n)<6^n$. Round 2 proves the general bound \[ c(n)<2^n h(n)^n \] for every $n$, and deduces the new implication \[ c(n)\gg n^n \Longrightarrow h(n)\ge \left(\frac12-o(1)\right)n. \]

So the Round-2 argument is gap-free and strictly stronger than the Round-1 conditional remark.

7. FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The original question about the true growth of $c(n)$ remains open. However, Round 2 proves a new structural theorem: \[ c(n)<2^n h(n)^n, \] where $h(n)$ is the Problem-770 cutoff for the gcd condition. This shows that any proof of \[ c(n)\gg n^n \] would automatically force \[ h(n)\ge \left(\frac12-o(1)\right)n, \] which is a much stronger consequence than anything extracted in Round 1.

8. COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 46%

9. REFERENCES

• T. F. Bloom, Erdős Problem #769, ErdosProblems.com, accessed 2026-03-07.
• P. Connor and P. Marmorino, Decomposing cubes into smaller cubes, Journal of Geometry 109 $2018$, Art. 19; checked for the currently recorded general upper and lower bounds.
• T. F. Bloom, Erdős Problem #770, ErdosProblems.com, accessed 2026-03-07.

OBJECTIVE AND REVIEW OF ALL VERSIONS

Erdős #769; independent attempt, 2026-09-23. Let $c(n)$ be the least threshold above which every integer occurs as the number of smaller homothetic cubes in a decomposition of the unit $n$-cube. Seek good bounds, especially whether $c(n)\gg n^n$. I read both 769.tex and 769_v2.tex completely. Their argument correctly uses the semigroup generated by $j^n-1$, but its residue threshold and initial tiling can both be sharpened.

WORK: THE EXACT THRESHOLD FOR A FIXED REFINEMENT FAMILY

Let $h$ be the least integer such that $\gcd(2^n-1,\ldots,h^n-1)=1$, put $a=2^n-1$, and let $S$ be the additive semigroup generated by those increments. For each residue $r$ modulo $a$, let $s_r$ be the smallest element of $S$ in that residue. Such elements exist because the generators span the finite cyclic group; nonnegative combinations suffice since the inverse of any residue is a nonnegative multiple of it. The largest integer outside $S$ is exactly \[ F=\max_{0\le r<a}s_r-a. \] Indeed in residue $r$, every $s_r+ja$, $j\ge0$, is represented and no smaller nonnegative integer in that residue is represented. Thus the last omission in that residue is $s_r-a$, with negative values harmless. For every positive $u\in S$, the count $1+u$ is realizable: start with the whole cube and apply the grid refinements corresponding to a representation of $u$. Its first positive increment already subdivides the original cube into smaller cubes. Consequently \[ c(n)\le F+2. \tag{1} \] Set $b=h^n-1$. A shortest path to any residue using the generator residues visits no residue twice, so it has at most $a-1$ edges. Its weight is at most $(a-1)b$, and minimal-weight $s_r$ is no larger. Therefore \[ c(n)\le(a-1)b-a+2 =(2^n-2)(h^n-1)-2^n+3. \tag{2} \] This subtracts $2^{n+1}-3$ from the supplied bound. If $h=3$, coprimeness makes $0,b,\ldots,(a-1)b$ exactly the least representatives, giving $F=ab-a-b$ and the sharper displayed form $c(n)\le(2^n-2)(3^n-2)+1$.

ADVERSARIAL VERIFICATION AND REMAINING GAP

All arguments concern a sufficient family of grid refinements. An omitted semigroup count need not be an impossible geometric tiling count, so $F+2$ is not asserted equal to $c(n)$. For example the two-generator bound at $n=2$ is $15$, while the official entry gives $c(2)=6$. The improvement to the supplied estimate is finite and does not change its exponential scale or settle the conjectured lower bound. The residue formula is the standard numerical-semigroup argument, proved here rather than claimed new.

SOURCES CHECKED

Both complete local versions; official indexed statement and background https://www.erdosproblems.com/history/769. All inequalities newly derived above are elementary and do not depend on the cited geometric bounds.

FINAL

UNRESOLVED. The refinement-family threshold is made exact and its elementary upper bound sharpened; the growth of $c(n)$ remains open.

COMPLETION ESTIMATE

Subjective progress toward the original asymptotic problem. COMPLETION: 10%