analysis--berkeley-202a-hw10.tex

\section{Math 202A - HW10 - Dan Davison - \texttt{ddavison@berkeley.edu}}

\begin{verbatim}
12.3. You have all the tools you need to prove the converse; try using g. (-4)
Aidan Backus, Nov 18 at 6:18pm

Review 1: You need to prove that your formula for \limsup_{n \to \infty} A_n is valid. (-1) It is not true
that a summable sequence x_i has compact support; x_i = i^{-2} is a counterexample. This invalidates your
bound on \mu(E) and hence your proof of the Borel-Cantelli lemma. (-3) Aidan Backus, Nov 21 at 1:24pm

12.3) 6 12.4) 0
Ian Francis, Nov 24 at 5:07am

Review 2: You are correct to guess that f bar, a continuous function with compact support, is not necessarily
lipschitz. Try \sqrt{x} on [0,1]. It's continuous with compact support, but not Lipschitz. However, you don't
need Lipschitz. Simply note that the result holds for f bar (using uniform convergence or DCT or whatever),
and then use the triangle inequality and translation invariance of Lebesgue measure to get the result for f.
(-6) Ian Francis, Dec 2 at 8:02pm
\end{verbatim}

\begin{mdframed}
  \includegraphics[width=400pt]{img/analysis--berkeley-202a-hw10-7127.png}
\end{mdframed}

\begin{verbatim}
Review 1: You need to prove that your formula for \limsup_{n \to \infty} A_n is valid. (-1) It is not true
that a summable sequence x_i has compact support; x_i = i^{-2} is a counterexample. This invalidates your
bound on \mu(E) and hence your proof of the Borel-Cantelli lemma. (-3)
\end{verbatim}

\begin{enumerate}[label=(\alph*)]
\item ~\\

The set $E$ whose elements belong to infinitely many of the sets $A_i$ is
\begin{align*}
  E = \bigcap_{i=1}^\infty \bigcup_{j=i}^\infty A_j =: \limsup_{i \to \infty} A_i.
\end{align*}
\begin{claim*}
  If $\sum_i \mu(A_i) < \infty$ then $\mu\(E\) = 0$.
\end{claim*}

\begin{proof}
  Since $\sum_{i=1}^\infty \mu(A_i) < \infty$ we see that only finitely many of the $A_i$ have $\mu(A_i) > 0$.

  Let $N$ be such that $\mu(A_i) = 0$ for all $i \geq N$.

  Note that
  \begin{align*}
    E = \bigcap_{i=1}^\infty \bigcup_{j=i}^\infty A_j \subseteq \bigcup_{j=N}^\infty A_j,
  \end{align*}
  therefore by monotonicity of measure
  \begin{align*}
    \mu(E) \leq \mu\(\bigcup_{j=N}^\infty A_j\) \leq \sum_{j=N}^\infty \mu(A_j) = 0.
  \end{align*}
\end{proof}

\item ~\\

We define a sequence of sets $A_1, A_2, \ldots \subseteq [0, 1)$ as follows: $x \in [0, 1)$ is an element
of $A_n$ if each of the $10$ digits occurs exactly $n$ times in the first $10n$ digits of the decimal expansion
of $x$.

$A$ is defined to be the set whose elements are in infinitely many of the $A_n$. Therefore
\begin{align*}
  A = \bigcap_{i=1}^\infty \bigcup_{j=i}^\infty A_j.
\end{align*}

\begin{claim*}
  The set $A$ is Lebesgue measurable.
\end{claim*}

