1 Introduction↩︎

The study of algebraic invariants of posets and matroids has seen a remarkable development over the past two decades. It has led not only to the solution of long-standing conjectures on positivity in matroid theory, see [1], but also opened up new lines of research and led to new positivity questions. For example, the Kazhdan-Lusztig polynomial, the \(Z\)-polynomial, the Hilbert-Poincaré series of the Chow ring, and the chain polynomial of the lattice of flats of any matroid have been conjectured to have only real zeros [2]–[6]. To match the complex recursions satisfied by these polynomials, there is a need for new methods on the geometry of zeros of polynomials that can handle such recursions. Equally important is to reveal new relations and recursions among these polynomials, ones that match better the type of recursions that the existing theory on zeros of polynomials can handle. These are the two motivating purposes of the paper.

In their influential work [7], Feichtner and Yuzvinsky introduced the Chow ring of an atomistic lattice \(L\), and gave a presentation for it via relations in terms of chains in the lattice. This ring is graded and finite-dimensional, allowing one to study its Hilbert-Poincaré series as an invariant of the lattice. When \(L\) is a geometric lattice, then the Chow ring satisfies the Kähler package [8], which implies that the Hilbert series of the Chow ring of a geometric lattice is always palindromic and unimodal. Moreover for specific classes of geometric lattices, these Hilbert series coincide with well-known families of polynomials; for example for boolean algebras one recovers the Eulerian polynomials, and for truncations of boolean algebras one recovers the derangement polynomials [9]. For these reasons, the Hilbert series of Chow rings of geometric lattices (or matroids) have garnered importance on their own and are now known as the Chow polynomials of matroids. A tightly connected construction is the one of augmented Chow ring of \(L\) introduced in [10], whose Hilbert series is known as the augmented Chow polynomial.

Ferroni-Schröter [5] and Huh-Stevens [4] independently conjectured that Chow polynomials and augmented Chow polynomials of matroids have only real zeros. This was recently verified in the uniform case in [11] and [12], respectively. Ferroni, Matherne and the second author extended the definition of Chow polynomials to arbitrary bounded posets using the framework of Kazhdan-Lusztig-Stanley theory [13]. These are palindromic polynomials that are conjectured to have only real zeros for all Cohen-Macaulay posets and Bruhat intervals (with the appropriate \(P\)-kernels [13]). In this larger context, Hoster and Stump [14] proved that Chow polynomials of boolean complexes with nonnegative \(h\)-vectors are real-rooted.

In this paper we develop a systematic approach to the study of zeros of Chow polynomials for a class of posets called \(\mathop{\mathrm{\mathrm{TN}}}\)-posets, which were introduced in [15], [16]. This class includes (rank-selected subposets of) affine and projective geometries, perfect matroid designs, dual partition lattices and dual Dowling lattices. To do so, we define and study Chow polynomials of totally nonnegative matrices (\(\mathop{\mathrm{\mathrm{TN}}}\)-matrices), i.e., matrices whose minors are all nonnegative. Our main result is Theorem 19, which states that the Chow polynomial of any lower triangular \(\mathop{\mathrm{\mathrm{TN}}}\)-matrix with all diagonal entries equal to one is real-rooted. A direct consequence of this is Theorem 25, which says that the Chow polynomial of any \(\mathop{\mathrm{\mathrm{TN}}}\)-poset is real-rooted. We also use our methods to prove that the Chow polynomial of any paving matroid is real-rooted, Corollary 11.
Outline. The structure of the paper is as follows. In Section 2 we review relevant Kazhdan–Lusztig–Stanley theory for posets, and provide new defining relations and properties of Chow functions (Theorem 2), and augmented Chow functions (Theorem 6). These relations reveal that a Chow polynomial always comes paired with another polynomial that we call a Chow-derangement polynomial. This pairing may be seen as a generalization of the classical pairing of Eulerian polynomials and derangement polynomials, see e.g. [17], [18].

In Section 3 we use the machinery developed in Section 2 to define and study (augmented) Chow polynomials of matrices. We relate this construction to (augmented) Chow polynomials of weak-rank uniform posets, a class of highly structured posets. We define and study a notion of \(\mathcal{I}_n\)-interlacing sequences of polynomials, which refines the notion of interlacing sequences to the case when the zeros of the polynomial in question interlace the zeros of its reciprocal. The new defining relations for Chow functions obtained in Section 2 translate into recursions that preserve \(\mathcal{I}_n\)-interlacing sequences of polynomials when combined with resolvability of \(\mathop{\mathrm{\mathrm{TN}}}\)-matrices (Definition 1), thus refining the method using resolvability that was initiated in [15]. This is used to prove interlacing preserving properties of the so called Chow-deranged map and the Chow-Eulerian transformation associated to a matrix \(R\). These are vast generalizations of two results of the first author and Solus [18], and Athanasiadis [19], respectively, on real-rootedness preserving properties of the deranged map and the Eulerian transformation. Indeed Theorems 17 and 18 generalize these results to any lower triangular \(\mathop{\mathrm{\mathrm{TN}}}\)-matrix with all diagonal entries equal to one. A direct consequence is Theorem 19 which states that the Chow polynomials associated to any such matrix are real-rooted.

In Section 5 we provide an explicit interpretation of the coefficients of the \(\gamma\)-polynomial of Chow polynomials of matrices as sums of certain minors of the matrix (Corollary 8) and as enumerators of certain non-intersecting paths in a network, following the work by Gessel and Viennot [20]. In Sections 6 and 7 we prove Theorem 25 and Theorem 27, which assert that (augmented) Chow polynomials of \(\mathop{\mathrm{\mathrm{TN}}}\)-posets and generalized paving posets (a class of posets that contains lattices of flats of paving matroids) are real-rooted.

