Interlacing and root intervals of endpoint-derivative sequences

Applying $f\mapsto(x-a)(x-b)f'$ or $f\mapsto((x-a)(x-b)f)'$ to a real-rooted polynomial with all roots in $[a,b]$ gives a polynomial of one higher degree that is real-rooted, interlaced by $f$, and has all roots in $[a,b]$.

Results

Fix real numbers $a\le b$ and put $q=(x-a)(x-b)$.

Theorem (one step). Let $f$ be real-rooted with positive leading coefficient, degree at least $1$, and all roots in $[a,b]$. Then $$ f\ll qf'\qquad\text{and}\qquad f\ll(qf)', $$ and all roots of $qf'$ and of $(qf)'$ lie in $[a,b]$. Moreover $qf'$ and $(qf)'$ have degree $\deg f+1$ and positive leading coefficient.

Theorem (sequences). Let $P_0$ be real-rooted with all roots in $[a,b]$, and suppose that every $P_n$ has positive leading coefficient and degree at least $1$. Suppose that $P_{n+1}=qP_n'$ for all $n$, or that $P_{n+1}=(qP_n)'$ for all $n$. Then every $P_n$ is nonzero and real-rooted and $P_n\ll P_{n+1}$ for all $n$, with a degree gap of one whenever $\deg P_{n+1}=\deg P_n+1$ for all $n$.

Use

Iterating these maps gives, for example, the rows of OEIS A142071, A172106, A172107 and A172108, which are therefore real-rooted and interlacing.

Proof

Both maps have the form $f\mapsto uf+qf'$, with $u=0$ or $u=q'$. The derivative step of Ma–Wang and Liu–Wang gives $f\ll uf+qf'$ when $q\le0$ at the roots of $f$ and $uf+qf'$ has positive leading coefficient and degree $\deg f+1$; here $q\le0$ on $[a,b]$. The sequence theorem follows by induction on $n$, since the one-step theorem preserves the hypotheses.

References

For derivative interlacing, see [Fis06, Ch. 1]. The derivative step is on the Ma–Wang and Liu–Wang page.

  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}
    }