\begin{proof}
  We define the $i$-th decadic interval for digit $k$ at rank $m$ to be the following interval containing
  numbers whose decimal expansion has a $k$ in the $m$-th position, where we choose the representation ending
  in $0$s where there is a choice:
  \begin{align*}
    I_{m, k, i} := \Bigg[\frac{10i + k}{10^m}, \frac{10i + k + 1}{10^m}\Bigg).
  \end{align*}
  % Let $B_{m, k}$ be the set of all numbers in $[0, 1)$ whose base-$K$ expansion has a $k$ in the $m$-th
  % position. At rank $m$ there are $K^m$ $K$-adic intervals each of length $K^{-m}$ and we have
  % \begin{align*}
  %   B_{m, k} = \bigcup_{i=0}^{K^{m-1} - 1} I_{m, k, i}.
  % \end{align*}
  % Thus, for example, in base 10, the numbers with a $7$ in the 2nd digit of their expansion are
  % \begin{align*}
  %   B_{2, 7}
  %   &= \bigcup_{i=0}^{9} \Bigg[\frac{10i + 7}{100}, \frac{10i + 7 + 1}{100}\Bigg) \\
  %   &= \Bigg[\frac{7}{100}, \frac{8}{100}\Bigg) \cup \Bigg[\frac{17}{100}, \frac{18}{100}\Bigg) \cup \cdots \Bigg[\frac{97}{100}, \frac{98}{100}\Bigg).
  % \end{align*}

  Recall our definition of $A_n$ as the set whose elements $x \in [0, 1)$ have the property that each of the
  digits $0, 1, \ldots, 9$ occur exactly $n$ times in the first $10n$ digits of the decimal expansion.

  Let $\mc I = \{I_{m, k, i} ~:~ m \geq 1, 0 \leq k < 10, i \in \N\}$ be the set of all decadic intervals at any
  rank. Let $g:\mc I \to \N$ be defined by
  \begin{align*}
    g(I_{m, k, i}) = \text{~the number of occurrences of $k$ in positions $1, \ldots, m$ for $x \in I_{m, k, i}$}.
  \end{align*}
  Note that each decadic interval at rank $m$ is a subset of some decadic interval at rank $m-1$. I.e. for
  all $m, k, i$ we have $I_{m+1, k, i} \subset I_{m, k', i'}$ for some $k', i'$. Therefore, when considering a
  single interval $I_{m, k, i}$ at rank $m$, the sequence of digits at positions $1, \dots, m-1$ is the same
  for all $x \in I_{m, k, i}$, and we see that $g$ is well-defined.

  Thus we have
  \begin{align*}
    A_n = \bigcap_{k=0}^{9} ~~ \bigcup_{\substack{i\in \{0, \ldots, 10^{10n} - 1\}\\g(I_{10n, k, i}) = n}} I_{10n, k, i}.
  \end{align*}
  $A_n$ is therefore in the Borel $\sigma$-algebra, since it can be written using countable (in fact finite)
  intersections and unions of intervals. Therefore $A_n$ is Lebesgue measurable.

  Therefore
  \begin{align*}
    A = \bigcap_{i=1}^\infty \bigcup_{j=i}^\infty A_j
  \end{align*}
  is also in the Borel $\sigma$-algebra, since it can be written using countable intersections and unions of
  intervals, and therefore also Lebesgue measurable.
\end{proof}

~\\
\item ~\\
\begin{claim*}
  The Lebesgue measure of $A$ is zero.
\end{claim*}

\begin{proof}
  Let $\mu$ be Lebesgue measure. We will show that $\sum_{n=1}^\infty \mu(A_n) < \infty$. The result then
  follows from part (a) above.

  We may view $\mu$ as a uniform probability measure, since $\mu([0, 1)) = 1$. The set $A_n$ then corresponds
  to the event that a sample of size $10n$ drawn uniformly with replacement from the set $\{0, 1, \ldots, 9\}$
  contains $n$ copies of each digit. A combinatorial argument shows that the probability of this event is equal
  to
  \begin{align*}
    \mu(A_n) = P(A_n)
    &= \frac{\prod_{i=1}^{10} {in \choose n}}{10^{10n}}.
  \end{align*}
  (The denominator corresponds to the fact that there are $10^{10n}$ ways of drawing a sample of size $10n$
  uniformly with replacement from the set $\{0, 1, \ldots, 9\}$; the numerator corresponds to the fact that
  there are ${10n \choose n}$ ways to choose the $n$ slots in which the $n$ copies of the digit $0$ go, then
  there are ${9n \choose n}$ ways to choose the $n$ slots in which the $n$ copies of the digit $1$ go, and so
  on.)

  Simplifying this expression, we obtain
  \begin{align*}
  \mu(A_n)
    &= \frac{1}{10^{10n}}\prod_{i=1}^{10}\frac{{(in)!}}{n!(in - n)!} \\
%    &= \frac{1}{10^{10n}n!}\prod_{i=1}^{10}\frac{{(in)!}}{((i - 1)n)!} \\
    &= \frac{1}{10^{10n}n!}\prod_{i=1}^{10} (in)(in -1)(in - 2)\cdots(in - n + 1) \\
    &= \frac{n^{10}}{10^{10n}n!}\prod_{i=1}^{10} (i)(i -1/n)(i - 2/n)\cdots(i - 1 + 1/n).
