Pólya frequency sequences with polynomial tails

If a Pólya frequency sequence eventually agrees with a polynomial, its causal forward difference is again a Pólya frequency sequence. Consequently, the values of a polynomial form a Pólya frequency sequence exactly when its Euler numerator is a PF polynomial.

Results

A sequence $a = (a_0, a_1, \dotsc)$ is a Pólya frequency (PF) sequence if its lower triangular Toeplitz matrix $(a_{i-j})_{i,j\ge0}$ is totally nonnegative. The causal forward difference of $a$ keeps the initial value, $$ (\Delta a)_0 = a_0, \qquad (\Delta a)_n = a_n - a_{n-1} \quad (n \ge 1), $$ so it corresponds to multiplying $\sum_n a_n x^n$ by $1 - x$. A PF polynomial is a real polynomial with nonnegative coefficients that is zero or has only real nonpositive roots.

Theorem (polynomial tails). Let $a$ be a PF sequence and let $p \ne 0$ be a real polynomial with $a_n = p(n)$ for all large $n$. Then $a_n>0$ for all large $n$, and $\Delta a$ is a PF sequence.

For a real polynomial $p$ of degree $d$, $$ \sum_{n \ge 0} p(n)\, x^n = \frac{W_p(x)}{(1-x)^{d+1}}, $$ where the Euler numerator $W_p$ has degree at most $d$ and its coefficients are the iterated causal differences $\Delta^{d+1}$ of $(p(n))_{n\ge0}$.

Theorem (Euler numerator criterion). The value sequence $(p(n))_{n\ge0}$ is a PF sequence if and only if $W_p$ is a PF polynomial.

Theorem (rootwise order). [Bra06, Thm. 4.6] Let $f, g$ be monic real-rooted polynomials of the same positive degree with all roots in $[-1, 0]$, and suppose the increasing roots of $f$ are coordinatewise at most those of $g$. Then the Euler numerators of $f$ and $g$ interlace.

