("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)}$$


$$||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$?

  • $\begingroup$ Yes, classical Weierstrass function and similar ones match the title question, for instance. $f(x)=\sum_{n=0}^\infty a^n \cos(b^n\pi x)$, $0<a<1$, $b$ positive odd integer and $ab >1 + 3\pi/2$ $\endgroup$ Jun 17, 2022 at 23:30
  • $\begingroup$ @JorgeZuniga how do you prove that? $\endgroup$
    – Derivative
    Jun 18, 2022 at 16:35


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.