The Liu–Wang and Ma–Wang interlacing criteria

If an interlacer of $f$ is added to $af$ with a coefficient that is nonpositive at the roots of $f$, the sum is again interlaced by $f$; the same holds for $uf+vf'$ with $v\le0$ at the roots.

Results

A polynomial is positive if its leading coefficient is positive. The conclusion $f\ll F$ includes that $F$ is real-rooted.

Theorem (Liu–Wang). [LW07, Thm. 2.1] Let $f,g,a,b\in\mathbb R[x]$ and $F=af+bg$. Suppose that $g\ll f$, that $g$ and $F$ are positive, and that $\deg f\le\deg F\le\deg f+1$. If $b(r)\le0$ at every real root $r$ of $f$, then $f\ll F$.

Theorem (Ma–Wang). [MW08, Thm. 2] Let $f,u,v\in\mathbb R[x]$ and $F=uf+vf'$. Suppose that $f$ is real-rooted, that $f$ and $F$ are positive, and that $\deg f\le\deg F\le\deg f+1$. If $v(r)\le0$ at every root $r$ of $f$, then $f\ll F$.

Theorem (Ma–Wang, strict form). Suppose in addition that $\deg f\ne0$, that $f$ has simple roots, that $\deg F=\deg f+1$, and that $v(r)<0$ at every root $r$ of $f$. Then $f\ll F$ and $F$ has simple roots.

Theorem (general form). Let $f,a\in\mathbb R[x]$ and, for a finite index set $s$, let $g_i,b_i\in\mathbb R[x]$. Put $F=af+\sum_{i\in s}b_ig_i$. Suppose that $f$ is real-rooted and positive, that $g_i\ll f$ and $g_i$ is positive for each $i$, that $F$ is positive, and that $\deg f\le\deg F\le\deg f+1$. If $$ \Bigl(\sum_{i\in s}b_i(r)\,g_i(r)\Bigr)f'(r)\le0 $$ at every real root $r$ of $f$, and $b_i(r)\le0$ for every $i$ at every repeated root $r$ of $f$, then $f\ll F$. The Liu–Wang theorem, the Ma–Wang theorem and the finite-sum form below are special cases.

Theorem (finite sums). Let $f\ne0$ be real-rooted, with leading coefficient of either sign, and let $F=af+\sum_{i\in s}b_ig_i$ with $g_i\ll f$ and $g_i$ positive, $F$ positive and $\deg f\le\deg F\le\deg f+1$. If $b_i(r)\le0$ at every root $r$ of $f$ for each $i$, then $f\ll F$.

Theorem (sign criteria). Let $F$ be positive with $\deg f\le\deg F\le\deg f+1$. Then $f\ll F$ in each of the following cases:

Conversely, if $g\ll f$ and both are positive, then $g(r)f'(r)\ge0$ at every root $r$ of $f$.

Theorem (sequences). Let $(P_n)_{n\ge0}$ be positive with $P_0\ll P_1$ and $\deg P_{n+1}\le\deg P_{n+2}\le\deg P_{n+1}+1$ for all $n$. Then $P_n\ll P_{n+1}$ for all $n$ in each of the following cases; in particular every $P_n$ is real-rooted.

Theorem (derivative–lag step). Let $f\ne0$ be real-rooted and positive, let $g\ll f$ be positive, and put $F=uf+vf'+wg$. Suppose that $F$ is positive and $\deg f\le\deg F\le\deg f+1$. If $v(r)\le0$ and $w(r)\le0$ at every root $r$ of $f$, then $f\ll F$.

Use

The criteria give the interlacing of consecutive rows of polynomial families defined by recurrences or by first-order differential operators.

References

