f-VECTORS OF BARYCENTRIC SUBDIVISIONS

FRANCESCO BRENTI AND VOLKMAR WELKER

Abstract. For a simplicial complex or more generally Boolean cell complex Δ we study the behavior of the f- and h-vector under barycentric subdivision. We show that if Δ has a non-negative h-vector then the h-polynomial of its barycentric subdivision has only simple and real zeros. As a consequence this implies a strong version of the Charney-Davis conjecture for spheres that are the subdivision of a Boolean cell complex or the subdivision of the boundary complex of a simple polytope.

For a general (d − 1)-dimensional simplicial complex Δ the hpolynomial of its n-th iterated subdivision shows convergent behavior. More precisely, we show that among the zeros of this hpolynomial there is one converging to infinity and the other d − 1 converge to a set of d − 1 real numbers which only depends on d.

1. Introduction

This work is concerned with the effect of barycentric subdivision on the enumerative structure of a simplicial complex. More precisely, we study the behavior of the f- and h-vector of a simplicial complex, or more generally, Boolean cell complex, under barycentric subdivisions. In our main result we show that if the h-vector of a simplicial complex or Boolean cell complex is non-negative then the h-polynomial (i.e., the generating polynomial of the h-vector) of its barycentric subdivision has only real simple zeros. Moreover, if one applies barycentric subdivision iteratively then there is a limiting behavior of the zeros of the h-polynomial, with one zero going to infinity and the other zero converging. The limit values of the zeros only depend on the dimension of the complex.

In this introductory section we first review the basic concepts around f- and h-vectors and give the basic definitions, then we outline the structure of this work.

Key words and phrases. Barycentric subdivision, f-vector, real-rootedness, unimodality.

Both authors partially supported by EU Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272 and the program on “Algebraic Combinatorics” at the Mittag-Leffler Institut in Spring 2005.

Our results hold in the generality of Boolean cell complexes. Recall that if Δ is a CW-complex then for two open cells A and A′ in Δ we define A ≤_{Δ} A′ if A is contained in the closure of A′ in Δ. If Δ is a regular CW-complex then this partial order on its cells already encodes the topology of Δ up to homeomorphism. In this text we consider the empty cell as a cell of any CW-complex Δ which then serves as the least element of the partial order on Δ. Thus we can identify Δ with the partial order on its cells. In particular, we write A ∈ Δ if we want to express that A is a cell of Δ. We call a regular CWcomplex Δ a Boolean cell complex if for each A ∈ Δ the lower interval [∅, A] := {B ∈ Δ | ∅ ≤_{Δ} B ≤_{Δ} A} is a Boolean lattice – i.e. the lattice of subsets of a set. The prime example of a Boolean cell complex is a simplicial complex. Most of the time we consider a simplicial complex as an abstract simplicial complex and therefore identify its open cells with subsets of the ground set of Δ. Adopting notions from simplicial complexes, we call a cell A ∈ Δ a face of Δ. By dim(A) we denote the dimension of the cell A. The dimension dim(Δ) of Δ is the maximal dimension of one of its faces. For −1 ≤ i ≤ d − 1 (=^{def} dim(Δ)) we write f_{i}^{Δ} for the number of i-dimensional faces of Δ. The vector 𝔣^{Δ} = (f_{−1}^{Δ}, …, f_{d−1}^{Δ}) is called the f-vector of Δ. Often it will be convenient to encode the f-vector of a Boolean cell complex as a polynomial. By 𝔣^{Δ}(t) = ∑_{i=0}^{d} f_{i−1}^{Δ}t^{d−i} we denote the f-polynomial of the (d − 1)- dimensional Boolean cell complex Δ. Information equivalent to the one carried by the f-vector is encoded in the h-vector. It is defined as 𝔥^{Δ} = (h_{0}^{Δ}, …, h_{d}^{Δ}) where 𝔥^{Δ}(t) = ∑_{i=0}^{d} h_{i}^{Δ}t^{d−i} is the expansion of 𝔣^{Δ}(t − 1) in terms of t-powers.

The barycentric subdivision of a Boolean cell complex Δ is the simplicial complex sd(Δ), that as an abstract simplicial complex is defined on the ground set Δ \ {∅} – the set of non-empty faces of Δ – with i-faces the strictly increasing flags A_{0} <_{Δ} ⋯ <_{Δ} A_{i} of faces in Δ \ {∅}. It is well known that Δ and sd(Δ) are homeomorphic. Thus Δ and sd(Δ) define cellulations and triangulations of the same space.

Throughout the paper we will use [n] to denote the set {1, …, n} for a natural number n ≥ 0.

2. The h-Vector of a Barycentric Subdivision

For the sake of completeness we sketch the proof of the following well known result.

Lemma 2.1. Let Δ be a (d−1)-dimensional Boolean cell complex then

f_{j}^{sd(Δ)} = ∑_{i=0}^{d} f_{i−1}^{Δ} (j + 1)! S(i, j + 1),

where S(j, i) is the Stirling number of the second kind.

Proof. By definition a j-face of sd(Δ) is a flag A_{0} <_{Δ} ⋯ <_{Δ} A_{j} of faces in Δ \ {∅}. Let us fix j and A_{j}. Since Δ is a Boolean cell complex, the interval [∅, A_{j}] is the Boolean lattice of subsets of a (dim(A_{j}) + 1)- element set. Thus we may identify each of the cells A_{0}, …, A_{j} with a subset of this set. Using this identification, the map sending A_{0} <_{Δ} ⋯ <_{Δ} A_{j} to (A_{0}, A_{1} \ A_{0}, ⋯, A_{j} \ A_{j−1}) is a bijection between j-faces of sd(Δ) with A_{j} as its largest element with respect to ≤_{Δ} and ordered partitions of A_{j} into j+1 non-empty blocks. The latter are enumerated by (j + 1)!S(i, j + 1), where i = dim(A_{j}) + 1. Now summing over all A_{j} of fixed dimension i − 1 we get f_{i−1}^{Δ}(j + 1)!S(i, j + 1). Summing over all i then yields the desired formula. □

Less obvious is the representation of the h-vector of a barycentric subdivision in terms of the h-vector of the original complex. In the formulation of the proposition we write

D(σ) = {i ∈ [d − 1] : σ(i) > σ(i + 1)},

des(σ) = #D(σ) for the number of descents of the permutation σ, and S_{d} for the symmetric group on [d]. For 1 ≤ d, 1 ≤ j ≤ d and 0 ≤ i ≤ d − 1 , we denote by A(d, i, j) the number of permutations σ ∈ S_{d} such that σ(1) = j and des(σ) = i. We define A(d, i, j) for all d ≥ 1 and all integers i and j. In particular, A(d, i, j) = 0 if i ≤ −1 or i ≥ d. A formula similar to the one in the following theorem appears in a slightly different context in [12, Chapter 3, Ex. 71] and [11, Theorem 8.3]. We were not able to deduce the following result from these formulas directly.

Theorem 2.2. Let Δ be a (d − 1)-dimensional Boolean cell complex. Then

h_{j}^{sd(Δ)} = ∑_{r=0}^{d} A(d + 1, j, r + 1) h_{r}^{Δ}

for 0 ≤ j ≤ d.

4 FRANCESCO BRENTI AND VOLKMAR WELKER

Proof. For all 0 ≤ j ≤ d we have that

