[proofplan] We index the two cubes by their generation and integer-vector labels and reduce to comparing them when one has generation at least as large as the other. The same-generation case follows because half-open dyadic cubes with the same side length tile $\mathbb{R}^n$ disjointly. The different-generation case reduces to a coordinate-wise comparison: in each coordinate, the lower-generation interval (longer) contains or is disjoint from the higher-generation interval (shorter), with no overlap configuration possible because both endpoints are integer multiples of the smaller side length. [/proofplan] [step:Index the two cubes by generation and integer label] By definition of $\mathcal{D}$, write \begin{align*} Q = Q_{k, m} = \prod_{i=1}^n [2^{-k} m_i, 2^{-k}(m_i + 1)), \qquad Q' = Q_{k', m'} = \prod_{i=1}^n [2^{-k'} m'_i, 2^{-k'}(m'_i + 1)), \end{align*} with $k, k' \in \mathbb{Z}$ and $m = (m_1, \dots, m_n) \in \mathbb{Z}^n$, $m' = (m'_1, \dots, m'_n) \in \mathbb{Z}^n$. Without loss of generality, $k \le k'$ — that is, $Q$ has side length $2^{-k}$ at least as large as $Q'$'s side length $2^{-k'}$. (If $k' < k$, swap the names of $Q$ and $Q'$; the conclusion is symmetric in the two cubes.) [/step] [step:Reduce the cube comparison to coordinate-wise interval comparisons] Both cubes are Cartesian products of half-open intervals on $\mathbb{R}$. For each coordinate index $i \in \{1, \dots, n\}$, define \begin{align*} J_i := [2^{-k} m_i, 2^{-k}(m_i + 1)), \qquad J'_i := [2^{-k'} m'_i, 2^{-k'}(m'_i + 1)), \end{align*} so $Q = \prod_{i=1}^n J_i$ and $Q' = \prod_{i=1}^n J'_i$. Two product sets satisfy: \begin{align*} Q \cap Q' = \prod_{i=1}^n (J_i \cap J'_i), \end{align*} and a product is empty iff at least one factor is empty. Hence: - $Q \cap Q' = \varnothing$ iff $J_i \cap J'_i = \varnothing$ for some $i$; - $Q \subseteq Q'$ iff $J_i \subseteq J'_i$ for every $i$; - $Q' \subseteq Q$ iff $J'_i \subseteq J_i$ for every $i$. It suffices to show that for each coordinate $i$, the pair $(J_i, J'_i)$ falls into one of these three configurations, with the configuration uniform across $i$ in a sense compatible with the cube-level conclusion. We make this precise in the next step. [/step] [step:Show that each coordinate pair $(J_i, J'_i)$ satisfies $J'_i \subseteq J_i$ or $J_i \cap J'_i = \varnothing$] Fix a coordinate $i$. Recall $k \le k'$. We claim: \begin{align*} \text{either } J'_i \subseteq J_i, \text{ or } J_i \cap J'_i = \varnothing. \end{align*} Compute. The interval $J_i = [2^{-k} m_i, 2^{-k}(m_i + 1))$ has length $2^{-k}$, and the interval $J'_i = [2^{-k'} m'_i, 2^{-k'}(m'_i + 1))$ has length $2^{-k'} \le 2^{-k}$ (since $k \le k'$). Subdivide $J_i$ into $2^{k' - k}$ half-open intervals of length $2^{-k'}$: \begin{align*} J_i = \bigsqcup_{\ell = 0}^{2^{k' - k} - 1} \left[ 2^{-k} m_i + \ell \cdot 2^{-k'}, \ 2^{-k} m_i + (\ell + 1) \cdot 2^{-k'} \right) = \bigsqcup_{\ell = 0}^{2^{k' - k} - 1} \left[ 2^{-k'}(2^{k' - k} m_i + \ell), \ 2^{-k'}(2^{k' - k} m_i + \ell + 1) \right). \end{align*} The disjoint-union notation $\bigsqcup$ is justified because consecutive half-open intervals share no points: the right endpoint of one equals the left endpoint of the next, but the right endpoint is excluded. This subdivision shows that $J_i$ equals the disjoint union of the half-open length-$2^{-k'}$ intervals indexed by integer labels $\ell$ in the range $\{2^{k' - k} m_i, 2^{k' - k} m_i + 1, \dots, 2^{k' - k} m_i + 2^{k' - k} - 1\}$. Now compare with $J'_i$. The interval $J'_i$ has integer label $m'_i$ at generation $k'$. Two cases: **Case A:** $m'_i \in \{2^{k' - k} m_i, \dots, 2^{k' - k} m_i + 2^{k' - k} - 1\}$. Then $J'_i$ equals one of the subdivision pieces of $J_i$, so $J'_i \subseteq J_i$. **Case B:** $m'_i \notin \{2^{k' - k} m_i, \dots, 2^{k' - k} m_i + 2^{k' - k} - 1\}$. Then $J'_i$ is disjoint from every subdivision piece of $J_i$, because distinct half-open length-$2^{-k'}$ intervals at the dyadic grid scale $2^{-k'}$ are disjoint (they have endpoints at integer multiples of $2^{-k'}$, and shifting the integer label by at least $1$ shifts the interval by at least $2^{-k'}$, equal to its full length, so no overlap is possible). Hence $J'_i \cap J_i = \varnothing$. So $J'_i \subseteq J_i$ in case A, and $J'_i \cap J_i = \varnothing$ in case B. The intermediate case ("$J'_i$ overlaps $J_i$ but is not contained in it") cannot occur. [/step] [step:Combine the coordinate dichotomies into a cube-level conclusion] By step 3, for each coordinate $i$, exactly one of these holds: - $J'_i \subseteq J_i$; - $J'_i \cap J_i = \varnothing$. Define $S := \{i \in \{1, \dots, n\} : J'_i \subseteq J_i\}$ and $S^c := \{1, \dots, n\} \setminus S$. **Case 1:** $S = \{1, \dots, n\}$, i.e., $J'_i \subseteq J_i$ for every $i$. Then $Q' = \prod_{i=1}^n J'_i \subseteq \prod_{i=1}^n J_i = Q$. Conclusion: $Q' \subseteq Q$. **Case 2:** $S \ne \{1, \dots, n\}$, i.e., there exists some $i_0 \in S^c$ with $J'_{i_0} \cap J_{i_0} = \varnothing$. Then \begin{align*} Q \cap Q' = \prod_{i = 1}^n (J_i \cap J'_i) = \varnothing, \end{align*} since the $i_0$-th factor of the product is empty. Conclusion: $Q \cap Q' = \varnothing$. These two cases exhaust all possibilities. The third conclusion in the theorem statement, $Q \subseteq Q'$, can occur only when $k \ge k'$; under the convention $k \le k'$ adopted in step 1, $Q \subseteq Q'$ reduces to $Q = Q'$ (when $k = k'$ and $S = \{1, \dots, n\}$, which forces $J'_i = J_i$ for all $i$ since both intervals have the same length, hence $m'_i = m_i$ and $Q = Q'$). Restoring symmetry, if the original inputs had $k' < k$ instead, swapping the roles of $Q$ and $Q'$ in cases 1 and 2 gives the alternative conclusion $Q \subseteq Q'$. Together: any pair $(Q, Q') \in \mathcal{D} \times \mathcal{D}$ falls into exactly one of $Q \cap Q' = \varnothing$, $Q \subseteq Q'$, or $Q' \subseteq Q$. [/step]