Dyadic rectangles in the $d$-dimensional unit cube

Question

Let $A = \{J \in \mathcal{D}^d([0, 1]^d) \mid |J| = 2^{-n}\}$ be the set of all dyadic rectangles in the $d$-dimensional unit cube with volume $2^{-n}$, where $J = I_1 \times \cdots \times I_d$ with $I_i$, $i = 1, \ldots, d$, dyadic intervals in $[0, 1]$. I want to find the cardinality of $A$. In fact I want to show that $\mathbf{card}(A) \approx 2^n n^{d - 1}$. I'll give an example: In the case $d=2$, we have $\mathbf{card}(A) =2^n (n+1)$, i.e, $n+1$ possible partitions of the square $[0,1]^2$. In each partitions the rectangles have area $2^{-n}$.

Answer 1

Take the cube $Q=[0,1]^d$ and consider the dyadic grid of scale $2^{-n}$ (that is, subdivide $Q$ in $2^{dn}$ cubes of sidelength $2^{-n}$ and volume $2^{-dn}$). Now we want to count how many rectangles of volume $2^{-n}$ there are. There are several different types of rectangles with $(0,0,\dots,0)$ as a corner, and then shifted versions of those.

Fix one of those shapes, and let $Q_{k_1, \dots, k_d}$ be a $d$-dimensional rectangle of volume $2^{-n}$, sides of length $2^{-k_1}, \dots, 2^{-k_d}$, where $k_i \geq 0$ for $i=1,\dots,d$ and $k_1 + \dots +k_d=n$, and having $(0,0,\dots,0)$ as a corner.

We have two things to count:

1. How many different types of rectangles can we have?
2. Given one type, how many different rectangles of the same type can we have inside $Q$?

For the first question, this corresponds to the number of solutions of $k_1 + \dots +k_d=n$. By Theorem two the number of solutions is ${n+d-1}\choose{n}$ which has the order of $n^{d-1}$ (as can be seen by writing out the factorials).

For the second question, fix a rectangle $Q_{k_1,\dots,k_d}$ and translate it so that one of its corners is the $(1,1,\dots,1)$ corner of $Q$. Now look at the translate of $(0,0,\dots,0)$, say $(p_1,\dots,p_d)$ (i.e. the point that $(0,0,\dots,0)$ is mapped to by the translation). We want to count the number of points $(x_1,\dots,x_d) \in Q$ of the dyadic grid of scale $2^{-n}$ with $x_i \leq p_i$ for every $i=1,\dots,d$. These are precisely the points we can translate the $(0,0,\dots,0)$ corner of $Q_{k_1,\dots,k_d}$ to so that it is still contained in $Q$.

We have $$ \prod_{i=1}^d \left( \frac{1-2^{-k_i}}{2^{-n}}+ 1\right) $$ points. In fact, fix the $i$-th coordinate. We have $p_i=1-2^{-k_i}=\frac{2^n-2^{k_1 \dots \hat{k_i}\dots k_d}}{2^n}$ and we want to count how many choices of $x_i$ there are. This is just the length of the interval $[0, p_i]$ divided by the scale of the grid, adding $1$ to include the right endpoint. Repeating the process for every coordinate and taking the product we get the expression above.

Now we have $$ \prod_{i=1}^d \left( \frac{1-2^{-k_i}}{2^{-n}}+ 1\right) \approx \prod_{i=1}^d \left( \frac{1-2^{-k_i}}{2^{-n}}\right) = 2^{dn} \prod_{i=1}^d \frac{2^{k_i}-1}{2^{k_i}} = \frac{2^{dn}}{2^n} \prod_{i=1}^d (2^{k_i}-1) \approx \frac{2^{dn}}{2^n} 2^n = 2^{dn}. $$

By multiplying the two results, we get $\mathbf{card}(A) \approx 2^{dn} n^{d-1}$. Note that your claim has a different exponent of $2$.