Elias Stein : Real Analysis

Question

I cannot understand why this particular line in the text is true:

" Moreover, there are $O(k^{d-1})$ cubes in $\cal{Q}\ '$ "

For the text see

http://books.google.com/books?id=2Sg3Vug65AsC&pg=PA12&lpg=PA12&dq=elias+stein+Moreover,+there+are+O%28k+d%C2%A11+%29+cubes+2+in+Q+0&source=bl&ots=DCMQaf06nz&sig=1V3GKoVbY9Xq8uOdJtD7kpYS9ug&hl=en&sa=X&ei=UQYgVO7yH5GayAS_1IL4Bw&ved=0CCAQ6AEwAA#v=onepage&q=elias%20stein%20Moreover%2C%20there%20are%20O%28k%20d%C2%A11%20%29%20cubes%202%20in%20Q%200&f=false

Answer 1

In the text we have the following situation. Consider a rectangle $R$ in $\mathbb{R}^d$. Fix a grid of cubes of side length $1/k$ for $k\in\mathbb{N}$ large.

Let $\mathcal{Q}^\prime$ be the collection of grid cubes $Q$ such that $Q\cap R\not=\emptyset$ and $Q\cap R^c\not=\emptyset$ (it is formulated a bit ambiguously in the text, but this is clearly what is meant). That is, $\mathcal{Q}^\prime$ consists of the grid cubes that intersect the boundary of $R$. Note that the boundary of $R$ is a union of $(d-1)$-dimensional rectangles.

One grid cube intersects the boundary on a surface of size comparable to $(1/k)^{d-1}$. Thus to cover the entire boundary we need about $\frac{1}{(1/k)^{d-1}}=k^{d-1}$ grid cubes, up to a constant depending on the size of $R$. That is, $\mathcal{Q}^\prime$ contains $O(k^{d-1})$ cubes.

Answer 2

If one of the $d-1$ dimensional sides of the rectangle $R$ has dimensions $$ l_1\times l_2\times l_3\times\cdots\times l_{d-1} $$ then there are at most $$ \begin{align} &\lceil k l_1+1\rceil\cdot\lceil k l_2+1\rceil\cdot\lceil k l_3+1\rceil\cdots\lceil k l_{d-1}+1\rceil\\ &\le \lceil k\rceil^{d-1}\cdot\lceil l_1+1\rceil\cdot\lceil l_2+1\rceil\cdot\lceil l_3+1\rceil\cdots\lceil l_{d-1}+1\rceil\\ &=k^{d-1}\cdot\lceil l_1+1\rceil\cdot\lceil l_2+1\rceil\cdot\lceil l_3+1\rceil\cdots\lceil l_{d-1}+1\rceil \end{align} $$ cubes of side $\frac1k$ on that side of the rectangle, assuming $k$ is an integer.

This is the same for all $2d$ faces, and so there is some constant, depending on the dimensions of the $R$, so that the number of cubes is less than that constant times $k^{d-1}$; that is $O\left(k^{d-1}\right)$.