Finite-degree tests for differential operators

A constant-coefficient operator $h(D)$ preserves Pólya frequency polynomials of degree at most $N$ if and only if the single polynomial $h(D)\,x^N$ is Pólya frequency. The same kind of test holds for pairs of operators with interlacing images and for the even-derivative operators $f\mapsto\sum_kc_kx^kf^{(2k)}$.

Results

A polynomial is PF (Pólya frequency) if it is zero or has nonnegative coefficients and only real nonpositive roots. Interlacing statements here use the zero-aware convention. For a real polynomial $h=\sum_jh_jx^j$ and $D=d/dx$ let $h(D)=\sum_jh_jD^j$. The degree-$N$ test of $h$ and its reversal, the Jensen test, are $$ T_N(h)=h(D)\,x^N=\sum_{j\le N}\frac{N!}{(N-j)!}\,h_j\,x^{N-j},\qquad J_N(h)=\sum_{j\le N}\frac{N!}{(N-j)!}\,h_j\,x^{j}. $$ For $\deg p\le N$, the finite free additive convolution of the test with $p$ is $T_N(h)\boxplus_Np=h(D)p$.

Theorem (scalar test). $h(D)$ maps every PF polynomial of degree at most $N$ to a PF polynomial if and only if $T_N(h)$ is PF.

Theorem (ordered tests). For real polynomials $h,k$ the following are equivalent.

  1. For every PF polynomial $p$ of degree at most $N$, the polynomials $h(D)p$ and $k(D)p$ are PF and $h(D)p\ll k(D)p$.
  2. $T_N(h)$ and $T_N(k)$ are PF and $T_N(h)\ll T_N(k)$.
  3. $J_N(h)$ and $J_N(k)$ are PF and $J_N(k)\ll J_N(h)$.

If $h\ne0$ is PF, then (1) holds for every $N$ if and only if $k$ is PF and $k\ll h$, and this happens exactly when $k$ is a nonnegative combination of $h$ and of the quotients $h/(x-u)$ with $h(u)=0$.

Theorem (even derivatives). Let $c_0=1$ and $c_k\ge0$, and put $$ \Delta_cf=\sum_{k\ge0}c_k\,x^kf^{(2k)},\qquad p_N(z)=\sum_{k\le N/2}(-1)^kc_k\,(N)_{2k}\,z^{N-2k}, $$ where $(N)_j=N(N-1)\dotsm(N-j+1)$. The following are equivalent: $\Delta_c$ maps every PF polynomial of degree at most $N$ to a PF polynomial; $\Delta_c(x^N)$ is real-rooted; $p_N$ is real-rooted. If $c_k=0$ for $k>M$ and the signed symbol $\sum_{k\le M}(-1)^kc_kw^{2k}$ is real-rooted, then this holds for every $N$.

For $c=(1,1,1,0,\dotsc)$ we get $\Delta_c(x^4)=x^2(x^2+12x+24)$ and $\Delta_c(x^5)=x^3(x^2+20x+120)$, so $\Delta_c$ preserves PF polynomials up to degree four but not five. For $c=(1,2,1,0,\dotsc)$ it preserves them in every degree.

Further results cover binomial symbols, with $J_N(h)=(sx+1)^r$ and $J_N(k)=(sx+1)^{r-1}$; the recurrence rows $x\,h(D)p+a\,k(D)p$ with $a\ge0$, which are PF and interlaced by $h(D)p$, and their multishift versions; and, when $p_N$ is real-rooted, preservation of interlacing by $\Delta_c$ through degree $N$.

Proof

Substituting $x=-z^2$ gives $\Delta_c(x^N)(-z^2)=(-1)^Nz^Np_N(z)$, which relates the last two conditions of the even-derivative theorem. The step from $p_N$ to all PF inputs uses the real stability of the symmetric polarization of $p_N$ and the Grace–Walsh–Szegő theorem [BB09, Theorem 2.3 and Proposition 2.4].

