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.
- If $f\ll h$ and $g\ll h$, then $f+g\ll h$.
- If $h\ll f$ and $h\ll g$, then $h\ll f+g$.
- 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.
- [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
def weightedSum : List (ℝ × ℝ[X]) → ℝ[X]
| [] => 0
| (a, p) :: l => C a * p + weightedSum l
⊢ Theorems
A sum of polynomials interlacing h interlaces hMain result
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
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
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
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
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
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
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
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
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
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
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.