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.