Unimodal Polynomials arising from symmetric functions

by

Francesco Brenti Department of Mathematics University of Michigan Ann Arbor, Michigan 48109-1003

Abstract We present a general result that, using the theory of symmetric functions, produces several new classes of symmetric unimodal polynomials. The result has applications to enumerative combinatorics including the proof of a conjecture by R. Stanley.

1 Introduction

A sequence of real numbers a_{0}, a_{1}, …, a_{d} is said to be symmetric if a_{i} = a_{d−i} for i = 0, …, ⌊\frac{d}{2}⌋ and is said to be unimodal if there exists an index 0 ≤ j ≤ d such that a_{1} ≤ a_{2} ≤ … ≤ a_{j−1} ≤ a_{j} ≥ a_{j+1} ≥ … ≥ a_{d}. A polynomial ∑_{i=0}^{d} a_{i}x^{i} ∈ R[x] is called symmetric (respectively, unimodal ) if the sequence {a_{0}, …, a_{d}} has the corresponding property.

Unimodal polynomials arise often in combinatorics, geometry, and algebra and have been the subject of considerable research in recent years. Many different fields of mathematics have been used to prove that certain families of polynomials are unimodal such as, for example, classical analysis (see, e.g., [14], [22]), linear algebra (see, e.g., [10], [11]), the representation theory of Lie algebras and superalgebras (see, e.g., [12], [16], [17]), algebraic geometry (see, e.g., [19], [20]), the theory of total positivity ( see, e.g., [2], [3]), the theory of symmetric functions ( see, e.g., [4]), as well as the use of bijections and injections (see, e.g., [13]). We refer the reader to [20] for an excellent survey of many of these techniques and further references.

In this paper we also use the theory of symmetric functions to prove a general result (Theorem 2, below) that produces many new infinite families of symmetric unimodal polynomials. The result has a wide applicability, in particular, a conjecture and a result of R. Stanley both follow as specializations of it.

For brevity reasons, we will call a nonzero polynomial a Λ-polynomial if it has nonnegative coefficients and is both symmetric and unimodal. Note that we require a Λ-polynomial to be nonzero. If p (x) is a Λ-polynomial then there is a unique n ∈ N such that x^{n} p (\frac{1}{x}) = p (x). We call the number \frac{n}{2} the center of symmetry of p (x), and we write C(p) = \frac{n}{2}. So, for example, C(x^{2} + 3x^{3} + x^{4}) = 3 and C(1 + x) = \frac{1}{2}. An elementary, though crucial property of Λ-polynomials, which will be used repeatedly in this paper, is the following. Theorem 1: Let p (x) and q(x) be two Λ-polynomials. Then p (x) q(x) is a Λpolynomial and C(p q) = C(p) + C(q).

Theorem 1 is well known and a proof of it can be found, e. g., in [20], Prop.1.2, or in [1].

2 The main result

Let x_{1}, x_{2}, x_{3}, … be independent variables, and let R[[x_{1}, x_{2}, …]] be the ring of formal power series in x_{1}, x_{2}, x_{3}, … with coefficients in R, where R is a commutative ring with identity (we refer the reader to [8] for the definition and the basic properties of R[[x_{1}, x_{2}, …]]). An element p ∈ R[[x_{1}, x_{2}, …]] is called symmetric if p (x_{σ(1)}, x_{σ(2)}, …) = p (x_{1}, x_{2}, …) for all bijections σ : P → P (where P =^{def} {1, 2, 3, …}), and is said to be bounded if there is a constant M such that all the monomials appearing in p have degree ≤ M. We let

Λ̂_{R} =^{def} {p ∈ R[[x_{1}, x_{2}, …]] ; p is symmetric },

and

Λ_{R} =^{def} {p ∈ Λ̂_{R} , p is bounded};

