Chebyshev level polynomials

If $f'$ has simple real roots, a level $f-s$ is real-rooted exactly when $f-s$ is nonnegative at the local maxima of $f$ and nonpositive at its local minima. All critical values of the Chebyshev polynomial $T_n$ are $\pm1$, so $T_n-h$ is real-rooted for every $n$ exactly when $|h|\le1$, and an affine change of variable turns these levels into Pólya frequency polynomials.

Results

Theorem (critical-value criterion). Let $f\in\mathbb R[x]$ have positive leading coefficient and degree at least $2$, and let $f'$ be real-rooted with simple roots. Then $f-s$ is real-rooted if and only if $$ f''(r)\,\bigl(f(r)-s\bigr)\le0\quad\text{for every root }r\text{ of }f' . $$ If $f'$ is real-rooted and all these inequalities are strict, then $f-s$ is real-rooted with simple roots.

Proposition (intermediate levels). Let $f$ have positive leading coefficient and degree at least $1$, let $a\le s\le b$, and let $f-a$ and $f-b$ be real-rooted. Then $f'\ll f-s$, and $f-s$ is real-rooted. If all roots of $f-a$ and of $f-b$ lie in $[L,U]$, then so do all roots of $f-s$.

Theorem (Chebyshev levels). Let $T_n$ be the Chebyshev polynomial of the first kind and $n\ge1$. If $|h|\le1$, then $T_n-h$ is real-rooted with all roots in $[-1,1]$; if $|h|<1$, its roots are simple and lie in $(-1,1)$. For fixed $h$, the polynomial $T_n-h$ is real-rooted for all $n\ge1$ if and only if $|h|\le1$. For $d\ge2$ and $c>1$, the polynomial $T_d+c$ is not real-rooted.

Theorem (affine levels). For real $\alpha,\lambda,h$ put $$ L_n(x)=\alpha\bigl(T_n(1+\lambda x)-h\bigr). $$ Then $L_{n+3}=(3+2\lambda x)(L_{n+2}-L_{n+1})+L_n$ for all $n\ge0$. For $\alpha,\lambda>0$, $|h|\le1$ and $n\ge1$, the polynomial $L_n$ has degree $n$, leading coefficient $\alpha2^{n-1}\lambda^n$ and is a Pólya frequency polynomial with all roots in $[-2/\lambda,0]$; if $|h|<1$, its roots are simple and lie in $(-2/\lambda,0)$. All $L_n$ with $n\ge1$ are Pólya frequency polynomials if and only if $|h|\le1$.

References

