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)$.
- The family is orthogonal, and $\langle P_n,P_n\rangle=\beta_1\cdots\beta_n$.
- If a linear functional $L'$ satisfies $L'(P_n)=0$ for all $n\ne0$, then $L'=L'(1)\cdot L$. In particular, $L$ is unique up to scaling.
- Let $R$ be an ordered ring and $\beta_{n+1}>0$ for all $n$. Then the pairing is positive definite: $\langle p,p\rangle>0$ for all $p\ne0$.
References
See [Fav35] and the interlacing overview on symmetricfunctions.com.
- [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
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
def functional (hrec : SatisfiesFavardRecurrence P α β) : R[X] →ₗ[R] R :=
hrec.basis.coord 0
The pairing ⟨p, q⟩ = L(pq)
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
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
theorem pairing_iIsOrtho
(hrec : SatisfiesFavardRecurrence P α β) :
hrec.pairing.iIsOrtho P
For positive β, the pairing is positive definite
theorem pairing_posDef
(hrec : SatisfiesFavardRecurrence P α β)
(hβ : ∀ n, 0 < β (n + 1)) :
hrec.pairing.toQuadraticMap.PosDef
The orthogonalizing functional is unique up to scaling
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.