Aissen–Schoenberg–Whitney theorem

The coefficients of a real polynomial form a Pólya frequency sequence if and only if the polynomial has nonnegative coefficients and only real nonpositive zeros.

Results

A real sequence $(a_k)_{k \geq 0}$ is a Pólya frequency sequence if its lower-triangular Toeplitz matrix, with $(i, j)$ entry $a_{i-j}$ for $j \leq i$ and $0$ otherwise, is totally nonnegative. A real polynomial $p$ is a PF polynomial if it has nonnegative coefficients and either $p=0$ or $p$ splits over $\mathbb R$ with only nonpositive zeros.

Theorem (Aissen–Schoenberg–Whitney). The coefficient sequence of a real polynomial $p$ is a Pólya frequency sequence if and only if $p$ is a PF polynomial.

Theorem (convolution). If $(a_k)$ and $(b_k)$ are Pólya frequency sequences, finite or infinite, then so is their Cauchy convolution $c_n = \sum_{k=0}^n a_k b_{n-k}$. Equivalently, if formal power series $F$ and $G$ have Pólya frequency coefficient sequences, so does $FG$.

Theorem (perturbation criterion). If $p$ and $q$ have nonnegative coefficients and $p+\mu q$ splits over $\mathbb R$ for every $\mu>0$, then the coefficients of $p$ form a Pólya frequency sequence.

