Iterated derivative shifts

The shift $p\mapsto p-\varepsilon p'$ preserves real-rootedness for every real $\varepsilon$ and, for $\varepsilon>0$, produces an interlacing polynomial and, after $\deg p$ iterations, simple roots. It is the standard way to perturb a real-rooted polynomial into one with simple roots.

Results

For real $\varepsilon$ let $T_\varepsilon p=p-\varepsilon p'$.

Theorem (real-rootedness). If $p$ is real-rooted, then $T_\varepsilon p$ is real-rooted for every real $\varepsilon$, and so is every iterate $T_\varepsilon^kp$. If $p\ne0$, then $T_\varepsilon^kp\ne0$.

Theorem (interlacing). If $p\ne0$ is real-rooted and $\varepsilon>0$, then $p\ll T_\varepsilon p$.

Theorem (derivative). Let $p$ be real-rooted with positive leading coefficient and $\deg p\ge1$. If $\varepsilon\le0$, then $p'\ll T_\varepsilon p$. The same holds without the assumption on the leading coefficient of $p$ if $p=dq$ and $p'=dr$, where $d\ne0$ is real-rooted, $r\ll q$, and $q,r$ have positive leading coefficients.

Theorem (simple roots). Let $f\ne0$ be real-rooted and $\varepsilon>0$. If $\deg f=n$, then $T_\varepsilon^nf$ has simple roots. If $\deg f\le k$, then $T_{-\varepsilon}^kf$ has simple roots.

Theorem (nearby roots). Let $p$ be real-rooted, $a$ a root of $p$, $n\ge0$ and $\eta>0$. Then there is $\delta>0$ such that for every $0<\varepsilon<\delta$ the polynomial $T_\varepsilon^np$ has a real root $b$ with $$ |a-b|<\bigl((\deg p+1)\eta\bigr)^{1/\deg p}\max(|a|,1). $$ The same holds for the roots of the $k$-th derivative of $p$, and for $a$ with $k<\operatorname{mult}_a(p)$ it gives a root of $(T_\varepsilon^np)^{(k)}$ near $a$, with $\deg p$ replaced by $\deg p^{(k)}$ in the bound.

Theorem (sequences). Let $P_i\ne0$ be real-rooted, $\varepsilon_i>0$ and $k_i\in\mathbb N$. Then $T_{\varepsilon_i}^{k_i}P_i$ is real-rooted and $T_{\varepsilon_i}^{k_i}P_i\ll T_{\varepsilon_i}^{k_i+1}P_i$. Moreover, let $P_0\ne0$ and $F_n\ne0$ be real-rooted, and let $\varepsilon_n$ be real. If $P_{n+1}=F_n\,T_{\varepsilon_n}^{k_n}P_n$, or $P_{n+1}=T_{\varepsilon_n}^{k_n}P_n\,F_n$, then every $P_n$ is nonzero and real-rooted.

References

