Chow polynomials of totally nonnegative matrices

Chow polynomials and Chow derangement polynomials of a lower-unitriangular totally nonnegative matrix are real-rooted or zero, consecutive Chow polynomials interlace, and each Chow polynomial interlaces the Chow derangement polynomial of the same index.

Results

We use the zero-aware interlacing convention. For a lower-triangular matrix $A$, the Chow derangement polynomials are $d_0=1$ and $$ d_n=x\,S_{n-1}\Bigl(\sum_{k<n}A(n,k)\,d_k\Bigr),\qquad S_m(q)=\frac{x^mq(1/x)-q}{x-1}\quad(n\ge1), $$ and the Chow polynomials are $c_n=\sum_{k\le n}A(n,k)\,d_k$. For the incidence data of a poset these generalize the Chow polynomials of matroids and posets; see the Chow-polynomial definition on symmetricfunctions.com.

Theorem (Brändén–Vecchi). Let $A$ be lower unitriangular and totally nonnegative. Then for every $n$ the polynomials $c_n$ and $d_n$ have nonnegative coefficients and each is zero or real-rooted. Moreover $c_n\ll c_{n+1}$ and $c_n\ll d_n$ [BV25].

Theorem (Pólya frequency symbols). Let $\gamma,\alpha_i,\beta_i\ge0$ with $\sum_i(\alpha_i+\beta_i)<\infty$, and let $A$ be the lower Toeplitz matrix of the coefficients of $$ e^{\gamma z}\,\prod_i(1+\alpha_iz)\Big/\prod_i(1-\beta_iz). $$ Then every $c_n$ is a Pólya frequency polynomial, that is, it has nonnegative coefficients and only real nonpositive roots, and $c_n\ll c_{n+1}$.

Theorem (signed words). For finite lists of real numbers $x_1,\dots,x_p$ and $y_1,\dots,y_q$, let $A$ be the Toeplitz matrix of $\prod_i(1+x_iz)\big/\prod_j(1-y_jz)$. Then $c_n$ equals the signed-word enumerator of length-$n$ words by descents and collisions, with the letter weights $x_i$, $y_j$. For $x_1=\dots=x_m=1$ and no $y_j$, it is the descent polynomial of the Smirnov words of length $n$ in $m$ letters.

Proposition (zero prefix). Let $a$ be the sequence $0,0,0,1,1,1,\dots$ and let $A$ be its Toeplitz matrix. Then $a$ is a Pólya frequency sequence, but $c_6=x^2+x+1$ is not real-rooted.

Proof

The proof uses the resolution of totally nonnegative matrices by Whitney elimination, as on the Brändén–Saud Leite page.

