Hilbert polynomials in Combinatorics

Francesco Brenti^{1}

Abstract We prove that several polynomials naturally arising in combinatorics are Hilbert

polynomials of standard graded commutative k-algebras.

1 Introduction

The purpose of this paper is to investigate which polynomials naturally arising in combinatorics are Hilbert polynomials of standard graded (commutative) k-algebras. Our motivation comes from the fact (first proved by R. Stanley [34]) that the order polynomial of a partially ordered set is a Hilbert polynomial. Since Stanley informally told me of this result I have been wondering whether it was an isolated one or an instance of a more general phenomenon. Several works of Stanley (see, e.g., [31], [32], and the references cited there) show that many sequences arising in combinatorics are Hilbert functions, but Stanley never explicitly considered Hilbert polynomials.

In this paper we begin such a systematic investigation. Our results show that several polynomials arising in combinatorics are Hilbert polynomials, and in many (but not all) cases we find general reasons for this. The techniques that we use are based on combinatorial characterizations of Hilbert functions and polynomials obtained by Macaulay in 1927 ([24]). Though the characterization of Hilbert functions is very well known and has been extensively used since then, the one for Hilbert polynomials is not, and is our main tool. Most of our results are non-constructive. More precisely, we often prove that a given combinatorial polynomial is Hilbert but we are unable to construct (in a natural way) a standard graded k-algebra having the given Hilbert polynomial.

The organization of the paper is as follows. In the next section we collect several definitions, notation, and results that will be used in the rest of this work. In section 3 we develop a general theory of Hilbert polynomials. More precisely, using Macaulay’s result, and other techniques, we present several operations on polynomials that preserve the Hilbert property, as well as results that give sufficient conditions on the coefficients of a polynomial (when expanded in terms of several different bases) that insure that the polynomial is Hilbert. We also introduce a new concept, which is naturally suggested by one of our results, which gives a measure of “how far” a polynomial is from being Hilbert.

1This work was carried out while the author was a member of the Institute for Advanced Study in Princeton, New Jersey, U.S.A., and was partially supported by NSF grant DMS 9304580 and EC grant No. CHRX-CT93-0400.

In section 4 we apply the general theory developed in section 3 to polynomials arising in enumerative and algebraic combinatorics. In particular, we prove that the σ and τpolynomials of a graph, the zeta polynomial of a partially ordered set, the R-polynomial of two generic elements in a Coxeter system, the Kazhdan-Lusztig polynomials and the descent generating function of a finite Coxeter system, various generalizations of the Eulerian polynomials related to Stirling (multi)-permutations, Stirling polynomials, and several polynomials obtained by specializing certain symmetric functions, are all Hilbert polynomials (up to a shift by 1 in some cases). Finally, in section 5, we present several conjectures arising from the present work together with the evidence that we have in their support, and we indicate directions and open problems for further research.

2 Notation, definitions, and preliminaries

In this section we collect some definitions, notation and results that will be used in the rest of this paper. We let P =^{def} {1, 2, 3, …} , N =^{def}P ∪{0}, Z be the ring of integers, and Q be the field of rational numbers; for a ∈N we let [a] =^{def} {1, 2, …, a} (where [0] =^{def} ∅). Given n, m ∈ P, n ≤ m, we let [n, m] =^{def} [m] \ [n − 1]. The cardinality of a set A will be denoted by |A|. Given a polynomial P (x), and i ∈ Z, we will denote by [x^{i}](P (x)) the coefficient of x^{i} in P (x). For a ∈ R we let ⌊a⌋ (respectively, ⌈a⌉) denote the largest integer ≤ a (respectively, smallest integer ≥ a).

Given a ring R and a variable x we denote by R[[x]] the ring of formal power series in x with coefficients in R. For i ∈ P we let (x)_{i} =^{def} x(x − 1) … (x − i + 1), ⟨x⟩_{i} =^{def} x(x +

1) … (x+i−1), (\begin{matrix}x \\ i \end{matrix}) =^{def} \frac{(x)_{i}}{i!} , and ((\begin{matrix}x \\ i \end{matrix})) =^{def} \frac{⟨x⟩_{i}}{i!} . We also let (x)_{0} =^{def} ⟨x⟩_{0} =^{def} (\begin{matrix}x \\ 0 \end{matrix}) =^{def} ((\begin{matrix}x \\ 0 \end{matrix})) =^{def}

1. Note that, for d ∈ P, \{(x)_{i}\}_{i=0,...,d}, \{⟨x⟩_{i}\}_{i=0,...,d}, \{(\begin{matrix}x \\ i \end{matrix})\}_{i=0,...,d}, \{((\begin{matrix}x \\ i \end{matrix}))\}_{i=0,...,d} and

\{(\begin{matrix}x+d−i \\ d \end{matrix})\}_{i=0,...,d} are all bases of the real vector space V_{d} of real polynomials of degree ≤ d. We call the first four the bases of lower factorials, upper factorials, binomial coefficients, and twisted binomial coefficients, respectively.

A sequence {a_{0}, a_{1}, …, a_{d}} (of real numbers) is log-concave if a_{i}^{2} ≥ a_{i−1}a_{i+1} for i = 1, …, d − 1. It is unimodal if there exists an index 0 ≤ j ≤ d such that a_{i} ≤ a_{i+1} for i = 0, …, j − 1 and a_{i} ≥ a_{i+1} for i = j, …, d − 1. It has no internal zeros if there are not three indices 0 ≤ i < j < k ≤ d such that a_{i}, a_{k} ≠ 0 and a_{j} = 0. It is symmetric if a_{i} = a_{d−i} for i = 0, …, ⌊\frac{d}{2}⌋. A polynomial ∑_{i=0}^{d} a_{i} x^{i} is log-concave (respectively, unimodal, with no internal zeros, symmetric) if the sequence {a_{0}, a_{1}, …, a_{d}} has the corresponding property. It is well known that if ∑_{i=0}^{d} a_{i} x^{i} is a polynomial with nonnegative coefficients and with only real zeros, then the sequence {a_{0}, a_{1}, …, a_{d}} is log-concave and unimodal, with no internal zeros (see, e.g., [8], or [14], Thm. B, p.270).

We follow [33] for enumerative combinatorics notation and terminology. In particular, we denote by S(n, k) (respectively, c(n, k)) the Stirling numbers of the second kind (respectively, signless Stirling numbers of the first kind) for n, k ∈ N, and we follow Chapter 3 of [33] for notation and terminology related to the theory of partially ordered sets.

We follow [25], Chap.I, for notation and terminology related to partitions and symmetric functions. In particular, we denote by P the set of all (integer) partitions, and by Λ the ring of symmetric functions. Also, given λ ∈ P, we denote by λ′ its conjugate, and by s_{λ} (respectively e_{λ}, h_{λ}, p_{λ}, m_{λ}) the Schur (respectively elementary, complete homogeneous, power sum, monomial ) symmetric function associated to λ. We will usually identify a partition λ = (λ_{1}, …, λ_{r}) with its diagram {(i, j) ∈ P × P : 1 ≤ i ≤ r, 1 ≤ j ≤ λ_{i}}.

We follow [31] for notation and terminology concerning graded algebras and Hilbert functions. In particular, by a graded k-algebra (k being a field, fixed once and for all) we mean a commutative, associative ring R, with identity, containing a copy of the field k (so that R is a vector space over k) together with a collection of k-subspaces {R_{i}}_{i∈N} such that:

i) R = ⨁_{i≥0} R_{i} (as a k-vector space);

ii) R_{0} = k;

iii) R_{i}R_{j} ⊆ R_{i+j} for all i, j ∈ N;

iv) R is finitely generated as a k-algebra.

Note that this implies that each R_{i} is a finite dimensional vector space over k. The Hilbert series of R is the formal power series

P (R; x) =^{def} ∑_{i≥0} dim_{k}(R_{i})x^{i} .

The following fundamental result is well known, and a proof of it can be found, e.g., in [3], Theorem 11.1, or in [31], Theorem 8.

Theorem 2.1 Let R be a graded k-algebra as above. Then

P (R; x) = \frac{h(R; x)}{∏_{i=1}^{r}(1 − x^{k_{i}})} ,

in Z[[x]], where h(R; x) ∈ Z[x] and k_{1}, …, k_{r} are the degrees of a homogeneous generating set of R (as a k-algebra).

We call

H(R; i) =^{def} dim_{k}(R_{i})

the Hilbert function of R. We say that a k-algebra R as above is standard if it can be finitely generated (as a k-algebra) by elements of R_{1}. From now on we will always assume that all our graded k-algebras are standard. If R is a standard graded k-algebra then we can take k_{1} = … = k_{r} = 1 in Theorem 2.1 and this, by well known results from the theory of rational generating functions (see, e.g., [33], Proposition 4.2.2 iii)), implies the following fundamental result which was first proved by Hilbert (in a more general setting, see, e.g., [31], Corollary 9, [3], Corollary 11.2, or [12], Theorem 4.1.3).

Theorem 2.2 Let R be a standard graded k-algebra. Then there exists a polynomial P_{R}(x) ∈ Q[x] and N ∈ P such that H(R; i) = P_{R}(i) for all i ≥ N.

The polynomial P_{R}(x) uniquely defined by the previous theorem is called the Hilbert polynomial of R. Note that if P (R; x) ∈ Z[x] then P_{R}(x) = 0.

Given n, i ∈ P it is not hard to show (see, e.g., [2], or [12], Lemma 4.2.6, p. 158) that there exist unique integers a_{i} > a_{i−1} > … > a_{j} ≥ j (for some j ∈ [i]) such that

n = (\begin{matrix}a_{i} \\ i \end{matrix} ) + (\begin{matrix}a_{i−1} \\ i−1 \end{matrix} ) + … + (\begin{matrix}a_{j} \\ j \end{matrix} ) .  (1)

We then define

n^{⟨i⟩} =^{def} (\begin{matrix}a_{i}+1 \\ i+1 \end{matrix}) + (\begin{matrix}a_{i−1}+1 \\ i \end{matrix}) + … + (\begin{matrix}a_{j}+1 \\ j+1 \end{matrix}) ,

and we also set 0^{⟨i⟩} =^{def} 0. We call (1) the i-binomial expansion of n. We say that a sequence {h_{0}, h_{1}, h_{2}, …} of nonnegative integers is an O-sequence if the following two conditions are satisfied:

i) h_{0} = 1;

ii) h_{i+1} ≤ (h_{i})^{⟨i⟩} for all i ∈ P.

We say that a finite sequence {h_{0}, h_{1}, …, h_{d}} is an O-sequence if {h_{0}, h_{1}, …, h_{d}, 0, 0, …} is an O-sequence. An O-sequence is sometimes also called an M-vector (see, e.g., [31]) or an M-sequence (see, e.g., [6], where a different, but equivalent, definition is given). Note that an O-sequence {h_{i}}_{i∈N} has no internal zeros (since if h_{i} = 0 then h_{i+1} ≤ (h_{i})^{⟨i⟩} = 0^{⟨i⟩} = 0). However, an O-sequence is not necessarily unimodal (take, e.g., (1, 4, 3, 4)). We say that a formal power series ∑_{i≥0} h_{i}x^{i} ∈ N[[x]] is an O-series if {h_{i}}_{i∈N} is an O-sequence.

Let x_{1}, …, x_{d} be a set of independent variables. Recall (see, e.g., [12], Definition 4.2.1, p. 155, or [30], §2, p. 59) that a (non-empty) set M of monomials in x_{1}, …, x_{d} is said to be an order ideal of monomials if p ∈ M and q divides p implies q ∈ M. In other words, if x_{1}^{a_{1}} … x_{d}^{a_{d}} ∈ M and b_{i} ∈ [0, a_{i}] for i ∈ [d] then x_{1}^{b_{1}} … x_{d}^{b_{d}} ∈ M. In particular, since M ≠ ∅, 1 = x_{1}^{0} … x_{d}^{0} ∈ M. For i ∈ P we let M_{i} =^{def} {p ∈ M : deg(p) = i} (where deg(x_{1}^{a_{1}} … x_{d}^{a_{d}}) =^{def} a_{1} + … + a_{d}), so M_{0} = {1}. The link between O-series, order ideals of monomials, and Hilbert series of standard graded k-algebras is given by the following fundamental and well known result which is due to Macaulay [24]. We refer the reader to [24], [13], or [12], Theorem 4.2.10, p. 160, for a proof (see also [30], §2).

