ON LINEAR TRANSFORMATIONS PRESERVING THE PÓLYA FREQUENCY PROPERTY

Petter Brändén^{1}

Matematik, Chalmers tekniska högskola och Göteborgs universitet S-412 96 Göteborg, Sweden

                   branden@math.chalmers.se

Abstract. We prove that certain linear operators preserve the Pólya frequency property and real-rootedness, and apply our results to settle some conjectures and open problems in combinatorics proposed by Bóna, Brenti and Reiner-Welker.

1. Introduction

Many sequences encountered in various areas of mathematics, statistics and computer science are known or conjectured to be unimodal or log-concave, see [8, 32, 34]. A sufficient condition for a sequence to enjoy these properties is that it is a Pólya frequency (P F for short) sequence, or equivalently for finite sequences, that its generating function has only real and non-positive zeros. It is often the case that the generating function of a finite P F -sequence has more transparent properties when expanded in a basis other than the standard basis {x^{i}}_{i≥0} of ℝ[x]. Therefore it is natural to investigate how P F -sequences translate when expressed in various basis. This amounts to studying properties of the linear operator that maps one basis to another. A systematic study of this was first pursued by Brenti in [7]. This is also the theme of this paper.

In Section 3 we will study linear operators of the type

ϕ_{F} = ∑_{k=0}^{n} Q_{k}(x)\frac{d^{k}}{dx^{k}} ,

where F (x, z) = ∑_{k=0}^{n} Q_{k}(x)z^{k} ∈ ℝ[x, z]. Here we will give sufficient conditions on F for ϕ_{F} to preserve the P F -property. The results attained generalizes and unifies theorems of Hermite, Poulain, Pólya and Schur. We will also in this section give a sufficient condition for a family of natural ℝ-bilinear forms to preserve the P F -property in both arguments. This generalizes results of Wagner [11, 37, 38].

1991 Mathematics Subject Classification. Primary: 05A15, 26C10 ; Secondary:

05A19, 05A05, 20F55.

1Research financed by the EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272, while the author was at Universitá di Roma “Tor Vergata”, Rome, Italy.

2 LINEAR TRANSFORMATIONS PRESERVING THE P F -PROPERTY

An important linear operator in combinatorics is the operator defined by E(\binom{x}{i}) = x^{i}, for all i ∈ ℕ. In Section 4 we will prove that whenever a polynomial f of degree d has nonnegative coefficients when expanded in the basis {x^{i}(x + 1)^{d−i}}_{i=0}^{d} the polynomial E(f) will have only real, non-positive and simple zeros.

In the remainder of the paper we use the theory developed to settle some conjectures and open problems raised in combinatorics. Highlights are; we prove that the q-Eulerian polynomials, A_{n}(x; q), defined by Foata and Schützenberger [17] and further studied by Brenti in [10] have only real zeros for all integers q. This settles a conjecture raised by Brenti. We will also continue the study of the W -Eulerian polynomials, defined for any finite Coxeter group W and the q-analog B_{n}(x; q), initiated by Brenti in [9].

In Section 7 we prove that the h-vectors of a family simplicial complexes associated to finite Weyl groups defined by Fomin and Zelevinski [18] are P F, thus settling an open problem raised by Reiner and Welker [30]. In Section 5 we prove that the numbers {W_{t}(n, k)}_{k=0}^{n−1} of t-stack sortable permutations in S_{n} with k descents form P F -sequences when t = 2, n − 2, and thereby settling two new cases of an open problem proposed by Bóna [2, 3].

2. Notation and preliminaries

In this section we collect definitions, notation and results that will be used frequently in the rest of the paper. Let {a_{i}}_{i=0}^{∞} be a sequence of real numbers. It is unimodal if there is a number p such that a_{0} ≤ a_{1} ≤ ⋯ ≤ a_{p} ≥ a_{p+1} ≥ ⋯, and log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for all i > 0.

An infinite matrix A = (a_{ij})_{i,j≥0} of real numbers is totally positive, T P, if all minors of A are nonnegative. An infinite sequence {a_{i}}_{i=0}^{∞} of real numbers is a Pólya frequency sequence, P F -sequence, if the matrix (a_{i−j})_{i,j≥0} is T P. Thus a P F -sequence is by definition log-concave and therefore also unimodal. A finite sequence a_{0}, a_{1}, a_{2}, …, a_{n} is said to be P F if the infinite sequence a_{0}, a_{1}, a_{2}, …, a_{n}, 0, 0, … is P F. A sequence {a_{i}}_{i=0}^{∞} is said to be P F_{r} if all minors of size r of (a_{i−j})_{i,j≥0} are nonnegative. If the polynomials {b_{i}(x)}_{i=0}^{d} are linearly independent over ℝ and r ∈ ℕ we define the set P F_{r}[{b_{i}(x)}_{i=0}^{d}] to be

P F_{r}[{b_{i}(x)}_{i=1}^{d}] = {∑_{i=0}^{d} λ_{i}b_{i}(x) : {λ_{i}}_{i=0}^{∞} is P F_{r}},

and P F [{b_{i}(x)}_{i=1}^{d}] = ⋂_{r=0}^{∞} P F_{r}[{b_{i}(x)}_{i=1}^{d}].

The following theorem characterizes P F -sequences. It was conjectured by Schoenberg and proved by Edrei [16], see also [24].

Theorem 2.1. Let {a_{i}}_{i=0}^{∞} be a sequence of real numbers with a_{0} = 1. Then it is a P F -sequence if and only if the generating function can be expanded, in a neighborhood of the origin, as

∑_{i≥0} a_{i}z^{i} = e^{γz} \frac{∏_{i≥0}(1 + α_{i}z)}{∏_{i≥0}(1 − β_{i}z)},

where γ ≥ 0, α_{i}, β_{i} > 0 and ∑_{i≥0}(α_{i} + β_{i}) < ∞.

A consequence of this theorem is that a finite sequence is P F if and only if its generating function is a polynomial with only real non positive zeros.

Let f, g ∈ ℝ[x] be real-rooted with zeros: α_{1} ≤ ⋯ ≤ α_{i} and β_{1} ≤ ⋯ ≤ β_{j}, respectively. We say that f interlaces g, denoted f ⪯ g, if j = i + 1 and

β_{1} ≤ α_{1} ≤ β_{2} ≤ ⋯ ≤ β_{j−1} ≤ α_{j−1} ≤ β_{j}.

We say that f alternates left of g, denoted f ≪ g, if i = j and

α_{1} ≤ β_{1} ≤ ⋯ ≤ β_{i−1} ≤ α_{i} ≤ β_{i}.

If in addition f and g have no common zero then we say that f strictly interlaces g and f strictly alternates left of g, respectively. We also say that two polynomials f and g alternate if one of the polynomials alternates left of or interlaces the other. We will need two simple lemmata concerning these concepts. A polynomial is said to be standard if its leading coefficient is positive.

Lemma 2.2. Let g and {f_{i}}_{i=1}^{n} be real-rooted standard polynomials.

(i) If for each 1 ≤ i ≤ n we have either g ≪ f_{i} or g ⪯ f_{i}. Then the sum F = f_{1} + f_{2} + ⋯ + f_{n} is real-rooted with g ⪯ F or g ≪ F, depending on the degree of F.

(ii) If for each 1 ≤ i ≤ n we have either f_{i} ≪ g or f_{i} ⪯ g. Then the sum F = f_{1} + f_{2} + ⋯ + f_{n} is real-rooted with F ⪯ g or F ≪ g, depending on the degree of F.

Proof. The lemma follows easily by counting the sign-changes of F at the zeros of g, see e.g., [39, Prop. 3.5]. □

The next lemma is obvious:

Lemma 2.3. If f_{0}, f_{1}, …, f_{n} are real-rooted polynomials with f_{0} ≪ f_{n} and f_{i−1} ≪ f_{i} for all 1 ≤ i ≤ n, then f_{i} ≪ f_{j} for all 0 ≤ i ≤ j ≤ n.

The following theorem is a characterization of alternating polynomials due to Obreschkoff [26] and Dedieu [14]:

