# Covering of Intervals

For a real interval $$I=[x-r,x+r]$$ and a number $$\alpha>0$$ we write $$\alpha I:=[x-\alpha r,x+\alpha r]$$, i.e. $$\alpha I$$ is the interval $$I$$ blown up by a factor $$\alpha$$ around its center.

For example, the Vitali Covering Lemma says that for any finite collection of intervals $$([a_j,b_j])_{1\leq j\leq n}$$ there is an index set $$J\subseteq\{1,\ldots,n\}$$ such that $$([a_j,b_j])_{j\in J}$$ is a subcollection of pairwise disjoint intervals with $$\bigcup_{1\leq j\leq n}[a_j,b_j]\subseteq\bigcup_{j\in J}3[a_j,b_j]$$

Setting: I have two finite collections of intervals $$([a_j,b_j])_{1\leq j\leq n}$$ and $$([c_j,d_j])_{1\leq j\leq n}$$ with the following three properties.

1. $$|a_j-c_j|\leq\delta$$ and $$|b_j-d_j|\leq \delta$$ for $$1\leq j\leq n$$,
2. $$\sum_{j=1}^n|(a_j-c_j)-(b_j-d_j)|\leq\delta$$,
3. $$\left|\bigcup_{j=1}^n[a_j,b_j]\right|\leq\varepsilon$$, where $$|A|$$ means the Lebesgue measure of a set $$A$$.

Here, $$\delta$$ and $$\varepsilon$$ are two positive "small" numbers.

Problem: I would like to show (or disprove) that the Lebesgue measure of $$\bigcup_{j=1}^n[c_j,d_j]$$ is, up to a constant that does not depend on the intervals or $$n$$, like that of $$\bigcup_{j=1}^n[a_j,b_j]$$ also small.

My attempt: I could prove that this is true if the $$[a_j,b_j]$$ are mutually disjoint: Indeed, by Vitali's Covering Lemma there is an index set $$J\subseteq\{1,\ldots,n\}$$ such that $$([c_j,d_j])_{j\in J}$$ is a subcollection of pairwise disjoint intervals with $$\bigcup_{1\leq j\leq n}[c_j,d_j]\subseteq\bigcup_{j\in J}3[c_j,d_j].$$ This implies with the help of 2. and 3. that \begin{align*} \left|\bigcup_{j=1}^n[c_j,d_j]\right| &\leq\left|\bigcup_{j\in J}3[c_j,d_j]\right| \leq\sum_{j\in J}\Big|3[c_j,d_j]\Big| =3\sum_{j\in J}|c_j-d_j| \\ &\leq 3\sum_{j\in J}|(a_j-b_j)-(c_j-d_j)|+3\sum_{j\in J}|a_j-b_j| \\ &\leq 3\delta+3\left|\bigcup_{j=1}^n[a_j,b_j]\right| \\ &\leq 3(\delta+\varepsilon). \end{align*}

However, I have not used 1. In case that the intervals $$[a_j,b_j]$$ are not pairwise disjoint, I don't know how to proceed. Any ideas are highly appreciated. Thanks in advance!

EDIT: (Thanks to mathworker21): Vitali's Covering Lemma is not necessary here, we can use the estimate \begin{align*} \left|\bigcup_{j=1}^n[c_j,d_j]\right| &\leq\sum_{j=1}^n|c_j-d_j| \end{align*} instead.

• Have you run into any problem with constructing a counterexample? – Dap Jan 6 '19 at 15:44
• Yes, I clearly tried to find counterexamples. Condition 2 implies (triangle inequality) that the sum of the lengths of the intervals differ only by $\delta$. Without condition 1 my claim is false: If all $[a_j,b_j]=[0,\varepsilon]$, say, then 3 is met ($\delta=\varepsilon$). Now, take $[c_j,d_j]=[(j-1)\varepsilon,j\varepsilon]$ for $j=1,\ldots,n$. Then 2 is also met, but $\left|\bigcup_{j=1}^n[c_j,d_j]\right|=|[0,n\varepsilon]|=n\varepsilon$. My overall problem is that I have not a clear idea on how geometrically combine 1 and 2. Therefore, I'm not entirely sure that my claim is true, though. – sranthrop Jan 6 '19 at 16:11
• @sranthrop I'm confused why you used Vitali covering lemma in your proof for when the $[a_j,b_j]$'s are mutually disjoint. Can't you just use $|\cup_j [c_j,d_j]| \le \sum_j d_j-c_j$ and run through the argument? – mathworker21 Jan 7 '19 at 19:31
• Thanks for asking and pointing this out. I think you are right. I'm working on this problem for weeks now and I'm so focused on some things. Thank you! – sranthrop Jan 7 '19 at 21:02
• how do you go from line 2 to 3 without disjoint intervals $[a_j,b_j]$? – Dunham Jan 7 '19 at 21:11

Here is a disproof. Take any $$\epsilon,\delta > 0$$. We construct $$([a_j,b_j])_{1 \le j \le n}, ([c_j,d_j])_{1 \le j \le n}$$ such that:

(1) $$|a_j-c_j| \le \delta$$ and $$|b_j-d_j| \le \delta$$ for each $$j$$.

(2) $$\sum_{j=1}^n |(a_j-c_j)-(b_j-d_j)| = 0$$.

(3) $$|\cup_{j=1}^n [a_j,b_j]| = \epsilon$$.

(4) $$|\cup_{j=1}^n [c_j,d_j]| = \sqrt{\epsilon \delta n}$$.