h_{j}^{sd(Δ)} = ∑_{i=0}^{j} (\begin{matrix}d−i \\ j−i \end{matrix}) (−1)^{j−i}f_{i−1}^{sd(Δ)}
= ∑_{i=0}^{j} (\begin{matrix}d−i \\ j−i \end{matrix}) (−1)^{j−i} ∑_{k=0}^{d} f_{k−1}^{Δ} S(k, i) i!
= ∑_{i=0}^{j} ∑_{k=0}^{d} (\begin{matrix}d−i \\ j−i \end{matrix}) (−1)^{j−i} S(k, i) i! ∑_{r=0}^{k} (\begin{matrix}d−r \\ d−k \end{matrix}) h_{r}^{Δ}
= ∑_{r=0}^{d} (∑_{k=0}^{d} ∑_{i=0}^{j}(−1)^{j−i} (\begin{matrix}d−i \\ j−i \end{matrix}) (\begin{matrix}d−r \\ d−k \end{matrix}) S(k, i) i!) h_{r}^{Δ}.

Now notice that if S = {s_{1}, …, s_{k}} ⊆ [d] and s_{1} < … < s_{k} then

#\{σ ∈ S_{d+1} : \begin{matrix}D(σ) ⊆ S, \\ σ(d + 1) = d + 1 − r \end{matrix} \} = (\begin{matrix}s_{k} \\ s_{k}−s_{k−1},...,s_{2}−s_{1},s_{1} \end{matrix}) (\begin{matrix}d−r \\ d−s_{k} \end{matrix} ) .

So,