Theorem 2.3 Let {h_{i}}_{i∈N} be a sequence of nonnegative integers. Then the following are equivalent:

i) ∑_{i≥0} h_{i}x^{i} is an O-series;

ii) there exists a standard graded k-algebra R such that P (R; x) = ∑_{i≥0} h_{i}x^{i}, in Z[[x]];

iii) there exists an order ideal of monomials M such that h_{i} = |M_{i}| for all i ∈ N.

The preceding result allows us, among other things, to prove that certain natural operations in the ring of formal power series preserve the property of being an O-series. The following result is known, but for lack of an adequate reference we give its proof here.

Proposition 2.4 Let ∑_{i≥0} a_{i}x^{i} and ∑_{i≥0} b_{i}x^{i} be two O-series, and j ∈ P. Then the following are also O-series:

i) (∑_{i≥0} a_{i}x^{i})(∑_{i≥0} b_{i}x^{i});

ii) ∑_{i≥0} a_{i}x^{i} + ∑_{i≥0} b_{i}x^{i} − 1;

iii) ∑_{i=0}^{j} a_{i}x^{i};

iv) ∑_{i≥0} a_{i}b_{i}x^{i};

v) ∑_{i≥0} a_{ji}x^{i}.

Proof. iii) is immediate from the definition of an O-series. The other statements all follow from corresponding constructions in the theory of graded algebras and Theorem 2.3. More precisely, let R = ⨁_{i≥0} R_{i} and S = ⨁_{i≥0} S_{i} be two standard graded k-algebras such that P (R; x) = ∑_{i≥0} a_{i}x^{i} and P (S; x) = ∑_{i≥0} b_{i}x^{i}. Then R ⊕ S, R ⊗_{k} S, R ∗ S (where ∗ denotes the Segre product, i.e., R ∗ S =^{def} ⨁_{i≥0}(R_{i} ⊗_{k} S_{i})) and R^{(j)} (where R^{(j)} denotes the j-th Veronese subalgebra of R, i.e., R^{(j)} =^{def} ⊕_{i≥0}R_{ij}) are again standard graded k-algebras and P (R⊕S; x) = P (R; x)+P (S; x)−1, P (R⊗_{k}S; x) = P (R; x)P (S; x), P (R ∗ S; x) = ∑_{i≥0} a_{i}b_{i}x^{i} and P (R^{(j)}; x) = ∑_{i≥0} a_{ji}x^{i} which, by Theorem 2.3, proves i), ii), iv), and v). □

Note that it is also possible to prove the preceding result by using the equivalence of parts i) and iii) in Theorem 2.3, thus avoiding commutative algebra.

Throughout this work, we say that a sequence {h_{i}}_{i∈N} (respectively, a polynomial H(x)) is a Hilbert function (respectively, a Hilbert polynomial) if there exists a standard graded k-algebra R such that h_{i} = H(R; i) for all i ∈ N (respectively, H(x) = P_{R}(x)). We say that a finite sequence {h_{0}, h_{1}, …, h_{d}} is a Hilbert function if the sequence {h_{0}, h_{1}, …, h_{d}, 0, 0, …} is a Hilbert function.

Just as Theorem 2.3 provides a numerical characterization of Hilbert functions, there is a numerical characterization of Hilbert polynomials, also due to Macaulay.

Theorem 2.5 Let P (x) ∈ Q[x] be such that P (Z) ⊆ Z, and let m_{0}, …, m_{d} be the unique integers such that

P (x) = ∑_{i=0}^{d} [((\begin{matrix}x \\ i+1 \end{matrix})) − ((\begin{matrix}x−m_{i} \\ i+1 \end{matrix} ))] ,  (2)

(where d = deg(P (x))). Then P (x) is a Hilbert polynomial if and only if m_{0} ≥ m_{1} ≥ … ≥ m_{d} ≥ 0.

The existence and uniqueness of the integers m_{0}, …, m_{d} is an elementary statement, and the “if” part of the above theorem is easy to show. A proof of the “only if” part of Theorem 2.5 is given, e.g., in [24], p. 536, [20], Corollary 5.7, p. 47, and [28], Theorem 2.1, (see also [12], Exercise 4.2.15, p. 165).

Because of the previous result, given a polynomial P (x) ∈ Q[x] such that P (Z) ⊆ Z, we call the integers m_{0}, …, m_{d} uniquely determined by (2) the Macaulay parameters of P (x), and we write M(P) = (m_{0}, …, m_{d}).

By a simplicial complex we mean a collection of sets Δ with the property that if A ∈ Δ and B ⊆ A then B ∈ Δ. We call the elements of Δ the faces of Δ. For S ∈ Δ, the dimension of S is |S| − 1. The dimension of Δ is dim(Δ) =^{def} max {|A| − 1 : A ∈ Δ}. Given a simplicial complex Δ of dimension d − 1 we let f_{i−1}(Δ) =^{def} |{A ∈ Δ : |A| = i}|, for i = 0, …, d, and call f(Δ) =^{def} (f_{0}(Δ), f_{1}(Δ), …, f_{d−1}(Δ)) the f-vector of Δ. We then define the h-vector of Δ, h(Δ) =^{def} (h_{0}(Δ), h_{1}(Δ), …, h_{d}(Δ)), by letting

∑_{i=0}^{d} h_{i}(Δ)x^{d−i} =^{def} ∑_{i=0}^{d} f_{i−1}(Δ)(x − 1)^{d−i} .  (3)

Clearly, knowledge of the f-vector of Δ is equivalent to the knowledge of its h-vector. Note that, by Theorem 2.3, if {f_{0}, …, f_{d−1}} is the f-vector of a simplicial complex then {1, f_{0}, …, f_{d−1}} is a Hilbert function.

Recall (see, e.g., [32], Def. 1.1, p. 62, or [12], Def. 5.1.2, p. 201) that we may associate a standard graded k-algebra to any finite simplicial complex Δ as follows. Let {v_{1}, …, v_{n}} be the set of 0-dimensional faces of Δ, x_{1}, …, x_{n} be indeterminates, and I_{Δ} be the ideal of k[x_{1}, …, x_{n}] generated by {x_{i_{1}} … x_{i_{r}} : 1 ≤ i_{1} < … < i_{r} ≤ n and {v_{i_{1}}, …, v_{i_{r}}} ∉ Δ}. Then it is well known, and easy to see, that R_{Δ} =^{def} k[x_{1}, …, x_{n}]/I_{Δ} is a standard graded k-algebra, called the Stanley-Reisner (or face) ring of Δ. This ring has been extensively studied and we refer the reader to [32], Chap. II, and [12], Chap. 5, for its fundamental properties.

3 A General Theory

Despite the fact that Theorems 2.3 and 2.5 completely characterize Hilbert functions and polynomials it is, in practice, a difficult task to decide if a given polynomial is Hilbert using just these theorems. For example, the reader can check (preferably with the aid of a computer) that M(x^{5}) = [731259975844000893012336498664405837946877348559859163646, 38242907207585681103208094427, 276560696326610, 23520860, 6900, 120] and that (according to Maple) the first entry of this sequence is two times a prime number ! Thus, the computation of the Macaulay parameters of a polynomial is in general not an easy task, neither computationally nor theoretically. Our purpose in this section is to use Theorems 2.3 and 2.5 to deduce other results on Hilbert polynomials that are easier to apply, even though they don’t characterize these objects completely. In particular, we wish to obtain conditions on the coefficients of a polynomial with respect to the bases defined in the previous section that insure that it is a Hilbert polynomial.

We begin with the following result which expresses the relationship between the Macaulay parameters of a polynomial and its coefficients with respect to the basis of twisted binomial coefficients.

Proposition 3.1 Let P (x) ∈ Q[x] be such that P (Z) ⊆ Z, and let

P (x) = ∑_{i=0}^{d} [((\begin{matrix}x \\ i+1 \end{matrix})) − ((\begin{matrix}x−m_{i} \\ i+1 \end{matrix} ))] = ∑_{i=0}^{d} c_{i} ((\begin{matrix}x \\ i \end{matrix})) ,  (4)

where d = deg(P (x)). Then

c_{i} = ∑_{j=0}^{d−i}(−1)^{j} (\begin{matrix}m_{i+j} \\ j+1 \end{matrix} ) ,  (5)

for i = 0, …, d.

Proof. It is easy to see that

((\begin{matrix}x−m \\ i+1 \end{matrix})) = ∑_{j=0}^{i+1}(−1)^{i+1−j} (\begin{matrix}m \\ i+1−j \end{matrix} ) ((\begin{matrix}x \\ j \end{matrix}))  (6)

for all m, i ∈ N. Therefore

((\begin{matrix}x \\ i+1 \end{matrix})) − ((\begin{matrix}x−m \\ i+1 \end{matrix})) = ∑_{j=0}^{i}(−1)^{i−j} (\begin{matrix}m \\ i+1−j \end{matrix} ) ((\begin{matrix}x \\ j \end{matrix})) .  (7)

Summing (7) (with m = m_{i}) for i = 0, …, d and comparing with (4) yields (5), as desired. □

Note that the previous result makes it easy to compute the coefficients of a polynomial with respect to the basis of twisted binomial coefficients from its Macaulay parameters (as implicitly noted also in [24], p. 537), but not conversely (even though the relations (5) are, of course, invertible). Hence, even a reasonably detailed knowledge of the coefficients {c_{0}, …, c_{d}} in (4) will not make it easy to decide if the polynomial is Hilbert. However, the relations (5) do have the following interesting consequence.

Theorem 3.2 For i ∈ N there exist Φ_{i} ∈ Q[x_{0}, …, x_{i}] such that:

i) deg(Φ_{i}) = 2^{i};

ii) if P (x) = ∑_{i=0}^{d} c_{i} ((\begin{matrix}x \\ i \end{matrix})) ∈ Q[x] is such that P (Z) ⊆ Z and M(P (x)) = (m_{0}, …, m_{d}), then m_{d−i} = Φ_{i}(c_{d}, …, c_{d−i}) for i = 0, …, d;

iii) the leading monomial of Φ_{i} is 2 (\frac{x_{0}}{2} )^{2^{i}}.

Proof. We define Φ_{i} ∈ Q[x_{0}, …, x_{i}] inductively as follows,

Φ_{0} =^{def} x_{0},  (8)
Φ_{i} =^{def} x_{i} − ∑_{j=1}^{i}(−1)^{j} (\begin{matrix}Φ_{i−j} \\ j+1 \end{matrix} ) ,  (9)

if i ≥ 1. Then i), ii), and iii) follow easily by induction on i ∈ P. In fact, by our induction hypotheses, deg((\begin{matrix}Φ_{i−j} \\ j+1 \end{matrix} )) = (j + 1)2^{i−j} for j = 1, …, i and hence, by (9), deg(Φ_{i}) = deg((\begin{matrix}Φ_{i−1} \\ 2 \end{matrix} )) = 2^{i} and the leading monomial of Φ_{i} is \frac{1}{2} (2 (\frac{x_{0}}{2} )^{2^{i−1}})^{2} = 2 (\frac{x_{0}}{2} )^{2^{i}}. Similarly, we deduce from (5) and our induction hypotheses that

m_{d−i} = c_{d−i} − ∑_{j=1}^{i}(−1)^{j} (\begin{matrix}m_{d−i+j} \\ j+1 \end{matrix} )
= c_{d−i} − ∑_{j=1}^{i}(−1)^{j} (\begin{matrix}Φ_{i−j}(c_{d},...,c_{d−i+j}) \\ j+1 \end{matrix})
= Φ_{i}(c_{d}, …, c_{d−i}),