%    &< \frac{1}{10^{10n}n!}\prod_{i=1}^{10} (in)^n \\
%    &= \frac{n^n}{10^{10n}n!}\prod_{i=1}^{10} i^n \\
%    &= \frac{n^n}{n!} \frac{3628800^n}{10^{10n}} \\
%    &< \frac{n^n}{1} \frac{3628800^n}{10^{10n}} \\
  \end{align*}

  The ratio test confirms that the series $\sum_{n=1}^\infty \mu(A_n)$ converges:
  \begin{align*}
    &\lim_{n\to\infty} \Bigg|\frac{(n+1)^{10}\prod_{i=1}^{10} (i)(i -\frac{1}{(n+1)} )\cdots(i - 1 +\frac{1}{(n+1)} )}{10^{10(n+1)}(n+1)!}     \frac{10^{10n}n!}{n^{10}\prod_{i=1}^{10} (i)(i -\frac{1}{n} )\cdots(i - 1 +\frac{1}{n} )}\Bigg| \\
    = &10^{-10}\lim_{n\to\infty} \frac{\prod_{i=1}^{10} (i)(i -\frac{1}{(n+1)} )\cdots(i - 1 +\frac{1}{(n+1)} )}{\prod_{i=1}^{10} (i)(i -\frac{1}{n} )\cdots(i - 1 +\frac{1}{n} )}     \frac{(n+1)^{9}}{n^{10}} \\
    = &10^{-10}\frac{\prod_{i=1}^{10} (i)(i )\cdots(i - 1  )}{\prod_{i=1}^{10} (i)(i )\cdots(i - 1 )}   \cdot  0 \\
    = &0.
  \end{align*}

  Thus $\sum_{n=1}^\infty \mu(A_n) < \infty$ and from part (a) it follows that $\mu(A) = 0$.
\end{proof}
\end{enumerate}

\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/analysis--berkeley-202a-hw10-5e9e.png}
\end{mdframed}

\begin{verbatim}
Review 2: You are correct to guess that f bar, a continuous function with compact support, is not necessarily
lipschitz. Try \sqrt{x} on [0,1]. It's continuous with compact support, but not Lipschitz. However, you don't need
Lipschitz. Simply note that the result holds for f bar (using uniform convergence or DCT or whatever), and then
use the triangle inequality and translation invariance of Lebesgue measure to get the result for f. (-6)
\end{verbatim}

\begin{proof}

  [incomplete]

  Let $h_1, h_2, ...$ be a sequence converging to $0$ from above, and define
  \begin{align*}
    g_n(x) := f(x + h_n) - f(x).
  \end{align*}
  Note that $g_n \to 0$ pointwise as $h \to 0$ and that $g_n$ is the difference of two integrable functions and
  therefore integrable. We must show that
  \begin{align*}
    \limninf \int |g_n| = 0.
  \end{align*}
  Suppose $f$ is Lipschitz continuous with compact support, such that for all $x, x' \in \R$ we
  have $|f(x') - f(x)| \leq M|x' - x|$. Let $A = \{x \in \R ~:~ |f(x)| > 0 \}$. Then the result follows from
  the dominated convergence theorem: $|g_n|$ is bounded above by $Mh_n\ind_A$ and therefore
  \begin{align*}
    \limninf \int |g_n| = \int \limninf |g_n| = \int 0 = 0.
  \end{align*}
  Let $\eps > 0$. We know (hint from @kshitij in Slack) from the approximation theorem Bass 8.4 that there
  exists a continuous function $\bar f$ with compact support such that
  \begin{align*}
    \int |f - \bar f| < \eps.
  \end{align*}
  I think that to complete this proof I need to do something similar to the following:
  \begin{enumerate}
  \item Show that $\bar f$ is Lipschitz
  \item Show that, because $f$ and $\bar f$ are close in the sense that $\int |f - \bar f| < \eps$, the result
    holds for $f$ as well as $\bar f$.
  \end{enumerate}
  Since $\bar f$ is continuous with compact support there exists $B > 0$ such that $|\bar f| \leq B$.

  However I don't think it's true that $\bar f$ is Lipschitz continuous and I'm not sure how to proceed.
\end{proof}




\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/analysis--berkeley-202a-hw10-551e.png}
\end{mdframed}

\begin{verbatim}
12.3. You have all the tools you need to prove the converse; try using g.
\end{verbatim}

