Chain polynomials of totally nonnegative matrices

Chain polynomials of a lower-unitriangular totally nonnegative matrix are real-rooted with zeros in $[-1,0]$, and consecutive ones interlace, by a theorem of Brändén and Saud Leite. We prove a more general version of their result on $1/(Q(u)-tu^r)$: the coefficient rows of every positive power and of the logarithm of $Q(u)-tB(u)$ are Pólya frequency polynomials, and consecutive ones interlace. The same method gives such rows for many generating functions built from Pólya frequency series.

Results

We use the zero-aware interlacing convention. A polynomial is a Pólya frequency (PF) polynomial if it has nonnegative coefficients and only real nonpositive roots. For a lower-triangular matrix $A$, the chain polynomials are $P_0=1$ and $$ P_{n+1}(x)=x\sum_{k\le n}A(n+1,k)\,P_k(x). $$

Theorem (Brändén–Saud Leite). [BL24, Thm. 3.7] Let $A$ be lower unitriangular and totally nonnegative. Then every $P_n$ has nonnegative coefficients, and is zero or has only real roots, all in $[-1,0]$. Moreover $P_n\ll P_{n+1}$ for all $n$.

If instead $A(n,n)=\delta>0$ for all $n$, then $P^A_n(x)=P^{A/\delta}_n(\delta x)$, so $P_n$ is a PF polynomial and $P_n\ll P_{n+1}$. A real lower-triangular matrix admits a resolution, that is, nonnegative weights $\lambda_{n,k}$ and monic polynomials $p_{n,k}$ with $p_{n,0}=P_n$, $p_{n,n}=x^n$, $x^k\mid p_{n,k}$ and $p_{n+1,k}=p_{n+1,k+1}+\lambda_{n,k}\,p_{n,k}$ for $k\le n$, if and only if it is lower unitriangular and totally nonnegative; it is then the path matrix of a triangular network with the Whitney elimination weights.

Theorem (rows of power series). Let $g,h$ be Pólya frequency sequences, and let $p_n$ be the coefficient of $z^n$ in $g(z)/\bigl(1-x\,(g(z)h(z)-g(0)h(0))\bigr)$. Then every $p_n$ is a PF polynomial and $p_n\ll p_{n+1}$; if $g(0),h(0)>0$, its roots lie in $[-1/(g(0)h(0)),0]$. The $p_n$ are the rows of the regularized kernel of the finite Toeplitz matrices of $g$ and $h$. For $g=1$ this is [BL24, Thm. 4.4].

In particular, if $h(0)=0$ the coefficients of $1/(1-x\,h(z))$, and if moreover $g(0)>0$ those of $g/(1-x\,g\,h)$, are PF polynomials in $x$ and consecutive ones interlace. This applies to $h=z(1+z)^d$ and $h=z/(1-z)^e$ for $d,e\ge0$, whose rows include OEIS A116088 ($d=2$), A116089 ($d=3$) and A206294 ($e=3$). For a PF polynomial $R$ and $m\ge1$, the coefficients $\rho_n$ of $1/(1-xR(zx^m))$ are PF polynomials, and $\rho_{mq+r}\ll\rho_{m(q+1)+r}$ for $0\le r<m$, because $\rho_{mq+r}$ is the reciprocal of $p_q$ for $g=R^r$ and $h=zR^{m-r}$; they are nonzero when $R(0)>0$. Finally, for nonnegative weights $b_n,w_n$, scalars $a_1,\dots,a_s\ge0$ and $r\ge1$, let $B$ and $B_j$ be the lower shifts with weights $b_n$ and $a_jw_n$, $S$ the unweighted lower shift, $G=I+B+\dots+B^N$ and $K=\prod_j(I+B_j)\,S^r$; then row $i$ of $\sum_q (G(KG)^q)_{i,0}\,x^q$ is a PF polynomial.

Theorem (powers and logarithms). Let $$ Q(u)=\prod_{i=1}^{d}(1-\alpha_iu),\qquad B(u)=c\,u^r\prod_j(1+\beta_ju), $$ with $d\ge1$, $\alpha_i>0$, $c>0$, $r\ge1$ and $\beta_j\ge0$, and put $q_n(t)=[u^n]\,(Q(u)-tB(u))^{-\kappa}$ for real $\kappa>0$. Then $q_n$ is nonzero with degree $\lfloor n/r\rfloor$, has positive coefficients up to that degree and only negative roots, and $q_n\ll q_{n+1}$. For $n\ge1$ the same holds for $\ell_n(t)=[u^n]\bigl(-\log(Q(u)-tB(u))\bigr)=\lim_{\kappa\to0^+}q_n/\kappa$, whose coefficients are $[t^k]\,\ell_n=\frac1k\,[u^n]\bigl(B(u)^k\,Q(u)^{-k}\bigr)$ for $k\ge1$.

