Feb 26

A C-algebra is a ring that's also a complex vector space, and a C-algebra homomorphism is a ring homomorphism that's C-linear.

If R is a C-algebra, then C-Spec(R) := {the C-algebra homs R->C}.

If R->S is a C-algebra homomorphism, there's a natural map C-Spec(S) -> C-Spec(R).

If R is a polynomial ring, C-Spec(R) is the corresponding vector space. If R is a polynomial ring modulo an ideal I, C-Spec(R) is V(I).

The inclusion of a polynomial subring corresponds, under taking C-Spec, to linear projection.

Intersecting an ideal I with a polynomial subring, called elimination, corresponds to taking the projection of V(I) and then taking the closure.

Theorem. If I,J are ideals in C[x_1..x_n], so tI, (1-t)J are in C[t,x_1..x_n], then
I intersect J = ((tI) + (1-t)J) intersect C[x_1..x_n].

HW #5

Book problems, p30: 2.4, 2.8, 2.10, 2.11 (assume Buchberger's algorithm, section 2.5), 2.12, 2.14.

Feb 21

Proof of the Buchberger criterion for a Gr\"obner basis.

Feb 19

A standard monomial for an ideal I and term order < is a monomial not in init(I).

Theorem: the images in C[x_1..x_n]/I of the standard monomials are a basis of that space.

Definition of graded ideal and Hilbert function h_I(d).
Many examples of Hilbert functions.
h_I(d) = the number of standard monomials of degree d.

Basic case: I=0. Then the Hilbert function is (d+n-1 choose n-1), by a stars and bars argument.

Answers to HW #3

"1. Let phi: R->S be a ring homomorphism, and I an ideal of S. Let J = phi^{-1}(I) := {r in R : phi(r) in I}. Show J is an ideal of R."

The slow way: if j is in J and r is in R, then phi(rj) = phi(r) phi(j) = phi(r) * something in I, and I is an ideal, so phi(r) phi(j) is in I, hence phi(rj) is, hence rj is in J.

The quick way: J is the kernel of the composite ring homomorphism R -> S -> S/I.

"2. Let R = C[x_1..x_n]. For each i in 1..n, and t a nonzero complex number, define the ring homomorphism phi_{i,t} : R -> R by phi_{i,t}(x_j) = x_j for j not equal to i, and phi_{i,t}(x_i) = tx_i. Also phi_{i,t}(c) = c for c in C. (From here, you should be able to figure out what phi_{i,t} does to an arbitrary element of R.)

Let I be a monomial ideal. Show that phi_{i,t}^{-1}(I) = I for every i,t."

Let m_1,..,m_k be a bunch of monomials that together generate I.
Let m'_j = phi_{i,t}^{-1}(m_j), hence m'_j = t^{-e} m_j, where e is the exponent on x_i in m_j.
phi_{i,t}^{-1}(I) is generated by m'_1..m'_j, but the numbers t^{-e} are invertible so don't change the ideal generated. Hence it's again I.

"3. Harder: assume that phi_{i,t}^{-1}(I) = I for every i,t. Show I is a monomial ideal.
Hint: if g is a generator of I, then phi_{i,t}(g) in I for every i,t. Use this to show that g's monomials are also in I."

Let g be in I, and break g = sum_e x_i^e g_i, where g_i doesn't use the variable x_i.
By the assumption, sum_e (tx_i)^e g_e is in I also, for all nonzero t.
Let E be the lowest power of x_i occurring in g; then sum_e t^{e-E} x_i^e g_e is in I for all nonzero t.
Take the limit as t goes to zero, and we get just x_i^E g_E.
Since that's in the ideal, we can subtract it off of g, and start the process over with the new E.

(You might think it's weird to take limits, since this is an algebra problem. But if you think about dealing with ideals in (Z/<2>)[x_1..x_n] instead of C[x_1..x_n], you notice that the only nonzero t is t=1, and now every ideal I satisfies the stated condition!)

"4. Fix i, and call an ideal I of R[x_1..x_n]  x_i-homogeneous if phi_{i,t}^{-1}(I) = I for every t. Show that if I is x_i-homogeneous, then radical(I) is also x_i-homogeneous."

Let p be in radical(I), so p^m is in I for some m.
Let the lowest x_i-term of p be x_i^E p_E (as in question #3).
Then the lowest x_i-term of p^m is x_i^{mE} p_E^m.
Since I is x_i-homogeneous, we learn that x_i^{mE} p_E^m is in I.
Hence its mth root x_i^E p_E is in radical(I).
Subtract that off p and continue (as in question #3).

"5. Let I be a monomial ideal. Show that radical(I) is also a monomial ideal."

Put #3 and #4 together.

"6. Describe an algorithm that, given a system of generators of a monomial ideal, computes the radical (by giving a system of generators)."

Obviously we want the generators to be monomials; separate them into monomials if they're not.
Then for each monomial, if there's an exponent >1 replace it with 1, so now we have a list of squarefree monomials. That's the system of generators of rad(I).

"7. Prove your algorithm works."

First we need to be sure that the squarefree monomials produced this way are indeed in rad(I).
If m = \prod_{i=1}^n x_i^{e_i}, with E = max({e_i}), then multiply it by \prod_{i: e_i not 0} x_i^{E-e_i} to get a new monomial m' in I that uses the same variables, but now all with exponent E.
Its Eth root \prod_{i: e_i not 0} x^i is then the squarefree monomial in rad(I) described in #6.

Now we need to be sure that these generate rad(I).
By #5, we know that rad(I) is a monomial ideal. So we only want to know which monomials are in rad(I). By the argument in the last paragraph, any square-ful monomial in rad(I) is generated by a squarefree monomial also in rad(I), so we only need to know which squarefree monomials are in rad(I).  If g is a squarefree monomial, it's in rad(I)
iff some power of it is in I
iff that power is a multiple of some single generator m (we did this last week)
iff the variables used in g are a superset of the variables used in m
iff the variables used in g are a superset of the variables used in the m' constructed above.
So those m' generate the squarefree monomials in rad(I), which generate rad(I).

HW #4

1. Let r be a positive irrational number. Write x^a y^b < x^c y^d if a+rb < c+rd.
Show that this defines a monomial order.

2. Consider the vector space of 2x4 matrices M, with entries (m_ij), and let X = {M : M's rows are linearly dependent}.
For i < j, both from 1 to 4, let p_ij be the 2x2 determinant using columns i,j of M.
What's the relation of p_ij to X?

3. (continuing 2) Lex-order the variables m_11, m_12, m_13, m_14, m_21, m_22, m_23, m_24.
What are the leading terms of the six guys p_ij?

4. (continuing) Show that the p_ij are a Gr\"obner basis, by computing S-pairs.

Answers to HW #2

"1. Let R = C[x_1..x_n], and R_d := the homogeneous polynomials of degree d.
For n=2, compute dim(R_d)."

R_d is spanned by the monomials x_1^a x_2^{d-a}, of which there are d+1.

"2. An ideal I in a polynomial ring is called graded if I is the sum over d of (I intersect R_d), i.e., if for every p in I, when we break p into its homogeneous components p_d each of those is also in I. Give an example of an ideal in C[z] that is not graded, and prove that it isn't."

Let I = < x+1 >. Since 1 is not a multiple of 1+x, this is not a graded ideal.

"3. If I,J are graded ideals, show I+J and (I intersect J) are graded too."

Anything in I+J is of the form i+j. When we break i,j into their homogeneous components, we get things in I and J, hence in I+J.

If p is in I intersect J, then p is in I and in J, so each p_d is in I and in J, so each p_d is in I intersect J.

"4. Let M_n(C) denote the noncommutative (!) ring of nxn complex matrices, where multiplication is matrix multiplication.
Fix T an element of M_n(C).
Define f : C[z] -> M_n(C), taking p(z) |-> p(T).
Let I = ker(f). This is principal (being an ideal of C[z]), i.e. I = < m(z) > for some m(z). What is this polynomial called in a linear algebra class?
Compute it for T = identity matrix."

This polynomial is called the minimal polynomial (and divides the characteristic polynomial, by the Cayley-Hamilton theorem). For the identity matrix it's .

"5. Let p(z),q(z) be polynomials, and I = < p(z),q(z) >. Since I is principal, it's generated by some element r(z) = a(z)p(z) + b(z)q(z). What is this r(z) called? (some name involving p,q)"

The greatest common divisor of p & q. Pretty cool that it's also a linear combination of them.

[Do you see how to use the division algorithm to compute the a(z),b(z)?]

Let's do induction on deg(p)+deg(q). If deg(p) > deg(q), switch them without loss of generality. The division algorithm says q = mp + s, with deg(s) < deg(p) <= deg(q), so the pair (p,s) has lower total degree than (q,p). By induction, we can write gcd(p,s) = cp+ds for some polynomials c,d. Hence gcd(q,p) = gcd(p,s) = cp + ds = cp + d(q-mp) = dq + (c-md)p, which is what we wanted to compute.


"6. If p,q are two polynomials in C[z] such that p^2 = q^3, show that there exists another polynomial r such that p = r^3, q = r^2. (Hint: use the Fundamental Theorem of Algebra, that every polynomial in C[z] factors as a number times a product of (z-a_i)^{m_i}, where the m_i is the multiplicity of the root a_i.)"

If we factor, we find that the factor z-e shows up in p^2=q^3 the same number of times, M_e. Since M_e has to be a multiple of 2 (from the p^2) and 3 (from the q^3), it's got to be a multiple of 6. Hence p^2=q^3 is a 6th power of a polynomial, r, and this r does the job. Moreover, this r satisfies rq = p.

"7. Let R = C[x,y] / < x^2 - y^3 >. Use #6 to show that R is not isomorphic to C[z]."

Assume phi : R -> C[z] is an isomorphism, taking x |-> p(z) and y |-> q(z). Then by #6, there is some r(z) in C[z] with r^3 = p, r^2 = q. Since phi is a correspondence, there must be some f in R such that phi(f) = r. Since it is a ring isomorphism, this f must have fy = x. We want to show that no such f can exist.

This is a little confusing inside the quotient ring R, so pick F(x,y) an honest polynomial in the translate f = F + , hence F(x,y)y = x + (x^2-y^3)G(x,y) where G is some polynomial. If we set y=0, we get 0 = x + x^2G(x,0), which is impossible. Contradiction: there couldn't be such a phi.

Another way to say this is to look at the equation "fy=x" inside the quotient ring R / < y > = C[x,y] / < y, x^2-y^3 > = C[x,y] / < y, x^2 >, where it becomes "0=x", which is false.

HW #3

1. Let phi: R->S be a ring homomorphism, and I an ideal of S. Let J = phi^{-1}(I) := {r in R : phi(r) in I}. Show J is an ideal of R.

2. Let R = C[x_1..x_n]. For each i in 1..n, and t a nonzero complex number, define the ring homomorphism phi_{i,t} : R -> R by phi_{i,t}(x_j) = x_j for j not equal to i, and phi_{i,t}(x_i) = tx_i. Also phi_{i,t}(c) = c for c in C. (From here, you should be able to figure out what phi_{i,t} does to an arbitrary element of R.)

Let I be a monomial ideal. Show that phi_{i,t}^{-1}(I) = I for every i,t.

3. Harder: assume that phi_{i,t}^{-1}(I) = I for every i,t. Show I is a monomial ideal.
Hint: if g is a generator of I, then phi_{i,t}(g) in I for every i,t. Use this to show that g's monomials are also in I.

4. Fix i, and call an ideal I of R[x_1..x_n]  x_i-homogeneous if phi_{i,t}^{-1}(I) = I for every t. Show that if I is x_i-homogeneous, then radical(I) is also x_i-homogeneous.

5. Let I be a monomial ideal. Show that radical(I) is also a monomial ideal.

6. Describe an algorithm that, given a system of generators of a monomial ideal, computes the radical (by giving a system of generators).

7. Prove your algorithm works.

Feb 7

Thm. Given a monomial ideal, the vanishing set is a union of coordinate subspaces.
Proof: take one of the monomial generators, and look at the variables appearing in it. One of them must vanish. So V(I) is a union over those generators x_i, of the vanishing set of a monomial ideal on the coordinate hyperplane {x_i=0}. By induction, inside each one of those the vanishing set is a union of coordinate subspaces.

We defined simplicial complexes. This page about them is more about topology, but might be easier to understand. They correspond 1:1 to squarefree monomial ideals, as explained here (though that has a lot of extra stuff we haven't talked about).

We defined prime ideals, and showed that any intersection of prime ideals (such as just one) is radical. We looked at the prime ideals in Z, C[x], and R[x].

Feb 5

Given a polynomial, define its support to be the set of exponent vectors of its monomials.

Given an ideal generated by monomials, define its support, supp(I), to be the monomials in the ideal.

Theorem: a polynomial p is in a monomial ideal iff each of its monomials are, iff each one is a multiple of some monomial generator.

Theorem: Monomial ideals are finitely generated.

(Both of these can be found in section 1 of the book -- we've finally made it there.)

Answers to HW #1

"1. Let X be a set in C^n. Show V(I(X)) contains X. "

If x is in X, then every function vanishing on X vanishes on x, so x is in V(the functions vanishing on X), which is V(I(X)).


"2. Give an example of X where they're equal, and an example where they're not. "

If X is empty, then I(X) = C[x_1..x_n], and V(I(X)) is also empty (because for any point, there's a function not vanishing there).

If X is an infinite set in C^1, then I(X) = {0} because a polynomial p vanishes at z iff p is divisible by x-z, so it would have to be divisible by all x-z for all z in X. And then it would be infinite degree, if it weren't 0. Then, V(I(X)) = C^1. If X is infinite but not all of C^1, we have our example.

"3. Let I be an ideal in C[x_1,...,x_n]. Show I(V(I)) contains I. "

If i is in I, then i vanishes on V(I), so i is in the ideal of functions vanishing on V(I), i.e. i is in I(V(I)).

"4. If I,J are ideals, let I+J := {i+j : i in I, j in J}. Show I+J is an ideal. "

0's in there, and it's obviously closed under addition.
If p is in there, then p is of the form i+j. Then for any r, rp = r(i+j) = ri+rj, where ri is in I and rj is in J. Hence ri+rj is in I+J, so rp is in I+J, which was the condition we needed for an ideal.

"5. Show I+I = I. "

I+I is the ring elements of the form i+j, where i,j are in I.
(It is NOT the ring elements of the form i+i. For example, if the ring is Z, and I = Z, then I+I = I not the even integers.)
Since I is assumed to be closed under addition, each i+j is in I. That's one containment.
For the other, note that if j=0 then i+j = i, so everything in I is in I+I.

"6. Let I = < g_1, ..., g_m >. Show that V(I) = the set of x in C^n where every g_i vanishes. (Make sure you understand why that's different from the definition!)"

V(I) is the set of x where every p in I vanishes. p is in I if it's of the form sum_j r_j g_j.
If g_j vanishes at x, then so does r_j g_j, and so if each g_j vanishes there then so does p.
Hence, if every g_i vanishes at x, then every p in I vanishes at x, i.e. x is in V(I).
Conversely, if x is in V(I), then every p in I vanishes at x, so in particular every g_i vanishes at X.

"7. Assume g_1, ..., g_m are homogeneous linear polynomials, and let I be the ideal generated by them. Let p be another homogeneous linear polynomial. How would you test whether p is in I? (Describe an algorithm, perhaps, that correctly answers "yes" or "no" after finite time.)"

We're trying to write p = sum_i q_i g_i. Break q_i into its constant term c_i plus the rest, r_i.
Then p = sum_i c_i g_i + sum_i r_i g_i. The first of these two sums has only linear terms, and the second has no linear terms (just higher degree), so there can be no cancelation between them. Moreover p has only linear terms by assumption, so the sum_i r_i g_i part must vanish. The upshot is that it's no easier or harder to do this with general q_i than it is with constant coefficients. So the question becomes, can we write p as sum_i c_i g_i?

Write out the n coefficients of g_i as a row vector, and put them together into an mxn matrix.
Now we're asking whether p's row vector is in the row span of that matrix.
The algorithm that tests this is usually called Gaussian elimination (even though the Chinese invented it many centuries earlier).

"8. What if the (g_i) and p in #7 are all homogeneous of the same degree, but that degree isn't necessarily 1? "

The same degree argument as in #7 says that we only need to consider constant coefficients c_i. Now again, make each g_i and p into a row vector, except that the columns are now indexed by the monomials of that degree, instead of x_1..x_n (the monomials of degree 1). Then Gaussian elimination does the job once more.

HW #2

1. Let R = C[x_1..x_n], and R_d := the homogeneous polynomials of degree d.
For n=2, compute dim(R_d).

2. An ideal I in a polynomial ring is called graded if I is the sum over d of (I intersect R_d), i.e., if for every p in I, when we break p into its homogeneous components p_d each of those is also in I. Give an example of an ideal in C[z] that is not graded, and prove that it isn't.

3. If I,J are graded ideals, show I+J and (I intersect J) are graded too.

4. Let M_n(C) denote the noncommutative (!) ring of nxn complex matrices, where multiplication is matrix multiplication.
Fix T an element of M_n(C).
Define f : C[z] -> M_n(C), taking p(z) |-> p(T).
Let I = ker(f). This is principal (being an ideal of C[z]), i.e. I = < m(z) > for some m(z). What is this polynomial called in a linear algebra class?
Compute it for T = identity matrix.

5. Let p(z),q(z) be polynomials, and I = < p(z),q(z) >. Since I is principal, it's generated by some element r(z) = a(z)p(z) + b(z)q(z). What is this r(z) called? (some name involving p,q)

[Do you see how to use the division algorithm to compute the a(z),b(z)?]

6. If p,q are two polynomials in C[z] such that p^2 = q^3, show that there exists another polynomial r such that p = r^3, q = r^2. (Hint: use the Fundamental Theorem of Algebra, that every polynomial in C[z] factors as a number times a product of (z-a_i)^{m_i}, where the m_i is the multiplicity of the root a_i.)

7. Let R = C[x,y] / < x^2 - y^3 >. Use #6 to show that R is not isomorphic to C[z].

Jan 31

Def. The quotient of a ring by an ideal.

If X is a subset of C^n, define Fun(X) := C[x_1..x_n] / I(X).

Def. ring homomorphism and isomorphism.

Example. If X = {xy=0}, so I(X) = < xy >, then Fun(X) is not isomorphic to C[z].

Proof: Fun(X) has "zero divisors", and C[z] doesn't.

Lemma. If p,q are polynomials in C[z], q nonzero, then there exist polynomials m,r such that p = mq + r, and deg(r) < deg(q). (If r is 0, we define its degree to be negative infinity.)

Theorem. Any ideal in C[z] is principal (generated by one element).