In Section 8, we study the case of Toeplitz matrices in greater detail, and provide generating function identities for the Chow polynomials of interest in Theorem 28. In Theorem 31, we prove that the Chow polynomials associated to Toeplitz matrices of Pólya frequency sequences are real-rooted. In Section 8.1 we provide expressions for the generating series for the various Chow polynomials in the case when \(P\) is a binomial poset or a Sheffer poset. These are classes of highly regular posets studied by Doubilet, Rota and Stanley [21], and Ehrenborg and Readdy [22], respectively.

In Section 8.2 we show that the Chow polynomials associated to the Toeplitz matrices \((e_{i-j}(\mathbf{x}))_{i,j=0}^\infty\) and \((h_{i-j}(\mathbf{x}))_{i,j=0}^\infty\) coincide with the generalized Eulerian polynomials, with symmetric function coefficients, that have been studied frequently in the literature, by Stanley, Brenti, Stembridge, Shareshian and Wachs and others, see [23] and the references therein. Hence the theory developed in this paper serves as a framework for these polynomials, that, for example, enables us to reprove Schur \(\gamma\)-positivity results of Gessel and Shareshian-Wachs, as well as real-rootedness for the polynomials obtained when \(\mathbf{x}\) and \(\mathbf{y}\) are chosen to be suitable real and nonnegative vectors.

2 The incidence algebra and Chow functions↩︎

In this section we recall the construction of Chow functions and Chow polynomials of partially ordered sets (posets). For undefined poset terminology, we refer to [24]. Recall that an interval of a poset is a subposet of \(P\) of the form \([x,y]= \{z \in P : z\leq z \leq y\}\), where \(x,y\in P\). All posets \(P\) considered in this paper are locally finite, i.e., each interval of \(P\) is finite. We also say that a poset is bounded if it has unique least and largest elements, which we denote by \(\hat{0}\) and \(\hat{1}\), respectively. Given a poset \(P\), a weak rank function is a function \(\rho: P\times P \to \mathbb{N}\) such that

• \(\rho(x,y) = \rho_{x,y} > 0\) if and only if \(x < y\), and

• \(\rho_{x,y} = \rho_{x,z} + \rho_{z,y}\), for all \(x\leq z \leq y\) in \(P\).

A weakly ranked poset consists of a pair \((P,\rho)\), where \(\rho\) is a weak rank function for \(P\). By slight abuse of notation, we say that \(P\) is a weakly ranked poset, when this does not create confusion. If the poset has a least element \(\hat{0}\), we write \(\rho(x):= \rho_{\hat{0},x}\) for an element \(x \in P\) and call this the (weak) rank of \(x\) in \(P\). If \(\rho_{x,y} =1\) whenever \(y\) covers \(x\), then we say that \(P\) is graded (or ranked). Moreover if \(P\) is bounded, then we say that \(P\) has (weak) rank \(\rho(\hat{1})\).

The incidence algebra of a poset \(P\) over a ring \(R\) is the free \(R\)-module spanned by the intervals of \(P\). More explicitly, an element \(f\) associates to every interval \([x,y]\) of \(P\) an element in \(R\) which we denote by \(f_{x,y}\). The product (convolution) is defined by \[(fg)_{x,y} = \sum_{x\leq z \leq y}f_{x,z}g_{z,y}.\] We denote by \(\delta\) the multiplicative identity. In this paper the ring \(R\) will be a polynomial ring \(R= \mathrm{R}[t]\), where \(\mathrm{R}\) is an integral domain¹, and we denote by \(I(P)=I_{\mathrm{R}[t]}(P)\) the incidence algebra over \(\mathrm{R}[t]\). For a polynomial \(f \in \mathrm{R}[t]\) of degree at most \(n\), we define \[\mathcal{I}_n(f) = t^nf(t^{-1})\] and say that \(f\) is palindromic with center of symmetry \(n/2\), if \({\mathcal{I}_n(f) = f}\). Let \(I_\rho(P)\) the subalgebra of \(I(P)\) consisting of functions \(f\) such that \(\deg f_{x,y} \leq \rho_{x,y}\) for all \(x,y \in P\), and define \(\mathcal{I}: I_\rho(P) \to I_\rho(P)\) by \[\mathcal{I} (f)_{x,y} = \mathcal{I}_{\rho_{x,y}}(f_{x,y}), \quadfor allx\leq y.\] Hence \(\mathcal{I}\) is an involution and an automorphism, i.e., \(\mathcal{I}^2=\delta\) and \(\mathcal{I}(fg)=\mathcal{I}(f)\mathcal{I}(g)\) for all \(f,g \in I_\rho(P)\).

Given a weakly ranked poset \(P\), an element \(\kappa\) in \(I_\rho(P)\) is called a \(P\)-kernel if

• \(\kappa_{x,x} = 1\) for each \(x \in P\), and

• \(\kappa^{-1} = \mathcal{I}(\kappa)\).

The following theorem gives a characterization of \(P\)-kernels.

The function \(g\) is called the left Kazhdan-Lusztig-Stanley function associated to \(\kappa\).

Following [13], we define the reduced \(P\)-kernel to be the function \(\overline{\kappa} \in I_\rho(P)\) defined by \[\overline{\kappa} = \frac{1}{t-1} (\kappa-t\delta).\] Notice that \(\kappa-t\delta\) evaluated at \(t=1\) is equal to \(g(1)^{-1}g(1)-\delta=0\), and hence \(t-1\) divides \(\kappa-t\delta\) and thus \(\overline{\kappa}\) is an element of \(I_\rho(P)\) as claimed. The Chow function associated to \(\kappa\) (or \(g\)) is defined as the element of \(I_\rho(P)\), \[\label{Chow-def} (-\overline{\kappa})^{-1},\tag{2}\] i.e., the negative inverse of the reduced \(P\)-kernel.