Theorems

  • f interlaces (x-a)(x-b)f' when its roots lie in [a,b]Main result

    RealRooted.strictInterl_endpointDerivativesource
    theorem strictInterl_endpointDerivative {f : ℝ[X]} {a b : ℝ}
        (hf : f.Splits) (hdeg : 1 ≤ f.natDegree)
        (hf_pos : HasPosLeadingCoeff f)
        (hroots : ∀ r, f.IsRoot r → r ∈ Icc a b) :
        StrictInterl f (((X - C a) * (X - C b)) * f.derivative)
  • The roots of (x-a)(x-b)f' lie in [a,b]

    RealRooted.roots_endpointDerivative_mem_Iccsource
    theorem roots_endpointDerivative_mem_Icc {f : ℝ[X]} {a b : ℝ}
        (hab : a ≤ b) (hf : f.Splits) (hdeg : 1 ≤ f.natDegree)
        (hf_pos : HasPosLeadingCoeff f)
        (hroots : ∀ r, f.IsRoot r → r ∈ Icc a b) :
        ∀ r ∈ (((X - C a) * (X - C b)) * f.derivative).roots,
          r ∈ Icc a b
  • f interlaces ((x-a)(x-b)f)' when its roots lie in [a,b]

    RealRooted.strictInterl_derivative_endpointProductsource
    theorem strictInterl_derivative_endpointProduct {f : ℝ[X]} {a b : ℝ}
        (hf : f.Splits) (hdeg : 1 ≤ f.natDegree)
        (hf_pos : HasPosLeadingCoeff f)
        (hroots : ∀ r, f.IsRoot r → r ∈ Icc a b) :
        StrictInterl f (((X - C a) * (X - C b) * f).derivative)
  • The roots of ((x-a)(x-b)f)' lie in [a,b]

    RealRooted.roots_derivative_endpointProduct_mem_Iccsource
    theorem roots_derivative_endpointProduct_mem_Icc {f : ℝ[X]} {a b : ℝ}
        (hab : a ≤ b) (hf : f.Splits) (hf_pos : HasPosLeadingCoeff f)
        (hroots : ∀ r, f.IsRoot r → r ∈ Icc a b) :
        ∀ r ∈ (((X - C a) * (X - C b) * f).derivative).roots,
          r ∈ Icc a b
  • Iterating (x-a)(x-b)f' gives a chain P_n ≪ P_{n+1}

    RealRooted.strictInterl_endpointDerivative_sequencesource
    theorem strictInterl_endpointDerivative_sequence
        {P : ℕ → ℝ[X]} {a b : ℝ}
        (hab : a ≤ b)
        (hbase_splits : (P 0).Splits)
        (hbase_roots : ∀ r ∈ (P 0).roots, r ∈ Icc a b)
        (hpos : ∀ n, HasPosLeadingCoeff (P n))
        (hdeg : ∀ n, 1 ≤ (P n).natDegree)
        (hrec : ∀ n,
          P (n + 1) = ((X - C a) * (X - C b)) * (P n).derivative) :
        ∀ n, StrictInterl (P n) (P (n + 1))
  • Iterating ((x-a)(x-b)f)' gives a chain P_n ≪ P_{n+1}

    RealRooted.strictInterl_derivative_endpointProduct_sequencesource
    theorem strictInterl_derivative_endpointProduct_sequence
        {P : ℕ → ℝ[X]} {a b : ℝ}
        (hab : a ≤ b)
        (hbase_splits : (P 0).Splits)
        (hbase_roots : ∀ r ∈ (P 0).roots, r ∈ Icc a b)
        (hpos : ∀ n, HasPosLeadingCoeff (P n))
        (hdeg : ∀ n, 1 ≤ (P n).natDegree)
        (hrec : ∀ n,
          P (n + 1) = (((X - C a) * (X - C b)) * P n).derivative) :
        ∀ n, StrictInterl (P n) (P (n + 1))
  • Iterating (x-a)(x-b)f' with degrees rising by one: differ-by-one interlacing

    RealRooted.interlaces_endpointDerivative_sequencesource
    theorem interlaces_endpointDerivative_sequence
        {P : ℕ → ℝ[X]} {a b : ℝ}
        (hab : a ≤ b)
        (hbase_splits : (P 0).Splits)
        (hbase_roots : ∀ r ∈ (P 0).roots, r ∈ Icc a b)
        (hpos : ∀ n, HasPosLeadingCoeff (P n))
        (hdeg : ∀ n, 1 ≤ (P n).natDegree)
        (hrec : ∀ n,
          P (n + 1) = ((X - C a) * (X - C b)) * (P n).derivative)
        (hdeg_succ : ∀ n, (P n).natDegree + 1 = (P (n + 1)).natDegree) :
        ∀ n, Interlaces (P n) (P (n + 1))
  • Iterating ((x-a)(x-b)f)' with degrees rising by one: differ-by-one interlacing

    RealRooted.interlaces_derivative_endpointProduct_sequencesource
    theorem interlaces_derivative_endpointProduct_sequence
        {P : ℕ → ℝ[X]} {a b : ℝ}
        (hab : a ≤ b)
        (hbase_splits : (P 0).Splits)
        (hbase_roots : ∀ r ∈ (P 0).roots, r ∈ Icc a b)
        (hpos : ∀ n, HasPosLeadingCoeff (P n))
        (hdeg : ∀ n, 1 ≤ (P n).natDegree)
        (hrec : ∀ n,
          P (n + 1) = (((X - C a) * (X - C b)) * P n).derivative)
        (hdeg_succ : ∀ n, (P n).natDegree + 1 = (P (n + 1)).natDegree) :
        ∀ n, Interlaces (P n) (P (n + 1))
  • Iterating (x-a)(x-b)f' gives nonzero real-rooted rows

    RealRooted.isRealRooted_endpointDerivative_sequencesource
    theorem isRealRooted_endpointDerivative_sequence
        {P : ℕ → ℝ[X]} {a b : ℝ}
        (hab : a ≤ b)
        (hbase_splits : (P 0).Splits)
        (hbase_roots : ∀ r ∈ (P 0).roots, r ∈ Icc a b)
        (hpos : ∀ n, HasPosLeadingCoeff (P n))
        (hdeg : ∀ n, 1 ≤ (P n).natDegree)
        (hrec : ∀ n,
          P (n + 1) = ((X - C a) * (X - C b)) * (P n).derivative) :
        ∀ n, P n ≠ 0 ∧ (P n).Splits
  • Iterating ((x-a)(x-b)f)' gives nonzero real-rooted rows

    RealRooted.isRealRooted_derivative_endpointProduct_sequencesource
    theorem isRealRooted_derivative_endpointProduct_sequence
        {P : ℕ → ℝ[X]} {a b : ℝ}
        (hab : a ≤ b)
        (hbase_splits : (P 0).Splits)
        (hbase_roots : ∀ r ∈ (P 0).roots, r ∈ Icc a b)
        (hpos : ∀ n, HasPosLeadingCoeff (P n))
        (hdeg : ∀ n, 1 ≤ (P n).natDegree)
        (hrec : ∀ n,
          P (n + 1) = (((X - C a) * (X - C b)) * P n).derivative) :
        ∀ n, P n ≠ 0 ∧ (P n).Splits
  • (x-a)(x-b)f' has degree deg f + 1

    RealRooted.natDegree_endpointDerivativesource
    theorem natDegree_endpointDerivative {f : ℝ[X]} {a b : ℝ}
        (hdeg : 1 ≤ f.natDegree) :
        (((X - C a) * (X - C b)) * f.derivative).natDegree =
          f.natDegree + 1
  • (x-a)(x-b)f' has positive leading coefficient

    RealRooted.hasPosLeadingCoeff_endpointDerivativesource
    theorem hasPosLeadingCoeff_endpointDerivative {f : ℝ[X]} {a b : ℝ}
        (hf_pos : HasPosLeadingCoeff f) (hdeg : 1 ≤ f.natDegree) :
        HasPosLeadingCoeff (((X - C a) * (X - C b)) * f.derivative)
  • ((x-a)(x-b)f)' has degree deg f + 1

    RealRooted.natDegree_derivative_endpointProductsource
    theorem natDegree_derivative_endpointProduct {f : ℝ[X]} {a b : ℝ}
        (hf_pos : HasPosLeadingCoeff f) :
        (((X - C a) * (X - C b) * f).derivative).natDegree =
          f.natDegree + 1
  • ((x-a)(x-b)f)' has positive leading coefficient

    RealRooted.hasPosLeadingCoeff_derivative_endpointProductsource
    theorem hasPosLeadingCoeff_derivative_endpointProduct {f : ℝ[X]} {a b : ℝ}
        (hf_pos : HasPosLeadingCoeff f) :
        HasPosLeadingCoeff (((X - C a) * (X - C b) * f).derivative)

Lean source RealRooted/Challenges/Interlacing/EndpointDerivative.lean at revision d6670742. Formalized 2026-09-26.