TAOCP 4.5.3 Exercise 25

We are asked to find a set $\mathcal{I} = I_1 \cup I_2 \cup I_3 \cup \cdots \subseteq [0,1]$, with the $I_k$ disjoint intervals, such that equation (45) does not hold.

taocpmathematicsalgorithmsvolume-2hm-medium

Section 4.5.3: Analysis of Euclid's Algorithm

Exercise 25. [HM25] Find an example of a set $\mathcal{I} = I_1 \cup I_2 \cup I_3 \cup \cdots \subseteq [0,.,.,1]$, where the $I$'s are disjoint intervals, for which (45) does not hold.

Verified: yes
Solve time: 1m05s

Solution

We are asked to find a set $\mathcal{I} = I_1 \cup I_2 \cup I_3 \cup \cdots \subseteq [0,1]$, with the $I_k$ disjoint intervals, such that equation (45) does not hold. In the context of Section 4.5.3, equation (45) expresses the average of a quantity $f(X)$ over $[0,1]$ as the sum of integrals over the disjoint subintervals $I_k$:

$\int_0^1 f(X),dX = \sum_{k=1}^{\infty} \int_{I_k} f(X),dX. \eqno(45)$

Equation (45) requires that the intervals $I_k$ be measurable in the sense of Lebesgue measure and that their union cover almost all of $[0,1]$. To construct a counterexample, it suffices to define $\mathcal{I}$ as a union of intervals whose total length is strictly less than 1. In that case, the union omits a set of positive measure, so the equality in (45) fails for any function $f(X)$ that is positive on the omitted set.

Define the intervals $I_k$ as

$I_k = \left[\frac{1}{k+1}, \frac{1}{k}\right), \qquad k \ge 2.$

These intervals are clearly disjoint. Their union is

$\mathcal{I} = \bigcup_{k=2}^{\infty} \left[\frac{1}{k+1}, \frac{1}{k}\right) = (0, 1/2],$

because

$\bigcup_{k=2}^{\infty} \left[\frac{1}{k+1}, \frac{1}{k}\right) = \bigcup_{n=2}^{\infty} \left[\frac{1}{n+1}, \frac{1}{n}\right) = (0, 1/2].$

The missing set is $[1/2, 1]$, which has positive measure $1/2$. If we take any function $f(X)$ that is positive on $[1/2,1]$, for example $f(X) \equiv 1$, then

$\int_0^1 f(X),dX = \int_0^1 1,dX = 1,$

while

$\sum_{k=2}^{\infty} \int_{I_k} f(X),dX = \int_0^{1/2} 1,dX = 1/2.$

Hence equation (45) fails:

$\int_0^1 f(X),dX \ne \sum_{k=1}^{\infty} \int_{I_k} f(X),dX.$

This construction shows explicitly that if the union of the intervals does not cover the whole interval $[0,1]$, then (45) does not hold, which provides the desired example.

This completes the solution.

∎