Favard recurrences: real roots, interlacing and orthogonality

A monic three-term recurrence with positive subdiagonal coefficients produces real-rooted polynomials with consecutive interlacing, and orthogonal polynomials for a normalized linear functional.

Results

Let $P_0=1$, $P_1=x-\alpha_0$ and $$ P_{n+2}=(x-\alpha_{n+1})P_{n+1}-\beta_{n+1}P_n . $$

Theorem (interlacing). [Fav35] Let $\alpha_n,\beta_n$ be real and $\beta_{n+1}>0$ for all $n$. Then every $P_n$ is nonzero and real-rooted, and $P_n\ll P_{n+1}$.

Theorem (orthogonality). Let $R$ be an integral domain. The monic polynomials $P_n$ form a basis of $R[x]$. Let $L$ be the linear functional that extracts the coefficient of $P_0$ in this basis, and let $\langle p,q\rangle=L(pq)$.

References

See [Fav35] and the interlacing overview on symmetricfunctions.com.

  1. [Fav35] Jean Favard. Sur les polynômes de Tchebicheff. C. R. Acad. Sci. Paris, 200, 2052-2053, 1935.
    BibTeX
    @article{Favard1935,
      author = {Jean Favard},
      title = {Sur les polyn{\^o}mes de Tchebicheff},
      journal = {C. R. Acad. Sci. Paris},
      volume = {200},
      year = {1935},
      pages = {2052--2053}
    }

Definitions

  • Favard three-term recurrence

    RealRooted.SatisfiesFavardRecurrencesource
    def SatisfiesFavardRecurrence {R : Type*} [Ring R]
        (P : Nat → R[X]) (α β : Nat → R) : Prop :=
      P 0 = 1 ∧
      P 1 = X - C (α 0) ∧
      ∀ n : Nat,
        P (n + 2) =
          (X - C (α (n + 1))) * P (n + 1) - C (β (n + 1)) * P n
  • The normalized moment functional

    RealRooted.SatisfiesFavardRecurrence.functionalsource
    def functional (hrec : SatisfiesFavardRecurrence P α β) : R[X] →ₗ[R] R :=
      hrec.basis.coord 0
  • The pairing ⟨p, q⟩ = L(pq)

    RealRooted.SatisfiesFavardRecurrence.pairingsource
    def pairing (hrec : SatisfiesFavardRecurrence P α β) :
        LinearMap.BilinForm R R[X] :=
      (LinearMap.mul R R[X]).compr₂ hrec.functional

Theorems

  • For positive β, consecutive Favard polynomials interlace

    theorem favardInterlacing :
        ∀ {P : Nat → ℝ[X]} {α β : Nat → ℝ},
          SatisfiesFavardRecurrence P α β →
          (∀ n : Nat, 0 < β (n + 1)) →
          ∀ n : Nat, StrictInterl (P n) (P (n + 1))
  • For positive β, Favard polynomials are nonzero and real-rooted

    RealRooted.isRealRooted_of_favardsource
    theorem isRealRooted_of_favard
        {P : Nat → ℝ[X]} {α β : Nat → ℝ}
        (hrec : SatisfiesFavardRecurrence P α β)
        (hβ : ∀ n : Nat, 0 < β (n + 1)) :
        ∀ n : Nat, ((P n) ≠ 0 ∧ (P n).Splits)
  • The Favard polynomials are orthogonal for the pairing ⟨p, q⟩ = L(pq)Main result

    RealRooted.SatisfiesFavardRecurrence.pairing_iIsOrthosource
    theorem pairing_iIsOrtho
        (hrec : SatisfiesFavardRecurrence P α β) :
        hrec.pairing.iIsOrtho P
  • For positive β, the pairing is positive definite

    RealRooted.SatisfiesFavardRecurrence.pairing_posDefsource
    theorem pairing_posDef
        (hrec : SatisfiesFavardRecurrence P α β)
        (hβ : ∀ n, 0 < β (n + 1)) :
        hrec.pairing.toQuadraticMap.PosDef
  • The orthogonalizing functional is unique up to scaling

    RealRooted.SatisfiesFavardRecurrence.linearMap_eq_smul_functionalsource
    theorem linearMap_eq_smul_functional
        (hrec : SatisfiesFavardRecurrence P α β) (L : R[X] →ₗ[R] R)
        (hvanish : ∀ n, n ≠ 0 → L (P n) = 0) :
        L = L 1 • hrec.functional

Lean source RealRooted/Challenges/Interlacing/Favard.lean at revision d6670742. Formalized 2026-09-07.