Hypercube partition ratio growth rates

Problem 1.2 · arXiv:2401.00299

arXiv Problem high confidence— first stated 2024-11-07

Authors: Noga Alon, Jozsef Balogh, Vladimir N. Potapov

Status partial high confidence

Problem 1.2 asks which of the four ratios m'(d)/m(d), f_{\leq 2}(d)/m'(d), f(d)/f_{\leq 2}(d), and f(d)/m(d) is exponential in n=2^{d-1}. The source paper itself resolves two parts: part (iv) f(d)/m(d) is proved exponential in n, and part (i) m'(d)/m(d) is proved subexponential. Parts (ii) and (iii) remain explicitly open in the paper. No follow-up work specifically resolving parts (ii) or (iii) was found in the literature through May 2026.

Reviewer notes. Parts (i) and (iv) of Problem 1.2 are resolved within the original paper itself: f(d)/m(d) is exponential in n (part iv), and m'(d)/m(d) is subexponential (part i). Parts (ii) f_{\leq 2}(d)/m'(d) and (iii) f(d)/f_{\leq 2}(d) are stated as open. The paper was published in Illinois Journal of Mathematics, Vol. 69, Issue 1, April 2025. An unrelated paper 2411.04479 studies partitions of Z_q^n into subcubes (a different algebraic setting) and does not address Problem 1.2. No other citing paper addressing the open parts was found.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Problem. What is the order of magnitude of the following ratios? In particular, which one of them is an exponential function of $n$? (i) $m^{\prime}(d)/m(d)$, (ii) $f_{\leq 2}(d)/m^{\prime}(d)$, (iii) $f(d)/f_{\leq 2}(d),$ (iv) $f(d)/m(d)$.

Context

The hierarchy $m(d) \leq m^{\prime}(d) \leq f_{\leq 2}(d) \leq f(d)$ holds by definition, where $n = 2^{d-1}$. The paper proves that $f(d)/m(d)$ (part iv) is exponential in $n$, and shows part (i) is subexponential; parts (ii) and (iii) remain open.

Source paper

Partitioning the hypercube into smaller hypercubes
Noga Alon, Jozsef Balogh, Vladimir N. Potapov · 2024-11-07
https://arxiv.org/abs/2401.00299