Continuity of roots

Real-rootedness of monic polynomials of fixed degree is preserved under coefficientwise limits, and it propagates along continuous families of squarefree polynomials. Root counts are constant across intervals without roots. These facts are the basic tools for deformation and limit arguments.

Results

We write $\lVert p\rVert_1$ for the sum of the absolute values of the coefficients of $p$. Roots are counted with multiplicity.

Theorem (closure). Let $f$ be monic. If for every $\varepsilon>0$ there is a monic real-rooted polynomial $g$ of degree $\deg f$ with all coefficients within $\varepsilon$ of those of $f$, then $f$ is real-rooted. In particular, a coefficientwise limit of monic real-rooted polynomials of degree $\deg f$ is real-rooted.

Theorem (continuous families). Let $P_t$ be real polynomials of constant degree $d$ for $t$ in a preconnected set $S$, with each coefficient continuous in $t$ and each $P_t$ squarefree (equivalently, separable). If $P_a$ is real-rooted for some $a\in S$, then $P_b$ is real-rooted for all $b\in S$.

Theorem (nearby roots). Let $f,g$ be monic of the same degree $m$, let $g$ be real-rooted, and let all coefficients of $g$ be within $\varepsilon>0$ of those of $f$. For every complex root $z$ of $f$ there is a complex root $w$ of $g$ with $$|z-w|<\bigl((m+1)\varepsilon\bigr)^{1/m}\max(|z|,1).$$

Theorem (pencils). Let $f,g$ be monic of the same degree $m$, let $t>0$ and $\varepsilon>0$ with $(t+1)^{-1}(\lVert f\rVert_1+\lVert g\rVert_1)<\varepsilon$, and let $tf+g$ be nonzero and real-rooted. For every real root $a$ of $f$ there is a real root $b$ of $tf+g$, and for every complex root $z$ of $f$ there is a complex root $w$ of $tf+g$, within $((m+1)\varepsilon)^{1/m}\max(|a|,1)$, respectively $((m+1)\varepsilon)^{1/m}\max(|z|,1)$. Such $t>0$ exists for every $\varepsilon>0$.

Theorem (degree-increasing perturbation). Let $f$ be real-rooted, $\deg f<\deg g$ and $\rho>0$. There is $\delta>0$ such that for all $0<\mu<\delta$ with $f+\mu g$ real-rooted, every root $a$ of $f$ of multiplicity $k$ has at least $k$ roots of $f+\mu g$ within distance $\rho$ of $a$.

Theorem (root counts). Let $a\le b$ and let $p$ have no root in $[a,b]$. Then $p$ has equally many roots $\le a$ and $\le b$, equally many roots $>a$ and $>b$, and no root in $(a,b]$. If $f,g$ both have no root in $[a,b]$, then the number of roots $\le t$ of $f$ minus that of $g$, and likewise for roots $>t$, agree at $t=a$ and $t=b$. If $f,g$ have no root in $(a,b)$, the difference of the numbers of roots $>t$ is the same for all $t\in(a,b)$, and so is its parity.

Lemmas. For real $\mu\ne0$, the polynomials $f+\mu g$ and $g+\mu^{-1}f$ have the same roots. If $h\ne0$ is real-rooted and $f(-u^2)=u^n\,h\bigl((1-u^2)/u\bigr)$ for all nonzero $u\in\mathbb C$, then $f$ is real-rooted. If $t\mapsto P_t(a)$ is continuous and nonvanishing on $[t_0,t_1]$, then $P_{t_0}(a)\,P_{t_1}(a)>0$.

References

For the continuity of zeros, see [RS02].

  1. [RS02] Q. I. Rahman & G. Schmeisser. Analytic Theory of Polynomials. London Mathematical Society Monographs, Oxford University Press, 2002.
    BibTeX
    @book{RahmanSchmeisser2002,
      author    = {Rahman, Q. I. and Schmeisser, G.},
      title     = {Analytic Theory of Polynomials},
      publisher = {Oxford University Press},
      series    = {London Mathematical Society Monographs},
      year      = {2002}
    }

