Re: A note on a problem from Rudin's Real and Complex Analysis

This post is a short note regarding problem 14 from Page-59 of Rudin's Real and Complex Analysis.

Problem: Let, $f$ be a real-valued Lebesgue measurable function on $\mathbb{R}^k$, prove that there exists Borel functions $g$ and $h$ such that $\mu_k(\{x \in \mathbb{R}^k: g(x) \neq h(x)\}) = 0$ and $g(x) \le f(x) \le h(x)$ for all $x \in \mathbb{R}^k$.  (where, $\mu_k$ is the Lebesgue measure on $\mathbb{R}^k$)

As stated the proposition is incorrect. Best we can do is find Borel functions $g$ and $h$ such that $g(x) = h(x)$ a.e. $[\mu_k]$ and $g(x) \le f(x) \le h(x)$ a.e. $[\mu_k]$.

To see why it's not always possible to 'approximate' a lebesgue measurable function from both above and/or below by Borel functions, we rely on a cardinality argument. Roughly speaking, there aren't enough Borel functions to account for every modification of a lebesgue measurable function in a measure zero set.

Lemma: The cardinality of real Borel measurable functions on $\mathbb{R}$ is $2^{\aleph_0}$.

Proof: Since, constant functions are Borel measurable there are atleast $2^{\aleph_0}$ Borel functions. Again, to determine a Borel function $g$ it suffices to determine the sequence of sets $g^{-1}(q,\infty)$ for each $q \in \mathbb{Q}$ (ordered by inclusion). Since, there are $2^{\aleph_0}$ (i.e., the cardinality of Borel subsets of $\mathbb{R}$)-choices for each $g^{-1}(q,\infty)$ as $q$ varies over $\mathbb{Q}$, there are atmost $\left(2^{\aleph_0}\right)^{\aleph_0} = 2^{\aleph_0}$ real Borel measurable functions on $\mathbb{R}$. $\boxed{}$

Let us index the Borel functions by $\{g_j: j \in J\}$, where, $J$ is some indexing set with cardinality $2^{\aleph_0}$.

