# Miklos Schweitzer 2014 Problem 8: polynomial inequality

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?

• What is the problem statement for those of us unwilling to open pdf files from random sites? Dec 7 '14 at 19:03
• I will be starting a bounty on this question soon.
– user198454
Dec 9 '14 at 16:05
• @TheMathTroll: for what purpose, if I may dare to ask? Dec 9 '14 at 16:20
• to see if there are any elementary solutions / better explained solutions? I am particularly interested in elementary solutions.
– user198454
Dec 10 '14 at 0:20
• The purpose is here: komal.hu/verseny/… Dec 10 '14 at 10:11

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}}.$$

• Thanks! I do not understand why is it sufficient to only consider $f(x)=x^n$ since that is the easiest function to approximate? I also don't understand how could $\frac{2}{4^n}$ be achieved here. So we are finding the $f(x)$ and $p(x)$ such that they are the best approximations of each other, right? I understand how did you get the best approximation of $x^n$ (for polynomials with degree less than $n$), but why did you just disregard all other possible polynomials $f(x)$ (that all their terms have degree greater than $n$ and the sum of its coefficients is $1$?)
– user198454
Dec 8 '14 at 5:56
• @TheMathTroll: By the error in the Lagrange approximation, $x^n$ is the best approximable function. With the best choice of interpolation nodes, the uniform error is exactly $\frac{2}{4^n}$. Dec 8 '14 at 9:15
• What do you mean the "best approximable function"? Does that mean the function that has the least possible error? How did you show that x&n is the best approximable function? May I see the proof?
– user198454
Dec 8 '14 at 10:03
• @TheMathTroll: yes, the best approximable function is the function for which the uniform error of the best polynomial approximation is the least possible. Again, to prove that $x^n$ is the best approximable function you only need the formula for the error of the Lagrange interpolation. Dec 8 '14 at 10:27
• is the formula for the error of the lagrange interpolation the one of the link? By the way, is there an elementary solution to this problem?
– user198454
Dec 8 '14 at 10:28

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}}$.