I have a problem which requires this exercise to proof a statement:

Exercise 2: Let $p = (p_1,p_2,...,p_n)$ and $q = (q_1,q_2,...,q_n)$ be points in $\mathbb{R}^n$ with $p_k < q_k$ for each $k$. Let $R = [p_1,q_1]\times...\times[p_n,q_n]$ and show that

$\mbox{diam}(R) = d(p,q) = [\sum_{k=1}^{n}(q_k-p_k)^2]^{\frac{1}{2}}.$

My problem is:

Let $F = [a_1,b_1]\times...\times[a_n,b_n]\subset \mathbb{R}^n$ and let $\epsilon > 0$; use Exercise 2 to show that there are rectangles $R_1,...,R_m$ such that $F = \cup_{k=1}^{m}R_k$ and diam$R_k < \epsilon$ for each $k$. If $x_k \in R_k$, then it follows that $R_k \subseteq B(x_k;\epsilon).$

Possible solution:

By the Archimidean Principle, we can pick $m \in \mathbb{N}$ such that

$\sqrt{\sum_{i = 2}^{n}(b_i - a_i)^2 + \frac{(b_1 - a_1)^2}{m^2}} < \epsilon.$

Define \begin{align*} R_1 &= [a_1, a_1 + \frac{(b_1 - a_1)}{m}]\times[a_2,b_2]\times...\times[a_n,b_n] \\ R_2 &= [a_1 + \frac{(b_1 - a_1)}{m},a_1 + \frac{2(b_1 - a_1)}{m}]\times[a_2,b_2]\times...\times[a_n,b_n]\\ \vdots \\ R_k &= [a_1 + \frac{(k-1)(b_1 - a_1)}{m},a_1 + \frac{k(b_1 - a_1)}{m}]\times[a_2,b_2]\times...\times[a_n,b_n] \\ \vdots \\ R_m &= [a_1 + \frac{(m-1)(b_1 - a_1)}{m},b_1]\times[a_2,b_2]\times...\times[a_n,b_n] \end{align*} Clearly, $F = \displaystyle\bigcup_{k = 1}^{m}R_k$. Consider the points $p,q \in R_k$ \begin{align*} p =& (a_1 + \frac{(k-1)(b_1 - a_1)}{m}, a_2,...,a_n)\\ q =& (a_1 + \frac{k(b_1 - a_1)}{m}, b_2,...,b_n) \end{align*}

Now by Exercise 2 we have that

$\mbox{diam}(R_k) = d(p,q) = \sqrt{\sum_{i = 2}^{n}(b_i - a_i)^2 + \frac{(b_1 - a_1)^2}{m^2}} < \epsilon$.

Now if $x_k \in R_k$, then for any $y_k \in R_k$, $d(x_k,y_k) \leq \mbox{diam}(R_k) < \epsilon$. Hence, $x_k \in B(x_k,\epsilon)$ and $R_k \subseteq B(x_k,\epsilon)$.

Can anyone verify this proof? I've prove everything by myself. My professor wants every detail!


There's a mistake in your proof, you do not have $F=\bigcup_{k=1}^mR_k$. The idea is however correct.

To see where it fails, try drawing it in 2 dimensions. F is then a rectangle, you've sliced each side into $m$ equal portions, in other word you made an $m$ by $m$ grid of smaller rectangles out of F. You then defined your $R_k$ as being the diagonal, smaller rectangles... Meaning you're missing all the other $m(m-1)$ rectangles.

If we go back to $n$ dimensions, you have a $m\times m\times\ldots\times m$ (a total of n times) hypergrid, which contains $m^n$ small hyper-rectangles. In your definition, you only take the $m$ diagonal elements and you're then missing $m(m^{n-1}-1)$ hyper-rectangles.


Because I have no clue what your background in maths (and other related topics) is, I have included a lot of details below. If you still need more on some points feel free to ask though, if you already know part of what's below, my apologies for making it so long.

Defining enough hyper-rectangles

Let $M$ be a positive integer such that

$$\frac{\operatorname{diam}(F)}M =\sqrt{\sum_{i=1}^n\left( \frac{b_i-a_i}M\right)^2} <\epsilon$$