by (9), as desired. □

The following easy consequence of Proposition 3.1 will be useful later on.

Lemma 3.3 Let P (x) = ∑_{i=0}^{d} c_{i} ((\begin{matrix}x \\ i \end{matrix})) be a Hilbert polynomial such that c_{d} = 1. Then c_{d−1} ≥ 1.

Proof. From (5) we deduce that m_{d} = c_{d} , and m_{d−1} = c_{d−1} +(\begin{matrix}c_{d} \\ 2 \end{matrix} ), and the thesis follows from Theorem 2.5. □

Note that a Hilbert polynomial satisfying the hypotheses of Lemma 3.3 does not necessarily have all its coefficients nonnegative when expanded in terms of the basis of the twisted binomial coefficients. For example, M (((\begin{matrix}x \\ 2 \end{matrix})) + 4 ((\begin{matrix}x \\ 1 \end{matrix})) − 2 ((\begin{matrix}x \\ 0 \end{matrix}))) = (4, 4, 1).

It is of course easy to compute the Macaulay parameters of polynomials of small degree, and the following computational result will be convenient later on.

Proposition 3.4 Let a, b, c ∈ Z. Then ax^{2} + bx + c is a Hilbert polynomial if and only if

0 ≤ 2a ≤ b + 2a^{2} − 2a ≤ c + (\begin{matrix}b+2a^{2}−2a \\ 2 \end{matrix}) − (\begin{matrix}2a \\ 3 \end{matrix}).

Proof. One computes that

∑_{i=0}^{2} [((\begin{matrix}x \\ i+1 \end{matrix})) − ((\begin{matrix}x−m_{i} \\ i+1 \end{matrix} ))] = x^{2} (\frac{m_{2}}{2} ) + (m_{1} + m_{2} − \frac{m_{2}^{2}}{2} ) x + m_{0} − (\begin{matrix}m_{1} \\ 2 \end{matrix} ) + (\begin{matrix}m_{2} \\ 3 \end{matrix} ) ,

and the thesis follows from Theorem 2.5. □

The next result gives some fundamental operations on polynomials that preserve the property of being a Hilbert polynomial. Some of these are known, but for lack of an adequate reference we give a complete proof here.

Theorem 3.5 Let A(x), B(x) ∈ Q[x] be two Hilbert polynomials, k ∈ P, m ∈ N, and {h_{0}, …, h_{r}} be a Hilbert function. Then the following are Hilbert polynomials:

i) A(x) + B(x);

ii) A(x)B(x);

iii) A(kx + m);

iv) A(x) − A(x − 1);

v) k A(x) + m;

vi) ∑_{i=0}^{r} h_{i}A(x − i).

Proof. By hypothesis there exist H_{1}, H_{2} : N → N such that {H_{1}(n)}_{n∈N} and {H_{2}(n)}_{n∈N} are O-sequences, and H_{1}(n) = A(n), H_{2}(n) = B(n) if n ≥ n_{0} (for some n_{0} ∈ N). Hence, by ii) of Proposition 2.4, {1, H_{1}(1) + H_{2}(1), H_{1}(2) + H_{2}(2), …} is an O-sequence and H_{1}(n) + H_{2}(n) = A(n) + B(n) for n ≥ n_{0} and this shows that A(x) + B(x) is a Hilbert polynomial. In an exactly analogous way (using iv) and v) of Proposition 2.4) one proves ii), and iii) for m = 0.

To prove iv) note that by Theorem 2.5 and our hypotheses we have that

A(x) = ∑_{i=0}^{d} [((\begin{matrix}x \\ i+1 \end{matrix})) − ((\begin{matrix}x−m_{i} \\ i+1 \end{matrix} ))]  (10)

where m_{0} ≥ m_{1} ≥ … ≥ m_{d} ≥ 0, and d =^{def} deg(A(x)). Therefore

A(x) − A(x − 1) = ∑_{i=0}^{d} [((\begin{matrix}x \\ i+1 \end{matrix})) − ((\begin{matrix}x−1 \\ i+1 \end{matrix})) − ((\begin{matrix}x−m_{i} \\ i+1 \end{matrix} )) + ((\begin{matrix}x−1−m_{i} \\ i+1 \end{matrix} ))]
= ∑_{i=0}^{d−1} [((\begin{matrix}x \\ i+1 \end{matrix})) − ((\begin{matrix}x−m_{i+1} \\ i+1 \end{matrix} ))]

and iv) follows from Theorem 2.5. Also, (10) implies that

A(x + 1) = ∑_{i=0}^{d} [((\begin{matrix}x+1 \\ i+1 \end{matrix})) − ((\begin{matrix}x+1−m_{i} \\ i+1 \end{matrix} ))] .  (11)

Now note that,

((\begin{matrix}x+1 \\ i+1 \end{matrix})) − ((\begin{matrix}x+1−m \\ i+1 \end{matrix})) = ∑_{j=0}^{i} [((\begin{matrix}x \\ j+1 \end{matrix})) − ((\begin{matrix}x−m \\ j+1 \end{matrix}))]

and hence

M (((\begin{matrix}x+1 \\ i+1 \end{matrix})) − ((\begin{matrix}x+1−m \\ i+1 \end{matrix}))) = (\underbrace{m, m, …, m}_{i+1})  (12)

for all m, i ∈ N. Therefore, by Theorem 2.5, every summand on the RHS of (11) is a Hilbert polynomial and this, by i), implies that A(x + 1) is a Hilbert polynomial. Hence A(x + m) is a Hilbert polynomial and this concludes the proof of iii) since we have already observed that iii) holds if m = 0.

Now note that it follows easily from (10) that M(A(x) + m) = (m + m_{0}, m_{1}, …, m_{d}). Hence, by Theorem 2.5, A(x) + m is a Hilbert polynomial and v) follows from i).

To prove vi) let R and S be two standard graded k-algebras such that P (R; x) = ∑_{n≥0} H_{1}(n)x^{n} and P (S; x) = ∑_{n=0}^{r} h_{n}x^{n}. Then

P (R ⊗_{k} S; x) = ∑_{n≥0} (∑_{i=0}^{n} h_{i}H_{1}(n − i)) x^{n}

(where h_{i} =^{def} 0 if i > r), and hence

H(R ⊗_{k} S; n) = ∑_{i=0}^{r} h_{i} A(n − i)

if n ≥ n_{0} + r, and vi) follows. □

Note that while parts i), ii), iii) (for m = 0), and vi) of Theorem 3.5 have a clear algebraic and geometric interpretation, we have been unable to find any algebraic or geometric explanation for parts iii) (when m > 0), and iv).

It is natural to ask whether there are other operations on polynomials which preserve the property of being a Hilbert polynomial. One operation to consider, in view of part iv) of Theorem 3.5, is the anti-difference of a polynomial A(x) (i.e., the unique polynomial ∇A such that (∇A)(n) = ∑_{j=0}^{n} A(j) for all n ∈ N). This, however, fails to preserve the property of being a Hilbert polynomial. For example, A(x) = 3x is a Hilbert polynomial (since M(3x) = (3, 3)) but

(∇A)(x) = 3 ((\begin{matrix}x \\ 2 \end{matrix}))

is not a Hilbert polynomial (since M (3 ((\begin{matrix}x \\ 2 \end{matrix}))) = (2, 3, 3)). However, it is not hard to compute the Macaulay parameters of a polynomial A(x) if the Macaulay parameters of A(x) − A(x − 1) are known, and hence to obtain a necessary and sufficient condition on a Hilbert polynomial so that its anti-difference is again a Hilbert polynomial.

Proposition 3.6 Let A(x) ∈ Q[x] be such that A(Z) ⊆ Z and suppose that M(A(x) − A(x − 1)) = (m_{0}, …, m_{d}). Then

M(A(x)) = (m_{−1}, m_{0}, …, m_{d})

where m_{−1} =^{def} ∑_{i=0}^{d}(−1)^{i} (\begin{matrix}m_{i}+1 \\ i+2 \end{matrix}) + A(−1).

Proof. Let B(x) =^{def} A(x) − A(x − 1), for brevity. Then we have from our hypothesis and the definition of (∇B)(x) that, for all n ∈ N,

(∇B)(n) = ∑_{j=0}^{n} B(j)
= ∑_{i=0}^{d} ∑_{j=0}^{n} [((\begin{matrix}j \\ i+1 \end{matrix})) − ((\begin{matrix}j−m_{i} \\ i+1 \end{matrix} ))]
= ∑_{i=0}^{d} [((\begin{matrix}n \\ i+2 \end{matrix})) − ((\begin{matrix}n−m_{i} \\ i+2 \end{matrix} )) + ((\begin{matrix}−m_{i}−1 \\ i+2 \end{matrix}))]
= ∑_{i=0}^{d+1} [((\begin{matrix}n \\ i+1 \end{matrix})) − ((\begin{matrix}n−m′_{i} \\ i+1 \end{matrix} ))]

where m′_{0} = ∑_{i=0}^{d} ((\begin{matrix}−m_{i}−1 \\ i+2 \end{matrix})), and m′_{i} = m_{i−1}, for i = 1, …, d + 1. Therefore M(∇B) =

(m′_{0}, m_{0}, …, m_{d}) and hence M((∇B)(x)+A(−1)) = (A(−1)+m′_{0}, m_{0}, …, m_{d}), as desired. □

Corollary 3.7 Let A(x) ∈ Q[x] be a Hilbert polynomial of degree d with Macaulay parameters (m_{0}, …, m_{d}), and B(x) ∈ Q[x] be such that B(x) − B(x − 1) = A(x). Then B(x) is a Hilbert polynomial if and only if

m_{0} ≤ ∑_{i=0}^{d}(−1)^{i} (\begin{matrix}m_{i}+1 \\ i+2 \end{matrix}) + B(−1).□

We now wish to study which polynomials of the bases defined in the previous section are Hilbert polynomials.

Theorem 3.8 Let d ∈ P, a_{0}, …, a_{d} ∈ P, and i ∈ [0, d]. Then:

i) x^{d} is a Hilbert polynomial if and only if d ≥ 3;

ii) ⟨x⟩_{d} is a Hilbert polynomial if and only if d ≥ 3;

iii) a_{0}(x + a_{1}) … (x + a_{d}) is a Hilbert polynomial; iv) (\begin{matrix}x \\ d \end{matrix}) is not a Hilbert polynomial;

v) ((\begin{matrix}x \\ d \end{matrix})) is not a Hilbert polynomial;

vi) (\begin{matrix}x+d−i \\ d \end{matrix}) is a Hilbert polynomial if and only if i = 0.

Proof. A straightforward computation using Theorem 2.5 shows that x and x^{2} are not Hilbert polynomials, while x^{3}, x^{4}, and x^{5} are. So i) follows from part ii) of Theorem 3.5. Also, it is easily verified, using Theorem 2.5, that ⟨x⟩_{2} is not a Hilbert polynomial, while ⟨x⟩_{3} is. But, by Proposition 3.4, r and x + r are Hilbert polynomials whenever r ≥ 1, so ii) and iii) follow from part ii) of Theorem 3.5. Furthermore, we have from (6) that

(\begin{matrix}x+d−i \\ d \end{matrix}) = ∑_{j=d−i+1}^{d}(−1)^{d−j} (\begin{matrix}i−1 \\ d−j \end{matrix} ) ((\begin{matrix}x \\ j \end{matrix})) ,

if i ∈ [d], so iv), v), and the “only if” part of vi) follow from Lemma 3.3. On the other hand, if i = 0 then

(\begin{matrix}x+d \\ d \end{matrix}) = ((\begin{matrix}x+1 \\ d \end{matrix})) ,

which is a Hilbert polynomial since \{((\begin{matrix}n+1 \\ d \end{matrix}))\}_{n∈N} is the Hilbert function of k[x_{0}, …, x_{d}]