Theorem 2.4. Let f, g ∈ ℝ[x]. Then f and g alternate (strictly alternate) if and only if all polynomials in the space

{αf + βg : α, β ∈ ℝ},

have only real (real and simple) zeros.

An immediate but non-trivial consequence of this theorem is:

Corollary 2.5. Let ϕ : ℝ[x] → ℝ[x] be a linear operator. Then ϕ preserves the real-rootedness property (real- and simple-rootedness property) if and only if ϕ preserves the alternating property (strictly alternating property).

We denote by ℕ the set of natural numbers {0, 1, 2, …}. The symmetric group of bijections π : {1, 2, …, n} → {1, 2, …, n} is denoted by S_{n}. A descent in a permutation π ∈ S_{n} is an index 1 ≤ i ≤ n, such that π(i) > π(i + 1). Let des(π) denote the number of descents in π. The Eulerian polynomials, A_{n}(x), are defined by A_{n}(x) = ∑_{π∈S_{n}} x^{des(π)+1} and satisfies, see e.g. [12]

∑_{k≥0} k^{n}x^{n} = \frac{A_{n}(x)}{(1 − x)^{n+1}} .

The binomial polynomials are defined by \binom{x}{0} = 1 and \binom{x}{k} = \frac{x(x−1)···(x−k+1)}{k!} for k ≥ 1.

In several proofs we will implicitly use the fact that the zeros of a polynomial are continuous functions of the coefficients of the polynomial. In particular the limit of a sequence of real-rooted polynomials is again real-rooted. For a treatment of these matters we refer the reader to [25].

3. A class of linear operators preserving the P F -property

For any polynomial F (x, z) = ∑_{k=0}^{n} Q_{k}(x)z^{k} ∈ ℝ[x, z] we define a linear operator ϕ_{F} : ℝ[x] → ℝ[x] by,

ϕ_{F} (f) := ∑_{k=0}^{n} Q_{k}(x)\frac{d^{k}}{dx^{k}} f(x).

In this section we will investigate for which F ∈ ℝ[x, z] the linear operator ϕ_{F} preserves real-rootedness- and the P F -property .

We will need some terminology and a theorem from [5]. For ξ ∈ ℝ let T_{ξ} : ℝ[x] → ℝ[x] be the translation operator defined by T_{ξ}(f(x)) = f(x + ξ). For any linear operator ϕ : ℝ[x] → ℝ[x] we define a linear transform L_{ϕ} : ℝ[x] → ℝ[x, z] by

L_{ϕ}(f) := ϕ(T_{z}(f))
= ∑_{n} ϕ(f^{(n)})(x)\frac{z^{n}}{n!}  (3.1)

= ∑_{n} \frac{ϕ(x^{n})}{n!}f^{(n)}(z).

Definition 3.1. Let ϕ : ℝ[x] → ℝ[x] be a linear operator. Define a function d_{ϕ} : ℝ[x] → ℕ ∪ {−∞} by: If ϕ(f^{(n)}) = 0 for all n ∈ ℕ, we let d_{ϕ}(f) = −∞. Otherwise let d_{ϕ}(f) be the smallest integer d such that ϕ(f^{(n)}) = 0 for all n > d. Hence d_{ϕ}(f) ≤ deg f for all f ∈ ℝ[x].

The set 𝒜 (ϕ) is defined as follows: If d_{ϕ}(f) ∈ {−∞, 0} and ϕ(f) is standard real- and simple-rooted, then f ∈ 𝒜 (ϕ). Moreover, f ∈ 𝒜 (ϕ) if d = d_{ϕ}(f) ≥ 1 and all of the following conditions are satisfied:

(i) ϕ(f^{(i)}) all have leading coefficients of the same sign and deg(ϕ(f^{(i−1)})) = deg(ϕ(f^{(i)})) + 1 for 1 ≤ i ≤ d,

(ii) ϕ(f) and ϕ(f′) have no common real zero, (iii) ϕ(f^{(d)}) strictly interlaces ϕ(f^{(d−1)}), (iv) for all ξ ∈ ℝ the polynomial L_{ϕ}(f)(ξ, z) is real-rooted.

The following theorem is proved in [5]:

Theorem 3.2. Let ϕ : ℝ[x] → ℝ[x] be a linear operator. If f ∈ 𝒜 (ϕ) then ϕ(f) is real- and simple-rooted.

We will also need the following classical theorem of Hermite and Poulain. For a proof see [26].

Theorem 3.3. Let f = a_{0} + a_{1}x + ⋯ + a_{n}x^{n} and g be real-rooted polynomials. Then the polynomial

f(\frac{d}{dx})g := a_{0}g(x) + a_{1}g′(x) + ⋯ + a_{n}g^{(n)}(x)

is real-rooted. Moreover, if f(\frac{d}{dx})g ≠ 0 then any multiple zero of f(\frac{d}{dx})g is a multiple zero of g.

The following theorem gives a sufficient condition for a polynomial to be mapped onto a real-rooted polynomial.

Theorem 3.4. Let F = ∑_{k=0}^{n} Q_{k}(x)z^{k} be such that Q_{0} ≠ 0 and (I) For all ξ ∈ ℝ, F (ξ, z) is real-rooted, (II) Q_{0} strictly interlaces or strictly alternates left of Q_{1}, and deg Q_{0} =

0 or Q_{0} and Q_{1} have leading coefficients of the same sign. Suppose that

(III) f is real- and simple-rooted and that for 0 ≤ k ≤ deg f the polynomials ϕ_{F} (f^{(k)}) have their leading term of the same sign with

deg ϕ_{F} (f^{(k)}) = deg Q_{0} + deg f − k.

Then ϕ_{F} (f) is real- and simple-rooted.

Proof. We will show that the set of real- and simple-rooted polynomials satisfying (III) is a subset of 𝒜 (ϕ_{F}) by verifying conditions (i)-(iv) of Definition 3.1. Condition (i) follows immediately from (III). For condition (iv) note that

L_{ϕ}(f)(ξ, z) = ∑_{k=0}^{n} Q_{k}(ξ)f^{(k)}(ξ + z),

so by the Theorem 3.3 condition (iv) is satisfied. Suppose that η is a common zero of ϕ_{F} (f) and ϕ_{F} (f′). By (3.1) we have that 0 is a multiple zero of L_{ϕ}(f)(η, z). Moreover, since L_{ϕ}(f)(η, z) is not identically equal to zero, by (II), Theorem 3.3 tells us that 0 is a multiple zero of f(η+z). This means that η is multiple zero of f contrary to the assumption that f is simple-rooted, and verifies condition (ii).

For condition (iii) we have to show that for all α ∈ ℝ such that x+α satisfies (III) the polynomial ϕ_{F} (1) = Q_{0} strictly interlaces f(x) := ϕ_{F} (x + α) = (x + α)Q_{0} + Q_{1}. This follows from (II) when analyzing the sign of f(x) := ϕ_{F} (x + α) at the zeros of Q_{0}: Let α_{k} < α_{k−1} < ⋯ < α_{1} be the zeros of Q_{0} ordered by size. Suppose that Q_{0} and Q_{1} are standard and that Q_{0} strictly interlaces or strictly alternates left of Q_{1}. Then sgn f(α_{i}) = sgn Q_{1}(α_{i}) = (−1)^{i} for 1 ≤ i ≤ k. By Rolle’s theorem we know that f has a zero in each interval (α_{i}, α_{i+1}). This accounts for k − 1 real zeros of f. Since Q_{0} has positive sign, so does f by condition (III). Now, because f(α_{1}) < 0 and f is standard, f must have a zero to the right of α_{1}. We now know that f has k zeros real. The signs at α_{i} forces the remaining zero to be in the interval (−∞, α_{k}). Thus Q_{0} strictly interlaces Q_{1} as was to be shown.

Now, if Q_{0} = A ∈ ℝ then deg Q_{1} ≤ 1. Suppose that Q_{1} = B ∈ ℝ. Then clearly A strictly interlaces (x + α)A + B. If Q_{0} = A and Q_{1} = Cx + D where A, B, C ∈ ℝ, then f = (A + C)x + Aα + D, so by (III) we have that Q_{0} strictly interlaces f. This concludes the proof. □

