Polynomial Approximations to Continuous Functions

When I was taking undergrad real analysis, the professor, Ali Tahzibi, was teaching us about the Stone-Weierstrass theorem, and he asked my class: let $e_{n} (f) = \inf_{p \in ℝ [x], deg (p) \leq n} ‖ f - p ‖_{\infty}$ where $‖ \cdot ‖_{\infty}$ is the supremum norm. The theorem says $e_{n} (f) \to 0$ , but can the convergence be arbitrarily slow? He offered one million bucks for the solution instantly grabbing my attention.

You can scarcely do mathematical analysis without polynomial approximations, so the Stone-Weierstrass theorem is foundational, and if it was possible to improve its rate of convergence that would be a major result. Initially, it seemed impossible to construct a function so pathological that even $e_{n} (f) > \frac{1}{\log (n)}$ , and the question was asking for a lot more than that. There are upper bounds on $e_{n} (f)$ for large classes of functions, including Hölder continuous, or those whose modulus of continuity is good enough. In particular, even famously pathological functions such as Weierstrass's example of a continuous nowhere differentiable function, or (with probability $1$ ) a Wiener process have upper bounds on $e_{n} (f)$ .

I pondered the question for a few days, and finally found a counterexample proving that the answer is no by relating approximations to the number of roots of a polynomial. Precisely, for any sequence $(a_{n})_{n \in ℕ}$ of positive real numbers converging to $0$ , there is a function $f : [0,1] \to ℝ$ such that $e_{n} (f) > a_{n}$ for all $n$ . He encouraged me to submit it to the American Mathematical Monthly for publication, which I did, and it was accepted a week later. I hope all my publications throughout my career follow a similar Blitzkrieg timeframe.

The construction of the counterexample is brutally simple. The key insight is that to force a polynomial approximant to have a high degree, you must force it to have a lot of roots. We can do this by making $f$ oscillate around $0$ , forcing a good-enough approximant to do the same. Fix a sequence $(a_{n})_{n \in ℕ}$ of numbers decreasing to $0$ , and let $g : [0,1] \to ℝ$ be an increasing continuous function such that $g (0) = 0$ and $f (x) = {\begin{matrix} 0 & x = 0 \\ g (x) \cos (\frac{π}{x}) & x \neq 0. \end{matrix}$ Where $g (\frac{1}{n + 2}) > a_{n}$ for all $n$ , which can be achieved defining $g$ as affine by parts in the intervals $(\frac{1}{k + 1}, \frac{1}{k})$ .

A polynomial approximation $p$ satisfying $‖ f - p ‖_{\infty} < a_{n}$ must have a root in each of the intervals $(\frac{1}{n + 2}, \frac{1}{n + 1}) \dots (\frac{1}{2}, 1)$ i.e. at least $n + 1$ roots so its degree is more than $n$ . Indeed, for each positive integer $k \leq n + 2$ , we have $f (\frac{1}{k}) = g (\frac{1}{k}) \cos (π k) = g (\frac{1}{k}) (- 1)^{k}$ , and

| f (\frac{1}{k}) - p (\frac{1}{k}) | < a_{n} < g (\frac{1}{n + 2}) \leq g (\frac{1}{k}) = | f (\frac{1}{k}) |

so $p (\frac{1}{k})$ and $f (\frac{1}{k})$ have the same sign.

In the literature, there is an equivalent construction. [1] They achieve it by letting $f = \sum_{k = 1}^{\infty} (a_{k + 1} - a_{k}) T_{3^{k}}$ where $T_{k} (x) = \cos (k \arccos (x))$ is a Chebyschev polynomial. Using Chebyschev polynomials as a basis is very useful to determine approximation-theoretical properties but unfortunately not much else. The construction as a lacunary series further obscures the properties of f. I think my construction gives more insight into why convergence is slow.

I think this is a pretty fun result, and I'm grateful to professor Tahzibi for suggesting it.

[1] Cheney, E. W. (2000). Introduction to Approximation Theory. Providence, RI: American Mathematical Society.