Ma–Wang endpoint steps

Ma and Wang study sequences of real-rooted polynomials generated by first-order differential recurrences whose roots stay in a window $[-c,0)$. Whether a step keeps the roots in the window depends on the multiplicity of the endpoint $-c$ as a root, and this classifies the affine recurrences with confined roots.

Results

For $c,a,b\in\mathbb R$ let $$ E_{c,a,b}(p)=(ax+b)\,p+x(x+c)\,p'. $$

Theorem (one step, Ma–Wang). Let $a>0$, and let $p$ be real-rooted with positive leading coefficient and all roots in $[-c,0)$. Then $E_{c,a,b}(p)$ has degree $\deg p+1$, positive leading coefficient, and $p\ll E_{c,a,b}(p)$. Let $m$ be the multiplicity of $-c$ as a root of $p$. The multiplicity of $-c$ in $E_{c,a,b}(p)$ is $m+1$ if $b=c(a+m)$ and $m$ otherwise. If also $b>0$, all roots of $E_{c,a,b}(p)$ lie in $[-c,0)$ if and only if $b\le c\,(a+m)$.

Theorem (classification). Let $c>0$, $\lambda>0$ and $0\le\mu<a$, let $P_0$ be real-rooted with positive leading coefficient and roots in $(-c,0)$, and let $$ P_{n+1}=\rho_n\,E_{c,a,\,c(a+\lambda n-\mu)}(P_n)\qquad(\rho_n>0). $$ Then all $P_n$ have their roots in $[-c,0)$ if and only if $\lambda=1/L$ and $\mu=r/L$ for integers $L\ge1$ and $r\ge0$. In that case every $P_n$ is real-rooted with positive leading coefficient, $P_n\ll P_{n+1}$, and the multiplicity of $-c$ in $P_n$ is $\lceil\max(n-r,0)/L\rceil$; for $L=2$ and $r=1$ this is $\lceil(n-1)/2\rceil$.

Proposition (closed window). Let $a>0$, $c\in\mathbb R$, and let $f$ be real-rooted with positive leading coefficient and roots in $[-1,0]$, with $m_0$ and $m_{-1}$ the multiplicities of $0$ and $-1$. Then $g=(ax+c)f+x(x+1)f'$ has degree $\deg f+1$, positive leading coefficient, and $f\ll g$. All roots of $g$ lie in $[-1,0]$ if and only if $0\le c+m_0$ and $0\le a+m_{-1}-c$. The multiplicity of $0$ in $g$ is $m_0+1$ if $c+m_0=0$ and $m_0$ otherwise; that of $-1$ is $m_{-1}+1$ if $c=a+m_{-1}$ and $m_{-1}$ otherwise.

Theorem (growing zero multiplicity). Let $u,v\ge0$ and let $f\ne0$ be a Pólya frequency polynomial with $v\deg f<b$. Then $(a+bx)f+x(u-vx)f'$ has degree $\deg f+1$, interlaces $f$, and is a Pólya frequency polynomial if and only if $0\le a+u\cdot\operatorname{mult}_0(f)$. Let $P_0=1$ and $$ P_{n+1}=\bigl((a-n)+(bn+c)x\bigr)P_n+r\,x(1-x)P_n'. $$ If $a=A$ and $r=R$ are natural numbers with $R>0$, and $b\ge R$ and $c>0$, then every $P_n$ is a Pólya frequency polynomial of degree $n$, $P_n\ll P_{n+1}$, and the multiplicity of the root $0$ of $P_n$ is $\lceil\max(n-A,0)/R\rceil$. Conversely, if $0<r\le b$ and $c>0$, all rows are Pólya frequency polynomials if and only if $a$ and $r$ are natural numbers.

References

[MW08, Theorem 2 and Corollary 3]. The closed-window step is an instance of the interval differential steps on the page on basis transforms.

  1. [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}
    }