Theorem (Karlin's sector estimate). Let $p$ be a real polynomial of degree $d\geq1$ with $p(0)>0$ whose coefficients form a Pólya frequency sequence. For every integer $m\geq1$, each complex zero $z$ of $p$ satisfies $$ |\arg z|\geq \frac{m\pi}{m+d-1}. $$ The threshold tends to $\pi$ as $m\to\infty$, so every zero lies on the negative real axis; this is the forward direction of the equivalence.

Proof

Karlin's repeated coefficient-window matrices of a Pólya frequency sequence are totally nonnegative, and for a complex zero $z$ the vector $(\operatorname{Im} z^j)_j$ lies in their kernel and has the sign variations of the sampled sine vector $(\sin j\theta)_j$, $\theta=\arg z$; comparing the many sign variations this forces with the bound $\lfloor N|\theta|/\pi\rfloor$ for $N+1$ samples gives the sector estimate. The Toeplitz matrix of a convolution is the product of the two Toeplitz matrices, and products of totally nonnegative matrices are totally nonnegative. The perturbation criterion follows from the reverse direction of the equivalence by letting $\mu\to0^+$ in the Toeplitz minors.

References

[ASW52]. See also the Aissen–Schoenberg–Whitney theorem on symmetricfunctions.com.

  1. [ASW52] Michael Aissen, I. J. Schoenberg, & A. M. Whitney. On the generating functions of totally positive sequences I. Journal d’Analyse Mathématique, 2(1), 93-103, 1952.
    BibTeX
    @article{AissenSchoenbergWhitney1952,
      author = {Aissen, Michael and Schoenberg, I. J. and Whitney, A. M.},
      title = {On the generating functions of totally positive sequences {I}},
      year = {1952},
      journal = {Journal d'Analyse Mathématique},
      volume = {2},
      number = {1},
      pages = {93--103},
      doi = {10.1007/BF02786970},
      url = {https://doi.org/10.1007/BF02786970}
    }

Definitions

  • Toeplitz matrix of a sequence

    RealRooted.toeplitzsource
    def toeplitz {R : Type*} [Zero R] (a : ℕ → R) : Matrix ℕ ℕ R :=
      .of fun i j ↦ if j ≤ i then a (i - j) else 0
  • Pólya frequency sequence

    RealRooted.IsPolyaFreqSeqsource
    def IsPolyaFreqSeq (a : ℕ → ℝ) : Prop :=
      (toeplitz a).IsTotallyNonneg
  • Cauchy convolution of sequences

    RealRooted.natCauchyConvolutionsource
    def natCauchyConvolution (a b : ℕ → ℝ) (n : ℕ) : ℝ :=
      ∑ k ∈ Finset.range (n + 1), a k * b (n - k)
  • Karlin's sector threshold mπ/(m+d−1)

    RealRooted.aswSectorThresholdsource
    def aswSectorThreshold (degree order : ℕ) : ℝ :=
      (order : ℝ) / ((order : ℝ) + degree - 1) * Real.pi
  • Karlin's repeated coefficient-window matrix

    RealRooted.aswKarlinMatrixsource
    def aswKarlinMatrix (u : ℕ → ℝ) (degree order blocks : ℕ) :
        Matrix (Fin (blocks * order)) (Fin (blocks * (degree + order - 1) + 1)) ℝ :=
      fun i j => toeplitz u (j : ℕ) (aswKarlinRowPos degree order i)
  • Imaginary parts of the powers of a complex root

    RealRooted.aswKarlinRootVectorsource
    def aswKarlinRootVector (z : ℂ) (degree order blocks : ℕ) :
        Fin (blocks * (degree + order - 1) + 1) → ℝ :=
      fun j => (z ^ (j : ℕ)).im
  • Sampled sine vector of the argument of a root

    RealRooted.aswKarlinSineVectorsource
    def aswKarlinSineVector (θ : ℝ) (degree order blocks : ℕ) :
        Fin (blocks * (degree + order - 1) + 1) → ℝ :=
      fun j => Real.sin ((j : ℕ) * θ)

Theorems

  • Pólya frequency coefficients if and only if a PF polynomialMain result

    RealRooted.isPolyaFreqSeq_coeff_iff_isPFPolynomialsourcestatement on symmetricfunctions.com
    theorem isPolyaFreqSeq_coeff_iff_isPFPolynomial {p : ℝ[X]} :
        IsPolyaFreqSeq p.coeff ↔ IsPFPolynomial p
  • Pólya frequency coefficients give real nonpositive zeros

    RealRooted.aissenSchoenbergWhitneyForwardsource
    theorem aissenSchoenbergWhitneyForward {p : ℝ[X]}
        (hpf : IsPolyaFreqSeq p.coeff) :
        p.Splits ∧ ∀ r ∈ p.roots, r ≤ 0
  • Nonnegative coefficients and real nonpositive zeros give PF coefficients

    RealRooted.aissenSchoenbergWhitney_reversesource
    theorem aissenSchoenbergWhitney_reverse {p : ℝ[X]}
        (hpnn : HasNonnegCoeffs p)
        (hsplits : p.Splits)
        (hroots : ∀ r ∈ p.roots, r ≤ 0) :
        IsPolyaFreqSeq p.coeff
  • Pólya frequency sequences are closed under convolution

    RealRooted.IsPolyaFreqSeq.natCauchyConvolutionsource
    protected theorem IsPolyaFreqSeq.natCauchyConvolution
        {a b : ℕ → ℝ} (ha : IsPolyaFreqSeq a) (hb : IsPolyaFreqSeq b) :
        IsPolyaFreqSeq (natCauchyConvolution a b)
  • Products of power series with PF coefficients have PF coefficients

    RealRooted.IsPolyaFreqSeq.coeff_mulsource
    theorem IsPolyaFreqSeq.coeff_mul {F G : PowerSeries ℝ}
        (hF : IsPolyaFreqSeq fun k => PowerSeries.coeff k F)
        (hG : IsPolyaFreqSeq fun k => PowerSeries.coeff k G) :
        IsPolyaFreqSeq fun k => PowerSeries.coeff k (F * G)
  • Karlin: PF zeros satisfy |arg z| ≥ mπ/(m+d−1) for every m ≥ 1

    RealRooted.aswKarlinSectorThreshold_le_abs_argsource
    theorem aswKarlinSectorThreshold_le_abs_arg {p : ℝ[X]} {z : ℂ}
        (hz : z ∈ (p.map (algebraMap ℝ ℂ)).roots)
        (hdegree : 0 < p.natDegree) (hconst : 0 < p.coeff 0)
        (hpf : IsPolyaFreqSeq p.coeff) {order : ℕ} (horder : 0 < order) :
        aswSectorThreshold p.natDegree order ≤ |z.arg|
  • PF coefficients if p + μq splits for every μ > 0

    RealRooted.IsPolyaFreqSeq.of_forall_pos_add_C_mul_splitssource
    theorem IsPolyaFreqSeq.of_forall_pos_add_C_mul_splits {p q : ℝ[X]}
        (hpnn : HasNonnegCoeffs p) (hqnn : HasNonnegCoeffs q)
        (hfamily : ∀ {μ : ℝ}, 0 < μ → (p + C μ * q).Splits) :
        IsPolyaFreqSeq p.coeff
  • The sector threshold tends to π as the order grows

    RealRooted.tendsto_aswSectorThresholdsource
    lemma tendsto_aswSectorThreshold (degree : ℕ) :
        Tendsto (aswSectorThreshold degree) atTop (nhds Real.pi)
  • Karlin window matrices of PF sequences are totally nonnegative

    RealRooted.IsPolyaFreqSeq.aswKarlinMatrix_isTotallyNonnegRectsource
    theorem IsPolyaFreqSeq.aswKarlinMatrix_isTotallyNonnegRect
        {u : ℕ → ℝ} (hpf : IsPolyaFreqSeq u) (degree order blocks : ℕ) :
        (aswKarlinMatrix u degree order blocks).IsTotallyNonnegRect
  • The Karlin window matrix is surjective when the constant coefficient is positive

    RealRooted.aswKarlinMatrix_mulVec_surjectivesource
    theorem aswKarlinMatrix_mulVec_surjective {u : ℕ → ℝ}
        (degree order blocks : ℕ) (hdegree : 0 < degree) (horder : 0 < order)
        (hconst : 0 < u 0) :
        Function.Surjective (aswKarlinMatrix u degree order blocks).mulVec
  • The root vector of a complex zero lies in the kernel of the window matrix

    RealRooted.aswKarlinMatrix_mulVec_rootVectorsource
    theorem aswKarlinMatrix_mulVec_rootVector {p : ℝ[X]} {z : ℂ}
        (hz : z ∈ (p.map (algebraMap ℝ ℂ)).roots)
        (order blocks : ℕ) (hdegree : 0 < p.natDegree) (horder : 0 < order) :
        aswKarlinMatrix p.coeff p.natDegree order blocks *ᵥ
          aswKarlinRootVector z p.natDegree order blocks = 0
  • The root vector and the sampled sine vector have the same sign variations

    RealRooted.signVariations_aswKarlinRootVector_eq_sinesource
    lemma signVariations_aswKarlinRootVector_eq_sine {z : ℂ} (hz : z ≠ 0)
        (degree order blocks : ℕ) :
        Fin.signVariations (aswKarlinRootVector z degree order blocks) =
          Fin.signVariations (aswKarlinSineVector z.arg degree order blocks)
  • A sampled sine vector has at most ⌊N|θ|/π⌋ sign variations

    RealRooted.signVariations_aswKarlinSineVector_le_floor_div_pi_abssource
    lemma signVariations_aswKarlinSineVector_le_floor_div_pi_abs
        (θ : ℝ) (degree order blocks : ℕ) :
        Fin.signVariations (aswKarlinSineVector θ degree order blocks) ≤
          ⌊(((blocks * (degree + order - 1) : ℕ) : ℝ) * |θ|) /
            Real.pi⌋₊
  • Below the threshold the sine vector has fewer than m sign variations

    RealRooted.signVariations_aswKarlinSineVector_lt_of_lt_thresholdsource
    lemma signVariations_aswKarlinSineVector_lt_of_lt_threshold
        {θ : ℝ} {degree order : ℕ} (hdegree : 0 < degree) (horder : 0 < order)
        (hθ0 : 0 ≤ θ) (hθ : θ < aswSectorThreshold degree order) :
        Fin.signVariations (aswKarlinSineVector θ degree order 1) < order
  • Karlin's repeated matrices force many sign variations on the sine vector

    RealRooted.aswKarlinRepeatedSineVariationLowerBoundsource
    theorem aswKarlinRepeatedSineVariationLowerBound
        {p : ℝ[X]} {z : ℂ} (hz : z ∈ (p.map (algebraMap ℝ ℂ)).roots)
        (hdegree : 0 < p.natDegree) (hconst : 0 < p.coeff 0)
        (hpf : IsPolyaFreqSeq p.coeff) {order blocks : ℕ}
        (horder : 0 < order) (hblocks : 0 < blocks) (him : z.im ≠ 0) :
        blocks * order - 1 ≤
          Fin.signVariations
            (aswKarlinSineVector z.arg p.natDegree order blocks) + 2
  • The sector inequality follows from the two sign-variation bounds

    RealRooted.aswSectorThreshold_le_of_signVariation_boundssource
    theorem aswSectorThreshold_le_of_signVariation_bounds
        {degree order : ℕ} {θ : ℝ}
        {v : Fin (1 * (degree + order - 1) + 1) → ℝ}
        (hsign : Fin.signVariations v =
          Fin.signVariations (aswKarlinSineVector θ degree order 1))
        (hkerLower : order ≤ Fin.signVariations v)
        (hsineUpper : θ < aswSectorThreshold degree order →
          Fin.signVariations (aswKarlinSineVector θ degree order 1) < order) :
        aswSectorThreshold degree order ≤ θ

Lean source RealRooted/Challenges/PolyaFrequency/AissenSchoenbergWhitney.lean at revision d6670742. Formalized 2026-10-05.