(in fact, it follows from (12) that the Macaulay parameters of (\begin{matrix}x+d \\ d \end{matrix}) are (\overbrace{1, 1, …, 1}^{d+1})). □

The reader will notice that the basis of lower factorials {(x)_{i}}_{i∈N} is missing from Theorem 3.8. It can be easily checked that (x)_{2}, and (x)_{3} are not Hilbert polynomials, and we conjecture (see section 5) that (x)_{d} is always a Hilbert polynomial if d ≥ 4.

Theorem 3.8 has several interesting consequences.

Corollary 3.9 Let P (x) ∈ Q[x] and suppose that P (x−1) ∈ N[x]. Then P (x) is a Hilbert polynomial.

Proof. By hypothesis we can write P (x) = ∑_{i=0}^{d} a_{i}(x + 1)^{i} where a_{0}, …, a_{d} ∈ N, so the thesis follows from part i) of Theorem 3.5 and part iii) of Theorem 3.8. □

Corollary 3.10 Let P (x) = ∑_{i=0}^{d} a_{i}x^{i} = ∑_{i=0}^{d} γ_{i}⟨x⟩_{i} ∈ Q[x]. Suppose that at least one of the following conditions is satisfied:

i) a_{0}, …, a_{d} ∈ N and a_{1}, a_{2} ≥ 3;

ii) γ_{0}, …, γ_{d} ∈ N and γ_{1} ≥ 3, γ_{2} ≥ 2.

Then P (x) is a Hilbert polynomial.

Proof. Assume first that i) holds. It follows from part i) of Theorem 3.5 and part i) of Theorem 3.8 that a_{i}x^{i} is a Hilbert polynomial for 0 ≤ i ≤ d, i ≠ 1, 2 (since a_{i} ∈ N). On the other hand, it follows from Proposition 3.4 that a_{1}x and a_{2}x^{2} are also Hilbert polynomials (since a_{1}, a_{2} ≥ 3), so the thesis follows from part i) of Theorem 3.5.

Similarly, if ii) holds then it follows from part i) of Theorem 3.5 and part ii) of Theorem 3.8 that γ_{i}⟨x⟩_{i} is a Hilbert polynomial for 0 ≤ i ≤ d, i ≠ 1, 2. On the other hand, it follows from Proposition 3.4 that γ_{1}⟨x⟩_{1} and γ_{2}⟨x⟩_{2} are also Hilbert polynomials (since γ_{1} ≥ 3, γ_{2} ≥ 2), so the thesis follows from part i) of Theorem 3.5. □

Another interesting consequence of Theorem 3.8 is the following.

Theorem 3.11 Let P (x) = ∑_{i=0}^{d} c_{i} ((\begin{matrix}x \\ i \end{matrix})) = ∑_{i=0}^{d} w_{i} (\begin{matrix}x+d−i \\ d \end{matrix}) = ∑_{i=0}^{d} a_{i}x^{i} be such that

P (Z) ⊆ Z. Suppose that any one of the following conditions is satisfied:

i) c_{0} ≥ c_{1} ≥ … ≥ c_{d} ≥ 0;

ii) w_{0} ≥ w_{1} ≥ … ≥ w_{d} ≥ 0;

iii) a_{0}, …, a_{d} ∈ N, d ≥ 3, and a_{0} ≤ a_{1} ≤ a_{2} ≤ a_{3}.

Then P (x) is a Hilbert polynomial.

Proof. Since P (Z) ⊆ Z we conclude easily (considering P (0), P (−1), …, P (−d + 1)) that c_{0}, …, c_{d} ∈ Z, and w_{0}, …, w_{d} ∈ Z.

Assume now that i) holds. Then there exist β_{0}, …, β_{d} ∈ N such that c_{i} = β_{i} + β_{i+1} + … + β_{d} for i = 0, …, d. Hence

P (x) = ∑_{i=0}^{d} c_{i} ((\begin{matrix}x \\ i \end{matrix})) = ∑_{i=0}^{d} ∑_{j=i}^{d} β_{j} ((\begin{matrix}x \\ i \end{matrix})) = ∑_{j=0}^{d} β_{j} (∑_{i=0}^{j} ((\begin{matrix}x \\ i \end{matrix}))) = ∑_{j=0}^{d} β_{j} ((\begin{matrix}x+1 \\ j \end{matrix})) ,

and the thesis follows from Theorems 3.5 and 3.8.

Similarly, if ii) holds then there exist b_{0}, …, b_{d} ∈ N such that w_{i} = b_{i} + b_{i+1} + … + b_{d} for i = 0, …, d. Hence

P (x) = ∑_{i=0}^{d} w_{i} (\begin{matrix}x+d−i \\ d \end{matrix}) = ∑_{i=0}^{d} ∑_{j=i}^{d} b_{j} (\begin{matrix}x+d−i \\ d \end{matrix}) = ∑_{j=0}^{d} b_{j} (∑_{i=0}^{j} (\begin{matrix}x+d−i \\ d \end{matrix})) .  (13)

Now note that

∑_{i=0}^{j} (\begin{matrix}x+d−i \\ d \end{matrix}) = ∑_{i=0}^{d} [((\begin{matrix}x+1−i \\ d+1 \end{matrix})) − ((\begin{matrix}x−i \\ d+1 \end{matrix}))]
= ((\begin{matrix}x+1 \\ d+1 \end{matrix})) − ((\begin{matrix}x−j \\ d+1 \end{matrix})) .

Hence ∑_{i=0}^{j} (\begin{matrix}x+d−i \\ d \end{matrix}) is a Hilbert polynomial by (12) and the thesis follows from (13), and Theorem 3.5.

Finally, assume that iii) holds. It is easily verified (using Theorem 2.5) that x^{2} + x^{3}, x + x^{2} + x^{3}, and 1 + x + x^{2} + x^{3} are Hilbert polynomials. But

P (x) = a_{0}(1 + x + x^{2} + x^{3}) + (a_{1} − a_{0})(x + x^{2} + x^{3}) + (a_{2} − a_{1})(x^{2} + x^{3}) +
+ (a_{3} − a_{2})x^{3} + ∑_{i=4}^{d} a_{i}x^{i},

so the thesis follows from our hypotheses and Theorems 3.5 and 3.8. □

For the basis \{(\begin{matrix}x \\ i \end{matrix})\}_{i=0,...,d} we have been unable to prove any results similar to Theorem 3.11. The main reason is that, in general, neither ∑_{i=0}^{j} (\begin{matrix}x \\ i \end{matrix}) nor ∑_{i=j}^{d} (\begin{matrix}x \\ i \end{matrix}) are Hilbert polynomials. For example, M ((\begin{matrix}x \\ 0 \end{matrix}) + (\begin{matrix}x \\ 1 \end{matrix}) + (\begin{matrix}x \\ 2 \end{matrix})) = (1, 0, 1) and M ((\begin{matrix}x \\ 2 \end{matrix}) + (\begin{matrix}x \\ 3 \end{matrix})) = (1, 1, −1, 1), (in fact, computations suggest that ∑_{i=0}^{j} (\begin{matrix}x \\ i \end{matrix}) is never a Hilbert polynomial if j ≥ 2 and that ∑_{i=j}^{d} (\begin{matrix}x \\ i \end{matrix}) is never a Hilbert polynomial if d ≥ 3 and 0 ≤ j ≤ d). So, in some sense, the basis \{(\begin{matrix}x \\ i \end{matrix})\}_{i=0,...,d} is, among the six bases considered, the “farthest” from Hilbert polynomials.

Given the close connection existing between Hilbert functions and polynomials it is natural to wonder if there are other ways to produce Hilbert polynomials from a Hilbert function.

Theorem 3.12 Let {h_{0}, …, h_{d}} be a Hilbert function. Then the following are Hilbert polynomials:

i) ∑_{i=0}^{d} h_{i} (\begin{matrix}x+d−i \\ d \end{matrix});

ii) ∑_{i=0}^{d} h_{i}⟨x⟩_{i}.

Proof. i) is an immediate consequence of part vi) of Theorems 3.5 and 3.8 (just take

A(x) = (x+d_{d})).

To prove ii) note that if h_{1} ≥ 3 and h_{2} ≥ 2 then the result follows from part ii) of Corollary 3.10. If h_{2} ≤ 1 then, by our hypothesis, h_{3} ≤ h_{2}^{⟨2⟩} ≤ 1, and therefore h_{4} ≤ h_{3}^{⟨3⟩} ≤ 1, etc.., so we conclude that h_{2} = … = h_{r} = 1 and h_{r+1} = … = h_{d} = 0 for some r ∈ [2, d]. But, by Proposition 3.4, 1 + h_{1}⟨x⟩_{1} and 1 + h_{1}⟨x⟩_{1} + ⟨x⟩_{2} are Hilbert polynomials for any h_{1} ∈ P. Hence, by part i) of Theorem 3.5 and part ii) of Theorem 3.8 we conclude that 1+h_{1}⟨x⟩_{1}+⟨x⟩_{2}+…+⟨x⟩_{r} is a Hilbert polynomial for any r ≥ 2. If h_{2} ≥ 2 but h_{1} ≤ 2, then by our hypothesis we conclude that 2 ≤ h_{2} ≤ h_{1}^{⟨1⟩} = (\begin{matrix}h_{1}+1 \\ 2 \end{matrix}) ≤ (\begin{matrix}3 \\ 2 \end{matrix}) = 3 and hence that h_{1} = 2 and 2 ≤ h_{2} ≤ 3. But, by Proposition 3.4, 1 + 2⟨x⟩_{1} + 2⟨x⟩_{2} and 1 + 2⟨x⟩_{1} + 3⟨x⟩_{2} are both Hilbert polynomials, so the result follows also in this case from part i) of Theorem 3.5 and part ii) of Theorem 3.8. □

Note that the preceding result fails for the bases \{x^{i}\}_{i=0,...,d}, \{(x)_{i}\}_{i=0,...,d} and \{(\begin{matrix}x \\ i \end{matrix})\}_{i=0,...,d}. For example, 1 + x + x^{2}, 1 + (x)_{1} + (x)_{2}, and 1 + (\begin{matrix}x \\ 1 \end{matrix}) + (\begin{matrix}x \\ 2 \end{matrix}) are not Hilbert polynomials.

Since, by Theorem 2.3, if (f_{0}, …, f_{d−1}) ∈ N^{d} is the f-vector of some simplicial complex then (1, f_{0}, …, f_{d−1}) is a Hilbert function, it is natural to investigate the analogue of Theorem 3.12 for f-vectors of simplicial complexes.

Theorem 3.13 Let (f_{0}, …, f_{d−1}) ∈ N^{d} (d ∈ P) be the f-vector of some simplicial complex. Then the following are Hilbert polynomials:

i) ∑_{i=0}^{d−1} f_{i} (\begin{matrix}x \\ i \end{matrix});

ii) ∑_{i=0}^{d−1} f_{i}⟨x⟩_{i};

iii) ∑_{i=0}^{d−1} f_{i}x^{i}.

Proof. Let Δ be a simplicial complex such that f(Δ) = (f_{0}, …, f_{d−1}), and let R_{Δ} be the Stanley-Reisner ring of Δ. It is then well known (see, e.g., [32], Theorem 1.4, p. 63, or [12], Theorem 5.1.7, p. 204), and also easy to see, that the Hilbert function of R_{Δ} is given by

H(R_{Δ}; n) = \{ \begin{matrix}1, & if n = 0, \\ ∑_{i=0}^{d−1} f_{i} (\begin{matrix}n−1 \\ i \end{matrix}) , & if n ∈ P, \end{matrix}  (14)

and i) follows from part iii) of Theorem 3.5.

To prove ii) and iii) note that if f_{2} ≥ 3 then necessarily f_{1} ≥ 3 and ii) and iii) follow from Corollary 3.10. If f_{2} ≤ 2 then dim(Δ) ≤ 2 and it is easy to check, using Proposition 3.4, that ∑_{i=1}^{2} f_{i}x^{i} and ∑_{i=0}^{2} f_{i}⟨x⟩_{i} are always Hilbert polynomials in this case. □

