Interlacing from a monomial chain

A linear operator that preserves nonnegative coefficients and real-rootedness of PF inputs, and maps the monomials $1,x,\dotsc,x^D$ to an interlacing chain, preserves interlacing of pairs with nonnegative coefficients and degree at most $D$. This reduces interlacing preservation to a check on monomials.

Results

A polynomial is PF (Pólya frequency) if it is zero or has nonnegative coefficients and only real, nonpositive roots.

Theorem (monomial chain). Let $T$ be a real-linear operator on $\mathbb R[x]$ and $D\in\mathbb N$. Suppose that

  1. $T$ maps polynomials with nonnegative coefficients to polynomials with nonnegative coefficients;
  2. $T$ maps every nonzero PF polynomial of degree at most $D$ to a nonzero real-rooted polynomial;
  3. $T(1)\ll T(x)\ll\dotsb\ll T(x^D)$.

If $f\ll g$ have nonnegative coefficients and $\deg g\le D$, then $Tf\ll Tg$.

Theorem (rootwise order). Let $T$ satisfy (1)--(3), and in addition $\deg Tp=D$ whenever $\deg p=D$. Let $r_1,\dotsc,r_D\le0$ be the roots of a monic polynomial $p$ of degree $D$.

Theorem (root derivative). Let $T$ be linear, $p=\prod_i(x-r_i)$, and let $\rho$ be a simple root of $Tp$. Then for each $i$ there is a function $\rho(s)$, differentiable at $0$, with $\rho(0)=\rho$ and $\rho(s)$ a root of $T\bigl((x-r_i-s)\prod_{j\ne i}(x-r_j)\bigr)$ for all small $s$, and $$ \rho'(0)=\frac{T\bigl(p/(x-r_i)\bigr)(\rho)}{(Tp)'(\rho)} . $$

Theorem (stable pencils). Let $T$ satisfy (1)--(3), and let $f,g\ne0$ have nonnegative coefficients with $1\le\deg f\le D$ and $\deg Tf\ge1$. If $f(z)+w\,g(z)$ is upper-half-plane stable, then so is $(Tf)(z)+w\,(Tg)(z)$.

Corollary (Narayana transform). The Mao–Wang Narayana transform $N_m$ satisfies $N_mf\ll N_mg$ whenever $f\ll g$ have nonnegative coefficients; see the Narayana page.

The proof rests on a closure property of quadratic pencils. Let $F\ll G\ll H$ have nonnegative coefficients. For $b\ge0$ put $$ Q_b=H+2bG+b^2F,\qquad A_b=G+bF,\qquad B_b=H+bG . $$

Theorem (quadratic closure). If $Q_b$ is real-rooted for every $b\ge0$, then $A_a\ll Q_a$ and $A_a\ll B_a$ for every $a\ge0$. That is, $$ G+aF\ \ll\ H+aG . $$

If $F,G,H$ have positive leading coefficients and $r$ is a root of none of them, then the quadratic $b\mapsto Q_b(r)$ has at most as many positive roots as the number of roots of $H$ above $r$ minus the number of roots of $F$ above $r$.

Proof

The quadratic closure propagates the monomial chain through all PF inputs, one nonpositive linear factor at a time. The Garloff–Wagner Krein expansion then passes from one-root deletions to every interlacing pair.

