Tuesday, May 12, 2009
Friday, May 01, 2009
Final and review sessions
Final: Tuesday May 12th, 11 AM-1:30 PM, in our usual room.
You may bring notes, HW, and stuff printed from the website, but not books.
Review sessions: Wednesday 6th, Monday 11th, at noon in the Malott lounge on the 5th floor. Be there or b2.
You may bring notes, HW, and stuff printed from the website, but not books.
Review sessions: Wednesday 6th, Monday 11th, at noon in the Malott lounge on the 5th floor. Be there or b2.
Wednesday, April 29, 2009
Answers to HW #11
1. Let R = F_p[x,y], and I generated by y(y-x^2).
Show there is no Frobenius splitting on R that compatibly splits I.
(Hint: if I were compatibly split, then so would various other ideals be, including one that isn't radical.)
We can colon out {y} to get {y-x^2}, or {y-x^2} to get {y}.
Adding those together, we get {y,y-x^2} = {y,x^2} (meaning the ideals; sorry about the lack of angle brackets).
These would all be compatibly split, hence radical, but {y,x^2} isn't.
2. Same problem, but I is generated by xy(x+y).
Colon out {x} to get {y(x+y)}, colon out {y(x+y)} to get {x},
add them together to get {x, y(x+y)} = {x, y^2}, same problem.
3. Let R be a graded ring, and phi a Frobenius splitting of it.
a) Show that phi is determined by its values on homogeneous elements.
b) For r homogeneous of degree k, define phi'(r) = the degree k/p part of phi(r), or 0 if k/p is not an integer.
For r not homogeneous, define phi'(r) = the sum of phi'(its homogeneous pieces).
Show that phi' is a Frobenius splitting.
c) Give a reasonable definition of a "graded Frobenius splitting".
a) This means, if phi_1 and phi_2 agree on all homogeneous elements, then they're supposed to be equal.
phi_1(anything) = phi_1(sum of homogeneous elements)
= sum of phi_1(those homogeneous elements), since phi_1 is additive
= sum of phi_2(those homogeneous elements), since phi_1 = phi_2 on them
= phi_2(sum of those homogeneous elements), since phi_2 is additive
= phi_2(original thing).
b) We have to check conditions (1),(2),(3) of a Frobenius splitting.
We get condition (1) for free, pretty much.
(3) is very easy: 1 is in R_0, so phi'(1) = the degree 0 part of phi(1) = the degree 0 part of 1 = 1.
(2) we only have to check homogeneous elements a,b, say of degrees j,k.
Then phi'(a^p b) = degree j+k/p part of phi(a^p b) = degree j+k/p part of a phi(b) = a*(degree k/p part of phi(b)) = a*phi'(b).
c) Call phi graded if its associated phi' is again phi.
Which is to say, phi(a homogeneous element of degree k) should be of degree k/p, and hence 0 if p doesn't divide k.
4. Let R be the subring of F_p[x] generated by x^2 and x^3, i.e. polynomials with no linear term. Show that R has no Frobenius splitting.
Note first that R is a graded ring, whose nth graded piece is multiples of x^n, unless n=1 in which case R_1=0.
Let phi be a splitting (for contradiction), and phi' its graded part, as constructed in #3.
Careful: you can't say phi'(x^p) = x phi'(1). That only holds for elements of R that are pth powers of elements of R.
x^3 = phi'(x^{3p}) = phi'(x^{2p} x^p) = x^2 phi'(x^p).
But phi'(x^p) should be degree 1, and the only thing there is 0.
So x^2 phi'(x^p) = x^2 * 0 = 0. Contradiction.
Hence there was no splitting.
5. Let R = C[a,b,c] / {ac} stupid blogger.com.
Let I be generated by {a,b}, as an ideal in R not just C[a,b,c].
a) Compute the Hilbert series H_R and H_{R/I}.
b) Show that H_{R/I} is not H_R times a polynomial.
c) Prove that the Hilbert Syzygy Theorem fails for this R and I; there is no finite graded resolution.
a) H_R = 1/(1-t)^3 * (1-t^2), H_{R/I} = H_{C[a,b,c]/{a,b}} = 1/(1-t).
b) The ratio is (1-t)^2 / (1-t^2) = (1-t)/(1+t).
The coefficients of its power series go 1,-2,+2,-2,+2,-2,... by the way.
c) If there were a finite graded resolution 0 -> ... R^powers -> ... -> R -> R/I -> 0, we could compute H_{R/I} = H_R * (1 - this + that ... ) where the finitely many terms in that alternating sum come from the terms in the resolution. But then H_{R/I} / H_R would be a polynomial.
(In fact there is a resolution that goes ... -> R^2 -> R^2 -> R^2 -> R -> R/I -> 0, with R^2s going back forever.)
6. Here is a simple program in Macaulay 2, a program to do (mostly) ring theory calculations.
Figure out what it's computing. Here's a comprehensive index of M2 commands. If you want to actually run M2 (so e.g. you can play with the code), here's how to get started.
Show there is no Frobenius splitting on R that compatibly splits I.
(Hint: if I were compatibly split, then so would various other ideals be, including one that isn't radical.)
We can colon out {y} to get {y-x^2}, or {y-x^2} to get {y}.
Adding those together, we get {y,y-x^2} = {y,x^2} (meaning the ideals; sorry about the lack of angle brackets).
These would all be compatibly split, hence radical, but {y,x^2} isn't.
2. Same problem, but I is generated by xy(x+y).
Colon out {x} to get {y(x+y)}, colon out {y(x+y)} to get {x},
add them together to get {x, y(x+y)} = {x, y^2}, same problem.
3. Let R be a graded ring, and phi a Frobenius splitting of it.
a) Show that phi is determined by its values on homogeneous elements.
b) For r homogeneous of degree k, define phi'(r) = the degree k/p part of phi(r), or 0 if k/p is not an integer.
For r not homogeneous, define phi'(r) = the sum of phi'(its homogeneous pieces).
Show that phi' is a Frobenius splitting.
c) Give a reasonable definition of a "graded Frobenius splitting".
a) This means, if phi_1 and phi_2 agree on all homogeneous elements, then they're supposed to be equal.
phi_1(anything) = phi_1(sum of homogeneous elements)
= sum of phi_1(those homogeneous elements), since phi_1 is additive
= sum of phi_2(those homogeneous elements), since phi_1 = phi_2 on them
= phi_2(sum of those homogeneous elements), since phi_2 is additive
= phi_2(original thing).
b) We have to check conditions (1),(2),(3) of a Frobenius splitting.
We get condition (1) for free, pretty much.
(3) is very easy: 1 is in R_0, so phi'(1) = the degree 0 part of phi(1) = the degree 0 part of 1 = 1.
(2) we only have to check homogeneous elements a,b, say of degrees j,k.
Then phi'(a^p b) = degree j+k/p part of phi(a^p b) = degree j+k/p part of a phi(b) = a*(degree k/p part of phi(b)) = a*phi'(b).
c) Call phi graded if its associated phi' is again phi.
Which is to say, phi(a homogeneous element of degree k) should be of degree k/p, and hence 0 if p doesn't divide k.
4. Let R be the subring of F_p[x] generated by x^2 and x^3, i.e. polynomials with no linear term. Show that R has no Frobenius splitting.
Note first that R is a graded ring, whose nth graded piece is multiples of x^n, unless n=1 in which case R_1=0.
Let phi be a splitting (for contradiction), and phi' its graded part, as constructed in #3.
Careful: you can't say phi'(x^p) = x phi'(1). That only holds for elements of R that are pth powers of elements of R.
x^3 = phi'(x^{3p}) = phi'(x^{2p} x^p) = x^2 phi'(x^p).
But phi'(x^p) should be degree 1, and the only thing there is 0.
So x^2 phi'(x^p) = x^2 * 0 = 0. Contradiction.
Hence there was no splitting.
5. Let R = C[a,b,c] / {ac} stupid blogger.com.
Let I be generated by {a,b}, as an ideal in R not just C[a,b,c].
a) Compute the Hilbert series H_R and H_{R/I}.
b) Show that H_{R/I} is not H_R times a polynomial.
c) Prove that the Hilbert Syzygy Theorem fails for this R and I; there is no finite graded resolution.
a) H_R = 1/(1-t)^3 * (1-t^2), H_{R/I} = H_{C[a,b,c]/{a,b}} = 1/(1-t).
b) The ratio is (1-t)^2 / (1-t^2) = (1-t)/(1+t).
The coefficients of its power series go 1,-2,+2,-2,+2,-2,... by the way.
c) If there were a finite graded resolution 0 -> ... R^powers -> ... -> R -> R/I -> 0, we could compute H_{R/I} = H_R * (1 - this + that ... ) where the finitely many terms in that alternating sum come from the terms in the resolution. But then H_{R/I} / H_R would be a polynomial.
(In fact there is a resolution that goes ... -> R^2 -> R^2 -> R^2 -> R -> R/I -> 0, with R^2s going back forever.)
6. Here is a simple program in Macaulay 2, a program to do (mostly) ring theory calculations.
Figure out what it's computing. Here's a comprehensive index of M2 commands. If you want to actually run M2 (so e.g. you can play with the code), here's how to get started.
-- What is the following code doing?
-- You can load it into Macaulay 2 by saying
-- load "hw.m2"
-- and run the subroutines yourself to figure out what they do.
syze = 2;
-- If you're willing to wait a while (overnight?), try changing this to syze=3
R = QQ[a_(1,1)..a_(syze,syze),b_(1,1)..b_(syze,syze)];
A = transpose genericMatrix(R,a_(1,1),syze,syze);
B = transpose genericMatrix(R,b_(1,1),syze,syze);
Generic matrices filled with variables
dp = M -> matrix apply(syze,i->apply(syze,j->(
if (i==j) then M_(i,j) else 0)));
lp = M -> matrix apply(syze,i->apply(syze,j->(
if (i>j) then M_(i,j) else 0)));
These take the diagonal part and strictly lower part of a matrix.
dec = I -> (
print "old:";
scan(flatten entries gens trim I, print); print "";
cs = decompose I;
scan(#cs, i->(print ("new in #" | toString(i+1) | ":");
scan(select(flatten entries gens cs_i, g->(g%I != 0)), print);
print ""; ))
)
Take the ideal I. Decompose it as a product of prime ideals.
For each one of those, list the new generators contained in that larger ideal,
where "new" is checked by seeing if it reduces to 0 mod I.
I1 = ideal {lp(A*B), lp(B*A)}; -- what are these equations, in words?
dec(I1); -- what does this do?
These equations say that A*B and B*A are both required to be upper triangular
(that their strict lower triangles vanish).
[They always have the same eigenvalues, as is easy to see if A is invertible,
then use continuity. The eigenvalues are now on the diagonal, so there are
syze! ways to match up A*B's diagonal with B*A's diagonal. That's why this
thing decomposes into syze! pieces.]
C = A*B-B*A;
C = C - dp(C);
I2 = ideal C; -- what are these equations, in words?
dec(I2);
C-dp(C) rips out the diagonal. Then we set the rest to 0. So the conditions are
that A and B almost commute -- A*B and B*A differ only on the diagonal.
[This turns out to break into 2 pieces. One is the piece where A and B
do in fact commute. There is exactly one other piece!
Moreover, the equations above are a Gr\"obner degeneration of these,
w.r.t. a certain weighting lambda on the variables.
If you find these equations interesting, you can read more
about this story here and here.]
Wednesday, April 22, 2009
Answers to HW #10
1. A ring is called a division ring if R is a (not necessarily commutative) ring with unit (and 0 not equal to 1) such that for each r in R, there is an r' such that rr' = r'r = 1. The Quaternions is the set H = { a + bi + cj + dk : a,b,c,d are real numbers}. Define a multiplication by setting i^2 = j^2 = k^2 = -1, ij = k, jk = i, and ik = -j. Show that H is a division ring. [Hint: Try proving that the complex numbers is a field using the complex conjugate, and try changing the proof for the Quaternions H].
(a+bi+cj+dk)(a-bi-cj-dk) = a^2 + b^2 + c^2 + d^2.
If not all a,b,c,d are 0, we can divide through to find an inverse for a+bi+cj+dk.
2. Recall that given a nonzero ring R, one always has at least two ideals; the zero ideal, and the whole ring. If these are the only two ideals, R is called simple.
Show that the ring of nxn matrices over a field F is simple.
Let I be a nonzero ideal and M a nonzero element. Let m_ij be a nonzero matrix element. Gotta start somewhere.
Let e_ij denote the matrix with a 1 at (i,j) and 0 elsewhere.
Then for I to be a 2-sided ideal, it must contain e_{ai} M e_{jb}/m_ij, which one can calculate to be e_{ab} by matrix multiplication.
So I contains every e_{ab}, hence their linear combinations, which is all matrices.
For the rest of the problems, R is a commutative ring with unit.
3. Define the nilradical of R, denoted N(R) as the set of all nilpotent elements of R.
(a) Show that N(R) is an ideal.
(b) Given an ideal I of R, compute N(R/I). So, N(R/I) corresponds to an ideal of R containing I. What is this ideal?
Let pi denote the map R -> R/I.
So we want r such that pi(r) in N(R/I),
i.e. pi(r)^p = 0 in R/I for some p,
i.e. (r+I)^p = 0+I for some p,
i.e. r^p + I = 0+I for some p,
i.e. r^p in I for some p,
i.e. r in Rad(I).
4. Let F_p be the field of p elements, Z/pZ. Note that in this field, p = 0. Let R = F_p[x], where x is a variable. Show that the function phi : R --> R that sends an element f of R to f^p is a ring homomorphism. What is its kernel?
[It may help if you know that (f+g)^p = \sum_{i=0}^p (p choose i) f^i * g^(p-i), where (p choose i) is the binomial coefficient p!/(i!(p-i)!).]
(p choose i) = p(p-1)...(p-i+1)/i!. If i is more than 0, then the numerator contains p. If i is less than p, then the denominator doesn't. Hence in these cases, (p choose i) is a multiple of p. Which is 0 in R.
5. Let I be an ideal of R, and consider the R-module R/I. Show that the first syzygy of R/I can be chosen to be I. Note: This amounts to proving that the kernel of the R-module homomorphism R --> R/I is I.
The point is that we can generate R/I using 1+I, so the usual map R -> R/I is a good place to start the resolution.
Then k+I = 0+I iff k+i=0 for some i iff k=-i is in I.
6. Let R = F[x,y,z] where F is any field, and let I be the ideal generated by the monomials x^2,xy,xz,y^2,yz,z^2. Find the first syzygies (there are 8) among these generators (i.e. the relations), and find the second syzygies (there are 3) among these generators (which, by definition, are the relations among the relations).
Incidentally H_{R/I} = 1 + 3t, which is a very easy calculation, and that's
= 1/(1-t)^3 (1 - 6 t^2 + 8 t^3 - 3 t^4).
So it would be nice (though it's not automatic) for the resolution to look as simple as that polynomial. And indeed it does.
Of the (6 choose 2) pairs, one only needs to look at pairs with gcd not 1.
That's where the 8 syzygies come from.
(a+bi+cj+dk)(a-bi-cj-dk) = a^2 + b^2 + c^2 + d^2.
If not all a,b,c,d are 0, we can divide through to find an inverse for a+bi+cj+dk.
2. Recall that given a nonzero ring R, one always has at least two ideals; the zero ideal, and the whole ring. If these are the only two ideals, R is called simple.
Show that the ring of nxn matrices over a field F is simple.
Let I be a nonzero ideal and M a nonzero element. Let m_ij be a nonzero matrix element. Gotta start somewhere.
Let e_ij denote the matrix with a 1 at (i,j) and 0 elsewhere.
Then for I to be a 2-sided ideal, it must contain e_{ai} M e_{jb}/m_ij, which one can calculate to be e_{ab} by matrix multiplication.
So I contains every e_{ab}, hence their linear combinations, which is all matrices.
For the rest of the problems, R is a commutative ring with unit.
3. Define the nilradical of R, denoted N(R) as the set of all nilpotent elements of R.
(a) Show that N(R) is an ideal.
(b) Given an ideal I of R, compute N(R/I). So, N(R/I) corresponds to an ideal of R containing I. What is this ideal?
Let pi denote the map R -> R/I.
So we want r such that pi(r) in N(R/I),
i.e. pi(r)^p = 0 in R/I for some p,
i.e. (r+I)^p = 0+I for some p,
i.e. r^p + I = 0+I for some p,
i.e. r^p in I for some p,
i.e. r in Rad(I).
4. Let F_p be the field of p elements, Z/pZ. Note that in this field, p = 0. Let R = F_p[x], where x is a variable. Show that the function phi : R --> R that sends an element f of R to f^p is a ring homomorphism. What is its kernel?
[It may help if you know that (f+g)^p = \sum_{i=0}^p (p choose i) f^i * g^(p-i), where (p choose i) is the binomial coefficient p!/(i!(p-i)!).]
(p choose i) = p(p-1)...(p-i+1)/i!. If i is more than 0, then the numerator contains p. If i is less than p, then the denominator doesn't. Hence in these cases, (p choose i) is a multiple of p. Which is 0 in R.
5. Let I be an ideal of R, and consider the R-module R/I. Show that the first syzygy of R/I can be chosen to be I. Note: This amounts to proving that the kernel of the R-module homomorphism R --> R/I is I.
The point is that we can generate R/I using 1+I, so the usual map R -> R/I is a good place to start the resolution.
Then k+I = 0+I iff k+i=0 for some i iff k=-i is in I.
6. Let R = F[x,y,z] where F is any field, and let I be the ideal generated by the monomials x^2,xy,xz,y^2,yz,z^2. Find the first syzygies (there are 8) among these generators (i.e. the relations), and find the second syzygies (there are 3) among these generators (which, by definition, are the relations among the relations).
Incidentally H_{R/I} = 1 + 3t, which is a very easy calculation, and that's
= 1/(1-t)^3 (1 - 6 t^2 + 8 t^3 - 3 t^4).
So it would be nice (though it's not automatic) for the resolution to look as simple as that polynomial. And indeed it does.
Of the (6 choose 2) pairs, one only needs to look at pairs with gcd not 1.
That's where the 8 syzygies come from.
Macaulay 2, version 1.2
with packages: Elimination, IntegralClosure, LLLBases, PrimaryDecomposition,
ReesAlgebra, SchurRings, TangentCone
i1 : R = QQ[x,y,z];
i2 : I = (ideal vars R)^2
2 2 2
o2 = ideal (x , x*y, x*z, y , y*z, z )
o2 : Ideal of R
i10 : syz gens I
o10 = {2} | -y 0 -z 0 0 0 0 0 |
{2} | x -z 0 -y 0 -z 0 0 |
{2} | 0 y x 0 0 0 0 -z |
{2} | 0 0 0 x -z 0 0 0 |
{2} | 0 0 0 0 y x -z 0 |
{2} | 0 0 0 0 0 0 y x |
6 8
o10 : Matrix R <--- R
i11 : ker oo
o11 = image {3} | z 0 0 |
{3} | x 0 -z |
{3} | -y 0 0 |
{3} | 0 z 0 |
{3} | 0 x 0 |
{3} | 0 -y z |
{3} | 0 0 x |
{3} | 0 0 -y |
HW #11, due Wed 4/29 (minor corrections to 3b and 5)
1. Let R = F_p[x,y], and I generated by y(y-x^2).
Show there is no Frobenius splitting on R that compatibly splits I.
(Hint: if I were compatibly split, then so would various other ideals be, including one that isn't radical.)
2. Same problem, but I is generated by xy(x+y).
3. Let R be a graded ring, and phi a Frobenius splitting of it.
a) Show that phi is determined by its values on homogeneous elements.
b) For r homogeneous of degree k, define phi'(r) = the degree k/p part of phi(r), or 0 if k/p is not an integer.
For r not homogeneous, define phi'(r) = the sum of phi'(its homogeneous pieces).
Show that phi' is a Frobenius splitting.
c) Give a reasonable definition of a "graded Frobenius splitting".
4. Let R be the subring of F_p[x] generated by x^2 and x^3, i.e. polynomials with no linear term. Show that R has no Frobenius splitting.
5. Let R = C[a,b,c] / {ac} stupid blogger.com.
Let I be generated by {a,b}, as an ideal in R not just C[a,b,c].
a) Compute the Hilbert series H_R and H_{R/I}.
b) Show that H_{R/I} is not H_R times a polynomial.
c) Prove that the Hilbert Syzygy Theorem fails for this R and I; there is no finite graded resolution.
6. Here is a simple program in Macaulay 2, a program to do (mostly) ring theory calculations.
Figure out what it's computing. Here's a comprehensive index of M2 commands. If you want to actually run M2 (so e.g. you can play with the code), here's how to get started.
Show there is no Frobenius splitting on R that compatibly splits I.
(Hint: if I were compatibly split, then so would various other ideals be, including one that isn't radical.)
2. Same problem, but I is generated by xy(x+y).
3. Let R be a graded ring, and phi a Frobenius splitting of it.
a) Show that phi is determined by its values on homogeneous elements.
b) For r homogeneous of degree k, define phi'(r) = the degree k/p part of phi(r), or 0 if k/p is not an integer.
For r not homogeneous, define phi'(r) = the sum of phi'(its homogeneous pieces).
Show that phi' is a Frobenius splitting.
c) Give a reasonable definition of a "graded Frobenius splitting".
4. Let R be the subring of F_p[x] generated by x^2 and x^3, i.e. polynomials with no linear term. Show that R has no Frobenius splitting.
5. Let R = C[a,b,c] / {ac} stupid blogger.com.
Let I be generated by {a,b}, as an ideal in R not just C[a,b,c].
a) Compute the Hilbert series H_R and H_{R/I}.
b) Show that H_{R/I} is not H_R times a polynomial.
c) Prove that the Hilbert Syzygy Theorem fails for this R and I; there is no finite graded resolution.
6. Here is a simple program in Macaulay 2, a program to do (mostly) ring theory calculations.
Figure out what it's computing. Here's a comprehensive index of M2 commands. If you want to actually run M2 (so e.g. you can play with the code), here's how to get started.
Wednesday 4/22
A Frobenius splitting on a ring R containing F_p is a map phi : R->R such that (1) it's additive (2) phi(a^p b) = a phi(b) (3) phi(1) = 1.
Def: a compatibly split ideal I is one such that phi(I) stays in I.
Thm:
0) Frobenius split rings are reduced (they have no nilpotents).
1) If I is compatibly split, then R/I is split.
2) ...and therefore I is radical.
3) If I,J are split then I+J and I intersect J are split.
4) If I is split, then I:J is split.
Def: a compatibly split ideal I is one such that phi(I) stays in I.
Thm:
0) Frobenius split rings are reduced (they have no nilpotents).
1) If I is compatibly split, then R/I is split.
2) ...and therefore I is radical.
3) If I,J are split then I+J and I intersect J are split.
4) If I is split, then I:J is split.
Talk next Monday 4/27
Next Monday David Vogan of MIT will be giving a talk aimed at undergrads that should be quite good.
Monday, April 20, 2009
Monday 4/20
Exact sequences.
Graded modules and their Hilbert series.
Exact sequences of graded modules give an alternating sum formula for Hilbert series.
Let lambda be a weighting on the variables, a natural number for each x_i.
With this, we can generalize the notions of
Then the easy theorem:
homog_lambda(I) + ideal(y) = init_lambda(I) + ideal(y).
Stupid blogger.com is stealing my angle brackets again.
Note that on the LHS the familiar lambda is (1,1,1,1,...,1),
whereas on the RHS the familiar lambda is (N^n, N^{n-1}, ..., N) where N is very large. (That picks out the lex-first term of any fixed polynomial, once N is big enough.)
Graded modules and their Hilbert series.
Exact sequences of graded modules give an alternating sum formula for Hilbert series.
Let lambda be a weighting on the variables, a natural number for each x_i.
With this, we can generalize the notions of
Then the easy theorem:
homog_lambda(I) + ideal(y) = init_lambda(I) + ideal(y).
Stupid blogger.com is stealing my angle brackets again.
Note that on the LHS the familiar lambda is (1,1,1,1,...,1),
whereas on the RHS the familiar lambda is (N^n, N^{n-1}, ..., N) where N is very large. (That picks out the lex-first term of any fixed polynomial, once N is big enough.)
Thursday, April 16, 2009
Answers to HW #9
1. Let Delta_1, Delta_2 be simplicial complexes on {1..n}.
Show that Delta_1 intersect Delta_2, Delta_1 union Delta_2 are both simplicial complexes too.
A simplicial complex is a collection (A) of subsets of {1..n}, (B) closed under shrinkage. (A) is obvious for both union and intersection, so we turn to (B).
Let F be a subset of {1..n}, and G a subset of F.
If F is in the intersection, then F is in Delta_1 and Delta_2, so G is too, hence G is in the intersection.
If F is in the union, then F is in one of Delta_1 or Delta_2, so G is in that one too, hence G is in the union.
2. Show H_{Delta_1 union Delta_2} = H_{Delta_1} + H_{Delta_2} - H_{the intersection}.
We computed H_Delta = \sum_{F in Delta} (t/(1-t))^|F|.
On the left hand side we sum over each F in the union, once.
On the right we sum over each F in the union either 1+0-0, 0+1-0, or 1+1-1 times, depending on whether it is in Delta_1, Delta_2, or both.
3. Take the two simplicial complexes from the last homework. Compute their Hilbert series (meaning, that of the associated Stanley-Reisner ideals) using the formula we have for general monomial ideals. Confirm that it matches the answer we get from the formula specifically for SR ideals.
The first one is I generated by {e, af, bd}. The usual monomial formula is 1/(1-t)^6 (1 -t-t^2-t^2 + t^3+t^3+t^4 - t^5). The fact that the LCMs are all products says that this is a complete intersection, i.e. the numerator factors, so we could also say 1/(1-t)^6 (1-t)(1-t^2)(1-t^2). Then that simplifies to 1/(1-t)^3 (1+t)^2.
Meanwhile, the formula specifically for S-R ideals gives us
1 + 5(t/(1-t)) + 8(t/(1-t))^2 + 4(t/(1-t))^3, for the 1 empty face, 5 vertices, 8 edges, and 4 triangles.
Multiply both sides by (1-t)^3, and the first calculation gives (1+t)^2, whereas the second gives (1-t)^3 + 5t(1-t)^2 + 8t^2(1-t) + 4t^3, and these are indeed the same.
The second ideal is generated by abc, so the general monomial formula is 1/(1-t)^4 (1-t^3) = 1/(1-t)^3 (1+t+t^2). The S-R formula is 1 + 4(t/(1-t)) + 6(t/(1-t))^2 + 3(t/(1-t))^3. Multiplying again by (1-t)^3, we get 1+t+t^2 vs. (1-t)^3 + 4t(1-t)^2 + 6t^2(1-t) + 3t^3, which again match.
4. Let I be a homogeneous ideal. But let's homogenize it again, anyway! Relate H_I and H_{homog(I)}.
Pick a homogeneous Gr\"obner basis. Then homogenizing it does exactly nothing to the basis; it only puts it into a ring with one more variable.
We can compute the Hilbert series from the leading terms of the Gr\"obner basis, as 1/(1-t)^{# variables} * something depending on those terms.
So the only difference between the two calculations is the number of variables.
Hence H_{homog(I)} = 1/(1-t) H_I.
Show that Delta_1 intersect Delta_2, Delta_1 union Delta_2 are both simplicial complexes too.
A simplicial complex is a collection (A) of subsets of {1..n}, (B) closed under shrinkage. (A) is obvious for both union and intersection, so we turn to (B).
Let F be a subset of {1..n}, and G a subset of F.
If F is in the intersection, then F is in Delta_1 and Delta_2, so G is too, hence G is in the intersection.
If F is in the union, then F is in one of Delta_1 or Delta_2, so G is in that one too, hence G is in the union.
2. Show H_{Delta_1 union Delta_2} = H_{Delta_1} + H_{Delta_2} - H_{the intersection}.
We computed H_Delta = \sum_{F in Delta} (t/(1-t))^|F|.
On the left hand side we sum over each F in the union, once.
On the right we sum over each F in the union either 1+0-0, 0+1-0, or 1+1-1 times, depending on whether it is in Delta_1, Delta_2, or both.
3. Take the two simplicial complexes from the last homework. Compute their Hilbert series (meaning, that of the associated Stanley-Reisner ideals) using the formula we have for general monomial ideals. Confirm that it matches the answer we get from the formula specifically for SR ideals.
The first one is I generated by {e, af, bd}. The usual monomial formula is 1/(1-t)^6 (1 -t-t^2-t^2 + t^3+t^3+t^4 - t^5). The fact that the LCMs are all products says that this is a complete intersection, i.e. the numerator factors, so we could also say 1/(1-t)^6 (1-t)(1-t^2)(1-t^2). Then that simplifies to 1/(1-t)^3 (1+t)^2.
Meanwhile, the formula specifically for S-R ideals gives us
1 + 5(t/(1-t)) + 8(t/(1-t))^2 + 4(t/(1-t))^3, for the 1 empty face, 5 vertices, 8 edges, and 4 triangles.
Multiply both sides by (1-t)^3, and the first calculation gives (1+t)^2, whereas the second gives (1-t)^3 + 5t(1-t)^2 + 8t^2(1-t) + 4t^3, and these are indeed the same.
The second ideal is generated by abc, so the general monomial formula is 1/(1-t)^4 (1-t^3) = 1/(1-t)^3 (1+t+t^2). The S-R formula is 1 + 4(t/(1-t)) + 6(t/(1-t))^2 + 3(t/(1-t))^3. Multiplying again by (1-t)^3, we get 1+t+t^2 vs. (1-t)^3 + 4t(1-t)^2 + 6t^2(1-t) + 3t^3, which again match.
4. Let I be a homogeneous ideal. But let's homogenize it again, anyway! Relate H_I and H_{homog(I)}.
Pick a homogeneous Gr\"obner basis. Then homogenizing it does exactly nothing to the basis; it only puts it into a ring with one more variable.
We can compute the Hilbert series from the leading terms of the Gr\"obner basis, as 1/(1-t)^{# variables} * something depending on those terms.
So the only difference between the two calculations is the number of variables.
Hence H_{homog(I)} = 1/(1-t) H_I.
Wednesday, April 15, 2009
HW #10, Due Wed. 4/22
1. A ring is called a division ring if R is a (not necessarily commutative) ring with unit (and 0 not equal to 1) such that for each r in R, there is an r' such that rr' = r'r = 1. The Quaternions is the set H = { a + bi + cj + dk : a,b,c,d are real numbers}. Define a multiplication by setting i^2 = j^2 = k^2 = -1, ij = k, jk = i, and ik = -j. Show that H is a division ring. [Hint: Try proving that the complex numbers is a field using the complex conjugate, and try changing the proof for the Quaternions H].
2. Recall that given a nonzero ring R, one always has at least two ideals; the zero ideal, and the whole ring. If these are the only two ideals, R is called simple.
Show that the ring of nxn matrices over a field F is simple.
For the rest of the problems, R is a commutative ring with unit.
3. Define the nilradical of R, denoted N(R) as the set of all nilpotent elements of R.
(a) Show that N(R) is an ideal.
(b) Given an ideal I of R, compute N(R/I). So, N(R/I) corresponds to an ideal of R containing I. What is this ideal?
4. Let F_p be the field of p elements, Z/pZ. Note that in this field, p = 0. Let R = F_p[x], where x is a variable. Show that the function phi : R --> R that sends an element f of R to f^p is a ring homomorphism. What is its kernel?
[It may help if you know that (f+g)^p = \sum_{i=0}^p (p choose i) f^i * g^(p-i), where (p choose i) is the binomial coefficient p!/(i!(p-i)!).]
5. Let I be an ideal of R, and consider the R-module R/I. Show that the first syzygy of R/I can be chosen to be I. Note: This amounts to proving that the kernel of the R-module homomorphism R --> R/I is I.
6. Let R = F[x,y,z] where F is any field, and let I be the ideal generated by the monomials x^2,xy,xz,y^2,yz,z^2. Find the first syzygies (there are 8) among these generators (i.e. the relations), and find the second syzygies (there are 3) among these generators (which, by definition, are the relations among the relations).
Have fun!
2. Recall that given a nonzero ring R, one always has at least two ideals; the zero ideal, and the whole ring. If these are the only two ideals, R is called simple.
Show that the ring of nxn matrices over a field F is simple.
For the rest of the problems, R is a commutative ring with unit.
3. Define the nilradical of R, denoted N(R) as the set of all nilpotent elements of R.
(a) Show that N(R) is an ideal.
(b) Given an ideal I of R, compute N(R/I). So, N(R/I) corresponds to an ideal of R containing I. What is this ideal?
4. Let F_p be the field of p elements, Z/pZ. Note that in this field, p = 0. Let R = F_p[x], where x is a variable. Show that the function phi : R --> R that sends an element f of R to f^p is a ring homomorphism. What is its kernel?
[It may help if you know that (f+g)^p = \sum_{i=0}^p (p choose i) f^i * g^(p-i), where (p choose i) is the binomial coefficient p!/(i!(p-i)!).]
5. Let I be an ideal of R, and consider the R-module R/I. Show that the first syzygy of R/I can be chosen to be I. Note: This amounts to proving that the kernel of the R-module homomorphism R --> R/I is I.
6. Let R = F[x,y,z] where F is any field, and let I be the ideal generated by the monomials x^2,xy,xz,y^2,yz,z^2. Find the first syzygies (there are 8) among these generators (i.e. the relations), and find the second syzygies (there are 3) among these generators (which, by definition, are the relations among the relations).
Have fun!
Saturday, April 11, 2009
Answers to HW #8
1. Let I be a radical ideal in R, and homog(I) its homogenization in R[y].
Show that homog(I) is radical.
Let f^2 be in homog(I). Let f_0 be the lowest-degree part of f, so f_0^2 is the lowest-degree part of f^2. Since f^2 is in homog(I) a homogeneous ideal, each degree component of it, e.g. f_0^2, is in homog(I).
Then there are two cases: f_0 is in homog(I) or not. If it is, replace f with f-f_0 and start over. That must terminate since the number of terms goes down. Eventually we get to the other case, that f_0 is not in homog(I). Replace f with f_0 and start over.
Okay, now f^2 is in homog(I), but f isn't, and f is homogeneous. Hence homog(dehomog(f)) = f / y^k, where k is the largest power of y that divides f. Let g = f / y^k; it is homogeneous and not a multiple of y. Hence homog(dehomog(g)) = g.
Okay, now (g y^k)^2 is in homog(I). Dehomogenizing, we learn dehomog(g)^2 is in I. Hence dehomog(g) is in I, since I is radical. Hence homog(dehomog(g)) = g is in homog(I). Therefore f = g y^k is in homog(I).
2. Let I be a radical homogeneous ideal in R[y].
Show that dehomog(I) is radical.
Let f^2 be in dehomog(I). Then f^2 = dehomog(g) for some homogeneous g in I. So homog(f^2) = g / y^k for the largest y^k dividing g.
Hence y^k homog(f^2) is in I. If k is odd, multiply by y again, staying in I.
Hence y^{k or k+1} homog(f)^2 is in I.
Since I is radical, y^{ceiling(k/2)} homog(f) is in I.
Dehomogenizing, we learn f is in I.
3. Let I be an ideal in R such that homog(I) is radical. Show that I is radical.
I = dehomog(homog(I)). Now apply #2.
4. Give an example of I in R[y], homogeneous but not radical, such that dehomog(I) is radical.
The simplest is I generated by y^2.
Geometrically, the idea is this. PV(I) lives in projective space. Being nonradical means it has some fuzz on it somewhere (that the generators of the radical would shave off). Dehomogenizing means intersecting PV(I) with affine space, throwing away the stuff at infinity. So we need to arrange for all the fuzz to be at infinity. The ideal y^2 cuts out exactly the hyperplane at infinity, but with fuzz.
5. Let I be generated by xy, x+y-1. Find a term order such that init(homog(I)) is radical.
Conclude that I is radical.
homog(I) is generated by xy, x+y-z (here the new variable is z).
With the right lex order, the initial terms are xy and -z.
Since those have gcd=1, this is a Gr\"obner basis whose initial terms are squarefree.
Hence I is radical.
6. Draw the simplicial complex associated to the ideal generated by {e, af, bd} in C[a,b,c,d,e,f].
It's a solid square cut into four triangles with a,b,f,d at the corners and c in the middle.
7. Draw the solid abc triangle, and put a vertex d in the middle, with new edges connected to a,b,c. (The red, but not blue, lines in this picture.) What's the corresponding Stanley-Reisner ideal, and its Hilbert series?
This wasn't at all well specified, for which I apologize. If you didn't manage to read my mind, but made clear what complex you were working with, that's good enough.
What I'd intended to indicate was a union of three solid triangles, abd & bcd & cad. So the only faces missing are abcd and abc itself. In particular the S-R ideal should be generated by abc.
Then the Hilbert series is 1/(1-t)^4 * (1-t^3).
Show that homog(I) is radical.
Let f^2 be in homog(I). Let f_0 be the lowest-degree part of f, so f_0^2 is the lowest-degree part of f^2. Since f^2 is in homog(I) a homogeneous ideal, each degree component of it, e.g. f_0^2, is in homog(I).
Then there are two cases: f_0 is in homog(I) or not. If it is, replace f with f-f_0 and start over. That must terminate since the number of terms goes down. Eventually we get to the other case, that f_0 is not in homog(I). Replace f with f_0 and start over.
Okay, now f^2 is in homog(I), but f isn't, and f is homogeneous. Hence homog(dehomog(f)) = f / y^k, where k is the largest power of y that divides f. Let g = f / y^k; it is homogeneous and not a multiple of y. Hence homog(dehomog(g)) = g.
Okay, now (g y^k)^2 is in homog(I). Dehomogenizing, we learn dehomog(g)^2 is in I. Hence dehomog(g) is in I, since I is radical. Hence homog(dehomog(g)) = g is in homog(I). Therefore f = g y^k is in homog(I).
2. Let I be a radical homogeneous ideal in R[y].
Show that dehomog(I) is radical.
Let f^2 be in dehomog(I). Then f^2 = dehomog(g) for some homogeneous g in I. So homog(f^2) = g / y^k for the largest y^k dividing g.
Hence y^k homog(f^2) is in I. If k is odd, multiply by y again, staying in I.
Hence y^{k or k+1} homog(f)^2 is in I.
Since I is radical, y^{ceiling(k/2)} homog(f) is in I.
Dehomogenizing, we learn f is in I.
3. Let I be an ideal in R such that homog(I) is radical. Show that I is radical.
I = dehomog(homog(I)). Now apply #2.
4. Give an example of I in R[y], homogeneous but not radical, such that dehomog(I) is radical.
The simplest is I generated by y^2.
Geometrically, the idea is this. PV(I) lives in projective space. Being nonradical means it has some fuzz on it somewhere (that the generators of the radical would shave off). Dehomogenizing means intersecting PV(I) with affine space, throwing away the stuff at infinity. So we need to arrange for all the fuzz to be at infinity. The ideal y^2 cuts out exactly the hyperplane at infinity, but with fuzz.
5. Let I be generated by xy, x+y-1. Find a term order such that init(homog(I)) is radical.
Conclude that I is radical.
homog(I) is generated by xy, x+y-z (here the new variable is z).
With the right lex order, the initial terms are xy and -z.
Since those have gcd=1, this is a Gr\"obner basis whose initial terms are squarefree.
Hence I is radical.
6. Draw the simplicial complex associated to the ideal generated by {e, af, bd} in C[a,b,c,d,e,f].
It's a solid square cut into four triangles with a,b,f,d at the corners and c in the middle.
7. Draw the solid abc triangle, and put a vertex d in the middle, with new edges connected to a,b,c. (The red, but not blue, lines in this picture.) What's the corresponding Stanley-Reisner ideal, and its Hilbert series?
This wasn't at all well specified, for which I apologize. If you didn't manage to read my mind, but made clear what complex you were working with, that's good enough.
What I'd intended to indicate was a union of three solid triangles, abd & bcd & cad. So the only faces missing are abcd and abc itself. In particular the S-R ideal should be generated by abc.
Then the Hilbert series is 1/(1-t)^4 * (1-t^3).
Wednesday, April 08, 2009
HW #9, due Wednesday 4/15
1. Let Delta_1, Delta_2 be simplicial complexes on {1..n}.
Show that Delta_1 intersect Delta_2, Delta_1 union Delta_2 are both simplicial complexes too.
2. Show H_{Delta_1 union Delta_2} = H_{Delta_1} + H_{Delta_2} - H_{the intersection}.
3. Take the two simplicial complexes from the last homework. Compute their Hilbert series (meaning, that of the associated Stanley-Reisner ideals) using the formula we have for general monomial ideals. Confirm that it matches the answer we get from the formula specifically for SR ideals.
4. Let I be a homogeneous ideal. But let's homogenize it again, anyway! Relate H_I and H_{homog(I)}.
...more to come
Show that Delta_1 intersect Delta_2, Delta_1 union Delta_2 are both simplicial complexes too.
2. Show H_{Delta_1 union Delta_2} = H_{Delta_1} + H_{Delta_2} - H_{the intersection}.
3. Take the two simplicial complexes from the last homework. Compute their Hilbert series (meaning, that of the associated Stanley-Reisner ideals) using the formula we have for general monomial ideals. Confirm that it matches the answer we get from the formula specifically for SR ideals.
4. Let I be a homogeneous ideal. But let's homogenize it again, anyway! Relate H_I and H_{homog(I)}.
...more to come
Tuesday, April 07, 2009
Hints
If p is a homogeneous polynomial in C[x_1,...,x_n,y], then homog(dehomog(p)) = p / y^k, where k is taken largest possible. (Namely, it's taken to be the smallest power occurring among the terms of p.)
If J is a homogeneous ideal in C[x_1,..,x_n,y], then the map dehomog: J -> dehomog(J) is onto.
If I is an ideal in C[x_1,..,x_n], then the map homog: I -> homog(I) is not onto; its image is the homogeneous polynomials in homog(I) that are not multiples of y.
Feel free to use these without proving them (though they're easy).
If J is a homogeneous ideal in C[x_1,..,x_n,y], then the map dehomog: J -> dehomog(J) is onto.
If I is an ideal in C[x_1,..,x_n], then the map homog: I -> homog(I) is not onto; its image is the homogeneous polynomials in homog(I) that are not multiples of y.
Feel free to use these without proving them (though they're easy).
Monday, April 06, 2009
Monday 4/6
The Hilbert series of SR(Delta) is sum_{faces F} (t/(1-t))^|F|.
Hence the Hilbert polynomial, in degree d, is sum_F (d-1 choose |F|-1).
Hence the Hilbert dimension is the # of elements of the largest face.
Something I really should have proved:
Thm.
If g_1,..,g_m is a Gr\"obner basis of I using a graded term order,
then homog(g_1),...,homog(g_m) is a Gr\"obner basis of homog(I)
using a graded term order in which y is cheap.
Pf. homog(g_i) has the same leading term as g_i (since it's of highest degree in g_i, so doesn't get any powers of y on it).
If we follow the reduction of S(homog(g_i), homog(g_j)),
at each step its dehomogenization matches that of the reduction S(g_i,g_j),
so we don't get stuck and we do reduce it to 0.
Corollary. If yf is in homog(I), then f is in homog(I).
Proof. If f isn't in homog(I), then after reducing for a while using one of the Gr\"obner bases supplied above it gets stuck.
Hence yf is also stuck, because the leading terms in {homog(g_i)} don't involve y. So yf isn't in homog(I).
Thm. If I is prime, then homog(I) is also prime.
Pf. Start with a,b s.t. ab in homog(I). Reduce to the case that a = homog(a_2), b = homog(b_2), using the Corollary. Then use a = homog(dehomog(a)) etc.
Hence the Hilbert polynomial, in degree d, is sum_F (d-1 choose |F|-1).
Hence the Hilbert dimension is the # of elements of the largest face.
Something I really should have proved:
Thm.
If g_1,..,g_m is a Gr\"obner basis of I using a graded term order,
then homog(g_1),...,homog(g_m) is a Gr\"obner basis of homog(I)
using a graded term order in which y is cheap.
Pf. homog(g_i) has the same leading term as g_i (since it's of highest degree in g_i, so doesn't get any powers of y on it).
If we follow the reduction of S(homog(g_i), homog(g_j)),
at each step its dehomogenization matches that of the reduction S(g_i,g_j),
so we don't get stuck and we do reduce it to 0.
Corollary. If yf is in homog(I), then f is in homog(I).
Proof. If f isn't in homog(I), then after reducing for a while using one of the Gr\"obner bases supplied above it gets stuck.
Hence yf is also stuck, because the leading terms in {homog(g_i)} don't involve y. So yf isn't in homog(I).
Thm. If I is prime, then homog(I) is also prime.
Pf. Start with a,b s.t. ab in homog(I). Reduce to the case that a = homog(a_2), b = homog(b_2), using the Corollary. Then use a = homog(dehomog(a)) etc.
Wednesday, April 01, 2009
HW #8, due Wednesday 4/8
You may use the following result (very similar to one proved in class):
Let J be a homogeneous ideal. If for every homogeneous f one
has f^2 in J => f in J, then J is radical.
1. Let I be a radical ideal in R, and homog(I) its homogenization in R[y].
Show that homog(I) is radical.
2. Let I be a radical homogeneous ideal in R[y].
Show that dehomog(I) is radical.
3. Let I be an ideal in R such that homog(I) is radical. Show that I is radical.
4. Give an example of I in R[y], homogeneous but not radical, such that dehomog(I) is radical.
5. Let I be generated by xy, x+y-1. Find a term order such that init(homog(I)) is radical.
Conclude that I is radical.
6. Draw the simplicial complex associated to the ideal generated by {e, af, bd} in C[a,b,c,d,e,f].
(Grr. Blogger is eating my less-than and more-than symbols with which to generate ideals.)
7. Draw the solid abc triangle, and put a vertex d in the middle, with new edges connected to a,b,c. (The red, but not blue, lines in this picture.) What's the corresponding Stanley-Reisner ideal, and its Hilbert series?
Let J be a homogeneous ideal. If for every homogeneous f one
has f^2 in J => f in J, then J is radical.
1. Let I be a radical ideal in R, and homog(I) its homogenization in R[y].
Show that homog(I) is radical.
2. Let I be a radical homogeneous ideal in R[y].
Show that dehomog(I) is radical.
3. Let I be an ideal in R such that homog(I) is radical. Show that I is radical.
4. Give an example of I in R[y], homogeneous but not radical, such that dehomog(I) is radical.
5. Let I be generated by xy, x+y-1. Find a term order such that init(homog(I)) is radical.
Conclude that I is radical.
6. Draw the simplicial complex associated to the ideal generated by {e, af, bd} in C[a,b,c,d,e,f].
(Grr. Blogger is eating my less-than and more-than symbols with which to generate ideals.)
7. Draw the solid abc triangle, and put a vertex d in the middle, with new edges connected to a,b,c. (The red, but not blue, lines in this picture.) What's the corresponding Stanley-Reisner ideal, and its Hilbert series?
Monday 3/30
The homogenization and dehomogenization of polynomials and ideals.
Geometrically, homogenization corresponds to taking the closure in projective space, whereas dehomogenization corresponds to intersecting a projective set with affine space.
We did x^2 = y^2 + 1 as an example, then dehomogenized using x,
which turned a hyperbola into a circle.
Geometrically, homogenization corresponds to taking the closure in projective space, whereas dehomogenization corresponds to intersecting a projective set with affine space.
We did x^2 = y^2 + 1 as an example, then dehomogenized using x,
which turned a hyperbola into a circle.
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.
Thursday, February 26, 2009
HW #6, due Wednesday 3/4
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.
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.
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.
Wednesday, January 28, 2009
HW #2, due Wednesday 2/4 (sixth problem added)
1. Let I = < x^a y^b, x^c y^d >. What is the Hilbert series H_{R/I}? Don't just repeat the formula from class -- simplify your answer as much as possible, depending on circumstances.
2. Let I = < x^a y^b z^c, x^d y^e z^f, x^g y^h z^i >.
Assume H_{R/I} = 1/(1-t)^3 * (1 - t^{a+d+g}) (1 - t^{b+e+h}) (1 - t^{c+f+i}).
What does this tell you about a..i?
3. Let M be a 2x2 matrix with entries a,b,c,d, and let I be the ideal generated by the entries of M^2.
a) Show (Trace M)^3 is in I.
b) Show Trace M is not in I.
Hint: when taking an R-linear combination of the generators of I, break the {r_i} coefficients up into their homogeneous components, and work one degree at a time.
4. Let X be a line union a point, specifically {x=0} union {x=1,y=0}.
a) Show the ideal I_X contains < xy, x^2 - x >.
b) Show the opposite containment.
5. Let I,J be monomial ideals. Explain how to program up an algorithm that tests whether I contains J.
6. Given a subspace A of a vector space B, define the map i_A : A -> B that just takes any vector to itself, and the map p_A : B -> B/A that takes any b to its coset b+A.
The map i_A is one-to-one, meaning that no two vectors map the same place.
The map p_A is onto, meaning that every element of the target is p_A(something).
A map that is one-to-one and onto is called a correspondence (or depending on context, a bijection, or an isomorphism, or...).
The point of this problem is to see that "subspace is to one-to-one as quotient space is to onto".
Let T : V -> W be a linear map from one vector space to another.
Find a subspace W' of W, and a map C : V -> W', such that C is onto and T = i_W' o C.
Find a subspace V' of V, and a map D : V/V' -> W, such that D is one-to-one and T = D o p_V'.
You should be able to write down W',C,V',D explicitly in terms of T,V,W.
2. Let I = < x^a y^b z^c, x^d y^e z^f, x^g y^h z^i >.
Assume H_{R/I} = 1/(1-t)^3 * (1 - t^{a+d+g}) (1 - t^{b+e+h}) (1 - t^{c+f+i}).
What does this tell you about a..i?
3. Let M be a 2x2 matrix with entries a,b,c,d, and let I be the ideal generated by the entries of M^2.
a) Show (Trace M)^3 is in I.
b) Show Trace M is not in I.
Hint: when taking an R-linear combination of the generators of I, break the {r_i} coefficients up into their homogeneous components, and work one degree at a time.
4. Let X be a line union a point, specifically {x=0} union {x=1,y=0}.
a) Show the ideal I_X contains < xy, x^2 - x >.
b) Show the opposite containment.
5. Let I,J be monomial ideals. Explain how to program up an algorithm that tests whether I contains J.
6. Given a subspace A of a vector space B, define the map i_A : A -> B that just takes any vector to itself, and the map p_A : B -> B/A that takes any b to its coset b+A.
The map i_A is one-to-one, meaning that no two vectors map the same place.
The map p_A is onto, meaning that every element of the target is p_A(something).
A map that is one-to-one and onto is called a correspondence (or depending on context, a bijection, or an isomorphism, or...).
The point of this problem is to see that "subspace is to one-to-one as quotient space is to onto".
Let T : V -> W be a linear map from one vector space to another.
Find a subspace W' of W, and a map C : V -> W', such that C is onto and T = i_W' o C.
Find a subspace V' of V, and a map D : V/V' -> W, such that D is one-to-one and T = D o p_V'.
You should be able to write down W',C,V',D explicitly in terms of T,V,W.
Wednesday 1/28
The Hilbert series for a general monomial ideal, by inclusion-exclusion.
The ideal membership problem, for monomial ideals.
The notation a == b mod I, and the generators of I as substitution rules in such congruences.
Term orders on monomials, which we will require to be well-orderings.
Examples: the lexicographic order, and the graded lexicographic order.
Given a term order, any polynomial p has a most expensive term, init p.
The reduction algorithm for testing ideal membership:
if p has a monomial m that's a multiple of some g_i,
replace p by p - (m/init g_i) g_i.
(It's enough to look only at p's most expensive monomial, init p.)
By the well-ordering condition, this terminates.
If the result is zero, then yes, the original p was in the ideal.
Scary example: I = < x-y, x-z >, with x the most expensive term. Then y-z is in the ideal, but this algorithm can't show it.
The ideal membership problem, for monomial ideals.
The notation a == b mod I, and the generators of I as substitution rules in such congruences.
Term orders on monomials, which we will require to be well-orderings.
Examples: the lexicographic order, and the graded lexicographic order.
Given a term order, any polynomial p has a most expensive term, init p.
The reduction algorithm for testing ideal membership:
if p has a monomial m that's a multiple of some g_i,
replace p by p - (m/init g_i) g_i.
(It's enough to look only at p's most expensive monomial, init p.)
By the well-ordering condition, this terminates.
If the result is zero, then yes, the original p was in the ideal.
Scary example: I = < x-y, x-z >, with x the most expensive term. Then y-z is in the ideal, but this algorithm can't show it.
Monday 1/26
The Hilbert series of R/I for I a polynomial ideal, as the generating function of the Hilbert function.
The elements of R/I_X, while no longer well-defined as polynomials, are still well-defined as functions on X.
Given S a subspace of R, when is there a well-defined multiplication on R/S? Answer: S an ideal.
(Actually, we only showed that if S is an ideal, then the multiplication on R/S is well-defined. But necessity is easy: the zero element of R/S is the coset 0 + S = S itself, and we want C*0 = 0 for any element C in R/S. Upstairs in R, that says r*s in S for any r in any C, any s in S.)
The elements of R/I_X, while no longer well-defined as polynomials, are still well-defined as functions on X.
Given S a subspace of R, when is there a well-defined multiplication on R/S? Answer: S an ideal.
(Actually, we only showed that if S is an ideal, then the multiplication on R/S is well-defined. But necessity is easy: the zero element of R/S is the coset 0 + S = S itself, and we want C*0 = 0 for any element C in R/S. Upstairs in R, that says r*s in S for any r in any C, any s in S.)
Wednesday, January 21, 2009
HW #1, due Wednesday 1/28
1. A monomial ideal is one generated by monomials.
Let R = C[x,y].
Find all monomial ideals I such that there are exactly 4 monomials not in I.
Let R = C[x,y].
Find all monomial ideals I such that there are exactly 4 monomials not in I.
(Note that you never need to have two generators where one divides the other.)
2. Let I,J be ideals in a ring R. Show that I intersect J is an ideal
(by checking each of conditions 1-3).
3. Let R = C[x,y], I = < x^2 y^20, x^15 y^4 >, J = < x^8 y^9 >.
Find generators for I intersect J.
4. Let Y = {0,1}, two elements of C. Find the ideal I_Y in C[x].
5. Compute the Hilbert function of C[x,y] / < x^a y^b >, for arbitrary a,b.
6. Let I be a monomial ideal in C[x,y]. Say that h_I(N)=0, for some large N. What can you say about the generators of I? (Assuming no redundant generators are used, meaning multiples of other generators.)
Wednesday 1/21
Partitions of sets, as indicating partial knowledge.
Cosets of a vector subspace.
Quotient vector spaces. Computing their dimension, in the finite-dim case.
The nth graded piece of a polynomial ring.
The Hilbert function of a monomial ideal (or really, of R/I).
Computing it by counting the leftover monomials.
Cosets of a vector subspace.
Quotient vector spaces. Computing their dimension, in the finite-dim case.
The nth graded piece of a polynomial ring.
The Hilbert function of a monomial ideal (or really, of R/I).
Computing it by counting the leftover monomials.
Monday 1/19
We defined polynomial rings (with complex coefficients), and ideals therein.
Monomial ideals.
Two natural ways to produce ideals:
1) Any subset X of C^n has an I_X of those polynomials that vanish at every point of X.
Example: if X is the y-axis in C^2, then I_X in C[x,y] is all multiples of x.
2) Given any set in a polynomial ring R, we can generate an ideal from it by taking all R-linear combinations.
Big theorem to come: any ideal has a finite generating set.
(Warning: in the links above, the ring R may not be a polynomial ring, and may not even be commutative. That leads to a bunch of extra worries, like "left ideals" vs. "right ideals", that are not our problem.)
Monomial ideals.
Two natural ways to produce ideals:
1) Any subset X of C^n has an I_X of those polynomials that vanish at every point of X.
Example: if X is the y-axis in C^2, then I_X in C[x,y] is all multiples of x.
2) Given any set in a polynomial ring R, we can generate an ideal from it by taking all R-linear combinations.
Big theorem to come: any ideal has a finite generating set.
(Warning: in the links above, the ring R may not be a polynomial ring, and may not even be commutative. That leads to a bunch of extra worries, like "left ideals" vs. "right ideals", that are not our problem.)
Welcome to Math 4370, Spring 2009
This is where I'll be putting class notes, homework, other announcements.
Rather than rechecking it constantly, you can subscribe to its RSS feed. (That's the point of having it as a blog.)
Rather than rechecking it constantly, you can subscribe to its RSS feed. (That's the point of having it as a blog.)
Subscribe to:
Posts (Atom)