# Full text of "Inductive proof of Macaulay's theorem"

## See other formats

Robotics Research
l^hnical Report

Inductive Proof of Macaulay's Theorem

by

Thomas Dubd

Technical Report No. 455

Robotics Report No. 202

June, 1989

\.

in
Eh

cj e
w o

SEh

o
o

e

O U

o

o x:

O 4J

Q4 w

r-i

Z3

o

c s

New York University
iint Institute of Mathematical Sciences

Computer Science Division

25 1 Mercer Street New York, N.Y 1 00 1 2

0T9""»::

in- ■

'(a

m .,

t ■

\r

. jp

1'

W- ,. -.

9

.*■

if

.:*

*.-"■

t":

. ^w i^

*

■t .

:# " It- i* ,
a' i:!;- ;5k >?«; ^.

^ :

'I*

it »

5* "

Inductive Proof of Macaulay's Theorem
by

Thomas Dubd

Technical Report No. 455

Robotics Report No. 202

June, 1989

New York University

Dept. of Computer Science

Courant Institute of Mathematical Sciences

251 Mercer Street

New York, New York 10012

Work on this paper has been supported by National Science Foundation Grant CCR-87-
03458.

Inductive Proof of Macaulay's Theorem

Thomas W. Dube

June 9, 1989

Abstract

Macaulay's theorem states that for every ideal / in a multi-variate
polynomial ring A = K[xi, . . . ,!„] there is a lexicographic monomial
ideal Lj such that L/ has the same Hilbert function as /. This theorem
allows one to characterize exactly the form of Hilbert polynomials.

This report uses a recursive characterization of a Borel-fixed mono-
mial ideal to provide a new inductive proof of Macaulay's famous
theorem.

1 Introduction

A power product A = Xj'x2"---x^" is lexicographically greater than B =
Xj'xj^ • • • ^n" if the first exponent at which they differ has a, > 6,. This
relationship is written as A>B and defines a total ordering on the set of
power products. The word degree will be used to refer to the total-degree
of a power product, i.e.

deg(xj'x^^--.x-) = J2a,

:=1

A monomial ideal L is called a lexicographic ideal if for every B E L
all the power products A with deg(yl) = deg(fi) and A> B are also in the
ideal L.

Theorem 1 (Macaulay) For any homogeneous polynomial ideal I there
exists a lexicographic ideal L such that I and L share the same Hilbert
function.

1 INTRODUCTION 2

This theorem was first proved in the classic paper by Macaulay [Ma 27].
As a corollary of this theorem, Macaulay was able to characterize the class
of polynomials which may occur as the Hilbert polynomials of ideals.

Corollary 2 Let I be a non-zero ideal of K\xi, . . . ,Xrx]- Then the Hilbert
polynomial of I can be expressed uniquely in the form

vM = zrvrr +i

where mo > rni > m^ > • • • > "^n-2 ^ 0-

Conversely, for every polynomial f{z) which has this form, there exists a

lexicographic ideal L such that '<Pi{z) — f{z).

This corolla'"y can be proved relativeb easily by considering the Hilbert
polynomials of lexicographic ideals. Ti.i Hilbert polynomial of a lexico-
graphic ideal is completely defined by considering the >-last power product

in the ideal. If this power product is >1 = Xj'Xj^ •••x°", then the Hilbert
polynomial has the form given above with

n-i-l

m, = ^ a, .

k=l

Macaiilay's theorem is more powerful than the corollary in lat the
theorem uates a property of the Hilbert function, while the corollary only
considers the Hilbert polynomial which is valid at large degrees. Macaulay
prefaced the original proof of his theorem with the warning:

It is too long and complicated to provide any but the most

The theorem has been often reproved, and the proofs are becoming shorter
and less tedious. Clements and Lindstrom [CILi 69] for example provides
a very readable proof. However, the subtlety of the theorem continues
to thwart those who attempt concise proofs. As recently as 1982, after
providing a proof of the theorem in his thesis, Bayer comments:

It would seem that such an obvious statement would lend itself
to a simpler proof, but after rejecting many false statements,
this author was unable to find one.

2 BACKGROUND 3

This report comprises yet anotlier proof of Macaulay's theorem. Although
it is hoped that the new proof is no worse than the ones already in the
literature, there is no claim that it is any better. The proof is provided
primarily els a further demonstration of the use of cone decompositions.
Once again, a decomposition of the ideal allows an inductive proof of a
constructive nature. The particular characterization of Borel fixed ideals
used in the proof may also be employed in other problems concerning these
ideals.

