(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
See other formats

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

Robotics Research 
l^hnical Report 

Inductive Proof of Macaulay's Theorem 


Thomas Dubd 

Technical Report No. 455 

Robotics Report No. 202 

June, 1989 



cj e 
w o 




O U 


o x: 

O 4J 

Q4 w 




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 


in- ■ 


m ., 

t ■ 


. jp 


W- ,. -. 







. ^w i^ 


■t . 

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

^ : 


it » 

5* " 

Inductive Proof of Macaulay's Theorem 

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- 

Inductive Proof of Macaulay's Theorem 

Thomas W. Dube 

June 9, 1989 


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 

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, 


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 


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 


m, = ^ a, . 


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 
tedious reading. 

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. 


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 

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}. 



Proof. Let / and L denote the following ideals: 

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


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


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



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 


/. But this leads to the contradiction: 

p<t<s<as = p . 

L L L 


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. 


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 /. 

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 

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. 


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. 


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). 


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


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

and similarly, 



|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 

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 

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


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


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 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- 

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 


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 


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

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


> J2\SdL{ri,d,\E\ 

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

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]. 


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 


and so taking cardinalities 


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


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))\ 


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


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



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))| 


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 


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. 


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 

contradicting lemma 9. 

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

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




[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- 

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

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

[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. 






s Name 


N.Y.U. Courant Institute of 

Mathematical Sciences