Multigraded Hilbert Series and Applications

by Martin Kreuzer (Dortmund) and Lorenzo Robbiano (Genova)

Entertainment for Bored People

Find all triples of non-negative integers (x, y, z) ∈ ℕ^{3} such that

3x − 5y + 4z = 0

1. Multigradings.

K field, P = K[x_{1}, …, x_{n}] polynomial ring

In this conference we shall encounter some bigradings (i.e. ℤ^{2}-gradings) on P. Which conditions should a ℤ^{m}-gra-ding on P satisfy in order to be useful for computer algebra?

Wish 1: The set of degrees of homogeneous polynomials should be well-ordered. There should be no infinite sequence of stictly decreasing degrees. (Finiteness of algorithms!) Wish 2: The graded version of Nakayama’s Lemma should hold. There should be a well-behaved notion of “minimal number of generators”.

Wish 3: The homogeneous components of finitely generated graded modules should be finite dimensional K-vector spaces. Hilbert functions and Hilbert series should exist. Wish 4: A degree-compatible term ordering σ should exist. We should be able to compute homogeneous objects by using σ-Gröbner bases. Wish 5: There should be an effective and well-defined way to compare degrees. One should be able to compute “degreeby-degree”.

Definition. Let w_{1}, …, w_{n} ∈ ℤ^{m}.

a) There exists a unique ℤ^{m}-grading on P such that K ⊆ P_{0} and x_{i} is homogeneous of multidegree w_{i} for i = 1, …, n. We form the matrix W = (w_{1} w_{2} ⋯ w_{n}) and say that P is graded by W.

b) The grading by W is called weakly positive if there exists a ℤ-linear combination of the rows of W all of whose entries are positive.

c) The grading by W is called positive if rank(W) = m, no column of W is zero and the first non-zero entry in each column of W is positive.

Proposition. Let P be graded by W ∈ Mat_{m,n}(ℤ).

a) If the grading is weakly positive, then wishes 1), 2), and 3) come true.

b) If the grading is positive, then it is weakly positive. Moreover, wishes 1) – 5) come true.

The proof will be contained in M. Kreuzer and L. Robbiano, Computational Commutative Algebra II, Springer Verlag 2004 (in preparation)

2. Multigraded Hilbert Series From now on let P always be weakly positively graded

by W ∈ Mat_{m,n}(ℤ). Definition. Let M be a finitely generated graded P -module.

a) The map HF_{M} : ℤ^{m} ⟶ ℤ given by

HF_{M}(i_{1}, …, i_{m}) = dim_{K}(M_{(i_{1},...,i_{m})})

is called the multigraded Hilbert function of M.

b) The series HS_{M}(z_{1}, …, z_{m}) = ∑_{i∈ℤ^{m}} HF_{M}(i) z_{1}^{i_{1}} ⋯ z_{m}^{i_{m}}

is called the multigraded Hilbert series of M.

Problem: Which object contains all multigraded Hilbert series? (It should be a ring!)

Remark. The group

ℤ[[z_{1}, …, z_{m}, z_{1}^{−1}, …, z_{m}^{−1}]]

is not a ring, since (1 + z_{1} + z_{1}^{2} + ⋯) · (1 + z_{1}^{−1} + z_{1}^{−2} + ⋯) cannot be defined. Example Let P = K[x_{1}, x_{2}] be graded by W = \binom{1 1}{0 −1}. Then the homogeneous component of multidegree (d_{1}, d_{2}) of P is K · x_{1}^{d_{1}+d_{2}}x_{2}^{−d_{2}}. Therefore we have

HS_{P} (z_{1}, z_{2}) = ∑_{(d_{1},d_{2})∈ℤ^{2}} z_{1}^{d_{1}+d_{2}}z_{2}^{−d_{2}}

Thus the multivariate Laurent series ring ℤ[[z_{1}, …, z_{m}]]_{z_{1}···z_{m}} does not contain all multigraded Hilbert series. Definition. Let σ be a monoid ordering on ℤ^{m}.

a) An element f ∈ ℤ[[z, z^{−1}]] is called a σ-Laurent series if Supp (f) is well-ordered by σ.

