Miklos Schweitzer 2014 Problem 8: polynomial inequality

Question

Look at problem 8 :

Let $n\geq 1$ be a fixed integer. Calculate the distance: $$\inf_{p,f}\max_{x\in[0,1]}|f(x)-p(x)|$$ where $p$ runs over polynomials with degree less than $n$ with real coefficients and $f$ runs over functions $$ f(x)=\sum_{k=n}^{+\infty}c_k\, x^k$$ defined on the closed interval $[0,1]$, where $c_k\geq 0$ and $\sum_{k=n}^{+\infty}c_k = 1.$

This is what I have so far.

Clearly for $n=1$, we have $1/2$. I am conjecturing for $n>1$, we have $(n-1)^{(n-1)} / n^n$ or something similar to that? (just put $x^{(n-1)}$ and $x^n$ then use AM-GM). it's just weird that the pattern does not fit, so it's probably wrong. Any ideas?

Answer 1

Your inequality does not hold since $x^{n-1}$ is not the best approximation polynomial of $x^n$ with respect to the uniform norm. By Chebyshev's theorem we have that if $p(x)$ is the best approximation polynomial for $f(x)$, then $f(x)=p(x)$ holds for $\partial p+1$ points in $[0,1]$.

For instance, if $f(x)=x^n$ and $p(x)$ is the Lagrange interpolation polynomial with respect to the points $x=\frac{k}{n}$ for $k=1,2,\ldots,n$, since $f^{(n)}(x)=n!$ we have: $$\|f(x)-p(x)\|_{\infty} = \left\|\prod_{k=1}^{n}\left(x-\frac{k}{n}\right)\right\|_{\infty}=\frac{n!}{n^n}$$ that is below your bound for any $n\geq 4$.

We can improve this bound by choosing our interpolation points more carefully: by selecting Chebyshev nodes, for instance: $x_k=\cos^2\frac{\pi(2k-1)}{4n}$ for $k=1,\ldots,n$.

In order to find the best approximation polynomial of $x^n$, have a look at the following answer of Noam Elkies on MO: https://mathoverflow.net/questions/70440/uniform-approximation-of-xn-by-a-degree-d-polynomial-estimating-the-error .

Since $\|T_n(2x-1)\|_\infty=1$, with the best choice for the interpolation nodes we have that the uniform error in approximating $x^n$ is always greater than $\color{red}{\frac{2}{4^n}}$.

Since for every function in our class we have $\frac{f^{(n)}(\xi)}{n!}\geq 1$ for any $\xi\in[0,1]$, $f(x)=x^n$ is the easiest function to approximate, and:

$$\inf_{p,f}\|f-p\|_{\infty}=\color{red}{\frac{2}{4^n}}.$$

Answer 2

Let $$t_n(x) = \frac1{2^{2n-1}} T_n(2x-1).$$ If $f-p=t_n$, i.e. $f(x)=x^n$ és $p(x) = x^n-t_n(x)$ then $$\max_{0\le x\le 1} \big|f(x)-p(x)\big| = \max_{0\le x\le 1} \big|t_n(x)\big| = \frac1{2^{2n-1}} \max_{-1\le x\le 1} \big|T_n(x)\big| = \frac1{2^{2n-1}}. $$

We show that this is the minimal possible value. For all functions $f(x)$ and different reals $a_0,a_1,\ldots,a_n$, denote by $f[a_0,a_1,\ldots,a_n]$ the divided difference of $f$ on the nodes $a_0,\ldots,a_n$. The divided difference of the power $X^N$ will be denoted by $X^N[a_0,a_1,\ldots,a_n]$. It is well-known (and can be proved by induction) that $$ f[a_0,a_1,\ldots,a_n] = \sum_{j=0}^n \frac{f(a_j)}{\prod\limits_{k\ne j}(a_j-a_k)}, \tag1 $$ and $$ X^N[a_0,a_1,\ldots,a_n] = \sum_{d_0+d_1+\dots+d_n=N-n} a_0^{d_0}a_1^{d_1}\cdots a_n^{d_n} \tag2 $$ where the exponents $d_0,\ldots,d_n$ run over the nonnegative integers. If $N<n$ then the sum is empty.

Let $a_k=\frac12(1+\cos\frac{k\pi}n)$; then $t_n(a_k)=\frac{(-1)^k}{2^{2n-1}}$. On the RHS of $(2)$ all summands are nonnegative; if $N\ge n$ then one of the terms is $a_0^{N-n}=1$. Hence, \begin{align*} X^N[a_0,\ldots,a_n] &= 0 \quad \text{if $N<n$}; \\ X^N[a_0,\ldots,a_n] &=1 \quad \text{if $N=n$}. \\ X^N[a_0,\ldots,a_n] &\ge 1 \quad \text{if $N>n$}. \tag{3} \end{align*}

Taking the divided difference term by term, we can see that $$ t_n[a_0,\ldots,a_n] = X^n[a_0,\ldots,a_n] = 1. $$

Now let $f(x) = \sum\limits_{k=n}^\infty c_k x^k$, and let $p(x)=-\sum\limits_{k=0}^{n-1}c_kx^k$ be an arbitrary plynomial with degree less than $n$. Let $M=\max\limits_{[0,1]}|f-p|$ and consider the divided difference $(f-p)[a_0,\ldots,a_n]$.

From (1) we get \begin{gather*} (f-p)[a_0,\ldots,a_n] = \sum_{j=0}^n \frac{f(a_j)-p(a_j)}{\prod\limits_{k\ne j}(a_j-a_k)} \le \sum_{j=0}^n \frac{M}{\Big|\prod\limits_{k\ne j}(a_j-a_k)\Big|} = \\ = 2^{2n-1}M \sum_{j=0}^n \frac{(-1)^j/2^{2n-1}}{\prod\limits_{k\ne j}(a_j-a_k)} = 2^{2n-1}M \sum_{j=0}^n \frac{t_n(a_j)}{\prod\limits_{k\ne j}(a_j-a_k)} = \\ = 2^{2n-1}M \cdot t_n[a_0,\ldots,a_n] = 2^{2n-1}M. \end{gather*}

On the other hand, by (3), $$ (f-p)[a_0,\ldots,a_n] = \sum_{k=0}^\infty c_k \cdot X^k[a_0,\ldots,a_n] \ge \sum_{k=0}^{n-1} c_k \cdot 0 + \sum_{k=n}^\infty c_k \cdot 1 = \sum_{k=n}^\infty c_k = 1. $$

Therefore, $1 \le (f-p)[a_0,\ldots,a_n] \le 2^{2n-1}M$, so $M\ge\dfrac1{2^{2n-1}}$.