Define a family of operators \(\mathcal{S}_n\), \(n \in \mathbb{N}\), on polynomials of degree at most \(n\) in \(\mathrm{R}[t]\) by \[\mathcal{S}_n(f )= \frac{\mathcal{I}_n(f) - f}{t-1}.\] The following theorem provides an alternative definition of the Chow function.

We call the unique function \(d\) achieved by Theorem 2 the Chow-derangement function associated to \(g\). If the poset is bounded, we call \(H_P = H_{\hat{0},\hat{1}}\) the Chow polynomial of \(P\) (with respect to \(g\)) and \(d_P= d_{\hat{0},\hat{1}}\) the Chow-derangement polynomial of \(P\).

Later in the paper, we will need the following slightly weaker version of Theorem 2.

In this paper we will be mostly concerned with a special class of functions \(g\), where \(g_{x,y} \in \mathrm{R}\) for all \(x\leq y\) and \(g_{x,x} = 1\) for each \(x \in P\). We call such functions scalar. An example of a scalar function is \(\zeta\), the zeta function of \(P\), which is defined by \(\zeta_{x,y} =1\) for all \(x \leq y\) in \(P\).

One would like an explicit interpretation of the function \(d\) in terms of the \(H\) polynomials. We will use the following non-recursive formula for \(H\).

When \(g\) is scalar, this simplifies to the following result.

We provide an interpretation for \(d\) in the case of scalar \(g\). For a weakly ranked and bounded poset \(P\) of rank \(n\), we denote by \(\tau(P)\) the truncation of \(P\), obtained from \(P\) by removing all elements of rank \(n-1\) and by setting the new rank of \(\hat{1}\) to be equal to \(n-1\). We keep denoting the rank function in the truncation by \(\rho\) to not overload the notation. If \(g \in I(P)\) is scalar², then the function \(g\) restricted to intervals of \(\tau(P)\) is still a function satisfying 1 . In particular one can define Chow functions with respect to \(g\) also in \(\tau(P)\).

2.1 Augmented Chow functions↩︎

In [13] the augmented Chow function was defined as the element in \(I_\rho(P)\), \[\label{Aug-Chow-def} \mathcal{I}(g) H.\tag{9}\] The next theorem offers an alternative equivalent definition.

We call the unique function \(A\) the Chow-Eulerian function associated to \(g\). When \(P\) is bounded, \(G_P = G_{\hat{0},\hat{1}}\) is called the augmented Chow polynomial of \(P\) (with respect to \(g\)) and \(A_P = A_{\hat{0},\hat{1}}\) is called the Chow-Eulerian polynomial of \(P\).

The proof of the next corollary is the same as that of Corollary 1.

We shall now see that augmented Chow polynomials are themselves Chow polynomials. This extends [13] where the case when \(g =\zeta\) was proved. Let \(P\) be a poset with a unique least element \(\hat{0}_P\). Denote by \((\mathrm{aug}(P),\rho_\mathrm{aug})\) the augmentation of \(P\), i.e., the poset obtained from \(P\) by adding a new least element \(\hat{0}_\mathrm{aug}\). The rank function \(\rho_\mathrm{aug}\) is such that \[(\rho_\mathrm{aug})_{x,y} = \begin{cases} \rho_{x,y}, & ifx\neq \hat{0}_\mathrm{aug},and \\ \rho_{\hat{0}_P,y} + 1, & ifx = \hat{0}_\mathrm{aug} and\;y \neq \hat{0}_\mathrm{aug}. \end{cases}\] Define the element \(\overline{g} \in I(\mathrm{aug}(P))\) by \[\overline{g}_{x,y} = \begin{cases} g_{x,y}, & ifx \neq \hat{0}_\mathrm{aug},and\\ g_{\hat{0}_P,y}, & ifx= \hat{0}_\mathrm{aug} and\;y \neq \hat{0}_\mathrm{aug},\\ 1, & if x= y = \hat{0}_\mathrm{aug}. \end{cases}\]

3 Chow polynomial of matrices and weak-rank uniform posets↩︎

Let \(R=(r_{n,k})_{n,k=0}^N\), where \(N \in \mathbb{N}\cup \{\infty\}\), be a lower triangular matrix with all diagonal entries equal to one. Consider the chain \([0,N]=\{0<1<\cdots<N\}\) graded by the rank function \(\rho(n) = n\). Then the matrix \(R\) corresponds to an element \(g = g[R]\) in the incidence algebra of \([0,N]\) defined by \[g_{k,n} = r_{n,k}, \quadfor all0\leq k \leq n \leq N.\] Clearly \(g\) satisfies 1 and therefore we can define the corresponding Chow, Chow-derangement, augmented Chow, and Chow-Eulerian polynomials. Corollaries 1 and 4 then translate as the following corollaries which provide the defining relations for these polynomials.

In Section 8 we will need the following result which tells us how the Chow polynomials behave under conjugation by a diagonal matrix.

Next we will see how Corollary 2 gives a non-recursive formula to compute \(H_n\). For \(S = \{ s_1 < s_2 < \cdots < s_m\} \subseteq [n-1]\) let \[\alpha_{[0,n]}(S) = \prod_{i=1}^{m+1} r_{s_i,s_{i-1}},\] where \(s_0 = 0\) and \(s_{m+1} = n\).

Let \(\partial_n R\) denote the matrix obtained from \(R\) by deleting the row and column indexed by \(n\). Theorem 4 implies that the Chow-derangement polynomials asssociated to \(R\) may be expressed as \[\label{dntruncR} d_n = \begin{cases} 1, &ifn=0,\\ 0, &ifn=1,\\ tH_{n-1}[\partial_{n-1}R], &ifn>1. \end{cases}\tag{13}\] In particular, \[H_n = r_{n,0} + t \sum_{k=2}^n r_{n,k}H_{k-1}[\partial_{k-1}R], \quad n\geq 0.\]