For Chebyshev polynomials, see [Sze39].

  1. [Sze39] G. Szegő. Orthogonal Polynomials. Colloquium Publications, American Mathematical Society, 1939.
    BibTeX
    @book{Szego1939,
      author = {Szegő, G.},
      title = {Orthogonal {P}olynomials},
      year = {1939},
      series = {Colloquium Publications},
      publisher = {American Mathematical Society},
      isbn = {9781470431716},
      doi = {10.1090/coll/023},
      url = {https://doi.org/10.1090/coll/023}
    }

Definitions

  • The affine level family α (T_n(1 + λ X) - h)

    RealRooted.Chebyshev.affineLevelsource
    def affineLevel (α lam h : ℝ) (n : ℕ) : ℝ[X] :=
      C α * ((T ℝ n - C h).comp (1 + C lam * X))

Theorems

  • f' interlaces f - s whenever s lies between two real-rooted levelsRealRooted original

    RealRooted.derivative_interlaces_sub_C_of_mem_Iccsource
    theorem derivative_interlaces_sub_C_of_mem_Icc {f : ℝ[X]} {a b s : ℝ}
        (hf_pos : HasPosLeadingCoeff f) (hdeg : f.natDegree ≠ 0)
        (hab : a ≤ b) (hs : s ∈ Icc a b)
        (ha_splits : (f - C a).Splits) (hb_splits : (f - C b).Splits) :
        Interlaces f.derivative (f - C s)
  • Critical-value criterion for f - s to be real-rootedMain resultRealRooted original

    RealRooted.splits_sub_C_iff_eval_secondDerivative_nonpossource
    theorem splits_sub_C_iff_eval_secondDerivative_nonpos {f : ℝ[X]}
        (hf_pos : HasPosLeadingCoeff f) (hdeg : 2 ≤ f.natDegree)
        (hder_splits : f.derivative.Splits) (hder_nodup : f.derivative.roots.Nodup)
        (s : ℝ) :
        (f - C s).Splits ↔
          ∀ r, f.derivative.IsRoot r →
            f.derivative.derivative.eval r * (f.eval r - s) ≤ 0
  • T_n - h is real-rooted for |h| ≤ 1RealRooted original

    RealRooted.Chebyshev.T_sub_C_splitssource
    theorem T_sub_C_splits {n : ℕ} (hn : n ≠ 0) {h : ℝ} (hh : h ∈ Icc (-1 : ℝ) 1) :
        (T ℝ n - C h).Splits
  • For |h| < 1 the roots of T_n - h are simple and lie in (-1, 1)RealRooted original

    RealRooted.Chebyshev.T_sub_C_splits_simple_roots_mem_Ioosource
    theorem T_sub_C_splits_simple_roots_mem_Ioo {n : ℕ} (hn : n ≠ 0) {h : ℝ}
        (hh : h ∈ Ioo (-1 : ℝ) 1) :
        (T ℝ n - C h).Splits ∧ HasSimpleRoots (T ℝ n - C h) ∧
          ∀ r ∈ (T ℝ n - C h).roots, r ∈ Ioo (-1 : ℝ) 1
  • All levels T_n - h are real-rooted exactly when |h| ≤ 1RealRooted original

    RealRooted.Chebyshev.forall_pos_T_sub_C_splits_iff_abs_le_onesource
    theorem forall_pos_T_sub_C_splits_iff_abs_le_one (h : ℝ) :
        (∀ n : ℕ, n ≠ 0 → (T ℝ n - C h).Splits) ↔ |h| ≤ 1
  • T_d + c is not real-rooted for d ≥ 2 and c > 1RealRooted original

    RealRooted.Chebyshev.not_splits_T_add_C_of_one_ltsource
    theorem not_splits_T_add_C_of_one_lt {d : ℕ} {c : ℝ}
        (hd : 2 ≤ d) (hc : 1 < c) :
        ¬(Polynomial.Chebyshev.T ℝ d + C c).Splits
  • The affine level family satisfies an order-three recurrenceRealRooted original

    RealRooted.Chebyshev.affineLevel_add_threesource
    theorem affineLevel_add_three (α lam h : ℝ) (n : ℕ) :
        affineLevel α lam h (n + 3) =
          (C 3 + C (2 * lam) * X) * affineLevel α lam h (n + 2) -
            (C 3 + C (2 * lam) * X) * affineLevel α lam h (n + 1) +
              affineLevel α lam h n
  • For α, λ > 0 and |h| ≤ 1 the affine level polynomials are PFRealRooted original

    RealRooted.Chebyshev.affineLevel_isPFPolynomialsource
    theorem affineLevel_isPFPolynomial {α lam h : ℝ} {n : ℕ}
        (hn : n ≠ 0) (hα : 0 < α) (hlam : 0 < lam)
        (hh : h ∈ Icc (-1 : ℝ) 1) :
        IsPFPolynomial (affineLevel α lam h n)
  • For |h| < 1 the roots are simple and lie in (-2/λ, 0)RealRooted original

    RealRooted.Chebyshev.affineLevel_splits_simple_roots_mem_Ioosource
    theorem affineLevel_splits_simple_roots_mem_Ioo {α lam h : ℝ} {n : ℕ}
        (hn : n ≠ 0) (hα : 0 < α) (hlam : 0 < lam)
        (hh : h ∈ Ioo (-1 : ℝ) 1) :
        (affineLevel α lam h n).Splits ∧ HasSimpleRoots (affineLevel α lam h n) ∧
          ∀ r ∈ (affineLevel α lam h n).roots, r ∈ Ioo (-2 / lam) 0
  • All affine levels are PF exactly when |h| ≤ 1RealRooted original

    RealRooted.Chebyshev.forall_pos_affineLevel_isPFPolynomial_iff_abs_le_onesource
    theorem forall_pos_affineLevel_isPFPolynomial_iff_abs_le_one
        (α lam h : ℝ) (hα : 0 < α) (hlam : 0 < lam) :
        (∀ n : ℕ, n ≠ 0 → IsPFPolynomial (affineLevel α lam h n)) ↔ |h| ≤ 1

Lean source RealRooted/Challenges/Roots/ChebyshevLevels.lean at revision d6670742. Formalized 2026-11-01.