This theorem is new. Its corollary for $\kappa=1$ and $B(u)=u^r$, that the coefficients of $1/(Q(u)-tu^r)$ have only negative roots and consecutive ones interlace, is the theorem of Brändén and Saud Leite [BL24, Thm. 4.5].

The rows $q_n$ are also PF with $q_n\ll q_{n+1}$ when $B$ is any nonzero real-rooted polynomial with nonnegative coefficients and $B(0)=0$. If $r=1$, and $[u^2]Q>0$ or $[u^2]B>0$, consecutive rows interlace strictly with simple roots; for $Q=1-u$ and $B=u$, every $q_n$ is a positive multiple of $(1+t)^n$. The case $\kappa=1$ is the rational function $1/(Q(u)-tB(u))$.

For a sequence $f$, the weighted derivative kernel has entries $K_\kappa(f)_{ij}=\bigl(j+\kappa\,(i+1-j)\bigr)f_{i+1-j}$ for $j\le i+1$ and $0$ otherwise. It is totally nonnegative when $f$ is the coefficient sequence of a real-rooted polynomial with nonnegative coefficients and $\kappa\ge0$. If $Q(0)=1$ and $B(0)=0$, then $$ n!\,q_n(t)=\det\Bigl(K_\kappa\bigl((-1)^kQ_k\bigr)+t\,\mathrm{checkerboard}\,K_\kappa(B_k) \Bigr)_{n\times n}, $$ where $Q_k,B_k$ are the coefficients of $u^k$ and the checkerboard matrix multiplies the $(i,j)$ entry by $(-1)^{i+j}$. For $H(0)=1$, $\det K_\kappa((-1)^kH_k)$ is $n!\,[u^n]H^{-\kappa}$, which is positive when $H$ is a nonempty product of factors $1-\alpha_iu$ with $\alpha_i>0$ and $\kappa>0$. The coefficients of $q_n$ satisfy a finite recurrence in $n$ with coefficients from $Q$ and $B$.

Proof

Whitney elimination produces the resolution of a totally nonnegative unitriangular matrix, and its recurrence assembles each $P_n$ from lower rows by nonnegative combinations, which preserve interlacing. For powers and logarithms we use the determinant formula with weighted derivative kernels; see also determinant pencils.