Start with the Cantor set $C \subset \mathbb{R}$ which is a set of lebesgue measure zero. Let $C = C_1 \sqcup C_2$ be a partition into subsets such that $|C_1| = |C_2| = 2^{\aleph_0}$. Let us index the elements of $C_1 = \{x_j : j \in J\}$ and $C_2 = \{x_j' : j \in J\}$. Now, if we consider a functions $f: C \to \mathbb{Z}$ such that $f(x_j) < g_j(x_j)$ and $f(x_j') > g_j(x_j')$ for each $j \in J$ (such a $f$ is possible to construct since $\mathbb{Z}$ is an unbounded discrete subset of $\mathbb{R}$), and extend it to $\mathbb{R}$ by defining $f(x) = 0$ for $x \in \mathbb{R}\setminus C$, we have constructed a lebesgue measurable function $f$ which violates the requirement of the proposition form the book.

N.B.: If we were given the scenario that $f$ is a 'bounded' real-lebesgue measurable function on $\mathbb{R}$ (or if, $f:\mathbb{R} \to [-\infty,\infty]$ is lebesgue measurable on the extended real-line), then it is possible to construct borel functions (respectively, extended Borel functions) with the required property that is $g \le f \le h$ for all $x \in \mathbb{R}$. As long as range of $f$ has unbounded discrete subset we may modify $f$ in the above fashion inside an uncountable subset of measure zero such that it is no longer possible to be bounded by Borel functions at all points.

Gaining further insight into AMM 11832

This post is aimed as a second solution (v2.0) to AMM problem 11832 proposed by Donald Kunth, U.S.A.

My first proof in a previous blog entry: AMM problem 11832 by D. Knuth

(I believe this new line of computation gains more insight into the cog and wheels (working principles) behind the creation of the identity, rather than my initial approach, which was designed for dealing with a specific case).

We begin with the a theorem with generating functions:

The following is an excerpt from K. N. Boyadzheiv's paper:

Theorem: Given a pair of sequence $\displaystyle (a_n)_{n \ge 0}$ and $\displaystyle (b_n)_{n\ge 0}$ that are Binomial Inverses of each other, that is they satisfy the relation:

$\displaystyle a_n = \sum\limits_{k=0}^{n} (-1)^{n-k}\binom{n}{k} b_k$ and $\displaystyle b_n = \sum\limits_{k=0}^{n} \binom{n}{k} a_k$

for each $n \ge 0$, then the corresponding generating functions with central binomial coefficient weight are related as follows:

If $\displaystyle f_{b}(z) = \sum\limits_{n=0}^{\infty} \binom{2n}{n}b_nz^n$ then, $\displaystyle f_a(z) = \sum\limits_{n=0}^{\infty} \binom{2n}{n}a_nz^n = \frac{f_b\left(\frac{z}{1+4z}\right)}{\sqrt{1+4z}}$

Proof:

Lemma: For complex number $\alpha$ and $|z|$ in suitable region of convergence, we have:

$$\displaystyle \sum\limits_{n=0}^{\infty} (-1)^n\binom{\alpha}{n}a_nz^n = (1+z)^{\alpha}\sum\limits_{n=0}^{\infty}(-1)^n\binom{\alpha}{n}\left(\frac{z}{1+z}\right)^n\left(\sum\limits_{k=0}^{n}\binom{n}{k}a_k\right)$$

which is a consequence of Euler's series transformation formula.

The special case $\displaystyle \alpha = -\frac{1}{2}$ is what we are after, $\displaystyle \binom{-1/2}{n} = \frac{1}{4^n}\binom{2n}{n}$ and making the substitution $z \mapsto 4z$ we get the desired result. [Q.E.D.]

For further details please refer to the original paper itself.

Back to the problem at hand:

We have the Binomial transformation formula: $\displaystyle \sum\limits_{k=1}^{n}(-1)^{n-k}\binom{n}{k}(H_{2k} - H_k) = (-1)^{n-1}\left(\frac{4^n}{2n\binom{2n}{n}} - \frac{1}{2n}\right)$ which can be easily established. Hence, putting it into the machinery provided by the theorem, we get:

$$g(z) := \sum\limits_{n=1}^{\infty} \binom{2n}{n}\left(\frac{4^n}{2n\binom{2n}{n}} - \frac{1}{2n}\right)z^n = \frac{1}{2}\sum\limits_{n=1}^{\infty} \frac{4^nz^n}{n} - \frac{1}{2} \sum\limits_{n=1}^{\infty} \binom{2n}{n}\frac{z^n}{n}= -\frac{1}{2}\log (1-4z) + \log \left(\frac{1+\sqrt{1-4z}}{2}\right)$$

and as a consequence:

$$f(z) := \sum\limits_{n=1}^{\infty} (-1)^{n-1}\binom{2n}{n} (H_{2n} - H_n)z^n = \frac{g\left(\frac{z}{1+4z}\right)}{\sqrt{1+4z}} = \frac{1}{\sqrt{1+4z}}\log \left(\frac{1+\sqrt{1+4z}}{2}\right)$$

Making the change $z \mapsto -z$ in the above identity we get:

$\displaystyle \sum\limits_{n=1}^{\infty} \binom{2n}{n} (H_{2n} - H_n)z^n = \frac{-1}{\sqrt{1-4z}}\log \left(\frac{1+\sqrt{1-4z}}{2}\right)$

Dividing both sides with $z$ and integration leads to D. Knuth's identity, as we saw in my previous proof:

$$\boxed{\sum\limits_{n=1}^{\infty} \binom{2n}{n} (H_{2n-1}- H_n)\frac{z^n}{n} = \log^2 \left(\frac{1+\sqrt{1-4z}}{2}\right) = \log^2 (C(z))}$$