Definitions

  • The step p ↦ (aX + b) p + X (X + c) p'

    RealRooted.MaWang.endpointStepsource
    def endpointStep (c a b : ℝ) (p : ℝ[X]) : ℝ[X] :=
      (C a * X + C b) * p + X * (X + C c) * p.derivative
  • The ceiling-division multiplicity at the endpoint

    RealRooted.MaWang.affineEndpointMultiplicitysource
    def affineEndpointMultiplicity (L r n : ℕ) : ℕ := (n - r) ⌈/⌉ L
  • The step f ↦ (a + bX) f + X (u - vX) f'

    RealRooted.growingZeroStepsource
    @[expose] def growingZeroStep (a b u v : ℝ) (f : ℝ[X]) : ℝ[X] :=
      (C u * X + C (-v) * X ^ 2) * f.derivative +
        (C a + C b * X) * f

Theorems

  • The multiplicity of the endpoint -c after one step

    RealRooted.MaWang.endpointStep_rootMultiplicitysource
    theorem endpointStep_rootMultiplicity {c a b : ℝ} {p : ℝ[X]}
        (ha : 0 < a) (hp : HasPosLeadingCoeff p) (hs : p.Splits)
        (hroots : ∀ r ∈ p.roots, -c ≤ r ∧ r < 0) :
        (endpointStep c a b p).rootMultiplicity (-c) =
          if b = c * (a + p.rootMultiplicity (-c))
          then p.rootMultiplicity (-c) + 1 else p.rootMultiplicity (-c)
  • The roots stay in [-c, 0) exactly when b ≤ c (a + multiplicity of -c)

    RealRooted.MaWang.endpointStep_roots_mem_Ico_iffsource
    theorem endpointStep_roots_mem_Ico_iff {c a b : ℝ} {p : ℝ[X]}
        (ha : 0 < a) (hb : 0 < b) (hp : HasPosLeadingCoeff p) (hs : p.Splits)
        (hroots : ∀ r ∈ p.roots, -c ≤ r ∧ r < 0) :
        (∀ r ∈ (endpointStep c a b p).roots, -c ≤ r ∧ r < 0) ↔
          b ≤ c * (a + p.rootMultiplicity (-c))
  • The step interlaces its input

    RealRooted.MaWang.endpointStep_strictInterlsource
    theorem endpointStep_strictInterl {c a b : ℝ} {p : ℝ[X]}
        (ha : 0 < a) (hp : HasPosLeadingCoeff p) (hs : p.Splits)
        (hroots : ∀ r ∈ p.roots, -c ≤ r ∧ r < 0) :
        StrictInterl p (endpointStep c a b p)
  • Slope 1/L, intercept r/L: roots in [-c, 0), interlacing, multiplicity ⌈(n - r)/L⌉

    RealRooted.MaWang.affineEndpointSequencesource
    theorem affineEndpointSequence {P : ℕ → ℝ[X]} {c a : ℝ} {rho : ℕ → ℝ}
        (L r : ℕ) (hc : 0 < c) (hL : 0 < L) (ha : (r : ℝ) / L < a)
        (hrec : ∀ n, P (n + 1) = C (rho n) *
          endpointStep c a (c * (a + (n : ℝ) / L - (r : ℝ) / L)) (P n))
        (hrho : ∀ n, 0 < rho n)
        (h0pos : HasPosLeadingCoeff (P 0)) (h0s : (P 0).Splits)
        (h0roots : ∀ z ∈ (P 0).roots, -c < z ∧ z < 0) :
        ∀ n, HasPosLeadingCoeff (P n) ∧ (P n).Splits ∧
          (∀ z ∈ (P n).roots, -c ≤ z ∧ z < 0) ∧
          (P n).rootMultiplicity (-c) = affineEndpointMultiplicity L r n ∧
          StrictInterl (P n) (P (n + 1))
  • Converse: confinement of all rows forces slope 1/L and intercept r/L

    RealRooted.MaWang.affineEndpointParameters_of_roots_mem_Icosource
    theorem affineEndpointParameters_of_roots_mem_Ico
        {P : ℕ → ℝ[X]} {c a lambda mu : ℝ} {rho : ℕ → ℝ}
        (hc : 0 < c) (hlambda : 0 < lambda) (hmu : 0 ≤ mu) (ha : mu < a)
        (hrec : ∀ n, P (n + 1) = C (rho n) *
          endpointStep c a (c * (a + lambda * (n : ℝ) - mu)) (P n))
        (hrho : ∀ n, 0 < rho n)
        (h0pos : HasPosLeadingCoeff (P 0)) (h0s : (P 0).Splits)
        (h0roots : ∀ z ∈ (P 0).roots, -c < z ∧ z < 0)
        (hall : ∀ n z, z ∈ (P n).roots → -c ≤ z ∧ z < 0) :
        ∃ L r : ℕ, 0 < L ∧ lambda = 1 / (L : ℝ) ∧ mu = (r : ℝ) / L
  • Classification of the affine endpoint sequences with confined rootsMain result

    RealRooted.MaWang.affineEndpointSequence_roots_mem_Ico_iffsource
    theorem affineEndpointSequence_roots_mem_Ico_iff
        {P : ℕ → ℝ[X]} {c a lambda mu : ℝ} {rho : ℕ → ℝ}
        (hc : 0 < c) (hlambda : 0 < lambda) (hmu : 0 ≤ mu) (ha : mu < a)
        (hrec : ∀ n, P (n + 1) = C (rho n) *
          endpointStep c a (c * (a + lambda * (n : ℝ) - mu)) (P n))
        (hrho : ∀ n, 0 < rho n)
        (h0pos : HasPosLeadingCoeff (P 0)) (h0s : (P 0).Splits)
        (h0roots : ∀ z ∈ (P 0).roots, -c < z ∧ z < 0) :
        (∀ n z, z ∈ (P n).roots → -c ≤ z ∧ z < 0) ↔
          ∃ L r : ℕ, 0 < L ∧ lambda = 1 / (L : ℝ) ∧ mu = (r : ℝ) / L
  • The slope-one-half case

    RealRooted.MaWang.halfSlopeEndpointSequencesource
    theorem halfSlopeEndpointSequence
        {P : ℕ → ℝ[X]} {c a : ℝ} {rho : ℕ → ℝ}
        (hc : 0 < c) (ha : (1 : ℝ) / 2 < a)
        (hrec : ∀ n, P (n + 1) = C (rho n) *
          endpointStep c a (c * (a + (n : ℝ) / 2 - (1 : ℝ) / 2)) (P n))
        (hrho : ∀ n, 0 < rho n)
        (h0pos : HasPosLeadingCoeff (P 0)) (h0s : (P 0).Splits)
        (h0roots : ∀ z ∈ (P 0).roots, -c < z ∧ z < 0) :
        ∀ n, HasPosLeadingCoeff (P n) ∧ (P n).Splits ∧
          (∀ z ∈ (P n).roots, -c ≤ z ∧ z < 0) ∧
          (P n).rootMultiplicity (-c) = affineEndpointMultiplicity 2 1 n ∧
          StrictInterl (P n) (P (n + 1))
  • The closed two-endpoint step (aX + c) f + X (X + 1) f' on [-1, 0]

    RealRooted.affineEndpointStep_closedsource
    theorem affineEndpointStep_closed {a c : ℝ} {p : ℝ[X]}
        (ha : 0 < a) (hp : HasPosLeadingCoeff p) (hs : p.Splits)
        (hroots : ∀ r ∈ p.roots, r ∈ Icc (-1 : ℝ) 0) :
        (MaWang.endpointStep 1 a c p).natDegree = p.natDegree + 1 ∧
          HasPosLeadingCoeff (MaWang.endpointStep 1 a c p) ∧
          (MaWang.endpointStep 1 a c p).Splits ∧
          Interlaces p (MaWang.endpointStep 1 a c p) ∧
          ((∀ r ∈ (MaWang.endpointStep 1 a c p).roots, r ∈ Icc (-1 : ℝ) 0) ↔
            0 ≤ c + p.rootMultiplicity 0 ∧
              0 ≤ a + p.rootMultiplicity (-1) - c) ∧
          ((MaWang.endpointStep 1 a c p).rootMultiplicity 0 =
            if c + p.rootMultiplicity 0 = 0 then p.rootMultiplicity 0 + 1
            else p.rootMultiplicity 0) ∧
          (MaWang.endpointStep 1 a c p).rootMultiplicity (-1) =
            if c = a + p.rootMultiplicity (-1) then p.rootMultiplicity (-1) + 1
            else p.rootMultiplicity (-1)
  • Roots stay in [-1, 0] iff 0 ≤ c + m₀ and 0 ≤ a + m₋₁ - c

    RealRooted.affineEndpointStep_roots_mem_Icc_iffsource
    theorem affineEndpointStep_roots_mem_Icc_iff {a c : ℝ} {p : ℝ[X]}
        (ha : 0 < a) (hp : HasPosLeadingCoeff p) (hs : p.Splits)
        (hroots : ∀ r ∈ p.roots, r ∈ Icc (-1 : ℝ) 0) :
        (∀ r ∈ (MaWang.endpointStep 1 a c p).roots, r ∈ Icc (-1 : ℝ) 0) ↔
          0 ≤ c + p.rootMultiplicity 0 ∧
            0 ≤ a + p.rootMultiplicity (-1) - c
  • The PF threshold depends on the multiplicity of the root zero: 0 ≤ a + u m₀

    RealRooted.growingZeroStep_isPFPolynomial_iffsource
    theorem growingZeroStep_isPFPolynomial_iff
        {a b u v : ℝ} {f : ℝ[X]} (hf : IsPFPolynomial f) (hf0 : f ≠ 0)
        (hu : 0 ≤ u) (hv : 0 ≤ v)
        (hraise : v * (f.natDegree : ℝ) < b) :
        IsPFPolynomial (growingZeroStep a b u v f) ↔
          0 ≤ a + u * (f.rootMultiplicity 0 : ℝ)
  • The integer growing-zero family is PF and interlacing, with endpoint multiplicity at zero

    RealRooted.growingZeroFamily_pf_degree_multiplicity_interlacingsource
    theorem growingZeroFamily_pf_degree_multiplicity_interlacing
        (A R : ℕ) {b c : ℝ} (hR : 0 < R) (hb : (R : ℝ) ≤ b) (hc : 0 < c) :
        ∀ n : ℕ,
          IsPFPolynomial (growingZeroFamily A R b c n) ∧
          (growingZeroFamily A R b c n).natDegree = n ∧
          (growingZeroFamily A R b c n).rootMultiplicity 0 =
            MaWang.affineEndpointMultiplicity R A n ∧
          StrictInterl (growingZeroFamily A R b c n)
            (growingZeroFamily A R b c (n + 1)) ∧
          (growingZeroFamily A R b c n).leadingCoeff =
            (Finset.range n).prod fun j => (b - R) * j + c
  • All rows of the growing-zero family are PF exactly for integer parameters

    RealRooted.growingZeroFamily_all_isPFPolynomial_iffsource
    theorem growingZeroFamily_all_isPFPolynomial_iff
        {a r b c : ℝ} (hr : 0 < r) (hb : r ≤ b) (hc : 0 < c) :
        (∀ n, IsPFPolynomial (growingZeroFamily a r b c n)) ↔
          ∃ A R : ℕ, 0 < R ∧ a = A ∧ r = R

Lean source RealRooted/Challenges/Interlacing/MaWangEndpointSteps.lean at revision d6670742. Formalized 2026-11-01.