References

  1. [BV25] Petter Brändén & Lorenzo Vecchi. Chow polynomials of totally nonnegative matrices and posets. arXiv e-prints, 2025.
    BibTeX
    @article{BrandenVecchi2025x,
      author = {Petter Brändén and Lorenzo Vecchi},
      title = {Chow polynomials of totally nonnegative matrices and posets},
      year = {2025},
      eprint = {2509.17852v3},
      url = {https://arxiv.org/abs/2509.17852v3},
      journal = {arXiv e-prints}
    }

Definitions

  • Chow derangement polynomials

    RealRooted.BrandenVecchi.chowDerangementsource
    def chowDerangement (A : LowerTriangularMatrix R) : ℕ → R[X]
      | 0 => 1
      | n + 1 =>
          X * Polynomial.chowS n (∑ k : Fin (n + 1),
            C (A (n + 1) k) * chowDerangement A k)
      termination_by n => n
      decreasing_by exact k.isLt
  • Chow polynomials of a lower-triangular matrix

    RealRooted.BrandenVecchi.chowPolynomialsource
    def chowPolynomial (A : LowerTriangularMatrix R) (n : ℕ) : R[X] :=
      ∑ k ∈ Finset.range (n + 1), C (A n k) * chowDerangement A k
  • Chow polynomials of a Pólya frequency symbol

    RealRooted.BrandenVecchi.aissenSchoenbergWhitneyEdreiChowsource
    def aissenSchoenbergWhitneyEdreiChow
        (gamma : ℝ) (alpha beta : ℕ → ℝ) (n : ℕ) : ℝ[X] :=
      chowPolynomial (aswEdreiToeplitz gamma alpha beta) n
  • Chow polynomials of a supersymmetric symbol

    RealRooted.BrandenVecchi.finiteSupersymmetricChowsource
    def finiteSupersymmetricChow (xs ys : List ℝ) (n : ℕ) : ℝ[X] :=
      chowPolynomial (finiteSupersymmetricToeplitz xs ys) n
  • A sequence shifted by a zero prefix and scaled

    RealRooted.BrandenVecchi.scaledZeroPrefixsource
    def scaledZeroPrefix (C : ℝ) (N : ℕ) (a : ℕ → ℝ) (d : ℕ) : ℝ :=
      if N ≤ d then C * a (d - N) else 0

Theorems

  • Chow polynomials have nonnegative coefficients

    RealRooted.BrandenVecchi.chowPolynomial_nonnegCoeffs_of_isTotallyNonnegsource
    theorem chowPolynomial_nonnegCoeffs_of_isTotallyNonneg
        (hunit : LowerTriangularMatrix.IsLowerUnitriangular A)
        (hA : Matrix.IsTotallyNonneg A) (n : ℕ) :
        HasNonnegCoeffs (chowPolynomial A n)
  • Each Chow polynomial is zero or real-rooted

    RealRooted.BrandenVecchi.chowPolynomial_eq_zero_or_splits_of_isTotallyNonnegsource
    theorem chowPolynomial_eq_zero_or_splits_of_isTotallyNonneg
        (hunit : LowerTriangularMatrix.IsLowerUnitriangular A)
        (hA : Matrix.IsTotallyNonneg A) (n : ℕ) :
        chowPolynomial A n = 0 ∨ (chowPolynomial A n).Splits
  • Chow derangement polynomials have nonnegative coefficients

    RealRooted.BrandenVecchi.chowDerangement_nonnegCoeffs_of_isTotallyNonnegsource
    theorem chowDerangement_nonnegCoeffs_of_isTotallyNonneg
        (hunit : LowerTriangularMatrix.IsLowerUnitriangular A)
        (hA : Matrix.IsTotallyNonneg A) (n : ℕ) :
        HasNonnegCoeffs (chowDerangement A n)
  • Each Chow derangement polynomial is zero or real-rooted

    RealRooted.BrandenVecchi.chowDerangement_eq_zero_or_splits_of_isTotallyNonnegsource
    theorem chowDerangement_eq_zero_or_splits_of_isTotallyNonneg
        (hunit : LowerTriangularMatrix.IsLowerUnitriangular A)
        (hA : Matrix.IsTotallyNonneg A) (n : ℕ) :
        chowDerangement A n = 0 ∨ (chowDerangement A n).Splits
  • Consecutive Chow polynomials interlaceMain result

    RealRooted.BrandenVecchi.chowPolynomial_interl_succ_of_isTotallyNonnegsource
    theorem chowPolynomial_interl_succ_of_isTotallyNonneg
        (hunit : LowerTriangularMatrix.IsLowerUnitriangular A)
        (hA : Matrix.IsTotallyNonneg A) (n : ℕ) :
        Interl (chowPolynomial A n) (chowPolynomial A (n + 1))
  • The Chow polynomial c_n interlaces the Chow derangement polynomial d_n

    RealRooted.BrandenVecchi.chowPolynomial_interl_chowDerangement_of_isTotallyNonnegsource
    theorem chowPolynomial_interl_chowDerangement_of_isTotallyNonneg
        (hunit : LowerTriangularMatrix.IsLowerUnitriangular A)
        (hA : Matrix.IsTotallyNonneg A) (n : ℕ) :
        Interl (chowPolynomial A n) (chowDerangement A n)
  • Pólya frequency symbols give Pólya frequency Chow polynomials

    RealRooted.BrandenVecchi.aissenSchoenbergWhitneyEdreiChow_isPFPolynomialsource
    theorem aissenSchoenbergWhitneyEdreiChow_isPFPolynomial
        {gamma : ℝ} {alpha beta : ℕ → ℝ} (hgamma : 0 ≤ gamma)
        (halpha : ∀ i, 0 ≤ alpha i) (hbeta : ∀ i, 0 ≤ beta i)
        (hsum : Summable fun i => alpha i + beta i) (n : ℕ) :
        IsPFPolynomial (aissenSchoenbergWhitneyEdreiChow gamma alpha beta n)
  • Consecutive Chow polynomials of a Pólya frequency symbol interlace

    RealRooted.BrandenVecchi.aissenSchoenbergWhitneyEdreiChow_interl_succsource
    theorem aissenSchoenbergWhitneyEdreiChow_interl_succ
        {gamma : ℝ} {alpha beta : ℕ → ℝ} (hgamma : 0 ≤ gamma)
        (halpha : ∀ i, 0 ≤ alpha i) (hbeta : ∀ i, 0 ≤ beta i)
        (hsum : Summable fun i => alpha i + beta i) (n : ℕ) :
        Interl (aissenSchoenbergWhitneyEdreiChow gamma alpha beta n)
          (aissenSchoenbergWhitneyEdreiChow gamma alpha beta (n + 1))
  • Chow polynomials of finite supersymmetric symbols are signed-word enumerators

    RealRooted.BrandenVecchi.finiteSupersymmetricChow_eq_finiteSignedWordEnumeratorsource
    theorem finiteSupersymmetricChow_eq_finiteSignedWordEnumerator
        (xs ys : List ℝ) (n : ℕ) :
        finiteSupersymmetricChow xs ys n =
          finiteSignedWordEnumerator xs ys n
  • Chow polynomials of (1+z)^m are Smirnov word descent polynomials

    RealRooted.BrandenVecchi.finiteSupersymmetricChow_replicate_one_nil_eq_smirnovsource
    theorem finiteSupersymmetricChow_replicate_one_nil_eq_smirnov
        (m n : ℕ) :
        finiteSupersymmetricChow (List.replicate m (1 : ℝ)) [] n =
          weightedSmirnovPolynomial (fun _ : Fin m => (1 : ℝ)) n
  • The sequence 0, 0, 0, 1, 1, 1, ... is a Pólya frequency sequence

    RealRooted.BrandenVecchi.three_zero_prefix_constant_isPolyaFreqSeqsource
    theorem three_zero_prefix_constant_isPolyaFreqSeq :
        IsPolyaFreqSeq (scaledZeroPrefix 1 3 (fun _ : ℕ => (1 : ℝ)))
  • For the sequence 0, 0, 0, 1, 1, ..., c_6 = x² + x + 1 is not real-rooted

    RealRooted.BrandenVecchi.chowPolynomial_three_zero_prefix_six_not_splitssource
    theorem chowPolynomial_three_zero_prefix_six_not_splits :
        ¬(chowPolynomial
          (toeplitz (scaledZeroPrefix 1 3 (fun _ : ℕ => (1 : ℝ)))) 6).Splits

Lean source RealRooted/Challenges/Combinatorial/BrandenVecchi.lean at revision d6670742. Formalized 2026-09-12.