In some cases it may be convenient to have sharper hypothesis. Therefore we state the following form of the theorem.

Corollary 3.5. Let d ∈ ℕ be given and let F = ∑_{k=0}^{n} Q_{k}(x)z^{k} be such that Q_{0} ≠ 0 and

(i) For all ξ ∈ ℝ, F (ξ, z) is real-rooted, (ii) Q_{0} strictly interlaces or strictly alternates left of Q_{1}, and deg Q_{0} =

0 or Q_{0} and Q_{1} have leading coefficients of the same sign. (iii) The polynomials ϕ_{F} (x^{k}), 0 ≤ k ≤ d have the same sign and

deg ϕ_{F} (x^{k}) = deg Q_{0} + k.

Then ϕ_{F} (f) is real-rooted (real- and simple-rooted) if f is real-rooted (real and simple-rooted) and deg(f) ≤ d.

Proof. The case of real- and simple-rooted f follows immediately from Theorem 3.4 since (iii) implies (III). If f is a real-rooted polynomial of degree at most d, then f is the limit of a sequence {f_{k}}_{k=0}^{∞} of real- and simple-rooted polynomials of degree at most d. It follows that ϕ_{F} (f) is the limit of ϕ_{F} (f_{k}), and the thesis follows by continuity. □

In the language of P F -sequences we have:

Theorem 3.6. Let d ∈ ℕ be given and let F = ∑_{k=0}^{n} Q_{k}(x)z^{k} ∈ ℝ[x, z] be such that Q_{0} ≠ 0 and (i) For all ξ ∈ ℝ, F (ξ, z) is real-rooted, (ii) ϕ_{F} (1) strictly interlaces ϕ_{F} (x). (iii) For all 0 ≤ k ≤ d

deg ϕ_{F} (x^{k}) = deg Q_{0} + k,

and ϕ_{F} (x^{k}) ∈ P F_{1}. Then P F [{ϕ_{F} (x^{i})}_{i=0}^{d}] ⊆ P F [x^{i}].

Several old results can be derived from these last few theorems. In [27, p. 163] Pólya gave a theorem which he states probably was the most general theorem on real-rootedness known at the time. ”Dieser Satz gehört wohl zu den allgemeinsten bekannten Sätzen über Wurzelrealität.”:

Theorem 3.7. Let f(x) be a real-rooted polynomial of degree n, and let

b_{0} + b_{1}x + ⋯ + b_{n+m}x^{n+m}, (m ≥ 0)

be a real-rooted polynomial such that b_{i} > 0 for 0 ≤ i ≤ n. Then the equation

G(x, y) := b_{0}f(y) + b_{1}xf′(y) + b_{2}x^{2}f′′(y) + ⋯ + b_{n}f^{(n)}(y) = 0,

has n real intersection points, (counted with multiplicity), with the line

sx − ty + u = 0,

provided that s, t ≥ 0, s + t > 0 and u ∈ ℝ.

Proof. We may assume that s, t > 0 since the other cases follows by continuity when s and/or t tends to zero. Thus we may write the equation as

a_{0}g(x) + a_{1}xg′(x) + a_{2}x^{2}g′′(x) + ⋯ + a_{n}g^{(n)}(x) = 0,

where g(x) = f(st^{−1}x + ut^{−1}) and a_{i} = s^{i}t^{−i}b_{i}. Now, we see that all hypothesis of Corollary 3.5 are satisfied for

F (x, z) = a_{0} + a_{1}xz + a_{2}x^{2}z^{2} + ⋯ + a_{n+m}x^{n+m}z^{n+m},

when d = n. □

We will later need one famous consequence of this theorem, t = 1, s = u = 0, due to Schur [31].

Theorem 3.8. Let f = ∑_{k=0}^{n} a_{k}x^{k} and g = ∑_{k=0}^{m} b_{k}x^{k} be two realrooted polynomials such that g has all zeros of the same sign. Then the polynomial

(fSg)(x) = ∑_{k≥0}^{M} k!a_{k}b_{k}x^{k},

where M = min(m, n) has only real zeros.

3.1. Multiplier-sequences. A multiplier-sequence is a sequence T = {γ_{i}}_{i=0}^{∞} of real numbers such that if a polynomial f(x) = a_{0} + a_{1}x + ⋯ + a_{n}x^{n} has only real zeros, then the polynomial

T [p(x)] := a_{0}γ_{0} + a_{1}γ_{1}x + ⋯ + a_{n}γ_{n}x^{n},

also has only real zeros. There is a characterization of multipliersequences due to Pólya and Schur [27, p. 100-124]:

Theorem 3.9. Let T = {γ_{i}}_{i=0}^{∞} be a sequence of real numbers and let ϕ(x) = T [e^{x}] = ∑_{k=0}^{∞} γ_{k} \frac{x^{k}}{k!} be its exponential generating function. Then T is a multiplier-sequence if and only if ϕ is a real entire function which can be written as

ϕ(x) = cx^{n}e^{−αx^{2}+βx} ∏_{k=1}^{∞}(1 + δ_{k}x)e^{−δ_{k}x},

where c, β, δ_{k} ∈ ℝ, c ≠ 0, α ≥ 0, n ∈ ℕ and ∑_{k=1}^{∞} δ_{k}^{2} < ∞.

The following lemma is well-known but elementary, so we give a proof here.

Lemma 3.10. A multiplier-sequence is strictly log-concave. In particular, a nonnegative multiplier-sequence has no internal zeros.

Proof. If f(x) = a_{m}x^{m} + a_{m+1}x^{m+1} + ⋯ + a_{n}x^{n} is real-rooted with a_{m}a_{n} ≠ 0, then the coefficients satisfy (see [21, p. 52]):

\frac{a_{i}^{2}}{\binom{n}{i}2} > \frac{a_{i−1}}{\binom{n}{i−1}} \frac{a_{i+1}}{\binom{n}{i+1}} (m < i < n).

Now, if Γ = {γ_{i}}_{i=0}^{∞} is a multiplier-sequence, then Γ[(x + 1)^{n}] is realrooted for all n ∈ ℕ, which implies

γ_{i} > γ_{i−1}γ_{i+1},

for all i such that there are integers m < i < n with γ_{m}γ_{n} ≠ 0.

□

Theorem 3.11. Let {λ_{k}}_{k=0}^{∞} be a non-negative multiplier-sequence, and let α < β ∈ ℝ be given. Define two ℝ-bilinear forms ℝ[x]×ℝ[x] → ℝ[x] by

f · g := ∑_{k≥0} \frac{λ_{k}}{k!} f^{(k)}(x)g^{(k)}(x)(x − α)^{k}(x − β)^{k},

f ∘ g := ∑_{k≥0} \frac{λ_{k}}{k!} f^{(k)}(x)g^{(k)}(x)(x − α)^{k},

If f is real-rooted and g is [α, β]-rooted, then f · g is real-rooted. If f is real-rooted and g is [−∞, α]-rooted, then f ∘ g is real-rooted.

Proof. We prove the statement for · since the case of ∘ is similar. We may assume that λ_{0} > 0. Clearly the theorem is true if λ_{i} = 0 for all i > 0, so by Lemma 3.10 we may assume that λ_{1} > 0. Let g have all zeros simple and in the interval (α, β), and let ϕ be the linear operator defined by ϕ(f) = f · g. Then ϕ = ϕ_{F}, where

F (x, z) = ∑_{k≥0} λ_{k} \frac{g^{(k)}(x)}{k!}(x − α)^{k}(x − β)^{k}z^{k}.

Since {λ_{k}}_{k≥0} is a multiplier sequence F (ξ, z) is real-rooted for all real choices of ξ. Now, Q_{0} = λ_{0}g(x) and Q_{1} = λ_{1}(x − α)(x − β)g′(x), so Q_{0} strictly interlaces Q_{1}. Moreover, deg ϕ(x^{k}) = deg Q_{0} + k for all k, so all the hypothesis of Corollary 3.5 are fulfilled. Since any [α, β]-rooted polynomial is the limit of polynomial which are (α, β)- and simplerooted the thesis follows by continuity. □

