("Hard" in the same way that $\varphi=\frac{1+\sqrt 5}2$ is "hard to approximate by rationals".)

I'll state the problem here and give the motivation below. Is there a continuous function $f$ defined on a compact interval, with finitely many local extrema, such that for all polynomials $P$ and all $n$ large,

$$||f-P||_\infty=\sup_x |f(x)-P(x)|<\frac 1n\implies P\text{ has degree }\geq k(n)$$

for any function $k:\mathbb N\to\mathbb N$? The answer is yes if $k$ grows polynomially and unknown otherwise.

A professor asked me: for any function $k:\mathbb N\to\mathbb N$ is there a continuous function $f:[0,1]\to \mathbb R$ such that if $P$ is a polynomial and

$$||f-P||_\infty=\sup_{x\in [0,1]}|f(x)-P(x)|<\frac 1n$$

then the degree of $P$ is at least $k(n)$? I answered that the function

$$f(x)=g(x)\cos\left(\frac\pi x\right)$$

where $g$ is continuous, increasing, and satisfies $\lim_{x\to 0}g(x)=0$ and $g\left(\frac 1{k(n)+2}\right)>\frac 1n$ for all $n$ satisfies the condition required. To prove that, notice that if $P$ is a polynomial and $||f-P||_\infty<\frac 1n$ then $|f\left(\frac 1h\right)-P\left(\frac 1h\right)|<\frac 1n$ for all $h\in\{1,2,\dots ,k(n)+2\}$. And for each of these, $f\left(\frac 1h\right)=(-1)^hg\left(\frac 1h\right)$ so $f\left(\frac 1h\right)$ and $P\left(\frac 1h\right)$ must have the same sign, which alternates with each consecutive $h$, so $P$ must have $k(n)+1$ roots, so its degree is greater than $k(n)$.

(There's a solution to an equivalent problem in "Introduction to Approximation Theory" by Cheney but we don't know what the function he constructs "looks like", as it's an infinite sum of Chebyschev polynomials.)

Now consider the same problem with the additional constraint that $f$ has finitely many local extrema. The most general result I could find about this is Bernstein's theorem which can be used to prove that the function $f:[-1,1]\to\mathbb R$,

$$f(x)=\frac 1{\log\left(\frac{\arccos(|x|)}2\right)}$$

satisfies

$$||f-P||_\infty<\frac 1n\implies P\text{ has degree }\geq n^t$$

for all $t\in\mathbb N$ and $n$ sufficiently large. You can prove that by noticing that $g(x)=f(\cos(x))$ is not $\alpha$-Hölder for any $\alpha>0$ and applying Bernstein's theorem.

So the question is whether this is the hardest it can possibly be to approximate a function by polynomials. Can we, for example, find an example for $k(n)=n^n$?