• Ingen resultater fundet

Gradings and homogeneity

In document Preface (Sider 52-55)

In the following we will define gradings onk[x1, . . . , xn]. These definitions can easily be generalized to any semigroup ringR[S], but we stick to the polynomial ring to keep things simple.

Definition 5.3.1 By a grading on k[x1, . . . , xn] we mean a monoid homomor- phismφ :Nn → S to a semigroup S. Foru ∈ Nn the φ-degree of xu and u is φ(u).

Definition 5.3.2 Let φ be a grading on k[x1, . . . , xn]. A polynomial f ∈ k[x1, . . . , xn] is φ-homogeneous if every exponent of f has the same φ-degree.

An ideal I ⊆ k[x1, . . . , xn] is φ-homogeneous if it has a generating set of φ- homogeneous polynomials.

Example 5.3.3 Thestandard grading onk[x1, . . . , xn] is defined asφ:Nn→N with φ(u) = Pn

i=1ui for u ∈ Nn. We sometimes call φ(u) the total degree of xu. A polynomial is homogeneous in the standard grading if every term has the same usual total degree.

• x31−x22x3+x33 is homogeneous in the standard grading.

• x21−x12 is not homogeneous in the standard grading.

• hx1 −x2, x31 −x22x3 +x33 +x1 −x2i = hx1 −x2, x31 −x32x3 +x33i is a homogeneous ideal in the standard grading.

Example 5.3.4 Let ω ∈ Rn. We may define the grading φω : Nn → R by φω(u) := ω·u. For a polynomial f ∈ k[x1, . . . , xn] the initial form inω(f) is φω-homogeneous by Definition 1.4.1. For simplicity we sometimes just say ω- homogeneous. If I ⊆ k[x1, . . . , xn] is an ideal then the initial ideal inω(I) is ω-homogeneous by Definition 1.6.1.

Example 5.3.5 A matrix A ∈ Nd×n defines a grading φA : Nn → Nd by φA(u) := Au. Notice that if ω is a a vector in the rowspace of A then any φ-homogeneous polynomial is also ω-homogeneous.

A priori, it is not clear that the last ideal in Example 5.3.3 is homogeneous.

In the following we will find an algorithm for deciding if an ideal is homogeneous.

Lemma 5.3.6 Let φ be a grading on k[x1, . . . , xn]. Let f, g ∈ k[x1, . . . , xn] be φ-homogeneous and h ∈ k[x1, . . . , xn] a single term. The polynomial hf is φ-homogeneous. If the terms of f and g have the same φ-degree, then f +g is φ-homogeneous.

Proof. Leth =cxu and let cxu and c′′xu′′ be two terms off resulting in two termsccxu+u and cc′′xu+u′′. We check that they have the same φ-degree:

φ(u+u) =φ(u) +φ(u) =φ(u) +φ(u′′) =φ(u+u′′).

Hencehf isφ-homogeneous. It is clear from the definition thatf+gis homo- geneous since all terms have the sameφ-degree. 2

Lemma 5.3.7 Let f, g ∈k[x1, . . . , xn]\ {0} be φ-homogeneous and ≺ a term ordering. Then the S-polynomialS(f, g) is φ-homogeneous.

Proof. The S-polynomial was defined as S(f, g) = lcm(in(f),in(g))

in(f) f −lcm(in(f),in(g)) in(g) g

to carefully make two terms cancel - one from each summand. Each summand isφ-homogeneous by Lemma 5.3.6. Since two terms cancel they must have the sameφ-degree. Therefore all terms of the S-polynomial have the sameφ-degree.

2

Lemma 5.3.8 Let f and f1, . . . , fs be φ-homogeneous polynomials. The re- mainderrproduced by the division algorithm (Algorithm 1.5.1) isφ-homogeneous.

Proof. In the division algorithm f is assigned to p and p is adjusted until it eventually becomes zero and the algorithm terminates. At the beginning p is φ-homogeneous because f is. In each iteration the p remains φ-homogeneous because we only subtract φ-homogeneous polynomials from p of the same φ- degree. Thereforepremainsφ-homogeneous of the same degree until it becomes 0. Terms are moved fromp to the remainderr. Therefore ther = 0 when the algorithm terminates. 2