A sequence of real numbers Γ = {γ_{k}}_{k=0}^{∞} is called an multiplier nsequence if for any real-rooted polynomial f = a_{0} + a_{1}x + ⋯ + a_{n}x^{n} of degree at most n the polynomial Γ[f] := a_{0}γ_{0} + a_{1}γ_{1}x + ⋯ + a_{n}γ_{n}x^{n} is real-rooted. There is a simple algebraic characterization of multiplier n-sequences [13]:

Theorem 3.12. Let Γ = {γ_{k}}_{k=0}^{∞} be a sequence of real numbers. Then Γ is a multiplier n-sequence if and only if Γ[(x+1)^{n}] is real-rooted with all its zeros of the same sign.

Recall the definition of the hypergeometric function _{2}F_{1}:

2F_{1} (a, b; c; z) = ∑_{m=0}^{∞} \frac{(a)_{m}(b)_{m}z^{m}}{(c)_{m}m!} ,

where (α)_{0} = 1 and (α)_{m} = α(α + 1) ⋯ (α + m − 1) when m ≥ 1. The Jacobi polynomial P_{n}^{(α,β)}(x) can be expressed as follows [28, p. 254]:

P_{n}^{(α,β)}(x) = \frac{(1 + α)_{n}}{n!}_{2}F_{1} (−n, 1 + α + β + n; 1 + α; \frac{1 − x}{2}) , (3.2)

We need the following lemma:

Lemma 3.13. Let n be a positive integer and r a non-negative real number. Then Γ = \{\binom{−n−r}{k}\}_{k=0}^{∞} is a multiplier n-sequence.

Proof. Let r > 0. Then

Γ[(x + 1)^{n}] = ∑_{k=0}^{n} \binom{−n − r}{k}\binom{n}{k}x^{k}
= _{2}F_{1} (−n, n + r; 1; x)
= P_{n}^{(0,r−1)}(1 − 2x),

where the last equality follows from (3.2). Since the Jacobi polynomials are known, see [28], to have all their zeros in [−1, 1] when α, β > −1, we have that Γ[(x+1)^{n}] has all its zeros in [0, 1]. The case r = 0 follows by continuity when we let r tend to zero from above. □

For any real number q let Γ_{q} := {q + k}_{k=0}^{∞}.

Corollary 3.14. Let n > 1 be a positive integer. Then Γ_{q} is an nsequence if and only if q ∉ (−n, 0).

Proof. Let q ∈ ℝ be given. We have to determine for which n > 1 the zeros of Γ_{q}[(x + 1)^{n}] are all real and of the same sign. Now,

Γ_{q}[(x + 1)^{n}] = (x + 1)^{n−1}{(n + q)x + q}.

If q ≥ 0 or n = −q then all zeros are negative so we may assume that q < 0 and n ≠ −q. If n > −q then q/(n + q) is negative so Γ_{q}[(x + 1)^{n}] has zeros of different signs. If on the other hand n < −q then q/(n + q) is positive which gives that all zeros of Γ_{q}[(x + 1)^{n}] are negative, and the lemma follows. □

4. The E-transformation

The E-transformation is the invertible linear operator, E : ℝ[x] → ℝ[x], defined by

E(\binom{x}{i}) = x^{i},

for all i ∈ ℕ. The P F -preserving properties of this linear operator was first studied in [7] and later in [38, 39] and [5]. It is important in the theory of (P, ω)-partitions since it maps the order-polynomial of a labeled poset to the E-polynomial of the same labeled poset, see [7, 38]. In, [7] Brenti proved the following theorem. Let λ(f) and Λ(f) denote the smallest and the largest real zero of the polynomial f, respectively.

Theorem 4.1. Suppose that f ∈ ℝ[x] has only real zeros and that f(n) = 0 for all n ∈ ([λ(f), −1] ∪ [0, Λ(f)]) ∩ ℤ. Then E(f) has all zeros real and non-positive.

In this section we will prove the following theorem:

Theorem 4.2. For all n ∈ ℕ we have

P F_{1}[\{x^{i}(x + 1)^{n−i}\}_{i=0}^{n}] ⊆ P F [\binom{x}{i}]

Moreover if f ∈ P F_{1}[{x^{i}(x + 1)^{n−i}}_{i=0}^{n}] then E(f) has simple zeros and

E((x + 1)^{d}) ≪ E(f) ≪ E(x^{d}).

The diamond product of two polynomials in ℝ[x] is the ℝ-bilinear form defined by

(f ⋄ g)(x) := E(E^{−1}(f)E^{−1}(g)).  (4.1)

This product was first studied by Wagner in [38, 39] and further studied in [5]. See also Section 8 of this paper. Using the Vandermonde identity

\binom{x}{i}\binom{x}{j} = ∑_{k≥0} \binom{k}{k − i, i + j − k, k − j}\binom{x}{k},

it follows, see [39], that

(f ⋄ g)(x) = ∑_{k≥0} \frac{f^{(k)}(x)}{k!} \frac{g^{(k)}(x)}{k!}x^{k}(x + 1)^{k}.  (4.2)

We will later need a symmetry property of E. Let R : ℝ[x] → ℝ[x] be the algebra automorphism defined by R(x) = −1 − x.

Lemma 4.3.

RE = ER

Proof. From (4.2) it follows that

R(f ⋄ g) = R(f) ⋄ R(g)  (4.3)

Note that RE(f) = ER(f) whenever f is linear. Now, suppose that f, g are polynomials such that RE(f) = ER(f) and RE(g) = ER(g). Then

RE(fg) = R(E(f) ⋄ E(g)) by (4.1)
= (RE(f)) ⋄ (RE(g)) by (4.3)
= (ER(f)) ⋄ (ER(g))
= E(R(f)R(g))
= ER(fg).

Since we may view E and R as ℂ-linear operators on ℂ[x], and ⋄ as a ℂ-bilinear form on ℂ[x], the lemma follows from the fundamental theorem of algebra. □

Lemma 4.4. Let α ∈ [−1, 0] and let f be a polynomial such that E(f) is [−1, 0]-rooted. Then E((x−α)f) is [−1, 0]-rooted and E(f) interlaces E((x − α)f). If E(f) in addition only has simple zeros, then so does E((x − α)f).

Proof. Let g = E(f) and let α ∈ [−1, 0]. By (4.2) we have that

E((x − α)f) = (x − α)g + x(x + 1)g′.  (4.4)

Since g interlaces (x − α)g and x(x + 1)g′ it also interlaces the sum, by Lemma 2.2. Also, if x ∉ [−1, 0] then the summands have the same sign so E((x − α)f) cannot have any zeros outside [−1, 0]. Suppose that g has only simple zeros. Then by (4.4) the only possible common zeros of g and E((x − α)f) are 0 and −1. If deg(f) ≥ 1 it also follows from (4.4) that the multiplicities of 0 and −1 of E((x − α)f) are the same as those of g. Hence the (simple) zeros of g separates the zeros of E((x−α)f) except possibly at 0, −1, and we conclude that E((x−α)f) has only simple zeros. □

Lemma 4.5. For all integers n ≥ 1 we have

(x + 1)E(x^{n}) = xE((x + 1)^{n}).

Proof. We may write

x^{n} = ∑_{k=1}^{n} a_{k}\binom{x}{k},

where a_{k} ∈ ℝ. Thus

E((x + 1)^{n}) = ∑_{k=1}^{n} a_{k}E[\binom{x}{k} + \binom{x}{k − 1}]

= ∑_{k=1}^{n} a_{k}(x^{k} + x^{k−1})
= (x + 1)x^{−1}E(x^{n}).
□

For i ∈ ℕ and let RR_{n} denote the set of real-rooted monic polynomials of degree n. We define a partial order ≤ on RR_{n} as follows: If f, g ∈ RR_{n} have zeros α_{1} ≤ α_{2} ≤ ⋯ ≤ α_{n} and β_{1} ≤ β_{2} ≤ ⋯ ≤ β_{n} respectively then f ≤ g, if α_{i} ≤ β_{i} for 1 ≤ i ≤ n.