b) The set of all σ-Laurent series forms a ring ℤ[[z, z^{−1}]]_{σ} which is called the σ-Laurent series ring. Proposition. a) If P is weakly positively graded by W, then there exists a monoid ordering σ on ℤ^{m} which is a wellordering on the set of degrees of homogeneous elements of a non-zero finitely generated graded P -module.

b) If P is positively graded by W, we can take σ = Lex.

Proposition. (Basic Properties of HS_{M}) Let P be weakly positively graded by W.

a) We have HS_{P} (z_{1}, …, z_{m}) = _{\frac{1}{∏_{j=1}^{n}(1−z_{1}^{w_{1j}} ···z_{m}^{w_{mj}})}}.

b) The shifted module M(d), where M(d)_{i} = M_{d+i} for i ∈ ℤ^{m}, satisfies HS_{M(d)}(z) = z^{−d} HS_{M}(z).

c)HS_{M} is additive on homogeneous short exact sequences.

d) For a graded submodule M of a graded free P -module F = ⨁_{i=1}^{r} P (−δ_{i}) and a module term ordering σ we have HS_{M}(z) = HS_{LT_{σ}(M)}(z).

e) Under a field extension K ⊆ L, we have HS_{M⊗L}(z) = HS_{M}(z).

f) The usual algorithm for computing HS_{M} in the standard graded case continues to work in the multigraded case.

g) The series HS_{M}(z) has the shape

HS_{M}(z) = \frac{z^{α} HN_{M}(z)}{∏_{j=1}^{n}(1 − z_{1}^{w_{1j}} ⋯ z_{m}^{w_{mj}})}

where HN_{M}(z) ∈ ℤ[z] is called the multivariate Hilbert numerator of M.

h) (Change of Gradings) Let A = (a_{ij}) ∈ Mat_{r,m}(ℤ) be such that A · W defines a weakly positive grading on P. Then we have M_{W,d} = M_{AW,Ad} for all d ∈ ℤ^{m} and

HS_{M,AW} (z) = HS_{M,W} (z_{1}^{a_{11}} ⋯ z_{r}^{a_{r1}}, …, z_{1}^{a_{1m}} ⋯ z_{r}^{a_{rm}})

3. Hilbert Bases.

Let P be weakly positively graded by W. Let 1 ≤ ℓ ≤ m and A = (I_{ℓ} 0) ∈ Mat_{ℓ,m−ℓ}(ℤ). Then the matrix U = AW is the upper part of W, i.e. W is of the form W = \binom{U}{V}. We say that the grading given by W is a refinement of the grading given by U. Proposition. (Hilbert Series and Refinements) Let M be a finitely generated graded P -module.

a) Let o = (0, …, 0) ∈ ℤ^{ℓ} and (P_{U,o})_{e} = P_{(o,e)} for all e ∈ ℤ^{m−ℓ}. Then P_{U,o} is a finitely generated graded K-algebra which is graded by V.

b) Let (M_{U,d})_{e} = M_{(d,e)} for d ∈ ℤ^{ℓ} and e ∈ ℤ^{m−ℓ}. Then M_{U,d} is a finitely generated graded P_{U,o}-module.

c) HS_{M_{U,d},V} (z̃_{1}, …, z̃_{m−ℓ}) = ∑_{e∈ℤ^{m−ℓ}} dim_{K}(M_{(d,e)}) z̃^{e} d) If P is weakly positively graded by U, then we have

dim_{K}(M_{U,d}) < ∞ for all d ∈ ℤ^{ℓ} and

HS_{M,U}(z_{1}, …, z_{ℓ}) = HS_{M,W} (z_{1}, …, z_{ℓ}, 1, …, 1)

The most difficult part of the proof is a). We have

P_{U,o} = ⟨x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} | U · (α_{1}, …, α_{n})^{tr} = 0; α_{1}, …, α_{n} ∈ ℕ⟩

We need a description of the set of all such (α_{1}, …, α_{n}).

Definition. Let A = (a_{ij}) ∈ Mat_{m,n}(ℤ) and z = (z_{1}, …, z_{n}).

a) The subgroup of ℤ^{n} of solutions of A·z = 0 is denoted by L(A). Morevoer, let L_{+}(A) = L(A) ∩ ℕ^{n}.

b) For j = 1, …, s, let t_{j} = y_{1}^{a_{1j}} ⋯ y_{m}^{a_{mj}} ∈ L = K[y, y^{−1}] be the Laurent power product associated to the j^{th} column of A.

