Wagner’s lemma

Interlacing is preserved by sums of polynomials with a common interlacing partner, and multiplication by $x$ reverses it for polynomials with nonpositive roots.

Results

Theorem (Wagner's lemma). Let $f,g$ have positive leading coefficients.

  1. If $f\ll h$ and $g\ll h$, then $f+g\ll h$.
  2. If $h\ll f$ and $h\ll g$, then $h\ll f+g$.
  3. If all real roots of $f$ and $g$ are nonpositive, then $f\ll g$ if and only if $g\ll xf$.

In particular, if $f\ll g$ and both have nonnegative coefficients, then $g\ll xf$.

Proposition (finite sums). Let $f_1,\dots,f_k$ have positive leading coefficients with $f_i\ll h$ for all $i$, and let $a_1,\dots,a_k\ge0$, not all zero. Then $\sum_ia_if_i\ll h$. In particular $\sum_if_i\ll h$ for $k\ge1$.

Proposition (nonnegative combinations). Let $f\ll g$ have positive leading coefficients and let $a,b\ge0$ be not both zero. Then $f\ll af+bg$ and $af+bg\ll g$.

Proposition (common factor). For $r\in\mathbb R$, $f\ll g$ if and only if $(x-r)f\ll(x-r)g$.

Proposition (chains). If $F_a\ll F_{a+1}\ll\dots\ll F_b$ and $F_a\ll F_b$, then $F_i\ll F_j$ for all $a\le i\le j\le b$.

References

[Wag92]. Part (1) is Wagner’s lemma on symmetricfunctions.com.

  1. [Wag92] David G Wagner. Total positivity of Hadamard products. Journal of Mathematical Analysis and Applications, 163(2), 459-483, 1992.
    BibTeX
    @article{Wagner1992,
      doi = {10.1016/0022-247x(92)90261-b},
      url2 = {https://doi.org/10.1016/0022-247x(92)90261-b},
      year = {1992},
      month = jan,
      publisher = {Elsevier {BV}},
      volume = {163},
      number = {2},
      pages = {459--483},
      author = {David G Wagner},
      title = {Total positivity of {H}adamard products},
      journal = {Journal of Mathematical Analysis and Applications}
    }

Definitions

  • The weighted sum of a list of weight–polynomial pairs

    RealRooted.weightedSumsource
    def weightedSum : List (ℝ × ℝ[X]) → ℝ[X]
      | [] => 0
      | (a, p) :: l => C a * p + weightedSum l

Theorems

  • A sum of polynomials interlacing h interlaces hMain result

    RealRooted.StrictInterl.add_of_right_of_posLeadingCoeffsource
    theorem StrictInterl.add_of_right_of_posLeadingCoeff {f g h : ℝ[X]}
        (hfh : StrictInterl f h) (hgh : StrictInterl g h)
        (hf_pos : HasPosLeadingCoeff f) (hg_pos : HasPosLeadingCoeff g) :
        StrictInterl (f + g) h
  • The common-left version

    RealRooted.StrictInterl.add_of_leftsource
    theorem StrictInterl.add_of_left {f g h : ℝ[X]}
        (hhf : StrictInterl h f) (hhg : StrictInterl h g)
        (hf_pos : HasPosLeadingCoeff f) (hg_pos : HasPosLeadingCoeff g) :
        StrictInterl h (f + g)
  • Multiplication by x reverses interlacing, in either degree pattern

    RealRooted.strictInterl_iff_mul_X_of_roots_nonpossource
    theorem strictInterl_iff_mul_X_of_roots_nonpos {f g : ℝ[X]}
        (hf_nonpos : ∀ r ∈ f.roots, r ≤ 0) (hg_nonpos : ∀ r ∈ g.roots, r ≤ 0) :
        StrictInterl f g ↔ StrictInterl g (X * f)
  • If f ≪ g, then f ≪ af + bg for a, b ≥ 0 not both zero

    RealRooted.StrictInterl.nonneg_combo_leftsource
    theorem StrictInterl.nonneg_combo_left {f g : ℝ[X]}
        (hfg : StrictInterl f g)
        (hf_pos : HasPosLeadingCoeff f) (hg_pos : HasPosLeadingCoeff g)
        {a b : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b)
        (hab : 0 < a ∨ 0 < b) :
        StrictInterl f (C a * f + C b * g)
  • If f ≪ g, then af + bg ≪ g for a, b ≥ 0 not both zero

    RealRooted.StrictInterl.nonneg_combo_rightsource
    theorem StrictInterl.nonneg_combo_right {f g : ℝ[X]}
        (hfg : StrictInterl f g)
        (hf_pos : HasPosLeadingCoeff f) (hg_pos : HasPosLeadingCoeff g)
        {a b : ℝ} (ha : 0 ≤ a) (hb : 0 ≤ b)
        (hab : 0 < a ∨ 0 < b) :
        StrictInterl (C a * f + C b * g) g
  • A consecutive chain with interlacing endpoints is an interlacing sequence

    RealRooted.strictInterl_chain_of_consecutive_of_endpointsource
    theorem strictInterl_chain_of_consecutive_of_endpoint (F : ℕ → ℝ[X]) (a b : ℕ)
        (hcons : ∀ k, a ≤ k → k < b → StrictInterl (F k) (F (k + 1)))
        (hext : StrictInterl (F a) (F b)) :
        ∀ i j, a ≤ i → i ≤ j → j ≤ b → StrictInterl (F i) (F j)
  • Wagner's sum theorem when f + g has no root in common with h

    RealRooted.StrictInterl.add_of_right_of_no_common_rightsource
    theorem StrictInterl.add_of_right_of_no_common_right {f g h : ℝ[X]}
        (hfh : StrictInterl f h) (hgh : StrictInterl g h)
        (hf_pos : HasPosLeadingCoeff f) (hg_pos : HasPosLeadingCoeff g)
        (hno : ∀ r : ℝ, h.IsRoot r → ¬ (f + g).IsRoot r) :
        StrictInterl (f + g) h
  • A nonnegative weighted sum of polynomials interlacing h interlaces h

    RealRooted.StrictInterl.weightedSum_right_of_nonnegsource
    theorem StrictInterl.weightedSum_right_of_nonneg :
        ∀ (l : List (ℝ × ℝ[X])) (h : ℝ[X]),
          (∀ ap ∈ l, 0 ≤ ap.1) →
          (∀ ap ∈ l, StrictInterl ap.2 h) →
          (∀ ap ∈ l, HasPosLeadingCoeff ap.2) →
          (∃ ap ∈ l, 0 < ap.1) →
          StrictInterl (weightedSum l) h
  • A finite sum of polynomials interlacing h interlaces h

    RealRooted.StrictInterl.sum_rightsource
    theorem StrictInterl.sum_right
        (l : List ℝ[X]) (h : ℝ[X])
        (hstrictInterl : ∀ p ∈ l, StrictInterl p h)
        (hpos : ∀ p ∈ l, HasPosLeadingCoeff p)
        (hne : l ≠ []) :
        StrictInterl l.sum h
  • If f ≪ g and both have nonnegative coefficients, then g ≪ xf

    RealRooted.strictInterl_mul_X_of_strictInterl_of_nonnegsource
    theorem strictInterl_mul_X_of_strictInterl_of_nonneg {f g : ℝ[X]}
        (h : StrictInterl f g) (hfnn : HasNonnegCoeffs f) (hgnn : HasNonnegCoeffs g) :
        StrictInterl g (X * f)
  • Multiplying both sides by a common linear factor preserves interlacing, and conversely

    RealRooted.StrictInterl.mul_X_sub_C_both_iffsource
    theorem StrictInterl.mul_X_sub_C_both_iff {f g : ℝ[X]} (r : ℝ) :
        StrictInterl f g ↔ StrictInterl ((X - C r) * f) ((X - C r) * g)

Lean source RealRooted/Challenges/Interlacing/Wagner.lean at revision d6670742. Formalized 2026-07-10.