I am trying to solve the following problem:
Let $ K=\{f \in C^1([0,1], \mathbb{R}): f(0)=0, |f'(x)|\leq 1 \; \forall x\} \subset C([0,1],\mathbb{R})$
- Prove that $K$ is precompact in $C([0,1])$
- Prove that, for every $n \in \mathbb{N}$, $K$ can be covered with $4^n$ closed balls in $C([0,1])$ of radius $1/n$ (Hint: Consider balls centered at suitable piecewise affine functions with slope $\pm1$).
I was able to prove point (1) by applying Arzelà–Ascoli theorem. I am struggling to prove point (2). I tried to construct the balls explicitly but with no success, even in the case $n=1$. I started by observing that for every $f \in K$ we have $$ -x \leq f(x) \leq x \quad \forall x \in [0,1] $$ and I thought that this could be useful. I then considered the balls of radius $1$ centered at $f_1(x) = x$ and $f_2(x) =-x$ but these do not seem enough. I thought that maybe I should consider vertical translations of $f_1$ and $f_2$ or some zig-zag looking functions, but I am unable to conclude. Also, maybe I do not have to construct the balls explicitly, but I do not have in mind other ways to prove their existence (the only thing that comes to my mind is to use the fact that compact metric spaces are totally bounded, but I do not know how).
Could you please give me some help? Thank you.
P.s. This problem is taken from a past entrance exam to a PhD in Mathematical Analysis. If you recognize that this is from some book, or if you have a source of similar problems, please tell me.
This answer is based on linear interpolation on the grid $\Lambda_n$ defined below. The key point is that the assumption on $K$ allow one to severely restrict the number of different piecewise linear functions needed to get good approximations. The verification that the closed balls defined here do work is a tedious induction which is essentially case checking which I outline at the end.
Fix $n \geq 1$.
For each $k = 0, \dots n$, define $\Lambda_n^{(k)} = \{ \frac{j}{n}: |j| \leq k\}$. Let $\tilde{\Xi}_n = \Lambda_n^{(0)} \times \dots \Lambda_n^{(n)}$ and finally let $$\Xi_n = \left \{a = (a_0, \dots, a_n) \in \tilde{\Xi}_n: \text{ for } j = 0, \dots, n-1, \, \, |a_{j+1} - a_j| \leq \frac{1}{n} \right\}$$
It is a simple exercise to verify that $|\Xi_n| = 3^n$ (a bit better than we need).
This is all the set-up needed to define the centers of the closed balls we will use. Indeed, for $a = (a_0, a_1, \dots, a_n) \in \Xi_n$, we can define $f_a \in C([0,1])$ by letting $f_a(x) = a_k$ if $x = \frac{k}{n}$ with $k = 0, \dots, n$ and by linearly interpolating otherwise. Define $\Phi: \Xi_n \to C([0,1])$ by $\Phi(a) = f_a$. Note that $\Phi(\Xi_n)$ is a set of piecewise affine functions with affine segments of slope $\pm 1$ as suggested in the hint.
Then I claim that $$K \subseteq \bigcup_{f \in \Phi(\Xi_n)} \overline{B}(f, \frac{1}{n}).$$
Fix $g \in K$. We will prove that $g$ lies in the right hand side by constructing $a^g \in \Xi_n$ such that $\|g - \Phi(a^g)\|_\infty \leq \frac{1}{n}$.
Without loss of generality, we can assume that $g(\frac{1}{n}) < \frac{1}{n}$. If $g(\frac{1}{n}) = \frac{1}{n}$ then apply the proof below to $-g$ to get a sequence $a^{-g}$ and define $a^g = -a^{-g}$. For $i \geq 1$, let $j_i$ be such that $g(\frac{i}{n}) \in \left[\frac{j_i}{n}, \frac{j_i+1}{n}\right)$. Let $j_0 = 0$.
I inductively construct the sequence $a^g$ with the additional property that $a_i^g \in \{\frac{j_i}{n}, \frac{j_i + 1}{n}\}$. We have little choice but to choose $a_0^g = 0$. Suppose now that we have defined suitable $a_0^g, \dots, a_k^g$ for $k < n$. We need to find a suitable $a_{k+1}^g$.
If $j_{k+1} = j_k + 1$ then let $a_{k+1}^g = a_k^g + \frac{1}{n}$. Similarly, if $j_{k+1} = j_k - 1$ then let $a_{k+1}^g = a_k^g - \frac{1}{n}$.
If $j_{k+1} = j_k$ and there exists $y \in [\frac{k}{n}, \frac{k+1}{n})$ such that $g(y) > \frac{j_k + 1}{n}$ then let $a_{k+1}^g = j_k + \frac1n$. Otherwise let $a_{k+1}^g = j_k$.
Finally one has
Sketch Proof: An induction using the definition of $a^g$ and $\Phi$. This is straightforward but involves a lot of tedious casework. The key point is that since $|g'| \leq 1$, once $g$ is below a line of slope $1$, it cannot cross above it and similarly for lines of slope $-1$. The details are below.
Proof of Proposition:
Again, without loss of generality, we consider only the case $g(\frac{1}{n}) < \frac{1}{n}$.
The base case $k = 0$ is trivial. Now suppose that $$\sup_{y \in [0, \frac{k}{n}]} |g(y) - \Phi(a^g)(y)| \leq \frac{1}{n}.$$
Case 1: $j_{k+1} = j_k + 1$
Since $|g'| \leq 1$, one can check that if $g(\frac{k}{n}) \in [\frac{j_k}{n}, \frac{j_k + 1}{n})$ and $g(\frac{k+1}{n}) \in [\frac{j_k+1}{n}, \frac{j_k + 2}{n})$ then for $y \in [\frac{k}{n}, \frac{k+1}{n}]$, we have that $$g(y) \in \left[\frac{j_k}{n} + (y - \frac{k}{n}), \frac{j_k + 1}{n} + (y - \frac{k}{n})\right)$$ which is sufficient for the inductive step in this case since $a_k^g \in \{\frac{j_k}{n}, \frac{j_k + 1}{n}\}$, $a_{k+1}^g = a_k^g + \frac1n$ and hence $\Phi(a^g)$ is affine of slope $+1$ on $[\frac{k}{n}, \frac{k+1}{n})$. This means that $\Phi(a^g)$ is precisely one of the two bounding lines of the region we showed $g$ to lie in.
Case 2 $j_{k+1} = j_k - 1$
This is essentially the same as case $1$, up to a reflection about the $x$-axis so I omit the details.
Case 3 $j_{k+1} = j_k$ and there exists $y \in [\frac{k}{n}, \frac{k+1}{n})$ such that $g(y) > \frac{j_k + 1}{n}$.
First suppose that $a_k^g = \frac{j_k+1}{n}$. In this case, we need to show that for $y \in [\frac{k}{n}, \frac{k+1}{n}]$, we have that $g(y) \in [\frac{j_k}{n}, \frac{j_k + 2}{n}]$. The upper bound is trivial since $g(\frac{k}{n}) < \frac{j_k + 1}{n}$ and $|g'| \leq 1$. The lower bound follows from the fact there is a $y \in [\frac{k}{n}, \frac{k+1}{n})$ with $g(y) > \frac{j_k + 1}{n}$ and the fact that $|g'| \leq 1$.
Otherwise, we have that $a_k^g = \frac{j_k}{n}$. In this case, we need to show that for $y \in [\frac{k}{n}, \frac{k+1}{n}]$, we have that $g(y) \in [\frac{j_k}{n} + (y - \frac{k}{n}), \frac{j_k + 1}{n} + (y - \frac{j_k}{n})]$. The upper bound follows as in previous cases. For the lower bound, notice that if $g$ drops below the line $\frac{j_k}{n} + (y - \frac{k}{n})$ then since $|g'| \leq 1$, it cannot cross back above it. This contradicts the assumption that there is a $y \in [\frac{k}{n}, \frac{k+1}{n})$ such that $g(y) > \frac{j_k + 1}{n}$.
Case 4 $j_{k+1} = j_k$ and for $y \in [\frac{k}{n}, \frac{k+1}{n})$ we have that $g(y) \leq \frac{j_k + 1}{n}$.
First, if $a_k^g = \frac{j_k}{n}$ then we need to show that for $y \in [\frac{k}{n}, \frac{k+1}{n}]$, we have that $g(y) \in [\frac{j_k - 1}{n}, \frac{j_k + 1}{n}]$. The lower bound is trivial from $|g'| \leq 1$ and the upper bound follows by assumption.
Otherwise, $a_k^g = \frac{j_k + 1}{n}$. Then we need to show that for $y \in [\frac{k}{n}, \frac{k+1}{n}]$, we have that $g(y) \in [\frac{j_k}{n} - (y - \frac{k}{n}), \frac{j_k + 2}{n} - (y - \frac{k}{n})]$. The lower bound is once again trivial from the fact that $|g'| \leq 1$ and $g(\frac{k}{n}) \geq \frac{j_k}{n}$. The upper bound follows from our assumption since the line $\frac{j_k + 2}{n} - (y - \frac{k}{n})$ lies above the horizontal line $j_k + 1$.
Edit: The easiest way to understand the proof (and the way I came up with it) is by drawing some pictures, starting with the grid $\{(\frac{j}{n}, b_j): 0 \leq j \leq n, b_j \in \Lambda_n^{(j)}\}$ and a function $g \in K$ and then trying to approximate $g$.
Below is one such picture. The black and green nodes are points in the grid. The blue curve represents the function $g \in K$ and then the green nodes represent $a^g$ generated by my induction. The green dashed lines are then $\Phi(a^g)$. Finally, the red dashed lines are the boundaries of the set of curves at distance at most $\frac{1}{n}$ from $\Phi(a^g)$ which we need to show $g$ cannot cross. The case checking is then just checking that $g$ does not cross those lines regardless of their slope in any interval.