Proposition 5.3.9 Let φ be a grading on k[x1, . . . , xn]. Let I ⊆k[x1, . . . , xn] be a φ-homogeneous ideal and ≺ a term ordering. Then the reduced Gr¨obner basis G(I) is φ-homogeneous.

Proof. By Hilbert’s Basis Theorem 1.1.6 there exists a finite generating set G⊆k[x1, . . . , xn] for I. We also know that there exists a generating set G ⊆ k[x1, . . . , xn] of φ-homogeneous polynomials since I is φ-homogeneous, which could be infinite. We now take everyg∈Gand express it in terms of elements ofG:

g=

m

X

i=1

figi

for somem ∈N,fi ∈k[x1, . . . , xn] andgi ∈G. Doing so for all finitely many terms in g requires only a finite number of terms of the type gi. We let G′′

denote this finite set ofφ-homogeneous polynomials which generate I.

If we perform Buchberger’s Algorithm on G′′, the result is φ-homogeneous because the operations of taking S-polynomials and remainder preserves ho- mogeneity (Lemma 5.3.7 and Lemma 5.3.8. The minimizing and autoreducing algorithms (Algorithm 1.7.8 and Algorithm 1.7.9) also preserveφ-homogeneity and together produce the unique reduced Gr¨obner basis ofI with respect to≺. We conclude that this Gr¨obner basis isφ-homogeneous. 2

Knowing that the reduced Gr¨obner basis is always homogeneous can be used to compute a homogeneous generating set for a homogeneous ideal but also to check if and ideal is homogeneous.

Algorithm 5.3.10

Input: A set G⊆k[x1, . . . , xn]and a grading φ.

Output: “Yes” if the ideal hGi is φ-homogeneous and “No” otherwise.

• Compute the reduced Gr¨obner basis H:=G(hGi).

• Return “Yes” if all polynomials in H are φ-homogeneous and “No” oth- erwise.

Example 5.3.11 The ideal hx2 +y −3zx, y2z +zx−1i ⊆ Q[x, y, z] is not homogeneous in the standard grading because its reduced Gr¨obner basis with respect to the lexicographic ordering (withz≺y≺x) is not homogeneous:

{y4z2+ 1−3z2+yz2−2y2z+ 3y2z3, x−3z+yz−y2+ 3y2z2+y4z}. Definition 5.3.12 By aφ-homogeneous part of a polynomial f we mean the sum of all terms inf of a particularφ-degree.

Lemma 5.3.13 Let φ be a grading on R := k[x1, . . . , xn]. Let I ⊆ R be a φ-homogeneous ideal. A polynomial f ∈ I if and only if every φ-homogeneous part of f is inI.

Proof. Clearly, if every φ-homogeneous part of f is in I then so is the sum, which equals f. On the other hand, let f ∈ I be a polynomial, let h be a φ-homogeneous part of f, and let G(I) be the reduced Gr¨obner basis of I with respect to some term ordering ≺. The division algorithm will produce an expression f = P

iaifi with a1 being polynomials and fi ∈ G(I). By splitting each ai into terms and multiplying out we get an expression f = P

jbjgj wherebj is a single term andgj ∈ G(I). Since eachbj is homogeneous, any homogeneous part of f is written as f = P

j∈Jbjgj for J chosen to give just the terms in the right φ-degree. Since gj ∈ I we conclude that the φ- homogeneous part is inI. 2

Proposition 5.3.14 Let R := k[x1, . . . , xn] and φ :Nn → S a grading. As a k-vector space we may write R as a direct sum:

R= M

m∈S

Rm

where Rm is thek-vector space of homogeneous polynomials of φ-degree m (to- gether with 0). Furthermore, if I is a φ-homogeneous ideal then we can define Im to be the set of φ-homogeneous polynomials in I of degree m (together with 0). As a vector space we have

I = M

m∈S

Im.

Proof. Clearly, a polynomial can be uniquely be split into finitely many non- zero homogeneous parts of differentφ-degree, which provesR=L

m∈SRm. A polynomial f ∈ I is also in R and therefore splits into φ-homogeneous parts.

Each of these is inI by Corollary 5.3.13 and therefore in an Im. 2

In document Preface (Sider 52-55)