Sturm root counting

Sign changes of the signed Euclidean remainder sequence count the distinct real roots of a polynomial in an interval. This gives an exact, finite test for real-rootedness, and the Hermite–Sylvester criterion gives a second one through a positive semidefinite matrix of power sums.

Results

For a real polynomial $p$, the Sturm sequence is the signed Euclidean remainder sequence of $p$ and $p'$; its sign variation at $x$ is the number of sign changes of its values at $x$, zero values omitted. For arbitrary $p$ we apply it to its radical (the squarefree part, with the repeated factors removed), and write $V_p(x)$ for the resulting variation.

Theorem (Sturm). Let $p\ne0$ and $a<b$ with $p(b)\ne0$. Then the number of distinct real roots of $p$ in the open interval $(a,b)$ is $V_p(a)-V_p(b)$.

Theorem (real-rootedness by sign changes). Let $p\ne0$ and $a<b$, and suppose every real root of $p$ lies in $(a,b)$. Then $p$ is real-rooted if and only if $V_p(a)-V_p(b)$ equals the degree of the squarefree part of $p$.

Hermite–Sylvester criterion [Syl53]. Let $f$ be a monic real polynomial of degree $n$ and $s_k=\sum_zz^k$ the power sums of its complex roots, counted with multiplicity. Put $H_f=(s_{i+j})_{0\le i,j\le n-1}$. Then $f$ is real-rooted if and only if $H_f$ is positive semidefinite.

Proposition (degree at most three). A real polynomial of degree at most three is real-rooted if and only if its cubic discriminant is nonnegative.

References

  1. [Syl53] James Joseph Sylvester. XVIII. On a theory of the syzygetic relations of two rational integral functions, comprising an application to the theory of Sturm's functions, and that of the greatest algebraical common measure. Philosophical Transactions of the Royal Society of London, (143), 407-548, 1853.
    BibTeX
    @article{Sylvester1853,
      author = {Sylvester, James Joseph},
      title = {{XVIII}. {O}n a theory of the syzygetic relations of two rational integral functions, comprising an application to the theory of {S}turm's functions, and that of the greatest algebraical common measure},
      year = {1853},
      journal = {Philosophical Transactions of the Royal Society of London},
      number = {143},
      pages = {407--548},
      doi = {10.1098/rstl.1853.0018},
      url = {https://doi.org/10.1098/rstl.1853.0018}
    }

Definitions

  • Signed remainder sequence

    Polynomial.signedRemainderSequencesource
    def signedRemainderSequence (p q : K[X]) : List K[X] :=
      if _hq : q = 0 then [p]
      else p :: signedRemainderSequence q (-(p % q))
    termination_by q.degree
    decreasing_by
      simpa only [degree_neg] using degree_mod_lt p _hq
  • Sign variations of the Sturm sequence

    RealRooted.sturmVariationssource
    def sturmVariations (p : ℝ[X]) (x : ℝ) : ℕ :=
      (sturmValues p x).signVariations
  • Squarefree part

    RealRooted.sturmSquarefreePartsource
    def sturmSquarefreePart (p : ℝ[X]) : ℝ[X] :=
      radical p
  • Sign variations of the squarefree Sturm sequence

    RealRooted.distinctSturmVariationssource
    def distinctSturmVariations (p : ℝ[X]) (x : ℝ) : ℕ :=
      sturmVariations (sturmSquarefreePart p) x
  • Number of distinct roots in an interval

    RealRooted.distinctRootCountIoosource
    def distinctRootCountIoo (p : ℝ[X]) (a b : ℝ) : ℕ :=
      (p.roots.toFinset.filter fun r ↦ a < r ∧ r < b).card
  • Hermite matrix of Newton power sums

    Polynomial.hermiteMatrixsource
    def hermiteMatrix (p : ℝ[X]) : Matrix (Fin p.natDegree) (Fin p.natDegree) ℝ :=
      fun i j => newtonSum p (i + j)

Theorems

  • Sturm's theorem

    RealRooted.distinctRootCountIoo_eq_distinctSturmVariations_subsource
    theorem distinctRootCountIoo_eq_distinctSturmVariations_sub
        {p : ℝ[X]} (hp : p ≠ 0) {a b : ℝ} (hab : a < b) (hb : ¬ p.IsRoot b) :
        distinctRootCountIoo p a b =
          distinctSturmVariations p a - distinctSturmVariations p b
  • A Sturm test for real-rootedness

    RealRooted.splits_iff_distinctSturmVariations_sub_eq_natDegreesource
    theorem splits_iff_distinctSturmVariations_sub_eq_natDegree
        {p : ℝ[X]} (hp : p ≠ 0) {a b : ℝ} (hab : a < b)
        (hbound : ∀ r : ℝ, p.IsRoot r → a < r ∧ r < b) :
        p.Splits ↔
          distinctSturmVariations p a - distinctSturmVariations p b =
            (sturmSquarefreePart p).natDegree
  • Hermite–Sylvester: real-rooted iff the Hermite matrix is PSDMain result

    Polynomial.splits_iff_hermiteMatrix_posSemidefsourcestatement on symmetricfunctions.com
    theorem splits_iff_hermiteMatrix_posSemidef {p : ℝ[X]} (hp : p.Monic) :
        p.Splits ↔ (hermiteMatrix p).PosSemidef
  • A real polynomial of degree at most three is real-rooted iff its discriminant is ≥ 0

    RealRooted.cubicDiscr_nonneg_iff_splits_of_natDegree_le_threesource
    theorem cubicDiscr_nonneg_iff_splits_of_natDegree_le_three
        {p : ℝ[X]} (hdeg : p.natDegree ≤ 3) :
        0 ≤ cubicDiscr p ↔ p.Splits

Lean source RealRooted/Challenges/Roots/Sturm.lean at revision d6670742. Formalized 2026-09-27.