Let also \(\overline{R}=(\overline{r}_{n,k})_{n,k=0}^{N+1}\) be the matrix obtained form \(R\) by adding a new initial row \([1,0,0,\ldots]\) and a new initial column \([1,r_{0,0}, r_{1,0}, r_{2,0}, \ldots]\). Then, by Theorem 7, the augmented Chow polynomials \(G_n\) of \(R\) satisfy \[\label{aug-matrx} G_n= H_{n+1}[\overline{R}], \quad n \geq 0.\tag{14}\]

Similarly, the Chow-Eulerian polynomials \(A_n\) satisfy \(A_0=1\), and \[\label{DR-def} A_n = t H_n[\partial_n \overline{R}], \quad n \geq 1.\tag{15}\]

3.1 Weak-rank uniform posets↩︎

We shall now see that the Chow polynomials of certain matrices are actually characteristic Chow polynomials of posets, by following the construction in [15]. We say that a weakly ranked poset \(P\) with a least element \(\hat{0}\) is weak-rank uniform if for any \(x\) and \(y\) in \(P\) with \(\rho(x) = \rho(y)\), \[\label{wru} |\{z \leq x : \rho(z) = k\}| = |\{z \leq y : \rho(z) = k\}|, \quad \text{ for each }0\leq k \leq \rho(x).\tag{16}\] If \(\rho(x) = n\), we define \(r_{n,k}=r_{n,k}(P) = |\{z \leq x : \rho(z) = k \}|\), and write \(R = R(P) = (r_{n,k})_{n,k\geq 0}\). Notice that \(r_{n,0} = r_{n,n} = 1\) for each \(n\). If \(P\) is graded and satisfies 16 , then we say that \(P\) is rank-uniform.

4 Totally nonnegative matrices and their Chow-polynomials↩︎

The main result of this section is Theorem 19, which says that the Chow polynomial of any lower triangular and totally nonnegative matrix with all diagonal entries equal to one is real-rooted. We shall first prepare for the proof of this result by introducing relevant notation and proving some preliminary results on interlacing sequences of polynomials.

4.1 Totally nonnegative and resolvable matrices↩︎

We start by collecting some notation and results from [15]. Recall that a matrix with real entries is totally nonnegative (or \(\mathop{\mathrm{\mathrm{TN}}}\)) if all of its minors are nonnegative.

If the matrix \(R\) is resolvable, then we say that the polynomials \((R_{n,k})_{0\leq k \leq n \leq N}\) resolve \(R\).

Notice that if \(R\) is resolvable, then by 17 , \[\label{r-sum} R_{n+1,k}= t^{n+1}+ \sum_{j \geq k} \lambda_{n,j}R_{n,j}, \;\;\;\;0\leq k \leq n<N.\tag{18}\] The next theorem, proved in [15], characterizes resolvability in terms of totally nonnegative matrices and “quantum” real-rooted polynomials.

4.2 Interlacing zeros and \(\mathcal{I}_n\)-interlacing sequences of polynomials↩︎

Recall that a polynomial \(p \in \mathbb{R}[t]\) is called real-rooted if all of its zeros are real. For technical reasons, the zero polynomial is considered to be real-rooted. Suppose \(p\) and \(q\) are two real-rooted polynomials in \(\mathbb{R}[t]\) with zeros \(\cdots \leq \beta_2 \leq \beta_1\) and \(\cdots \leq \alpha_2 \leq \alpha_1\), respectively. The zeros interlace if \[\cdots \leq \beta_2 \leq \alpha_2 \leq \beta_1\leq \alpha_1 \;\;\; or\;\;\; \cdots \leq \alpha_2 \leq \beta_2 \leq \alpha_1 \leq \beta_1.\] If \(p\) and \(q\) have interlacing zeros, then the Wronskian \(W[p,q]:=p'q-pq'\) is either nonpositive on \(\mathbb{R}\) or nonnegative on \(\mathbb{R}\). We write \(p \prec q\) if \(p\) and \(q\) are real-rooted, their zeros interlace, and \(W[p,q] \leq 0\) on all of \(\mathbb{R}\). For technical reasons we consider the identically zero polynomial to be real-rooted and write \(0 \prec p\) and \(p \prec 0\) for any other real-rooted polynomial \(p\).

A polynomial \(f \in \mathbb{C}[t]\) is called stable if either \(f \equiv 0\) or all the zeros of \(f\) have nonpositive imaginary parts. The Hermite-Biehler theorem relates stability to interlacing zeros, for a proof see [28]⁴.

One consequence of Theorem 13 is that \(p\) and \(q\) in \(\mathbb{R}[t]\) are real-rooted whenever \(q+ip\) is stable. Moreover, it follows that for real-rooted polynomials \(p\) and \(q\) in \(\mathbb{R}[t]\):

• \(p \prec \alpha p\) for all \(\alpha \in \mathbb{R}\),

• \(p\prec q\) if and only if \(-q \prec p\),

• \(p\prec q\) if and only if \(\alpha p \prec \alpha q\), for some \(\alpha \in \mathbb{R}\setminus \{0\}\).

The following lemma follows directly from Remark 12.

We will make frequent use of the following proposition.

A sequence of polynomials \(f_1, \ldots, f_m \in \mathbb{R}_{\geq 0}[t]\) is called interlacing if \(f_i \prec f_j\) for all \(i<j\). The following elementary lemma is useful when proving that sequences of polynomials are interlacing, see e.g. [28].

We will now define a central notion of this paper.

The next lemma provides some simple operations that preserve interlacing and \(\mathcal{I}_n\)-interlacing sequences.