We want to split $F$ into smaller hyper-rectangles so that their diameter is no more than $\frac{\operatorname{diam}(F)}M$, and that they are a partition of $F$. The most natural way to do that is, as you tried previously, to divide $F$ into a hyper-grid of size $M\times M\times\ldots\times M$ ($n$ times).

It is quite annoying to do so formally, and even more so if you limit yourself to only one index. For now let's see what we can do with multiple indices, consider $n$ integers $i_1,i_2,\ldots,i_n\in\left[\!\left[ 0,M-1 \right]\!\right]$ and define

\begin{align*} R({i_1,\ldots,i_n}) &= \left[ a_1+\frac{i_1(b_1-a_1)}M, \ a_1+\frac{(i_1+1)(b_1-a_1)}M \right] \times\ldots\times \left[ a_n+\frac{i_n(b_n-a_n)}M, \ a_n+\frac{(i_n+1)(b_n-a_n)}M \right] \end{align*}

Proof that our hyper-rectangles do not spill outside of $F$ (edit 2)

As requested, here are some details on proving the inclusion $$ \bigcup_{0\le i_1,\ \ldots\ ,i_n\le M-1} R(i_1,\ldots,i_n) \subseteq F $$ Consider one small hyper-rectangle $R(i_1,\ldots,i_n)$ and let $x\in R(i_1,\ldots,i_n)$. For $k$, $1\le k\le n$, we have by definition of the hyper-rectangle $$a_k+\frac{i_k(b_k-a_k)}M \le x_k \le a_k+\frac{(i_k+1)(b_k-a_k)}M$$ Now remember that $0\le i_k\le M-1$, we deduce the following: \begin{align*} 0\le \frac{i_k}M &\implies a_k\le a_k+\frac{i_k(b_k-a_k)}M\\ \frac{i_k+1}M\le 1 &\implies a_k+\frac{(i_k+1)(b_k-a_k)}M \le a_k+ b_k-a_k=b_k \end{align*} It follows that $a_k\le x_k\le b_k$. This is true for all $1\le k\le n$, therefore $x\in F$, thus $R(i_1,\ldots,i_n)\subseteq F$, and finally $$ \bigcup_{0\le i_1,\ \ldots\ ,i_n\le M-1} R(i_1,\ldots,i_n) \subseteq F $$

Proof that we have enough hyper-rectangles (v2)

We now want to prove the reverse inclusion (which was where your previous approach failed).

Let $x=(x_1,x_2,\ldots,x_n)\in F$. Then $\forall k\in\left[\!\left[ 1,n \right]\!\right]$, $a_k\le x_k\le b_k$. In particular, there is some integer $i_k$ such that $$ a_k+\frac{i_k(b_k-a_k)}M\le x_k \le a_k+\frac{(i_k+1)(b_k-a_k)}M $$ Indeed it suffices to take \begin{cases} i_k=M-1 & \text{if $x_k=b_k$} \\ i_k=\left\lfloor\frac{(x_k-a_k)M}{b_k-a_k}\right\rfloor & \text{if $x_k< b_k$} \end{cases} Basically if we exclude the special case "$x_k=b_k$", $i_k$ is just the index of the slice of length $\frac{b_k-a_k}M$ that contains $x_k$. To see why this works, notice that $x_k$ can be written as $x_k=a_k+q\frac{b_k-a_k}M$. Specifically, we can always define the real number $q=M\frac{x_k-a_k}{b_k-a_k}$. Because $a_k\le x_k\le b_k$, we know that $0\le \frac{x_k-a_k}{b_k-a_k}\le 1$, hence $0\le q\le M$. In general $q$ is not an integer and cannot be used "as is" for our indices. We can however use the floor function to get an integer. By definition, we have $\lfloor q\rfloor\le q<\lfloor q\rfloor+1$. If we go back to $x_k$ using these inequalities we obtain $$ a_k+\lfloor q\rfloor\frac{b_k-a_k}M \le a_k+q\frac{b_k-a_k}M=x_k < a_k+(\lfloor q\rfloor+1)\frac{b_k-a_k}M $$ If you compare this to the definition of our hyper-rectangles, it is obvious you can very often use $\lfloor q\rfloor$ as an index. The only exception is when $\lfloor q\rfloor$ is equal to $M$, because our indices must be strictly smaller than $M$. If you backtrack the equations, this can only occur if $q\ge M$, which means $q=M$, which also means $x_k=b_k$. This is however okay, because $b_k$ is covered by our last slice that have index $M-1$. This assymetry occurs because when $x_k$ is right at the boundary between $2$ slices, you need to decide whether you put the point in the left slice or the right slice. In this definition here, we decide to put it in the right slice, and treat the rightmost point (when $x_k=b_k$) as a special case (and put it in the left slice).