Theorem 4.6. Suppose that f and g are [−1, 0]-rooted with f ≤ g. Then E(f) and E(g) are [−1, 0]- and simple-rooted, with E(f) ≪ E(g).

Proof. By Lemma 4.4 and induction we only have to show that E(f) ≪ E(g). If f and g have the same zeros except for one, i.e., f = (x − α)h and g = (x − β)h, where α < β, then

E(g) = E(f) − (β − α)E(h),

and since E(h) interlaces E(f) we have E(f) ≪ E(g) by Lemma 2.2.

Now, suppose that f and g are [−1, 0]-rooted polynomials of degree n such that f ≤ g. Then there are [−1, 0]-rooted polynomials {h_{i}}_{i=0}^{M} with

(x + 1)^{n} = h_{0} ≤ h_{1} ≤ ⋯ ≤ h_{M} = x^{n},

such that f, g ∈ {h_{i}}_{i=0}^{M} and h_{i−1} and h_{i} only differ in one zero for 1 ≤ i ≤ n. We therefore have

E(h_{0}) ≪ E(h_{1}) ≪ ⋯ ≪ E(h_{M}),

and since E(h_{0}) ≪ E(h_{M}), by Lemma 4.5, the theorem follows from Lemma 2.3. □

A consequence of Theorem 4.6 is that if {f_{i}}_{i=1}^{m} is a sequence of standard [−1, 0]-rooted polynomials of the same degree d, then by Lemma 2.2 and Theorem 4.6, the image under E of any non-negative sum F = ∑_{i=1}^{m} μ_{i}f_{i} will be [−1, 0]-rooted with

E((x + 1)^{d}) ≪ E(F) ≪ E(x^{d}).

It is easy to see that a standard polynomial f of degree d is [−1, 0]- rooted if and only if f can be written as

f(x) = (x + 1)^{d}g(\frac{x}{x + 1}),

where g is a standard and (−∞, 0)-rooted. On the other hand, since x^{i}(x + 1)^{d−i} is [−1, 0]-rooted we have that F can be written as a nonnegative sum of standard [−1, 0]-rooted polynomial of degree d if and only if

F (x) = ∑_{i=0}^{d} a_{i}x^{i}(x + 1)^{d−i},

where a_{i} ≥ 0. This proves Theorem 4.2.

5. t-stack sortable permutations

For relevant definitions regarding t-stack sortable permutations we refer the reader to [2]. Let W_{t}(n, k) be the number of t-stack sortable permutations in the symmetric group, S_{n}, with k descents. Recently, Bóna [1, 3] showed that for fixed n and t the numbers {W_{t}(n, k)}_{k=0}^{n−1} form a unimodal sequence. When t = n − 1 and t = 1 we get the Eulerian and the Narayana numbers (see [36] and [33, Exercise 6.36]), respectively. These are known to be P F -sequences and Bóna [2, 3] has raised the question if this is true for general t. Here we will settle the problem to the affirmative for t = 2 and t = n − 2.

The numbers W_{2}(n, k) are surprisingly hard to determine despite their compact and simple form. It was recently shown that

W_{2}(n, k) = \frac{(n + k)!(2n − k − 1)!}{(k + 1)!(n − k)!(2k + 1)!(2n − 2k − 1)!}.

See [4, 15, 20, 23] for proofs and more information on 2-stack sortable permutations.

From the case r = 0 in Lemma 3.13 and the identity

∑_{k=0}^{n} \binom{2n − k − 1}{n − 1}\binom{n}{k}x^{k} = (−1)^{n} ∑_{k=0}^{n} \binom{−n}{k}\binom{n}{k}(−x)^{n−k},

it follows that \binom{2n−k−1}{n−1} is an n-sequence.

Theorem 5.1. For all n ≥ 0 the sequence {W_{2}(n, k)}_{k=0}^{n−1}, which records 2-stack sortable permutations by descents, is P F.

Proof. We may write W_{2}(n, k) as

W_{2}(n, k) = \frac{\binom{2n−k−1}{n−1}\binom{n+k}{n−1}\binom{2n}{2k+1}}{n^{2}\binom{2n}{n}}.

An simple consequence of the notion of P F -sequences reads as follows: If {a_{i}}_{i≥0} is P F then so is {a_{ki}}_{i≥0}, where k is any positive integer. Applying this to the polynomial x(1 + x)^{2n} we see that ∑_{k} \binom{2n}{2k+1}x^{k} is real-rooted. Therefore the polynomial,

∑_{k=0}^{n−1} \binom{n + k}{n − 1}\binom{2n}{2k + 1}x^{k} = ∑_{k=0}^{n−1} \binom{2n − k − 1}{n − 1}\binom{2n}{2k + 1}x^{n−1−k},

is real-rooted. Another application of Lemma 3.13 gives that W_{n,2}(x) is real-rooted. □

It is easy to see that a permutation π ∈ S_{n} is (n − 2)-stack sortable if and only if it is not of the form σn1. Thus the generating function satisfies

xW_{n,n−2}(x) = A_{n}(x) − xA_{n−2}(x),

where A_{n}(x) is the nth Eulerian polynomial.

Theorem 5.2. For all real numbers t > −2 and integers n > 2, the polynomial

A_{n}(t, x) = A_{n}(x) + txA_{n−2}(x),

is real- and simple-rooted. Moreover, A_{n}(t, x)/x strictly interlaces A_{n+1}(t, x)/x for −2 < t ≤ 3.

Corollary 5.3. For all n ≥ 2 we have that {W_{n−2}(n, k)}_{k=0}^{n−1} is P F. Moreover, W_{n,n−2}(x) strictly interlaces W_{n+1,n−1}(x).

Proof of Theorem 5.2. It is well known that A_{n−1}(x) ≪ xA_{n−2}(x) and A_{n−1}(x) ⪯ A_{n}(x). So by Lemma 2.2 we have that A_{n}(t, x) is real- and simple-rooted for t ≥ 0. However, when t < 0 a similar argument does not apply.

Let E_{n}(t, x) = A_{n}(t, \frac{x}{1+x}). Then

E_{n}(t, x) = E_{n}(x) + tx(1 + x)E_{n−2}(x),

where the coefficient to x^{k} in E_{n}(x) counts the number of surjections σ : [n] → [k], see [7, 38]. These polynomials satisfy the recursion:

E_{n}(x) = x\frac{d}{dx}((1 + x)E_{n−1}(x)),

with initial condition E_{1}(x) = x. Thus, if we let G_{n}(x) = E_{n+1}(x)/x we have the following recursion:

G_{n}(x) = \frac{d}{dx}(x(1 + x)G_{n−1}(x)),  (5.1)

with G_{0}(x) = 1. Obviously G_{n}(x) is real- and simple-rooted. If we apply (5.1) two times we get the equation:

G_{n}(x) = (1 + 6x + 6x^{2})G_{n−2}(x) + 3x(1 + 2x)(1 + x)G′_{n−2}(x)+

x^{2}(1 + x)^{2}G′′_{n−2}(x),

and

G_{n}(t, x) = (1+(6+t)x+(6+t)x^{2})G_{n−2}(x)+3x(1+2x)(1+x)G′_{n−2}(x)+

x^{2}(1 + x)^{2}G′′_{n−2}(x).

To apply Theorem 3.4 we need show that for all ξ ∈ ℝ and −2 < t < 0 the polynomial

F (ξ, z) := (1 + (6 + t)ξ + (6 + t)ξ^{2}) + 3ξ(1 + 2ξ)(1 + ξ)z + ξ^{2}(1 + ξ)^{2}z^{2}

is real-rooted. The discriminant of F (ξ, z),

Δ(F (ξ, z)) = ξ^{2}(1 + ξ)^{2}(2 + t + (3 − t)(1 + 2ξ)^{2}),

