Relation between two extremal properties of Chebyshev polynomials

Question

The Chebyshev polynomials $T_n$ have the following “minimal ∞-norm” property, also known as “Chebyshev's theorem”:

(A) Let $P$ be an $n$-the degree polynomial with leading coefficient $2^{n-1}$. Then $$ \max_{x \in [-1,1]} |P(x)| \ge 1 = \max_{x \in [-1,1]} |T_n(x)| \, . $$ $|T_n(x)|$ attains that maximum exactly at the point $x_k = \cos(k \pi/n)$, $0 \le k \le n$.

In a recent answer I needed (and proved) the following lemma:

(B) Let $ 1 \ge x_0 > x_1 > \ldots > x_n \ge -1 $ be $(n+1)$ distinct real numbers and $P$ be an $n$-th degree polynomial with leading coefficient $K$ such that $P(x_k) = (-1)^k$ for $0 \le k \le n$. Then $K \ge 2^{n-1}$.

$K = 2^{n-1}$ holds exactly if $P = T_n$ and $x_k = \cos(k \pi/n)$, $0 \le k \le n$.

Proof (sketch): $f(x) = P(x) - T_n(x)$ has the property that $f(x_k) \ge 0$ for even $k$, and $f(x_k) \le 0$ for odd $k$. By repeated application of the mean-value theorem one concludes that $f^{(n)}(c) \ge 0$ for some $c \in (-1, 1)$, so that $$ 0 \le f^{(n)}(c) = P^{(n)}(c) - T_n^{(n)}(c) = n! (K - 2^{n-1}) \, . $$ Strict inequality holds unless $T_n(x_k) = (-1)^k$ for all $k$.

The proof of Chebyshev's theorem is quite similar: One observes that $P(x) - T_n(x)$ has alternating signs at the points $\cos(k \pi /n)$ and then applies the intermediate-value theorem.

So we have two “extremal properties” of the Chebyshev polynomials whose proofs look similar. Therefore my question is:

Is there a relationship between Lemma B and Chebyshev's theorem? In particular, can (B) be deduced from (A)?

Answer 1

This is not an answer but a comment with a little R script that may be useful to the OP:

It is my impression that (B) does not follow from (A). However, (A) provides an upper bound for the principal coefficients of the polynomials described in the OP.

The Lemma proved by Martin states that if $K_n$ is the principal coefficient of the polynomial $P_n$ of degree at most $n$ such that $P_n(x_j)=(-1)^j$, $0\leq j\leq n$, where $-1\leq x_0<\ldots <x_n\leq 1$, then $$2^{n-1}\leq K_n$$

On the other hand, to follows from Chebychev's bound on the uniform norm of all monic polynomials $p(x)=a_0+a_1x+\ldots+x^n$ over $[-1,1]$ that for any $P(x)=b_0+b_1x+\ldots + b_nx^n$, $b_n\neq0$, $$\|P\|_\infty\geq |b_n|2^{1-n}$$

Thus, $\|P_n\|_\infty\geq1$ and $$2^{n-1}\leq K_n\leq \|P_n\|_\infty 2^{n-1}$$

Here is a little R script that estimates the coefficients $K_n$ for uniform partitions of $[-1,1]$.

### Lagrange interpolation coefficients
library(polynom)
library(dplyr)
N <- 21
an <- vector(mode = 'numeric', length = N-2)
for(i in 3:N){
  x <- seq(-1,1, length.out = i)
  y <- (-1)^(0:(length(x)-1))
  print(p<- polynom::poly.calc(x,y))
  an[i-2] <- p[[i]]
}

data.frame( n.node = 3:N, degree = 2:(N-1), prin.coeff = an) %>%
  mutate( lowbound = 2^(degree-1),
    ratio = abs(prin.coeff)/lowbound
  )

This yields output

     n.nodes degree    prin.coeff low.bound   abs.ratio
1       3      2    2.000000e+00        2    1.000000
2       4      3   -4.500000e+00        4    1.125000
3       5      4    1.066667e+01        8    1.333333
4       6      5   -2.604167e+01       16    1.627604
5       7      6    6.480000e+01       32    2.025000
6       8      7   -1.634014e+02       64    2.553147
7       9      8    4.161016e+02      128    3.250794
8      10      9   -1.067627e+03      256    4.170418
9      11     10    2.755732e+03      512    5.382289
10     12     11   -7.147659e+03     1024    6.980136
11     13     12    1.861393e+04     2048    9.088831
12     14     13   -4.863885e+04     4096   11.874718
13     15     14    1.274630e+05     8192   15.559449
14     16     15   -3.348646e+05    16384   20.438515
15     17     16    8.816580e+05    32768   26.906065
16     18     17   -2.325751e+06    65536   35.488138
17     19     18    6.145597e+06   131072   46.887183
18     20     19   -1.626387e+07   262144   62.041727
19     21     20    4.309980e+07   524288   82.206352

with a little more effort one may add code to estimate $\|P_n\|_\infty$ and produce the upper bounds.