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
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.
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
/. But this leads to the contradiction:
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
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) .
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.