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.
