Tuesday, March 31, 2009
Wednesday, March 25, 2009
The midterm
I handed out the midterm. If you didn't get one email me.
It's due in Anna's basement office Friday 2:30-3:30. If you can't come then email her.
Once you start it, you have three hours (consecutive!), during which you can't talk to other people about it nor touch a computer, nor use textbooks.
You may use stuff from the course webpage you've printed out, and anything else you've written.
Other details are on the front page. They shouldn't be too surprising.
It's due in Anna's basement office Friday 2:30-3:30. If you can't come then email her.
Once you start it, you have three hours (consecutive!), during which you can't talk to other people about it nor touch a computer, nor use textbooks.
You may use stuff from the course webpage you've printed out, and anything else you've written.
Other details are on the front page. They shouldn't be too surprising.
Monday 3/23
Went back to proving that Hilb dim = homogeneous Krull dim.
Projective geometry.
Points, lines, and conics in the projective plane.
The embedding of affine space in projective space.
The three types of conics all look the same in the projective plane;
it's just a question of how they intersect the line at infinity.
The homogenization of a polynomial using a new variable.
Projective geometry.
Points, lines, and conics in the projective plane.
The embedding of affine space in projective space.
The three types of conics all look the same in the projective plane;
it's just a question of how they intersect the line at infinity.
The homogenization of a polynomial using a new variable.
Friday, March 13, 2009
Answers to HW #7
1. Let I be a homogeneous ideal in a polynomial ring R, and r a homogeneous element of degree k.
Let J = I + < r >.
Show that
a) For each n, h_J(n) is at least h_I(n) - h_I(n-k).
b) If they are equal for all n, then r is not a zero divisor.
a) Consider the map (R/I)_{n-k} -> (R/I)_n given by multiplication by r.
We figured out in class that the quotient by the image is (R/J)_n.
So dim (R/I)_n = dim (R/J)_n + dim r*(R/I)_{n-k}.
The dimension of r*(R/I)_{n-k} is at most the dimension of (R/I)_{n-k}, so we get the inequality claimed.
b) If they're equal, then dim r*(R/I)_{n-k} = dim (R/I)_{n-k}, so the multiply-by-r map has no kernel. Which means r is not a zero divisor.
2. A list {r_1, r_2, ..., r_m} is called a regular sequence if each r_j is not a zero divisor in R/< r_1, ..., r_{j-1} >.
If {b,c} is a regular sequence, show that {c,b} is a regular sequence.
Oops: I had meant b,c to be homogeneous. (It's true even if they're not, but don't bother with that.)
We showed in class that if r is not a zero divisor in R/I, and is homogeneous of degree k, then H_{I+< r >}(t) = H_I(t) * (1-t^k).
So if {b,c} is a regular sequence, with degrees k,k', then H_{< b,c >}(t) = H_0(t) (1 - t^k) (1 - t^k').
Certainly c is not a zero divisor in R. So H_{< c >}(t) = H_0(t) (1 - t^k').
By the previous question, H_{< c,b >}(t) is coefficientwise at least H_0(t) (1 - t^k') (1 - t^k), with equality iff b is not a zero divisor in R/< c >.
But since < b,c > = < c,b >, we know this is an equality -- so b is not a zero divisor.
3. Let p(n) be a polynomial of degree d, and k a number. Show that q(n) = p(n) - p(n-k) is a polynomial of degree d-1.
First we check it for p(n) = n^d. Then q(n) = n^d - (n^d - d n^{d-1} k + ...), canceling the first term in the binomial series but not the next term, k d n^{d-1}.
Now say p(n) = a n^d + terms of degree at most d-1.
Then q(n) = (a k d n^{d-1} + terms of degree at most d-2) + (terms of degree at most d-2), which is indeed of degree d-1.
4. For p(n) a polynomial, let Delta p be the polynomial with values (Delta p)(n) = p(n) - p(n-1).
Notice that if p only takes integer values (when fed integers), then Delta p does so too.
a) Show that Delta {n choose k} = {n n-1 choose k-1}.
(n choose k) - (n-1 choose k) counts all k-element subsets of {1..n} minus all k-element subsets of {1..n-1}. What's left over is k-element subsets of {1..n} that include n. By ripping out the element n, those subsets correspond 1:1 with (k-1)-element subsets of {1..n-1}. The number of those is {n-1 choose k-1}.
b) Show that every polynomial p(n) is a linear combination of the polynomials {n choose k}, where k goes from 0 to degree p.
If p is constant it's clear, which will be the base of our induction.
Let d = degree(p).
Then p(n) = c n^d + a polynomial of degree < d.
Note that d! {n choose d} = n^d + a polynomial of degree < d.
So p(n) - c d! {n choose d} = a polynomial of degree < d.
By induction on d, the RHS is a linear combination as desired. Now add c d! {n choose d} to both sides.
c) Give an example of a polynomial with noninteger coefficients that nonetheless always produces integers.
{n choose 2} = n(n-1)/2.
d) Show that every integer-valued polynomial p(n) is a linear combination with integer coefficients of the polynomials {n choose k}, where k goes from 0 to degree p.
(In particular, this applies to Hilbert polynomials.)
Write p(n) = sum_{k=0}^{degree p} c_k {n choose k} using part (b).
Then (Delta^i p)(n) = sum_{k=0}^{degree p} c_k {n-i choose k-i}.
Obviously, all the terms with k < i vanish for any n.
If n = i, then the terms with k > i vanish too.
So (Delta^i p)(i) = c_i.
Notice that when q is integer-valued, so is Delta q, so Delta^i p only takes on integer values. Hence each c_i is an integer.
5. Let I in C[x_1...x_5] be generated by {x_i x_j - x_k x_l}, for all i,j,k,l such that i+j=k+l.
a) Show this is a Gr\"obner basis with respect to lex order.
First notice that we can leave out the generators with i > j since they're the same as the ones with i and j switched. Then we can leave out those with i=k or j=k, since the generator is then 0.
Consider the subset of the form x_i x_j - x_{floor{(i+j)/2}} x_{ceiling{(i+j)/2}}, where floor(x) is the greatest integer below x, ceiling(x) the least above.
Call this second term RHS(i,j) for now. Then any other relation x_i x_j - x_k x_l can be written as
x_i x_j - RHS(i,j) - (x_k x_l - RHS(k,l))
so this subset already generates the ideal. In particular, if it's a Gr\"obner basis, then adding the other generators won't break that.
At this point all of our generators have i at most j. But the i=j generators and the i=j-1 generators are x_i x_i - x_i x_i and x_i x_j - x_i x_j, i.e. zero. So we were already leaving those out.
When we compute the S-polynomial of two of these generators (ignoring the pairs with relatively prime initial terms, since we can), we get a cubic. So let's see what the reduction algorithm does to an arbitrary cubic monomial x_a x_b x_c, with a at most b at most c. (Note that a,b,c may include repeats.)
If c-a > 1, then the reduction algorithm trades x_a x_c either for x_d^2 or x_d x_{d+1}, depending on c-a being even or odd. In particular it gives us another cubic monomial x_a' x_b' x_c', where a+b+c = a'+b'+c'. It only gets stuck when a=b=c, or a=b=c-1, or a+1=b=c. We can even predict which case we'll get to, depending on the value of a+b+c mod 3 (0 if a=b=c, 1 if a=b=c-1, 2 if a+1=b=c).
Now let's see what happens to an S-polynomial x_a x_b x_c - x_d x_e x_f under reduction. Observe that a+b+c=d+e+f. We've just figured out that the reduction algorithm will replace either term with the same cubic monomial, and then they'll cancel. So the S-polynomials reduce to zero, making this a Gr\"obner basis.
b) Find the reduced Gr\"obner basis.
It's the subset we said above -- x_i x_j - RHS(i,j), where i < j-1.
The leading coefficients are all 1.
Since each generator is homogeneous quadratic, the only way this set would fail to be a reduced Gr\"obner basis is if some term of some generator was a constant multiple of the leading term of another generator. But the left terms have i < j-1, and the RHS terms have i'=j' or i'=j'-1.
c) Decompose V(the initial ideal).
Two variables can be nonzero at the same time only if they're adjacent, like x_3 and x_4, otherwise their product is the leading term of one of the generators.
So the components are the 12-plane, the 23-plane, the 34-plane, and the 45-plane. (And so on, if we had more variables.)
d) Compute the Hilbert polynomial.
The easiest thing is to compute directly the number of standard monomials of degree n. We've already figured out that a monomial is standard if it uses one variable, or two adjacent variables.
The number of monomials x_i^k x_{i+1}^{n-k}, for k not 0 or n, is n-1.
So the total is 5 (for the monomials x_i^n, i from 1 to 5) plus 4(n-1) (just counted, where i goes from 1 to 4), or 4n+1.
Let J = I + < r >.
Show that
a) For each n, h_J(n) is at least h_I(n) - h_I(n-k).
b) If they are equal for all n, then r is not a zero divisor.
a) Consider the map (R/I)_{n-k} -> (R/I)_n given by multiplication by r.
We figured out in class that the quotient by the image is (R/J)_n.
So dim (R/I)_n = dim (R/J)_n + dim r*(R/I)_{n-k}.
The dimension of r*(R/I)_{n-k} is at most the dimension of (R/I)_{n-k}, so we get the inequality claimed.
b) If they're equal, then dim r*(R/I)_{n-k} = dim (R/I)_{n-k}, so the multiply-by-r map has no kernel. Which means r is not a zero divisor.
2. A list {r_1, r_2, ..., r_m} is called a regular sequence if each r_j is not a zero divisor in R/< r_1, ..., r_{j-1} >.
If {b,c} is a regular sequence, show that {c,b} is a regular sequence.
Oops: I had meant b,c to be homogeneous. (It's true even if they're not, but don't bother with that.)
We showed in class that if r is not a zero divisor in R/I, and is homogeneous of degree k, then H_{I+< r >}(t) = H_I(t) * (1-t^k).
So if {b,c} is a regular sequence, with degrees k,k', then H_{< b,c >}(t) = H_0(t) (1 - t^k) (1 - t^k').
Certainly c is not a zero divisor in R. So H_{< c >}(t) = H_0(t) (1 - t^k').
By the previous question, H_{< c,b >}(t) is coefficientwise at least H_0(t) (1 - t^k') (1 - t^k), with equality iff b is not a zero divisor in R/< c >.
But since < b,c > = < c,b >, we know this is an equality -- so b is not a zero divisor.
3. Let p(n) be a polynomial of degree d, and k a number. Show that q(n) = p(n) - p(n-k) is a polynomial of degree d-1.
First we check it for p(n) = n^d. Then q(n) = n^d - (n^d - d n^{d-1} k + ...), canceling the first term in the binomial series but not the next term, k d n^{d-1}.
Now say p(n) = a n^d + terms of degree at most d-1.
Then q(n) = (a k d n^{d-1} + terms of degree at most d-2) + (terms of degree at most d-2), which is indeed of degree d-1.
4. For p(n) a polynomial, let Delta p be the polynomial with values (Delta p)(n) = p(n) - p(n-1).
Notice that if p only takes integer values (when fed integers), then Delta p does so too.
a) Show that Delta {n choose k} = {
(n choose k) - (n-1 choose k) counts all k-element subsets of {1..n} minus all k-element subsets of {1..n-1}. What's left over is k-element subsets of {1..n} that include n. By ripping out the element n, those subsets correspond 1:1 with (k-1)-element subsets of {1..n-1}. The number of those is {n-1 choose k-1}.
b) Show that every polynomial p(n) is a linear combination of the polynomials {n choose k}, where k goes from 0 to degree p.
If p is constant it's clear, which will be the base of our induction.
Let d = degree(p).
Then p(n) = c n^d + a polynomial of degree < d.
Note that d! {n choose d} = n^d + a polynomial of degree < d.
So p(n) - c d! {n choose d} = a polynomial of degree < d.
By induction on d, the RHS is a linear combination as desired. Now add c d! {n choose d} to both sides.
c) Give an example of a polynomial with noninteger coefficients that nonetheless always produces integers.
{n choose 2} = n(n-1)/2.
d) Show that every integer-valued polynomial p(n) is a linear combination with integer coefficients of the polynomials {n choose k}, where k goes from 0 to degree p.
(In particular, this applies to Hilbert polynomials.)
Write p(n) = sum_{k=0}^{degree p} c_k {n choose k} using part (b).
Then (Delta^i p)(n) = sum_{k=0}^{degree p} c_k {n-i choose k-i}.
Obviously, all the terms with k < i vanish for any n.
If n = i, then the terms with k > i vanish too.
So (Delta^i p)(i) = c_i.
Notice that when q is integer-valued, so is Delta q, so Delta^i p only takes on integer values. Hence each c_i is an integer.
5. Let I in C[x_1...x_5] be generated by {x_i x_j - x_k x_l}, for all i,j,k,l such that i+j=k+l.
a) Show this is a Gr\"obner basis with respect to lex order.
First notice that we can leave out the generators with i > j since they're the same as the ones with i and j switched. Then we can leave out those with i=k or j=k, since the generator is then 0.
Consider the subset of the form x_i x_j - x_{floor{(i+j)/2}} x_{ceiling{(i+j)/2}}, where floor(x) is the greatest integer below x, ceiling(x) the least above.
Call this second term RHS(i,j) for now. Then any other relation x_i x_j - x_k x_l can be written as
x_i x_j - RHS(i,j) - (x_k x_l - RHS(k,l))
so this subset already generates the ideal. In particular, if it's a Gr\"obner basis, then adding the other generators won't break that.
At this point all of our generators have i at most j. But the i=j generators and the i=j-1 generators are x_i x_i - x_i x_i and x_i x_j - x_i x_j, i.e. zero. So we were already leaving those out.
When we compute the S-polynomial of two of these generators (ignoring the pairs with relatively prime initial terms, since we can), we get a cubic. So let's see what the reduction algorithm does to an arbitrary cubic monomial x_a x_b x_c, with a at most b at most c. (Note that a,b,c may include repeats.)
If c-a > 1, then the reduction algorithm trades x_a x_c either for x_d^2 or x_d x_{d+1}, depending on c-a being even or odd. In particular it gives us another cubic monomial x_a' x_b' x_c', where a+b+c = a'+b'+c'. It only gets stuck when a=b=c, or a=b=c-1, or a+1=b=c. We can even predict which case we'll get to, depending on the value of a+b+c mod 3 (0 if a=b=c, 1 if a=b=c-1, 2 if a+1=b=c).
Now let's see what happens to an S-polynomial x_a x_b x_c - x_d x_e x_f under reduction. Observe that a+b+c=d+e+f. We've just figured out that the reduction algorithm will replace either term with the same cubic monomial, and then they'll cancel. So the S-polynomials reduce to zero, making this a Gr\"obner basis.
b) Find the reduced Gr\"obner basis.
It's the subset we said above -- x_i x_j - RHS(i,j), where i < j-1.
The leading coefficients are all 1.
Since each generator is homogeneous quadratic, the only way this set would fail to be a reduced Gr\"obner basis is if some term of some generator was a constant multiple of the leading term of another generator. But the left terms have i < j-1, and the RHS terms have i'=j' or i'=j'-1.
c) Decompose V(the initial ideal).
Two variables can be nonzero at the same time only if they're adjacent, like x_3 and x_4, otherwise their product is the leading term of one of the generators.
So the components are the 12-plane, the 23-plane, the 34-plane, and the 45-plane. (And so on, if we had more variables.)
d) Compute the Hilbert polynomial.
The easiest thing is to compute directly the number of standard monomials of degree n. We've already figured out that a monomial is standard if it uses one variable, or two adjacent variables.
The number of monomials x_i^k x_{i+1}^{n-k}, for k not 0 or n, is n-1.
So the total is 5 (for the monomials x_i^n, i from 1 to 5) plus 4(n-1) (just counted, where i goes from 1 to 4), or 4n+1.
Wednesday 3/11
Def: the Hilbert dimension of a homogeneous ideal is 1 + degree of the Hilbert polynomial, or 0 if the Hilbert polynomial is 0.
Theorem. HilbDim(I) = HilbDim(Rad(I)).
Proof. If I is not radical, we can add some homogeneous x whose square is in I.
Then do nullity plus rank on the map (R/I)_n -> (R/I)_{n+k} that multiplies by x.
Theorem. Let I be homogeneous.
1) If I is a prime ideal, and J (homogeneous) properly contains I, then HilbDim(J) < HilbDim(I).
2a) If I is not prime, then there exists J (homogeneous) properly containing it, with HilbDim(J) = HilbDim(I).
2b) That J can be taken to be prime.
Proof.
1) Even adding one element lowers the HilbDim by 1, by a calculation last week.
2a) If I is not radical, use the previous theorem.
Otherwise let a,b not in I, ab in I, and check that the map R/I -> R/I+< a > \oplus R/I+< b > is 1:1. Do nullity plus rank on that.
2b) Repeat 2a and use ACC.
We didn't get to
Theorem. HilbDim(I) = homogeneous KrullDim(I) (which is at most KrullDim(I)).
Proof. In a chain of homogeneous prime ideals, the HilbDim must drop at each step by (1) of the last theorem. That gives "HilbDim is at most homogeneous KrullDim".
Conversely, we can alternate the following two steps: increase I to a prime ideal without changing the HilbDim (using (2b)), and then increase it using one new homogeneous generator, lowering the HilbDim by 1, by the calculation last week. We get stuck only when we get to whole ring. This constructs a long sequence of prime ideals, giving "HilbDim is at least homogeneous KrullDim".
Theorem. HilbDim(I) = HilbDim(Rad(I)).
Proof. If I is not radical, we can add some homogeneous x whose square is in I.
Then do nullity plus rank on the map (R/I)_n -> (R/I)_{n+k} that multiplies by x.
Theorem. Let I be homogeneous.
1) If I is a prime ideal, and J (homogeneous) properly contains I, then HilbDim(J) < HilbDim(I).
2a) If I is not prime, then there exists J (homogeneous) properly containing it, with HilbDim(J) = HilbDim(I).
2b) That J can be taken to be prime.
Proof.
1) Even adding one element lowers the HilbDim by 1, by a calculation last week.
2a) If I is not radical, use the previous theorem.
Otherwise let a,b not in I, ab in I, and check that the map R/I -> R/I+< a > \oplus R/I+< b > is 1:1. Do nullity plus rank on that.
2b) Repeat 2a and use ACC.
We didn't get to
Theorem. HilbDim(I) = homogeneous KrullDim(I) (which is at most KrullDim(I)).
Proof. In a chain of homogeneous prime ideals, the HilbDim must drop at each step by (1) of the last theorem. That gives "HilbDim is at most homogeneous KrullDim".
Conversely, we can alternate the following two steps: increase I to a prime ideal without changing the HilbDim (using (2b)), and then increase it using one new homogeneous generator, lowering the HilbDim by 1, by the calculation last week. We get stuck only when we get to whole ring. This constructs a long sequence of prime ideals, giving "HilbDim is at least homogeneous KrullDim".
Monday, March 09, 2009
Monday 3/9
Domains, prime ideals, Krull dimension.
Next time: Krull dimension = degree(Hilbert polynomial)+1 for homogeneous ideals.
Next time: Krull dimension = degree(Hilbert polynomial)+1 for homogeneous ideals.
Thursday, March 05, 2009
HW #7, due Wednesday 3/11 (corrected)
1. Let I be a homogeneous ideal in a polynomial ring R, and r a homogeneous element of degree k.
Let J = I + < r >.
Show that
a) For each n, h_J(n) is at least h_I(n) - h_I(n-k).
b) If they are equal for all n, then r is not a zero divisor.
2. A list {r_1, r_2, ..., r_m} is called a regular sequence if each r_j is not a zero divisor in R/< r_1, ..., r_{j-1} >.
If {b,c} is a regular sequence, show that {c,b} is a regular sequence.
Oops: I had meant b,c to be homogeneous. (It's true even if they're not, but don't bother with that.)
3. Let p(n) be a polynomial of degree d, and k a number. Show that q(n) = p(n) - p(n-k) is a polynomial of degree d-1.
4. For p(n) a polynomial, let Delta p be the polynomial with values (Delta p)(n) = p(n) - p(n-1).
Notice that if p only takes integer values (when fed integers), then Delta p does so too.
a) Show that Delta {n choose k} = {n n-1 choose k-1}.
b) Show that every polynomial p(n) is a linear combination of the polynomials {n choose k}, where k goes from 0 to degree p.
c) Give an example of a polynomial with noninteger coefficients that nonetheless always produces integers.
d) Show that every integer-valued polynomial p(n) is a linear combination with integer coefficients of the polynomials {n choose k}, where k goes from 0 to degree p.
(In particular, this applies to Hilbert polynomials.)
5. Let I in C[x_1...x_5] be generated by {x_i x_j - x_k x_l}, for all i,j,k,l such that i+j=k+l.
a) Show this is a Gr\"obner basis with respect to lex order.
b) Find the reduced Gr\"obner basis.
c) Decompose V(the initial ideal).
d) Compute the Hilbert polynomial.
Let J = I + < r >.
Show that
a) For each n, h_J(n) is at least h_I(n) - h_I(n-k).
b) If they are equal for all n, then r is not a zero divisor.
2. A list {r_1, r_2, ..., r_m} is called a regular sequence if each r_j is not a zero divisor in R/< r_1, ..., r_{j-1} >.
If {b,c} is a regular sequence, show that {c,b} is a regular sequence.
Oops: I had meant b,c to be homogeneous. (It's true even if they're not, but don't bother with that.)
3. Let p(n) be a polynomial of degree d, and k a number. Show that q(n) = p(n) - p(n-k) is a polynomial of degree d-1.
4. For p(n) a polynomial, let Delta p be the polynomial with values (Delta p)(n) = p(n) - p(n-1).
Notice that if p only takes integer values (when fed integers), then Delta p does so too.
a) Show that Delta {n choose k} = {
b) Show that every polynomial p(n) is a linear combination of the polynomials {n choose k}, where k goes from 0 to degree p.
c) Give an example of a polynomial with noninteger coefficients that nonetheless always produces integers.
d) Show that every integer-valued polynomial p(n) is a linear combination with integer coefficients of the polynomials {n choose k}, where k goes from 0 to degree p.
(In particular, this applies to Hilbert polynomials.)
5. Let I in C[x_1...x_5] be generated by {x_i x_j - x_k x_l}, for all i,j,k,l such that i+j=k+l.
a) Show this is a Gr\"obner basis with respect to lex order.
b) Find the reduced Gr\"obner basis.
c) Decompose V(the initial ideal).
d) Compute the Hilbert polynomial.
Wednesday, March 04, 2009
Answers to HW #6 (tiny correction to #1)
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.
If g_i = f^2 h, then h g_i = f^2 h^2 is in I too, so fh is in I (by the assumption I = Rad(I)). Hence some init(g_j) divides init(fh). By the assumption deg f > 0, j is not i. Since init(g_j) divides init(fh), it divides init(g f^2 h) = init(g_i). But then our list is not a reduced Gr\"obner basis, contradiction.
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.
If I is not radical, then there exists g not in I, and a number N, such that g^N is in I. Let k be the least number such that g^k is in I. (So k > 1, and is at most N.) Let f = g^{k-1}. Then f^2 = g^{2(k-1)} = g^k g^{k-2}, which only makes sense because k is at least 2. In particular, f is not in I, but f^2 is in I.
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.
#3 is actually the special case of #4 where each f_i = init(f_i). So we'll just do #4.
By #2 it's enough to check that f^2 in I => f in I.
So say f is a polynomial such that f^2 is in I. If f=0 we're done; otherwise we can talk about init(f).
Since f^2 is in I and we have a Gr\"obner basis, some init(f_i) | init(f^2) = init(f)^2.
Since init(f_i) is squarefree, it already divides init(f).
So we can replace f by f - m f_i where m = init(f)/init(f_i), canceling the leading term of f. This new guy has (f - mf_i)^2 = f^2 + f_i(-2m + f_i), so again in I, so we can run the reduction algorithm again. Since it only gets stuck when f=0, we see that f reduces to 0, which means f is in I.
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.
a) If f^N is in I intersect J, then f^N is in I and f^N is in J, hence f is in I and J, hence f is in I intersect J.
b) My favorite example is I = < y >, J = < y-x^2 >. (We can see that J is radical by taking a term order for which y is the leading term and applying #4.)
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.
If a=0, we have bc,bd,de=0 left.
If b=0, we have de=0 left, so either d=0 or e=0. So far {a=b=d=0} union {a=b=e=0}.
If not b=0, we have c=d=0. This adds {a=c=d=0}.
If not a=0, we have c=e=0, leaving bd=0, so either b=0 or d=0: {c=e=b=0} union {c=e=d=0}.
In the end, the solutions are the union of five 2-planes in 5-space.
Show that each g_i is squarefree, i.e. is not divisible by f^2 for any polynomial f of degree > 0.
If g_i = f^2 h, then h g_i = f^2 h^2 is in I too, so fh is in I (by the assumption I = Rad(I)). Hence some init(g_j) divides init(fh). By the assumption deg f > 0, j is not i. Since init(g_j) divides init(fh), it divides init(
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.
If I is not radical, then there exists g not in I, and a number N, such that g^N is in I. Let k be the least number such that g^k is in I. (So k > 1, and is at most N.) Let f = g^{k-1}. Then f^2 = g^{2(k-1)} = g^k g^{k-2}, which only makes sense because k is at least 2. In particular, f is not in I, but f^2 is in I.
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.
#3 is actually the special case of #4 where each f_i = init(f_i). So we'll just do #4.
By #2 it's enough to check that f^2 in I => f in I.
So say f is a polynomial such that f^2 is in I. If f=0 we're done; otherwise we can talk about init(f).
Since f^2 is in I and we have a Gr\"obner basis, some init(f_i) | init(f^2) = init(f)^2.
Since init(f_i) is squarefree, it already divides init(f).
So we can replace f by f - m f_i where m = init(f)/init(f_i), canceling the leading term of f. This new guy has (f - mf_i)^2 = f^2 + f_i(-2m + f_i), so again in I, so we can run the reduction algorithm again. Since it only gets stuck when f=0, we see that f reduces to 0, which means f is in I.
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.
a) If f^N is in I intersect J, then f^N is in I and f^N is in J, hence f is in I and J, hence f is in I intersect J.
b) My favorite example is I = < y >, J = < y-x^2 >. (We can see that J is radical by taking a term order for which y is the leading term and applying #4.)
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.
If a=0, we have bc,bd,de=0 left.
If b=0, we have de=0 left, so either d=0 or e=0. So far {a=b=d=0} union {a=b=e=0}.
If not b=0, we have c=d=0. This adds {a=c=d=0}.
If not a=0, we have c=e=0, leaving bd=0, so either b=0 or d=0: {c=e=b=0} union {c=e=d=0}.
In the end, the solutions are the union of five 2-planes in 5-space.
Wednesday 3/4
Thm. The Hilbert function of R/I is eventually a polynomial, the "Hilbert polynomial".
Def. Zero divisor in a ring.
Thm: If R/I contains a nonzero divisor r of degree k, then one can write down the Hilbert series and polynomial of R/(I +) in terms of that of R/I.
Ex. If r,s are of degree A and B in C[x_1..x_n], then r is automatically a nonzero divisor, but s might be a zero divisor in R/< r >. If it's not, then the Hilbert series is 1/(1-t)^n * (1-t^A) * (1-t^B).
(Remember a HW problem that asked for a Hilbert series that looked like that?)
Def. Zero divisor in a ring.
Thm: If R/I contains a nonzero divisor r of degree k, then one can write down the Hilbert series and polynomial of R/(I +
Ex. If r,s are of degree A and B in C[x_1..x_n], then r is automatically a nonzero divisor, but s might be a zero divisor in R/< r >. If it's not, then the Hilbert series is 1/(1-t)^n * (1-t^A) * (1-t^B).
(Remember a HW problem that asked for a Hilbert series that looked like that?)
Monday 3/2
We proved the strong Nullstellensatz: I_V(I) = I.
I talked about my favorite Gr\"obner bases, which led to pipe dreams. The paper is here if you're feeling really ambitious.
I talked about my favorite Gr\"obner bases, which led to pipe dreams. The paper is here if you're feeling really ambitious.
Tuesday, March 03, 2009
Answers to HW #5
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.
When the reduction algorithm is asked to reduce a homogeneous polynomial, using other homogeneous polynomials, the result is homogeneous.
The S-polynomial of two homogeneous polynomials is homogeneous (of degree = degree(that lcm)).
Hence Buchberger's algorithm creates not just a Gr\"obner basis, but one 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.
Let {x^e} denote the set of standard monomials of degree n (e is really a vector, here).
Then the claim is that their images {x^e + I_n} form a basis of R_n / I_n.
Proof: given an element r of R_n (not necessarily in I), when we run the reduction algorithm on r we get stuck at a new element r+i in the same coset r+I. But this r+i is a C-linear combination of the {x^e} (or we wouldn't be stuck). So r+I is a combination of {x^e + I}, i.e. the {x^e + I_n} span R_n / I_n.
Now look at a linear combination \sum_e c_e x^e. For this to give the zero element of R_n / I_n, it needs to be in I_n, i.e. to be in I. But the reduction algorithm will be stuck on this, unless it's already the zero polynomial, i.e. all the c_e were zero. So the {x^e + I_n} are linearly independent.
3. Show that h_I = h_{init I}, so H_I = H_{init I} (the Hilbert series).
I and init I have the same standard monomials (since they were defined using only the initial terms in the Gr\"obner basis), so by #2 their Hilbert functions are the same, and the Hilbert
series are derived from those.
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).
Either way we get (1 - t^2) / (1-t)^3; the 2 is 0+2+0 when b^2 is the leading term, and 1+0+1 when ac is.
5. Let I = < the entries of M^2, where M is a 2x2 matrix >. Compute the Hilbert series H_I.
We computed a Gr\"obner basis for I in class,
bc + d^2, ac + cd, ab + bd, a^2 - d^2, ad^2 + d^3
whose initial terms are {bc, ac, ab, a^2, ad^2}.
Then our formula for the Hilbert series of that monomial ideal is 1/(1-t)^4 times
1 - (4t^2 + t^3) + (5t^3 + 4t^4 + t^5) - (t^3 + 3t^4 + 5t^5 + t^6) + (t^4 + t^5 + 3t^6) - t^6
where I've grouped the 2^5 terms according to the sizes of the subsets of the generators,
= 1 - 4t^2 + 3t^3 + 2t^4 - 3t^5 + t^6.
6. Let J be the larger ideal containing I and also the generator Trace(M). Compute the Hilbert series H_J.
This has a much simpler reduced Gr\"obner basis: a+d, bc+d^2.
The initial terms are {a,bc}, and the numerator of the Hilbert series is 1 - t - t^2 + t^3.
Note that this factors as (1-t)(1-t^2), which is secretly a statement about the independence of these generators.
1. Show that I has a Grobner basis consisting of homogeneous polynomials.
When the reduction algorithm is asked to reduce a homogeneous polynomial, using other homogeneous polynomials, the result is homogeneous.
The S-polynomial of two homogeneous polynomials is homogeneous (of degree = degree(that lcm)).
Hence Buchberger's algorithm creates not just a Gr\"obner basis, but one 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.
Let {x^e} denote the set of standard monomials of degree n (e is really a vector, here).
Then the claim is that their images {x^e + I_n} form a basis of R_n / I_n.
Proof: given an element r of R_n (not necessarily in I), when we run the reduction algorithm on r we get stuck at a new element r+i in the same coset r+I. But this r+i is a C-linear combination of the {x^e} (or we wouldn't be stuck). So r+I is a combination of {x^e + I}, i.e. the {x^e + I_n} span R_n / I_n.
Now look at a linear combination \sum_e c_e x^e. For this to give the zero element of R_n / I_n, it needs to be in I_n, i.e. to be in I. But the reduction algorithm will be stuck on this, unless it's already the zero polynomial, i.e. all the c_e were zero. So the {x^e + I_n} are linearly independent.
3. Show that h_I = h_{init I}, so H_I = H_{init I} (the Hilbert series).
I and init I have the same standard monomials (since they were defined using only the initial terms in the Gr\"obner basis), so by #2 their Hilbert functions are the same, and the Hilbert
series are derived from those.
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).
Either way we get (1 - t^2) / (1-t)^3; the 2 is 0+2+0 when b^2 is the leading term, and 1+0+1 when ac is.
5. Let I = < the entries of M^2, where M is a 2x2 matrix >. Compute the Hilbert series H_I.
We computed a Gr\"obner basis for I in class,
bc + d^2, ac + cd, ab + bd, a^2 - d^2, ad^2 + d^3
whose initial terms are {bc, ac, ab, a^2, ad^2}.
Then our formula for the Hilbert series of that monomial ideal is 1/(1-t)^4 times
1 - (4t^2 + t^3) + (5t^3 + 4t^4 + t^5) - (t^3 + 3t^4 + 5t^5 + t^6) + (t^4 + t^5 + 3t^6) - t^6
where I've grouped the 2^5 terms according to the sizes of the subsets of the generators,
= 1 - 4t^2 + 3t^3 + 2t^4 - 3t^5 + t^6.
6. Let J be the larger ideal containing I and also the generator Trace(M). Compute the Hilbert series H_J.
This has a much simpler reduced Gr\"obner basis: a+d, bc+d^2.
The initial terms are {a,bc}, and the numerator of the Hilbert series is 1 - t - t^2 + t^3.
Note that this factors as (1-t)(1-t^2), which is secretly a statement about the independence of these generators.
Subscribe to:
Posts (Atom)