Let \(\mathbb{I}_n\) be the set of all polynomials \(f \in \mathbb{R}_{\geq 0}[t]\) of degree at most \(n\) for which \(f \prec I_n(f)\).

4.3 Chow-deranged maps and Chow-Eulerian transformations↩︎

Let \(R=(r_{n,k} )_{n,k=0}^N\), where \(N \in \mathbb{N}\cup\{\infty\}\), be a lower triangular matrix, with entries in \(\mathrm{R}\), and with all diagonal entries equal to one. Let further \(\mathrm{R}_N[t]\) be the \(\mathrm{R}\)-module of all polynomials in \(\mathrm{R}[t]\) of degree at most \(N\). We define two \(\mathrm{R}\)-linear maps \(\mathcal{D}=\mathcal{D}_R : \mathrm{R}_N[t] \to \mathrm{R}_N[t]\) and \(\mathcal{A}=\mathcal{A}_R: \mathrm{R}_N[t] \to \mathrm{R}_N[t]\) \[\mathcal{D}(t^n)= d_n \quadand\quad \mathcal{A}(t^n) = A_n, \quad n \leq N,\] where \(d_n\) and \(A_n\) are the Chow-derangement polynomials and Chow-Eulerian polynomials associated to \(R\), respectively. These maps are called the Chow-deranged map and the Chow-Eulerian map, respectively. Notice that (iv) in Corollaries 6 and 7 translate to \[H_n = \mathcal{D}(R_n) \quadand\quad G_n= \mathcal{A}(R_n).\]

Theorem 18 below generalizes Athanasiadis result to any resolvable matrix. Suppose \(R\) is resolvable, and define \[d_{n,k} = \mathcal{D}(R_{n,k}) \quadandA_{n,k} = \mathcal{A}(R_{n,k}), \quad 0\leq k \leq n \leq N.\]

The proof of the next theorem is identical to that of the previous.

The first important consequence of Theorem 17 establishes the real-rootedness of the Chow polynomials and Chow-derangement polynomials of any lower triangular \(\mathop{\mathrm{\mathrm{TN}}}\)-matrix with all diagonal entries equal to one.

Again, the proof of the augmented version of Theorem 19 is identical.

5 \(\gamma\)-Chow polynomials of matrices↩︎

The linear space of all palindromic polynomials with center of symmetry \(n/2\) has a basis \(\{t^k(1+t)^{n-2k}\}_{k=0}^{\lfloor n/2\rfloor}\). Hence, if \(\mathcal{I}_n(f)=f\), we may define its \(\gamma\)-polynomial, \(\gamma(f)\), to be the unique polynomial of degree at most \(\lfloor n/2\rfloor\) for which \[f = (1+t)^n\gamma(f)\left(\frac{t}{(1+t)^2} \right),\] see [32]. These polynomials satisfy the following properties that we will use freely.

• \(\gamma(fg) = \gamma(f)\gamma(g)\),

• in particular, \(\gamma((1+t)f) = \gamma(f)\) and \(\gamma(tf) = t\gamma(f)\),

• if \(f\) and \(g\) have the same center of symmetry, \(\gamma(f+g) = \gamma(f) + \gamma(g)\).

5.1 Coefficients of \(\gamma\)-Chow polynomials of matrices↩︎

Given a lower triangular matrix \(R=(r_{n,k})_{n,k=0}^N\) with all diagonal entries equal to one, we know that the Chow polynomials \(H_n=H_n[R]\) are palindromic with center of symmetry \((n-1)/2\). We write \(\gamma_n[R] = \gamma(H_n[R])\) for the \(\gamma\)-polynomial of \(H_n[R]\), and we call it a \(\gamma\)-Chow polynomials of the matrix \(R\). The main goal of this section is to give an interpretation to the coefficients of these polynomials. For a set \({S =\{s_1< \cdots < s_k\} \subseteq [n-1]}\) define \[\beta_{[0,n]}(S) = \sum_{T \subseteq S} (-1)^{|S\setminus T|} \alpha_{[0,n]}(T).\] A set \(S\) of integers is called stable if it does not contain any two consecutive integers.

For \(C,D \subseteq [0, N]\), denote by \(R[C,D]\) the submatrix of \(R\) with rows indexed by \(C\) and columns indexed by \(D\).

Notice that when \(R\) is \(\mathop{\mathrm{\mathrm{TN}}}\), then Corollary 8 immediately implies that the coefficients of the \(\gamma\)-Chow polynomials associated to \(R\) are nonnegative.

Suppose \(R\) is a resolvable matrix. Then the minors of \(R\) have a combinatorial interpretation in terms of the \(\lambda_{n,k}\)’s as follows. For \(N \in \mathbb{N}\cup\{\infty\}\), let \(\Gamma_N\) be the directed graph on \(\{ (i,j) \in \mathbb{N}^2: j\leq i \leq N\}\) with edges \[(i,j) \to (i,j+1) \;\;\; and\;\;\;(i+1,j) \to (i,j),\] and let \(\lambda=(\lambda_{i,j})_{0\leq j \leq i < N}\) be an array of nonnegative numbers.

Attach the weight \(\lambda_{i,j}\) to the vertical edge \((i+1,j) \to (i,j)\), and attach the weight \(1\) to each horizontal edge, see Figure 1. Let further \(r_{n,k}(\Gamma_N, \lambda)\) be the weighted sum of all paths from \((n,0)\) to \((k,k)\), where the weight of a path is the product of the weights of the edges used in the path, and let \(R(\Gamma_N, \lambda)= \left(r_{n,k}(\Gamma_N, \lambda)\right)_{n,k=0}^N\). By [15], \(R=R(\Gamma_N, \lambda)\).