Theorems

  • Transport along a preconnected parameter set

    RealRooted.splits_of_isPreconnectedsource
    theorem splits_of_isPreconnected {T : Type*} [TopologicalSpace T]
        {s : Set T} (hs : IsPreconnected s) {P : T → ℝ[X]} {d : ℕ}
        (hcoeff : ∀ k : ℕ, ContinuousOn (fun t => (P t).coeff k) s)
        (hdeg : ∀ t ∈ s, (P t).natDegree = d) (hsqfree : ∀ t ∈ s, Squarefree (P t))
        {a b : T} (ha : a ∈ s) (hb : b ∈ s) (hsplits : (P a).Splits) :
        (P b).Splits
  • Transport along a squarefree path

    RealRooted.splits_of_pathsource
    theorem splits_of_path (P : ℝ → ℝ[X]) {d : ℕ}
        (hcoeff : ∀ k : ℕ, ContinuousOn (fun t => (P t).coeff k) (Icc 0 1))
        (hdeg : ∀ t ∈ Icc (0 : ℝ) 1, (P t).natDegree = d)
        (hsqfree : ∀ t ∈ Icc (0 : ℝ) 1, Squarefree (P t)) (h0 : (P 0).Splits) :
        (P 1).Splits
  • Transport from fibrewise separability

    RealRooted.splits_of_path_of_separablesource
    theorem splits_of_path_of_separable (P : ℝ → ℝ[X]) {d : ℕ}
        (hcoeff : ∀ k : ℕ, ContinuousOn (fun t => (P t).coeff k) (Icc 0 1))
        (hdeg : ∀ t ∈ Icc (0 : ℝ) 1, (P t).natDegree = d)
        (hsep : ∀ t ∈ Icc (0 : ℝ) 1, (P t).Separable) (h0 : (P 0).Splits) :
        (P 1).Splits
  • Closure under coefficient approximation

    RealRooted.splits_of_monic_of_coeff_approxsource
    theorem splits_of_monic_of_coeff_approx {f : ℝ[X]} (hf : f.Monic)
        (happrox : ∀ ε : ℝ, 0 < ε → ∃ g : ℝ[X],
          g.Monic ∧ g.natDegree = f.natDegree ∧ g.Splits ∧
            ∀ i : ℕ, ‖g.coeff i - f.coeff i‖ < ε) :
        f.Splits
  • Closure under coefficientwise limitsMain result

    RealRooted.splits_of_monic_of_coeff_tendstosource
    theorem splits_of_monic_of_coeff_tendsto {f : ℝ[X]} (hf : f.Monic)
        {g : ℕ → ℝ[X]} (hg_monic : ∀ M, (g M).Monic)
        (hg_degree : ∀ M, (g M).natDegree = f.natDegree)
        (hg_splits : ∀ M, (g M).Splits)
        (hcoeff : ∀ i, Filter.Tendsto (fun M => (g M).coeff i) Filter.atTop
          (nhds (f.coeff i))) :
        f.Splits
  • A nearby root under coefficient control

    RealRooted.exists_aroot_near_of_monic_of_coeff_closesource
    theorem exists_aroot_near_of_monic_of_coeff_close
        {f g : ℝ[X]} {z : ℂ} {ε : ℝ}
        (hε : 0 < ε)
        (hz : f.aeval z = 0)
        (hf_monic : f.Monic) (hg_monic : g.Monic)
        (hdeg : g.natDegree = f.natDegree)
        (hcoeff : ∀ i : ℕ, ‖g.coeff i - f.coeff i‖ < ε)
        (hg_rr_splits : g.Splits) :
        ∃ w : ℂ, w ∈ g.aroots ℂ ∧
          ‖z - w‖ < ((f.natDegree + 1) * ε) ^ ((f.natDegree : ℝ)⁻¹) * max ‖z‖ 1
  • A nearby real root in a left pencil

    RealRooted.exists_real_root_near_in_left_familysource
    theorem exists_real_root_near_in_left_family
        {f g : ℝ[X]} {a t ε : ℝ}
        (ha : f.IsRoot a)
        (hf_monic : f.Monic) (hg_monic : g.Monic)
        (hdeg : g.natDegree = f.natDegree)
        (ht : 0 < t)
        (hcoeff_bound : (t + 1)⁻¹ * (coeffSumRange f + coeffSumRange g) < ε)
        (hrr_ne : (C t * f + g) ≠ 0) (hrr_splits : (C t * f + g).Splits) :
        ∃ b : ℝ, (C t * f + g).IsRoot b ∧
          ‖a - b‖ < ((f.natDegree + 1) * ε) ^ ((f.natDegree : ℝ)⁻¹) * max ‖a‖ 1
  • A nearby complex root in a left pencil

    RealRooted.exists_complex_aroot_near_in_left_familysource
    theorem exists_complex_aroot_near_in_left_family
        {f g : ℝ[X]} {z : ℂ} {t ε : ℝ}
        (hz : f.aeval z = 0)
        (hf_monic : f.Monic) (hg_monic : g.Monic)
        (hdeg : g.natDegree = f.natDegree)
        (ht : 0 < t)
        (hcoeff_bound : (t + 1)⁻¹ * (coeffSumRange f + coeffSumRange g) < ε)
        (hrr_ne : (C t * f + g) ≠ 0) (hrr_splits : (C t * f + g).Splits) :
        ∃ w : ℂ, w ∈ (C t * f + g).aroots ℂ ∧
          ‖z - w‖ < ((f.natDegree + 1) * ε) ^ ((f.natDegree : ℝ)⁻¹) * max ‖z‖ 1
  • Large-parameter coefficient control

    RealRooted.exists_t_pos_with_normalized_left_family_boundsource
    theorem exists_t_pos_with_normalized_left_family_bound
        (f g : ℝ[X]) {ε : ℝ} (hε : 0 < ε) :
        ∃ t : ℝ, 0 < t ∧ (t + 1)⁻¹ * (coeffSumRange f + coeffSumRange g) < ε
  • Real-rootedness from a symmetric substitution

    RealRooted.splits_of_symmetric_substitutionsource
    theorem splits_of_symmetric_substitution {f h : ℝ[X]} (n : ℕ)
        (hh : h ≠ 0) (hhs : h.Splits)
        (hrel : ∀ {u : ℂ}, u ≠ 0 →
          f.aeval (-(u ^ 2)) = u ^ n * h.aeval ((1 - u ^ 2) / u)) :
        f.Splits
  • Reciprocal scaling of root multisets

    RealRooted.add_right_roots_eq_add_left_invsource
    theorem add_right_roots_eq_add_left_inv
        {f g : ℝ[X]} {μ : ℝ} (hμ : μ ≠ 0) :
        (f + C μ * g).roots = (g + C μ⁻¹ * f).roots
  • Reciprocal scaling of upper root counts

    RealRooted.add_right_roots_gt_card_eq_add_left_invsource
    theorem add_right_roots_gt_card_eq_add_left_inv
        {f g : ℝ[X]} {μ x : ℝ} (hμ : μ ≠ 0) :
        ((f + C μ * g).roots.filter (x < ·)).card =
          ((g + C μ⁻¹ * f).roots.filter (x < ·)).card
  • Endpoint signs across a nonvanishing family

    RealRooted.eval_endpoint_pos_of_forall_ne_zerosource
    theorem eval_endpoint_pos_of_forall_ne_zero
        {p : ℝ → ℝ[X]} {a t₀ t₁ : ℝ}
        (hle : t₀ ≤ t₁)
        (hcont : ContinuousOn (fun t => (p t).eval a) (Set.Icc t₀ t₁))
        (hne : ∀ t ∈ Set.Icc t₀ t₁, (p t).eval a ≠ 0) :
        0 < (p t₀).eval a * (p t₁).eval a
  • Constancy of lower root counts

    RealRooted.card_roots_filter_le_eq_of_no_isRoot_Iccsource
    theorem card_roots_filter_le_eq_of_no_isRoot_Icc
        {p : ℝ[X]} {a b : ℝ} (hab : a ≤ b)
        (h : ∀ x, a ≤ x → x ≤ b → ¬ p.IsRoot x) :
        (p.roots.filter (· ≤ a)).card = (p.roots.filter (· ≤ b)).card
  • Constancy of upper root counts

    RealRooted.card_roots_filter_gt_eq_of_no_isRoot_Iccsource
    theorem card_roots_filter_gt_eq_of_no_isRoot_Icc
        {p : ℝ[X]} {a b : ℝ} (hab : a ≤ b)
        (h : ∀ x, a ≤ x → x ≤ b → ¬ p.IsRoot x) :
        (p.roots.filter (a < ·)).card = (p.roots.filter (b < ·)).card
  • Bundled root-count constancy

    RealRooted.card_roots_filter_all_eq_of_no_isRoot_Iccsource
    theorem card_roots_filter_all_eq_of_no_isRoot_Icc
        {p : ℝ[X]} {a b : ℝ} (hab : a ≤ b)
        (h : ∀ x, a ≤ x → x ≤ b → ¬ p.IsRoot x) :
        (p.roots.filter (· ≤ a)).card = (p.roots.filter (· ≤ b)).card ∧
          (p.roots.filter (a < ·)).card = (p.roots.filter (b < ·)).card ∧
            (p.roots.filter (fun x => a < x ∧ x ≤ b)).card = 0
  • Stability of lower count differences

    RealRooted.card_roots_filter_le_sub_eq_of_no_isRoot_Iccsource
    theorem card_roots_filter_le_sub_eq_of_no_isRoot_Icc
        {f g : ℝ[X]} {a b : ℝ} (hab : a ≤ b)
        (hf : ∀ x, a ≤ x → x ≤ b → ¬ f.IsRoot x)
        (hg : ∀ x, a ≤ x → x ≤ b → ¬ g.IsRoot x) :
        ((f.roots.filter (· ≤ a)).card : ℤ) - (g.roots.filter (· ≤ a)).card
          = ((f.roots.filter (· ≤ b)).card : ℤ) - (g.roots.filter (· ≤ b)).card
  • Stability of upper count differences

    RealRooted.card_roots_filter_gt_sub_eq_of_no_isRoot_Iccsource
    theorem card_roots_filter_gt_sub_eq_of_no_isRoot_Icc
        {f g : ℝ[X]} {a b : ℝ} (hab : a ≤ b)
        (hf : ∀ x, a ≤ x → x ≤ b → ¬ f.IsRoot x)
        (hg : ∀ x, a ≤ x → x ≤ b → ¬ g.IsRoot x) :
        ((f.roots.filter (a < ·)).card : ℤ) - (g.roots.filter (a < ·)).card
          = ((f.roots.filter (b < ·)).card : ℤ) - (g.roots.filter (b < ·)).card
  • Count differences at interior samples

    RealRooted.card_roots_filter_gt_sub_eq_of_no_isRoot_Ioosource
    theorem card_roots_filter_gt_sub_eq_of_no_isRoot_Ioo
        {f g : ℝ[X]} {a b x y : ℝ}
        (hf : ∀ z : ℝ, a < z → z < b → ¬ f.IsRoot z)
        (hg : ∀ z : ℝ, a < z → z < b → ¬ g.IsRoot z)
        (hax : a < x) (hxb : x < b) (hay : a < y) (hyb : y < b) :
        ((f.roots.filter (x < ·)).card : ℤ) - (g.roots.filter (x < ·)).card =
          ((f.roots.filter (y < ·)).card : ℤ) - (g.roots.filter (y < ·)).card
  • Parity of interior count differences

    RealRooted.odd_card_roots_filter_gt_sub_iff_of_no_isRoot_Ioosource
    theorem odd_card_roots_filter_gt_sub_iff_of_no_isRoot_Ioo
        {f g : ℝ[X]} {a b x y : ℝ}
        (hf : ∀ z : ℝ, a < z → z < b → ¬ f.IsRoot z)
        (hg : ∀ z : ℝ, a < z → z < b → ¬ g.IsRoot z)
        (hax : a < x) (hxb : x < b) (hay : a < y) (hyb : y < b) :
        (Odd (((f.roots.filter (x < ·)).card : ℤ) -
            (g.roots.filter (x < ·)).card) ↔
          Odd (((f.roots.filter (y < ·)).card : ℤ) -
            (g.roots.filter (y < ·)).card))
  • Roots of f survive near their positions in a degree-increasing perturbation f + μgRealRooted original

    RealRooted.degreeIncreasing_local_lower_countsource
    theorem degreeIncreasing_local_lower_count {f g : ℝ[X]}
        (hf : f.Splits) (hlt : f.natDegree < g.natDegree)
        (ρ : ℝ) (hρ : 0 < ρ) :
        ∃ δ : ℝ, 0 < δ ∧ ∀ μ : ℝ, 0 < μ → μ < δ → (f + C μ * g).Splits →
          ∀ a ∈ f.roots.toFinset,
            f.roots.count a ≤
              ((f + C μ * g).roots.filter (fun q => |q - a| < ρ)).card

Lean source RealRooted/Challenges/Roots/RootContinuity.lean at revision d6670742. Formalized 2026-10-06.