Descartes' rule of signs

The number of positive roots of a real polynomial, counted with multiplicity, is at most the number of sign changes in its coefficients, and the difference is even.

Results

Theorem (Descartes' rule of signs). For a real polynomial $p$, let $V(p)$ be the number of sign changes in the sequence of its coefficients, ignoring zeros. Then the number of positive roots of $p$ is at most $V(p)$, and $V(p)$ minus this number is even. Applying this to $p(-x)$ gives the same statement for negative roots.

Theorem (Budan–Fourier). Let $p\ne0$ be a real polynomial of degree $n$ and let $V(x)$ be the number of sign changes in $p(x),p'(x),\dotsc,p^{(n)}(x)$, ignoring zeros. For $a<b$, the number of roots of $p$ in $(a,b]$, counted with multiplicity, is at most $V(a)-V(b)$, and $V(a)-V(b)$ minus this number is even.

Use

Taking $a=0$ and $b$ large recovers Descartes' rule.

References

R. Descartes, La Géométrie, 1637. F. D. Budan, Nouvelle méthode pour la résolution des équations numériques, 1807; J. Fourier, Analyse des équations déterminées, 1831. See also Descartes' rule of signs on symmetricfunctions.com.

Definitions

  • Number of positive roots

    Polynomial.positiveRootCountsource
    noncomputable def positiveRootCount (p : ℝ[X]) : ℕ :=
      p.roots.countP (0 < ·)
  • Number of negative roots

    Polynomial.negativeRootCountsource
    noncomputable def negativeRootCount (p : ℝ[X]) : ℕ :=
      p.roots.countP (· < 0)

Theorems

  • Descartes' rule of signsMain result

    Polynomial.descartes_rule_of_signssourcestatement on symmetricfunctions.com
    theorem descartes_rule_of_signs (p : ℝ[X]) :
        p.positiveRootCount ≤ p.signVariations ∧
          Even (p.signVariations - p.positiveRootCount)
  • Descartes' rule of signs for negative roots

    Polynomial.descartes_rule_of_signs_negativesource
    theorem descartes_rule_of_signs_negative (p : ℝ[X]) :
        p.negativeRootCount ≤ (p.comp (-X)).signVariations ∧
          Even ((p.comp (-X)).signVariations - p.negativeRootCount)
  • Budan–Fourier theorem

    Polynomial.budan_fouriersource
    theorem budan_fourier {p : ℝ[X]} (hp : p ≠ 0) {a b : ℝ} (hab : a < b) :
        (p.roots.filter fun r => a < r ∧ r ≤ b).card ≤
            List.signVariations ((List.range (p.natDegree + 1)).map
              fun i => (derivative^[i] p).eval a) -
            List.signVariations ((List.range (p.natDegree + 1)).map
              fun i => (derivative^[i] p).eval b) ∧
          Even (List.signVariations ((List.range (p.natDegree + 1)).map
              fun i => (derivative^[i] p).eval a) -
            List.signVariations ((List.range (p.natDegree + 1)).map
              fun i => (derivative^[i] p).eval b) -
            (p.roots.filter fun r => a < r ∧ r ≤ b).card)

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