Math 104 Assignment 12

1. Another integral problem

   Suppose that $f : [a, b] \to \R$ is integrable. Prove that $t \mapsto \max(f(t), 0)$ is integrable. Use this to show that the absolute value of an integrable function is integrable.

   (This was the one step we were missing in our proof that \[\abs{\int_a^b f(t)\,dt} \leq \int_a^b \abs{f(t)}\,dt.\] Note as well that since $\max(f(t), g(t)) = \max(f(t)-g(t), 0) + g(t)$ this shows that the maximum of two integrable functions is integrable.)

2. Uniform convergence and sums

   In this problem, we will make the assumption that sequences are indexed beginning at $0$ rather than at $1$.

   Suppose $(h_n)_n$ is a sequence of functions from a set $S$ to a metric space $X$. The sequence is said to be uniformly Cauchy if for every $\epsilon \gt 0$ there is some $N$ so that for any $n, m \gt N$ and any $s \in S$, $\abs{f_n(s)-f_m(s)} \lt \epsilon$. Next week we will see that uniformly convergent sequences of functions are uniformly Cauchy, and that if $X$ is complete, all uniformly Cauchy sequences of functions from $S$ to $X$ converge uniformly.

   1. Suppose that $(a_k)_k$ is a sequence in $\R$. For each $n \in \N_0$, set \[s_n = \sum_{k=0}^n a_k.\] If $(s_n)_n$ converges, we write $\sum_{k=0}^\infty a_k = \lim_{n\to\infty}s_n.$ Show that the sequence $(s_n)_n$ converges if and only if for every $\epsilon \gt 0$ there is some $N \in \N$ so that for any $n, m \in \N$ with $N \lt n \lt m$, \[\abs{\sum_{k=n}^{m-1} a_k} \lt \epsilon.\]
   2. Suppose now that $X$ is a set, and $(f_k)_k$ is a sequence of function $X \to \R$. For each $n \in \N_0$, set \[g_n = \sum_{k=0}^n f_k.\] Show that the sequence $(g_n)_n$ converges uniformly if and only if for every $\epsilon \gt 0$ there is some $N \in \N$ so that for any $n, m \in \N$ with $N \lt n \lt m$, \[\sup_{x \in X}\abs{\sum_{k=n}^{m-1} f_k(x)} \lt \epsilon.\] In this case, we say that $\sum_{k=0}^\infty f_k$ converges uniformly, and use this to denote the uniform limit of $(g_n)_n$.
   3. Suppose that $(B_k)_k$ is a sequence in $\R_{\geq 0}$ so that \[\sum_{k=0}^\infty B_k\] converges, and $(f_k)_k$ is a sequence of functions $X \to \R$ so that $f_k$ is bounded by $B_k$: that is, $\abs{f_k(x)} \leq B_k$ for all $x \in X$. Use parts A and B to show that \[\sum_{k=0}^\infty f_k\] converges uniformly.
   4. Show that if $\abs{r} \lt 1$, then \[\sum_{k=0}^\infty r^k = \frac1{1-r}.\] (Hint: first notice that $(1-r)(1+r+r^2+\cdots+r^n) = 1-r^{n+1}$.)
   5. Suppose that $(a_k)_k$ is a sequence in $\R$ so that $\limsup_{k\to\infty} \abs{a_k}^{1/k} \lt 1$. Prove that \[\sum_{k=0}^\infty a_k x^k\] converges uniformly on $[-1, 1]$. (Here, "$a_kx^k$" is being used to mean the function $x \mapsto a_kx^k$.)

   A function of the form above is called a power series. Since a power series is the uniform limit of polynomials—which are continuous—it is continuous.