then Λ_{R} and Λ̂_{R} are subrings of R[[x_{1}, x_{2}, …]] and Λ_{R} ⊂ Λ̂_{R}. We call Λ̂_{R} the ring of symmetric formal power series and Λ_{R} the ring of symmetric functions , with coefficients in R. Note that Λ_{R}_{≠}^{⊂}Λ̂_{R} since, for example, ∏_{i≥1}(1 + x_{i}) ∈ Λ̂_{R} \ Λ_{R}.

We will follow Chap.I of [9] for symmetric function notation and terminology. In particular, we will denote by s_{λ} (respectively, h_{λ}, e_{λ}, m_{λ}, and p_{λ}) the Schur (respectively, complete homogeneous, elementary, monomial, and power sum ) symmetric functions, associated to the partition λ. We also denote by P the set of all partitions, and by ΛQ^{n} the subspace of all elements of Λ_{Q} that are homogeneous

of degree n. If λ = (λ_{1} ≥ λ_{2} ≥ … ≥ λ_{l} > 0) ∈ P then we let |λ| =^{def} ∑_{i=1}^{l}λ_{i}, and we also write λ ⊢ n if n = |λ|. We call a basis {a_{λ}}_{λ∈P} of Λ_{Q} standard if, for all n ∈ N, {a_{λ} : λ ⊢ n} is a basis of ΛQ^{n}. Note that a standard basis {a_{λ}}_{λ∈P} is homogeneous and that deg (a_{λ}) = |λ|.

We now come to the crucial definition of this paper. We say that an ordered triple ({a_{λ}}_{λ∈P} , {b_{λ}}_{λ∈P} , {c_{λ}}_{λ∈P}) of standard bases of Λ_{Q} is compatible if:

(i) if c_{λ} = ∑_{μ} f_{λ μ} a_{μ} then f_{λ μ} ≥ 0, for all λ , μ ∈ P;

(ii) if a_{λ} b_{μ} = ∑_{ν} g_{λ μ}^{ν} a_{ν} then g_{λ μ}^{ν} ≥ 0, for all λ , μ , ν ∈ P.

Conditions (i) and (ii) above are very mild and often automatically satisfied. In fact, we have the following result. Proposition 1: The ordered triple ({a_{λ}}_{λ∈P} , {b_{λ}}_{λ∈P} , {c_{λ}}_{λ∈P}) is compatible in each of the following cases:

(i) a_{λ} = b_{λ} = c_{λ} ∈ {m_{λ} , e_{λ} , h_{λ} , s_{λ} , p_{λ}};

(ii) a_{λ} = m_{λ} , and b_{λ} = c_{λ} ∈ {m_{λ} , e_{λ} , h_{λ} , s_{λ} , p_{λ}};

(iii) a_{λ} = p_{λ} , and b_{λ} , c_{λ} ∈ {p_{λ} , h_{λ}};

(iv) a_{λ} = s_{λ} , and b_{λ} , c_{λ} ∈ {e_{λ} , h_{λ} , s_{λ}}.

The proof of the preceding Proposition follows immediately from the results in Chap.1, §6 of [9] and from our definitions, and is therefore omitted.

We are now in a position to state and prove the main result of this paper. Theorem 2: Let {r_{μ}(q)}_{μ∈S} , {u_{ν}(q)}_{ν∈T} be two families of Λ-polynomials, where S, T ⊆ P and (0) ∉ S. Suppose that there exists n, k ∈ Z such that

C(r_{μ}) = \frac{n |μ|}{2} , C(u_{ν}) = \frac{n |ν| + k}{2} ,

for all μ ∈ S, ν ∈ T. For ρ ∈ P, define a polynomial R_{ρ}(q) by

∑_{ρ∈P} R_{ρ}(q)a_{ρ} = \frac{∑_{ν∈T}u_{ν}(q)c_{ν}}{1 − ∑_{μ∈S}r_{μ}(q)b_{μ}} ,  (1)