2 Background

2.1 Lexicographic Ideals

Recall the definition of a lexicographic ideal L: If a degree d power product
t is in L, then every degree d power product s which is lexicographically
greater than t is also in L.

Notation: For a lexicographic ideal L, let id denote the last degree d power
product in L. If L contains no power products of degree d than id is defined
to be 0.

The ideal L is fully defined by listing the set

{io, £i, i2, . . •} ,

since any power product p is in L if and only if p>ideg(p)-

Lemma 3 For any power product < = i"' • • • i^", the set of power products
{s : deg(5) < deg(f) &: s>t} generates a lexicographic ideal L whose power

products are {p : p>t}.

L

t}.
L

Proof. Let / and L denote the following ideals:

/ = ({s : deg(5) < deg(t) & s>t})

L

L = ({p : p>t}).

L

Then L is a lexicographic ideal with id the lexicographically last degree d
power products satisfying id>t.

L

2 BACKGROUND 4

LCI: For p = x\' ■ ■ ■ x^" G L, let j be the first index such that a^ 7^ 6j.
Since p>t it follows be the definition of the lexicographic ordering

that bj > Cj. Let tj = x"' • • ■x^-' be the projection of t onto the first
j variables. There are two cases to consider:

1. tj = t. In this case p is a multiple of t and hence in I.

2. deg(ij) < deg{t). Then s = Xjtj is in the basis for /, and p is a
multiple of s.

I C L: Assume otherwise and let p be a power product in / — L. Since
p ^ L, it follows that p<t. In the basis of /, every power product 5

satisfies s>t. Now since p E I, p = as where 5 is a basis element of

L

p<t<s<as = p .

L L L

D

The ideal L described by this lemma will be called the lexicographic ideal
defined by t .

2.2 Borel Fixed Ideals

Definition: A monomial ideal / is said to be Borel-fixed if it is invariant
under an upper-trangular linear change of coordinates. In practice, it is
often convenient to use one of the equivalent definitions:

1. A monomial ideal / is Borel-fixed if for each pair of variables x,. Zj
such that i < j,

XjM € / implies i.M G / .

2. A monomial ideal / is Borel-fixed if

i,+iM e / implies x.M e / .

This can be sharpened to provide the following effective criteria for a Borel-
fixed ideal.

3 BOREL FIXED SETS 5

Lemma 4 Let I be a monomial ideal generated by a set of monomials
F = {/i, . . . , fr}, and let d be the maximum of the degrees of the /, . Then,
I is Borel fixed if and only if for each monomial M with deg(A/) < d

Xi+iM e / implies x,M G I .

Proof. The implication in the => direction follows from the definition.

Conversely, assume that for deg(A/) < d, x,+iM G / implies x,M E I.
For any i and monomial M such that x,+iM G /, it must be shown that
x,M € /. Since F is a monomial basis for /, x,+iM — f^P for some fj and
monomial P. If the exponent of Xi+i in P is nonzero, then M G /, and
hence x,M t /. Otherwise, fj = x,+iN for some A'^, then x.A'^ G / and
therefore x,M = x,NP G /.
D

In [Ba 82], [Gi 84] a key step in the analysis of Grobner basis complexity
is the transformation to generic coordinates. In this usage, generic coordi-
nates for an ideal / refers to a coordinate system where the head ideal of /
w.r.t the reverse lexicographic ordering is Borel-fixed. The term generic is
used because after nearly any random change of coordinates this condition
will occur.

[Ba 82] provides an informal proof that if the coefficient field K is infi-
nite, then almost all linear upper triangular coordinate changes result in a
transformation to generic coordinates. This same conclusion follows from
(Ga 73], but there analytical methods are employed. jDu 88a] provides a
formal construction which shows that if the coefficient field is infinite, than
a generic coordinate system can always be found.

3 Borel Fixed Sets

This section is used to establish several properties of sets which are Borel
fixed. A new recursive characterization of Borel fixed sets will also be
presented.

We begin by listing three simple properties of Borel fixed sets. These
properties are all easily verifiable, and the proofs will be omitted. Let B
be an arbitrary Borel fixed set. Then,

1. For j — I,.. . ,n, B f] PP[ii,. . . ,Xj] is Borel fixed.