References

  1. [BL24] Petter Brändén & Leonardo Saud Maia Leite. Totally nonnegative matrices, chain enumeration and zeros of polynomials. arXiv e-prints, 2024.
    BibTeX
    @article{BrandenLeite2024x,
      author = {Petter Brändén and Leonardo Saud Maia Leite},
      title = {Totally nonnegative matrices, chain enumeration and zeros of polynomials},
      journal = {arXiv e-prints},
      Eprint = {2412.06595},
      url = {https://arxiv.org/abs/2412.06595},
      year = {2024}
    }

Definitions

  • Coefficients of (Q(u) - tB(u))^(-κ) as polynomials in t

    RealRooted.BrandenLeite.affineNegativePowerCoeffsource
    @[expose] noncomputable def affineNegativePowerCoeff
        (κ : R) (Q B : PowerSeries R) (n : ℕ) : Polynomial R :=
      coeff n (subst (map Polynomial.C Q - C Polynomial.X * map Polynomial.C B - 1)
        (binomialSeries (Polynomial R) (-Polynomial.C κ)))
  • Coefficients of -log(Q(u) - tB(u)) as polynomials in t

    RealRooted.BrandenLeite.affineLogCoeffsource
    @[expose] noncomputable def affineLogCoeff {R : Type*} [CommRing R] [Algebra ℚ R]
        (Q B : PowerSeries R) (n : ℕ) : Polynomial R :=
      coeff n (-logOf (map Polynomial.C Q - C Polynomial.X * map Polynomial.C B))
  • Chain polynomials

    RealRooted.BrandenLeite.chainPolynomialsource
    def chainPolynomial {R : Type*} [Semiring R] (A : LowerTriangularMatrix R) : ℕ → R[X]
      | 0 => 1
      | n + 1 =>
          X * ∑ k : Fin (n + 1), A (n + 1) k • chainPolynomial A k
    termination_by n => n
    decreasing_by exact k.isLt
  • Resolvable matrix

    RealRooted.BrandenLeite.IsResolvablesource
    def IsResolvable {S : Type*} [CommSemiring S] [LE S]
        (R : LowerTriangularMatrix S) : Prop :=
      Nonempty (Resolution R)
  • Rows of 1 / (1 - x h(z))

    RealRooted.BrandenLeite.compositionRowsource
    def compositionRow {R : Type*} [CommSemiring R]
        (h : PowerSeries R) (n : ℕ) : R[X] :=
      ∑ k ∈ Finset.range (n + 1),
        C (PowerSeries.coeff n (h ^ k)) * X ^ k
  • Rows of g / (1 - x g h)

    RealRooted.BrandenLeite.twoKernelRowsource
    def twoKernelRow {R : Type*} [CommSemiring R]
        (g h : PowerSeries R) (n : ℕ) : R[X] :=
      ∑ k ∈ Finset.range (n + 1),
        C (PowerSeries.coeff n (g ^ (k + 1) * h ^ k)) * X ^ k
  • The weighted derivative kernel of a coefficient sequence

    RealRooted.BrandenLeite.weightedDerivativeKernelsource
    def weightedDerivativeKernel {R : Type*} [CommRing R] (κ : R) (f : ℕ → R) :
        Matrix ℕ ℕ R :=
      fun i j ↦ if j ≤ i + 1 then ((j : R) + κ * (i + 1 - j : ℕ)) * f (i + 1 - j)
        else 0
  • Numerators of g / (1 - x (g h - g(0) h(0)))

    RealRooted.BrandenLeite.pfFactorNumeratorsource
    def pfFactorNumerator (g h : ℕ → ℝ) (n : ℕ) : ℝ[X] :=
      ∑ q ∈ Finset.range (n + 1),
        C (PowerSeries.coeff n
          (PowerSeries.mk g *
            positivePartSeries
              (fun k ↦ PowerSeries.coeff k
                (PowerSeries.mk g * PowerSeries.mk h)) ^ q)) * X ^ q

Theorems

  • Positive real powers: negative roots, exact degree and consecutive interlacingRealRooted original

    RealRooted.BrandenLeite.affineNegativePowerCoeff_factor_propertiessource
    theorem affineNegativePowerCoeff_factor_properties
        {ι ν : Type*} (s : Finset ι) (hs : s.Nonempty) (α : ι → ℝ)
        (hα : ∀ i ∈ s, 0 < α i) (t : Finset ν) (β : ν → ℝ)
        (hβ : ∀ j ∈ t, 0 ≤ β j) {c κ : ℝ} (hc : 0 < c) (hκ : 0 < κ)
        (r : ℕ) (hr : r ≠ 0) (n : ℕ) :
        let Q : Polynomial ℝ
  • Logarithmic rows: negative roots, exact degree and consecutive interlacingRealRooted original

    RealRooted.BrandenLeite.affineLogCoeff_factor_propertiessource
    theorem affineLogCoeff_factor_properties
        {ι ν : Type*} (s : Finset ι) (hs : s.Nonempty) (α : ι → ℝ)
        (hα : ∀ i ∈ s, 0 < α i) (t : Finset ν) (β : ν → ℝ)
        (hβ : ∀ j ∈ t, 0 ≤ β j) {c : ℝ} (hc : 0 < c)
        (r : ℕ) (hr : r ≠ 0) (n : ℕ) (hn : n ≠ 0) :
        let Q : Polynomial ℝ
  • For r = 1 and positive [u²]Q or [u²]B: simple roots, no common roots in consecutive rowsRealRooted original

    RealRooted.BrandenLeite.affineNegativePowerCoeff_factor_simple_and_disjointsource
    theorem affineNegativePowerCoeff_factor_simple_and_disjoint
        {ι ν : Type*} (s : Finset ι) (hs : s.Nonempty) (α : ι → ℝ)
        (hα : ∀ i ∈ s, 0 < α i) (t : Finset ν) (β : ν → ℝ)
        (hβ : ∀ j ∈ t, 0 ≤ β j) {c κ : ℝ} (hc : 0 < c) (hκ : 0 < κ) (n : ℕ) :
        let Q : ℝ[X]
  • Consecutive chain polynomials interlaceMain resultRealRooted original

    RealRooted.BrandenLeite.interl_chainPolynomial_succ_of_isTotallyNonnegsource
    theorem interl_chainPolynomial_succ_of_isTotallyNonneg
        (hunit : LowerTriangularMatrix.IsLowerUnitriangular R)
        (hR : Matrix.IsTotallyNonneg R) (n : ℕ) :
        Interl (chainPolynomial R n) (chainPolynomial R (n + 1))
  • Chain polynomials are real-rootedRealRooted original

    RealRooted.BrandenLeite.chainPolynomial_eq_zero_or_splits_of_isTotallyNonnegsource
    theorem chainPolynomial_eq_zero_or_splits_of_isTotallyNonneg
        (hunit : LowerTriangularMatrix.IsLowerUnitriangular R)
        (hR : Matrix.IsTotallyNonneg R) (n : ℕ) :
        chainPolynomial R n = 0 ∨ (chainPolynomial R n).Splits
  • Zeros of chain polynomials lie in [-1, 0]RealRooted original

    RealRooted.BrandenLeite.roots_chainPolynomial_mem_Icc_of_isTotallyNonnegsource
    theorem roots_chainPolynomial_mem_Icc_of_isTotallyNonneg
        (hunit : LowerTriangularMatrix.IsLowerUnitriangular R)
        (hR : Matrix.IsTotallyNonneg R) (n : ℕ) :
        ∀ x ∈ (chainPolynomial R n).roots, x ∈ Set.Icc (-1) 0
  • Chain polynomials have nonnegative coefficientsRealRooted original

    RealRooted.BrandenLeite.chainPolynomial_hasNonnegCoeffs_of_isTotallyNonnegsource
    theorem chainPolynomial_hasNonnegCoeffs_of_isTotallyNonneg
        (hunit : LowerTriangularMatrix.IsLowerUnitriangular R)
        (hR : Matrix.IsTotallyNonneg R) (n : ℕ) :
        HasNonnegCoeffs (chainPolynomial R n)
  • Resolvable if and only if totally nonnegativeRealRooted original

    RealRooted.BrandenLeite.isResolvable_iff_lowerUnitriangular_and_isTotallyNonnegsource
    theorem isResolvable_iff_lowerUnitriangular_and_isTotallyNonneg
        {R : LowerTriangularMatrix ℝ} :
        IsResolvable R ↔
          LowerTriangularMatrix.IsLowerUnitriangular R ∧
            Matrix.IsTotallyNonneg R
  • Chain polynomials with positive constant diagonal are PFRealRooted original

    RealRooted.BrandenLeite.chainPolynomial_isPFPolynomial_of_pos_constantDiagonalsource
    theorem chainPolynomial_isPFPolynomial_of_pos_constantDiagonal
        {δ : ℝ} {A : LowerTriangularMatrix ℝ} (hδ : 0 < δ)
        (hlower : LowerTriangularMatrix.IsLowerTriangular A)
        (hdiag : ∀ n, A n n = δ) (hA : Matrix.IsTotallyNonneg A) (n : ℕ) :
        IsPFPolynomial (chainPolynomial A n)
  • Rows of 1 / (1 - x h(z)) with h(0) = 0 are PF and interlaceRealRooted original

    RealRooted.BrandenLeite.compositionRows_isPFPolynomial_and_interl_of_zerosource
    theorem compositionRows_isPFPolynomial_and_interl_of_zero
        {f : ℕ → ℝ} (hf : IsPolyaFreqSeq f) (hf0 : f 0 = 0) :
        (∀ n, IsPFPolynomial (compositionRow (PowerSeries.mk f) n)) ∧
          ∀ n, Interl (compositionRow (PowerSeries.mk f) n)
            (compositionRow (PowerSeries.mk f) (n + 1))
  • Rows of g / (1 - x g h) are PF and interlaceRealRooted original

    RealRooted.BrandenLeite.twoKernelRows_pf_and_interlsource
    theorem twoKernelRows_pf_and_interl
        {g h : ℕ → ℝ} (hg : IsPolyaFreqSeq g) (hh : IsPolyaFreqSeq h)
        (hg0 : 0 < g 0) (hh0 : h 0 = 0) :
        (∀ n, IsPFPolynomial
            (twoKernelRow (PowerSeries.mk g) (PowerSeries.mk h) n)) ∧
          ∀ n, Interl
            (twoKernelRow (PowerSeries.mk g) (PowerSeries.mk h) n)
            (twoKernelRow (PowerSeries.mk g) (PowerSeries.mk h) (n + 1))
  • Rows of 1 / (1 - x z (1+z)^d) are PF and interlaceRealRooted original

    RealRooted.BrandenLeite.binomialCompositionRows_pf_and_interlsource
    theorem binomialCompositionRows_pf_and_interl (d : ℕ) :
        (∀ n, IsPFPolynomial
          (compositionRow (PowerSeries.mk (binomialCompositionKernel d)) n)) ∧
          ∀ n, Interl
            (compositionRow (PowerSeries.mk (binomialCompositionKernel d)) n)
            (compositionRow
              (PowerSeries.mk (binomialCompositionKernel d)) (n + 1))
  • Rows of 1 / (1 - x z / (1-z)^e) are PF and interlaceRealRooted original

    RealRooted.BrandenLeite.inversePowerCompositionRows_pf_and_interlsource
    theorem inversePowerCompositionRows_pf_and_interl (e : ℕ) :
        (∀ n, IsPFPolynomial
          (compositionRow
            (PowerSeries.mk (inversePowerCompositionKernel e)) n)) ∧
          ∀ n, Interl
            (compositionRow
              (PowerSeries.mk (inversePowerCompositionKernel e)) n)
            (compositionRow
              (PowerSeries.mk (inversePowerCompositionKernel e)) (n + 1))
  • Every lower-unitriangular TNN matrix is a Whitney-elimination network path matrixRealRooted original

    RealRooted.BrandenLeite.networkMatrix_resolutionLambda_eqsource
    theorem networkMatrix_resolutionLambda_eq
        (R : LowerTriangularMatrix ℝ)
        (hunit : LowerTriangularMatrix.IsLowerUnitriangular R)
        (hR : Matrix.IsTotallyNonneg R) :
        networkMatrix (resolutionLambda R) = R
  • Tiling polynomials of weighted lower shifts are PFRealRooted original

    RealRooted.BrandenLeite.weightedShiftTilingRow_separated_isPFPolynomialsource
    theorem weightedShiftTilingRow_separated_isPFPolynomial
        {b : ℕ → ℝ} (hb : ∀ n, 0 ≤ b n)
        {alphas : List ℝ} (halphas : ∀ a ∈ alphas, 0 ≤ a)
        {w : ℕ → ℝ} (hw : ∀ n, 0 ≤ w n)
        (N : ℕ) {r : ℕ} (hr : r ≠ 0) (i : Fin (N + 1)) :
        IsPFPolynomial
          (weightedShiftTilingRow b (alphas.map fun a n => a * w n) N r i)
  • Weighted derivative kernels of real-rooted nonnegative polynomials are TNNRealRooted original

    RealRooted.weightedDerivativeKernel_isTotallyNonnegsource
    theorem weightedDerivativeKernel_isTotallyNonneg {F : ℝ[X]} (hF : F.Splits)
        (hnn : HasNonnegCoeffs F) {κ : ℝ} (hκ : 0 ≤ κ) :
        (weightedDerivativeKernel κ F.coeff).IsTotallyNonneg
  • Rows of a negative power are determinants of an affine pencil of weighted kernelsRealRooted original

    RealRooted.BrandenLeite.det_weightedDerivativeKernel_affineNegativePowerCoeffsource
    theorem det_weightedDerivativeKernel_affineNegativePowerCoeff
        (κ : R) (Q B : PowerSeries R) (hQ : constantCoeff Q = 1)
        (hB : constantCoeff B = 0) (n : ℕ) :
        Matrix.det
          ((((weightedDerivativeKernel κ (fun k => (-1 : R) ^ k * coeff k Q)).submatrix
            Fin.val Fin.val : Matrix (Fin n) (Fin n) R).map Polynomial.C) +
          (Polynomial.X : Polynomial R) • (Matrix.checkerboard
            ((weightedDerivativeKernel κ (fun k => coeff k B)).submatrix
              Fin.val Fin.val : Matrix (Fin n) (Fin n) R)).map Polynomial.C) =
          (n.factorial : Polynomial R) * affineNegativePowerCoeff κ Q B n
  • Determinants of signed weighted kernels are coefficients of negative powersRealRooted original

    RealRooted.BrandenLeite.det_weightedDerivativeKernel_subst_binomialSeries_negsource
    theorem det_weightedDerivativeKernel_subst_binomialSeries_neg
        (κ : R) (H : PowerSeries R) (hH : constantCoeff H = 1) (n : ℕ) :
        ((weightedDerivativeKernel κ (fun k => (-1 : R) ^ k * coeff k H)).submatrix
          Fin.val Fin.val : Matrix (Fin n) (Fin n) R).det =
          (n.factorial : R) * coeff n (subst (H - 1) (binomialSeries R (-κ)))
  • Signed kernel determinants are positive for products of factors 1 - αu, α > 0RealRooted original

    RealRooted.BrandenLeite.det_weightedDerivativeKernel_signed_prod_linear_possource
    theorem det_weightedDerivativeKernel_signed_prod_linear_pos {ι : Type*}
        (s : Finset ι) (hs : s.Nonempty) (α : ι → ℝ)
        (hα : ∀ i ∈ s, 0 < α i) {κ : ℝ} (hκ : 0 < κ) (n : ℕ) :
        ((weightedDerivativeKernel κ
          (fun k ↦ (-1 : ℝ) ^ k * coeff k
            (∏ i ∈ s, (1 - C (α i) * X : PowerSeries ℝ)))).submatrix
          Fin.val Fin.val : Matrix (Fin n) (Fin n) ℝ).det > 0
  • A finite coefficient recurrence for the rows of a negative powerRealRooted original

    RealRooted.BrandenLeite.coeff_affineNegativePowerCoeff_recurrencesource
    theorem coeff_affineNegativePowerCoeff_recurrence
        (κ : ℝ) (Q B : PowerSeries ℝ)
        (hQ : constantCoeff Q = 1) (hB : constantCoeff B = 0)
        (n i : ℕ) :
        (affineNegativePowerCoeff κ Q B (n + 1)).coeff i =
          -((n + 1 : ℕ) : ℝ)⁻¹ *
            ∑ k ∈ Finset.range (n + 1),
              ((n - k : ℕ) + κ * (k + 1 : ℕ)) *
                ∑ j ∈ Finset.range (i + 1),
                  (Polynomial.C (coeff (k + 1) Q) -
                    Polynomial.X * Polynomial.C (coeff (k + 1) B)).coeff j *
                    (affineNegativePowerCoeff κ Q B (n - k)).coeff (i - j)
  • Rows have degree ⌊n/r⌋ and positive coefficients up to that degreeRealRooted original

    RealRooted.BrandenLeite.natDegree_affineNegativePowerCoeff_and_coeff_possource
    theorem natDegree_affineNegativePowerCoeff_and_coeff_pos
        (Q B : PowerSeries ℝ) (κ : ℝ) (r : ℕ)
        (hQ : constantCoeff Q = 1) (hr : r ≠ 0) (hκ : 0 < κ)
        (hB : ∀ n, 0 ≤ coeff n B)
        (hBzero : ∀ n < r, coeff n B = 0) (hBpos : 0 < coeff r B)
        (hQpos : ∀ (k n : ℕ), 0 < coeff n
          (subst (Q - 1) (binomialSeries ℝ (-κ - (k : ℝ))))) (n : ℕ) :
        (affineNegativePowerCoeff κ Q B n).natDegree = n / r ∧
          ∀ k ≤ n / r, 0 < (affineNegativePowerCoeff κ Q B n).coeff k
  • Consecutive negative-power rows interlace when the linear coefficient of B is positiveRealRooted original

    RealRooted.BrandenLeite.interlaces_affineNegativePowerCoeff_succsource
    theorem interlaces_affineNegativePowerCoeff_succ
        {κ : ℝ} (hκ : 0 < κ) (Q B : ℝ[X])
        (hQ : Q.coeff 0 = 1) (hB : B.coeff 0 = 0) (hB₁ : 0 < B.coeff 1)
        (hQs : (Q.comp (-Polynomial.X)).Splits)
        (hQnn : HasNonnegCoeffs (Q.comp (-Polynomial.X)))
        (hBs : B.Splits) (hBnn : HasNonnegCoeffs B) (n : ℕ) :
        Interlaces (affineNegativePowerCoeff κ (Q : PowerSeries ℝ) B n)
          (affineNegativePowerCoeff κ (Q : PowerSeries ℝ) B (n + 1))
  • Consecutive rows interlace for every nonzero split numerator B with B(0) = 0RealRooted original

    RealRooted.BrandenLeite.interl_affineNegativePowerCoeff_prod_linear_succsource
    theorem interl_affineNegativePowerCoeff_prod_linear_succ
        {ι : Type*} (s : Finset ι) (hs : s.Nonempty) (α : ι → ℝ)
        (hα : ∀ i ∈ s, 0 < α i) {κ : ℝ} (hκ : 0 < κ)
        (B : ℝ[X]) (hBne : B ≠ 0) (hB0 : B.coeff 0 = 0)
        (hBs : B.Splits) (hBnn : HasNonnegCoeffs B) (n : ℕ) :
        Interl (affineNegativePowerCoeff κ
          ((∏ i ∈ s, (1 - C (α i) * X) : ℝ[X]) : PowerSeries ℝ) B n)
          (affineNegativePowerCoeff κ
            ((∏ i ∈ s, (1 - C (α i) * X) : ℝ[X]) : PowerSeries ℝ) B (n + 1))
  • Rows with product-of-linear-factor denominators are PF polynomialsRealRooted original

    RealRooted.BrandenLeite.isPFPolynomial_affineNegativePowerCoeff_prod_linearsource
    theorem isPFPolynomial_affineNegativePowerCoeff_prod_linear
        {ι : Type*} (s : Finset ι) (hs : s.Nonempty) (α : ι → ℝ)
        (hα : ∀ i ∈ s, 0 < α i) {κ : ℝ} (hκ : 0 < κ)
        (B : ℝ[X]) (hB : B.coeff 0 = 0) (hBs : B.Splits)
        (hBnn : HasNonnegCoeffs B) (n : ℕ) :
        IsPFPolynomial (affineNegativePowerCoeff κ
          ((∏ i ∈ s, (1 - Polynomial.C (α i) * Polynomial.X) : ℝ[X]) : PowerSeries ℝ)
          B n)
  • The logarithmic row is the limit of q_n / κ as κ tends to 0 from aboveRealRooted original

    RealRooted.BrandenLeite.tendsto_coeff_affineNegativePowerCoeff_divsource
    theorem tendsto_coeff_affineNegativePowerCoeff_div
        (Q B : PowerSeries ℝ) (hQ : constantCoeff Q = 1) (hB : constantCoeff B = 0)
        {n : ℕ} (hn : n ≠ 0) (k : ℕ) :
        Tendsto (fun a : ℝ => (affineNegativePowerCoeff a Q B n).coeff k / a)
          (𝓝[>] 0) (𝓝 ((affineLogCoeff Q B n).coeff k))
  • Explicit parameter coefficients of the logarithmic rowsRealRooted original

    RealRooted.BrandenLeite.coeff_affineLogCoeff_of_ne_zerosource
    theorem coeff_affineLogCoeff_of_ne_zero
        (Q B : PowerSeries ℝ) (hQ : constantCoeff Q = 1) (hB : constantCoeff B = 0)
        {n k : ℕ} (hn : n ≠ 0) (hk : k ≠ 0) :
        (affineLogCoeff Q B n).coeff k =
          (1 / (k : ℝ)) * coeff n
            (B ^ k * subst (Q - 1) (binomialSeries ℝ (-(k : ℝ))))
  • Logarithmic rows have exact degree ⌊n/r⌋ and positive coefficientsRealRooted original

    RealRooted.BrandenLeite.natDegree_affineLogCoeff_and_coeff_possource
    theorem natDegree_affineLogCoeff_and_coeff_pos
        (Q B : PowerSeries ℝ) (r : ℕ) (hQ : constantCoeff Q = 1) (hr : r ≠ 0)
        (hB : ∀ n, 0 ≤ coeff n B) (hBzero : ∀ n < r, coeff n B = 0)
        (hBpos : 0 < coeff r B)
        (hQpos : ∀ (k : ℕ), k ≠ 0 → ∀ m, 0 < coeff m
          (subst (Q - 1) (binomialSeries ℝ (-(k : ℝ)))))
        {n : ℕ} (hn : n ≠ 0) (hzero : 0 < (affineLogCoeff Q B n).coeff 0) :
        (affineLogCoeff Q B n).natDegree = n / r ∧
          ∀ k ≤ n / r, 0 < (affineLogCoeff Q B n).coeff k
  • Logarithmic rows are PF polynomials and consecutive rows interlaceRealRooted original

    RealRooted.BrandenLeite.affineLogCoeff_factor_pf_and_interlsource
    theorem affineLogCoeff_factor_pf_and_interl
        {ι ν : Type*} (s : Finset ι) (hs : s.Nonempty) (α : ι → ℝ)
        (hα : ∀ i ∈ s, 0 < α i) (t : Finset ν) (β : ν → ℝ)
        (hβ : ∀ j ∈ t, 0 ≤ β j) {c : ℝ} (hc : 0 < c)
        (r : ℕ) (hr : r ≠ 0) (n : ℕ) (hn : n ≠ 0) :
        let Q : Polynomial ℝ
  • Rational rod rows are the exponent-one negative-power rowsRealRooted original

    RealRooted.BrandenLeite.rationalRodRow_eq_affineNegativePowerCoeffsource
    theorem rationalRodRow_eq_affineNegativePowerCoeff
        (ys : List ℝ) (c : ℝ) {r : ℕ} (hr : r ≠ 0)
        (xs : List ℝ) (n : ℕ) :
        rationalRodRow ys c r xs n =
          affineNegativePowerCoeff 1 (rationalBackgroundDenominator ys)
            (markedFactorSeries c r xs) n
  • Numerators of two PF factors are PF polynomials and consecutive rows interlaceRealRooted original

    RealRooted.BrandenLeite.pfFactorNumerators_pf_and_interlsource
    theorem pfFactorNumerators_pf_and_interl
        {g h : ℕ → ℝ} (hg : IsPolyaFreqSeq g) (hh : IsPolyaFreqSeq h) :
        (∀ n, IsPFPolynomial (pfFactorNumerator g h n)) ∧
          ∀ n, Interl (pfFactorNumerator g h n)
            (pfFactorNumerator g h (n + 1))
  • With g(0), h(0) > 0 the zeros lie in [-1/(g(0) h(0)), 0]RealRooted original

    RealRooted.BrandenLeite.roots_pfFactorNumerator_mem_Icc_of_possource
    theorem roots_pfFactorNumerator_mem_Icc_of_pos
        {g h : ℕ → ℝ} (hg : IsPolyaFreqSeq g) (hh : IsPolyaFreqSeq h)
        (hg0 : 0 < g 0) (hh0 : 0 < h 0) (n : ℕ) :
        ∀ x ∈ (pfFactorNumerator g h n).roots,
          x ∈ Set.Icc (-((g 0) * h 0)⁻¹) 0
  • PF-factor numerators are the regularized kernel rows of the finite Toeplitz factorsRealRooted original

    RealRooted.BrandenLeite.pfFactorNumerator_eq_regularizedKernelRow_finsource
    theorem pfFactorNumerator_eq_regularizedKernelRow_fin
        (g h : ℕ → ℝ) {N : ℕ} (i : Fin (N + 1)) :
        pfFactorNumerator g h i.val =
          regularizedKernelRow (finiteToeplitz g N) (finiteToeplitz h N) i
  • Delayed renewal rows are reciprocal shifts of PF-factor numerators in each residue classRealRooted original

    RealRooted.BrandenLeite.renewalPolynomial_eq_reciprocalShift_pfFactorNumeratorsource
    theorem renewalPolynomial_eq_reciprocalShift_pfFactorNumerator
        (R : ℝ[X]) {m r : ℕ} (hrm : r < m) (q : ℕ) :
        renewalPolynomial R m (m * q + r) =
          reciprocalShift q
            (pfFactorNumerator (R ^ r).coeff
              (X * R ^ (m - r)).coeff q)
  • Delayed renewal rows of a PF polynomial are PFRealRooted original

    RealRooted.renewalPolynomial_isPF_of_isPFPolynomialsource
    theorem renewalPolynomial_isPF_of_isPFPolynomial
        {R : ℝ[X]} (hR : IsPFPolynomial R)
        {m r : ℕ} (hrm : r < m) (q : ℕ) :
        IsPFPolynomial (renewalPolynomial R m (m * q + r))
  • For R(0) > 0, consecutive renewal rows in a residue class are nonzero and interlaceRealRooted original

    RealRooted.strictInterl_renewalPolynomial_residue_succsource
    theorem strictInterl_renewalPolynomial_residue_succ
        {R : ℝ[X]} (hR : IsPFPolynomial R) (hR0 : 0 < R.coeff 0)
        {m r : ℕ} (hrm : r < m) (q : ℕ) :
        StrictInterl (renewalPolynomial R m (m * q + r))
          (renewalPolynomial R m (m * (q + 1) + r))

Lean source RealRooted/Challenges/Combinatorial/BrandenLeite.lean at revision d6670742. Formalized 2026-09-24.