where ({a_{λ}}_{λ∈P} , {b_{λ}}_{λ∈P} , {c_{λ}}_{λ∈P}) is a compatible triple of standard bases of Λ_{Q}. Then R_{ρ}(q) is a Λ-polynomial and C(R_{ρ}) = \frac{n|ρ|+k}{2}. Proof: Note first that the symmetric formal power series 1 − ∑_{μ∈S}r_{μ}(q) b_{μ} is an

invertible element of Q[q][[x_{1}, x_{2}, …]] and that, therefore, the expression on the RHS of (1) is a well defined element of Λ̂_{Q[q]}. Now let

c_{ν} = ∑_{λ∈P} f_{ν λ} a_{λ} ,  (2)

and

a_{ρ} b_{μ} = ∑_{λ} g_{ρ μ}^{λ} a_{λ} .  (3)

From our hypotheses and definitions there then follows that f_{ν λ} = 0 unless |ν| = |λ|, g_{ρ μ}^{λ} = 0 unless |λ| = |ρ| + |μ|, and

f_{ν λ} ≥ 0 , g_{ρ μ}^{λ} ≥ 0

for all ν, λ, ρ, μ ∈ P. Rewrite now (1) as

∑_{ρ∈P} R_{ρ}(q)a_{ρ} − ∑_{ρ∈P} ∑_{μ∈S} R_{ρ}(q)r_{μ}(q)a_{ρ}b_{μ} = ∑_{ν∈T} u_{ν}(q)c_{ν} ,  (4)

Substituting (2) and (3) in (4) and then equating the coefficients of a_{λ} on both sides we obtain that

