# Show that $\inf \{ \| f-P \|_{\infty}\mid P \in P_n \} \geq \delta_n$ for any decreasing sequence $\delta_n \to 0$

I'm trying to show that given any decreasing sequence $$\delta_n \to 0$$, we can find a continuous function $$f: [-1,1] \to \mathbb{R}$$ such that $$\inf\{\|f-P \|_{\infty}\mid P \text{ a polynomial of degree at most } n \} \geq \delta_n.$$

The hint I've been given is to show that, if $$\gamma_j$$ is a sequence of non-negative numbers with $$\sum_{j \geq 1} \gamma_j$$ convergent and $$T_j$$ is the $$j$$th Chebyshev polynomial, then show that $$\displaystyle \sum_{j \geqslant 1} \gamma_j T_{3^j}$$ converges uniformly on $$[-1,1]$$ to a continuous function $$f$$ and that if $$P_n = \sum_{j=1}^n \gamma_j T_{3^j}$$ then we can find points $$-1 \leqslant x_0 \leqslant \cdots \leqslant x_{3^{n+1}} \leqslant 1$$ with $$f(x_k) - P_n(x_k) = (-1)^{k+1} \sum_{j=n+1}^{\infty} \gamma_j.$$I haven't even managed to do much with the very first part of the hint, I'm having trouble showing that it converges uniformly. Given that I can't come up with a candidate limit, I suppose I need to show that its uniformly Cauchy (assuming that partial sums of $$\gamma_j$$ are Cauchy) but I'm not sure how to work with the Chebyshev polynomials.

In any case, I'm uncertain as to how the hint even applies to the question, I can see that $$\sum_{j=n+1}^\infty \gamma_j$$ is a decreasing sequence, which is more or less the only link I can think of between the parts, but again, doesn't help in any way.

As mentioned in the comment, the Bernstein's lethargy theorem is a generalization of the result you are looking for. Below is a proof following the hints you were given.

Convergence

Note that for for $$n \in \mathbb{N}$$, for $$x \in [-1,1]$$, $$T_n(x)=\cos(n\mbox{Arccos}(x))$$. With $$||\cdot||_{\infty}$$ the supremum norm on $$\mathcal{C}^0([-1,1]),\mathbb{R})$$, we have the upper bound $$\sum \limits_{n=1}^{\infty} ||\gamma_n T_{3^n}||_{\infty} \le \sum \limits_{n=1}^{\infty} |\gamma_n| \cdot 1 = \sum \limits_{n=1}^{\infty} \gamma_n < +\infty$$.

The series $$\sum \limits_{n\ge 0} \gamma_nT_{3^n}$$ is normally convergent on $$[-1,1]$$, so it is uniformly convergent to some $$f$$. 



Existence of the $$P_n$$

Note that if $$\cos(\theta)=-1$$ then $$\theta \equiv \pi \pmod{2\pi}$$ so $$3\theta \equiv \pi \pmod{2\pi}$$ and by induction $$\cos(3^k\theta) = -1$$. Similarly, $$\cos(\theta)=1 \Rightarrow \forall k \ge 0, \cos(3^k\theta)=1$$. (*)

Now for any $$n$$, we know that $$T_{3^n}$$ equioscillates: denoting $$x_k = \cos\big(\pi - \frac{k\pi}{3^{n+1}}\big)$$ for $$0\le k \le 3^{n+1}$$, we have $$-1=x_0<... and $$T_{3^{n+1}}(x_k) = \cos\big(3^{n+1}\cdot (\pi - \frac{k \pi}{3^{n+1}})\big) = (-1)^{1-k} = (-1)^{k+1}$$. Then for all $$j \ge n+1$$ we have $$T_{3^j}(x_k) = \cos\big(3^{j-n-1} \cdot 3^{n+1}\mbox{Arccos}(x_k)\big) = (-1)^{k+1}$$ because of (*).

Hence, $$\sum \limits_{j=n+1}^{\infty} \gamma_j T_{3^j}(x_k) = \sum \limits_{j=n+1}^{\infty} \gamma_j (-1)^{k+1}$$. With $$P_n := \sum \limits_{j=1}^n \gamma_j T_{3^j}$$, we have $$f-P_n = \sum \limits_{j \ge n+1} \gamma_j T_{3^j}$$, so: $$\mbox{Choosing } x_k := \cos\big(\pi-\frac{k\pi}{3^{n+1}}\big) \mbox{for 0\le k \le 3^{n+1}, we have } (f-P_n)(x_k) = (-1)^{k+1} \sum \limits_{j=n+1}^{\infty} \gamma_j.$$

Conclusion about the distance of $$f$$ to polynomial spaces

We will denote $$d_p(f)=d(f,\mathbb{R}_p[X]) := \inf \{||f-P||_{\infty}, P\in \mathbb{R}_p[X]\}$$. We have $$P_n \in \mathbb{R}_{3^n}[X] \subset \mathbb{R}_{3^{n+1}-1}[X]$$ and there are $$3^{n+1}+1 \ge 3^{n+1}-1$$ equioscillation points to $$f$$ so according to the equioscillation theorem, for any degree $$p \in [\![3^n,3^{n+1}-1]\!]$$, $$P_n$$ is the best approximation to $$f$$ in $$\mathbb{R}_p[X]$$ so $$\forall n \ge 0,\ \forall p \in [\![3^n,3^{n+1}-1]\!],\ d_p(f) = ||f-P_n||_{\infty} = \sum \limits_{j=n+1}^{\infty} \gamma_j.$$

Now a last constructive part. Let $$(\delta_n)$$ be any sequence of real decreasing to $$0$$. Denote $$\gamma_j = \delta_j - \delta_{j+1}$$. Then $$\gamma_j$$ is non negative and its sum converges. We apply what is above to these $$\gamma_j$$ and obtain some function $$f$$. Let $$p \ge 1$$. There exists $$n \ge 0$$ such that $$3^n \le p < 3^{n+1}$$. Thus $$n < p$$ (because $$3^p \ge 2^p \ge p+1$$). The previous inequality gives us $$d_p(f) = \sum \limits_{j=n+1}^{\infty} \gamma_j = \delta_{n+1} - 0$$. And $$(\delta_k)$$ is decreasing and $$n+1 \le p$$ so finally $$d_p(f) \ge \delta_p$$.