Associate to \(\sigma \in \mathfrak{S}_n\) a function \(f=f_\sigma : [n] \rightarrow \mathbb{N}\) for which \(f(i)\leq i-1\) for each \(i\) by \[f_\sigma(j)= |\{i<j:\sigma(i)>\sigma(j)\}|.\] Recall that \(i \in [n-1]\) is called a descent of \(\sigma \in \mathfrak{S}_n\) if \(\sigma(i) > \sigma(i+1)\). Let \(\mathrm{D}(\sigma)= \{i \in [n-1] : \sigma(i) > \sigma(i+1)\}\) denote the descent set of \(\sigma\). The following theorem now follows from a result due to Gessel and Viennot [20].

The next theorem now follows from Theorems 21 and 22.

5.2 Interlacing properties of \(\gamma\)-Chow polynomials↩︎

Next we will prove some refined interlacing properties satisfied by \(\gamma\)-Chow polynomials of \(\mathop{\mathrm{\mathrm{TN}}}\)-matrices. These will be used in Section 7 to prove that Chow polynomials of paving matroids are real-rooted.

The following result relates the zeros of a polynomial with the zeros of its \(\gamma\)-polynomial.

Let \(R\) be a lower triangular matrix with all diagonal entries equal to one. Define polynomials \(\sigma_{n,k}\) and \(\tau_{n,k}\), \(0\leq k \leq n\), in \(\mathrm{R}[t]\) by \[\sigma_{n,k} = \gamma(\mathcal{S}_n(d_{n,k})) \quadand\quad \tau_{n,k} = \gamma(\mathcal{S}_{n+1}(d_{n,k})).\]

We collect some simple properties of the operators \(\mathcal{S}_n\) in a lemma.

The following corollary will be used to prove that Chow polynomials of paving matroids are real-rooted.

6 Chow polynomials of \(\mathrm{TN}\)-posets↩︎

In this paper, a weakly rank-uniform poset \(P\) is called a \(\mathop{\mathrm{\mathrm{TN}}}\)-poset if the matrix \(R(P)\) is \(\mathop{\mathrm{\mathrm{TN}}}\). Below is a list of examples of \(\mathop{\mathrm{\mathrm{TN}}}\)-posets, for proofs see [15], [16].

• Boolean cell complex with nonnegative \(h\)-vectors. For example Cohen-Macaulay simplicial complexes and face lattices of simplicial polytopes.

• Cubical complexes with nonnegative cubical \(h\)-vectors [35]. These include face lattices of cubical polytopes, i.e., polytopes for which all faces are hypercubes.

• \(q\)-poset with nonnegative \(h\)-vectors [36]. For example shellable \(q\)-complexes [37].

• Perfect matroid designs [38], i.e., rank uniform geometric lattices. These include (truncations of) projective geometries and affine geometries.

• Dual of Dowling lattices [39]. In particular, the dual of partition lattices.

Recall that if \(P\) is a weakly ranked poset of rank \(r\) and \(S \subseteq [r-1]\), then \[P_S= \{ x \in P : \rho(x) \in S \cup \{0,r\}\}\] is the rank selected subposet induced by \(S\). Since submatrices of \(\mathop{\mathrm{\mathrm{TN}}}\)-matrices are \(\mathop{\mathrm{\mathrm{TN}}}\) it follows that the class of \(\mathop{\mathrm{\mathrm{TN}}}\)-posets is closed under rank selection. Hence any rank-selected poset of any poset listed above is \(\mathop{\mathrm{\mathrm{TN}}}\).

If we apply Theorem 25 to a above, then we recover the result of Hoster and Stump [14].

It follows from [16] that \(\mathrm{aug(P)}\) is \(\mathop{\mathrm{\mathrm{TN}}}\) whenever \(P\) is \(\mathop{\mathrm{\mathrm{TN}}}\). Hence the above results are also true for the characteristic augmented Chow polynomials.

Recall that the characteristic augmented Chow polynomial of a poset \(P\) is equal to the one of its dual \(P^*\) by [11], from which the following consequence follows.

7 Chow polynomials of lattices of flats of paving matroids↩︎

Let \(P\) be a graded, rank uniform and bounded poset of rank \(n\) and let \(0\leq d <n\). Consider a subset \(\mathcal{H} \subseteq P\) of pairwise incomparable elements such that \(d < \rho(x) < n\) for each \(x \in \mathcal{H}\). Let \(P(d,\mathcal{H})\) be the weakly ranked poset of rank \(n\) obtained by adjoining \(\hat{1}\) and \(\mathcal{H}\) to the set \(\{x \in P \mid \rho(x) \leq d\}\) and by declaring all elements in \(\mathcal{H}\) to be of rank \(d+1\) and \(\rho(\hat{1}) = d+2\). Notice also that if \[\label{paving32graded32condition} \text{for each x of rank \rho(x) \leq d there exists a y \in \mathcal{H} such that x\leq y},\tag{20}\] then \(P(d,\mathcal{H})\) is graded again. If \(P\) is a boolean algebra on \(n\) elements and \(\mathcal{H}\) satisfies 20 , then \(P(d,\mathcal{H})\) is a paving geometric lattice of rank \(d+2\).

8 Toeplitz matrices↩︎

In this section we will focus on the special case when \(R\) is a Toeplitz matrix. Let \(\{a_n\}_{n=0}^\infty\) be a sequence of elements in an integral domain \(\mathrm{R}\), where \(a_0=1\). Associate to \(\{a_n\}_{n=0}^\infty\) the lower triangular Toeplitz matrix \(R=(a_{n-k})_{n,k=0}^\infty\), where \(a_m=0\) if \(m<0\).