Note that there exists a complete numerical characterization, similar to Theorem 2.3, of the sequences that are the f-vector of some simplicial complex (see, e.g., [12], §5.1, p. 201, or [32], Theorem 2.1, p. 64). Therefore, one could state Theorem 3.13 without any reference to simplicial complexes.

We conclude our general discussion on Hilbert polynomials by introducing a concept which measures “how far” a polynomial is from being Hilbert. The crucial result for this definition is the following.

Theorem 3.14 Let P (x) ∈ Z[x] be a polynomial with positive leading term. Then there exists M ∈ N such that P (x + i) is a Hilbert polynomial for any i ≥ M.

Proof. Let P (x) = ∑_{j=0}^{d} a_{j}x^{j} where a_{j} ∈ Z and a_{d} ∈ P. Then

P (x + i) = ∑_{j=0}^{d} a_{j}(x + i)^{j}
= ∑_{j=0}^{d} a_{j} ∑_{k=0}^{j} (\begin{matrix}j \\ k \end{matrix}) x^{k}i^{j−k}
= ∑_{k=0}^{d} (∑_{j=k}^{d} a_{j} (\begin{matrix}j \\ k \end{matrix}) i^{j−k}) x^{k}.

Hence the coefficient of x^{k} in P (x + i) is a polynomial in i of degree d − k and positive leading term, for k = 0, …, d. Therefore there exists N ∈ N such that P (x + i) ∈ N[x] if i > N. The thesis follows from Corollary 3.9. □

The preceding theorem suggests, and allows us to make, the following definition. Given a polynomial P (x) ∈ Z[x] with positive leading term we let

H{P } =^{def} max{i ∈ N : P (x + i) is not a Hilbert polynomial} + 1  (15)

(where max{∅} =^{def} −1). We call H{P } the Hilbert index of P (x). Hence P (x + i) is a Hilbert polynomial for all i ≥ H{P }, and P (x) is a Hilbert polynomial if H{P } = 0.

Part iii) of Theorem 3.5 (with k = m = 1) enables us to give the following useful characterization of the Hilbert index of a polynomial.

Corollary 3.15 Let P (x) ∈ Z[x] be a polynomial with positive leading term and i ∈ N. Then P (x + i) is a Hilbert polynomial if and only if i ≥ H{P }. □

Since (\begin{matrix}x \\ d \end{matrix}) and ((\begin{matrix}x \\ d \end{matrix})) are not Hilbert polynomials it is natural to wonder, in light of the concept just introduced, what is their Hilbert index. As a matter of fact, we have already answered this question in Theorem 3.8, essentially, but we record the result here.

Proposition 3.16 Let d ∈ P. Then H \{(\begin{matrix}x \\ d \end{matrix})\} = d and H \{((\begin{matrix}x \\ d \end{matrix}))\} = 1.

Proof. Part vi) of Theorem 3.8 shows that ((\begin{matrix}x \\ d \end{matrix})) = (\begin{matrix}x+d−1 \\ d \end{matrix}) is not a Hilbert polynomial while ((\begin{matrix}x+1 \\ d \end{matrix})) = (\begin{matrix}x+d \\ d \end{matrix}) is, hence by Corollary 3.15 H \{(\begin{matrix}x \\ d \end{matrix})\} = d, and H \{((\begin{matrix}x \\ d \end{matrix}))\} = 1. □

Note that Theorem 3.2 has the following interesting consequence.

Theorem 3.17 Let P (x) ∈ Z[x] be a polynomial with positive leading term. Then there exists M ∈ N such that i P (x) is a Hilbert polynomial for any i ≥ M.

Proof Let P (x) = ∑_{j=0}^{d} c_{j} ((\begin{matrix}x \\ j \end{matrix})) where c_{d} > 0. Then we have from Theorem 3.2 that

M(i P (x)) = (Φ_{d}(ic_{d}, …, ic_{0}), Φ_{d−1}(ic_{d}, …, ic_{1}), …, Φ_{1}(ic_{d}, ic_{d−1}), Φ_{0}(ic_{d}))  (16)

for all i ∈ Z. But, again by Theorem 3.2, Φ_{j}(ic_{d}, …, ic_{d−j}) − Φ_{j−1}(ic_{d}, …, ic_{d−j+1}) is a polynomial in i of degree 2^{j} and positive leading term, for j = 1, …, d. Therefore there exists N ∈ N such that

Φ_{d}(ic_{d}, …, ic_{0}) ≥ Φ_{d−1}(ic_{d}, …, ic_{1}) ≥ … ≥ Φ_{1}(ic_{d}, ic_{d−1}) ≥ Φ_{0}(ic_{d})

for all i ≥ N, and the result follows from (16), Theorem 2.5, and our hypothesis since Φ_{0}(ic_{d}) = ic_{d} ≥ 0 if i ≥ 0. □

Therefore, one could define a second “Hilbert index” in analogy with (15). We leave the investigation of this “Hilbert index” to the interested reader. In particular, it would be interesting to know if the analogue of Corollary 3.15 holds for it.

4 Applications to Combinatorics

In this section we apply the general results obtained in the previous one to prove that several polynomials arising in enumerative and algebraic combinatorics are actually Hilbert polynomials.

We begin by considering several polynomials associated to graph colorings. Let G = (V, E) be a graph (without loops and multiple edges). A map φ : V → P is said to be a coloring of G if φ(x) ≠ φ(y) for all x, y ∈ V such that (x, y) ∈ E. Given n ∈ P we denote by P_{G}(n) the number of colorings φ : V → P such that φ(V) ⊆ [n]. It is then well known (see, e.g., [26], or [14], §4.1, p. 179) that there exists a polynomial χ(G; x) ∈ Z[x], of degree |V |, such that χ(G; n) = P_{G}(n) for all n ∈ P. This polynomial is called the chromatic polynomial of G and has been extensively studied (see, e.g., [27], for a survey). Since χ(G; x) is a polynomial one may write

χ(G; x) = ∑_{i=0}^{|V |} a_{i}(x)_{i} = ∑_{i=0}^{|V |}(−1)^{|V |−i}c_{i}⟨x⟩_{i} .

Then the polynomials σ(G; x) =^{def} ∑_{i=0}^{|V |} a_{i}x^{i} and τ(G; x) =^{def} ∑_{i=0}^{|V |} c_{i}x^{i} are called the σpolynomial and the τ-polynomial of G, respectively. Despite the fact that knowledge of one of these three polynomials implies knowledge of the other two it is often the case that σ(G; x) and τ(G; x) are more convenient to handle then χ(G; x) itself. For this reason σ(G; x) and τ(G; x) have also been studied, and we refer the reader to [9], [10], and the references cited there, for more information on these two polynomials.

Theorem 4.1 Let G = (V, E) be a graph on p vertices, with p ≥ 3. Then the following are Hilbert polynomials:

i) σ(G; x);

ii) τ(G; x);

iii) (−1)^{p}χ(G; −(x + 1)).

Proof. It is easy to verify directly (using Theorem 2.5 and some patience) that the theorem holds if p = 3.

We first prove i) by induction on p ≥ 3. Assume that p ≥ 4. If G = K_{p} (the complete graph on p vertices) then σ(G; x) = x^{p} and i) holds by Theorem 3.8. If G ≠ K_{p} then it follows from Theorem 1 of [26] that

χ(G; x) = χ(K_{p}; x) + ∑_{j=1}^{(\begin{matrix}p \\ 2 \end{matrix})−|E|} χ(G_{j}; x),

and (therefore) that

σ(G; x) = σ(K_{p}; x) + ∑_{j=1}^{(\begin{matrix}p \\ 2 \end{matrix})−|E|} σ(G_{j}; x),

where each G_{j} has p−1 vertices, and i) follows from our induction hypothesis and Theorem 3.5.

Similarly, we prove ii) by induction on p ≥ 3. If G = N_{p} (the empty graph on p vertices) then it is easy to see (see, e.g., [33], p. 209, or [9], p. 748) that

τ(N_{p}; x) = ∑_{i=1}^{p} S(p, i)x^{i} = σ(N_{p}; x)

and the result follows from i). If G ≠ N_{p} then there follows from repeated application of Proposition 5.1 of [9] that

τ(G; x) = τ(N_{p}; x) + ∑_{j=1}^{|E|} τ(G_{j}; x)

where each G_{j} has p−1 vertices, and ii) follows from our induction hypothesis and Theorem 3.5.

Finally, note that iii) follows immediately from Corollary 3.9 and the well known fact (see, e.g., [26]) that (−1)^{p}χ(G; −x) ∈ N[x]. □

Note that the above proof shows that (−1)^{p}χ(G; −(x + 1)) is a Hilbert polynomial for any p ≥ 1.

Regarding the chromatic polynomial itself we have the following result (see also Conjecture 5.3) whose proof is analogous to that of part i) of Theorem 4.1 and is therefore omitted.

Proposition 4.2 The following statements are equivalent:

i) χ(G; x) is a Hilbert polynomial for all graphs G with at least 4 vertices;

ii) (x)_{p} is a Hilbert polynomial for all p ≥ 4. □

Another connection between chromatic polynomials and Hilbert functions appears in [4].

We now consider Hilbert polynomials arising from the theory of finite partially ordered sets. Let P be a finite poset. Recall (see, e.g., [33], §3.11, p. 129) that the zeta polynomial of P is the unique polynomial Z(P; x) such that Z(P; n + 1) equals the number of multichains of P of length n − 1, for all n ∈ P (see, [33], §3.11, for further information about zeta polynomials), and that the order polynomial of P is the unique polynomial Ω(P; x) such that Ω(P; n) equals the number of order preserving maps ω : P → [n], for all n ∈ P (see [33], §4.5, for further information about order polynomials). Given a finite labeled poset (P, ω) (i.e., P is a finite poset, and ω : P → [p] is a bijection, where p =^{def} |P |) and a linear extension τ of P (i.e., an order preserving bijection τ : P → [p]) we let

d(τ, ω) =^{def} |{i ∈ [p − 1] : ω(τ^{−1}(i)) > ω(τ^{−1}(i + 1))}|,

and w_{i}(P, ω) be the number of linear extensions τ of P such that d(τ, ω) = i − 1, for i = 1, …, p. The sequence {w_{1}(P, ω), …, w_{p}(P, ω)} is one of the fundamental enumerative invariants of the labeled poset (P, ω) and has been studied extensively (see, e.g, [29], and [8]). In particular, it is known (see, e.g., [29], §I.2, Definition 3.2, p.8, and Proposition 8.3, p. 24) that if ω is a linear extension of P then the numbers w_{i}(P; ω) do not depend on ω. In this case we write w_{i}(P) instead of w_{i}(P; ω).

Theorem 4.3 Let P be a finite poset of size p. Then:

i) Z(P; x + 1) is a Hilbert polynomial;

ii) Ω(P; x + 1) is a Hilbert polynomial;

iii) (w_{1}(P), …, w_{p}(P)) is a Hilbert function.

Proof. It is well known (see, e.g., [33], Prop. 3.11.1, p. 129) that

Z(P; x + 1) = ∑_{i=0}^{l} b_{i} (\begin{matrix}x−1 \\ i \end{matrix})  (17)

where b_{i} is the number of chains of P of length i (i.e., totally ordered subsets of P of cardinality i + 1), and l is the length of the longest chain of P. But the collection of all chains of P is clearly a simplicial complex (usually denoted Δ(P) and called the order complex of P, see, e.g., [33], p. 120) and its f-vector is (b_{0}, b_{1}, …, b_{l}). Hence i) follows from (17) and (14). Also, it is well known (see, e.g., [33], §3.11, p. 130), and easy to see, that

Ω(P; x) = Z(J(P); x)  (18)

(where J(P) denotes the lattice of order ideals of P, see, e.g., [33], §3.4) and so ii) follows from i). To prove iii) note that using (17) and (18) we conclude that

