If $f:[0,1]\rightarrow\mathbb{R}$ satisfies $|f(x)-f(y)|<|x-y|\ $ for all $x$, $y\in[0,1]$ and $\epsilon>0$ is fixed, why must there be a polynomial $p$ of degree less than $\frac{10}{\epsilon^3}$ such that $|f-p|_{\infty}<\epsilon$?
I've tried an $\frac{\epsilon}{3}$-type method, using $|f(x)-p(x)|\leq|p(x)-p(y)|+|p(y)-f(y)|+|x-y|$, but couldn't get good enough bounds on the RHS. Since $f$ must be (uniformly) continuous, maybe we could use Bernstein polynomials? Or does the peculiar bound on the degree give us a clue as to how to find a suitable $p$?
Many thanks for any help with this!
Since the function $f$ is continuous on $[0,1]$ we can apply the Jackson's theorem which says $$ |f(x)-P_n(x)|\leq C \omega\left( f,\frac{1}{n}\right), $$ where $P_n$ is a polynomial of degree at most $n$ and $\omega(f,\delta)$ is the modulus of continuity of $f$. Here the sharp value of $C$ is known. More details can be found here https://www.encyclopediaofmath.org/index.php/Jackson_inequality. Using the Lipschitzian property of $f$ an estimation for the degree follows (if the error is controlled by $\varepsilon$). If you want to avoid Jackson's theorem, then, you are right, the Bernstein polynomials can be used. By very elementary calculation gives that $$ |f(x)-B_n(f,x)|\leq C \omega\left( f,\frac{1}{\sqrt{n}}\right), $$ see e.g. www.springer.com/cda/content/document/cda_downloaddocument/9780387954844-c36.pdf Theorem 36.4.