Consider the formal power series \(f= \sum_{n=0}^\infty a_nz^n\) in \(\mathrm{R}[[z]]\), and define formal power series in \(\mathrm{R}[t][[z]]\) by \[\begin{align} {2} D(z,t) &= \sum_{n =0}^\infty d_n(t) z^n, \quad H(z,t) &= \sum_{n=0}^\infty H_n(t) z^n, \\ A(z,t) &= \sum_{n =0}^\infty A_n(t) z^n, \quad G(z,t) &= \sum_{n=0}^\infty G_n(t) z^n. \end{align}\] where \(d_n(t), H_n(t), A_n(t)\) and \(G_n(t)\) are the Chow-derangement polynomials, Chow polynomials, Chow-Eulerian polynomials and augmented Chow polynomials associated to \(R\), respectively.

The next proposition provides the generating function for the Chow polynomials of iterated truncations of the Toeplitz matrix corresponding to \(f(z)\).

A sequence \(\{a_n\}_{n=0}^\infty\) of real numbers is a Pólya frequency sequence if the Toeplitz matrix \(R=(a_{n-k})_{n,k=0}^\infty\) is \(\mathop{\mathrm{\mathrm{TN}}}\). Pólya frequency sequences were characterized by Aissen, Schoenberg, Whitney and Edrei [40] as follows.

Applying Theorem 19 to Toeplitz matrices produces four families of real-rooted polynomials to any series \(f\) of the form 21 .

8.1 Binomial and Sheffer posets↩︎

Recall [21], [24], [42] that a binomial poset is a locally finite poset \(P\) for which

• there exists an infinite chain in \(P\),

• each interval of \(P\) is graded, and

• there exists a function \(B : \mathbb{N}\to \mathbb{N}\), called the factorial function of \(P\), such that the number of maximal chains in any interval \([x,y]\) in \(P\) is equal to \(B(\rho(x,y))\).

Hence \(P\) is rank uniform with \[\label{rank-B} r_{n,k}(P) = \frac{B(n)}{B(k)\cdot B(n-k)}, \quad 0 \leq k \leq n,\tag{22}\] since each maximal chain in \([\hat{0}, x]\), \(\rho(x)=n\), passes through a unique element of rank \(k\).

Let \(\mathbb{F}_q\) be a field with \(q\) elements, and let \(V(q)\) be the free \(\mathbb{F}_q\)-linear space over the set \(\{e_1, e_2, \ldots\}\). Let further \(\mathbb{B}(q)\) be the lattice of all finite dimensional subspaces of \(V(q)\). Then \(\mathbb{B}(q)\) is boolean with factorial function given by \[\mathbf{(n)!}=1 \cdot(1+q) \cdots (1+q+\cdots + q^{n-1}).\] By Theorem 32, \[\sum_{n=0}^\infty H_n(t) \frac{z^n}{\mathbf{(n)!}} = \frac{(1-t)e_q(z)}{e_q(tz)-te_q(z)},\] where \(e_q(z)= \sum_{n=0}^\infty z^n/\mathbf{(n)!}\) is the \(q\)-exponential function. For \(\sigma \in \mathfrak{S}_n\), let \(\textrm{maj}(\sigma)= \sum_{i\in \mathrm{D}(\sigma)} i\). From the work of Shareshian and Wachs [23] it follows that \[H_n(t) = \sum_{\sigma \in \mathfrak{S}_n} q^{\textrm{maj}(\sigma)-\textrm{exc}(\sigma)} t^{\textrm{exc}(\sigma)},\] the \(q\)-analog, \(A_n(q,t)\), of the Eulerian polynomial studied by Shareshian and Wachs in [23]. This was first proved by Hameister, Rao and Simpson [9].

Moreover, it follows similarly from Theorem 32 that the augmented Chow polynomials, \(G_n(t)\), of \(\mathbb{B}(q)\) are the \(q\)-binomial Eulerian polynomials \(\widetilde{A}_n(q,t)\) studied by Shareshian and Wachs in [43]. The truncated projective geometries \(\mathbb{B}_n^k(q)=\tau^k[\hat{0}, x]\), where \(x\) is an element of \(\mathbb{B}(q)\) of rank \(n+k\) are geometric lattices. Proposition 29 provides identities for the various Chow polynomials associated to \(\mathbb{B}_n^k(q)\). For example, \[\sum_{n \geq 0} H_{\mathbb{B}_n^k(q)}(t) \frac{z^n}{\mathbf{(n)!}} = 1+ \frac{\sum_{n \geq k}(1-t^k)\frac{z^k}{\mathbf{(n)!}}}{e_q(tz)-te_q(z)},\] which was first proved in [9] in an equivalent form. Since \(\mathbb{B}(q)\) is a \(\mathop{\mathrm{\mathrm{TN}}}\)-poset we know that the polynomials \(A_n(q,t)\), \(\widetilde{A}_n(q,t)\) and \(H_{\mathbb{B}_n^k(q)}(t)\), \(n,k \in \mathbb{N}\), are all real-rooted.

For \(\sigma \in \mathfrak{S}_n\), let \(\mathrm{inv}(\sigma)= |\{i<j : \sigma(i) >\sigma(j)\}\). The next result was first proved in [43].

Ehrenborg and Readdy generalized the notion of binomial posets in [22]. A poset \(P\) is called a Sheffer poset if there are two functions \(B : \mathbb{N}\to \mathbb{N}\) and \(C: \mathbb{N}\to \mathbb{N}\) such that

1. \(P\) is locally finite with a least element \(\hat{0}\), and \(P\) contains an infinite chain.

2. Each interval in \(P\) is graded, and hence \(P\) has a rank function \(\rho : P \to \mathbb{N}\).

3. The number of maximal chains in \([\hat{0}, x]\) is equal to \(C(\rho(x))\), for each \(x \in P\).