[SP14]; [Obr63].

  1. [SP14] J Schur & G Polya. Über zwei Arten von Faktorenfolgen in der Theorie der algebraischen Gleichungen. J. Reine Angew. Math., 1914.
    BibTeX
    @article{SchurPolya1914,
      title={{\"U}ber zwei {A}rten von {F}aktorenfolgen in der {T}heorie der algebraischen {G}leichungen},
      author={Schur, J and Polya, G},
      year={1914},
      journal={J. Reine Angew. Math.},
      publisher={Walter de Gruyter, Berlin/New York Berlin, New York}
    }
  2. [Obr63] Nikola Obreschkoff. Verteilung und Berechnung der Nullstellen reeller Polynome. Hochschulbücher für Mathematik, vol. 55, VEB Deutscher Verlag der Wissenschaften, 1963.
    BibTeX
    @book{Obreschkoff1963,
      author = {Obreschkoff, Nikola},
      title = {Verteilung und Berechnung der Nullstellen reeller Polynome},
      series = {Hochschulb{\"u}cher f{\"u}r Mathematik},
      volume = {55},
      publisher = {VEB Deutscher Verlag der Wissenschaften},
      address = {Berlin},
      year = {1963}
    }

Theorems

  • Positive shifts preserve splitness

    RealRooted.splits_tDerivsource
    theorem splits_tDeriv {eps : ℝ} {p : ℝ[X]} (heps : 0 < eps) (hp : p.Splits) :
        (tDeriv eps p).Splits
  • All real shifts preserve splitnessMain result

    RealRooted.splits_tDeriv_allsource
    theorem splits_tDeriv_all {eps : ℝ} {p : ℝ[X]} (hp : p.Splits) :
        (tDeriv eps p).Splits
  • Positive shifts give interlacing

    RealRooted.strictInterl_tDerivsource
    theorem strictInterl_tDeriv {eps : ℝ} {p : ℝ[X]}
        (heps : 0 < eps) (hp₀ : p ≠ 0)
        (hp : p.Splits) :
        StrictInterl p (tDeriv eps p)
  • Nonpositive shifts from the derivative

    RealRooted.derivative_strictInterl_tDeriv_of_nonpossource
    theorem derivative_strictInterl_tDeriv_of_nonpos {eps : ℝ} {p : ℝ[X]}
        (heps : eps ≤ 0) (hp : p.Splits)
        (hp_pos : HasPosLeadingCoeff p) (hdeg : 1 ≤ p.natDegree) :
        StrictInterl p.derivative (tDeriv eps p)
  • Common-factor derivative interlacing

    RealRooted.derivative_strictInterl_tDeriv_of_nonpos_of_common_factorsource
    theorem derivative_strictInterl_tDeriv_of_nonpos_of_common_factor {eps : ℝ} {p d q r : ℝ[X]}
        (heps : eps ≤ 0) (hp : p.Splits) (hdeg : 1 ≤ p.natDegree)
        (hd_ne : d ≠ 0) (hd_splits : d.Splits)
        (hp_def : p = d * q) (hder_def : p.derivative = d * r)
        (hrq : StrictInterl r q) (hq_pos : HasPosLeadingCoeff q)
        (hr_pos : HasPosLeadingCoeff r) :
        StrictInterl p.derivative (tDeriv eps p)
  • Simple roots after degree-many shifts

    RealRooted.hasSimpleRoots_iterateTDeriv_of_natDegreesource
    theorem hasSimpleRoots_iterateTDeriv_of_natDegree
        {f : ℝ[X]} {n : ℕ} {eps : ℝ}
        (heps : 0 < eps) (hf₀ : f ≠ 0)
        (hf : f.Splits)
        (hdeg : f.natDegree = n) :
        HasSimpleRoots (iterateTDeriv eps n f)
  • Simple roots after enough negative shifts

    RealRooted.hasSimpleRoots_iterateTDeriv_neg_of_natDegree_lesource
    theorem hasSimpleRoots_iterateTDeriv_neg_of_natDegree_le
        {eps : ℝ} (heps : 0 < eps) {p : ℝ[X]} (hp_ne : p ≠ 0)
        (hp_splits : p.Splits) {k : ℕ} (hdeg : p.natDegree ≤ k) :
        HasSimpleRoots (iterateTDeriv (-eps) k p)
  • Nearby roots for monic regularizations

    RealRooted.exists_delta_and_real_root_near_iterateTDerivsource
    theorem exists_delta_and_real_root_near_iterateTDeriv
        (n : ℕ) {p : ℝ[X]} {a ε : ℝ}
        (ha : p.IsRoot a)
        (hp : p.Splits) (hp_monic : p.Monic)
        (hε : 0 < ε) :
        ∃ δ > 0, ∀ ⦃eps : ℝ⦄, 0 < eps → ‖eps‖ < δ →
          ∃ b ∈ (iterateTDeriv eps n p).roots,
            ‖a - b‖ < ((p.natDegree + 1) * ε) ^ ((p.natDegree : ℝ)⁻¹) * max ‖a‖ 1
  • Nearby roots after normalization

    RealRooted.exists_root_near_iterateTDerivsource
    theorem exists_root_near_iterateTDeriv
        (n : ℕ) {p : ℝ[X]} {a ε : ℝ}
        (ha : p.IsRoot a)
        (hp_ne : p ≠ 0) (hp_splits : p.Splits)
        (hε : 0 < ε) :
        ∃ δ > 0, ∀ ⦃eps : ℝ⦄, 0 < eps → ‖eps‖ < δ →
          ∃ b : ℝ, (iterateTDeriv eps n p).IsRoot b ∧
            ‖a - b‖ < ((p.natDegree + 1) * ε) ^ ((p.natDegree : ℝ)⁻¹) * max ‖a‖ 1
  • Nearby roots in a derivative tower

    RealRooted.exists_root_near_derivative_iterateTDerivsource
    theorem exists_root_near_derivative_iterateTDeriv
        (n k : ℕ) {p : ℝ[X]} {a ε : ℝ}
        (ha : ((derivative^[k]) p).IsRoot a)
        (hp_ne : ((derivative^[k]) p) ≠ 0) (hp_splits : ((derivative^[k]) p).Splits)
        (hε : 0 < ε) :
        ∃ δ > 0, ∀ ⦃eps : ℝ⦄, 0 < eps → ‖eps‖ < δ →
          ∃ b : ℝ, ((derivative^[k]) (iterateTDeriv eps n p)).IsRoot b ∧
            ‖a - b‖ <
              ((((derivative^[k]) p).natDegree + 1) * ε) ^
                ((((derivative^[k]) p).natDegree : ℝ)⁻¹) * max ‖a‖ 1
  • Nearby roots from multiplicity

    RealRooted.exists_root_near_iterateTDeriv_of_lt_multiplicitysource
    theorem exists_root_near_iterateTDeriv_of_lt_multiplicity
        (n k : ℕ) {p : ℝ[X]} {a ε : ℝ}
        (ha : k < p.rootMultiplicity a)
        (hp_ne : ((derivative^[k]) p) ≠ 0) (hp_splits : ((derivative^[k]) p).Splits)
        (hε : 0 < ε) :
        ∃ δ > 0, ∀ ⦃eps : ℝ⦄, 0 < eps → ‖eps‖ < δ →
          ∃ b : ℝ, ((derivative^[k]) (iterateTDeriv eps n p)).IsRoot b ∧
            ‖a - b‖ <
              ((((derivative^[k]) p).natDegree + 1) * ε) ^
                ((((derivative^[k]) p).natDegree : ℝ)⁻¹) * max ‖a‖ 1
  • Sequence iterates preserve splitness

    RealRooted.Tactic.iterateTDeriv_sequence_splitssource
    theorem iterateTDeriv_sequence_splits
        {eps : Nat → ℝ} {P : Nat → ℝ[X]} (K : Nat → ℕ)
        (heps : ∀ i : Nat, 0 < eps i)
        (hP : ∀ i : Nat, (P i).Splits) :
        ∀ i : Nat, (iterateTDeriv (eps i) (K i) (P i)).Splits
  • Sequence iterates interlace

    RealRooted.Tactic.iterateTDeriv_sequence_strictInterl_succsource
    theorem iterateTDeriv_sequence_strictInterl_succ
        {eps : Nat → ℝ} {P : Nat → ℝ[X]} (K : Nat → ℕ)
        (heps : ∀ i : Nat, 0 < eps i)
        (hP0 : ∀ i : Nat, P i ≠ 0)
        (hP : ∀ i : Nat, (P i).Splits) :
        ∀ i : Nat,
          StrictInterl (iterateTDeriv (eps i) (K i) (P i))
            (iterateTDeriv (eps i) (K i + 1) (P i))
  • An iterate remains real-rooted

    RealRooted.isRealRooted_iterateTDerivsource
    theorem isRealRooted_iterateTDeriv {eps : ℝ} {k : Nat} {p : ℝ[X]}
        (hp : p ≠ 0 ∧ p.Splits) :
        iterateTDeriv eps k p ≠ 0 ∧ (iterateTDeriv eps k p).Splits
  • Left-factor product recurrence

    RealRooted.isRealRooted_of_iteratedTDeriv_product_sequencesource
    theorem isRealRooted_of_iteratedTDeriv_product_sequence
        {P F : Nat → ℝ[X]} {eps : Nat → ℝ} {k : Nat → Nat}
        (hbase : P 0 ≠ 0 ∧ (P 0).Splits)
        (hfactor : ∀ n : Nat, F n ≠ 0 ∧ (F n).Splits)
        (hstep :
          ∀ n : Nat, P (n + 1) = F n * iterateTDeriv (eps n) (k n) (P n)) :
        ∀ n : Nat, P n ≠ 0 ∧ (P n).Splits
  • Right-factor product recurrence

    RealRooted.isRealRooted_of_iteratedTDeriv_product_right_sequencesource
    theorem isRealRooted_of_iteratedTDeriv_product_right_sequence
        {P F : Nat → ℝ[X]} {eps : Nat → ℝ} {k : Nat → Nat}
        (hbase : P 0 ≠ 0 ∧ (P 0).Splits)
        (hfactor : ∀ n : Nat, F n ≠ 0 ∧ (F n).Splits)
        (hstep :
          ∀ n : Nat, P (n + 1) = iterateTDeriv (eps n) (k n) (P n) * F n) :
        ∀ n : Nat, P n ≠ 0 ∧ (P n).Splits

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