3. A poorly-behaved function

   Let $C : \R \to [-1, 1]$ be a continuous function with the properties that $C(2k) = 1$ and $C(2k+1) = -1$ for every $k \in \Z$, and that $\abs{C(x)-C(y)} \leq 4\abs{x-y}$ for all $x, y \in \R$.

   1. Prove that \[\sum_{j=0}^\infty \paren{\frac34}^j C(9^j x)\] converges uniformly to some function $W : \R \to \R$.
   2. Let $n \in \N$ and $a \in \Z$. Show that \[\abs{W\paren{\frac{a+1}{9^n}} - W\paren{\frac{a}{9^n}}} \gt \paren{\frac34}^n.\] (Hint: the analysis here requires getting your hands dirty, and you'll probably need to make use of both 2D and its hint. Break the sum up into two pieces, and show that the tail is large enough to overcome the first piece.)
   3. Conclude that $W$ is continuous, but not differentiable at any point in $\R$.
   

Here are some further problems to think about out of interest. You do not need to attempt them, nor should you submit them with the assignment. They are coloured by approximate difficulty: easy/medium/hard.

• Uniform convergence and boundedness

  Suppose that $X$ is a set and $(f_n)_n$ is a sequence of functions $X \to \R$, so that each $f_n$ is bounded. Suppose further that $(f_n)_n$ converges uniformly to some $f : X \to \R$. Show that $(f_n)_n$ is uniformly bounded: that is, there is some $T \in \R$ so that for all $x \in X$ and all $n \in \N$, \[\abs{f_n(x)} \leq T.\]

• Uniform convergence and derivatives

  For each $n \in \N$, let \begin{align*} f_n : \R &\longrightarrow \R \\ x &\longmapsto \frac{x}{1+nx^2}. \end{align*} Show that the sequence $(f_n)_n$ converges uniformly (on $\R$) to some function $f$, and that $(f_n')_n$ converges to $f'$ pointwise on $\R\setminus\set0$, but not at $0$.

• Pointwise convergence versus metric space convergence

  Suppose $S$ is a set, and consider the set of functions from $S$ to $\R$, $\R^S = \set{f : S \to \R}$. Let us say that a metric $d$ on $\R^S$ gives rise to the topology of pointwise convergence if whenever $(f_n)_n$ is a sequence of functions in $\R^S$ we have that $(f_n)_n$ converges to a function $f$ with respect to $d$ if and only if $(f_n)_n$ converges pointwise to $f$.

  Show that there is a metric on $\R^S$ giving rise to the topology of pointwise convergence if and only if there is a one-to-one function $\varphi : S \to \N$.

• Uniform convergence versus metric space convergence

  1. Suppose that $S$ is a set and $(M, d_M)$ is a bounded metric space. Define a metric $d_\infty$ on $M^S = \set{f : S \to M}$ by \[d_\infty(f, g) = \sup_{s \in S} d_M(f(s), g(s)).\] Show that a sequence of functions $(f_n)_n$ in $M^S$ converges uniformly to $f : S \to M$ if and only if $(f_n)_n$ converges to $f$ with respect to the metric $d_\infty$.
  2. Let $(M, d_M)$ be a metric space. Define $d_M' : M \times M \to \R_{\geq 0}$ by $d_M'(x, y) = \min(1, d_M(x, y))$. Show that $d_M'$ is a metric equivalent to $d_M$ (i.e., $d_M'$ is a metric such that sets are open with respect to $d_M$ if and only if they are open with respect to $d_M'$). Notice that $(M, d_M')$ is bounded.
  3. Suppose that $X$ is a set, and $d, d'$ are equivalent metrics on $X$. Show that sequences converge with respect to $d$ if and only if they converge with respect to $d'$.
  4. Suppose that $S$ is a set and $(M, d_M)$ is an arbitrary metric space. Show that there is a metric on $M^S$ so that sequences in $M^S$ converge with respect to the metric if and only if they converge uniformly. (We say "the topology of uniform convergence is metrizable".)

• Monotone convergence of functions (Dini's Theorem)

  Suppose that $K$ is a compact metric space, and $(f_n)_n$ is a sequence of continuous functions $K \to \R$, so that $f_1 \leq f_2 \leq f_3 \leq \cdots$. Suppose further that $(f_n)_n$ converges pointwise to some continuous function $f$: that is, for every $x \in K$, \[\limni f_n(x) = f(x).\] Prove that $(f_n)_n$ converges to $f$ uniformly.

• A norm on integrable functions

  Let $R$ be the set of integrable functions on the interval $[a, b]$. Given $f \in R$, define \[\norm{f}_2 = \paren{\int_a^b\abs{f(t)}^2\,dt}^{\frac12}.\]

  1. Show that $\norm\cdot_2$ satisfies the triangle inequality in the following sense: for all $f, g, h \in R$, \[\norm{f-h}_2 \leq \norm{f-g}_2 + \norm{g-h}_2.\]
  2. Suppose $f \in R$. Show that for any $\epsilon \gt 0$, there is a continuous function $g \in R$ with \[\norm{f-g}_2 \lt \epsilon.\] (Hint: choose a suitable partition $P = \set{x_0, \ldots, x_n}$, and take a piece-wise linear function $g$ so that $g(x_i) = f(x_i)$.)
  3. Suppose $f \in R$. Show that for any $\epsilon \gt 0$ there is a polynomial $p \in R$ so that \[\norm{f-p}_2 \lt \epsilon.\] (Hint: for this one you need the Weierstrass Approximation Theorem, which we hopefully will cover next week.)

  The function $d_2(f, g) = \norm{f-g}_2$ on $R\times R$ is a pseudo-metric on $R$: it satisfies the triangle inequality, $d_2(f,f) = 0$, and $d_2(f, g) = d_2(g, f)$, but $d_2(f, g)=0$ does not imply $f = g$. If we define $\sim$ by $f\sim g$ whenever $d_2(f, g) = 0$, then $R/\sim$ becomes a metric space; what we have done is show that (equivalence classes of) polynomials are dense in $R/\sim$.

• Monotony

  State precisely what is meant by:

  • a monotone sequence of functions;
  • a sequence of monotone functions; and
  • a monotone sequence of monotone functions.

  Provide examples to show that these three concepts are different.

• Uniform closures of algebras need not be algebras

  Recall that for $x \in \R$, $\floor{x}$ (the floor of $x$) is the greatest integer $k \in \Z$ with $k \leq x$. For $n \in \N$, define \begin{align*} \varphi_n: \R &\longmapsto \R\\ t & \longmapsto 2^{-n}\floor{2^nt}. \end{align*} Finally, let $\mathscr{A}$ be the algebra of functions generated by $(\varphi_n)_n$. That is, $\mathscr{A}$ consists of all functions which are finite sums of scalar multiples of finite products of $\varphi_n$'s.

  Let $\overline{\mathscr{A}}$ be the uniform closure $\mathscr{A}$. Show that $\overline{\mathscr{A}}$ is not an algebra. (Hint: $x\mapsto x$ is in $\overline{\mathscr{A}}$, but $x \mapsto x^2$ is not.)

  Reflect on what this example says about trying to plot quadratic or linear functions on a pixelated display.

• More on power series

  Prove that a power series is differntiable, and its derivative is given by differentiating the sum term-by-term. (This is not immediate and does take work, as in general, uniform limits of differentiable functions need not be differentiable, or may have derivatives unrelated to the derivatives of their approximants.) Conclude that a power series is infinitely differentiable.

• Functions orthogonal to polynomials are zero

  Let $f : [0, 1] \to \R$ be continuous.

  1. Show that $f \equiv 0$ if \[\int_0^1 f(t)^2\,dt = 0.\]
  2. Suppose that for every $n \in \N\cup\set0$, \[\int_0^1 f(t)t^n\,dt = 0.\] Show that $f \equiv 0$. (Hint: by the end of the week, we will have proved the following theorem which you may find useful: if $K \subseteq \R$ is compact and $g : K \to \R$ is continuous, there is a sequence of polynomials $(p_n)_n$ which converges uniformly to $g$ on $K$. Use this to show that $\int_0^1 f(t)^2\,dt=0$.)

• Another weird pathology

  Show by example that there exists a function $f : \R \to \R$ such that $f$ takes on every real value on every non-empty open set. That is, for any $U \subseteq \R$ open and any $y \in \R$, there is some $x \in U$ with $f(x) = y$. (This isn't really related to this week's material in particular, it's just an interesting problem.)

• Coins and random numbers

  Suppose you're interested in generating integers uniformly at random from $0$ to $N-1$ by flipping coins. If $N = 2$ and you have a fair coin, this is easy: flip it once, and answer $0$ if it's tails and $1$ if it's heads. If $N = 2^k$ you can similarly do this using $k$ flips of a fair coin, writing down a $k$-bit binary number. If you allow yourself to take an arbitrarily large number of flips, you can make this work for any $N$: for example, to generate something from $0$ to $9$, uniformly generate numbers with $N=16$ using four flips each, and take the first that is less than $10$. This can take a rather long time.

  What happens if you are making flips with unfair coins? If you have a coin which lands on heads with probability $1/3$ and a fair coin, you can get a uniform random number from $\set{0,1,2}$ as follows: flip the biased coin, and if you see heads, answer $2$; otherwise, flip the fair coin and return $0$ or $1$ based on its result. If you have $N-1$ biased coins with probabilities $\frac1{N}, \frac1{N-1}, \ldots, \frac12$ of landing heads, you can do a similar trick to get a fair number from $0$ to $N-1$: flip the coins starting from the least fair, and answer the first time you see heads.

  Unfortunately, biased coins are somewhat difficult and expensive to manufacture, so we would like to use as few as possible. This leads to the following question: given a natural number $N$, what is the minimum number of biased coins required to generate a number in $\set{0,1,\ldots,N-1}$ uniformly at random, using a number of flips you must fix ahead of time? Does the answer change if you are only allowed to use coins with rational bias?