4. If \(\hat{0}< x \leq y\), then the number of maximal chains in \([x,y]\) is equal to \(B(\rho(x,y))\).

The functions \(B\) and \(C\) are called the factorial functions associated to \(P\). Hence Sheffer posets are rank uniform, and binomial posets are the Sheffer posets for which \(B=C\).

If \(P\) is a Sheffer poset, then \[r_{n,k}(P)= \frac{ C(n) }{C(k) \cdot B(n-k)}, \quad \quad 0<k \leq n,\] see [22].

The next corollaries follow from Theorem 33 and Example 5.

8.2 Symmetric and supersymmetric functions↩︎

When \[f(z) = \prod_{n = 0}^\infty (1+x_n z) = \sum_{n \geq 0} e_n(\mathbf{x})z^n \quador\quad f(z) = \prod_{n = 0}^\infty (1-x_n z)^{-1} = \sum_{n \geq 0} h_n(\mathbf{x})z^n,\] where \(e_n(\mathbf{x})\) and \(h_n(\mathbf{x})\) are the \(n\)th elementary symmetric and complete homogeneous polynomials, respectively, then a result due to Stanley, see [23], provides a combinatorial interpretation of the Chow polynomial \(H_n(t)\) for the matrices \((e_{i-j}(\mathbf{x}))_{i,j=0}^\infty\) and \((h_{i-j}(\mathbf{x}))_{i,j=0}^\infty\). Here we work over the integral domain \(\Lambda(\mathbf{x})\) of symmetric functions, see [45], [46]. The various Chow polynomials for these matrices have been extensively studied under different names in the literature. In particular, these polynomials play an important role in the celebrated work of Shareshian and Wachs on generalizations of Eulerian polynomials, see [23] and the references therein.

For \(R=(e_{i-j}(\mathbf{x}))_{i,j=0}^\infty\), Stanley proved \[H_n(t) = \sum_{w \in W_n} t^{\mathrm{des}(w)} \prod_{i=1}^n x_{w(i)},\] where \(W_n\) is the set of Smirnov words of length \(n\), i.e., words \(w : [n] \to \mathbb{N}\) for which \(w(i) \neq w(i+1)\) for each \(i\), and \(\mathrm{des}(w)= |\{ i \in [n-1] : w(i)>w(i+1)\}|\).

Let \(Q_n\) be the set of words \(w : [n] \to \mathbb{Z}\setminus \{0\}\) for which \[w(i)= w(i+1)\;\;\; implies\;\;\;w(i)<0.\] For \(w \in Q_n\), let \(\mathrm{col}(w)= |\{i : w(i)=w(i+1)\}|\) denote the number of collisions in \(w\). Motivated by Theorem 30, we extend Stanley’s result to give a combinatorial interpretation of the Chow polynomials of essentially any Pólya frequency sequence. In the following theorem we work over the integral domain \(\mathbb{Z}[[x_1,y_1,x_2,y_2,\ldots]]\).

Let \(\mu \subseteq \lambda\) be integer partitions. Then the supersymmetric skew Schur function, \(s_{\lambda/\mu}(\mathbf{x}/\mathbf{y})\), may be defined by the Jacobi-Trudi identity as \[s_{\lambda/\mu}(\mathbf{x}/\mathbf{y}) = \det\left( e_{\lambda'_i-\mu'_j-i+j}(\mathbf{x}/\mathbf{y}) \right)_{1\leq i,j\leq \ell(\lambda')},\] see [45] and [47]. These series have nonnegative integer coefficients. The series \(s_{\lambda}(\mathbf{x}/\mathbf{y}) = s_{\lambda/0}(\mathbf{x}/\mathbf{y})\) is called a supersymmetric Schur function. They form a basis for the integral domain \(\Lambda(\mathbf{x}/\mathbf{y})\) of supersymmetric functions, see [47]. We will now use Corollary 8 to give an alternative and unified proof of an unpublished result of Gessel, see [32], who proved the case of Theorem 35 for \(H_n\) and \(d_n\), and Shareshian and Wachs [43] who proved Theorem 35 for \(G_n\).

Let \(f(\mathbf{x}/\mathbf{y};t) \in \Lambda(\mathbf{x}/\mathbf{y})[t]\) be a palindromic polynomial in \(t\) with center of symmetry \(n/2\) and with coefficients in \(\Lambda(\mathbf{x}/\mathbf{y})\). Then we may write \[f(\mathbf{x}/\mathbf{y};t) = \sum_{k=0}^{\lfloor n/2 \rfloor} \gamma_k(\mathbf{x}/\mathbf{y}) t^k (1+t)^{n-2k}.\] We say that \(f(\mathbf{x}/\mathbf{y};t)\) is super Schur \(\gamma\)-positive if each \(\gamma_k(\mathbf{x}/\mathbf{y})\) has a nonnegative expansion in super Schur functions. Notice that \(f(\mathbf{x}/\mathbf{y};t) \in \Lambda(\mathbf{x}/\mathbf{y})\) is super Schur \(\gamma\)-positive if and only if \(f(\mathbf{x}/0;t)\) is Schur \(\gamma\)-positive if and only if \(f(0/\mathbf{y};t)\) is Schur \(\gamma\)-positive. This is because the maps from supersymmetric functions to symmetric functions defined by \[s_\lambda(\mathbf{x}/\mathbf{y}) \longmapsto s_\lambda(\mathbf{x}) \quadand\quad s_\lambda(\mathbf{x}/\mathbf{y}) \longmapsto s_{\lambda'}(\mathbf{y})\] are bijective. Theorem 35 says that the coefficients of the \(\gamma\)-Chow polynomials associated to \((e_{i-j}(\mathbf{x}/\mathbf{y}))_{i,j=0}^\infty\) are super Schur nonnegative.

References↩︎