1. Let I be a radical ideal, and {g_1..g_m} a reduced Gr\"obner basis for it.
Show that each g_i is squarefree, i.e. is not divisible by f^2 for any polynomial f of degree > 0.
2. Let I be an ideal such that for all f, if f^2 is in I, then f is in I. Show that I is radical.
3. Let I be a monomial ideal generated by squarefree monomials. Show that I is radical.
Hint: show that if p is in I, then init(p) and p-init(p) are in I. Use this to show that it is enough to test the condition in question #2 when f is a monomial.
4. Let I be an ideal with a Gr\"obner basis {f_1,...,f_n}, such that each init(f_i) is a squarefree monomial. Show that I is radical.
5. Let I and J be two radical ideals.
a) Show that I intersect J is radical.
b) Give an example where I+J (which concatenates their generators) is not radical.
6. Let I = < ac,bc,bd,ae,de > inside C[a,b,c,d,e]. Decompose V(I) as a union of subspaces. Make it minimal, so no subspace in your list contains another.
Thursday, February 26, 2009
Wednesday, February 25, 2009
Wednesday 2/25
We did a couple of things with monomial ideals:
1) if a monomial ideal is radical, then it's generated by squarefree monomials.
2) V(a monomial ideal) = a union of coordinate planes of various dimensions.
Case 2 of the weak Nullstellensatz: when the projection of V(I) to a coordinate line hits a finite set.
Algebraically, I intersect C[x_i] = < f(x_i) >, and the finite set is the set of roots.
We showed that I + < x_i - m > is still not the whole ring, if m is one of the roots.
So enlarge I, and repeat until done, at which point I = < x_i - m_i : i=1..n >, and that V(I) contains one point, (m_1,...,m_n).
We started the strong Nullstellensatz, but didn't finish it.
1) if a monomial ideal is radical, then it's generated by squarefree monomials.
2) V(a monomial ideal) = a union of coordinate planes of various dimensions.
Case 2 of the weak Nullstellensatz: when the projection of V(I) to a coordinate line hits a finite set.
Algebraically, I intersect C[x_i] = < f(x_i) >, and the finite set is the set of roots.
We showed that I + < x_i - m > is still not the whole ring, if m is one of the roots.
So enlarge I, and repeat until done, at which point I = < x_i - m_i : i=1..n >, and that V(I) contains one point, (m_1,...,m_n).
We started the strong Nullstellensatz, but didn't finish it.
HW due Monday instead
Insofar as I was unavailable this Monday for OH, I will accept this HW next Monday. (If you're already done you can give it to me today, of course.)
This won't be an ongoing delay -- the HW assigned today will still be due Wednesday.
This won't be an ongoing delay -- the HW assigned today will still be due Wednesday.
Monday, February 23, 2009
Plane flight, and class, canceled Mon 2/23
My flight was canceled, and I am delayed coming home a day, so class and office hours are canceled for today.
Sunday, February 22, 2009
Answers to HW #4
1. Let V be a k-dimensional subspace of C^n.
Let I(V) be generated by the linear polynomials { \sum_i v_i x_i : (v_1,...,v_n) in V }.
How would you find a finite generating set for I(V), in ten words or less?
"Pick a basis."
"Pick a basis of V, and use only those."
That sort of thing.
The point being that all the other linear polynomials are already C-linear combinations, much less R-linear.
2. A Gr\"obner basis is reduced if
a) the coefficient on every leading term is 1,
b) no term in any generator can be reduced using another generator.
Show that every ideal in a polynomial ring has a reduced Gr\"obner basis.
We proved already that I has a finite Gr\"obner basis.
Apply the reduction algorithm to each element of the basis, using only the other generators; if you get to zero throw the element away, otherwise replace it with the reduced version.
Obviously this doesn't change the ideal; to see that it's still a Gr\"obner basis, observe that anything that would reduce to 0 before will still reduce to 0.
As we do these reductions, the leading monomials can only decrease. So at some point they stop decreasing.
Reduce all the generators one last time (not changing the leading monomials). For each one, we get stuck when no term can be reduced using another generator. Since we don't change the leading monomials, we will remain stuck, i.e. we will have condition (b).
Now divide each generator by its leading coefficient, to achieve (a). This obviously doesn't change whether we have a Gr\"obner basis, nor what ideal it generates.
3 = 1+2. Let M be an m x n matrix. Let I(M) = I(the span of the row vectors) from Q#1.
Describe an algorithm to fiddle with M, from which one can read off a reduced Gr\"obner basis for I(M).
The usual algorithm to put a matrix in reduced row-echelon form. Then the conditions on that form exactly say that the generating set is a reduced Gr\"obner basis.
4. Let I be an ideal, and define Rad(I) = {p : for some natural number n, p^n is in I}.
a) Show that Rad(I) contains I.
b) Show that Rad(I) is an ideal.
c) If I = I_X for some subset X of C^n, show that Rad(I) = I.
a) For any p, we can take n=1.
b) It contains I, so it contains 0.
Let p,q be in Rad(I), and m,n such that p^m, q^n are in I.
Then for any r, (rp)^m = r^m p^m is in I too. So rp is in Rad(I).
Consider the binomial expansion of (p+q)^{m+n-1}.
The Ath term is a multiple of p^A b^{m+n-1 - A}.
If A is at least m, then p^A = p^m p^{A-m}, so p^A is in I, so p^A b^{m+n-1 - A} is.
If A < m, then m+n-1-A = n + (m-1 - A) is at least n, so b^{m+n-1-A} is in I.
Hence every term in the binomial expansion is in I. So p+q is in Rad(I).
(If you used m+n instead of m+n-1, or something larger, that's totally fine.)
c) p in Rad(I_X)
=> some p^m in I
=> p^m(x) = 0 for all x in X
=> (p(x))^m = 0 for all x in X
=> p(x) = 0 for all x in X
=> p in I_X
Hence Rad(I_X) is contained in I_X. But we already knew the opposite containment.
Let I(V) be generated by the linear polynomials { \sum_i v_i x_i : (v_1,...,v_n) in V }.
How would you find a finite generating set for I(V), in ten words or less?
"Pick a basis."
"Pick a basis of V, and use only those."
That sort of thing.
The point being that all the other linear polynomials are already C-linear combinations, much less R-linear.
2. A Gr\"obner basis is reduced if
a) the coefficient on every leading term is 1,
b) no term in any generator can be reduced using another generator.
Show that every ideal in a polynomial ring has a reduced Gr\"obner basis.
We proved already that I has a finite Gr\"obner basis.
Apply the reduction algorithm to each element of the basis, using only the other generators; if you get to zero throw the element away, otherwise replace it with the reduced version.
Obviously this doesn't change the ideal; to see that it's still a Gr\"obner basis, observe that anything that would reduce to 0 before will still reduce to 0.
As we do these reductions, the leading monomials can only decrease. So at some point they stop decreasing.
Reduce all the generators one last time (not changing the leading monomials). For each one, we get stuck when no term can be reduced using another generator. Since we don't change the leading monomials, we will remain stuck, i.e. we will have condition (b).
Now divide each generator by its leading coefficient, to achieve (a). This obviously doesn't change whether we have a Gr\"obner basis, nor what ideal it generates.
3 = 1+2. Let M be an m x n matrix. Let I(M) = I(the span of the row vectors) from Q#1.
Describe an algorithm to fiddle with M, from which one can read off a reduced Gr\"obner basis for I(M).
The usual algorithm to put a matrix in reduced row-echelon form. Then the conditions on that form exactly say that the generating set is a reduced Gr\"obner basis.
4. Let I be an ideal, and define Rad(I) = {p : for some natural number n, p^n is in I}.
a) Show that Rad(I) contains I.
b) Show that Rad(I) is an ideal.
c) If I = I_X for some subset X of C^n, show that Rad(I) = I.
a) For any p, we can take n=1.
b) It contains I, so it contains 0.
Let p,q be in Rad(I), and m,n such that p^m, q^n are in I.
Then for any r, (rp)^m = r^m p^m is in I too. So rp is in Rad(I).
Consider the binomial expansion of (p+q)^{m+n-1}.
The Ath term is a multiple of p^A b^{m+n-1 - A}.
If A is at least m, then p^A = p^m p^{A-m}, so p^A is in I, so p^A b^{m+n-1 - A} is.
If A < m, then m+n-1-A = n + (m-1 - A) is at least n, so b^{m+n-1-A} is in I.
Hence every term in the binomial expansion is in I. So p+q is in Rad(I).
(If you used m+n instead of m+n-1, or something larger, that's totally fine.)
c) p in Rad(I_X)
=> some p^m in I
=> p^m(x) = 0 for all x in X
=> (p(x))^m = 0 for all x in X
=> p(x) = 0 for all x in X
=> p in I_X
Hence Rad(I_X) is contained in I_X. But we already knew the opposite containment.
Saturday, February 21, 2009
HW #5, due Wednesday 2/25
Let I = < f_1, ..., f_k > where the f_i are each homogeneous polynomials.
1. Show that I has a Grobner basis consisting of homogeneous polynomials.
2. Assume hereafter that the {f_i} are a reduced Grobner basis.
Recall that the Hilbert function h_I(n) is the dimension of R_n / I_n.
Call a monomial standard if it isn't divisible by any of the leading monomials of the {f_i}.
Show that h_I(n) is the number of standard monomials of degree n.
3. Show that h_I = h_{init I}, so H_I = H_{init I} (the Hilbert series).
4. The polynomial b^2 - ac has two possible leading terms (depending on term order), so I = < b^2 - ac > has two possible init I. Compute each of their Hilbert series (and show they are equal, as problem 3 predicts).
5. Let I = < the entries of M^2, where M is a 2x2 matrix >. Compute the Hilbert series H_I.
6. Let J be the larger ideal containing I and also the generator Trace(M). Compute the Hilbert series H_J.
1. Show that I has a Grobner basis consisting of homogeneous polynomials.
2. Assume hereafter that the {f_i} are a reduced Grobner basis.
Recall that the Hilbert function h_I(n) is the dimension of R_n / I_n.
Call a monomial standard if it isn't divisible by any of the leading monomials of the {f_i}.
Show that h_I(n) is the number of standard monomials of degree n.
3. Show that h_I = h_{init I}, so H_I = H_{init I} (the Hilbert series).
4. The polynomial b^2 - ac has two possible leading terms (depending on term order), so I = < b^2 - ac > has two possible init I. Compute each of their Hilbert series (and show they are equal, as problem 3 predicts).
5. Let I = < the entries of M^2, where M is a 2x2 matrix >. Compute the Hilbert series H_I.
6. Let J be the larger ideal containing I and also the generator Trace(M). Compute the Hilbert series H_J.
Thursday, February 12, 2009
Answers to HW #3
1. For I a monomial ideal in R = C[x_1,...,x_n], let the multigraded Hilbert series be the sum of all the monomials in R that aren't in I.
a) Compute this for R = C[x,y] and I = 0, as a ratio of polynomials.
b) Generalize our inclusion-exclusion formula for Hilbert series to multigraded Hilbert series.
a) Every monomial is uniquely the product of some x^i and some y^j, so the sum of all monomials = (1 + x + x^2 + ...)(1 + y + y^2 + ...) = 1 / (1-x)(1-y).
b) At each step of inclusion-exclusion, we want to take out or add back the monomials that are multiples of some \product_i (x_i)^(e_i) for some exponents (e_i).
Adding all those monomials up (to give the term), we get the prefactor \product_i 1/(1-x_i) times the monomial \product_i (x_i)^(e_i).
Now the same inclusion-exclusion argument gives the formula
H = \product_i 1/(1-x_i) \sum_{S subset of 1..n} (-1)^|S| \product_i (x_i)^{max_{j in S} e_{ij}}.
(When all the x_i are set equal to t, we recover the singly graded Hilbert series, and the maxes get added together.)
2. Let f,g be two polynomials, and fix a term order <. Assume that gcd(init(f),init(g)) = 1. Show that the reduction algorithm reduces the S-polynomial of f and g to zero (using f and g alone). (Moral: one needn't bother fiddling with the S-polynomial of f and g in this case.)
Write f = init(f) + f', g = init(g) + g'.
By the assumption, S(f,g) = init(g) f - init(f) g = (g-g')f - (f-f')g = f'g - g'f.
As we apply the reduction algorithm, we add multiples of f and g; each step along the way looks like pg - qf. Since the initial terms only decrease during reduction, init(qf) is at most init(g'f) = init(g')init(f) < init(g)init(f). Hence init(q) < init(g).
Do we ever get stuck? If p=0 and q=0, we're done. If p=0 but q not, we can use f to reduce, similarly if q=0 but p not.
If p,q are not both zero, we can talk about the initial terms of pg and qf.
We claim they are different, for otherwise init(p) init(g) = init(q) init(f), so init(g) divides init(q) init(f). Then by the gcd=1, we learn init(g) divides init(q), but that's impossible because init(g) > init(q).
Since the leading monomials of pg and qf are different, one of them is the leading monomial of pg-qf. So the algorithm is not stuck; the leading monomial of pg-qf is a multiple of either the leading monomial of g or f, depending.
(This was definitely the hardest homework question so far!)
3. If f and g are monomials, what is their S-polynomial?
It's lcm(f,g) - lcm(f,g) = 0.
4. Compute a Gröbner basis for I = < x^2 - y, x^3 - z > with respect to lex order.
1&2: x^3 - x^3 -> xy - z, call this 3.
1&3: x^2 y - x^2 y -> y^2 - xz, call this 4.
2&3: x^3 y - x^3 y -> yz - x^2 z -> yz - xy^2 -> yz -yz = 0.
1&4: x^2 z - x^2 z -> yz - xy^2 -> yz - yz = 0.
2&4: x^3 z - x^3 z -> z^2 - x^2 y^2 -> z^2 - z^2 = 0.
3&4: xyz - xyz -> z^2 - y^3, call this 5.
1&5, 2&5, 4&5: gcd = 1 so we don't need to test.
3&5: xy^3 - xy^3 -> z y^2 - x z^2 -> z y^2 - z y^2 -> 0.
In all, x^2 - y, x^3 - z, xy - z, y^2 - xz, z^2 - y^3.
Can any of the generators in your list be safely left out?
Generator #2 reduces to 0 using #1 and #3. So not only is it in the ideal they generate, but it isn't necessary for reducing anybody else -- #1 and #3 are on the job.
5. Let p = x^2 + 3xy - y^2. Find a term order that makes x^2 the leading term, another that makes -y^2 the leading term, and show that 3xy isn't be the leading term under any term order.
Lex order with x>y makes x^2 the leading term, x < y makes y^2 the leading term.
Either x < y or x > y. If x < y, then xy < y^2. If x > y, then x^2 > xy. So no matter what, xy is not the leading term.
a) Compute this for R = C[x,y] and I = 0, as a ratio of polynomials.
b) Generalize our inclusion-exclusion formula for Hilbert series to multigraded Hilbert series.
a) Every monomial is uniquely the product of some x^i and some y^j, so the sum of all monomials = (1 + x + x^2 + ...)(1 + y + y^2 + ...) = 1 / (1-x)(1-y).
b) At each step of inclusion-exclusion, we want to take out or add back the monomials that are multiples of some \product_i (x_i)^(e_i) for some exponents (e_i).
Adding all those monomials up (to give the term), we get the prefactor \product_i 1/(1-x_i) times the monomial \product_i (x_i)^(e_i).
Now the same inclusion-exclusion argument gives the formula
H = \product_i 1/(1-x_i) \sum_{S subset of 1..n} (-1)^|S| \product_i (x_i)^{max_{j in S} e_{ij}}.
(When all the x_i are set equal to t, we recover the singly graded Hilbert series, and the maxes get added together.)
2. Let f,g be two polynomials, and fix a term order <. Assume that gcd(init(f),init(g)) = 1. Show that the reduction algorithm reduces the S-polynomial of f and g to zero (using f and g alone). (Moral: one needn't bother fiddling with the S-polynomial of f and g in this case.)
Write f = init(f) + f', g = init(g) + g'.
By the assumption, S(f,g) = init(g) f - init(f) g = (g-g')f - (f-f')g = f'g - g'f.
As we apply the reduction algorithm, we add multiples of f and g; each step along the way looks like pg - qf. Since the initial terms only decrease during reduction, init(qf) is at most init(g'f) = init(g')init(f) < init(g)init(f). Hence init(q) < init(g).
Do we ever get stuck? If p=0 and q=0, we're done. If p=0 but q not, we can use f to reduce, similarly if q=0 but p not.
If p,q are not both zero, we can talk about the initial terms of pg and qf.
We claim they are different, for otherwise init(p) init(g) = init(q) init(f), so init(g) divides init(q) init(f). Then by the gcd=1, we learn init(g) divides init(q), but that's impossible because init(g) > init(q).
Since the leading monomials of pg and qf are different, one of them is the leading monomial of pg-qf. So the algorithm is not stuck; the leading monomial of pg-qf is a multiple of either the leading monomial of g or f, depending.
(This was definitely the hardest homework question so far!)
3. If f and g are monomials, what is their S-polynomial?
It's lcm(f,g) - lcm(f,g) = 0.
4. Compute a Gröbner basis for I = < x^2 - y, x^3 - z > with respect to lex order.
1&2: x^3 - x^3 -> xy - z, call this 3.
1&3: x^2 y - x^2 y -> y^2 - xz, call this 4.
2&3: x^3 y - x^3 y -> yz - x^2 z -> yz - xy^2 -> yz -yz = 0.
1&4: x^2 z - x^2 z -> yz - xy^2 -> yz - yz = 0.
2&4: x^3 z - x^3 z -> z^2 - x^2 y^2 -> z^2 - z^2 = 0.
3&4: xyz - xyz -> z^2 - y^3, call this 5.
1&5, 2&5, 4&5: gcd = 1 so we don't need to test.
3&5: xy^3 - xy^3 -> z y^2 - x z^2 -> z y^2 - z y^2 -> 0.
In all, x^2 - y, x^3 - z, xy - z, y^2 - xz, z^2 - y^3.
Can any of the generators in your list be safely left out?
Generator #2 reduces to 0 using #1 and #3. So not only is it in the ideal they generate, but it isn't necessary for reducing anybody else -- #1 and #3 are on the job.
5. Let p = x^2 + 3xy - y^2. Find a term order that makes x^2 the leading term, another that makes -y^2 the leading term, and show that 3xy isn't be the leading term under any term order.
Lex order with x>y makes x^2 the leading term, x < y makes y^2 the leading term.
Either x < y or x > y. If x < y, then xy < y^2. If x > y, then x^2 > xy. So no matter what, xy is not the leading term.
Wednesday, February 11, 2009
Wednesday 2/11
Lemma.
If every ideal (resp. monomial ideal) in n variables is finitely generated,
then the ACC holds for ideals (resp. monomial ideals) in n variables.
Pf. Take the union of the ideals; that's again an ideal, and its last generator occurs at some finite step along the way..
Lemma.
If the ACC holds for monomial ideals in n variables,
then every ideal in n+1 variables is finitely generated.
Pf. Take slices of the monomial ideals, to get an increasing chain in one dimension down, which by assumption must stop at some slice.
Thm. Every monomial ideal is f.g., and ACC holds in any number of variables.
Thm. The Buchberger algorithm terminates.
Pf. Look at the monomial ideal generated by the initial terms of the generators; this strictly increases each time we add a new generator (or else we wouldn't bother adding it).
Def. Colon ideals.
Def. init I.
If every ideal (resp. monomial ideal) in n variables is finitely generated,
then the ACC holds for ideals (resp. monomial ideals) in n variables.
Pf. Take the union of the ideals; that's again an ideal, and its last generator occurs at some finite step along the way..
Lemma.
If the ACC holds for monomial ideals in n variables,
then every ideal in n+1 variables is finitely generated.
Pf. Take slices of the monomial ideals, to get an increasing chain in one dimension down, which by assumption must stop at some slice.
Thm. Every monomial ideal is f.g., and ACC holds in any number of variables.
Thm. The Buchberger algorithm terminates.
Pf. Look at the monomial ideal generated by the initial terms of the generators; this strictly increases each time we add a new generator (or else we wouldn't bother adding it).
Def. Colon ideals.
Def. init I.
HW #4, due Wednesday 2/18
1. Let V be a k-dimensional subspace of C^n.
Let I(V) be generated by the linear polynomials { \sum_i v_i x_i : (v_1,...,v_n) in V }.
How would you find a finite generating set for I(V), in ten words or less?
2. A Gr\"obner basis is reduced if
a) the coefficient on every leading term is 1,
b) no term in any generator can be reduced using another generator.
Show that every ideal in a polynomial ring has a reduced Gr\"obner basis.
3 = 1+2. Let M be an m x n matrix. Let I(M) = I(the span of the row vectors) from Q#1.
Describe an algorithm to fiddle with M, from which one can read off a reduced Gr\"obner basis for I(M).
4. Let I be an ideal, and define Rad(I) = {p : for some natural number n, p^n is in I}.
a) Show that Rad(I) contains I.
b) Show that Rad(I) is an ideal.
c) If I = I_X for some subset X of C^n, show that Rad(I) = I.
...more to come
Let I(V) be generated by the linear polynomials { \sum_i v_i x_i : (v_1,...,v_n) in V }.
How would you find a finite generating set for I(V), in ten words or less?
2. A Gr\"obner basis is reduced if
a) the coefficient on every leading term is 1,
b) no term in any generator can be reduced using another generator.
Show that every ideal in a polynomial ring has a reduced Gr\"obner basis.
3 = 1+2. Let M be an m x n matrix. Let I(M) = I(the span of the row vectors) from Q#1.
Describe an algorithm to fiddle with M, from which one can read off a reduced Gr\"obner basis for I(M).
4. Let I be an ideal, and define Rad(I) = {p : for some natural number n, p^n is in I}.
a) Show that Rad(I) contains I.
b) Show that Rad(I) is an ideal.
c) If I = I_X for some subset X of C^n, show that Rad(I) = I.
Monday, February 09, 2009
Monday 2/9
Just for practice, we computed a Gr\"obner basis for the ideal generated by the entries of M^2.
Then we worried about whether the Buchberger algorithm terminates.
For culture, we talked about an algorithm suspected, but not known, to terminate.
Then we defined the Ascending Chain Condition on ideals in a ring, which we'll prove next time for monomial ideals.
Then we worried about whether the Buchberger algorithm terminates.
For culture, we talked about an algorithm suspected, but not known, to terminate.
Then we defined the Ascending Chain Condition on ideals in a ring, which we'll prove next time for monomial ideals.
Saturday, February 07, 2009
Wednesday 2/4
We proved Buchberger's criterion, that if the S-polynomials reduce to 0 then anything in I does.
Three key insights:
1) When the reduction algorithm works, it doesn't just say "yes, p is in the ideal"; rather, by keeping track of the reductions it gives a specific way to write p = sum_i r_i g_i (where the g_i are the generators).
2) In that expression p = sum_i r_i g_i, each init(r_i g_i) is as cheap or cheaper than init(p).
3) The initial term of an S-polynomial S(g_i,g_j) is strictly cheaper than the LCM of the initial monomials.
With those in mind, it should be easier to read this proof, which is the one we followed in class. (Warning: he writes "F" sometimes for a general field, or even "Fq", rather than using the complex numbers, but it doesn't make any difference in this proof.)
Three key insights:
1) When the reduction algorithm works, it doesn't just say "yes, p is in the ideal"; rather, by keeping track of the reductions it gives a specific way to write p = sum_i r_i g_i (where the g_i are the generators).
2) In that expression p = sum_i r_i g_i, each init(r_i g_i) is as cheap or cheaper than init(p).
3) The initial term of an S-polynomial S(g_i,g_j) is strictly cheaper than the LCM of the initial monomials.
With those in mind, it should be easier to read this proof, which is the one we followed in class. (Warning: he writes "F" sometimes for a general field, or even "Fq", rather than using the complex numbers, but it doesn't make any difference in this proof.)
Wednesday, February 04, 2009
Hw #3, due Wednesday 2/11
1. For I a monomial ideal in R = C[x_1,...,x_n], let the multigraded Hilbert series be the sum of all the monomials in R that aren't in I.
a) Compute this for R = C[x,y] and I = 0, as a ratio of polynomials.
b) Generalize our inclusion-exclusion formula for Hilbert series to multigraded Hilbert series.
2. Let f,g be two polynomials, and fix a term order <. Assume that gcd(init(f),init(g)) = 1. Show that the reduction algorithm reduces the S-polynomial of f and g to zero (using f and g alone). (Moral: one needn't bother fiddling with the S-polynomial of f and g in this case.)
3. If f and g are monomials, what is their S-polynomial?
4. Compute a Gröbner basis for I = < x^2 - y, x^3 - z > with respect to lex order.
Can any of the generators in your list be safely left out?
5. Let p = x^2 + 3xy - y^2. Find a term order that makes x^2 the leading term, another that makes -y^2 the leading term, and show that 3xy isn't be the leading term under any term order.
(Oops; I left out the 3 in p the first time. That wasn't the point of the problem.)
a) Compute this for R = C[x,y] and I = 0, as a ratio of polynomials.
b) Generalize our inclusion-exclusion formula for Hilbert series to multigraded Hilbert series.
2. Let f,g be two polynomials, and fix a term order <. Assume that gcd(init(f),init(g)) = 1. Show that the reduction algorithm reduces the S-polynomial of f and g to zero (using f and g alone). (Moral: one needn't bother fiddling with the S-polynomial of f and g in this case.)
3. If f and g are monomials, what is their S-polynomial?
4. Compute a Gröbner basis for I = < x^2 - y, x^3 - z > with respect to lex order.
Can any of the generators in your list be safely left out?
5. Let p = x^2 + 3xy - y^2. Find a term order that makes x^2 the leading term, another that makes -y^2 the leading term, and show that 3xy isn't be the leading term under any term order.
(Oops; I left out the 3 in p the first time. That wasn't the point of the problem.)
Monday, February 02, 2009
Monday 2/2
Definition of S-polynomial.
Easy theorem: for the reduction algorithm to suffice for determining ideal membership, it had better reduce the S-polynomials to zero, making it a Gröbner basis.
Buchberger's algorithm: when it doesn't, just throw them in as new generators, and repeat until done. The result is a Gröbner basis.
Theorems to be proven: the converse of that easy theorem (Buchberger's criterion), and the fact that Buchberger's algorithm terminates.
Easy theorem: for the reduction algorithm to suffice for determining ideal membership, it had better reduce the S-polynomials to zero, making it a Gröbner basis.
Buchberger's algorithm: when it doesn't, just throw them in as new generators, and repeat until done. The result is a Gröbner basis.
Theorems to be proven: the converse of that easy theorem (Buchberger's criterion), and the fact that Buchberger's algorithm terminates.
Subscribe to:
Posts (Atom)