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.
Wednesday, February 11, 2009
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.)
Friday, June 13, 2008
Final exam with answers
Here.
Here's how grades work: add up your homework percentage, midterms, twice the final, and divide by 5.
Then find the range:
-----A
70
-----B
55
-----C
40
-----D
25
-----F
with + and - in those ranges too.
Here's how grades work: add up your homework percentage, midterms, twice the final, and divide by 5.
Then find the range:
-----A
70
-----B
55
-----C
40
-----D
25
-----F
with + and - in those ranges too.
Thursday, June 12, 2008
Monday, June 09, 2008
Neeraj's office hours
"I plan on having OH on Wed 2:30-3:30 so that they can come by to pick up exams and such. (2:30 is when one finals time-slot ends, so even if students have exams that day, they can drop by between 2:30-3.)"
Office hours
I'll be in my office (7450 APM) Tuesday 11-4 and Wednesday 11-2. I'll be giving preference to my Math 109 students on Tuesday and my Ma 20b students on Wednesday, but anyone will be welcome any time.
If you want to call ahead to check "Are you already tied up with the other class?", feel free; my office number is 858-534-6450.
(Don't get 7450 and 6450 confused!)
If you want to call ahead to check "Are you already tied up with the other class?", feel free; my office number is 858-534-6450.
(Don't get 7450 and 6450 confused!)
Some practice questions (now with answers)
Of course you should look again at the practice questions for the midterms. Here are some new ones. "^" means superscript, so x^2 means x squared, etc.
1. Write out the first ten terms (up to x^9) in the Taylor series of
a) f(x) = 1 / (1-x^2)
A. We did this for 1/(1-x) and got 1 + x + x^2 + x^3 + ...
So plug in x^2, and you get
1/(1-x^2) = 1 + x^2 + x^4 + x^6 + x^8 + ... omitting terms higher than x^9.
b) (1-x^4) f(x).
A. You could take the answer above and multiply by 1-x^4. There'd be a lot of cancelation.
Or you could notice that 1 - x^4 = (1+x^2)(1-x^2), so the answer to (b) is 1 + x^2 on the nose.
2. For which values of b does
\integral_{x=0}^{infinity} (e^{bx} + e^{-bx}) dx
converge?
A. None.
If b>0, then the first term goes to infinity, and the second to zero, so the integrand doesn't go to zero (it goes to infinity).
If b<0, then the second term goes to infinity, and the first to zero, so the integrand doesn't go to zero (it goes to infinity).
If b=0, then both terms are 1, so the integrand doesn't go to zero (it's always 2).
3. You've invented the Next Big Thing. It will sell increasingly well,
until the Next Next Big Thing comes out, at which point sales will collapse.
But that won't happen until N months from now.
A representative of MicrohooTM offers you $1000 up front, plus
a pay rate of $100/month at time t. Alternately, she can offer
you a pay rate of $t/month (paid continuously), with nothing up front.
Which deal should you take? You answer should depend on N.
A. This was a lousy question (which is why I kicked it out of the final, where no question is as badly worded as this one).
What it was supposed to get across was the idea that if you take deal #1, then by time S (S < N) you've accumulated 1000 + 100*S dollars.
Whereas if you take deal #2, by time S (S < N) you've accumulated integral_{t=0}^S t dt dollars.
For S small, 1000 + 100*S > S^2/2. Whereas for S large, deal #2 is better. You can figure out when deal #2 starts to beat deal #1 by solving this quadratic equation for S. If N is less than that number, take deal #1; if N is more, take deal #2.
1. Write out the first ten terms (up to x^9) in the Taylor series of
a) f(x) = 1 / (1-x^2)
A. We did this for 1/(1-x) and got 1 + x + x^2 + x^3 + ...
So plug in x^2, and you get
1/(1-x^2) = 1 + x^2 + x^4 + x^6 + x^8 + ... omitting terms higher than x^9.
b) (1-x^4) f(x).
A. You could take the answer above and multiply by 1-x^4. There'd be a lot of cancelation.
Or you could notice that 1 - x^4 = (1+x^2)(1-x^2), so the answer to (b) is 1 + x^2 on the nose.
2. For which values of b does
\integral_{x=0}^{infinity} (e^{bx} + e^{-bx}) dx
converge?
A. None.
If b>0, then the first term goes to infinity, and the second to zero, so the integrand doesn't go to zero (it goes to infinity).
If b<0, then the second term goes to infinity, and the first to zero, so the integrand doesn't go to zero (it goes to infinity).
If b=0, then both terms are 1, so the integrand doesn't go to zero (it's always 2).
3. You've invented the Next Big Thing. It will sell increasingly well,
until the Next Next Big Thing comes out, at which point sales will collapse.
But that won't happen until N months from now.
A representative of MicrohooTM offers you $1000 up front, plus
a pay rate of $100/month at time t. Alternately, she can offer
you a pay rate of $t/month (paid continuously), with nothing up front.
Which deal should you take? You answer should depend on N.
A. This was a lousy question (which is why I kicked it out of the final, where no question is as badly worded as this one).
What it was supposed to get across was the idea that if you take deal #1, then by time S (S < N) you've accumulated 1000 + 100*S dollars.
Whereas if you take deal #2, by time S (S < N) you've accumulated integral_{t=0}^S t dt dollars.
For S small, 1000 + 100*S > S^2/2. Whereas for S large, deal #2 is better. You can figure out when deal #2 starts to beat deal #1 by solving this quadratic equation for S. If N is less than that number, take deal #1; if N is more, take deal #2.
Saturday, June 07, 2008
Sections to study for the final
5.2,3,4,5,6
6.1,2,3
7.2,6,7
9.1,2,3,5
10.1,2,3,5,7
The final will cover all of those (or, as much as can practicably be tested in 3 hours), pretty evenly. It will NOT be just stuff since the second midterm!
Same basic rules for the final -- closed book, bring one double-sided sheet of notes, no calculator, no blue book necessary -- with the extra proviso that you bring your UCSD ID. Do remember to turn off your phone... or else.
6.1,2,3
7.2,6,7
9.1,2,3,5
10.1,2,3,5,7
The final will cover all of those (or, as much as can practicably be tested in 3 hours), pretty evenly. It will NOT be just stuff since the second midterm!
Same basic rules for the final -- closed book, bring one double-sided sheet of notes, no calculator, no blue book necessary -- with the extra proviso that you bring your UCSD ID. Do remember to turn off your phone... or else.
Monday, June 02, 2008
Subscribe to:
Posts (Atom)