c) Let φ : P ⟶ L be defined by φ(x_{i}) = t_{i} for i = 1, …, n. Then I(A) = ker(φ) is called the toric ideal of A.

Proposition. (Computation of Toric Ideals) Let f = y_{1} ⋯ y_{m}. For j = 1, …, n, let p_{j} = min{i | f^{i} t_{j} ∈ K[y_{1}, …, y_{m}]} and t′_{j} = f^{p_{j}} t_{j}.

a) I(A) = [(f^{p_{1}}x_{1} − t′_{1}, …, f^{p_{n}}x_{n} − t′_{n}) : f^{∞}] ∩ P

b) I(A) is generated by pure binomials, i.e. by polynomials x^{α} − x^{β} such that gcd(x^{α}, x^{β}) = 1.

Definition. Let A ∈ Mat_{m,n}(ℤ). On L_{+}(A) we define a partial ordering ≻ by (α_{1}, …, α_{n}) ≻ (β_{1}, …, β_{n}) ⟺ ⟺ α_{i} ≥ β_{i} for i = 1, …, n.

a) The set of minimal elements of L_{+}(A) \ {0} with respect to ≻ is called the Hilbert basis of L_{+}(A).

b) The matrix Ā = \binom{A 0}{I_{n} I_{n}} ∈ Mat_{m+n,2n}(ℤ) is called the Lawrence lifting of A.

Theorem. (Computation of Hilbert Bases) Let A = (a_{ij}) ∈ Mat_{m,n}(ℤ) and let G be a reduced Gröbner basis of I(Ā) ⊆ K[x_{1}, …, x_{n}, w_{1}, …, w_{n}]. then the set

H = {α ∈ ℕ^{n} | x^{α} − w^{α} ∈ G}

is the Hilbert basis of L_{+}(A).

Proposition. Let H be the Hilbert basis of L_{+}(A). Then every element of the monoid L_{+}(A) is an ℕ-linear combination of the elements of H.

Example. Consider A = (3, −5, 4). The Lawrence lifting of A is

Ā = ( \begin{matrix}3 & −5 & 4 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{matrix} )

Using CoCoA, we find I(Ā) = (x_{2}x_{3}^{2}w_{1} − x_{1}w_{2}w_{3}^{2}, x_{3}w_{1}^{3}w_{2} − x_{1}^{3}x_{2}w_{3}, x_{1}^{2}x_{2}^{2}x_{3}−w_{1}^{2}w_{2}^{2}w_{3}, x_{3}^{3}w_{1}^{4}−x_{1}^{4}w_{3}^{3}, x_{1}^{5}x_{2}^{3}−w_{1}^{5}w_{2}^{3}, x_{2}^{4}x_{3}^{5}− w_{2}^{4}w_{3}^{5}, x_{1}x_{2}^{3}x_{3}^{3} − w_{1}w_{2}^{3}w_{3}^{3}). Hence the Hilbert basis of L_{+}(A) is

{(2, 2, 1), (5, 3, 0), (0, 4, 5), (1, 3, 3)}

4. Application to Weakly Positive Matrices Question: Does there exists a vector with positive coordinates which is a linear combination of the vectors (−1, 5, 5) and (−2, 13, −12) ?

In other words, is the grading defined by W = \binom{−1 5 5}{−2 13 −12} weakly positive?

Answer: We need to find (z_{1}, …, z_{5}) ∈ ℤ^{5} such that

\begin{aligned}−z_{1} − 2z_{2} & = z_{3} + 1 \\ 5z_{1} + 13z_{2} & = z_{4} + 1 \\ −5z_{1} − 12z_{2} & = z_{5} + 1 \end{aligned}

and such that z_{3}, z_{4}, z_{5} ∈ ℕ. Using a slight generalization of the above theory, we find the solution (−5, 2, 0, 0, 0). Hence we have

−5 (−1, 5, −5) + 2 (−2, 13, −12) = (1, 1, 1)

i.e. the grading defined by W is weakly positive.

5. Application to Magic Squares Question: In 1514, Albrecht Dürer painted the famous Jupiter magic square

( \begin{matrix}16 & 3 & 2 & 13 \\ 5 & 10 & 11 & 8 \\ 9 & 6 & 7 & 12 \\ 4 & 15 & 14 & 1 \end{matrix} )