\{ \begin{matrix}R_{λ}(q) = ∑_{ρ∈P} ∑_{μ∈S}R_{ρ}(q)r_{μ}(q)g_{ρ μ}^{λ} + ∑_{ν∈T}u_{ν}(q)f_{ν λ} & if λ ≠ 0, \\ R_{(0)}(q) = f_{(0)(0)} u_{(0)}(q). \end{matrix}  (5)

We now proceed by induction on |λ|. The thesis is clearly true if |λ| = 0. So fix λ ∈ P with |λ| ≥ 1 and assume that the thesis holds for all partitions such that |ρ| < |λ|. Since (0) ∉ S we have that |ρ| < |λ| and hence, by our induction hypothesis, that R_{ρ}(x) is a Λ-polynomial and C(R_{ρ}) = \frac{n|ρ|+k}{2}, for all partitions ρ appearing in the first sum on the RHS of (5). But, by hypothesis, r_{μ}(x) is a Λpolynomial and C(r_{μ}) = \frac{n |μ|}{2} for all μ ∈ S. Therefore, by Theorem 1, R_{ρ}(x) r_{μ}(x) is a Λ-polynomial and

C(R_{ρ} r_{μ}) = \frac{n (|ρ| + |μ|) + k}{2}
= \frac{n |λ| + k}{2}

for all ρ and μ appearing in the first sum on the RHS of (5). On the other hand, by our assumptions, all polynomials u_{ν}(x) f_{ν λ} appearing in the second sum on the RHS of (5) are also Λ-polynomials and

C(u_{ν}(x) f_{ν λ}) = \frac{n |ν| + k}{2}
= \frac{n |λ| + k}{2} .

So all polynomials on the RHS of (5) are Λ-polynomials with center of symmetry equal to \frac{n |λ|+k}{2}. Therefore their sum, R_{λ}(x), is also a Λ-polynomial with the same center of symmetry, as desired. This concludes the induction step and hence the proof.□

It may seem that Theorem 2 should be of limited use because it produces only one sequence of Λ-polynomials starting with two such sequences. However, as will be seen in the next section, in many applications the sequence {R_{λ}(q)}_{λ∈P} is much more complicated than the two starting sequences {u_{ν}(q)}_{ν∈T} and {r_{μ}(q)}_{μ∈S}.

3 Applications

Our first application of Theorem 2 is the following. Proposition 2: For each partition λ define a polynomial R_{λ}(q) by

∑_{λ} R_{λ}(q) s_{λ} = \frac{1}{1 − ∑_{k≥2}(q + q^{2} + … + q^{k−1}) s_{k}}  (6)

Then R_{λ}(q) is a Λ-polynomial and C(R_{λ}) = \frac{|λ|}{2}. Proof: Take a_{λ} = b_{λ} = c_{λ} = s_{λ} for λ ∈ P and let S =^{def} {(k) : k ≥ 2}, r_{μ}(x) =^{def} q + q^{2} + … + q^{|μ|−1} if μ ∈ S, T =^{def} {(0)}, μ_{(0)}(x) =^{def} 1. Then all the hypotheses of Theorem 2 are satisfied with n = 1 and k = 0, and the result follows.□

Proposition 2 verifies a conjecture of R. Stanley (see the remarks preceding Prop.7.8 in [20]).

Our second application is closely related to the previous one. Proposition 3: For each partition λ, define a polynomial T_{λ}(q) by

∑_{λ} T_{λ}(q) s_{λ} = \frac{∑_{k≥1}(1 + q + … + q^{k−1}) s_{k}}{1 − ∑_{k≥2}(q + q^{2} + … + q^{k−1}) s_{k}} .  (7)

Then T_{λ}(q) is a Λ-polynomial and C(T_{λ}) = \frac{|λ|−1}{2}. Proof: Take a_{λ}, b_{λ}, c_{λ}, S and r_{μ}(q) as in the proof of Proposition 2 and let T =^{def} {(k) : k ≥ 1}, u_{ν}(q) =^{def} 1 + q + q^{2} + … + q^{|ν|−1} if ν ∈ T. Then all the hypotheses of Theorem 2 are satisfied with n = 1 and k = −1 and the result follows.□

Proposition 3 is equivalent to a result of R. Stanley (see Prop.7.7 in [20]). However, our proof only uses standard results from the theory of symmetric functions while the sketch of proof given in [20] uses techniques from the theory of representations of the symmetric group and from algebraic geometry. To see that the two results are equivalent just observe that

\frac{∑_{k≥1}(1 + q + … + q^{k−1}) s_{k}}{1 − ∑_{k≥2}(q + q^{2} + … + q^{k−1}) s_{k}} + 1 = \frac{∑_{k≥0}s_{k}}{1 − ∑_{k≥2}(q + q^{2} + … + q^{k−1}) s_{k}} ,

which is the definition used in Prop.7.7. of [20].

4 Combinatorial consequences

In this section we look at some combinatorial properties of the polynomials studied in the last section. Following [7], §3, we define a map R : Λ_{Q[q]} → Q[q][[t]] by

R(p) =^{def} ∑_{n≥0}[x_{1} … x_{n}](p)\frac{t^{n}}{n!}  (8)

where p ∈ Λ and [x_{1} … x_{n}](p) denotes the coefficient of x_{1} … x_{n} in p, (where ∏_{i=1}^{n}x_{i} =^{def} 1 if n = 0). It is then easy to see that R is a ring homomorphism. Also, from the combinatorial interpretation of the Schur functions (see, e.g., [9], eq.(5.12), p. 42 or [15]) it follows immediately that, for any partition λ,

R(s_{λ}) = f^{λ} \frac{t^{|λ|}}{|λ|!}  (9)

where f^{λ} denotes the number of standard tableaux of shape λ (see, e.g., [9], p.5 for the definition of a standard tableau).

We may now prove the following result. Proposition 4: Let T_{λ}(q) be the polynomials defined in Proposition 3. Then, for n ∈ P,

∑_{λ⊢n} f^{λ} T_{λ}(q) = \frac{1}{q} A_{n}(q) ,  (10)

where A_{n}(q) is the n-th Eulerian polynomial. Proof: Multiplying both sides of (7) by q and then adding 1 gives

1 + ∑_{λ∈P} q T_{λ}(q) s_{λ} = \frac{1 + qt + ∑_{k≥2}q^{k} s_{k}}{1 − ∑_{k≥2}(q + q^{2} + … + q^{k−1}) s_{k}} ,

applying now R on both sides and using (8) and (9) we obtain

1 + ∑_{λ∈P} q T_{λ}(q) f^{λ} \frac{t^{|λ|}}{|λ|!} = \frac{e^{qt}}{1 − \frac{1}{1−q}(qe^{t} − q − e^{qt} + 1)}
= \frac{(1 − q) e^{qt}}{e^{qt} − qe^{t}}
= ∑_{n≥0} A_{n}(q) \frac{t^{n}}{n!}

where, in the last equality, we have used a well known generating function for Eulerian polynomials (see, e.g., eq.(5i) on p.244 of [5]). Equating now the coefficients of t^{n} yields (10), as desired.□

Note that, by Proposition 3, the preceding result gives yet another proof of the well known fact that the Eulerian polynomials are symmetric and unimodal.

Let now n ∈ P and σ ∈ S_{n} (where S_{n} is the symmetric group on n elements). An element i ∈ [n] (where [n] =^{def} {1, 2, …, n}) is called an excedance of σ if σ(i) > i, we denote the number of excedances of σ by e(σ). The permutation σ ∈ S_{n} is called a derangement if σ(i) ≠ i for i = 1, 2, …, n (i.e., σ has no fixed points). We denote the set of all derangements of S_{n} by D_{n}. We define polynomials d_{n}(q) by

d_{n}(q) =^{def} ∑_{σ∈D_{n}} q^{e(σ)} ,  (11)

for n ∈ P ( so that d_{1}(q) = 0), we also let d_{0}(q) =^{def} 1. Since d_{n}(1) = |D_{n}| we may consider d_{n}(q) as a q-analogue of the derangement numbers. These are different, however, from other q-derangement numbers that have been previously considered in the literature ( see, e.g., [6], [21]).

It is not hard to write down the exponential generating function for the polynomials d_{n}(q). Proposition 5: Let d_{n}(q) be the polynomials defined by (11), then

∑_{n≥0} d_{n}(q) \frac{t^{n}}{n!} = \frac{1 − q}{e^{tq} − q e^{t}} .

Proof : It is well known (see, e.g., [18], Prop.1.3.12) that A_{n}(q) = ∑_{σ∈S_{n}} q^{e(σ)+1}. Therefore, for n ∈ P, we have that

\frac{1}{q} A_{n}(q) = ∑_{S⊆[n]} ∑_{σ∈D_{|S|}}q^{e(σ)}
= ∑_{i=0}^{n} \binom{n}{i} d_{i}(q) .

There follows that

q e^{t} ∑_{n≥0} d_{n}(q)\frac{t^{n}}{n!} = ∑_{n≥0} A_{n}(q)\frac{t^{n}}{n!} + q − 1
= \frac{(1 − q)e^{qt}}{e^{qt} − q e^{t}} + (q − 1)
= \frac{(1 − q)q e^{t}}{e^{tq} − q e^{t}} ,

where in the last equality we have used again eq.(5i) on p.244 of [5], and the proof follows.□

We can now prove the following result. Proposition 6: Let R_{λ}(q) be the polynomials defined in Proposition 2. Then, for n ∈ N,

∑_{λ⊢n} f^{λ} R_{λ}(q) = d_{n}(q) .

Proof : Applying the homomorphism R defined by (8) to both sides of (6) yields

∑_{λ∈P} R_{λ}(q) f^{λ} \frac{t^{|λ|}}{|λ|!} = \frac{1}{1 − ∑_{k≥2}(q + q^{2} + … + q^{k−1})\frac{t^{k}}{k!}}

= \frac{1 − q}{e^{tq} − q e^{t}}
= ∑_{n≥0} d_{n}(q)\frac{t^{n}}{n!} ,

and the proof follows.□

By Proposition 2, the following is an immediate consequence of the previous result. Corollary 1: For n ∈ P, the polynomials d_{n}(q) defined by (11) are symmetric and unimodal.

It would be interesting to have a combinatorial proof of this result.

Even though the techniques presented in this paper cannot be used to prove it, we feel that the following stronger statement actually holds. Conjecture: For n ∈ P, the polynomials d_{n}(q) defined by (11) have only real zeros.

The conjecture has been verified for n ≤ 14. It is possible that the techniques used in [2] and [3] may be useful in attacking the above conjecture which, in fact, is closely related to one of the conjectures appearing in §3.4 of [2].

Given the results of Propositions 4 and 6 it is natural to ask for a combinatorial interpretation of the polynomials T_{λ}(q) and R_{λ}(q) themselves, a problem that had already been raised in [20]. Such a combinatorial interpretation has recently been found by J. Stembridge and will appear in a forthcoming paper of his. Acknowledgment. The author would like to thank Richard Stanley for some valuable suggestions in §4.

References

[1] G. E. Andrews, A theorem on reciprocal polynomials with applications to permutations and compositions, Amer. Math. Monthly 82(1975), 830-833.

[2] F. Brenti, Unimodal, Log-concave and Polya Frequency Sequences in Combinatorics, Ph.D. Thesis, June 1988, Massachusetts Institute of Technology.

[3] F. Brenti, Unimodal, Log-concave and Polya Frequency Sequences in Combinatorics, to appear in Memoirs Amer. Math. Soc..

[4] L. Butler, A unimodality result in the enumeration of subgroups of a finite abelian group, Proc. Amer. Math. Soc., 101(1987),771-775.

[5] L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974.

[6] A.M. Garsia and J. Remmel, A combinatorial interpretation of q-derangement and q-Laguerre numbers, Europ. J. Combinatorics, 1(1980),47-59.

[7] I. Gessel and G. Viennot, Determinants, paths, and plane partitions, preprint.

[8] I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley, New York, 1983.

[9] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, New York/London, 1979.

[10] R. Proctor, Representations of sl(2,C) on posets and the Sperner property, SIAM J. Algebraic Discrete Methods 3 (1982), 275-280.

[11] R. Proctor, Solution of two difficult combinatorial problems with linear algebra, Amer. Math. Monthly, 89 (1982), 721-734.

[12] R. Proctor, Bruhat lattices, plane partitions generating functions, and minuscule representations, Europ. J. Combinatorics, 5 (1984), 331-350.

[13] B. Sagan, Inductive and injective proofs of log concavity results, Discrete Math., 68 (1988), 281-292.

[14] R. Simion, A multiindexed Sturm sequence of polynomials and unimodality of certain combinatorial sequences, J. Combinatorial Theory(A), 36 (1984), 15-22.

[15] R. Stanley, Theory and application of plane partitions: Part 1, Studies Applied Math., 50(1971), 167-188.

[16] R. Stanley, Unimodal sequences arising from Lie algebras, in Young Day Proceedings T. V. Narayana, R. M. Mathsen, and J. G. Williams, eds., Dekker, New York/Basel, 1980, pp. 127-136.

[17] R. Stanley, Unimodality and Lie superalgebras, Studies in Applied Math. 72 (1985), 263-281.

[18] R. Stanley, Enumerative Combinatorics, vol.1, Wadsworth and Brooks/Cole, Monterey, CA, 1986.

[19] R. Stanley, Generalized h-vectors, intersection cohomology of toric varieties, and related results, Advanced Studies in Pure Math. 11 (1987), 187-213.

[20] R. Stanley, Log-concave and unimodal sequences in Algebra, Combinatorics and Geometry, to appear in Annals of the New York Academy of Sciences.

[21] M. Wachs, On q-derangement numbers, preprint.

[22] D. Wagner, The partition polynomial of a finite set system,preprint.