∑_{\{S⊆[d], #S=k\}} #\{σ ∈ S_{d+1} : \begin{matrix}D(σ) ⊆ S, \\ σ(d + 1) = d + 1 − r \end{matrix} \}

= ∑_{1≤s_{1}<...<s_{k}≤d} (\begin{matrix}s_{k} \\ s_{k}−s_{k−1},...,s_{2}−s_{1},s_{1} \end{matrix}) (\begin{matrix}d−r \\ d−s_{k} \end{matrix} )
= ∑_{j=k}^{d} (\begin{matrix}d−r \\ d−j \end{matrix}) ∑_{1≤s_{1}<...<s_{k−1}≤j−1} (\begin{matrix}j \\ j−s_{k−1},...,s_{2}−s_{1},s_{1} \end{matrix}) = ∑_{j=k}^{d} (\begin{matrix}d−r \\ d−j \end{matrix}) S(j, k) k!

Therefore,

∑_{k=0}^{d} ∑_{i=0}^{j}(−1)^{j−i} (\begin{matrix}d−i \\ j−i \end{matrix}) (\begin{matrix}d−r \\ d−k \end{matrix}) S(k, i) i!

= ∑_{i=0}^{j}(−1)^{j−i} (\begin{matrix}d−i \\ j−i \end{matrix}) ∑_{\{S⊆[d], #S=i\}} #\{σ ∈ S_{d+1} : \begin{matrix}D(σ) ⊆ S, \\ σ(d + 1) = d + 1 − r \end{matrix} \}

= ∑_{\{S⊆[d], #S≤j\}}(−1)^{j−#S} (\begin{matrix}d−#S \\ j−#S \end{matrix}) #\{σ ∈ S_{d+1} : \begin{matrix}D(σ) ⊆ S, \\ σ(d + 1) = d + 1 − r \end{matrix} \}

= ∑_{\{S⊆[d], #S≤j\}}(−1)^{j−#S} (\begin{matrix}d−#S \\ j−#S \end{matrix}) ∑_{T ⊆S} #\{σ ∈ S_{d+1} : \begin{matrix}D(σ) = T, \\ σ(d + 1) = d + 1 − r \end{matrix} \}

= ∑_{\{T ⊆[d], #T ≤j\}} #\{σ ∈ S_{d+1} : \begin{matrix}D(σ) = T, \\ σ(d + 1) = d + 1 − r \end{matrix} \} ∑_{\{S⊇T, #S≤j\}}(−1)^{j−#S} (\begin{matrix}d−#S \\ j−#S \end{matrix})

= ∑_{\{T ⊆[d], #T ≤j\}} #\{σ ∈ S_{d+1} : \begin{matrix}D(σ) = T, \\ σ(d + 1) = d + 1 − r \end{matrix} \} ∑_{i=#T}^{j}(−1)^{j−i} (\begin{matrix}d−i \\ j−i \end{matrix}) (\begin{matrix}d−#T \\ i−#T \end{matrix} ) .

But

∑_{i=#T}^{j}(−1)^{j−i} (\begin{matrix}d−i \\ j−i \end{matrix}) (\begin{matrix}d−#T \\ i−#T \end{matrix} ) = (\begin{matrix}d−#T \\ j−#T \end{matrix} ) ∑_{i=#T}^{j}(−1)^{j−i} (\begin{matrix}j−#T \\ i−#T \end{matrix} )
= δ_{j,#T}

Hence

∑_{k=0}^{d} ∑_{i=0}^{j}(−1)^{j−i} (\begin{matrix}d−i \\ j−i \end{matrix}) (\begin{matrix}d−r \\ d−k \end{matrix}) S(k, i)i!

= ∑_{\{T ⊆[d], #T =j\}} #\{σ ∈ S_{d+1} : \begin{matrix}D(σ) = T, \\ σ(d + 1) = d + 1 − r \end{matrix} \}

= #\{σ ∈ S_{d+1} : \begin{matrix}des(σ) = j, \\ σ(d + 1) = d + 1 − r \end{matrix} \},

and the result follows. □

Corollary 2.3. Let Δ be a (d − 1)-dimensional Boolean cell complex such that h_{i}^{Δ} ≥ 0 for 1 ≤ i ≤ d. Then for 0 ≤ i ≤ d

h_{i}^{sd(Δ)} ≥ h_{i}^{Δ}.

Furthermore, (h_{0}^{sd(Δ)}, …, h_{d}^{sd(Δ)}) has no internal zeros.

Proof. We have from Theorem 2.2 and our hypotheses that h_{j}^{sd(Δ)} ≥ A(d + 1, j, j + 1) h_{j}^{Δ} so the result follows since A(d + 1, j, j + 1) ≥ 1 for all 0 ≤ j ≤ d. Furthermore, if h_{j}^{sd(Δ)} = 0 for some j < d then, since A(d + 1, j, r + 1) > 0 for all r = 0, …, d, we conclude from Theorem 2.2 that h_{0}^{Δ} = 0, which is a contradiction. □

Note that for any (d − 1)-dimensional Boolean cell complex Δ we have h_{0}^{Δ} = 1 and h_{d}^{Δ} = (−1)^{d}·χ̃(Δ) for the reduced Euler-characteristic χ̃(Δ) of Δ. In particular, h_{0}^{sd(Δ)} = 1 and by the topological invariance of the Euler-characteristic also h_{d}^{sd(Δ)} = h_{d}^{Δ}. Of course both identities are also implicit in Theorem 2.2.

Example 2.4. It is not true that h_{i}^{sd(Δ)} ≥ h_{i}^{Δ} for any Boolean cell complex Δ and any i. For example let Δ be the disjoint union of a 2simplex and a triangle with f-vector 𝔣^{Δ} = (1, 6, 6, 1) and h-vector 𝔥^{Δ} = (1, 3, −3, 0). Then 𝔣^{sd(Δ)} = (1, 13, 18, 6) and 𝔥^{sd(Δ)} = (1, 10, −5, 0).

Before we proceed with the next corollary we summarize some basic facts about the numbers A(d, i, j).

Lemma 2.5.

(i)

A(d, i, j) = ∑_{l=1}^{j−1} A(d − 1, i − 1, l) + ∑_{l=j+1}^{d}A(d − 1, i, l − 1),

for 2 ≤ d, 1 ≤ j ≤ d, and 0 ≤ i ≤ d − 1. (ii)

A(d, i, j) = A(d, d − 1 − i, d + 1 − j)

for 1 ≤ d, 1 ≤ j ≤ d and 0 ≤ i ≤ d − 1.

Proof. For (i) the recursion formula just reflects the enumeration of the permutations in S_{d} with σ(1) = j and des(σ) = i by l = σ(2). For (ii) the assertion reflects the fact that the map σ(1) ⋯ σ(d) ↔ d + 1 − σ(1) ⋯ d + 1 − σ(d) is a bijection between the sets enumerated by the two numbers. □

We call the h-vector 𝔥^{Δ} (resp. h-polynomial 𝔥^{Δ}(t)) of a Boolean cell complex Δ reciprocal if h_{i}^{Δ} = h_{d−i}^{Δ} for 0 ≤ i ≤ d (resp. 𝔥^{Δ}(t) = t^{d}𝔥^{Δ}(\frac{1}{t})). Clearly, 𝔥^{Δ} is reciprocal if and only if 𝔥^{Δ}(t) is. Either condition is equivalent to the h-vector satisfying the Dehn-Sommerville relations (see [1, Theorem 5.4.2]).

Corollary 2.6. Let Δ be a (d − 1)-dimensional Boolean cell complex with reciprocal h-vector then sd(Δ) also has reciprocal h-vector.

Proof. By Lemma 2.5 and Theorem 2.2 we get

h_{j}^{sd(Δ)} = ∑_{i=0}^{d} A(d + 1, j, i + 1)h_{i}^{Δ}.

= ∑_{i=0}^{d} A(d + 1, d − j, d − i + 1)h_{d−i}^{Δ}

= ∑_{i=0}^{d} A(d + 1, d − j, i + 1)h_{i}^{Δ}
= h_{d−j}^{sd(Δ)}

□

3. Main Result

For the formulation of the following result we recall that a sequence (a_{0}, …, a_{d}) of real numbers is called log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for 1 ≤ i ≤ d − 1. We say that (a_{0}, …, a_{d}) has internal zeros, if there are 0 ≤ i < j ≤ d such that a_{i}, a_{j} ≠ 0 and a_{i+1} = a_{i+2} = ⋯ = a_{j−1} = 0. It is a well known and easy to prove fact that if (a_{0}, …, a_{d}) is a logconcave sequence of non-negative real numbers and has no internal zeros then it is unimodal; that is there is a 0 ≤ j ≤ d such that a_{0} ≤ ⋯ ≤ a_{j} ≥ ⋯ ≥ a_{d}. By another well known fact (see, e.g., [, §7.1]) it follows that if the polynomial a_{0} + a_{1}t + ⋯ + a_{d}t^{d} has only real zeros then (a_{0}, …, a_{d}) is log-concave.

Theorem 3.1. Let Δ be a (d − 1)-dimensional Boolean cell complex such that h_{i}^{Δ} ≥ 0 for 0 ≤ i ≤ d. Then

𝔥^{sd(Δ)}(t) = ∑_{i=0}^{d} h_{i}^{sd(Δ)}t^{d−i}

has only simple and real zeros. In particular, 𝔥^{sd(Δ)} = (h_{0}^{sd(Δ)}, …, h_{d}^{sd(Δ)}) is a log-concave and unimodal sequence.

Before we can prove Theorem 3.1 we need a few definitions and a lemma about permutation statistics of Coxeter groups of types A_{d} and B_{d}. The Coxeter group of type A_{d} is the symmetric group S_{d+1} and we have defined the respective statistics already in Section 2. The Coxeter group of type B_{d} is the group of all bijections σ of {±1, …, ±d} in itself such that σ(−i) = −σ(i) for 1 ≤ i ≤ d. An element of B_{d} is called a signed permutation. For σ ∈ B_{d} one conveniently sets σ(0) := 0. Then i ∈ [0, d − 1] is a descent of σ ∈ B_{d} if σ(i) > σ(i + 1). In particular, 0 is a descent if and only if σ(1) < 0. By des_{B}(σ) we denote the number of descents of the signed permutation σ. By N(σ) we denote the number of i ∈ [d] such that σ(i) < 0. Let 𝔄(d + 1, i, j) be the set of pairs (S, σ) of (j − 1)-subsets S of [d] and σ ∈ S_{d+1} such that σ has i descents and σ(1) = j.

Lemma 3.2. Let d ≥ 1, j ∈ [d + 1] and 0 ≤ i ≤ d. There is a bijection between 𝔄(d + 1, i, j) and the set of signed permutations τ ∈ B_{d} with i descents and N(τ) = j − 1.

Proof. For (S, σ) ∈ 𝔄(d + 1, i, j) we define τ_{(S,σ)} ∈ B_{d} as follows. Let S = {s_{1} > … > s_{j−1}} and [d] \ S = {s_{j} < … < s_{d}}. Then define τ_{(S,σ)} ∈ B_{d} by

τ_{(S,σ)}(r) = \{ \begin{matrix}−s_{σ(r+1)} & if & σ(r + 1) < j \\ s_{σ(r+1)−1} & if & σ(r + 1) > j \end{matrix} ,

(and τ_{(S,σ)}(0) = 0).

We show that for 0 ≤ r ≤ d:

τ_{(S,σ)}(r) > τ_{(S,σ)}(r + 1) ⇔ σ(r + 1) > σ(r + 2). (3.1)

This is clear for r = 0, so assume 1 ≤ r ≤ d. Let us distinguish the four possible cases:

▷ σ(r + 1), σ(r + 2) < j. In this case τ_{(S,σ)}(r) > τ_{(S,σ)}(r + 1) ⇔ s_{σ(r+1)} < s_{σ(r+2)}, which is equivalent to σ(r + 1) > σ(r + 2). ▷ σ(r + 1), σ(r + 2) > j. In this case τ_{(S,σ)}(r) > τ_{(S,σ)}(r + 1) ⇔ s_{σ(r+1)−1} > s_{σ(r+2)−1}, which is equivalent to σ(r +1) > σ(r +2). ▷ σ(r+1) < j, σ(r+2) > j. In this case clearly σ(r+1) < σ(r+2)

and τ_{(S,σ)}(r) < 0 < τ_{(S,σ)}(r + 1).

▷ σ(r+1) > j, σ(r+2) < j. In this case clearly σ(r+1) > σ(r+2)

and τ_{(S,σ)}(r) > 0 > τ_{(S,σ)}(r + 1).

Thus des_{B}(τ_{(S,σ)}) = des(σ). Clearly N(τ_{(S,σ)}) = j − 1. One easily checks that the map (S, σ) ↦ τ_{(S,σ)} is injective and surjective from 𝔄(d + 1, i, j) to the set of signed permutations in B_{d} with i descents and N(τ) = j − 1. □

Proof of Theorem 3.1. By Theorem 2.2 the following identity holds.

(3.2)  \frac{∑_{i=0}^{d}h_{i}^{sd(Δ)}t^{i}}{(1 − t)^{d+1}} = ∑_{j=0}^{d}h_{j}^{Δ} · \frac{∑_{i=0}^{d}A(d + 1, i, j + 1)t^{i}}{(1 − t)^{d+1}}

If B(d, i, j) is the number of signed permutations in B_{d} such that des_{B}(σ) = i and N(σ) = j then it follows from [3, Corollary 3.9, eq.(25)] that:

(3.3)  \frac{∑_{i=0}^{d}B(d, i, j)t^{i}}{(1 − t)^{d+1}} = ∑_{r≥0} \binom{d}{j}r^{j}(r + 1)^{d−j}t^{r}

Using Lemma 3.2 it follows from (3.3) that

(3.4)  \frac{∑_{i=0}^{d}A(d + 1, i, j + 1)t^{i}}{(1 − t)^{d+1}} = ∑_{r≥0} r^{j}(r + 1)^{d−j}t^{r}.

Therefore, by (3.2)

(3.5)  \frac{∑_{i=0}^{d}h_{i}^{sd(Δ)}t^{i}}{(1 − t)^{d+1}} = ∑_{r≥0}(∑_{j=0}^{d}h_{j}^{Δ}r^{j}(r + 1)^{d−j}) t^{r}.

By [4, Theorem 4.2] it follows that if we write

∑_{j=0}^{d} h_{j}^{Δ}r^{j}(r + 1)^{d−j} = ∑_{j=0}^{d} k_{j}^{Δ}\binom{r}{j} (3.6)

then the polynomial ∑_{j=0}^{d} k_{j}^{Δ}r^{j} has non-negative coefficients and only

simple and real zeros. Using the Binomial Theorem we obtain, by (3.5) and (3.6)

\frac{∑_{i=0}^{d}h_{i}^{sd(Δ)}t^{i}}{(1 − t)^{d+1}} = ∑_{r≥0}(∑_{j=0}^{d}k_{j}^{Δ}\binom{r}{j}) t^{r}

= ∑_{j=0}^{d}k_{j}^{Δ} ∑_{r≥0} \binom{r}{j} t^{r}

= ∑_{j=0}^{d}k_{j}^{Δ} \frac{t^{j}}{(1 − t)^{j+1}}

= \frac{∑_{j=0}^{d} k_{j}^{Δ}t^{j}(1 − t)^{d−j}}{(1 − t)^{d+1}} .

This finishes the proof of the main assertion.

Since polynomials with only real zeros have a log-concave coefficient sequence and since by Corollary 2.3 𝔥^{sd(Δ)} is non-negative and has no internal zeros the unimodality of 𝔥^{sd(Δ)} follows. □

Remark 3.3. Let (h_{0}, …, h_{d}) ∈ ℝ^{d+1} such that h_{i} ≥ 0 for 0 ≤ i ≤ d.

If we set h′_{j} = ∑_{i=0}^{d}A(d + 1, j, i + 1)h_{i} for 0 ≤ j ≤ d then the polynomial

h′_{d} + h′_{d−1}t + ⋯ h′_{0}t^{d} has only real and simple zeros.

Proof. The proof of Theorem 3.1 never uses the fact that h_{i}^{Δ} is the h-vector of a Boolean cell complex. The proof only relies on h_{i}^{Δ} ≥ 0 and the formula transforming h_{i}^{Δ} into h_{i}^{sd(Δ)}. Therefore, the remark follows from the proof of Theorem 3.1. □

Note that since sd(Δ) is a flag simplicial complex, that is, all minimal non-faces are of size 2, it is known that 𝔥^{sd(Δ)}(t) has at least one real zero. This fact for flag simplicial complexes appears in [10] or [6]. As mentioned in [10] this is actually a well known fact in commutative algebra, where it appears as a theorem saying that the numerator polynomial of the Hilbert-series of a standard graded Koszul k-algebra has at least one real zero. The following example shows that the assumptions of the theorem are actually needed.

Example 3.4. Let Δ be the disjoint union of a 2-simplex and a 1simplex. Then 𝔥^{Δ} = (1, 2, −3, 1) and 𝔥^{sd(Δ)} = (1, 7, −3, 1) so 𝔥^{sd(Δ)}(t) has only one real zero.

Corollary 3.5. Let Δ be a (d−1)-dimensional simplicial complex that is Cohen-Macaulay over some field k. Then

𝔥^{sd(Δ)}(t) = ∑_{i=0}^{d} h_{i}^{sd(Δ)}t^{d−i}

has only simple and real zeros. In particular, 𝔥^{sd(Δ)} = (h_{0}^{sd(Δ)}, …, h_{d}^{sd(Δ)}) is a log-concave and unimodal sequence. In particular, all conclusions hold for Gorenstein, Gorenstein^{∗} simplicial complexes, for simplicial spheres and boundary complexes of simplicial polytopes.

Proof. All mentioned simplicial complex are Cohen-Macaulay over some field k. Therefore, it suffices to recall that Cohen-Macaulay simplicial complexes have a non-negative h-vector without internal zeros. This well known fact follows since if Δ is Cohen-Macaulay the sequence (h_{0}^{Δ}, …, h_{d}^{Δ}) is the Hilbert-function h_{i}^{Δ} = dim_{k} A_{i} of a 0-dimensional standard graded k-algebra A = A_{0} ⊕ ⋯ ⊕ A_{d} (see [1, Chapter 5] for details). Being the dimension of a k-vector space clearly implies that h_{i}^{Δ} ≥ 0. Now the fact that a standard graded k-algebra is generated in degree 1 implies that there cannot be internal zeros in the sequence (h_{0}^{Δ}, …, h_{d}^{Δ}). □

The preceding corollary assures that there is an abundance of interesting simplicial complexes satisfying the assumption of Theorem 3.1.

As another corollary we can treat barycentric subdivisions of simple polytopes. Here we leave the setting of Boolean cell complexes. Note, that for a (general) polytope P the barycentric subdivision sd(Δ) of its boundary complex Δ is the simplicial complex of all linearly ordered subsets of the proper part of its face lattice L(P). We refer to Ziegler’s book [14] for the definition of a simple polytopes, its f-vector, polytope duality, and the face lattice L(P) of a polytope P.

Corollary 3.6. Let Δ be the boundary complex of a simple d-polytope. Then

𝔥^{sd(Δ)}(t) = ∑_{i=0}^{d} h_{i}^{sd(Δ)}t^{d−i}

has only simple and real zeros. In particular, 𝔥^{sd(Δ)} = (h_{0}^{sd(Δ)}, …, h_{d}^{sd(Δ)}) is a log-concave and unimodal sequence.

Proof. Let Δ be the boundary complex of the simple polytope P. Since P is a simple polytope it is the dual of a simplicial polytope Q. The face lattices L(P) of P and L(Q) of Q are order dual; that is they are isomorphic with the order relation reversed. In particular, there is a bijection between the (i + 1) element chains in the proper parts of L(P) and L(Q). In particular, if Δ_{Q} is the boundary complex of Q, then sd(Δ) and sd(Δ_{Q}) are isomorphic simplicial complexes. Thus f^{sd(Δ)}(t) = f^{sd(Δ_{Q})}(t). Now the assertion follows from Corollary 3.5.

□

At this point we would like to add examples that show that the additional generality of Boolean cell complexes enriches the class of complexes for which the theorem holds by interesting examples.

Example 3.7. An injective word over the alphabet [n] is a word i_{1} ⋯ i_{j} for which i_{r} ≠ i_{s} for all 1 ≤ r < s ≤ j. We call {i_{1}, …, i_{j}} the content of the injective word i_{1} ⋯ i_{j}. We order injective words by saying i′_{1} ⋯ i′_{l} ⪯ i_{i} … i_{j} if there is a sequence of indices 1 ≤ s_{1} < ⋯ < s_{l} ≤ j such that i′_{1} ⋯ i′_{l} = i_{s_{1}} ⋯ i_{s_{l}}. For a simplicial complex Δ over ground set [n] we denote by Γ(Δ) the partially ordered set of all injective words with content in Δ. It is easily seen that Γ(Δ) is the face poset of a Boolean cell complex. In [8], where the complexes Γ(Δ) are defined, it is shown that all Γ(Δ) have non-negative h-vector, thus providing a big class of Boolean cell complexes satisfying the assumptions of Theorem 3.1. It should be mentioned that if Δ is the full simplex then the Boolean cell complex Γ(Δ) is a well studied object (see the references in [8]).

At this point we are in position to relate our results to the Charney-Davis conjecture [5]. The original conjecture states that if Δ is a flag (d − 1)-dimensional Gorenstein^{∗} simplicial complex and d is even then (−1)^{⌊ \frac{d}{2} ⌋}(h_{0}^{Δ} −h_{1}^{Δ} +⋯+(−1)^{d}h_{d}^{Δ}) ≥ 0. Alternatively, the assertion can be phrased as (−1)^{⌊ \frac{d}{2} ⌋}𝔥^{Δ}(−1) ≥ 0. Since d odd implies for Gorenstein^{∗} simplicial complexes by h_{i}^{Δ} = h_{d−i}^{Δ} that 𝔥^{Δ}(−1) = 0 we will drop the assumption d even and say that a simplicial complex Δ with reciprocal h-vector satisfies the Charney-Davis Conjecture if (−1)^{⌊ \frac{d}{2} ⌋}𝔥^{Δ}(−1) ≥ 0. The latter number is also called Charney-Davis quantity of Δ. Barycentric subdivisions already appear in one of the first instances where the Charney-Davis conjecture was verified. Stanley [13] shows that if Δ is the barycentric subdivision of the boundary complex of a (not necessarily simplicial) polytope then the Charney-Davis conjecture holds for Δ. More recently, the work of Karu [9] implies the conjecture for order complexes of Gorenstein^{∗} posets. As a corollary of Theorem 3.5 we obtain the following result which strengthens Karu’s results in the case of subdivisions of Boolean cell complexes whose face poset is Gorenstein^{∗} and subdivisions of boundary complexes of simple polytopes.

Corollary 3.8. The Charney-Davis conjecture holds for:

(i) Subdivisions of (d − 1)-dimensional Boolean cell complexes Δ for which h_{i}^{Δ} ≥ 0 and h_{i}^{Δ} = h_{d−i}^{Δ} for 0 ≤ i ≤ d.

(ii) Subdivisions of boundary complexes of simple d-polytopes.

If d is even then the assumptions imply that the Charney-Davis quantity of sd(Δ) is strictly positive.

Proof. The case (ii) follows from (i) by the arguments used in the proof of Corollary 3.6. Therefore we can restrict our attention to (i).

First let us verify the Charney-Davis conjecture for sd(Δ) for (i). By Corollary 2.6 the assumptions imply that sd(Δ) has a reciprocal h-polynomial 𝔥^{sd(Δ)}(t). By Theorem 3.1 we also know that 𝔥^{sd(Δ)} has only real zeros. Since the coefficients of 𝔥^{sd(Δ)}(t) are non-negative and h_{0}^{sd(Δ)} = 1 it follows that the zeros of 𝔥^{sd(Δ)}(t) are all strictly negative. Being a reciprocal polynomial with non-zero constant coefficient also implies that if α is a zero then \frac{1}{α} is a zero. Thus the zeros are either −1 or come in pairs α < −1 < \frac{1}{α} < 0. If −1 is a zero then the assertion follows immediately. If −1 is not a zero then d must be even and the \frac{d}{2} factors (−1 − α)(−1 − \frac{−1}{α}) of 𝔥^{sd(Δ)}(−1) have all negative sign. Thus 𝔥^{sd(Δ)}(−1) has sign (−1)^{\frac{d}{2}} , which implies Charney-Davis.

Let again d be even. Since there is an even number of zeros of 𝔥^{sd(Δ)}(t) which by Theorem 3.1 are simple and real it follows that −1 can only be a simple zero. But since all zeros come in pairs α, \frac{1}{α} this is impossible. Thus 𝔥^{sd(Δ)}(−1) ≠ 0 and it follows from the first part of the proof that the Charney-Davis quantity is strictly positive.

□

Note that the arguments showing that a monic real reciprocal hpolynomial with only real zeros and non-negative coefficients satisfies the Charney-Davis conjecture can also be found in [10].

Remark 3.9. It had been asked in [5] whether for flag Gorenstein^{∗} simplicial complexes Δ the h-polynomial 𝔥^{Δ}(t) has only real zeros. This conjecture has been shown to fail by Gal [6] for dim Δ ≥ 5 even for the class of flag boundary complexes of simplicial polytopes. For d ≤ 4 an even more general assertion is true. Namely, in [10, Corollary 4.14] it is shown that if A is a finitely generated Koszul Gorenstein k-algebra such that the numerator 𝔥^{A}(t) of its Hilbert-series Hilb(A, t) = \frac{𝔥^{A}(t)}{(1−t)^{d}} has degree ≤ 3 then 𝔥^{A}(t) has only real zeros.

Question 3.10. Is the conclusion of Theorem 3.1 true for barycentric subdivisions sd(Δ) of boundary complexes Δ of (not necessarily simplicial or simple) polytopes whose toric h-vector (or usual h-vector) is non-negative ?

In the remaining section we study the effect of barycentric subdivision on the Stanley-Reisner ring of a simplicial complex. Recall, that for a simplicial complex Δ on ground set Ω the Stanley-Reisner ideal I_{Δ} is the ideal generated within S = k[x_{ω} | ω ∈ Ω] by \underline{x}_{A} = ∏_{ω∈A} x_{ω} for A ∉ Δ. In particular, I_{Δ} is minimally generated by \underline{x}_{A} for A a minimal non-face of Δ. By k[Δ] we denote the quotient S/I_{Δ}. Since I_{Δ} is a homogeneous ideal, the quotient k[Δ] is a standard graded kalgebra k[Δ] ≅ ⨁_{i≥0} A_{i}^{Δ}. By Hilb(k[Δ], t) = ∑_{i≥0} dim_{k} A_{i}^{Δ} we denote the Hilbert-series of k[Δ]. In the process of passing from Δ to sd(Δ) the ring theoretic properties change as follows:

▷ The Krull dimensions dim(k[Δ]) and dim(k[sd(Δ)]) coincide. ▷ The Hilbert-series of k[Δ] and k[sd(Δ)] are given as:

Hilb(k[Δ], t) = \frac{h_{0}^{Δ} + ⋯ + h_{d}t^{t}}{(1 − t)^{d}}

and

Hilb(k[sd(Δ)], t) = \frac{h_{0}^{sd(Δ)} + ⋯ + h_{d}^{sd(Δ)}t^{d}}{(1 − t)^{d}} .

▷ k[sd(Δ)] is Koszul.

Question 3.11. Is there a version of the main result for graded rings ? What is the “barycentric subdivision” of a standard graded k-algebra ? For that we have in mind an operator sd(·) that transforms a standard graded algebra A into a standard graded algebra sd(A) such that:

• sd(k[Δ]) = k[sd(Δ)] for simplicial complexes Δ.

• dim(A) = dim(sd(A)).

• The numerator polynomials of the Hilbert-series of A and sd(A) transform ”similarly” as the ones of k[Δ] and k[sd(Δ)].

• sd(A) is Koszul.

4. Limiting Behavior

For a number n ≥ 1 and a Boolean cell complex Δ we denote by sd^{n}(Δ) the result of an n-fold application of the subdivision operator sd to Δ. If we fix a geometric realization |Δ| of Δ in some real vector space then one may regard the geometric realizations | sd^{n}(Δ)| of the complexes sd^{n}(Δ) as triangulations of the same space with simplices of volume converging to 0.

Example 4.1. If dim(Δ) = 0 then sd(Δ) = Δ which clearly implies that the h-vector remains invariant under barycentric subdivision.

If dim(Δ) > 0 then still h_{0}^{sd^{n}(Δ)} = h_{0}^{Δ} = 1 and h_{d}^{sd^{n}(Δ)} = h_{d}^{Δ}. But experimentally one observes that all the other coefficients of 𝔥^{sd^{n}(Δ)}(t) grow rapidly in absolute value. The following result shows that this growth is reflected in the behavior of a single root of 𝔥^{sd^{n}(Δ)}(t). Moreover, all other roots converge to real numbers, which only depend on the dimension of the simplicial complex.

Theorem 4.2. For a number d ≥ 1 there are real negative numbers α_{1}, …, α_{d−2} such that for every Boolean cell complex Δ of dimension d − 1 there are sequences (β_{i}^{(n)})_{n≥1}, 1 ≤ i ≤ d of complex numbers such that

(i) β_{i}^{n}, 1 ≤ i ≤ d, are real for n sufficiently large.

(ii) lim_{n→∞}β_{i}^{(n)} = α_{i} for 1 ≤ i ≤ d − 2.

(iii) lim_{n→∞}β_{d−1}^{(n)} = 0.

(iv) lim_{n→∞}β_{d}^{(n)} = −∞.

(v) For n ≥ 1

∏_{i=1}^{d}(t − β_{i}^{(n)}) = 𝔥^{sd^{n}(Δ)}(t).

Before we can come to a proof of Theorem 4.2 we need to analyze the transformation from 𝔥^{Δ} to 𝔥^{sd(Δ)} more closely. As a byproduct we will prove the following proposition.

Proposition 4.3. Let Δ be a (d−1)-dimensional Boolean cell complex. Then there is a number N(Δ) such that for n ≥ N(Δ) we have

h_{i}^{sd^{n}(Δ)} > 0

for 1 ≤ i ≤ d − 1. In particular, any (d − 1)-dimensional triangulable topological space X has a triangulation Δ such that

h_{i}^{Δ} > 0

for 1 ≤ i ≤ d − 1.

First we set up the matrices of the transformations that send f- and h-vectors of simplicial complexes to those of their barycentric subdivision. Let 𝔉_{d−1} = (f_{ij}^{d−1})_{0≤i,j≤d} be the matrix with entries f_{ij}^{d−1} := (i + 1)!S(j, i + 1). Let ℌ_{d−1} = (h_{ij}^{d−1})_{0≤i,j≤d} be the matrix with entries h_{ij}^{d−1} := A(d + 1, i, j + 1). Now Lemma 2.1 and Theorem 2.2 can be rephrased as follows:

𝔣^{sd(Δ)} = 𝔉_{d−1}𝔣^{Δ},
𝔥^{sd(Δ)} = ℌ_{d−1}𝔥^{Δ}.

In the sequel we summarize some simple results on the matrices ℌ_{d−1} and 𝔉_{d−1} that will be used in the proof of the main theorem of this section.

Lemma 4.4. Let d ≥ 1. Then:

(i) The matrices 𝔉_{d−1} and ℌ_{d−1} are similar.

(ii) The matrices 𝔉_{d−1} and ℌ_{d−1} are diagonizable with eigenvalue 1 of multiplicity 2 and eigenvalues 2!, 3!, …, d! of multiplicities 1. In particular, there is a basis of rational eigenvectors.

Proof. Since the transformation from 𝔣^{Δ} to 𝔥^{Δ} is an invertible linear transformation the matrices 𝔉_{d−1} and ℌ_{d−1} are similar by Lemma 2.1 and Theorem 2.2. For the second assertion consider 𝔉_{d−1}. Clearly, 𝔉_{d−1} is an upper triangular matrix with diagonal 1, 1, 2!, 3!, …, d!. Thus it remains to be shown that the eigenspace for eigenvalue 1 is of dimension 2. But this follows since the first and the second unit vectors are eigenvectors for the eigenvalue 1. □

The following lemmas give the crucial information on the eigenvectors of ℌ_{d−1}.

Lemma 4.5. Let d ≥ 2 and v_{1}^{1}(d), v_{1}^{2}(d), v_{2}(d), …, v_{d}(d) be a basis of ℝ^{d} consisting of eigenvectors of the matrix 𝔉_{d−1}, where v_{1}^{1}(d), v_{1}^{2}(d) are eigenvectors for the eigenvalue 1 and v_{i}(d) is an eigenvector for the eigenvalue i!, 2 ≤ i ≤ d. Then the vectors v_{1}^{1}(d + 1) := (v_{1}^{1}(d), 0), v_{1}^{2}(d + 1) := (v_{1}^{2}(d), 0) and v_{i}(d + 1) := (v_{i}(d), 0) are eigenvectors of 𝔉_{d} for the eigenvalues 1, 1, 2!, …, d!.

Proof. The assertion follows from the fact that 𝔉_{d−1} and 𝔉_{d} are upper triangular and that if one deletes the (d + 1)-st column and row from 𝔉_{d} then one obtains 𝔉_{d−1}. □

Lemma 4.6. Let d ≥ 2 and let w_{1}^{1}, w_{1}^{2}, w_{2}, w_{3}, …, w_{d} be a basis of eigenvectors of the matrix ℌ_{d−1}, where w_{1}^{1}, w_{1}^{2} are eigenvectors for the eigenvalue 1 and w_{i} is an eigenvector for the eigenvalue i!, 2 ≤ i ≤ d.

(i) Let Δ be a (d − 1)-dimensional Boolean cell complex. If we expand 𝔥^{Δ} = a_{1}^{1}w_{1}^{1}+a_{1}^{2}w_{1}^{2}+∑_{i=2}^{d} a_{i}w_{i} in terms of the eigenvectors, then a_{d} ≠ 0.

(ii) The first and the last coordinate entry in w_{2}, …, w_{d} is zero.

(iii) The vectors w_{1}^{1} and w_{1}^{2} can be chosen such that

w_{1}^{1} = (1, i_{1}, …, i_{d−1}, 0) and w_{1}^{2} = (0, j_{1}, …, j_{d−1}, 1).

(iv) The vector w_{d} can be chosen such that w_{d} = (0, b_{1}, …, b_{d−1}, 0) for strictly positive rational numbers b_{i}, 1 ≤ i ≤ d − 1.

Proof. (i) From Lemma 4.5 we deduce that if one expands the fvector of Δ in terms of a basis of eigenvectors of 𝔉_{d−1} then by f_{d−1}^{Δ} ≠ 0 the coefficient of the eigenvector for the eigenvalue d! is non-zero. Since 𝔉_{d−1} and ℌ_{d−1} are similar the assertion follows.

(ii) From the definition of ℌ_{d−1} it is clear that the first row is the first unit vector and the last row the (d + 1)-st unit vector. Thus if we denote by ℌ′_{d−1} the matrix which results from ℌ_{d−1} by deleting the first and (d + 1)-st rows and columns, then the characteristic polynomial of ℌ_{d−1} splits into (1 − t)^{2} times the characteristic polynomial of ℌ′_{d−1}. In particular, ℌ′_{d−1} has eigenvalues 2!, …, d! and therefore is diagonizable. Let w′_{2}, …, w′_{d} be eigenvectors of ℌ′_{d−1} for the eigenvalues 2!, …, d!. Again by the fact that the first and last row of ℌ_{d−1} are the first and the (d + 1)-st unit vector it follows that (0, w′_{2}, 0), …, (0, w′_{d}, 0) are eigenvectors of ℌ_{d−1} for the eigenvalues 2!, …, d!. Since all eigenspaces are of dimension 1 the assertion follows.

(iii) Follows immediately from (ii). (iv) Let ℌ′_{d−1} be as in the proof of (ii). The entries of ℌ′_{d−1} are

A(d + 1, j, i) for 1 ≤ j ≤ d − 1 and 2 ≤ i ≤ d. It is easily seen that these numbers are strictly positive. Therefore, by the Perron-Frobenius Theorem [7, Theorem 8.2.11] it follows that there is an eigenvector w′_{d} for the eigenvalue d! with strictly positive entries. Now the assertion follows by (ii).

□

Now we can prove Proposition 4.3.

Proof of Proposition 4.3. For d − 1 = 0 there is nothing to prove. Assume d ≥ 2 and let w_{1}^{1}, w_{1}^{2}, w_{2}, w_{3}, …, w_{d} be a basis of eigenvectors of the matrix ℌ_{d−1}, where w_{1}^{1}, w_{1}^{2} are eigenvectors for the eigenvalue 1 and w_{i} is an eigenvector for the eigenvalue i!, 2 ≤ i ≤ d.

By Lemma 4.6 (iv) we may assume that w_{d} = (0, b_{1}, ….b_{d−1}, 0) for strictly positive b_{i}, 1 ≤ i ≤ d − 1. Let

𝔥^{Δ} = a_{1}^{1}w_{1}^{1} + a_{1}^{2}w_{1}^{2} + a_{2}w_{2} + ⋯ + a_{d}w_{d}

be the expansion of 𝔥^{Δ} as a linear combination of eigenvectors of ℌ_{d−1}. By Lemma 4.6 we have a_{d} ≠ 0. Clearly, for n ≥ 1,

𝔥^{sd^{n}(Δ)} = a_{1}^{1}w_{1}^{1} + a_{1}^{2}w_{1}^{2} + 2^{n}a_{2}w_{2} + ⋯ + (d!)^{n}a_{d}w_{d}.

Hence

lim_{n→∞} \frac{𝔥^{sd^{n}(Δ)}}{d!^{n}} = a_{d}w_{d}.

In particular, for sufficiently large n the signs of a_{d}b_{i} and h_{i}^{sd^{n}(Δ)}, 1 ≤ i ≤ d − 1, all coincide. Since for any (d − 1)-dimensional Boolean cell complex the h_{1}-entry in its h-vector equals the number of vertices minus d, it follows that

h_{1}^{sd^{n}(Δ)} = f_{0}^{sd^{n}(Δ)} − d.

Thus from lim_{n→∞} f_{0}^{sd^{n}(Δ)} = +∞ we can deduce that h_{1}^{sd^{n}(Δ)} is strictly positive for sufficiently large n. From this we deduce that a_{d}b_{1} must be strictly positive and therefore also a_{d}. But then h_{i}^{sd^{n}(Δ)},1 ≤ i ≤ d − 1, is strictly positive for sufficiently large n.

Now let X be a (D − 1)-dimensional triangulable topological space and Δ triangulation of X. It is well known that Δ and sd(Δ) are homeomorphic. It follows from the first part that for sufficiently large n the simplicial complex sd^{n}(Δ) is a triangulation of X such that h_{i}^{sd^{n}(Δ)} > 0, 1 ≤ i ≤ d − 1. □

We mention a fact derived in the proof of Proposition 4.3 that will become important later.

Remark 4.7. The vector w_{d} and its coefficient a_{d} from Lemma 4.6 (i) can be chosen to be simultaneously non-negative.

Lemma 4.8. Let w_{d} = (0, b_{1}, …, b_{d−1}, 0) be an eigenvector of ℌ_{d−1} for the eigenvalue d! such that b_{i} > 0 for all 1 ≤ i ≤ d − 1. Then the polynomial b_{d−1}t + ⋯ b_{1}t^{d−1} has only real and simple zeroes.

Proof. The vector w_{d} satisfies the assumptions of Remark 3.3. Therefore, for (h_{0}, …, h_{d}) = ℌ_{d−1}w_{d} it follows that h_{d} + h_{d−1}t + ⋯ + h_{0}t^{d} has only real and simple zeros. Since w_{d} is an eigenvector of ℌ_{d−1} for the eigenvalue d! it follows that h_{0} = h_{d} = 0 and h_{i} = d!b_{i}. Thus, d!(b_{d−1}t + ⋯ + b_{1}t^{d−1}) = h_{d} + h_{d−1}t + ⋯ + h_{0}t^{d} and b_{d−1}t + ⋯ b_{1}t^{d−1} has only real and simple zeros. □

We now formulate a technical lemma on the behavior of sequences of polynomials and its zeros which will serve as the key ingredient in the proof of Theorem 4.2.

Lemma 4.9. Let (g_{n}(t))_{n≥0} be a sequences of real polynomials of degree d − 2, f(t) another real polynomial of degree d − 2 and ρ > 1, h_{d} real numbers such that:

▷ lim_{n→∞} g_{n}(t)/ρ^{n} = 0, where the limit is taken in R^{d−1}.

▷ All the roots of the polynomial f(t) are strictly negative and all

coefficients of f(t) are strictly positive. Then there are real numbers α_{i}, 1 ≤ i ≤ d − 2 and sequences (β_{i}^{n})_{n≥0}, 1 ≤ i ≤ d of complex numbers such that:

(i) β_{i}^{n}, 1 ≤ i ≤ d, are real for n sufficiently large.

(ii) lim_{n→∞} β_{i}^{n} = α_{i}, 1 ≤ i ≤ d − 2.

(iii) lim_{n→∞} β_{d−1}^{n} = 0.

(iv) lim_{n→∞} β_{d}^{n} = −∞.

(v) ∏_{i=0}^{d−1}(t − β_{i}^{n}) = h_{d} + tg_{n}(t) + ρ^{n}tf(t) + t^{d}.

Proof. Let −∞ < γ_{1} < ⋯ < γ_{d−2} < 0 be the roots of f(t). Consider a zero γ_{i} of the polynomial f(t). Since γ_{i} is a simple zero of f_{n}(t) there is an ϵ > 0 such that either (A) f(x) > 0 if x ∈ (γ_{i} − ϵ, γ_{i}) and f(x) < 0 if x ∈ (γ_{i}, γ_{i} + ϵ) or (B) f(x) < 0 if x ∈ (γ_{i} − ϵ, γ_{i}) and f(x) > 0 if x ∈ (γ_{i}, γ_{i} + ϵ). Without loss of generality we may assume (A). Set

R_{n}^{−} = min_{x∈[γ_{i}−ϵ,γ_{i}]}(h_{d} + tg_{n}(t) + ρ^{n}tf(t) + t^{d})

R_{n}^{+} = max_{x∈[γ_{i},γ_{i}+ϵ]}(h_{d} + tg_{n}(t) + ρ^{n}tf(t) + t^{d})

By assumption lim_{n→∞} g_{n}(t)/ρ^{n} = 0 and hence

(4.1)  lim_{n→∞} 1/ρ^{n} · (h_{d} + tg_{n}(t) + t^{d}) = 0

Set M_{n} := max_{t∈[γ_{i}−ϵ,γ_{i}+ϵ]}1/ρ^{n} · |h_{d} + tg_{n}(t) + t^{d}|. From (4.1) it follows

that lim_{n→∞} M_{n} = 0. Thus for any δ > 0 there is an N(δ) such that

|M_{n}| < δ for n > N(δ). Set δ^{−} := −\frac{1}{2} min_{t∈[γ_{i}−ϵ,γ_{i}]}tf(t) and t∗− ∈ [γ_{i}−ϵ, γ_{i}]

such that δ^{−} = \frac{1}{2}t^{−}f(t^{−}). By assumption δ^{−} > 0. Then for n > N(δ^{−})

R_{n}^{−} ≤ h_{d} + t^{−}g(t^{−}) + (t^{−})^{d} + ρ^{n}t^{−}f(t^{−})
. ≤ ρ^{n}M_{n} − 2ρ^{n}δ^{−}
< ρ^{n}δ^{−} − 2ρ^{n}δ^{=} − ρ^{n}δ^{−} ≤ −δ^{−} < 0

If we set δ^{+} := \frac{1}{2} max_{t∈[γ_{i},γ_{i}+ϵ]}tf(t) then analogous arguments show R_{n}^{+} >

δ^{+} > 0 for n > N(δ^{+}). In particular, for all n > N(δ^{−}), N(δ^{+}) there is is a zero of h_{d} + tg_{n}(t) + ρ^{n}tf(t) + t^{d} in the interval [γ_{i} − ϵ, γ_{i} + ϵ]. If we choose ϵ < 1/4 min_{1≤i≤d−3}(γ_{i+1} − γ_{i}) then the intervals [γ_{i} − ϵ, γ_{i} + ϵ] are disjoint and hence the zeros distinct. In this situation we denote by β_{i}^{n} the zero of h_{d} + tg_{n}(t) + ρ^{n}tf(t) + t^{d} in the interval [γ_{i} − ϵ, γ_{i} + ϵ]. Our arguments show that at β_{i}^{n} the polynomial h_{d} + tg_{n}(t) + ρ^{n}tf(t) + t^{d} changes the sign in the same way as tf(t) does at γ_{i}.

From now on we assume n ≥ N(δ^{−}), N(δ^{+}). We now have to distinguish between odd and even d.

First, we consider the case d is even. From the assumption it follows that tf(t) < 0 for t < γ_{1} and for γ_{d−2} < t < 0. Thus at β_{1}^{n} the polynomial h_{d} + tg_{n}(t) + ρ^{n}tf(t) + t^{d} changes sign from − to + and at β_{d−2}^{n} from + to −. By lim_{t→±∞}(h_{d} + tg_{n}(t) + ρ^{n}tf(t) + t^{d}) = +∞ it follows that there is a zero β_{d−1}^{n} > β_{d−2}^{n} and a zero β_{d}^{n} < β_{1}^{n}. If d is odd analogous arguments prove the existence of zeros β_{d−1}^{n} > β_{d−2}^{n} and β_{d}^{n} < β_{1}^{n}.

So far we have shown that for n large enough all zeros of h_{d}+tg_{n}(t)+ ρ^{n}tf(t) + t^{d} are simple and real.

For fixed 1 ≤ i ≤ d−2 and large enough n each sequence (β_{i}^{n})_{n≥1},1 ≤ i ≤ d − 2, lies in a compact interval on the real line. Since we can choose the length of the interval to be arbitrarily small it follows that the sequences (β_{i}^{n})_{n≥1}, 1 ≤ i ≤ d − 2, converge to fixed real numbers α_{i}. The coefficients of t^{i}, 1 ≤ i ≤ d − 1, in the polynomial h_{d} + tg_{n}(t) + ρ^{n}tf(t) + t^{d} converge to +∞ by lim_{n→∞} g_{n}(t)/ρ^{n} = 0 and the fact that all coefficients of f(t) are strictly positive. It follows that there must be a zero of large absolute value. On the other hand from the fact that the constant term h_{d} is independent of n it follows that there must also be a zero close to 0. Since β_{d}^{n} is bounded from above by γ_{1} it follows that lim_{n→∞} β_{d}^{n} = −∞. But this in turn implies lim_{n→∞} β_{d−1}^{n} = 0. □

Now we are in position to provide a proof of Theorem 4.2.

Proof of Theorem 4.2. Let w_{1}^{1}, w_{1}^{2}, w_{2}, …, w_{d} be eigenvectors of ℌ_{d−1} for the eigenvalues 1, 1, 2 …, d! satisfying (iii) and (iv) of Lemma 4.6. If we expand 𝔥^{Δ} as a linear combination 𝔥^{Δ} = a_{1}^{1}w_{1}^{1} + a_{1}^{2}w_{1}^{2} + a_{2}w_{2} + ⋯ a_{d}w_{d} then by Lemma 4.6 (i) and Remark 4.7 we know that a_{d} > 0. The h-polynomial 𝔥^{Δ}(t) decomposes analogously into a_{1}^{1}H_{1}^{1}(t) + a_{1}^{2}H_{1}^{2}(t) + a_{2}H_{2}(t) + ⋯ + a_{d}H_{d}(t), where H_{1}^{1}(t), H_{1}^{2}(t), H_{2}(t), …, H_{d}(t) are the generating polynomials of the vectors w_{1}^{1}, w_{1}^{2}, w_{2}, …, w_{d} when read backwards; that is if (v_{0}, …, v_{d}) is the vector then v_{d} + v_{d−1}t + ⋯+v_{0}t^{d} is its generating polynomial when read backward. By Lemma 4.6 (iii) it follows that a_{1}^{1} = h_{d}^{Δ} and a_{1}^{2} = h_{0}^{Δ} = 1. Clearly, 𝔥^{sd^{n}(Δ)}(t) = h_{d}^{Δ}H_{1}^{1}(t) + H_{1}^{2}(t) + 2^{n}a_{2}H_{2}(t) + ⋯ + (d!)^{n}a_{d}H_{d}(t). We set

g_{n}(t) := \frac{1}{t}(h_{d}^{Δ}H_{1}^{1}(t) + H_{1}^{2}(t) + 2^{n}a_{2}H_{2}(t) + ⋯
⋯ + (d − 1)!^{n}a_{d−1}H_{d−1}(t) − h_{d}^{Δ} − t^{d})

and

f(t) := \frac{a_{d}H_{d}(t)}{d!t}.

By Lemma 4.6 (ii)-(iv) it follows that f(t) and g_{n}(t) are polynomials of degree d−2. Moreover, by Lemma 4.6 and Remark 4.7 all coefficients of f(t) are all strictly positive and

𝔥^{sd^{n}(Δ)}(t) = h_{d} + tg_{n}(t) + (d!)^{n}tf(t) + t^{d}.

By Lemma 4.8 the polynomial H_{d}(t) and therefore the polynomial f(t) has only simple and real zeros that are all strictly negative. Thus g_{n}(t) and f(t) satisfy the assumption of Lemma 4.9 and therefore the assertion follows by Lemma 4.9. □

It seems to be a challenging problem to determine the numbers α_{i}, 1 ≤ i ≤ d − 2, from Theorem 4.2. As our proofs show this in turn is closely related to determining eigenvectors of the matrices 𝔉_{d−1} and ℌ_{d−1} for the eigenvalue d!. We were not able to give an explicit description of such an eigenvector.

Problem 4.10. Give a description of an eigenvector of the matrices 𝔉_{d−1} and ℌ_{d−1} for the eigenvalue d!.

Acknowledgment

We thank the referee for her/his numerous suggestions. In particular, we are grateful for asking the question that led us to the proof Proposition 4.3.

References

[1] W. Bruns and J. Herzog, Cohen-Macaulay Rings, Cambridge University Press, Cambridge, 1993.

[2] A. Björner, J.D. Farley, Chain polynomials of distributive lattices are 75% unimodal, Electr. J. of Comb. 12 (2005) 1-7.

[3] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, European J. Combin. 15 (1994) 417–441.

[4] P. Bränden, On linear transformations preserving the Pólya Frequency property, Trans. Amer. Math. Soc. 358 (2006) 3697-3716.

[5] R. Charney and M. Davis, Euler characteristic of a nonpositively curved, piecewise Euclidean manifold, Pac. J. Math. 171 (1995) 117–137.

[6] S.R. Gal, The real root conjecture fails for five- and higher-dimensional spheres, Disc. and Comp. Geom. 34 (2005) 269-284.

[7] R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985.

[8] J. Jonsson and V. Welker, Complexes of injective words, in preparation.

[9] K. Karu, The cd-index of fans and lattices, Compositio Math. 142 (2006) 701-718.

[10] V. Reiner, V. Welker, On the Charney-Davis and Neggers-Stanley conjectures, J. Comb. Theory, Ser A, 109 (2005) 247-280.

[11] Stanley, R.P., Some aspects of groups acting on posets, J. Comb. Theory, Ser A, 32 (1982) 132-161.

[12] Stanley, R.P., Enumerative Combinatorics, Vol. I, Cambridge University Press, Cambridge, 1997.

[13] Stanley, R.P., Flag f-vectors and the cd-index, Math. Z. 216 (1994) 483-499.

[14] Ziegler, G.M., Lectures on Polytopes, Springer Verlag, New York, 1994.

Dipartimento di Matematica, Universita’ di Roma ”Tor Vergata”, Via della Ricerca Scientifica, 1, 00133, Roma, Italy

  E-mail address: brenti@mat.uniroma2.it

Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, 35032 Marburg, Germany

  E-mail address: welker@mathematik.uni-marburg.de