\begin{proof}
  Let $X = P \cup N$ be a Hahn decomposition of $X$, such that $P$ is a $\mu$-positive set and $N$ is
  a $\mu$-negative set. Then
  \begin{align*}
    |\mu|(A) =\int_{A\cap P} 1 \dmu + \int_{A \cap N} -1 \dmu.
  \end{align*}
  Let $\ms F = \big\{f: X \to [-1, 1] ~: ~ f \text{~measurable} \big\}$ and define $g \in \ms F$ by
  \begin{align*}
    g(x) =
    \begin{cases}
      1  & x \in P \\
      -1 & x \in N.
    \end{cases}
  \end{align*}
  Then
  \begin{align*}
    |\mu|(A) = \int_A g \dmu = \Bigg|\int_A g \dmu\Bigg|.
  \end{align*}
  Let $f \in \ms F$ where $f \neq g$ and note that

  \begin{align*}
    -\int_{A \cap N} g \dmu \leq \int_{A \cap N} f \dmu \leq \int_{A \cap N} g \dmu,
  \end{align*}
  and
  \begin{align*}
    -\int_{A \cap P} g \dmu \leq \int_{A \cap P} f \dmu \leq \int_{A \cap P} g \dmu.
  \end{align*}

  Therefore
  \begin{align*}
    \Big|\int_A f \dmu\Big|
    &= \Big|\int_{A \cap P} f \dmu + \int_{A \cap N} f \dmu\Big| \\
    &\leq \Big|\int_{A \cap P} f \dmu\Big| + \Big|\int_{A \cap N} f \dmu\Big| \\
    &\leq \Big|\int_{A \cap P} g \dmu\Big| + \Big|\int_{A \cap N} g \dmu\Big| \\
    &= \Big|\int_{A} g \dmu\Big| \\
    &= |\mu|(A).
  \end{align*}
  Therefore $|\mu|(A)$is an upper bound for $\Big\{ \big|\int_A f \dmu\big| : |f| \leq 1 \Big\}$.
  \red{TODO} we must also show that $|\mu|(A)$ is the least upper bound.

  Therefore
  \begin{align*}
    \Big|\int_{A} g \dmu\Big| = \sup\Bigg\{ \Big|\int_A f \dmu\Big| : |f| \leq 1 \Bigg\}.
  \end{align*}
\end{proof}


\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/analysis--berkeley-202a-hw10-8336.png}
\end{mdframed}

\begin{proof}

  [incomplete]

  % Recall that
  % \begin{align*}
  %   \lambda^+(A) &= \lambda(A \cap P) \\
  %   \lambda^-(A) &= -\lambda(A \cap N),
  % \end{align*}
  % where $X = P \cup N$ is a Hahn decomposition of $X$.
\end{proof}


\newpage
\begin{mdframed}
\includegraphics[width=400pt]{img/analysis--berkeley-202a-hw10-0220.png}
\end{mdframed}

Recall that
\begin{align*}
  \mu^+(A) &= \mu(A \cap P) \\
  \mu^-(A) &= -\mu(A \cap P),
\end{align*}
where $X = P \cup N$ is a Hahn decomposition of $X$.

Let $L = \{\mu(B) ~:~ B \in \mc A, B \subset A\}$.

Let $B \in \mc A$ and $B \subset A$. Then
\begin{align*}
  B = \((A \cap P) \cap B\) \cup \((A \cap N) \cap B\),
\end{align*}
and this is a union of disjoint sets.

\begin{claim*}
  $\mu^+(A) = \sup \{\mu(B) ~:~ B \in \mc A, B \subset A\}$
\end{claim*}

\begin{proof}

  [incomplete]

  Using the disjoint union from above we have
  \begin{align*}
    \mu(B)
    &= \mu\((A \cap P) \cap B\) + \mu\((A \cap N) \cap B\) \\
    &\leq \mu\((A \cap P) \cap B\) \\
    &\leq \mu(A \cap P) \\
    &= \mu^+(A).
  \end{align*}
  Therefore $\mu^+(A)$ is an upper bound for $L$.

  Now suppose $l$ is another upper bound for $L$.

  ... \red{TODO}
\end{proof}

\begin{claim*}
  $\mu^-(A) = -\inf \{\mu(B) ~:~ B \in \mc A, B \subset A\}$
\end{claim*}

\begin{proof}

  [incomplete]

  Using the disjoint union from above we have
  \begin{align*}
    \mu(B)
    &= \mu\((A \cap P) \cap B\) + \mu\((A \cap N) \cap B\) \\
    &\geq \mu\((A \cap N) \cap B\) \\
  \end{align*}

\end{proof}