(T)Chebyshev Polynomials, again (II)

Relevant wiki.- Chebyshev Polynomials

Theorem.-

If $p$ is a monic polynomial of degree $n \ge 1$ in $[-1, 1]$ with coefficients in $\mathbb{R}$ , then $|| p ||_{\infty} \ge \frac{1}{2^{n - 1}} = || \frac{1}{2^{n - 1}} \cdot T_n ||_{\infty}$ in [-1, 1], whith $T_n$ being Chebyshev polynomial of first kind of degree n and $|| f ||_{\infty} = \text{ supremum } \{|f(x)|; x \in [-1, 1]\}$ .

---

Therefore, $\displaystyle \min_{p \in P_6 [-1, 1]} || p ||_{\infty} = \frac{1}{2^5} = \frac{1}{32} = 0.03125$ and it's got with the polynomial $\frac{1}{2^5} \cdot T_6 (t) = \frac{1}{32}\cdot(32t^6 - 48t^4 + 18t^2 - 1)$

---

$\large \boxed{\text{Chebyshev polynomials}}$

Chebyshev polynomials (of first kind) are defined by recurrence: $\begin{cases} T_{0} (t) = 1 \\ T_{1} (t) = t \\ T_{n + 1} (t) = 2tT_{n} (t) - T_{n - 1} (t), \space \forall n \ge 1 \end{cases}$

First Examples.-

$\begin{aligned} T_0(t) &= 1 \\ T_1(t) &= t \\ T_2(t) &= 2t^2 - 1 \\ T_3(t) &= 4t^3 - 3t \\ T_4(t) &= 8t^4 - 8t^2 + 1 \\ T_5(t) &= 16t^5 - 20t^3 + 5t \\ T_6(t) &= 32t^6 - 48t^4 + 18t^2 - 1. \\ \end{aligned}$

---

Observations.-

$\boxed{1.-}$ The recurrent formula uniquely determines these polynomials, i.e, these polynomials are well-defined and are unique defined by this recurrence.

$\boxed{2.-}$ $T_n \text{ is a polynomial of degree n (Prove it by induction)}$ .

$\boxed{3.-}$ The coefficient of $t^n$ in $T_n$ is $2^{n - 1}, \space \forall n \ge 1$ . Prove it by induction too.

---

Proposition.-

$T_n (t) = \cos \left(n \cos^{-1} (t) \right), \space \forall t \in [-1,1]$ , where $\cos^{-1} : [-1, 1] \to [0, \pi]$ is a continuous determitation of $\cos^{-1}$ .

---

Proof.-

Let's define $f_n (t) = \cos \left(n \cos^{-1} (t) \right)$ , where $(f_n)_{n = 0}^\infty$ satisfies: $f_0 (t) = 1, \quad f_1 (t) = t$ Now, we are going to use $\cos (n + 1) \theta = \cos (n\theta) \cos \theta - \sin \theta \sin (n\theta) \\\cos (n - 1) \theta = \cos (n\theta) \cos \theta + \sin \theta \sin (n\theta)$ Therefore, $\cos (n + 1) \theta + \cos (n - 1) \theta = 2\cos (n\theta) \cos \theta \Rightarrow$ $\cos (n + 1) \theta = 2\cos (n\theta) \cos \theta - \cos (n - 1) \theta, \space \forall \theta \in [0, \pi]$ Let's call, $\cos \theta = t \iff \theta = \cos^{-1} (t), \space \forall \theta \in [0, \pi], \space \forall t \in [-1, 1] \Rightarrow$ $\cos \left( (n +1) \cos^{-1} (t) \right) = 2t \cos \left(n \cos^{-1} (t) )\right) - \cos\left((n - 1) \cos^{-1} (t)\right) \Rightarrow$ $f_{n + 1} (t) = 2tf_n (t) - f_{n-1}(t), \space \forall t \in [-1, 1] \Rightarrow f_n = T_n , n = 0, 1, ...$ $\boxed{\text{q.e.d}}$

---

Proposition.-

If $(T_n)_{ n = 0}^\infty$ is the sequence of Chebyshev polynomials (of first kind), then:

$\boxed{1.-}$ $|T_n (t)| \leq 1, \space \forall t \in [-1, 1]$

$\boxed{2.-}$ $T_n \left( \cos (\frac{j\pi}{n}) \right) = (-1)^j, \space \forall \space 0 \leq j \leq n$

$\boxed{3.-}$ $T_n \left( \cos (\frac{(2j - 1)\pi}{2n}) \right) = 0, \space \forall \space 1 \leq j \leq n$

---

Proof.-

$\boxed{1.-}$ Trivial due to previous proposition.

$\boxed{2.-}$ $T_n \left( \cos (\frac{j\pi}{n}) \right) = \cos \left(n \cdot (\frac{j\pi}{n}) \right) = (-1)^j,\space \forall \space 0 \leq j \leq n$

$\boxed{3.-}$ $T_n \left( \cos (\frac{(2j - 1)\pi}{2n}) \right) = \cos \left( n \cdot (\frac{(2j - 1)\pi}{2n}) \right) = \cos \left( \frac{(2j - 1)\pi}{n} \right) = 0, \space \forall \space 1 \leq j \leq n$

$\boxed{\text{q.e.d}}$

---

Theorem.-

If $p$ is a monic polynomial of degree $n \ge 1$ in $[-1, 1]$ with coefficients in $\mathbb{R}$ , then $|| p ||_{\infty} \ge \frac{1}{2^{n - 1}} = || \frac{1}{2^{n - 1}} \cdot T_n ||_{\infty}$ in [-1, 1], (whith $T_n$ being Chebyshev polynomial of first kind of degree n and $|| f ||_{\infty} = \text{ supremum } \{|f(x)|; x \in [-1, 1]\}$ .)

---

Proof.- (by contradiction or reductio ad absurdum)

I'm going to use the two previous propositions and this Bolzano's theorem

Let's suppose that there exists a monic polynomial $p$ of degree $n \ge 1$ such that $|| p ||_\infty < \frac{1}{2^{n - 1}} \iff |p(t)| < \frac{1}{2^{n - 1}}, \space \forall t \in [-1, 1]$ Take $t_i = \cos \frac{i\pi}{n}, \space i = 0, 1, ... , n$ and remember that $T_n (t_i) = (-1)^i, \space i = 0, 1, ... , n$ . Let's call $\frac{1}{2^{n - 1}} \cdot T_n (t) = q(t)$ which it's a monic polynomial of degree n. Then, $(-1)^i \cdot p(t_i) \leq |p (t_i)| < \frac{1}{2^{n - 1}} = \frac{1}{2^{n - 1}} \cdot T_n (t_i) \cdot (- 1)^i = (-1)^i \cdot q (t_i) \Rightarrow$ $(-1)^i \left( q (t_i) - p (t_i) \right) > 0, \space \forall \space 0 \leq i \leq n \Rightarrow$ $q(t) - p(t)$ changes sign at least n times, i.e, $q(t) - p(t)$ has at least n zeros (due to Bolzano theorem) but $\delta (q - p) = \text{ degree ((q(t) - p(t))) } \leq n - 1$ . (Contradiction due to fundamental theorem of Algebra) $\square$ .

$\boxed{\text{q.e.d}}$