is non-negative when −2 ≤ t ≤ 3, so F (ξ, z) real-rooted for these t. Since all the Q_{k}s are standard it is easy to see that condition (III) in the statement of Theorem 3.4 is satisfied. Moreover, 1+(6+t)x+(6+t)x^{2} strictly interlaces 3x(1 + 2x)(1 + x) when t > −2 so Theorem 3.4 applies. Since G_{n} strictly interlaces G_{n+1} we have by Theorem 3.4 and Corollary 2.5 that ϕ_{F} (G_{n}) strictly interlaces ϕ_{F} (G_{n+1}). Thus A_{n}(t, x) strictly interlaces A_{n+1}(t, x). □

6. q-Eulerian and W -Eulerian polynomials

A q-analog of the Eulerian polynomials was introduced and studied in [17] and further studied in [10]. It is defined by

A_{n}(x; q) := ∑_{π∈S_{n}} x^{exc(π)}q^{c(π)},

where c(π) and exc(π) denotes the number of cycles and excedances in π respectively. These polynomials satisfy the recursion

A_{n+1}(x; q) = (nx + q)A_{n}(x; q) − x(x − 1)\frac{∂}{∂x}A_{n}(x; q),

with initial condition A_{0}(x; q) := 1. See [10] for a proof. The following theorem appears in [10].

Theorem 6.1. Let q ∈ ℝ, q > 0. Then the polynomials A_{n}(x, q) have only real non-positive simple zeros.

Brenti also makes the following conjecture:

Conjecture 6.2. Let n, m ∈ ℕ. Then A_{n}(x; −m) has only real zeros.

In what follows we will prove this conjecture using multiplier nsequences. For n ∈ ℕ define the polynomials E_{n}(x; q) by:

E_{n}(x; q) := (1 + x)^{n}A_{n}(\frac{x}{1 + x}; q).

It is clear that E_{n}(x; q) is real-rooted if and only if A_{n}(x; q) is realrooted. These polynomials satisfy a somewhat easier recursion. Namely,

E_{n+1}(x; q) = (1 + x)\{qE_{n}(x; q) + x\frac{∂}{∂x}E_{n}(x; q)\},  (6.1)

with initial condition E_{0}(x; q) = 1. Now, for q ∈ ℝ let Γ_{q} : ℝ[x] → ℝ[x] be the linear operator defined by Γ_{q}(f(x)) = qf(x) + xf′(x). Since Γ_{q}(x^{n}) = (q + n)x^{n} we may apply Lemma 3.14.

Theorem 6.3. Let q ∈ ℝ and n ∈ ℕ. If q ≥ 0, n ≤ −q or q ∈ ℤ then E_{n}(x; q) has only real zeros.

Proof. We may write (6.1) as

E_{n+1}(x; q) = (x + 1)Γ_{q}[E_{n}(x; q)].

The cases q ≥ 0 and n ≤ −q follow from Lemma 3.14 by induction. We may therefore assume that q = −m is a negative integer. We claim that deg E_{n}(x; q) = n if n ≤ m and deg E_{n}(x; q) = m if n ≥ m. From this the real-rootedness follows by Lemma 3.14 and induction. The case n ≤ m is clear since Γ_{q}[x^{n−1}] = −(m−n+1) < 0. The case n > m also follows by induction. Suppose that n ≥ m and that deg E_{n}(x; q) = m. Then by the recursion we have that deg E_{n+1}(x; q) ≤ m + 1. Moreover, since Γ_{q}[x^{m}] = 0 we have that deg E_{n+1}(x; q) ≤ m. Let a ≠ 0 be the coefficient to x^{m} of E_{n}(x; q). Then the coefficient to x^{m} of E_{n+1}(x; q) is aΓ_{q}[x^{m−1}] = −a, so deg E_{n+1}(x; q) = m, and the thesis follows. □

The Eulerian polynomial, P (W, x), of a finite Coxeter group W is the polynomial,

P (W, x) = ∑_{σ∈W} x^{d_{W} (σ)},

where d_{W} (σ) is the number of W -descents of σ, see [9]. This polynomial is also the generating function for the h-vector of the Coxeter complex associated to (W, S). For Coxeter groups of type A_{n} we have that P (A_{n}, x) = A_{n}(x)/x, the shifted Eulerian polynomial. Also, for Coxeter groups of type B_{n} it is known, see [9], that P (B_{n}, x), has only real zeros. It is easy to see that P (W_{1} × W_{2}, x) = P (W_{1}, x)P (W_{2}, x) for finite Coxeter groups W_{1} and W_{2}. Also, the real-rootedness can be checked ad hoc for the exceptional groups. Thus, by the classification of finite irreducible Coxeter groups, to prove that P (W, x) has only real zeros for all finite Coxeter groups it suffices to prove that P (D_{n}, x) is real-rooted for Coxeter groups of type D_{n}. The real-rootedness of P (D_{n}, x) is conjectured by Brenti in [9]. It is known that the Eulerian polynomials of type A_{n}, B_{n} and D_{n} are related by, see [9, 29, 35]:

P (D_{n}, x) = P (B_{n}, x) − n2^{n−1}xP (A_{n−1}, x).

This relationship was first noticed by Stembridge [35]. One step towards proving the real-rootedness of P (D_{n}, x) is to learn more about the relationships between the zeros of P (B_{n}, x) and P (A_{n}, x).

Brenti [9] introduced a q-analog of P (B_{n}, x)

B_{n}(x; q) = ∑_{σ∈B_{n}} q^{N(σ)}x^{d_{B}(σ)},  (6.2)

where d_{B}(σ) is the number of B_{n}-descents of σ and N(σ) is the number of negative entries of σ, see [9]. He proved that

∑_{i≥0}((1 + q)i + 1)^{n}x^{i} = \frac{B_{n}(x; q)}{(1 − x)^{n+1}} ,  (6.3)

and that B_{n}(x; q) is real- and simple-rooted for all q ≥ 0. Suppose that f(i) is a polynomial in i of degree d, then the polynomial W (f) is defined by

∑_{i≥0} f(i)x^{i} = \frac{W (f)(x)}{(1 − x)^{d+1}} ,

One can show, see [7], that E(f) and W (f) are related by:

E(f)(x) = (1 + x)^{deg(f)}W (f)(\frac{x}{1 + x}).  (6.4)

It follows that W (f) has only real non-positive roots if and only if E(f) is [−1, 0]-rooted. Since ((1 + q)i + 1)^{n} is a [−1, 0]-rooted polynomial in i for any q ≥ 0 it follows from e.g. Theorem 4.2 that B_{n}(x; q) is real-rooted in x for any fixed q ≥ 0. It is natural to generalize B_{n}(x; q) to have n+1 parameters as B_{n}(x; q) := W ( ∏_{i=0}^{n} ((1+q_{i})x+1)). This polynomial has a nice combinatorial interpretation:

Theorem 6.4. For all n ∈ ℕ we have:

B_{n}(x, q) = ∑_{σ∈B_{n}} q_{1}^{χ_{1}(σ)}q_{2}^{χ_{2}(σ)} ⋯ q_{n}^{χ_{n}(σ)}t^{d_{B}(σ)},

where

χ_{i}(σ) = \begin{cases}1 if σ_{i} < 0, \\ 0 if σ_{i} > 0. \end{cases}

Proof. The proof is an obvious generalization of the proof of Theorem 3.4 of [9]. □

Note that this theorem gives a semi-combinatorial interpretation of the W -transform of any [−1, 0)-rooted polynomial.

Corollary 6.5. Let n ∈ ℕ and let q_{1}, q_{2}, …, q_{n} be non-negative real numbers. Then B_{n}(x; q) has only real and simple zeros.

We need the following lemma on the degree of W (f).

Lemma 6.6. Let f ∈ ℝ[x]. Then

deg W (f) = deg f − mult(−1, E(f)).

Moreover, mult(−1, E(f)) is equal to the maximal integer k such that (x + 1)(x + 2) ⋯ (x + k) divides f.

Proof. Since deg E(f) = deg f for all f we have by (6.4) that deg W (f) = deg f − mult(−1, E(f)). If we expand f in the basis \{\binom{−x−1}{i}\} as:

f(x) = ∑_{i≥0}(−1)^{i}a_{i}\binom{−x − 1}{i},
= ∑_{i≥0} \frac{a_{i}}{i!} (x + 1) ⋯ (x + i),

we have by Lemma 4.3 that

E(f)(x) = ∑_{i≥0} a_{i}(x + 1)^{i},

and the lemma follows. □

We now have more precise knowledge of the location of the zeros of B_{n}(x; q) for any given q ≥ 0.

Theorem 6.7. Let 0 < q < t ∈ ℝ and n > 0 be an integer. Then

B_{n}(x; 0) ⪯ B_{n}(x; t) ≪ B_{n}(x; q) ≪ xB_{n}(x; 0),

where the three first polynomials have no common zeros.

Proof. Let 0 < r < s < 1. Then by the proof of Lemma 4.4 we have

E(x^{n}) ≪ E(x(x+r)^{n−1}) ≪_{strict} E((x+r)^{n}) ≪_{strict} E((x+r)^{n−1}(x+s)) ≪

E((x + s)^{n}) ≪_{strict} E((x + s)^{n−1}(x + 1)) ≪ E((x + 1)^{n}),

where ≪_{strict} means strictly alternating left of. Since (x + 1)E(x^{n}) = xE((x + 1)^{n}) this implies

E(x^{n}) ≪_{strict} E((x + r)^{n}) ≪_{strict} E((x + s)^{n}) ≪_{strict} E((x + 1)^{n}).

Now since

B_{n}(x; q) = (q+1)^{n}W ((x+\frac{1}{1 + q})^{n}) = (q+1)^{n}(1−x)^{n}E((x+\frac{1}{1 + q})^{n})(\frac{x}{1 − x}),

we see by Lemma 6.6 that deg B_{n}(x; 0) = n − 1 and deg B_{n}(x; q) = n if q ≠ 0. Moreover, the alternating property is preserved under the operation (6.4) and the theorem follows. □

It follows from (6.2) that P (B_{n}, x) = B_{n}(x; 1) and P (A_{n}, x) = B_{n}(x; 0).

Corollary 6.8. For all integers n ≥ 1 we have that P (A_{n}, x) strictly interlaces P (B_{n}, x).

Since P (A_{n}, x) ≪ xP (A_{n−1}, x) and P (A_{n}, x) ⪯ P (B_{n}, x), we have by Lemma 2.2 that for all t ≥ 0 the polynomial P (B_{n}, x) + txP (A_{n−1}, x) is real-rooted. Unfortunately a similar argument does not apply when t < 0.

One can extract more from (6.3). Brenti [9] proved that the polynomial

∑_{σ∈B_{n},N(σ)∈{k,n−k}} x^{d_{B}(σ)},

is real-rooted for all choices of 0 ≤ k ≤ n. Using Theorem 4.6 we can extend this result to:

Corollary 6.9. Let S be any subset of [0, n]. Then the polynomial

P (B_{n}, S; x) := ∑_{σ∈B_{n},N(σ)∈S} x^{d_{B}(σ)},

has only real and simple zeros.

Proof. Comparing the coefficient of q^{i} in both sides of (6.3) we see that P (B_{n}, S; x) = W (f_{n}(S; x)) where

f_{n}(S; x) = ∑_{s∈S} \binom{n}{s}x^{s}(x + 1)^{n−s}.

So the theorem follows from Theorem 4.2. □

One instance of Theorem 6.9 is particularly interesting. Recall that a Coxeter group of type D_{n} is isomorphic to the subgroup

D_{n} = {σ ∈ B_{n} : 2 | N(σ)}

Hence, we have the following corollary

Corollary 6.10. For all n ∈ ℕ the polynomial

∑_{σ∈D_{n}} x^{d_{B}(σ)}

has only real and simple zeros.

Note that the above polynomial is not P (D_{n}, x), since B_{n}-descents and D_{n}-descents are not the same.

7. The h-vector of a family of simplicial complexes defined by Fomin and Zelevinsky

Fomin and Zelevinsky [18] recently associated to any finite Weyl group W a simplicial complex Δ_{F Z}(W). For the classical Weyl groups these polynomials are given by

h(Δ_{F Z}(A_{n−1}), x) = \frac{1}{n} ∑_{k=0}^{n−1} \binom{n}{k}\binom{n}{k + 1}x^{k},

h(Δ_{F Z}(B_{n}), x) = ∑_{k=0}^{n} \binom{n}{k}\binom{n}{k}x^{k},
h(Δ_{F Z}(D_{n}), x) = h(Δ_{F Z}(B_{n}), x) − nxh(Δ_{F Z}(A_{n−2}), x).

It is known that the h-polynomials corresponding to A_{n} and B_{n} have only real zeros. We will here show that so has h(Δ_{F Z}(D_{n}), x).

Theorem 7.1. Let α, β ∈ ℝ be such that α ≥ 0, 2α + β > 0 and let n ≥ 2 be an integer. Then the polynomial

F_{n}(α, β) := αh(Δ_{F Z}(B_{n}), x) + βnxh(Δ_{F Z}(A_{n−2}), x),

is real- and simple-rooted. Moreover, h(Δ_{F Z}(B_{n−1}), x) strictly interlaces F_{n}(α, β) if α > 0 and strictly alternates left of F_{n}(α, β) if α = 0.

Corollary 7.2. Let W be a finite Weyl group. Then h(Δ_{F Z}(W), x) has only real and simple zeros. For the classical Weyl groups we have the following relationships:

h(Δ_{F Z}(A_{n−1}), x) ⪯ h(Δ_{F Z}(A_{n}), x),
h(Δ_{F Z}(B_{n−1}), x) ⪯ h(Δ_{F Z}(B_{n}), x),
h(Δ_{F Z}(B_{n−1}), x) ⪯ h(Δ_{F Z}(D_{n}), x),
h(Δ_{F Z}(A_{n−1}), x) ⪯ h(Δ_{F Z}(B_{n}), x),

where the interlacing is strict.

Proof. For the exceptional Weyl group one can check the real-rootedness ad hoc, see [30]. That {h(Δ_{F Z}(A_{n}), x)}_{n≥0} form a Sturm sequence is proved in [6]. The other cases follows from Theorem 7.1. □

The Hadamard product of two polynomials

p(x) = a_{0} + a_{1}x + ⋯ + a_{m}x^{m}
q(x) = b_{0} + b_{1}x + ⋯ + b_{n}x^{n}

is the polynomial

(p ⋆ q)(x) = a_{0}b_{0} + a_{1}b_{1}x + ⋯ + a_{N}b_{N}x^{N},

where N = min(m, n). Málo proved that if the zeros of p are real and the zeros of q are real and of the same sign then the zeros of p ⋆ q are real as well. This also follows from Theorem 3.8 since p ⋆ q = Γ[pSq] where Γ is the multiplier sequence \{\frac{1}{k!}\}_{k=0}^{∞}. It is known, see e.g. [19], that if f has only real zeros then all zeros of Γ[f] are real and simple except for possibly at the origin.

Proof of Theorem 7.1. Let F_{n}(α, β) = αh(Δ_{F Z}(B_{n}), x)+βnxh(Δ_{F Z}(A_{n−2}), x). We may write F_{n}(α, β) as

F_{n}(α, β) = α(x + 1)^{n} ⋆ (x + 1)^{n} + β(x(x + 1)^{n−1}) ⋆ (x + 1)^{n−1},

where the first summand can be written as

(x + 1)((x + 1)^{n−1} ⋆ (x + 1)^{n−1}) + 2(x(x + 1)^{n−1}) ⋆ (x + 1)^{n−1}.

Thus F_{n}(α, β) = α(x+1)f +(2α+β)g where f = (x+1)^{n−1} ⋆(x+1)^{n−1} and g = (x(x + 1)^{n−1}) ⋆ (x + 1)^{n−1}. By the discussion before this proof we have that for all real choices of γ, δ ∈ ℝ the polynomial