3 BOREL FIXED SETS 6

2. For any degree d, let g be the lexicographically last power product in
B. Then B - {g} is Borel fixed.

3. For any degree d, let h be the lexicographically first power product
not in B. Then B U {h} is Borel fixed.

Now, for any set B of degree d > power products [d > 1) partition B into
the sets i?i(B),i?2(-B), . . . ,i?„(5) where 6 e B is in the subset Ri{B) if i,
is the last variable which has a non-zero exponent in 6. In other words,

R,{B) = {xf-'-xf' eB : a,>0} .

Since every power product in the set R,{B) has a non-zero exponent of x,,
the set Rt{B) can be put in a one-to-one correspondence with the set

S,(B) = {x;'h : heR,(B)} .

And so,

B = ®r=i{^.^ : ^e S,[B} .
The definition of the sets 5,(5) now allows a powerful recursive character-
ization of a Borel fixed set.

Lemma 5 A set B e PP(xi, . . . ,Xnl of degree d power products ts Borel
fixed if and only if

1. 5 n PP[ii,. . .,x„_i] is Borel fixed.

2. Sr,{B) is Borel fixed.

S. 5„(5;nPP[xi,...,x„_i]C5„_a(B).

The simple proof of this lemma will follow this paragraph, but first the
statement of this lemma deserves a bit of discussion. Any Borel fbced set of
power products B can be split into those which do not include the variable
x„ (i.e. B n PP[xi,...,x„_i]), and those which do {Rn{B)). The first 2
conditions of this lemma constrains these two sets. The third condition
describes how these two sets must fit together. This is a useful definition
for inductive proofs, because the two sets are in a sense simpler than B
itself. The set B fi PP[xi, . . . , x„] has only n — 1 variables, and the set
Sn{B) is of degree d — 1.

Proof. If is Borel, then clearly these three properties must hold. Suppose
onversely that B is not Borel. Then there exists an h and an i such that
x,+i/i € B, but x,7i ^ B. There are three cases to consider.

3 BOREL FIXED SETS 7

1. If x,+i/j e PP(xi,...,x„_i] then B n PP[xi, . . . ,x„_i] is not Borel.

2. If /i is a multiple of x„, then Sn{B) is not Borel.

3. If h is not a multiple of Xn, and ? = n — 1, then

Xnh e Rn{B) nPP[xi,...,x„_i), but X„_i/l ^ Ru-i{B).
Hence h € 5„(5) n PP[ii, . . . ,x„_i] - 5„_i(5).

D

In applying this lemma, the cardinality of the sets will be considered. Note
that

n-l

|BnPP(xi,...,x„_i]| = J2\S'iB)\ ,

and similarly,

t=i

n-l

|5„(S)nPP[xi,...,x„_i]| = ^|5.(5„(B))1 .

A nice property of Borel-fixed monomial ideals is that they admit a
particularly easy form of cone decomposition [Du 89]. Let / C >1 be a
Borel-fixed ideal generated by a set of power products of degree < d, and
let B be the set of degree d power products in /. Then / can be expressed
as a direct sum (over K) of

1. the power products in / of degree < d, and

2. for t = 1, . . . , n, the sets of the form

®heRi{B)h • K[xi,...,Xr,] .

It then follows that the Hilbert polynomial of / is of the form

p,w = |:i5,(B)i(^-f:p'). (1)

4 MACAULAY'S THEOREM 8

4 Macaulay's Theorem

Let L{i, d, m) denote the lexicographic set consisting of the m >-greatest
degree d power products of PP[ii, . . . ,x,]. Now, for B a Borel fixed set of
degree d power products, define

T{B) = U,"=i{x./i : heL{i,d~l,\S,{B)\)} .

Trivially for i = 1, . . . , n,

S,{T{B)) = L{i,d-1,\S,{B)\) ,

and hence

\S,{T{B))\ = \S,{B)\.

Lemma 6 Let B be a Borel-fixed set of degree d power products such that
T{B) is also Borel fixed. If

1. /i = i?'---i^"Gr(5) (a^^O),

2. g = x\' ■■■xl' ^ T[B) (b, # O;, and
S. g>h

then u < V.

Proof. By the definition of T{B),

heT{B) => xZ'heL{u,d-l,\S^{B)\).
Now looking for a contradiction, suppose that u > v. Then

1. g>h => x~^g>x~^h, and

L " L

2. x„-iff ePP[xi,...,i„]

L{u,d — 1, |5u(5)|) is a lexicographic set over PP[xi, . . . ,Xu\- Since it con-
tains x~^h, it must also contain the >-greater power product x^^g. And
so

x:'geL{u,d-l,\S^{B)\) =^ x,x:'geT{B).

4 MACAULAY'S THEOREM 9

Finally, since T{B) is Borel-fixed this leads to the contradiction g G T[B).

D

The usefulness of the set T{B) is that it is closer to being a lexicographic
ideal than B. This idea of closeness is made explicit in the proof of following
lemma.

Lemma 7 Let B C PP[xi, . . . ,Xn] be a Borel-fixed set of degree d power
products. Suppose that for every Borel-fixed set C C PP(ii, . . . ,Xn] of degree
d power that the set T{C) is also Borel-fixed.
Then for /c = 1, . . . , n,

i:\S,{B)\ > i:\S.(L{n,d,\B\))\ .

i-1 «=1

Proof. The assumption concerning sets of the form C is given for technical
reasons, and lemma 8 shows that this assumption is always satisfied. For
now though, this assumption allows one to conclude that T{B) is Borel-
fixed.

K T{B) is a lexicographic set, then since it contains \B\ power products
of degree d, then it is the lexicographic set L{n,d,\B\). The lemma then
follows trivially since for each i = 1, . . . ,n,

\Si{B)\ = \S,{T{B))\ = \S,{L{n,d,\B\)\ .

Assume otherwise that T{B) is not lexicographic. Let h — x^' • ■ ■ x^" be the
lexicographically last power product of T{B), and let g = i/ • • • x^" be the
lexicographically first degree d power product not in T{B) — {h}, where a^
and 6„ are non-zero. Since T{B) is not lexicographic g>h, and by lemma

6, u < V.

Let E denote the ideal {T{B) - {h} U {g}). Then E is a. Borel fixed
ideal and for A; = 1, . . . , n

x:i5.(B)i = j:\smB))\ > j:\s,{E)\. (2)
t=i »=i 1=1

Furthermore at k = u the inequality

f:\s,{B)\ > f:\s,{E)\.
1=1 t=i

4 MAC AUL AY'S THEOREM 10

is strict and so summing the inequalities (2) for /c = 1, . . . , n yields

t=i .=1

Now using induction on the value X),"-i '^|'S'i(-E')i, one may assume that
for k = 1 , . . . , n

Then,

Z\S,{E)\ > Z\S'iL{n,d,\E\]
t=i 1=1

i:\s,{B)\ > j:\s,{E)\
1=1 1=1

k

> J2\SdL{ri,d,\E\
«=i

= f2\S,{L{n,d,\B\
f=i

To apply this lemma requires some assurance that the set T{B) will be
Borel fixed. The following lemma shows that this is always the case.

Lemma 8 Let B C PP[ii, ...,!„] be any Borel fixed set of degree d power
products. Then the set T[B) is also Borel fixed.

Proof. The proof of this lemma uses induction on the number of n and
the degree d. The lemma holds trivially for any d if n = 2, and it also
holds for all n if rf = 1. So assume inductively that the lemma holds for
{d — l,n), and {d,n — 1). To show that T{B) is Borel fixed, consider the
three conditions of lemma 5.

1. T{B) n PP[xi, . . . , x„_i] is Borel fixed.

Let C = BnPP[ii,.. . ,x„_i]. Then C is a Borel fixed ideal of degree
d and n — 1 variables. By the induction hypothesis T{C) is Borel
fixed. But T{C) is exactly the set T{B) n PP[xi, . . . ,i„_i].

4 MACAU LAY'S THEOREM 11

2. 5„(r(5)) is Borel fixed.

This is trivial since by construction 5„(r(5)) is a lexicographic set.

3. 5„(r(B))nPP[xi,...,x„_,] C 5„_i(r(/?)).

Since these are both lexicographic sets over degree d - 1 elements of
PP[ii,. . .,in_i], the inclusion can be proved simply by considering
the cardinality of the sets.

Consider the set Sn{B). This is a Borel-fixed set of n variable power
products of degree d-1. Using the induction hypothesis, for every set
C of this form the set T{C) is also Borel-fixed. And so the previous
lemma may be applied with /c = n - 1 to yield,

J2\SdSn{B))\ > Yl\S,{L{n,d-l,\S„{B)\)) .
t=i t=i

Furthermore, since 5 is a Borel set, condition 3 of lemma 5 states
that

5„(5)nPP[ii,...,x„_i]C5„_i(5)

and so taking cardinalities

n-l

X:|5.(5„(5))| < |5„_i(B)|.

t=i

Putting this all together,

|5„(r(B))nPP[xi,...,i„_i]| = |L(n,cf-l,|5„(5)|)nPPlxi,...,x„_i]|

= J2\Sr{L{n,d-l,\S.m))\

n-l

< x:i5.(5„(5))i

t=i

< |5„_i(fi)| = |5„_x(r(5))i

D

4 MACAULAY'S THEOREM 12

Lemma 9 Let I be any Borel fixed ideal generated by k degree d power
products, and let L be the lexicographic ideal generated by L{n,d,k). Then
for any degree z,

Proof. For z < d, ipiiz) — (pii^) — 0. For z > d the Hilbert functions
attain the polynomial forms:

"-^ ^ - d^n-i\

'Pl{z) = ^ |5,(I'(n,(f, /c))|

So,

z —

n — i

""^ ^ z-d + n-i

<Pj{z)-<pM = Yl{\SAI)\-\SAL{n,d,k))\)

n — I

Using the combinatorial identity I j = II;=o I 1 >

<pj{z)-M^) = Emn\-\sd^n,d,k))\)\Y:["''^y'^)

= t(['~'^y''^ jX:(|5.(/)|-|5.(L(n,d,/c))|)

But from lemma 7, each sum X^"r/(|5,(/)| — \S,{L{n,d,k))\) is a non-
negative constant a^, so

D

Lemma 9 allows an easy proof of Macaualy's theorem.

Theorem 10 (Macaulay) For every ideal I C ff [ij, . . . ,i„] there is a
lexicographic ideal L such that I and L have the same Hilbert function.

4 MACAULAY'S THEOREM 13

Proof. For an arbitrary ideal /, the existence of generic coordinates shows
that there is a Borel fixed ideal I such that / and /' share the same Hilbert
function. So, we may limit our attention tc monomial ideals / which are
Borel fixed.

For each degree 2, let Bd be the set of degree z power products in /.
Since by assumption / is a Borel fixed ideal, each B^ is a Borel fixed set
of power products. Now let L be the ideal generated by the infinite set of
power products

L' - uZoL{n,z,\B,\) .

Now, L must contain only those power products in L'. Otherwise, there
would be a degree d and power product p such that p e L{n,z, |5j|) but
for some x,, x,p ^ L{n, 2 + 1, |Sd+i|). But this implies

And so, the set of power products in L is exactly L' , and

ip^iz) = \L{n,z,\B,\)\ = \B,\ = ipj{z) .

D

REFERENCES 14

References

[Ba 82] D. Bayer, The Division Algorithm and the Hilbert Scheme,

Ph.D. thesis. Harvard University 1982.

[ClLi 69] G.F. Clements and B. Lindstrom, A Generalization of a Com-

binatorial Theorem of Macaulay, Journal of Combinato-
rial Theory 7, 1969, 230-1 ''.S.

(Du 88] T. Dube, Quantitative Analysis of Problems in Computer Al-

gebra: Grobner Bases and the Nullstellensatz, Ph.D. thesis,
Nev^^ York University 1988.

[Du 89] T. Dube, The Structure of Polynomial Ideals and Grobner

Bases (to appear in SIAM Journal of Computing).

[Gi 84] M. Giusti, Sorrte Effectivity Problems in Polynomial Ideal

Theory, Lecture Notes in Computer Science 174, 1984,159-
171.

[Ga 73] A. Galligo, A Propos du Theorrhe de Preparation de Weier-

strauss. Lecture Notes in Mathematics 409, 1973, 543-
579.

[Ma 27] F.S. Macaulay, Some Properties of Enumemtion in the The-

ory of Modular Systems, Proceedings the London

Mathematical Society 26, 1927, 531-555.

Inductive proof of
Macaulay's theorem.

c.l

^U COMPACT ^

oate

c.l

SORROWER

s Name

LIBRARY

N.Y.U. Courant Institute of

Mathematical Sciences

DATE DUE

j

CAYLORO

PmNTeOlNU.S.A.