Take any $$L \in \mathbb{N}$$, and let $$R = \frac{L\delta}{\epsilon}$$ and $$n = RL$$. (It's not a big deal to assume $$R \in \mathbb{N}$$). For $$0 \le l \le L-1$$ and $$1 \le r \le R$$, let $$[a_{lR+r},b_{lR+r}] = [l,l+\frac{\epsilon}{L}]$$ and $$[c_{lR+r},d_{lR+r}] = [l-\delta+(r-1)\frac{\epsilon}{L},l-\delta+r\frac{\epsilon}{L}]$$.

• +1 - although I did find it a "big deal" to see exactly how $\epsilon$ and $\delta$ are related (both in this answer, and in the question itself). – Calum Gilhooley Jan 9 '19 at 2:49
• @CalumGilhooley I'm a bit confused. In my answer, $\epsilon$ and $\delta$ were arbitrary. If you are objecting because $\frac{L\delta}{\epsilon}$ might not be an integer, then we can just define $R = \lceil \frac{L\delta}{\epsilon} \rceil$ instead. If I'm missing something, let me know. – mathworker21 Jan 9 '19 at 7:56
• Thank you, that helps. I think you mean $R=\lfloor\frac{L\delta}{\epsilon}\rfloor$, which ensures that $[c_{lR},d_{lR}]$ and $[c_{lR+1},d_{lR+1}]$ don't overlap, for $1=1,2,\ldots,L-1$. More simply, we can choose $R$ arbitrarily - as "large" as we like - and define $L=\lceil\frac{R\epsilon}{\delta}\rceil$. Then $\left\lvert\bigcup_{j=1}^n[c_j,d_j]\right\rvert = R\epsilon$, which is unbounded by any function of $(\epsilon,\delta)$. – Calum Gilhooley Jan 9 '19 at 15:41
• @CalumGilhooley ah yes, that's simpler. thanks! – mathworker21 Jan 9 '19 at 16:04
• Thank you, guys, very much for all your effort and this nice solution, although my claim which I hoped was true unfortunately turned out to be false. – sranthrop Jan 9 '19 at 20:44

(Disclaimer: this is more of a pedantic comment than an answer!)

Does it change the meaning of the question essentially if one drops the stipulation that $$\delta$$ and $$\epsilon$$ are "small" - I confess to being unable to understand what that statement means in the present context - and asks instead:

Do there exist a number $$h > 0$$, and functions $$f, g$$ (of one and two range-limited real variables, respectively), such that if $$0 < \epsilon < h$$, and condition 3 holds, then for all $$\delta$$ such that $$0 < \delta < f(\epsilon)$$, and all $$n$$ and $$a_j, b_j, c_j, d_j$$ ($$1 \leqslant j \leqslant n$$) such that conditions 1 and 2 hold, we have $$\left\lvert\bigcup_{j=1}^n[c_j,d_j]\right\rvert \leqslant g(\epsilon, \delta)$$?

A more demanding (but I think less plausible) reformulation of the question is as follows:

Do there exist numbers $$h, h' > 0$$, and a function $$g$$ (of two range-limited real variables), such that if $$0 < \epsilon < h$$ and $$0 < \delta < h'$$, then for all $$n$$ and $$a_j, b_j, c_j, d_j$$ ($$1 \leqslant j \leqslant n$$) such that conditions 1 to 3 hold, we have $$\left|\bigcup_{j=1}^n[c_j,d_j]\right| \leqslant g(\epsilon, \delta)$$?

If the second reformulation accurately represents the meaning of the question, then a special case of mathworker21's argument still gives the answer "no". On the other hand, if the first reformulation is satisfactory, then mathworker21's construction cannot be applied, and the question remains open.

[Not so! See the addendum below.]

Disposing of the second reformulation first:

Given $$h, h' > 0$$, take any $$\epsilon$$ such that $$0 < \epsilon < \min\{h, h', 1\}$$. Let $$\delta = \epsilon$$, let $$k$$ be a positive integer, and, in mathworker21's construction, let $$L = R = k$$, $$n = k^2$$. Then $$\left\lvert\bigcup_{j=1}^n[c_j,d_j]\right\rvert = k\epsilon$$. Because this measure is not bounded above by any function of $$\epsilon$$ and $$\delta$$, the required function $$g$$ cannot exist. $$\square$$

On the first reformulation (which I think is a more reasonable interpretation of the question), we may still choose any value of $$\epsilon$$ that is "small enough", i.e. $$\epsilon < h$$, and try to derive a contradiction; but now we must allow $$\delta$$ to take on any "sufficiently small" value, i.e. any value less than some unspecified $$f(\epsilon)$$. In these circumstances, I don't see how mathworker21's construction can be carried out.

(I don't know what the answer is in this case, but it seems best to check my understanding of the question before possibly barking up the wrong tree!)

Even if the first reformulation is valid, the same general construction does still apply. This "answer" is therefore probably best viewed as a long-winded comment in confirmation of mathworker21's answer.

Given $$h > 0$$, and a function $$f$$, take any $$\epsilon$$ such that $$0 < \epsilon < \min\{h, 1\}$$, and any positive integer $$k$$ such that $$\frac{\epsilon}{k} < f(\epsilon)$$. Define $$\delta = \frac{\epsilon}{k}$$, In mathworker21's construction, let $$R = k$$, $$L = k^2$$, $$n = k^3$$. Then $$\left\lvert\bigcup_{j=1}^n[c_j,d_j]\right\rvert = k\epsilon$$, much as before. Again, the required function $$g$$ cannot exist. $$\square$$

• Thanks a lot for this very detailed discussion and answer to my question! – sranthrop Jan 9 '19 at 20:45
• I've done something useful? ... Excuse me, I think I'm going to have to lie down for a minute! :) – Calum Gilhooley Jan 9 '19 at 20:51