γf + δg = ((γ + δx)(x + 1)^{n−1}) ⋆ (x + 1)^{n−1},

is real- and simple-rooted. By the Obreschkoff theorem we infer that f strictly alternates left of g. Now, since f ⪯ (x + 1)f and f ≪ g we know by Lemma 2.2 that f either interlaces or alternates left of F_{n}(α, β) for all α, β ∈ ℝ such that sgn(α) = sgn(2α + β). Moreover, since g and f have no common zeros nor does F_{n}(α, β) and f (provided that 2α + β ≠ 0). □

8. Two bilinear forms

There are a few bilinear forms on polynomials that occur frequently in combinatorics. Let # : ℝ[x] × ℝ[x] → ℝ[x] be defined by

(f#g)(x) := ∑_{k≥0} f^{(k)}(x)g^{(k)}(x)\frac{x^{k}}{k!} .

This product is important when analyzing how the the zeros of σpolynomials behave under disjoint union of graphs, see [11].

Theorem 8.1. Let f be real-rooted and let g have only real zeros of the same sign. Then f#g is real-rooted.

Proof. The theorem follows from Theorem 3.11, since {1}_{k=0}^{∞} is trivially a multiplier-sequence. □

This generalizes a result of Wagner, who proved that f#g is realrooted whenever f and g have only non-negative zeros, see [11, 37].

Recall the definition, (4.2), of the diamond product. This product is important in the theory of (P, ω)-partitions and the Neggers-Stanley conjecture, see [38]. Applying Theorem 3.11 with the multiplier-sequence \{\frac{1}{k!}\}_{k≥0} we get:

Theorem 8.2. Let f be real-rooted and let g have all zeros in the interval [−1, 0]. Then f ⋄ g is real-rooted.

This was first proved by Wagner [39] under the additional hypothesis that f has all zeros in [−1, 0], and generalized by the present author in Acknowledgments. The author would like to thank Francesco Brenti for interesting discussions and helpful suggestions on the topic of this paper during the authors stay at Universitá di Roma “Tor Vergata”.

References

[1] M. Bóna. Corrigendum: “Symmetry and unimodality in t-stack sortable permutations”. J. Combin. Theory Ser. A, 99(1):191–194, 2002.

[2] M. Bóna. A survey of stack-sorting disciplines. Electron. J. Combin., 9(2), 2002.

[3] M. Bóna. Symmetry and unimodality in t-stack sortable permutations. J. Combin. Theory Ser. A, 98(1):201–209, 2002.

[4] M. Bousquet-Mélou. Multi-statistic enumeration of two-stack sortable permutations. Electron. J. Combin., 5(1):Research Paper 21, 12 pp. (electronic), 1998.

[5] P. Brändén. On operators on polynomials preserving real-rootedness and the Neggers-Stanley conjecture. J.Algebraic Comb., to appear.

[6] P. Brändén. The generating function of two-stack sortable permutations by descents is real-rooted. preprint: arXiv:math.CO/0303149.

[7] F. Brenti. Unimodal, log-concave and Pólya frequency sequences in combinatorics. Mem. Amer. Math. Soc., 81(413):viii+106, 1989.

[8] F. Brenti. Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update. In Jerusalem combinatorics ’93, volume 178 of Contemp. Math., pages 71–89. Amer. Math. Soc., Providence, RI, 1994.

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

[10] F. Brenti. A class of q-symmetric functions arising from plethysm. J. Combin. Theory Ser. A, 91(1-2):137–170, 2000.

[11] F. Brenti, G. F. Royle, and D. G. Wagner. Location of zeros of chromatic and related polynomials of graphs. Canad. J. Math., 46(1):55–80, 1994.

[12] L. Comtet. Advanced combinatorics. D. Reidel Publishing Co., Dordrecht, enlarged edition, 1974. The art of finite and infinite expansions.

[13] T. Craven and G. Csordas. Multiplier sequences for fields. Illinois J. Math., 21(4):801–817, 1977.

[14] J. Dedieu. Obreschkoff’s theorem revisited: what convex sets are contained in the set of hyperbolic polynomials? J. Pure Appl. Algebra, 81(3):269–278, 1992.

[15] S. Dulucq, S. Gire, and O. Guibert. A combinatorial proof of J. West’s conjecture. Discrete Math., 187(1-3):71–96, 1998.

[16] A. Edrei. On the generating functions of totally positive sequences. II. J. Analyse Math., 2:104–109, 1952.

[17] D. Foata and M. Schützenberger. Théorie géométrique des polynômes eulériens. Lecture Notes in Mathematics, Vol. 138. Springer-Verlag, Berlin, 1970.

[18] S.V. Fomin and A.V. Zelevinsky. Y-systems and generalized associahedra. Ann. of Math., 158(158):977–1018, 2003.

[19] J. Garloff and D. G. Wagner. Hadamard products of stable polynomials are stable. J. Math. Anal. Appl., 202(3):797–809, 1996.

[20] I. P. Goulden and J. West. Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations. J. Combin. Theory Ser. A, 75(2):220–242, 1996.

[21] G. H. Hardy, J. E. Littlewood, and G. Pólya. Inequalities. Cambridge, at the University Press, 1952. 2d ed.

[22] O. J. Heilmann and E. H. Lieb. Theory of monomer-dimer systems. Comm. Math. Phys., 25:190–232, 1972.

[23] B. Jacquard and G. Schaeffer. A bijective census of nonseparable planar maps. J. Combin. Theory Ser. A, 83(1):1–20, 1998.

[24] S. Karlin. Total positivity. Vol. I. Stanford University Press, Stanford, Calif, 1968.

[25] M. Marden. Geometry of polynomials. Second edition. Mathematical Surveys, No. 3. American Mathematical Society, Providence, R.I., 1966.

[26] N. Obreschkoff. Verteilung und Berechnung der Nullstellen reeller Polynome. VEB Deutscher Verlag der Wissenschaften, Berlin, 1963.

[27] G. Pólya. Collected papers. The MIT Press, Cambridge, Mass.-London, 1974. Vol. II: Location of zeros, Edited by R. P. Boas, Mathematicians of Our Time, Vol. 8.

[28] E. D. Rainville. Special functions. The Macmillan Co., New York, 1960.

[29] V. Reiner. Descents and one-dimensional characters for classical Weyl groups. Discrete Math., 140(1-3):129–140, 1995.

[30] V. Reiner and V. Welker. On the Charney-Davis and the Neggers-Stanley conjectures. http://www.math.umn.edu/˜ reiner/Papers/papers.html, 2002.

[31] J. Schur. Zwei sätze über algebraische gleichungen mit lauter reellen wurzeln. J. Reine Angew. Math., 144(2):75–88, 1914.

[32] R. P. Stanley. Log-concave and unimodal sequences in algebra, combinatorics, and geometry. In Graph theory and its applications: East and West (Jinan, 1986), volume 576 of Ann. New York Acad. Sci., pages 500–535. New York Acad. Sci., New York, 1989.

[33] R. P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.

[34] R. P. Stanley. Positivity problems and conjectures in algebraic combinatorics. In Mathematics: frontiers and perspectives, pages 295–319. Amer. Math. Soc., Providence, RI, 2000.

[35] J. R. Stembridge. Some permutation representations of Weyl groups associated with the cohomology of toric varieties. Adv. Math., 106(2):244–301, 1994.

[36] R. A. Sulanke. The Narayana distribution. J. Statist. Plann. Inference, 101(1-2):311–326, 2002. Special issue on lattice path combinatorics and applications (Vienna, 1998).

[37] D. G. Wagner. The partition polynomial of a finite set system. J. Combin. Theory Ser. A, 56(1):138–159, 1991.

[38] D. G. Wagner. Enumeration of functions from posets to chains. European J. Combin., 13(4):313–324, 1992.

[39] D. G. Wagner. Total positivity of Hadamard products. J. Math. Anal. Appl., 163(2):459–483, 1992.

Matematik, Chalmers tekniska högskola och Göteborgs universitet, S-412 96 Göteborg, Sweden

E-mail address: branden@math.chalmers.se