1 + ∑_{n≥1} ∑_{i=0}^{p} f_{i} (\begin{matrix}n−1 \\ i \end{matrix}) x^{n} = ∑_{n≥0} Z(J(P); n + 1)x^{n}
= ∑_{n≥0} Ω(P; n + 1)x^{n}

= \frac{∑_{i=1}^{p}w_{i}(P)x^{i−1}}{(1 − x)^{p+1}}  (19)

by a well known result from the theory of P -partitions (see, e.g., [33], Theorem 4.5.14, p. 219), where f_{i} is the number of chains of J(P) of length i (i.e., the number of i-dimensional faces of Δ(J(P))). This implies, by (3) and the binomial theorem (see, e.g., [33], p. 16), that (w_{1}(P), …, w_{p}(P)) is the h-vector of Δ(J(P)). But it is well known (see, e.g., [33], §3.4) that J(P) is always a distributive lattice. This, in turn, implies that Δ(J(P)) is shellable (see, e.g., [12], Theorem 5.1.12, p. 208, and [33], §3.3) and iii) follows from the fact that h-vectors of shellable complexes are O-sequences (see, e.g., Theorem 5.1.15 of [12]). □

Part ii) of Theorem 4.3 was first proved by Stanley ([34]) and, as mentioned in the Introduction, was the motivation and origin of the present work. The preceding result suggests the question of whether, more generally, the order polynomial Ω(P, ω; x + 1) of a labeled poset (P, ω) (see, e.g., [29], §13, p. 45, or [8], p. 1, for definitions) is a Hilbert polynomial. This is easily seen to be false. For example, if P = [3] and ω(1) = 3, ω(2) = 2, ω(3) = 1, then it is easy to see that Ω(P, ω; x+1) = (\begin{matrix}x+1 \\ 3 \end{matrix}) which is not a Hilbert polynomial by part vi) of Theorem 3.8. Nonetheless, we feel that there are general classes of labeled posets for which Ω(P, ω; x + 1) is a Hilbert polynomial (see Conjecture 5.7 and the comments following it). Note that, by part i) of Theorem 3.12 and well known results on the order polynomial (see, e.g., [8], Theorem 5.7.1, p. 66) part ii) is a consequence of part iii) in Theorem 4.3. Therefore, iii) also fails, in general, if ω is not a linear extension.

Taking appropriate posets P for which the zeta polynomial is known allows us to find explicit classes of Hilbert polynomials. We give one such example here.

Corollary 4.4 Let k, m ∈ P. Then \frac{1}{m} (\begin{matrix}(kx+1)m \\ m−1 \end{matrix}) is a Hilbert polynomial.

Proof. Let P_{k,m} be the poset of all non-crossing, k-divisible, partitions of [km], ordered by refinement (see, e.g., [33], Chapter 3, Ex. 68.a, p. 169, [8], §6.3, p. 73, or [16], for definitions). Then by a result of Edelman (see [16], Corollary 4.4, or [33], loc. cit.) we have that

Z(P_{k,m}; x + 1) = \frac{1}{m} (\begin{matrix}(kx+1)m \\ m−1 \end{matrix}) ,

and the thesis follows from Theorem 4.3. □

Note that using Theorems 3.5 and 3.8 one can easily prove that (\begin{matrix}(kx+1)m \\ m−1 \end{matrix}) is a Hilbert polynomial for all k, m ∈ P. However, we have been unable to find a similar proof (i.e., avoiding Theorem 4.3) for \frac{1}{m} (\begin{matrix}(kx+1)m \\ m−1 \end{matrix}).

For our next two applications we assume that the reader is familiar with the basic theory of Coxeter groups as presented, e.g., in Part II of [21]. In particular, given a Coxeter system (W, S) we denote by l : W → N its length function, and by ⪯ the Bruhat order on W. Given u, v ∈ W we denote by R_{u,v}(x) (respectively, P_{u,v}(x)) the R-polynomial (respectively, Kazhdan-Lusztig polynomial) of u and v and we let

d(v) =^{def} |{s ∈ S : l(vs) ≤ l(v)}|.  (20)

We refer the reader to [21], §§5.2, 5.9, 7.4, and 7.5 for the definitions of, and further information about, these concepts.

We need first the following simple observation.

Lemma 4.5 Let i, j ∈ N, j ≥ 2. Then x^{i}(x + 1)^{j} is a Hilbert polynomial.

Proof. By Theorems 3.5 and 3.8 it is clearly enough to prove the result for j = 2. If i ≥ 3 then x^{i}(x + 1)^{2} is a Hilbert polynomial by Theorems 3.5 and 3.8. On the other hand, one can verify directly (using Theorem 2.5) that (x + 1)^{2}, x(x + 1)^{2}, and x^{2}(x + 1)^{2} are all Hilbert polynomials and the result follows. □

Theorem 4.6 Let (W, S) be a Coxeter system and u, v ∈ W, u ⪯ v, be such that l(v) − l(u) ≥ 3. Then R_{u,v}(x + 1) is a Hilbert polynomial.

Proof. If l(v) − l(u) = 3 then it is easy to see (see, e.g., [21], §7.5) that R_{u,v}(x) equals either (x − 1)^{3} or (x − 1)^{3} + (x − 1)x and one can check that the result holds in this case. So assume that l(v) − l(u) ≥ 4. It is then well known (see, e.g., [21], §7.5, p. 154, or [15], Theorem 1.3) that

R_{u,v}(x + 1) = ∑_{i=0}^{⌊ \frac{d}{2} ⌋} a_{i}(x + 1)^{i}x^{d−2i}  (21)

where d =^{def} l(v) − l(u) and a_{i} ∈ N for i = 0, …, ⌊\frac{d}{2}⌋. If i = 1 then d − 2i ≥ 2 and hence (x + 1)x^{d−2i} is a Hilbert polynomial by Theorems 3.5 and 3.8 and the fact that (x + 1)x^{2} is a Hilbert polynomial. If i = 0 then d − 2i ≥ 4 and hence x^{d−2i} is a Hilbert polynomial by Theorem 3.8. If i ≥ 2 then (x + 1)^{i}x^{d−2i} is a Hilbert polynomial by Lemma 4.5. Hence the result follows from (21) and Theorem 3.5. □

Given a finite Coxeter system (W, S) we let

d_{i}(W) =^{def} |{v ∈ W : d(v) = i}|  (22)

for i ∈ N.

Theorem 4.7 Let (W, S) be a finite Coxeter system and u, v ∈ W, u ⪯ v. Then:

i) ∑_{w∈W} x^{d(w)} = ∑_{i≥0} d_{i}(W)x^{i} is a Hilbert polynomial;

ii) P_{u,v}(x + 1) is a Hilbert polynomial;

iii) {d_{0}(W), d_{1}(W), …, d_{|S|}(W)} is a Hilbert function.

Proof. Let, for brevity, P (W; x) =^{def} ∑_{w∈W} x^{d(w)}. If |S| ≤ 2 then either P (W; x) = 1 + x (if |S| = 1) or W is a finite dihedral group, in which case P (W; x) = 1 + (2p − 2)x + x^{2} for some p ≥ 2. In both cases i) holds by Proposition 3.4. So assume that |S| ≥ 3. Note that it follows immediately from the definition (22) that

d_{0}(W) = 1, d_{1}(W) ≥ |S|

for any (W, S) (since d(s) = 1 for all s ∈ S). Furthermore, it is known (see, e.g., [11], Theorem 2.4) that P (W; x) is always a symmetric unimodal polynomial. Hence

d_{2}(W) ≥ |S|

(since deg(P (W; x)) = |S| ≥ 3). Therefore d_{1}(W) ≥ 3 and d_{2}(W) ≥ 3 and i) follows from part i) of Corollary 3.10.

Since it is well known (see [23] and [1]) that Kazhdan-Lusztig polynomials of finite Coxeter systems have nonnegative coefficients, ii) follows immediately from Corollary 3.9.

To prove iii) let Δ(W, S) be the Coxeter complex of (W, S) (see, e.g., [5], or [21], §1.15, for the definition and further information about the Coxeter complex). By a result of Björner (see [5], Theorems 1.6, 2.1, and Proposition 1.2, or [11], Theorem 2.3) the hvector of Δ(W, S) is (d_{0}(W), d_{1}(W), …, d_{|S|}(W)). But, again by a result of Björner ([5], Theorem 2.1), Δ(W, S) is a shellable simplicial complex and iii) follows from Theorem 5.1.15 of [12]. □

Note that it is a long standing conjecture (see, [22], p. 166, and also [21], §7.9, p. 159) that Kazhdan-Lusztig polynomials have always nonnegative coefficients. It is therefore natural to conjecture that part ii) of Theorem 4.7 holds also for infinite Coxeter systems. Given the close connection existing between the R-polynomials and the Kazhdan-Lusztig polynomials of W (see, e.g., [21], §7.10, p. 160, eq. (20)) one can ask whether there is a direct proof of part ii) of Theorem 4.7 from Theorem 4.6. If this could be found then it would probably yield a proof of our conjecture. Also note that, by the remarks following Theorem 3.12, part i) is not a consequence of part iii) in Theorem 4.7.

If (W, S) is a Coxeter system of type A_{n} then it is well known that xP (W; x) = A_{n+1}(x) and d_{k}(W) = A(n + 1, k + 1) for n ∈ P and k ∈ N, where A_{n}(x) and A(n, k) denote the n-th Eulerian polynomial and the (n, k)-th Eulerian number, respectively. Though these objects have been widely studied (see, e.g., [17], [14], §6.5, and the references cited there) the preceding result seems to be new even in this special case.

Corollary 4.8 Let n ∈ P. Then \frac{1}{x}A_{n}(x) is a Hilbert polynomial and \{A(n, k)\}_{k=1,...,n} is a Hilbert function. □

We don’t know any combinatorial proof (i.e., avoiding commutative algebra) of the fact that {A(n, k)}_{k=1,...,n} is an O-sequence. Note that A_{n}(x) is not in general a Hilbert polynomial, for example A_{2}(x) = ⟨x⟩_{2}.

Some of the combinatorial sequences that have been most studied in enumerative combinatorics are those of the Stirling numbers. Strange as this may seem, we have not found in the literature any result relating to the question of whether these sequences are O-sequences. We answer a more general question in the affirmative here. For n, k, r ∈ P let S_{r}(n, k) be the number of set partitions of [n] into k blocks, each of size ≥ r. The numbers S_{r}(n, k) are usually called the r-associated Stirling numbers of the second kind (see, e.g., [14], Chapter V, Ex. 7, p. 221, for further information about these numbers).

Theorem 4.9 Let r, n ∈ P. Then:

i) {c(n, n − k)}_{k=0,...,n−1} is a Hilbert function;

ii) \{S_{r}(n, k)\}_{k=1,...,⌊ \frac{n}{r} ⌋} is a Hilbert function.

Proof. It is clear from the definitions that 1 + ix is an O-series for all i ≥ 1. But it is well known (see, e.g., [33], Proposition 1.3.4, p. 19) that

∑_{k=0}^{n−1} c(n, n − k)x^{k} = ∏_{i=1}^{n−1}(1 + ix)

so i) follows from part i) of Proposition 2.4.

To prove ii) let V = {S ⊆ [n − 1] : n − r ≥ |S| ≥ r} and Δ =^{def} {F ⊆ V : S ∩ T = ∅ for all S, T ∈ F such that S ≠ T, and ∑_{S∈F} |S| ≤ n − r}. It is then clear that Δ is a simplicial complex on vertex set V. Also,

f_{k−1}(Δ) = S_{r}(n, k + 1)

for all k = 0, …, ⌊\frac{n}{r}⌋ − 1 (since if \{S_{1}, …, S_{k}\} ∈ Δ then \{S_{1}, …, S_{k}, [n] \ (⋃_{i=1}^{k} S_{i})\} is a partition of [n] into k + 1 blocks, each of size ≥ r, and this is a bijection). Hence \{S_{r}(n, k)\}_{k=2,...,⌊\frac{n}{r}⌋} is the f-vector of a simplicial complex and therefore \{S_{r}(n, k)\}_{k=1,...,⌊\frac{n}{r}⌋}, by Theorem 2.3, is an O-sequence. □

