Wang–Yeh criterion

If $g\ll f$ have positive leading coefficients and $bc\le ad$, then $(bx+a)f+(dx+c)g$ is zero or real-rooted. Specializations give a bidiagonal preserver of PF polynomials and PF rows for triangular arrays with bilinear recurrences, such as the Eulerian and Stirling triangles.

Results

A polynomial is PF if it has nonnegative coefficients and is zero or real-rooted with only nonpositive roots. A sequence is PF if its Toeplitz matrix is totally nonnegative.

Theorem (Wang–Yeh). Let $f,g\in\mathbb R[x]$ have positive leading coefficients with $g\ll f$, and let $a,b,c,d\in\mathbb R$ satisfy $bc\le ad$. Then $$ (bx+a)\,f(x)+(dx+c)\,g(x) $$ is zero or real-rooted.

Corollary (PF preserver). Let $p=\sum_ku_kx^k$ be PF and let $a,b,c,d\in\mathbb R$ satisfy $bc\le ad$. Put $$ v_k=(a+c(k-1))\,u_{k-1}+(b+dk)\,u_k,\qquad u_{-1}=0. $$ If every $v_k$ is nonnegative, then $\sum_kv_kx^k$ is PF.

Corollary (bilinear triangular arrays). Let $A(n,k)$ be a nonnegative lower-triangular array with $A(0,0)=1$, $A(n+1,0)=(a(n+1)+c)A(n,0)$ and $$ A(n+1,k+1)=(r(n+1)+s(k+1)+t)\,A(n,k)+(a(n+1)+b(k+1)+c)\,A(n,k+1) $$ for all $n,k\ge0$. If $$ as\le rb\qquad\text{and}\qquad(a+c)s\le(r+s+t)b, $$ then every row $(A(n,0),A(n,1),\dotsc)$ is a PF sequence. Equivalently, every row polynomial $\sum_kA(n,k)x^k$ is PF.

Proof

By the Hermite–Biehler theorem, $g\ll f$ makes $f+ig$ stable in the upper half-plane, and multiplying by $(b-id)x+(a-ic)$, whose zero lies in the closed lower half-plane exactly when $bc\le ad$, keeps it stable; the real part of the product is $(bx+a)f+(dx+c)g$. For the PF preserver, the image of $p$ is $(ax+b)p+(cx+d)xp'$, and $p\ll xp'$. Each row of the triangular array is such an image of the previous row.

References

  1. [WY05] Yi Wang & Yeong-Nan Yeh. Polynomials with real zeros and Pólya frequency sequences. Journal of Combinatorial Theory, Series A, 109(1), 63-74, 2005.
    BibTeX
    @article{WangYeh2005,
      author = {Yi Wang and Yeong-Nan Yeh},
      title = {Polynomials with real zeros and {P}{\'o}lya frequency sequences},
      year = {2005},
      journal = {Journal of Combinatorial Theory, Series A},
      volume = {109},
      number = {1},
      pages = {63--74},
      doi = {10.1016/j.jcta.2004.07.008},
      url = {https://doi.org/10.1016/j.jcta.2004.07.008},
      eprint = {math/0611825}
    }

Definitions

  • Coefficient-bidiagonal operator

    RealRooted.bidiagonalOperatorsource
    def bidiagonalOperator (alpha beta : ℕ → ℝ) (p : ℝ[X]) : ℝ[X] :=
      diagonalOperator alpha p + X * diagonalOperator beta p

Theorems

  • (bx + a) f + (dx + c) g is real-rooted or zero when ad ≥ bcMain result

    RealRooted.wangYehAffine_eq_zero_or_splitssourcestatement on symmetricfunctions.com
    theorem wangYehAffine_eq_zero_or_splits
        {f g : ℝ[X]} {a b c d : ℝ}
        (hgf : StrictInterl g f)
        (hf_pos : HasPosLeadingCoeff f) (hg_pos : HasPosLeadingCoeff g)
        (hdet : b * c ≤ a * d) :
        (C b * X + C a) * f + (C d * X + C c) * g = 0 ∨
          ((C b * X + C a) * f + (C d * X + C c) * g).Splits
  • Affine bidiagonal transforms preserve Pólya-frequency polynomials

    RealRooted.IsPFPolynomial.wangYeh_bidiagonalsourcestatement on symmetricfunctions.com
    theorem IsPFPolynomial.wangYeh_bidiagonal
        {p : ℝ[X]} {a b c d : ℝ} (hp : IsPFPolynomial p)
        (hdet : b * c ≤ a * d)
        (hout : HasNonnegCoeffs
          (bidiagonalOperator (fun k => b + d * (k : ℝ))
            (fun k => a + c * (k : ℝ)) p)) :
        IsPFPolynomial
          (bidiagonalOperator (fun k => b + d * (k : ℝ))
            (fun k => a + c * (k : ℝ)) p)
  • Rows of a bilinear triangular recurrence are Pólya-frequency sequences

    RealRooted.IsPolyaFreqSeq.row_of_bilinear_recurrencesource
    theorem IsPolyaFreqSeq.row_of_bilinear_recurrence (A : ℕ → ℕ → ℝ) (r s t a b c : ℝ)
        (hlower : ∀ i j, i < j → A i j = 0) (hbase : A 0 0 = 1)
        (hzero : ∀ n, A (n + 1) 0 = (a * (n + 1 : ℝ) + c) * A n 0)
        (hsucc : ∀ n k, A (n + 1) (k + 1) =
          (r * (n + 1 : ℝ) + s * (k + 1 : ℝ) + t) * A n k +
            (a * (n + 1 : ℝ) + b * (k + 1 : ℝ) + c) * A n (k + 1))
        (hnonneg : ∀ n k, 0 ≤ A n k) (hrb : a * s ≤ r * b)
        (hboundary : (a + c) * s ≤ (r + s + t) * b) (n : ℕ) :
        IsPolyaFreqSeq (A n)
  • Row polynomials of a bilinear triangular recurrence are Pólya-frequency

    RealRooted.wangYeh_triangularRows_pfsource
    theorem wangYeh_triangularRows_pf
        (P : ℕ → ℝ[X]) (r s t a b c : ℝ)
        (hbase : P 0 = 1)
        (hzero : ∀ n,
          (P (n + 1)).coeff 0 =
            (a * (n + 1 : ℝ) + c) * (P n).coeff 0)
        (hsucc : ∀ n k,
          (P (n + 1)).coeff (k + 1) =
            (r * (n + 1 : ℝ) + s * (k + 1 : ℝ) + t) * (P n).coeff k +
              (a * (n + 1 : ℝ) + b * (k + 1 : ℝ) + c) *
                (P n).coeff (k + 1))
        (hnonneg : ∀ n, HasNonnegCoeffs (P n))
        (hrb : a * s ≤ r * b)
        (hboundary : (a + c) * s ≤ (r + s + t) * b) :
        ∀ n, IsPFPolynomial (P n)

Lean source RealRooted/Challenges/Preservers/WangYeh.lean at revision d6670742. Formalized 2026-10-06.