Theorem (Newton's forward-difference test). A real polynomial $q$ satisfies $q(n) \ge 0$ for all $n \in \mathbb N$ if and only if there is $K \in \mathbb N$ such that $q(n) \ge 0$ for all $n < K$ and $(\Delta_1^j q)(K) \ge 0$ for all $0 \le j \le \deg q$, where $\Delta_1 q(x) = q(x+1) - q(x)$.

Use

The Euler numerator criterion underlies Brenti's theorem on Euler numerators with roots in $[-1,0]$ and Wagner's product theorem for polynomial values; both are on the Hadamard products page.

Proof

For the polynomial-tail theorem, the Toeplitz minors of $\Delta a$ are limits of normalized minors of the Toeplitz matrix of $a$ whose last row lies far out in the tail; an initial run of zeros is handled by shifting. The direction from $W_p$ to the values is the convolution of $W_p$ with the PF coefficient sequence of $(1-x)^{-(d+1)}$.

References

  1. [Bra06] Petter Brändén. On linear transformations preserving the Pólya frequency property. Transactions of the American Mathematical Society, 358(8), 3697-3716, 2006.
    BibTeX
    @article{Branden2006,
      title = {On linear transformations preserving the {P}{\'{o}}lya frequency property},
      volume = {358},
      ISSN = {1088-6850},
      url = {http://dx.doi.org/10.1090/S0002-9947-06-03856-6},
      DOI = {10.1090/s0002-9947-06-03856-6},
      number = {8},
      journal = {Transactions of the American Mathematical Society},
      publisher = {American Mathematical Society (AMS)},
      author = {Br{\"a}nd{\'e}n, Petter},
      year = {2006},
      month = feb,
      pages = {3697--3716}
    }
  2. [Bre89] Francesco Brenti. Unimodal, log-concave and Pólya frequency sequences in combinatorics. Mem. Amer. Math. Soc., 81(413), viii+106, 1989.
    BibTeX
    @article{Brenti1989,
        AUTHOR = {Brenti, Francesco},
         TITLE = {Unimodal, log-concave and {P}{\'{o}}lya frequency sequences in
                  combinatorics},
       JOURNAL = {Mem. Amer. Math. Soc.},
      FJOURNAL = {Memoirs of the American Mathematical Society},
        VOLUME = {81},
          YEAR = {1989},
        NUMBER = {413},
         PAGES = {viii+106},
          ISSN = {0065-9266,1947-6221},
       MRCLASS = {05A15 (05A10 05A20)},
      MRNUMBER = {963833},
    MRREVIEWER = {Ira\ Gessel},
           DOI = {10.1090/memo/0413},
           URL = {https://doi.org/10.1090/memo/0413},
    }

Definitions

  • Causal forward difference

    Function.causalFwdDiffsource
    def causalFwdDiff {R : Type*} [Sub R] (a : ℕ → R) : ℕ → R
      | 0 => a 0
      | n + 1 => a (n + 1) - a n
  • Euler numerator of a polynomial-value sequence

    RealRooted.polynomialValueEulerNumeratorsource
    noncomputable def polynomialValueEulerNumerator (p : ℝ[X]) : ℝ[X] :=
      finiteEulerNumerator p.natDegree fun k =>
        ((fwdDiff (1 : ℕ))^[k] (polynomialValueSeq p)) 0

Theorems

  • A Pólya frequency sequence with a polynomial tail is eventually positiveRealRooted original

    RealRooted.IsPolyaFreqSeq.eventually_pos_of_eventually_polynomialsource
    theorem IsPolyaFreqSeq.eventually_pos_of_eventually_polynomial
        {a : ℕ → ℝ} (ha : IsPolyaFreqSeq a) {p : ℝ[X]} (hp : p ≠ 0)
        (hap : ∀ᶠ n in atTop, a n = p.eval (n : ℝ)) :
        ∀ᶠ n in atTop, 0 < a n
  • The causal forward difference of a Pólya frequency sequence with a polynomial tailMain resultRealRooted original

    RealRooted.IsPolyaFreqSeq.causalFwdDiff_of_eventually_polynomialsource
    theorem IsPolyaFreqSeq.causalFwdDiff_of_eventually_polynomial
        {a : ℕ → ℝ} (ha : IsPolyaFreqSeq a) {p : ℝ[X]} (hp : p ≠ 0)
        (hap : ∀ᶠ k in atTop, a k = p.eval (k : ℝ)) :
        IsPolyaFreqSeq (Function.causalFwdDiff a)
  • Newton's forward-difference test for nonnegativity on the natural numbersRealRooted original

    Polynomial.forall_nat_eval_nonneg_iff_fwdDiff_itersource
    theorem forall_nat_eval_nonneg_iff_fwdDiff_iter (q : ℝ[X]) :
        (∀ n : ℕ, 0 ≤ q.eval (n : ℝ)) ↔
          ∃ K : ℕ, (∀ n < K, 0 ≤ q.eval (n : ℝ)) ∧
            ∀ j ≤ q.natDegree, 0 ≤ (fwdDiff (1 : ℝ))^[j] q.eval (K : ℝ)
  • Iterated causal differences of polynomial values are the Euler numeratorRealRooted original

    RealRooted.polynomialValueSeq_causalFwdDiff_itersource
    theorem polynomialValueSeq_causalFwdDiff_iter (p : ℝ[X]) :
        (Function.causalFwdDiff^[p.natDegree + 1]) (polynomialValueSeq p) =
          fun n => (polynomialValueEulerNumerator p).coeff n
  • A Pólya frequency value sequence has a PF Euler numeratorRealRooted original

    RealRooted.isPFPolynomial_polynomialValueEulerNumerator_of_polyaFreqSeqsource
    theorem isPFPolynomial_polynomialValueEulerNumerator_of_polyaFreqSeq
        {p : ℝ[X]} (ha : IsPolyaFreqSeq (polynomialValueSeq p)) :
        IsPFPolynomial (polynomialValueEulerNumerator p)
  • A PF Euler numerator makes the value sequence Pólya frequencyRealRooted original

    RealRooted.isPolyaFreqSeq_polynomialValueSeq_of_eulerNumeratorsource
    theorem isPolyaFreqSeq_polynomialValueSeq_of_eulerNumerator
        {p : ℝ[X]} (h : IsPFPolynomial (polynomialValueEulerNumerator p)) :
        IsPolyaFreqSeq (polynomialValueSeq p)
  • Rootwise-ordered polynomials with roots in [−1, 0] have interlacing Euler numeratorsRealRooted original

    RealRooted.polynomialValueEulerNumerator_strictInterl_of_rootwiseLEsource
    theorem polynomialValueEulerNumerator_strictInterl_of_rootwiseLE
        {f g : ℝ[X]} {n : ℕ}
        (hf_monic : f.Monic) (hg_monic : g.Monic)
        (hf_splits : f.Splits) (hg_splits : g.Splits)
        (hf_degree : f.natDegree = n) (hg_degree : g.natDegree = n)
        (hn : n ≠ 0)
        (hf_roots : ∀ r ∈ f.roots, (-1 : ℝ) ≤ r ∧ r ≤ 0)
        (hg_roots : ∀ r ∈ g.roots, (-1 : ℝ) ≤ r ∧ r ≤ 0)
        (hfg : RootwiseLE f g) :
        StrictInterl (polynomialValueEulerNumerator f)
          (polynomialValueEulerNumerator g)

Lean source RealRooted/Challenges/PolyaFrequency/PolynomialTails.lean at revision d6670742. Formalized 2026-09-10.