References

  1. [Bra11] Petter Brändén. Iterated sequences and the geometry of zeros. Journal für die reine und angewandte Mathematik (Crelles Journal), 2011(658), 2011.
    BibTeX
    @article{Branden2011b,
      author = {Brändén, Petter},
      title = {Iterated sequences and the geometry of zeros},
      year = {2011},
      journal = {Journal für die reine und angewandte Mathematik (Crelles Journal)},
      volume = {2011},
      number = {658},
      doi = {10.1515/crelle.2011.063},
      url = {https://doi.org/10.1515/crelle.2011.063}
    }

Definitions

  • Quadratic interlacing pencil

    RealRooted.quadraticInterlacingPencilsource
    def quadraticInterlacingPencil (F G H : ℝ[X]) (a : ℝ) : ℝ[X] :=
      H + C (2 * a) * G + C (a ^ 2) * F
  • Tangent of the quadratic interlacing pencil

    RealRooted.quadraticInterlacingTangentsource
    def quadraticInterlacingTangent (F G : ℝ[X]) (a : ℝ) : ℝ[X] :=
      G + C a * F

Theorems

  • The monomial chain gives interlacing preservationMain result

    RealRooted.strictInterl_map_of_monomialChainsource
    theorem strictInterl_map_of_monomialChain
        {T : ℝ[X] →ₗ[ℝ] ℝ[X]} {D : ℕ} {f g : ℝ[X]}
        (hfg : StrictInterl f g)
        (hf : HasNonnegCoeffs f) (hg : HasNonnegCoeffs g)
        (hgdeg : g.natDegree ≤ D)
        (hTnn : ∀ ⦃p : ℝ[X]⦄, HasNonnegCoeffs p → HasNonnegCoeffs (T p))
        (hTrr : ∀ ⦃p : ℝ[X]⦄, IsPFPolynomial p → p ≠ 0 →
          p.natDegree ≤ D → T p ≠ 0 ∧ (T p).Splits)
        (hmono : ∀ m : ℕ, m + 1 ≤ D →
          StrictInterl (T (X ^ m)) (T (X ^ (m + 1)))) :
        StrictInterl (T f) (T g)
  • Moving one input root right moves every output root right

    RealRooted.rootwiseLE_monomialChain_rootPolynomial_list_setsource
    theorem rootwiseLE_monomialChain_rootPolynomial_list_set
        {T : ℝ[X] →ₗ[ℝ] ℝ[X]} {D : ℕ} (r : List ℝ) (i : ℕ)
        (hi : i < r.length) {b : ℝ} (hmove : r[i] ≤ b)
        (hr : ∀ x ∈ (r : Multiset ℝ), x ≤ 0)
        (hr_set : ∀ x ∈ ((r.set i b : List ℝ) : Multiset ℝ), x ≤ 0)
        (hTdegree : ∀ {p : ℝ[X]}, p.natDegree = D → (T p).natDegree = D)
        (hTnn : ∀ ⦃p : ℝ[X]⦄, HasNonnegCoeffs p → HasNonnegCoeffs (T p))
        (hTrr : ∀ ⦃p : ℝ[X]⦄, IsPFPolynomial p → p ≠ 0 →
          p.natDegree ≤ D → T p ≠ 0 ∧ (T p).Splits)
        (hmono : ∀ m : ℕ, m + 1 ≤ D →
          StrictInterl (T (X ^ m)) (T (X ^ (m + 1))))
        (hD : r.length = D) :
        RootwiseLE
          (T (rootPolynomial (r : Multiset ℝ)))
          (T (rootPolynomial ((r.set i b : List ℝ) : Multiset ℝ)))
  • Output roots are bounded by the images of (x + a)^D and (x + b)^D

    RealRooted.rootwiseLE_monomialChain_component_boundssource
    theorem rootwiseLE_monomialChain_component_bounds
        {T : ℝ[X] →ₗ[ℝ] ℝ[X]} {D : ℕ} {p : ℝ[X]} {a b : ℝ}
        (hmonic : p.Monic) (hsplits : p.Splits) (hdeg : p.natDegree = D)
        (ha : 0 ≤ a) (hab : a ≤ b)
        (hlo : ∀ r ∈ p.roots, -b ≤ r)
        (hhi : ∀ r ∈ p.roots, r ≤ -a)
        (hTdegree : ∀ {q : ℝ[X]}, q.natDegree = D → (T q).natDegree = D)
        (hTnn : ∀ ⦃q : ℝ[X]⦄, HasNonnegCoeffs q → HasNonnegCoeffs (T q))
        (hTrr : ∀ ⦃q : ℝ[X]⦄, IsPFPolynomial q → q ≠ 0 →
          q.natDegree ≤ D → T q ≠ 0 ∧ (T q).Splits)
        (hmono : ∀ m : ℕ, m + 1 ≤ D →
          StrictInterl (T (X ^ m)) (T (X ^ (m + 1)))) :
        RootwiseLE (T ((X + C b) ^ D)) (T p) ∧
          RootwiseLE (T p) (T ((X + C a) ^ D))
  • The Mao–Wang Narayana transform preserves interlacing

    RealRooted.strictInterl_narayanaTransformsource
    theorem strictInterl_narayanaTransform {f g : ℝ[X]} (hfg : StrictInterl f g)
        (hf : HasNonnegCoeffs f) (hg : HasNonnegCoeffs g) (m : ℕ) :
        StrictInterl (narayanaTransform m f) (narayanaTransform m g)
  • Implicit derivative of a simple output root in one input root

    RealRooted.exists_hasDerivAt_finRootPolynomial_shiftsource
    theorem exists_hasDerivAt_finRootPolynomial_shift
        {n : ℕ} {T : ℝ[X] →ₗ[ℝ] ℝ[X]} {r : Fin n → ℝ} {i : Fin n} {ρ : ℝ}
        (hroot : (T (finRootPolynomial r)).IsRoot ρ)
        (hregular : (T (finRootPolynomial r)).derivative.eval ρ ≠ 0) :
        ∃ branch : ℝ → ℝ,
          HasDerivAt branch
            ((T (finRootPolynomial r / (X - C (r i)))).eval ρ /
              (T (finRootPolynomial r)).derivative.eval ρ) 0 ∧
            branch 0 = ρ ∧
              ∀ᶠ s in 𝓝 0,
                (T (finRootPolynomial (Function.update r i (r i + s)))).IsRoot (branch s)
  • Monomial-chain operators preserve nonnegative stable pencils

    RealRooted.mvUpperHalfPlaneStable_bivariatePencil_map_of_monomialChainsource
    theorem mvUpperHalfPlaneStable_bivariatePencil_map_of_monomialChain
        {T : ℝ[X] →ₗ[ℝ] ℝ[X]} {D : ℕ} {f g : ℝ[X]}
        (hf : HasNonnegCoeffs f) (hg : HasNonnegCoeffs g) (hf0 : f ≠ 0) (hg0 : g ≠ 0)
        (hdeg : f.natDegree ≠ 0) (hfD : f.natDegree ≤ D) (hTdeg : (T f).natDegree ≠ 0)
        (hTnn : ∀ ⦃p : ℝ[X]⦄, HasNonnegCoeffs p → HasNonnegCoeffs (T p))
        (hTrr : ∀ ⦃p : ℝ[X]⦄, IsPFPolynomial p → p ≠ 0 →
          p.natDegree ≤ D → T p ≠ 0 ∧ (T p).Splits)
        (hmono : ∀ m : ℕ, m + 1 ≤ D →
          StrictInterl (T (X ^ m)) (T (X ^ (m + 1))))
        (hstab : MvUpperHalfPlaneStable (bivariatePencil f g)) :
        MvUpperHalfPlaneStable (bivariatePencil (T f) (T g))
  • Descartes budget for the quadratic parameter evaluation of an interlacing chainRealRooted original

    RealRooted.quadraticParameterEvaluation_positiveRootCount_lesource
    theorem quadraticParameterEvaluation_positiveRootCount_le
        {F G H : ℝ[X]} {r : ℝ}
        (hFpos : HasPosLeadingCoeff F) (hGpos : HasPosLeadingCoeff G)
        (hHpos : HasPosLeadingCoeff H) (hFG : StrictInterl F G)
        (hGH : StrictInterl G H) (hrF : ¬F.IsRoot r)
        (hrG : ¬G.IsRoot r) (hrH : ¬H.IsRoot r) :
        (quadraticParameterEvaluation F G H r).positiveRootCount ≤
          (H.roots.filter (r < ·)).card - (F.roots.filter (r < ·)).card
  • The tangent of a real-rooted quadratic pencil precedes the pencilRealRooted original

    RealRooted.strictInterl_quadraticInterlacingTangent_pencilsource
    theorem strictInterl_quadraticInterlacingTangent_pencil
        {F G H : ℝ[X]}
        (hF : HasNonnegCoeffs F) (hG : HasNonnegCoeffs G)
        (hH : HasNonnegCoeffs H) (hFG : StrictInterl F G)
        (hGH : StrictInterl G H)
        (hsplits : ∀ b : ℝ, 0 ≤ b →
          (quadraticInterlacingPencil F G H b).Splits)
        {a : ℝ} (ha : 0 ≤ a) :
        StrictInterl (quadraticInterlacingTangent F G a)
          (quadraticInterlacingPencil F G H a)
  • The tangent precedes the right member of the quadratic closureRealRooted original

    RealRooted.strictInterl_quadraticInterlacingRight_of_tangentsource
    theorem strictInterl_quadraticInterlacingRight_of_tangent
        {F G H : ℝ[X]} {a : ℝ}
        (hApos : HasPosLeadingCoeff (quadraticInterlacingTangent F G a))
        (hBpos : HasPosLeadingCoeff (quadraticInterlacingRight G H a))
        (hQpos : HasPosLeadingCoeff (quadraticInterlacingPencil F G H a))
        (hAQ : StrictInterl
          (quadraticInterlacingTangent F G a)
          (quadraticInterlacingPencil F G H a)) :
        StrictInterl
          (quadraticInterlacingTangent F G a)
          (quadraticInterlacingRight G H a)

Lean source RealRooted/Challenges/Preservers/MonomialChainOperator.lean at revision d6670742. Formalized 2026-05-12.