We now prove that a rather general class of polynomials arising from the enumeration of Stirling permutations are always Hilbert polynomials. Fix k ∈ P and m_{1}, m_{2}, … ∈ P. Recall (see, e.g., [8], §6.6) that a permutation a_{1}a_{2} … a_{m_{1}+...+m_{k}} of the multiset M_{k} =^{def} {1^{m_{1}}, 2^{m_{2}}, …, k^{m_{k}}} is called a Stirling permutation if 1 ≤ u < v < w ≤ m_{1} + … + m_{k} and a_{u} = a_{w} imply a_{v} ≥ a_{u}. Stirling permutations have been first introduced and studied in [19] in the case m_{1} = … = m_{k} = 2, and later in [18] (in the case m_{1} = … = m_{k}) and [8] (in the general case). We denote by Q_{k} the set of all Stirling permutations of M_{k}. So, for example, Q_{k} = S_{k} if m_{1} = … = m_{k} = 1. Given a permutation π = a_{1}a_{2} … a_{m_{1}+...+m_{k}} of M_{k} a descent of π is an index j ∈ [m_{1} + … + m_{k} − 1] such that a_{j} > a_{j+1}. For 0 ≤ i ≤ |M_{k}| − 1 we let B_{k,i} be the number of Stirling permutations of M_{k} with exactly i descents. So, if m_{1} = … = m_{k} = 1, then B_{k,i} is just the Eulerian number A(k, i + 1). There are (at least) two important generating functions associated with the numbers B_{k,i}, namely

B_{k}(x) =^{def} ∑_{i=0}^{|M_{k}|−1} B_{k,i}x^{i},  (23)

and

f_{k}(x) =^{def} ∑_{i=1}^{|M_{k}|} B_{k,i−1} (\begin{matrix}x+|M_{k}|−i \\ |M_{k}| \end{matrix})  (24)

(see, [8] §6.6, for further information on these two polynomials). As noted in [8], p. 78,

(24) is usually the better behaved of these two generating functions. This turns out to be true also from our present point of view. In fact, we will prove that (23) is always a Hilbert polynomial while {f_{k}(n + 1)}_{n∈N} is always a Hilbert function.

Theorem 4.10 Let k ∈ P and m_{1}, …, m_{k} ∈ P. Then:

i) {f_{k}(n + 1)}_{n∈N} is a Hilbert function;

ii) B_{k}(x) is a Hilbert polynomial.

In particular, f_{k}(x + 1) is a Hilbert polynomial.

Proof. We first prove i) by induction on k ∈ P. If k = 1 then B_{1}(x) = 1 and hence f_{1}(x) = (\begin{matrix}x+m_{1}−1 \\ m_{1} \end{matrix}) = ((\begin{matrix}x \\ m_{1} \end{matrix} )) and the result follows since \{((\begin{matrix}n+1 \\ m_{1} \end{matrix}))\}_{n∈N} is the Hilbert function of k[x_{0}, …, x_{m_{1}}]. So let k ∈ P and assume that ∑_{n≥0} f_{k}(n + 1)x^{n} is an O-series. From Proposition 6.6.1 (see also the proof of Theorem 6.6.2) of [8] we deduce that

∑_{n≥0}(n + 1)f_{k}(n + 1)x^{n} = ∑_{n≥0} ∑_{i=1}^{|M_{k+1}|} B_{k+1,i−1} (\begin{matrix}n+1+|M_{k}|+1−i \\ |M_{k}|+1 \end{matrix}) x^{n}
= \frac{B_{k+1}(x)}{(1 − x)^{|M_{k}|+2}} ,  (25)

by (23) and the binomial theorem (see, e.g., [33], p. 16). Therefore, again by the binomial theorem, we conclude from (23), (24), and (25) that

∑_{n≥0} f_{k+1}(n + 1)x^{n} = \frac{B_{k+1}(x)}{(1 − x)^{|M_{k+1}|+1}} = \frac{1}{(1 − x)^{m_{k+1}−1}} ∑_{n≥0}(n + 1)f_{k}(n + 1)x^{n}. (26)

Since ∑_{n≥0} x^{n} and ∑_{n≥0}(n + 1)x^{n} are both O-series, i) follows from our induction hypothesis and parts i) and iv) of Proposition 2.4.

To prove ii) note that it follows from [8], Proposition 6.6.1 (and it can also be verified directly), that B_{2}(x) = 1 + m_{1}x, and

B_{3}(x) = 1 + (3m_{1} + m_{2})x + m_{1}(m_{1} + m_{2} − 1)x^{2}.

Therefore B_{1}(x) and B_{2}(x) are Hilbert polynomials, and B_{3}(x) is a Hilbert polynomial if m_{1} ≥ 2 or if m_{2} ≥ 3 by part i) of Corollary 3.10. But it can be verified directly, using Proposition 3.4, that 1 + 5x + 2x^{2} and 1 + 4x + x^{2} are also Hilbert polynomials and this proves ii) if k ≤ 3. If k ≥ 4 then we see easily from our definitions that B_{k,1} ≥ 2^{k−1} ≥ 8 and B_{k,2} ≥ 3^{k−3} ≥ 3 (see also Proposition 6.6.1 of [8]) and ii) again follows from part i) of Corollary 3.10. □

Note that the proof of Theorem 4.10 actually yields an inductive procedure for constructing a ring R_{k} having {f_{k}(n + 1)}_{n∈N} as Hilbert function by alternatively taking Segre products and tensor products with polynomial rings on 2 and m_{k} − 1 variables, respectively. It would be interesting to study these rings and the corresponding varieties, and to see whether they can be defined directly in some explicit way. Also, note that, as observed in [8], §6.6, p.79, no combinatorial interpretation of the integers f_{k}(n + 1) is known except in the cases m_{1} = … = m_{k} = 1 and m_{1} = … = m_{k} = 2. While Theorem 4.10 does not provide such a combinatorial interpretation, it does provide an algebraic interpretation. Furthermore, if the rings R_{k} referred to above can be constructed explicitly, then a combinatorial interpretation of their Hilbert function would probably follow.

It is well known (see, e.g., [19]), and also easy to see, that S(n + k, n) is a polynomial function of n, for each k ∈ N. An interesting consequence of Theorem 4.10 is the following.

Corollary 4.11 Let k ∈ N. Then {S(n + 1 + k, n + 1)}_{n∈N} is a Hilbert function. In particular, S(x + 1 + k, x + 1) is a Hilbert polynomial.

Proof. Taking m_{i} = 2 for all i ∈ P yields, by part (ii) of Proposition 6.6.4 of [8], that f_{k}(n+1) = S(n+1+k, n+1) for all n ∈ N, and the result follows from part i) of Theorem 4.10. □

The polynomials S(x + k, x) are usually called Stirling polynomials (see, e.g., [19], or [8], §6.6, p. 80).

Corollary 4.11 can, in turn, be generalized in another direction using the theory of symmetric functions. We need first the following simple observation.

Proposition 4.12 Let f ∈ Λ. Then there exists a (necessarily unique) polynomial \overline{f}(x) ∈ Q[x] such that

\overline{f}(n) = f(1, 2, …, n, 0, 0, …)  (27)

for all n ∈ P.

Proof. It is well known (see, e.g., [25], Chapter I, §2, Ex.11, p. 23), and easy to see, that

S(n + k, n) = h_{k}(1, 2, …, n, 0, 0, …)  (28)

for all n ∈ P and k ∈ N, and that, as noted before Corollary 4.11, S(n + k, n) is a polynomial function of n for all k ∈ N. By definition (see, e.g., [25], Chapter I, §2) we have that

h_{λ}(x_{1}, x_{2}, …) = ∏_{i=1}^{l} h_{λ_{i}}(x_{1}, x_{2}, …)  (29)

if λ = (λ_{1}, …, λ_{l}), hence the result holds for the complete homogeneous symmetric functions h_{λ}, λ ∈ P. But every f ∈ Λ can be expressed as a finite linear combination of h_{λ}’ s, and the result follows. □

Thus Corollary 4.11 is asserting (by (28) and (27)) that {h_{k}(1, 2, …, n + 1)}_{n∈N} is a Hilbert function and \overline{h_{k}}(x + 1) is a Hilbert polynomial. This naturally suggests the problem of determining those symmetric functions f ∈ Λ for which these properties hold.

Theorem 4.13 Let λ ∈ P. Then the following are Hilbert functions:

i) {h_{λ}(1, 2, …, n + 1)}_{n∈N};

ii) {p_{λ}(1, 2, …, n + 1)}_{n∈N}.

In particular, both \overline{h_{λ}}(x + 1) and \overline{p_{λ}}(x + 1) are Hilbert polynomials.

Proof. i) follows immediately from (28), (29), Corollary 4.11, and Proposition 2.4. To prove ii) note that it follows from the definition (see, e.g., [25], Chapter I, §2) that

∑_{n≥0} \overline{p_{k}}(n + 1)x^{n} = (∑_{n≥0} x^{n}) (∑_{n≥0}(n + 1)^{k}x^{n})  (30)

for all k ∈ P. Since ∑_{n≥0} x^{n} and ∑_{n≥0}(n + 1)x^{n} are both Hilbert series this shows, by Proposition 2.4, that \{\overline{p_{k}}(n+1)\}_{n∈N} is a Hilbert function for all k ∈ P. Since, by definition (see, e.g., [25], Chapter I, §2), p_{λ}(x_{1}, x_{2}, …) = ∏_{i=1}^{l} p_{λ_{i}}(x_{1}, x_{2}, …) if λ = (λ_{1}, …, λ_{l}), ii) follows from Proposition 2.4. □

Given a Z-basis {b_{λ}}_{λ∈P} of Λ we say that f ∈ Λ is b-positive if f = ∑_{λ∈P} a_{λ}b_{λ} implies that a_{λ} ≥ 0 for all λ ∈ P. Then Theorem 4.13 has the following immediate consequence.

Corollary 4.14 Let f ∈ Λ be h-positive. Then \overline{f}(x + 1) is a Hilbert polynomial. □

Another consequence of Theorem 4.13 is the following. We denote by B_{k}(x) the k-th Bernoulli polynomial, for k ∈ P (see, e.g., [14], Chap. I, §14, p. 48, for the definition and further information about Bernoulli polynomials).

Corollary 4.15 Let k ∈ P. Then B_{k}(x + 2) − B_{k}(0) is a Hilbert polynomial.

Proof. It is well known (see, e.g., [14], §3.9, p. 155) that (k + 1)\overline{p_{k}}(n + 1) = B_{k+1}(n + 2) − B_{k+1}(0) for all k, n ∈ P. Hence

B_{k+1}(x + 2) − B_{k+1}(0) = (k + 1)\overline{p_{k}}(x + 1)  (31)

and the result follows from Theorems 3.5 and 4.13 and the fact that B_{1}(x+2)−B_{1}(0) = x+2 is a Hilbert polynomial. □

Note that B_{k}(x + 2) cannot be a Hilbert polynomial since, in general, B_{k}(N) ⊄ Z, and that B_{k}(x+1)−B_{k}(0) is not always a Hilbert polynomial (for example, B_{2}(x+1)−B_{2}(0) = x^{2} + x).

5 Open Problems

Despite the fact that Hilbert functions and polynomials are preserved by many natural operations on formal power series and polynomials, respectively (see Proposition 2.4 and Theorem 3.5), there are many sequences and polynomials naturally arising in enumerative and algebraic combinatorics for which we have been unable to decide whether they are Hilbert. In this section we survey the most striking such cases, and we present some conjectures together with the evidence that we have in their favor.

