Interlacing

Two real-rooted polynomials interlace if their roots alternate. Interlacing is the standard tool for proving that a sequence of polynomials is real-rooted. The convention below is used throughout the catalog; a page that departs from it says so.

Results

Let $f$ and $g$ be nonzero real-rooted polynomials with roots $s_1\le\dotsb\le s_k$ and $r_1\le\dotsb\le r_m$, listed with multiplicity. We say that $f$ interlaces $g$, and write $f\ll g$, if either

Thus $g$ has the largest root, and common and repeated roots are allowed. Some statements also allow $f=0$ or $g=0$; the zero polynomial then interlaces every polynomial and is interlaced by every polynomial. A sequence $p_0,p_1,\dotsc$ is a Sturm sequence if $p_{i+1}\ll p_i$ and $\deg p_{i+1}=\deg p_i-1$ for every $i$.

Theorem. If $f\ll g$, then $\deg g=\deg f$ or $\deg g=\deg f+1$. The first alternative of the definition holds exactly when $f\ll g$ and $\deg g=\deg f+1$.

Use

By Obreschkoff's theorem, $f\ll g$ or $g\ll f$ holds exactly when every real linear combination of $f$ and $g$ is real-rooted. Interlacing sequences arise from three-term recurrences and from principal submatrices, interlacing is preserved by differential operators with real-rooted symbol, and families with a common interleaver have real-rooted sums.

References

[Fis06]. See also interlacing on symmetricfunctions.com.

  1. [Fis06] Steve Fisk. Polynomials, roots, and interlacing. arXiv e-prints, 2006.
    BibTeX
    @article{Fisk2006x,
      Author = {Steve Fisk},
      Title = {Polynomials, roots, and interlacing},
      Year = {2006},
      Eprint = {arXiv:math/0612833},
      journal = {arXiv e-prints}
    }

Definitions

  • Interlacing f ≪ g of nonzero real-rooted polynomials

    RealRooted.StrictInterlsource
    def StrictInterl (f g : ℝ[X]) : Prop := (f ≠ 0 ∧ f.Splits) ∧ (g ≠ 0 ∧ g.Splits) ∧
      ∃ (ss rs : List ℝ),
        ss.Pairwise (· ≤ ·) ∧ rs.Pairwise (· ≤ ·) ∧
        (↑ss : Multiset ℝ) = f.roots ∧ (↑rs : Multiset ℝ) = g.roots ∧
        ((ss.length + 1 = rs.length ∧ ListInterlaces ss rs) ∨
          (ss.length = rs.length ∧ ListAlternates ss rs))
  • Interlacing, allowing zero polynomials

    RealRooted.Interlsource
    def Interl (f g : ℝ[X]) : Prop :=
      f = 0 ∨ g = 0 ∨ StrictInterl f g
  • Interlacing with degrees differing by one

    RealRooted.Interlacessource
    def Interlaces (g f : ℝ[X]) : Prop := (f ≠ 0 ∧ f.Splits) ∧ (g ≠ 0 ∧ g.Splits) ∧
      g.natDegree + 1 = f.natDegree ∧
      ∃ (rs ss : List ℝ),
        rs.Pairwise (· ≤ ·) ∧ ss.Pairwise (· ≤ ·) ∧
        (↑rs : Multiset ℝ) = f.roots ∧
        (↑ss : Multiset ℝ) = g.roots ∧
        ListInterlaces ss rs
  • Sturm sequence

    RealRooted.IsSturmSeqsource
    def IsSturmSeq : List ℝ[X] → Prop
      | [] => True
      | [_] => True
      | p :: q :: rest => Interlaces q p ∧ IsSturmSeq (q :: rest)

Theorems

  • Interlacing with a degree gap of oneMain result

    RealRooted.Interlaces.iff_strictInterl_and_natDegreesource
    theorem Interlaces.iff_strictInterl_and_natDegree {f g : ℝ[X]} :
        Interlaces f g ↔ StrictInterl f g ∧ f.natDegree + 1 = g.natDegree
  • Interlacing polynomials differ in degree by at most one

    RealRooted.StrictInterl.natDegree_eq_or_eq_succsource
    theorem StrictInterl.natDegree_eq_or_eq_succ {f g : ℝ[X]} (h : StrictInterl f g) :
        g.natDegree = f.natDegree ∨ g.natDegree = f.natDegree + 1
  • Interlacing implies interlacing in the sense allowing zero polynomials

    RealRooted.StrictInterl.toInterlsource
    lemma StrictInterl.toInterl {f g : ℝ[X]} (h : StrictInterl f g) : Interl f g

Lean source RealRooted/Challenges/Interlacing/Interlacing.lean at revision d6670742. Formalized 2026-10-05.