References

  1. [BB09] Julius Borcea & Petter Brändén. The Lee–Yang and Pólya–Schur programs. I. Linear operators preserving stability. Inventiones mathematicae, 177(3), 541-569, 2009.
    BibTeX
    @article{BorceaBranden2009I,
      doi = {10.1007/s00222-009-0189-3},
      url2 = {https://doi.org/10.1007/s00222-009-0189-3},
      year = {2009},
      month = mar,
      publisher = {Springer Science and Business Media {LLC}},
      volume = {177},
      number = {3},
      pages = {541--569},
      author = {Julius Borcea and Petter Br{\"{a}}nd{\'{e}}n},
      title = {The {L}ee--{Y}ang and {P}{\'{o}}lya--{S}chur programs. {I}. {L}inear operators preserving stability},
      journal = {Inventiones mathematicae}
    }

Definitions

  • The degree-N test h(D) X^N

    RealRooted.finiteDifferentialTestsource
    def finiteDifferentialTest (N : ℕ) (h : ℝ[X]) : ℝ[X] :=
      applyAsDifferentialOperator h (X ^ N)
  • Two symbols give ordered PF images through degree N

    RealRooted.PreservesOrderedPFUpTosource
    def PreservesOrderedPFUpTo (N : ℕ) (h k : ℝ[X]) : Prop :=
      ∀ {p : ℝ[X]}, IsPFPolynomial p → p.natDegree ≤ N →
        IsPFPolynomial (applyAsDifferentialOperator h p) ∧
          IsPFPolynomial (applyAsDifferentialOperator k p) ∧
            Interl (applyAsDifferentialOperator h p)
              (applyAsDifferentialOperator k p)
  • A nonnegative combination of h and quotients h/(x − u)

    RealRooted.HasKreinCompanionExpansionsource
    def HasKreinCompanionExpansion (h k : ℝ[X]) : Prop :=
      ∃ l : List (ℝ × ℝ[X]),
        k = weightedSum l ∧
          (∀ ap ∈ l, 0 ≤ ap.1) ∧
          ∀ ap ∈ l, IsKreinSummand h ap.2
  • The operator Δ_c f = ∑ cₖ xᵏ f^{(2k)}

    RealRooted.evenDerivativeOperatorsource
    def evenDerivativeOperator (c : ℕ → ℝ) (f : ℝ[X]) : ℝ[X] :=
      ∑ k ∈ Finset.range (f.natDegree / 2 + 1), C (c k) * X ^ k * derivative^[2 * k] f
  • The test polynomial p_N(z) = ∑ (-1)ᵏ cₖ (N)_{2k} z^{N-2k}

    RealRooted.evenDerivativeTestsource
    def evenDerivativeTest (c : ℕ → ℝ) (N : ℕ) : ℝ[X] :=
      ∑ k ∈ Finset.range (N / 2 + 1),
        C ((-1) ^ k * c k * (N.descFactorial (2 * k) : ℝ)) * X ^ (N - 2 * k)
  • The signed symbol ∑ (-1)ᵏ cₖ w^{2k}, so that p_N is the symbol applied to xᴺ

    RealRooted.evenDerivativeSymbolsource
    def evenDerivativeSymbol (c : ℕ → ℝ) (M : ℕ) : ℝ[X] :=
      ∑ k ∈ Finset.range (M + 1), C ((-1) ^ k * c k) * X ^ (2 * k)

Theorems

  • h(D) preserves PF polynomials of degree at most N exactly when h(D) X^N is PFMain resultRealRooted original

    RealRooted.PreservesPFUpTo.iff_finiteDifferentialTestsource
    theorem PreservesPFUpTo.iff_finiteDifferentialTest
        (N : ℕ) (h : ℝ[X]) :
        PreservesPFUpTo N h ↔ IsPFPolynomial (finiteDifferentialTest N h)
  • The finite free additive convolution with the test is the differential operatorRealRooted original

    RealRooted.finiteFreeAdditiveConvolution_finiteDifferentialTestsource
    theorem finiteFreeAdditiveConvolution_finiteDifferentialTest
        (N : ℕ) (h p : ℝ[X]) (hpdeg : p.natDegree ≤ N) :
        finiteFreeAdditiveConvolution N (finiteDifferentialTest N h) p =
          applyAsDifferentialOperator h p
  • Ordered PF images through degree N are detected by the two degree-N testsRealRooted original

    RealRooted.PreservesOrderedPFUpTo.iff_differentialTestssource
    theorem _root_.RealRooted.PreservesOrderedPFUpTo.iff_differentialTests
        (N : ℕ) (h k : ℝ[X]) :
        PreservesOrderedPFUpTo N h k ↔
          IsPFPolynomial (finiteDifferentialTest N h) ∧
            IsPFPolynomial (finiteDifferentialTest N k) ∧
              Interl (finiteDifferentialTest N h) (finiteDifferentialTest N k)
  • The same criterion through the reversed (Jensen) testsRealRooted original

    RealRooted.PreservesOrderedPFUpTo.iff_jensenDifferentialTestssource
    theorem _root_.RealRooted.PreservesOrderedPFUpTo.iff_jensenDifferentialTests
        (N : ℕ) (h k : ℝ[X]) :
        PreservesOrderedPFUpTo N h k ↔
          IsPFPolynomial (jensenDifferentialTest N h) ∧
            IsPFPolynomial (jensenDifferentialTest N k) ∧
              Interl (jensenDifferentialTest N k)
                (jensenDifferentialTest N h)
  • Binomial symbols with Jensen tests (sX + 1)^r, (sX + 1)^(r-1): ordered PF imagesRealRooted original

    RealRooted.PreservesOrderedPFUpTo.binomialDifferentialSymbolsource
    theorem _root_.RealRooted.PreservesOrderedPFUpTo.binomialDifferentialSymbol
        {N r : ℕ} {s : ℝ} (hr : r ≠ 0) (hrN : r ≤ N) (hs : 0 ≤ s) :
        PreservesOrderedPFUpTo N (binomialDifferentialSymbol N r s)
          (binomialDifferentialSymbol N (r - 1) s)
  • A binomial differential recurrence row is PF and preceded by the leading imageRealRooted original

    RealRooted.FiniteDegreeOrdered.binomialDifferentialRecurrence_pf_and_interlsource
    theorem binomialDifferentialRecurrence_pf_and_interl
        {N r : ℕ} {s a : ℝ} (hr : r ≠ 0) (hrN : r ≤ N)
        (hs : 0 ≤ s) (ha : 0 ≤ a) {p : ℝ[X]}
        (hp : IsPFPolynomial p) (hpdeg : p.natDegree ≤ N) :
        IsPFPolynomial
            (X * applyAsDifferentialOperator
                (binomialDifferentialSymbol N r s) p +
              C a * applyAsDifferentialOperator
                (binomialDifferentialSymbol N (r - 1) s) p) ∧
          Interl
            (applyAsDifferentialOperator (binomialDifferentialSymbol N r s) p)
            (X * applyAsDifferentialOperator
                (binomialDifferentialSymbol N r s) p +
              C a * applyAsDifferentialOperator
                (binomialDifferentialSymbol N (r - 1) s) p)
  • An ordered PF pair of images gives a PF row X h(D)p + a k(D)p preceded by h(D)pRealRooted original

    RealRooted.differentialRecurrence_pf_and_interlsource
    theorem differentialRecurrence_pf_and_interl {h k p : ℝ[X]}
        (hh : IsPFPolynomial (applyAsDifferentialOperator h p))
        (hk : IsPFPolynomial (applyAsDifferentialOperator k p))
        (horder : Interl (applyAsDifferentialOperator h p)
          (applyAsDifferentialOperator k p)) {a : ℝ} (ha : 0 ≤ a) :
        IsPFPolynomial
            (X * applyAsDifferentialOperator h p +
              C a * applyAsDifferentialOperator k p) ∧
          Interl (applyAsDifferentialOperator h p)
            (X * applyAsDifferentialOperator h p +
              C a * applyAsDifferentialOperator k p)
  • Multishift recurrence rows are PF and preceded by the full-symbol imageRealRooted original

    RealRooted.multishiftDifferentialRecurrence_pf_and_interlsource
    theorem multishiftDifferentialRecurrence_pf_and_interl
        {N r : ℕ} {s a : Fin (r + 1) → ℝ}
        (hrN : r + 1 ≤ N) (hs : ∀ i, 0 ≤ s i) (ha : ∀ i, 0 ≤ a i)
        {p : ℝ[X]} (hp : IsPFPolynomial p) (hpdeg : p.natDegree ≤ N) :
        IsPFPolynomial (multishiftDifferentialRecurrence N s a p) ∧
          Interl
            (applyAsDifferentialOperator (multishiftDifferentialSymbol N s) p)
            (multishiftDifferentialRecurrence N s a p)
  • Induction along a multishift recurrence from a PF seedRealRooted original

    RealRooted.multishiftDifferentialRecurrence_inductionsource
    theorem multishiftDifferentialRecurrence_induction
        {m : ℕ} {P : ℕ → ℝ[X]} {r : ℕ → ℕ}
        {s a : (n : ℕ) → Fin (r n + 1) → ℝ}
        (hseed : IsPFPolynomial (P m)) (hseeddeg : (P m).natDegree ≤ m)
        (hr : ∀ n, m ≤ n → r n + 1 ≤ n)
        (hs : ∀ n i, 0 ≤ s n i) (ha : ∀ n i, 0 ≤ a n i)
        (hrec : ∀ n, m ≤ n →
          P (n + 1) = multishiftDifferentialRecurrence n (s n) (a n) (P n)) :
        ∀ n, m ≤ n → IsPFPolynomial (P n) ∧ (P n).natDegree ≤ n
  • For PF h ≠ 0: k is PF with k ≪ h iff k is a nonnegative sum of h and h/(x − u)RealRooted original

    RealRooted.isPFPolynomial_and_interl_iff_hasKreinCompanionExpansionsource
    theorem isPFPolynomial_and_interl_iff_hasKreinCompanionExpansion
        {h k : ℝ[X]} (hh : IsPFPolynomial h) (hh0 : h ≠ 0) :
        IsPFPolynomial k ∧ Interl k h ↔ HasKreinCompanionExpansion h k
  • All-degree ordered PF preservation by (h, k) is equivalent to k being PF and k ≪ hRealRooted original

    RealRooted.forall_differential_images_iff_isPFPolynomial_and_interlsource
    theorem forall_differential_images_iff_isPFPolynomial_and_interl
        {h k : ℝ[X]} (hh : IsPFPolynomial h) (hh0 : h ≠ 0) :
        (∀ p : ℝ[X], IsPFPolynomial p →
          IsPFPolynomial (applyAsDifferentialOperator h p) ∧
            IsPFPolynomial (applyAsDifferentialOperator k p) ∧
              Interl (applyAsDifferentialOperator h p)
                (applyAsDifferentialOperator k p)) ↔
          IsPFPolynomial k ∧ Interl k h
  • Δ_c preserves PF through degree N iff Δ_c(xᴺ) is real-rooted iff p_N is real-rootedRealRooted original

    RealRooted.evenDerivative_preservesPF_tfaesource
    theorem evenDerivative_preservesPF_tfae (hc0 : c 0 = 1) (hc : ∀ k, 0 ≤ c k) (N : ℕ) :
        List.TFAE
          [∀ f : ℝ[X], IsPFPolynomial f → f.natDegree ≤ N → IsPFPolynomial (evenDerivativeOperator c f),
           (evenDerivativeOperator c (X ^ N)).Splits,
           (evenDerivativeTest c N).Splits]
  • If p_N is real-rooted, Δ_c maps PF polynomials of degree at most N to PF polynomialsRealRooted original

    RealRooted.isPFPolynomial_evenDerivativeOperatorsource
    theorem isPFPolynomial_evenDerivativeOperator (hc0 : c 0 = 1) (hc : ∀ k, 0 ≤ c k) {N : ℕ}
        (htest : (evenDerivativeTest c N).Splits) {f : ℝ[X]} (hf : IsPFPolynomial f)
        (hdeg : f.natDegree ≤ N) : IsPFPolynomial (evenDerivativeOperator c f)
  • If p_n is real-rooted, Δ_c ∏ (x + rᵢ) is real-rooted for rᵢ ≥ 0RealRooted original

    RealRooted.splits_evenDerivativeOperator_prodsource
    theorem splits_evenDerivativeOperator_prod (hc : c 0 = 1) {n : ℕ}
        (htest : (evenDerivativeTest c n).Splits) (r : Fin n → ℝ) (hr : ∀ i, 0 ≤ r i) :
        (evenDerivativeOperator c (∏ i, (X + C (r i)))).Splits
  • The polarization of p_n is real stable (Grace–Walsh–Szegő)RealRooted original

    RealRooted.mvRealStable_evenDerivativePolarizationsource
    theorem mvRealStable_evenDerivativePolarization (hc : c 0 = 1) {n : ℕ}
        (h : (evenDerivativeTest c n).Splits) : MvRealStable (evenDerivativePolarization c n)
  • Composition with −z²: Δ_c(xᴺ)(−z²) = (−1)ᴺ zᴺ p_N(z)RealRooted original

    RealRooted.evenDerivativeOperator_X_pow_compsource
    theorem evenDerivativeOperator_X_pow_comp (N : ℕ) :
        (evenDerivativeOperator c (X ^ N)).comp (-(X ^ 2)) =
          C ((-1) ^ N) * X ^ N * evenDerivativeTest c N
  • If p_N is real-rooted, then p_n is real-rooted for all n ≤ NRealRooted original

    RealRooted.splits_evenDerivativeTest_of_lesource
    theorem splits_evenDerivativeTest_of_le {n N : ℕ} (hn : n ≤ N)
        (h : (evenDerivativeTest c N).Splits) : (evenDerivativeTest c n).Splits
  • Consecutive monomial images Δ_c(xᵐ) and Δ_c(xᵐ⁺¹) interlaceRealRooted original

    RealRooted.strictInterl_evenDerivativeOperator_X_pow_succsource
    theorem strictInterl_evenDerivativeOperator_X_pow_succ (hc0 : c 0 = 1) (hc : ∀ k, 0 ≤ c k)
        {m N : ℕ} (hmN : m + 1 ≤ N) (htest : (evenDerivativeTest c N).Splits) :
        StrictInterl (evenDerivativeOperator c (X ^ m)) (evenDerivativeOperator c (X ^ (m + 1)))
  • Δ_c preserves interlacing of nonnegative-coefficient pairs through degree NRealRooted original

    RealRooted.strictInterl_evenDerivativeOperatorsource
    theorem strictInterl_evenDerivativeOperator (hc0 : c 0 = 1) (hc : ∀ k, 0 ≤ c k) {N : ℕ}
        (htest : (evenDerivativeTest c N).Splits) {f g : ℝ[X]} (hfg : StrictInterl f g)
        (hf : HasNonnegCoeffs f) (hg : HasNonnegCoeffs g) (hgdeg : g.natDegree ≤ N) :
        StrictInterl (evenDerivativeOperator c f) (evenDerivativeOperator c g)
  • Δ_c preserves zero-aware interlacing of PF pairs through degree NRealRooted original

    RealRooted.interl_evenDerivativeOperatorsource
    theorem interl_evenDerivativeOperator (hc0 : c 0 = 1) (hc : ∀ k, 0 ≤ c k) {N : ℕ}
        (htest : (evenDerivativeTest c N).Splits) {f g : ℝ[X]} (hf : IsPFPolynomial f)
        (hg : IsPFPolynomial g) (hgdeg : g.natDegree ≤ N) (h : Interl f g) :
        Interl (evenDerivativeOperator c f) (evenDerivativeOperator c g)
  • Δ_c((x + a) h) is real-rooted for PF h and every real aRealRooted original

    RealRooted.splits_evenDerivativeOperator_X_add_C_mulsource
    theorem splits_evenDerivativeOperator_X_add_C_mul (hc0 : c 0 = 1) (hc : ∀ k, 0 ≤ c k) {N : ℕ}
        (htest : (evenDerivativeTest c N).Splits) {h : ℝ[X]} (hh : IsPFPolynomial h) (a : ℝ)
        (hdeg : h.natDegree + 1 ≤ N) : (evenDerivativeOperator c ((X + C a) * h)).Splits
  • Finitely supported c with a real-rooted signed symbol: p_N is real-rooted for every NRealRooted original

    RealRooted.splits_evenDerivativeTest_of_splits_symbolsource
    theorem splits_evenDerivativeTest_of_splits_symbol (hc0 : c 0 = 1) (hM : ∀ k, M < k → c k = 0)
        (hs : (evenDerivativeSymbol c M).Splits) (N : ℕ) : (evenDerivativeTest c N).Splits
  • For c = (1, 1, 1, 0, …): Δ_c(x⁴) = x²(x² + 12x + 24)RealRooted original

    RealRooted.evenDerivativeOperator_capTwo_X_pow_foursource
    theorem evenDerivativeOperator_capTwo_X_pow_four :
        evenDerivativeOperator evenDerivativeCapTwo (X ^ 4) = X ^ 2 * (X ^ 2 + 12 * X + 24)
  • For c = (1, 1, 1, 0, …): Δ_c(x⁵) = x³(x² + 20x + 120)RealRooted original

    RealRooted.evenDerivativeOperator_capTwo_X_pow_fivesource
    theorem evenDerivativeOperator_capTwo_X_pow_five :
        evenDerivativeOperator evenDerivativeCapTwo (X ^ 5) = X ^ 3 * (X ^ 2 + 20 * X + 120)
  • For c = (1, 1, 1, 0, …) the operator preserves PF polynomials through degree fourRealRooted original

    RealRooted.IsPFPolynomial.evenDerivativeCapTwo_of_natDegree_le_foursource
    theorem IsPFPolynomial.evenDerivativeCapTwo_of_natDegree_le_four {f : ℝ[X]}
        (hf : IsPFPolynomial f) (hdeg : f.natDegree ≤ 4) :
        IsPFPolynomial (evenDerivativeOperator evenDerivativeCapTwo f)
  • For c = (1, 1, 1, 0, …) Δ_c(x⁵) is not real-rooted: preservation fails in degree fiveRealRooted original

    RealRooted.not_splits_evenDerivativeOperator_capTwo_X_pow_fivesource
    theorem not_splits_evenDerivativeOperator_capTwo_X_pow_five :
        ¬ (evenDerivativeOperator evenDerivativeCapTwo (X ^ 5)).Splits
  • For c = (1, 2, 1, 0, …), f + 2x f'' + x² f^(4) preserves PF polynomials in every degreeRealRooted original

    RealRooted.isPFPolynomial_evenDerivativeOperator_squaresource
    theorem isPFPolynomial_evenDerivativeOperator_square {f : ℝ[X]} (hf : IsPFPolynomial f) :
        IsPFPolynomial (evenDerivativeOperator evenDerivativeSquare f)
  • For c = (1, 2, 1, 0, …) the images of (x + 1)³ and (x + 1)⁴ interlaceRealRooted original

    RealRooted.strictInterl_evenDerivativeOperator_square_X_add_one_powsource
    theorem strictInterl_evenDerivativeOperator_square_X_add_one_pow :
        StrictInterl (X ^ 3 + 15 * X ^ 2 + 15 * X + 1)
          (X ^ 4 + 28 * X ^ 3 + 78 * X ^ 2 + 28 * X + 1)

Lean source RealRooted/Challenges/Preservers/FiniteDegreeDifferentialTests.lean at revision d6670742. Formalized 2026-11-01.