How many magic squares with magic sum 34 are there?

In fact, Dürer’s square is supermagic in the sense that all 2x2 submatrices centered on the main diagonal also have magic sum 34. How many supermagic squares with magic sum 34 are there?

Answer: There are two methods for solving the first problem.

1) Using multigraded Hilbert series:

Consider a polynomial ring P = K[y_{11}, y_{12}, …, y_{44}] in 16 indeterminates. We equip it with the ℤ^{10}-grading defined by the matrix W =

( \begin{matrix}1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \end{matrix} )

A tuple (α_{11}, …, α_{44}) ∈ ℕ^{16} defines a magic 4x4 square with magic sum s if and only if the power product y_{11}^{α_{11}} ⋯ y_{44}^{α_{44}} has multidegree W · (α_{11}, …, α_{44})^{tr} = (s, s, …, s). Therefore the number of such magic squares is the coefficient of z_{1}^{s} ⋯ z_{10}^{s} in the multigraded Hilbert series of P.

2) Using Hilbert bases:

Let a 4x4 square again be given by a tuple (a_{11}, …, a_{44}) ∈ ℤ^{16}. It is magic if and only if the linear system of equations A z = 0 is satisfied, where A =

( \begin{matrix}1 & 1 & 1 & 1 & −1 & −1 & −1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & −1 & −1 & −1 & −1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & −1 & −1 & −1 \\ 0 & 1 & 1 & 1 & −1 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & −1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & −1 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & −1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & −1 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & −1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & −1 \\ 0 & 1 & 1 & 1 & 0 & −1 & 0 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & 0 & −1 \\ 1 & 1 & 1 & 0 & 0 & 0 & −1 & 0 & 0 & −1 & 0 & 0 & −1 & 0 & 0 & 0 \end{matrix} )

Thus we need to compute the Hilbert basis of L_{+}(A) as above. It consists of 20 magic squares v_{1}, …, v_{20}, eight of which have magic sum 1 and 12 of which have magic sum 2.

In order to find the number of magic squares with magic sum 34, we compute the Hilbert function of K[x^{v_{1}}, …, x^{v_{20}}] in degree 34 and find that there are

163, 890, 864

of them. Similarly, we can compute that the number of supermagic squares of magic sum 34 is

12, 186, 468

6. Application to Statistics A 2x2 contingency table with margins (b_{1}, b_{2}, c_{1}, c_{2})

is an array of natural numbers of the form

( \begin{matrix}a_{11} & a_{12} & b_{1} \\ a_{21} & a_{22} & b_{2} \\ c_{1} & c_{2} \end{matrix} )

such that b_{1} = a_{11} +a_{12} and b_{2} = a_{21} +a_{22} and c_{1} = a_{11} +a_{21} and c_{2} = a_{12} + a_{22}. Question: How many contingency tables with margins (20, 39, 27, 32) are there? Answer: Again we can use either multigraded Hilbert series or Hilbert bases. For the first method, we equip the polynomial ring P = K[x_{1}, x_{2}, x_{3}, x_{4}] with the ℤ^{4}-grading defined by

W = ( \begin{matrix}1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{matrix} )

and compute the coefficient of z_{1}^{20}z_{2}^{39}z_{3}^{27}z_{4}^{32} in the multigraded Hilbert series of P. The result is 21.

For the second method, we introduce 8 indeterminates a_{ij}, b_{k}, c_{ℓ} and compute a Hilbert basis for the monoid of nonnegative solutions of the above system of four equations. Using the elements of that Hilbert basis, we can actually determine the 21 solutions of our problem: \binom{0 20}{27 12}, \binom{1 19}{26 13}, \binom{2 18}{25 14}, \binom{3 17}{24 15}, \binom{4 16}{23 16}, \binom{5 15}{22 17}, \binom{6 14}{21 18}, \binom{7 13}{20 19}, \binom{8 12}{19 20}, \binom{9 11}{18 21}, \binom{10 10}{17 22}, \binom{11 9}{16 23}, \binom{12 8}{15 24}, \binom{13 7}{14 25}, \binom{14 6}{13 26}, \binom{15 5}{12 27}, \binom{16 4}{11 28}, \binom{17 3}{10 29}, \binom{18 2}{9 30}, \binom{19 1}{8 31}, \binom{20 0}{7 32}