With those definitions, we thus have $x\in R(i_1,\ldots, i_n)$. Because this holds for every $x\in F$ we conclude that $$ F\subseteq \bigcup_{0\le i_1,\ \ldots\ ,i_n\le M-1} R(i_1,\ldots,i_n) $$ and we have as desired $$ F = \bigcup_{0\le i_1,\ \ldots\ ,i_n\le M-1} R(i_1,\ldots,i_n) $$

With this, your problem is basically solved since the diameter of each small hyper-rectangle is $\frac{\operatorname{diam}(F)}M <\epsilon$... But if you REALLY want to only use one index, there's a little more work to do.

Reducing to one index (probably too detailed bis)

When you have a finite number of indices that can take a finite number of integer values, there's a well known "trick" to reduce to only one index. For instance in the 2D case, assume you have a grid of height $h$ and width $w$. You can refer to any place in the grid with two integers $x$ and $y$, with $0\le x\le w-1$ and $0\le y \le h-1$.

To reduce to one index $i$, you can split the grid into its lines, and just stack them one after the other. You then get one very long line, of which you just take the index. You have the below correspondance \begin{align} x,y &\quad\rightarrow\quad i= x+y\times w\\ i &\quad\rightarrow\quad y=\left\lfloor\frac i w\right\rfloor, \ x=i-y\times w \end{align} and $i$ can take every value between $0$ and $h\times w-1$ (inclusive) for a total of $h\times w$ distinct values, which is precisely the number of places in our grid.

In the $n$ dimensional case, you want to do the same, except it gets much more annoying. If you have one saving grace here, it's that everything has the same size. Once again consider $n$ integers $i_1,\ldots, i_n$ in between $0$ and $M-1$, we define our unique index as $$I = \sum_{k=1}^n \left( i_k\times M^{k-1} \right)$$ The values of $I$ then range from $0$ to $M^n-1$ (inclusive) for a total of $M^n$ distinct values, and as many hyper-rectangles as we defined above. For $0\le I\le M^n-1$ you can properly retrieve the $n$ indices: $$ i_k =\left\lfloor \frac{I-\sum_{j>k}\left( i_j\times M^{j-1} \right)}{M^{i-1}} \right\rfloor $$ In summation, you can define $R_I = R(i_1,\ldots,i_n)$ and you get one index instead of $n$ indices.

As a conclusion, you may have a little bit more of work if you want the above definitions to perfectly match your problem statement. From my background I'm more used to indexing stuff from $0$, so my definitions use a $0$-initial index, whereas your problem statement uses an index that starts from $1$. Speaking of which, you'd have to define $m=M^n$.

  • $\begingroup$ In other words, I must define each $R_k$ as the union over any row any column in the $m\times m$ grid ? I think that will cover the whole F. But I will have to modify my $N$. $\endgroup$ Apr 7 '17 at 16:28
  • 1
    $\begingroup$ @RichardClare that would be correct, if you define your $R_k$ for every smaller rectangle you get a partition of $F$... This is kind of a pain for sure. $\endgroup$
    – N.Bach
    Apr 7 '17 at 16:31
  • $\begingroup$ I modify the proof to a simpler version, just making a partition in the first interval. I think this modification will work. Can you verify ? $\endgroup$ Apr 7 '17 at 17:19
  • 1
    $\begingroup$ @RichardClare your new definition of $m$ now looks wrong to me... $\sqrt{\sum_{i=2}^n(b_i-a_i)^2}$ has no guarantee of being smaller than $\epsilon$, so no matter how you choose $m$ you won't always get the desired inequality... On a side note, your approach would likely work if the problem used the hyper-volume instead of the diameter. $\endgroup$
    – N.Bach
    Apr 7 '17 at 17:26
  • $\begingroup$ You are right. I will have to find a better way. Did you have other approach ? $\endgroup$ Apr 7 '17 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.