Our first conjecture is naturally suggested by Theorem 4.9. Conjecture 5.1 Let n ∈ P. Then {S(n, n − k)}_{k=0,...,n−1} is a Hilbert function. We have verified this conjecture for n ≤ 24. In addition to the numerical evidence, there is a heuristic reasoning that suggests the validity of Conjecture 5.1. A sequence of positive integers is a Hilbert function if it “does not grow too fast”. Now, it is well known (see, e.g., [14], §7.1, Theorem D, p. 271) that the sequence {S(n, k)}_{k=1,...,n} is log-concave and unimodal, hence the real content of Conjecture 5.1 is for the values of k that precede the mode of the sequence. But it is known (see, e.g., [33], Chapter 1, Exercise 18, p.

47) that the mode of \{S(n, k)\}_{k=1,...,n} is less than ⌊\frac{n}{2}⌋. Hence one expects the sequence {S(n, n−k)}_{k=0,...,n−1} to grow “less rapidly” than {S(n, k)}_{k=1,...,n} and therefore we expect Conjecture 5.1 to be true since Theorem 4.9 holds.

Theorem 3.8 allows one to settle the question of whether a given polynomial is Hilbert pretty easily if its coefficients with respect to the basis {x^{i}}_{i∈N} are nonnegative and have a combinatorial interpretation. However, there are many polynomials for which this is not the case (especially polynomials that “count something” when evaluated at nonnegative integers) but that seem to be Hilbert. In this respect, we feel that the following is the most interesting and outstanding open problem arising from the present work. Conjecture 5.2 Let G be a graph on at least 4 vertices, and χ(G; x) be its chromatic polynomial. Then χ(G; x) is a Hilbert polynomial.

We have verified the above conjecture for all graphs with at most 15 vertices. Two related conjectures are the following.

Conjecture 5.3 Let d ∈ P, d ≥ 4. Then (x)_{d} is a Hilbert polynomial.

Conjecture 5.4 Let d ∈ P. Then 3d (\begin{matrix}x \\ d \end{matrix}) is a Hilbert polynomial.

We have verified these conjectures for d ≤ 15. Note that, by Proposition 4.2, Conjectures 5.2 and 5.3 are equivalent, while by Theorem 3.5 Conjecture 5.4 implies Conjecture 5.3.

For what concerns the symmetric functions f ∈ Λ such that \overline{f}(x + 1) is a Hilbert polynomial we have the following conjectures.

Conjecture 5.5 Let λ ∈ P. Then \overline{s_{λ}}(x + 1) is a Hilbert polynomial if and only if |λ| ≥ 3.

Conjecture 5.6 Let λ ∈ P. Then \overline{m_{λ}}(x+1) is a Hilbert polynomial if and only if |λ| ≥ 3.

We have verified the above conjectures for |λ| ≤ 7. Note that since any Schur symmetric function is m-positive (see, e.g., [25], Chapter I, §6), Conjecture 5.6 implies Conjecture 5.5 as well as Corollary 4.14.

While the specialization f ↦ f(1, 2, …, n + 1, 0, 0, …), for f ∈ Λ, has been suggested by Corollary 4.11, there is one other specialization which is routinely used in the theory of symmetric functions (see, e.g., [25], Chapter I, §2, Ex. 1, and §3, Ex. 4) namely f ↦ f(\underbrace{1, 1, …, 1}_{n}, 0, 0, …). Since it is easy to verify that f(\underbrace{1, 1, …, 1}_{n}, 0, 0, …) is a polynomial

function of n for any f ∈ Λ (see, e.g., [8], Proposition 6.2.1), it is natural to wonder for which symmetric functions f ∈ Λ one has that f(\underbrace{1, 1, …, 1}_{n+1}, 0, 0, …) is a Hilbert polynomial

(as a function of n). The answer for the p_{λ}’ s is of course trivial. For the Schur functions we believe that the following holds.

Conjecture 5.7 Let λ = (λ_{1}, …, λ_{r}) ∈ P be such that |λ| ≥ 7. Then s_{λ}(\underbrace{1, 1, …, 1}_{n+1}, 0,

0, …) is a Hilbert polynomial if and only if λ_{1} + λ_{2} ≥ 4.

We have verified Conjecture 5.7 for |λ| ≤ 12. It is worth noting that the “only if” part of Conjecture 5.7 also holds for 4 ≤ |λ| ≤ 6 (but not the “if” part, take, e.g., λ = (3, 3), (2, 2, 2), (2, 2, 1), or (3, 1)). What makes Conjecture 5.7 particularly tantalizing is that there is an explicit closed formula for s_{λ}(\underbrace{1, …, 1}_{n+1}, 0, 0, …), namely

s_{λ}(\underbrace{1, …, 1}_{n+1}, 0, 0, …) = ∏_{(i,j)∈λ} (\frac{n + 1 + j − i}{h(i, j)}) ,  (32)

where h(i, j) is the hook length of (i, j) in λ (see, e.g., [25], Chapter I, §1, Ex. 1, and §3, Ex. 4). This allows us to conclude in particular, by part vi) of Theorem 3.8, that Conjecture 5.7 does hold if l(λ) = 1 (i.e., for complete homogeneous symmetric functions) or if λ_{1} = 1 (i.e., for elementary symmetric functions). Note that s_{λ}(\underbrace{1, 1, …, 1}_{n}, 0, 0, …)

is also equal to the order polynomial of a column strict labeled Ferrers poset of shape λ (see, e.g., [8], §5.2, for further information). The monomial symmetric functions seem to exhibit an extremely mysterious behavior and we have been unable to extract any general conjecture from the data that we have. For example, if |λ| ≤ 8 and l(λ) ≥ 2 then we have verified that m_{λ}(\underbrace{1, …, 1}_{n+1}, 0, 0, …) is a Hilbert polynomial if and only if

λ ∈ {(3, 2, 1), (4, 2, 1), (3, 2, 1, 1), (2, 2, 1, 1, 1, 1), (3, 2, 1, 1, 1), (3, 2, 2, 1), (4, 2, 1, 1), (4, 3, 1), (5, 2, 1)}.

The results in section 3 also suggest several open problems. In particular, it would be interesting to answer the following questions, which are naturally suggested by Theorems 3.12 and 3.13. Problem 5.8 Let \{h_{0}, …, h_{d}\} be a Hilbert function. Is it true that then ∑_{i=0}^{d} h_{i} ((\begin{matrix}x \\ i \end{matrix})) is a Hilbert polynomial?

Problem 5.9 Let (f_{0}, …, f_{d}) be the f-vector of a simplicial complex. Is it true that then

∑_{i=0}^{d} f_{i}(x)_{i}, ∑_{i=0}^{d} f_{i} (\begin{matrix}x+d−i \\ d \end{matrix}), and ∑_{i=0}^{d} f_{i} ((\begin{matrix}x \\ i \end{matrix})) are Hilbert polynomials?

Finally, there is a general “open problem” that arises naturally with almost any result presented in this work. Namely, whenever we prove that a certain polynomial (or sequence) is Hilbert it is natural to wonder whether one can construct, in a natural way, a standard graded k-algebra having the given Hilbert polynomial or function. Besides giving a more illuminating proof of the original result, such a graded algebra would probably have interesting properties in its own right. We have not investigated this problem. However, we do believe that natural constructions of graded algebras exist that “explain” all parts of Theorems 3.5, 3.12, 3.13, and 4.7.

Acknowledgements. I would like to thank Fan Chung, Claudio Procesi, Richard Stanley, John Stembridge, and Bernd Sturmfels for useful conversations. Some of the computations in this paper have been carried out using a Maple package for handling symmetric functions developed by John Stembridge.

References

[1] D. Alvis, The left cells of the Coxeter group of type H_{4}, J. Algebra, 107 (1987), 160-168.

[2] I. Anderson, Combinatorics of Finite Sets, Oxford Science Publications, Clarendon Press, Oxford, 1987.

[3] M. F. Atiyah and I. G. Macdonald, Introduction to Commutative Algebra, Addison-Wesley, 1969.

[4] D. Bayer, Chromatic polynomials and Hilbert functions, preprint.

[5] A. Björner, Some combinatorial and algebraic properties of Coxeter complexes and Tits buildings, Adv. in Math., 52 (1984), 173-212.

[6] A. Björner, Face numbers of complexes and polytopes, Proceedings of the Int. Congress of Mathematicians, Berkeley, California, U.S.A., 1986, 1408-1418.

[7] A. Björner, A. Garsia, and R. Stanley, An introduction to Cohen-Macaulay partially ordered sets, in Ordered Sets (I. Rival, Editor), Reidal, Dordrecht/Boston, 1982, 583-615.

[8] F. Brenti, Unimodal, log-concave, and Pólya Frequency sequences in Combinatorics, Memoirs Amer. Math. Soc., no.413, 1989.

[9] F. Brenti, Expansions of chromatic polynomials and log-concavity, Trans. Amer. Math. Soc., 332(1992), 729-756.

[10] F. Brenti, G. Royle, and D. Wagner, Location of zeros of chromatic and related polynomials of graphs, Canadian J. Math., 46 (1994), 55-80.

[11] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, Europ. J. Combinatorics, 15(1994), 417-441.

[12] W. Bruns and J. Herzog, Cohen-Macaulay Rings, Cambridge, Studies in Advanced Mathematics, no. 39, Cambridge Univ. Press, Cambridge, 1993.

[13] G. Clements and B. Lindström, A generalization of a combinatorial theorem of Macaulay, J. Combinatorial Theory, 7(1969), 230-238.

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

[15] V. V. Deodhar, On some geometric aspects of Bruhat orderings. I. A finer decomposition of Bruhat cells, Invent. Math. 79 (1985), 499-511.

[16] P. Edelman, Chain enumeration and non-crossing partitions, Discrete Math., 31(1980), 171-180.

[17] D. Foata and M. Schutzenberger, Theorie geometrique des polynomes euleriens, Lecture Notes in Mathematics, no.138, Springer-Verlag, Berlin-New York, 1970.

[18] I. Gessel, A note on Stirling permutations, preprint.

[19] I. Gessel and R. Stanley, Stirling polynomials, J. Combinatorial Theory (A), 24(1978), 24-33.

[20] R. Hartshorne, Connectedness of the Hilbert scheme, Publ. Math. de l’I.H.E.S., No.29 (1966), 5-48.

[21] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no.29, Cambridge Univ. Press, Cambridge, 1990.

[22] D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165-184.

[23] D. Kazhdan and G. Lusztig, Schubert varieties and Poincaré duality, Geometry of the Laplace operator, Proc. Sympos. Pure Math. 34, Amer. Math. Soc., Providence, RI, 1980, pp. 185-203.

[24] F. S. Macaulay, Some properties of enumeration in the theory of modular systems, Proc. London Math. Soc., 26 (1927), 531-555.

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

[26] R. C. Read, An introduction to chromatic polynomials, J. Combinatorial Theory, 4(1968), 52-71.

[27] R. C. Read and W. T. Tutte, Chromatic polynomials, in Selected Topics in Graph Theory 3 (Beineke and Wilson, editors), Academic Press, New York, 1988.

[28] L. Roberts, Hilbert polynomials and minimum Hilbert functions, Queen’s Papers in Pure and Applied Mathematics, No. 61, (The Curves Seminar at Queen’s, Vol. II, A. V. Geramita, editor), 1982, Queen’s University, Kingston (Ontario).

[29] R. Stanley, Ordered Structures and Partitions, Memoirs Amer. Math. Soc., no.119, 1972.

[30] R. Stanley, Hilbert functions of graded algebras, Adv. in Math., 28 (1978), 57-83.

[31] R. Stanley, An Introduction to combinatorial commutative algebra, in Enumeration and Design, (D. M. Jackson and S. A. Vanstone, editors), Academic Press, Toronto,1984, 3-18.

[32] R. P. Stanley, Combinatorics and Commutative Algebra, Birkhäuser, 1983.

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

[34] R. P. Stanley, private communication, 1987.

Mathematical Sciences Research Institute 1000 Centennial Drive Berkeley, CA 94720-5070 U.S.A.