[LW07, Thm. 2.1]; [MW08, Thm. 2]; see also the Ma–Wang and Liu–Wang criteria on symmetricfunctions.com.

  1. [LW07] Lily L. Liu & Yi Wang. A unified approach to polynomial sequences with only real zeros. Advances in Applied Mathematics, 38(4), 542-560, 2007.
    BibTeX
    @article{LiuWang2007,
      doi = {10.1016/j.aam.2006.02.003},
      url2 = {https://doi.org/10.1016/j.aam.2006.02.003},
      year = {2007},
      month = may,
      publisher = {Elsevier {BV}},
      volume = {38},
      number = {4},
      pages = {542--560},
      author = {Lily L. Liu and Yi Wang},
      title = {A unified approach to polynomial sequences with only real zeros},
      journal = {Advances in Applied Mathematics}
    }
  2. [MW08] Shi-Mei Ma & Yi Wang. $q$-Eulerian polynomials and polynomials with only real zeros. The Electronic Journal of Combinatorics, 15(1), Research Paper 17, 2008.
    BibTeX
    @article{MaWang2008,
      doi = {10.37236/741},
      url2 = {https://doi.org/10.37236/741},
      year = {2008},
      month = jan,
      publisher = {The Electronic Journal of Combinatorics},
      volume = {15},
      number = {1},
      author = {Shi-Mei Ma and Yi Wang},
      title = {$q$-{E}ulerian Polynomials and Polynomials with Only Real Zeros},
      pages = {Research Paper 17},
      journal = {The Electronic Journal of Combinatorics}
    }

Theorems

  • General form: f ≪ af + Σ bᵢgᵢ from the combined flux at the zeros of fMain result

    RealRooted.LiuWang.strictInterl_mul_add_sum_mul_of_combined_flux_of_possource
    theorem strictInterl_mul_add_sum_mul_of_combined_flux_of_pos
        {ι : Type*} {f a : ℝ[X]} {s : Finset ι} {b g : ι → ℝ[X]}
        (hf_pos : HasPosLeadingCoeff f) (hf : f.Splits)
        (hg : ∀ i ∈ s, StrictInterl (g i) f)
        (hg_pos : ∀ i ∈ s, HasPosLeadingCoeff (g i))
        (hflux : ∀ r, f.IsRoot r →
          (∑ i ∈ s, b i * g i).eval r * f.derivative.eval r ≤ 0)
        (hrepeated : ∀ i ∈ s, ∀ r, f.IsRoot r → 1 < f.rootMultiplicity r →
          (b i).eval r ≤ 0)
        (hF_pos : HasPosLeadingCoeff (a * f + ∑ i ∈ s, b i * g i))
        (hdeg_lo : f.natDegree ≤ (a * f + ∑ i ∈ s, b i * g i).natDegree)
        (hdeg_hi : (a * f + ∑ i ∈ s, b i * g i).natDegree ≤ f.natDegree + 1) :
        StrictInterl f (a * f + ∑ i ∈ s, b i * g i)
  • f ≪ F when g interlaces f without common zeros and F g ≤ 0 at the zeros of f

    RealRooted.strictInterl_of_interlaces_eval_mul_nonpossource
    theorem strictInterl_of_interlaces_eval_mul_nonpos {f g F : ℝ[X]}
        (hgf : Interlaces g f) (hg_pos : HasPosLeadingCoeff g)
        (hF_pos : HasPosLeadingCoeff F)
        (hdeg_lo : f.natDegree ≤ F.natDegree) (hdeg_hi : F.natDegree ≤ f.natDegree + 1)
        (hno : ∀ r, f.IsRoot r → ¬ g.IsRoot r)
        (hsign : ∀ r, f.IsRoot r → F.eval r * g.eval r ≤ 0) :
        StrictInterl f F
  • Liu–Wang criterion: f ≪ af + bg when b ≤ 0 at the zeros of f

    RealRooted.LiuWang.strictInterl_mul_add_mul_of_eval_nonpossource
    theorem strictInterl_mul_add_mul_of_eval_nonpos {f g a b : ℝ[X]}
        (hgf : StrictInterl g f) (hg_pos : HasPosLeadingCoeff g)
        (hF_pos : HasPosLeadingCoeff (a * f + b * g))
        (hdeg_lo : f.natDegree ≤ (a * f + b * g).natDegree)
        (hdeg_hi : (a * f + b * g).natDegree ≤ f.natDegree + 1)
        (hb : ∀ r, f.IsRoot r → b.eval r ≤ 0) :
        StrictInterl f (a * f + b * g)
  • f ≪ F when F f' ≤ 0 at the simple zeros of f

    RealRooted.strictInterl_of_eval_mul_derivative_nonpossource
    theorem strictInterl_of_eval_mul_derivative_nonpos {f F : ℝ[X]}
        (hf_pos : HasPosLeadingCoeff f) (hf_splits : f.Splits) (hf_nodup : f.roots.Nodup)
        (hF_pos : HasPosLeadingCoeff F)
        (hdeg_lo : f.natDegree ≤ F.natDegree) (hdeg_hi : F.natDegree ≤ f.natDegree + 1)
        (hsign : ∀ r, f.IsRoot r → F.eval r * f.derivative.eval r ≤ 0) :
        StrictInterl f F
  • Ma–Wang criterion: f ≪ uf + vf' when v ≤ 0 at the zeros of f

    RealRooted.MaWang.strictInterl_derivative_of_nonpos_of_splitssourcestatement on symmetricfunctions.com
    theorem strictInterl_derivative_of_nonpos_of_splits {f u v : ℝ[X]}
        (hf : f.Splits)
        (hdeg_lo : f.natDegree ≤ (u * f + v * f.derivative).natDegree)
        (hdeg_hi : (u * f + v * f.derivative).natDegree ≤ f.natDegree + 1)
        (hF_pos : HasPosLeadingCoeff (u * f + v * f.derivative))
        (hf_pos : HasPosLeadingCoeff f)
        (hv_nonpos : ∀ r, f.IsRoot r → v.eval r ≤ 0) :
        StrictInterl f (u * f + v * f.derivative)
  • An interlacer g ≪ f has the sign of f' at the zeros of f

    RealRooted.StrictInterl.eval_mul_eval_derivative_nonnegsource
    theorem StrictInterl.eval_mul_eval_derivative_nonneg {g f : ℝ[X]} (hgf : StrictInterl g f)
        (hg_pos : HasPosLeadingCoeff g) (hf_pos : HasPosLeadingCoeff f) {r : ℝ}
        (hr : f.IsRoot r) :
        0 ≤ g.eval r * f.derivative.eval r
  • Strict Ma–Wang step: simple zeros propagate when v < 0

    RealRooted.MaWang.strictInterl_and_hasSimpleRoots_of_eval_negsource
    theorem MaWang.strictInterl_and_hasSimpleRoots_of_eval_neg {f F u v : ℝ[X]} (hf : f.Splits)
        (hf_pos : HasPosLeadingCoeff f) (hF_pos : HasPosLeadingCoeff F) (hdegf : f.natDegree ≠ 0)
        (hdeg : F.natDegree = f.natDegree + 1) (hsimple : HasSimpleRoots f)
        (hrec : F = u * f + v * f.derivative) (hv : ∀ r, f.IsRoot r → v.eval r < 0) :
        StrictInterl f F ∧ HasSimpleRoots F
  • Liu–Wang criterion for finite sums of interlacers, repeated roots allowed

    RealRooted.LiuWang.strictInterl_mul_add_sum_mul_of_eval_nonpossource
    theorem strictInterl_mul_add_sum_mul_of_eval_nonpos
        {ι : Type*} {f a : ℝ[X]} {s : Finset ι} {b g : ι → ℝ[X]}
        (hf_ne : f ≠ 0) (hf : f.Splits)
        (hg : ∀ i ∈ s, StrictInterl (g i) f)
        (hg_pos : ∀ i ∈ s, HasPosLeadingCoeff (g i))
        (hb : ∀ i ∈ s, ∀ r, f.IsRoot r → (b i).eval r ≤ 0)
        (hF_pos : HasPosLeadingCoeff (a * f + ∑ i ∈ s, b i * g i))
        (hdeg_lo : f.natDegree ≤ (a * f + ∑ i ∈ s, b i * g i).natDegree)
        (hdeg_hi : (a * f + ∑ i ∈ s, b i * g i).natDegree ≤ f.natDegree + 1) :
        StrictInterl f (a * f + ∑ i ∈ s, b i * g i)
  • Strict interlacing from strict critical signs

    RealRooted.strictInterl_of_eval_mul_derivative_negsource
    theorem strictInterl_of_eval_mul_derivative_neg
        {f F : ℝ[X]}
        (hf : f.Splits)
        (hf_pos : HasPosLeadingCoeff f)
        (hF_pos : HasPosLeadingCoeff F)
        (hdegf : f.natDegree ≠ 0)
        (hdeg_lo : f.natDegree ≤ F.natDegree)
        (hdeg_hi : F.natDegree ≤ f.natDegree + 1)
        (hsign : ∀ r, f.IsRoot r →
          F.eval r * f.derivative.eval r < 0) :
        StrictInterl f F
  • Liu–Wang criterion for three-term recurrences

    RealRooted.LiuWang.strictInterl_succ_of_recurrence_of_eval_nonpossource
    theorem strictInterl_succ_of_recurrence_of_eval_nonpos {P A B : ℕ → ℝ[X]}
        (hbase : StrictInterl (P 0) (P 1))
        (hpos : ∀ n, HasPosLeadingCoeff (P n))
        (hrec : ∀ n, P (n + 2) = A n * P (n + 1) + B n * P n)
        (hdeg_lo : ∀ n, (P (n + 1)).natDegree ≤ (P (n + 2)).natDegree)
        (hdeg_hi : ∀ n, (P (n + 2)).natDegree ≤ (P (n + 1)).natDegree + 1)
        (hB : ∀ n r, (P (n + 1)).IsRoot r → (B n).eval r ≤ 0) :
        ∀ n, StrictInterl (P n) (P (n + 1))
  • Ma–Wang criterion for derivative recurrences

    RealRooted.MaWang.strictInterl_derivative_nonpos_sequencesource
    theorem strictInterl_derivative_nonpos_sequence {P : Nat → ℝ[X]}
        {U V : Nat → ℝ[X]}
        (hbase : StrictInterl (P 0) (P 1))
        (hpos : ∀ n : Nat, HasPosLeadingCoeff (P n))
        (hV_nonpos : ∀ n : Nat, ∀ r, (P (n + 1)).IsRoot r → (V n).eval r ≤ 0)
        (hrec : ∀ n : Nat,
          P (n + 2) = U n * P (n + 1) + V n * (P (n + 1)).derivative)
        (hdeg_lo : ∀ n : Nat, (P (n + 1)).natDegree ≤ (P (n + 2)).natDegree)
        (hdeg_hi : ∀ n : Nat, (P (n + 2)).natDegree ≤ (P (n + 1)).natDegree + 1) :
        ∀ n : Nat, StrictInterl (P n) (P (n + 1))
  • Liu–Wang step with an additional derivative term

    RealRooted.LiuWang.strictInterl_derivative_lag_of_eval_nonpossource
    theorem strictInterl_derivative_lag_of_eval_nonpos
        {f g u v w : ℝ[X]}
        (hf_ne : f ≠ 0) (hf : f.Splits) (hf_pos : HasPosLeadingCoeff f)
        (hgf : StrictInterl g f) (hg_pos : HasPosLeadingCoeff g)
        (hF_pos : HasPosLeadingCoeff (u * f + v * f.derivative + w * g))
        (hdeg_lo : f.natDegree ≤ (u * f + v * f.derivative + w * g).natDegree)
        (hdeg_hi : (u * f + v * f.derivative + w * g).natDegree ≤ f.natDegree + 1)
        (hv_nonpos : ∀ r, f.IsRoot r → v.eval r ≤ 0)
        (hw_nonpos : ∀ r, f.IsRoot r → w.eval r ≤ 0) :
        StrictInterl f (u * f + v * f.derivative + w * g)
  • Liu–Wang criterion for derivative–lag recurrences

    RealRooted.LiuWang.strictInterl_sequence_of_derivative_lagsource
    theorem strictInterl_sequence_of_derivative_lag
        {P : Nat → ℝ[X]} {U V W : Nat → ℝ[X]}
        (hbase : StrictInterl (P 0) (P 1))
        (hpos : ∀ n : Nat, HasPosLeadingCoeff (P n))
        (hrec : ∀ n : Nat,
          P (n + 2) =
            U n * P (n + 1) + V n * (P (n + 1)).derivative + W n * P n)
        (hV_nonpos :
          ∀ n : Nat, P (n + 1) ≠ 0 ∧ (P (n + 1)).Splits →
            ∀ r, (P (n + 1)).IsRoot r → (V n).eval r ≤ 0)
        (hW_nonpos :
          ∀ n : Nat, P (n + 1) ≠ 0 ∧ (P (n + 1)).Splits →
            ∀ r, (P (n + 1)).IsRoot r → (W n).eval r ≤ 0)
        (hdeg_lo : ∀ n : Nat, (P (n + 1)).natDegree ≤ (P (n + 2)).natDegree)
        (hdeg_hi : ∀ n : Nat, (P (n + 2)).natDegree ≤ (P (n + 1)).natDegree + 1) :
        ∀ n : Nat, StrictInterl (P n) (P (n + 1))

Lean source RealRooted/Challenges/Interlacing/MaWangLiuWang.lean at revision d6670742. Formalized 2026-10-06.