# A min-max approximation

Let $$n\ge 1$$ be an integer, $$\mathcal P_n$$ be the vector space of all polynomial functions over $$[a,b]$$, of degree at most $$n$$.

My question is : Is it true that

$$\inf_{x_0,x_1,...,x_n\in[a,b], x_0

I can easily see that $$\inf_{x_0,x_1,...,x_n\in[a,b],x_0 but I don't know about the other reverse inequality.

• Take $[a,b]=[1,2]$, and $n=2$. Then in the right hand side you can always take infimum over polynomials $P(x)=\lambda x^{2}$ with $\lambda \to \infty$. In this case, the left-hand side stays bounded whereas the right-hand side goes to $-\infty$. – Paata Ivanishvili Oct 1 '18 at 15:10
• There is a modulus missing on the right, I guess... – user111 Oct 1 '18 at 16:08
• @user111: yeah there's a modulus sign .. thanks ... fixed it now – user521337 Oct 1 '18 at 22:47
• @PaataIvanishvili: there were some modulus sign missing ... please look at the edited question – user521337 Oct 1 '18 at 22:51
• Still does not work. Take $n=1$, and $[a,b]=[0,1]$. Then $\inf_{x_{1} \in [0,1]} \sup_{x\in [0,1]}|x-x_{1}| = \inf_{x_{1}\in [0,1]}\max\{|x_{1}|, |1-x_{1}|\}=1/2$. For the right hand side choose $P(x)=x$, then the right hand side is less than $\sup_{x\in [0,1]}|x^{2}-x|=1/4$. – Paata Ivanishvili Oct 2 '18 at 0:57

When $$[a,b]=[-1,1]$$, the $$\inf$$ on the right-hand side is attained (uniquely) by the monic Chebyshev polynomial $$T_{n+1}$$. It is well known that its roots belong to $$[-1,1]$$ and are simple.

For a general interval $$[a,b]$$, using the linear map $$f(x)=\left(\frac{2}{b-a}\right)x-\left(\frac{b+a}{b-a}\right)$$ that sends $$[a,b]$$ onto $$[-1,1]$$, it is clear that the $$\inf$$ on the right-hand side is attained by $$\left(\frac{b-a}{2}\right)^{n+1} T_{n+1}(f(x)),$$ which, of course, has all its (simple) roots in $$[a,b]$$.

Actually, a more general result holds true. Replace $$[a,b]$$ with any compact subset $$K$$ of the complex plane $$\mathbb{C}$$. Set, for a polynomial $$P$$, $$\|P\|_{K}=\sup_{z\in K}|P(x)|,$$ and let $$T_{n}$$ be a polynomial that achieves the minimum of $$\|P\|_{K}$$ among all monic polynomials of degree $$n$$.

Claim: All the zeros of $$T_{n}$$ belong to the convex hull of $$K$$.

Indeed, assume that $$z_{0}$$ is a root of $$T_{n}$$ that does not belong to the convex hull of $$K$$. Then, $$K$$ lies in a cone with vertex at $$z_{0}$$, of opening $$<\pi$$. Choose a $$z_{1}$$ on the bisector $$L$$ of that cone, sufficiently close to $$z_{0}$$ so that $$K$$ lies in the half-plane, delimited by the perpendicular to $$L$$ at $$z_{1}$$ (and not containing $$z_{0}$$). Since $$|z-z_{1}|<|z-z_{0}|,\quad z\in K,$$ one gets $$\|\tilde T_{n}\|_{K}<\|T_{n}\|_{K}$$ where $$\tilde T_{n}(z)=T_{n}(z)(z-z_{1})/(z-z_{0})$$, which contradicts the assumption on $$T_{n}$$.

Take any interval $$[a,b]$$. We want to show that
$$\inf_{a\leq x_{0}<\ldots Notice that $$|x^{n+1}-P(x)| = \prod_{j=0}^{n}|x-z_{j}|$$ for some $$z_{j} \in \mathbb{C}$$. Moreover by varying the polynomial $$P$$ we can make $$z_{j}$$ to be an abitrary complex numbers (if $$\mathcal{P}_{n}$$ are real polynomials then whenever $$z_{j}$$ is complex for some $$j$$ there will be its conjugate counterpart as well so we will have terms of the form $$|x-z_{j}|^{2}$$)

Next since $$|x-z_{j}|\geq |x-\Re z_{j}|$$ it is always better to choose $$z_{j}$$ to be real numbers. Thus we only need to verify that $$\inf_{a\leq x_{0}<\ldots Becuase of the symmetry in the right hand side without loss of generality we can assume that $$x_{0}\leq x_{1}\leq \ldots \leq x_{n}$$. It is clear that the right hand side is attainable for some $$x,x_{0},\ldots, x_{n}$$. Next, consider the function $$f(x)= \prod_{j=0}^{n}|x-x_{j}|$$ on $$[a,b]$$, and fix points $$x_{0}\leq \ldots \leq x_{n}$$. Let $$x_{\ell}$$ be the smallest point such that $$x_{\ell}>b$$. By moving $$x_{\ell}$$ towards the point $$b$$ the value of the function $$f(x)$$ decreasis no matter where $$x$$ is located in $$[a,b]$$. Similarlry if $$x_{q}$$ is the largest point such that $$x_{q} then by moving $$x_{q}$$ towards $$a$$ the value of $$f(x)$$ decreasis. This means that $$\inf_{x_{0},x_{1}, \ldots, x_{n}}\sup_{x \in [a,b]} \prod_{j=0}^{n}|x-x_{j}| = \inf_{a\leq x_{0}\leq x_{1}\leq \ldots\leq x_{n}\leq b}\sup_{x \in [a,b]} \prod_{j=0}^{n}|x-x_{j}|$$ and this proves the claim because it really does not matter whether we take infimum in the righ hand side over $$x_{0} or $$x_{0}\leq x_{1}...$$ by continuity. For example if you have a contiuous function $$g(x_{1}, x_{2})\geq 0$$ then one can easily see that $$\inf_{a\leq x_{0} and you can iterate this equality for the rest of the variables.

• there are typo s ... in your very first equality of the statement you want to prove, you've two $\inf$ s and then so on at each and every step ... – user521337 Oct 2 '18 at 2:12
• you say "beacuse of the symmetry of RHS, we can assume $x_0<x_1<...<x_n$ ..." is that really true or do you mean $x_0\le x_1\le...\le x_n$ ? – user521337 Oct 2 '18 at 2:17
• It does not matter we have $<$ or $\leq$ because of the $\inf$. – Paata Ivanishvili Oct 2 '18 at 2:28
• I have updated the answer. It should not play a role that the infimum is taken with respect to domain $x_{0}<x_{1}$ or $x_{0}\leq x_{1}$ because everything is continuous and if it happens that in the second case the infimum is attained (notice that by compactness it is always attained) for some $x^{*}_{0}$ and $x^{*}_{1}$ such that $x^{*}_{0}=x^{*}_{1}$ then by taking the infimum over the domain $x_{0}<x_{1}$ you can take sequence $x_{0}^{k}, x_{1}^{k}$ such that $x_{0}^{k}<x_{1}^{k}$ and $\lim_{k \to \infty} x_{j}^{k} \to x_{j}^{*}$ for each $j=0,1$ then by continuouty you get the result. – Paata Ivanishvili Oct 2 '18 at 13:52