Hilbert Functions and the Chinese Remainder Theorem: Open Problems


Preliminary Problems

Problem 1: Given points x1, ... , xn of k and values v1, ... , vn of k, find all polynomials f(x) in k[x] such that f(xi) = vi for all i.
Solution: There exists a unique solution, fL(x), of degree at most n-1; it is given by the Lagrange interpolation formula: The complete set of solutions is fL(x) + (g); i.e., fL(x) + p(x)g(x), where p(x) is any polynomial. [In the usual notation, (g) is the ideal generated by g(x).]

Restatement of Problem 1 and Solution: The problem is to find all f(x) conguent mod Ij to vj, for all j, where Ij is the ideal (x-xj) of the ring R=k[x]. I.e., given an element v = (v1, ... , vn) of R/I1 x ... x R/In, find all elements f of R mapping to v under the homomorphism H : f -> (f1, ... , fn), where fj is the image of f under the quotient R -> R/Ij. The Chinese Remainder Theorem (CRT) tells us that H : R -> R/I1 x ... x R/In is surjective with kernel I=I1...In; i.e., there is a solution, and given any solution f, the set of all solutions is just f + I. The usual proof of the CRT is by finding elements uj such that H(uj) = ( 0, ... , 1, 0, ...,0), with the 1 in the jth spot. Then a solution is given by u1F1+...+unFn, where Fj maps to fj under the quotient R -> R/Ij.

Problem 2: Take the same problem as Problem 1, except now specify not just the value we want at each of the n points, but also the first tj derivatives. I.e., we ask to recover an f, only being given f modulo Ij = (x-xj)tj+1 for each j.
Solution: The solution is formally the same as before if we merely redefine Ij to be (x-xj)tj+1. The CRT again gives us H : R -> R/I1 x ... x R/In with kernel I = I1...In, again there is a unique solution fL, now of degree at most t1 + ... + tn + n - 1, given by a generalized Lagrange interpolation formula, and the complete solution set is fL + I.

Problem 3: How many solutions are there of degree at most N?
Solution: Let (I)t denote the elements (including 0) of the ideal I of degree at most t. This is a k-vector space; its dimension as a function of t is denoted hI(t), called the Hilbert function of I. But fL is the least degree solution and I is principal, generated by g(x). Thus the set of solutions of degree at most N is empty if N < deg fL, and otherwise it is just fL + (I)N, which we can regard as a space of dimension hI(N). Thus the solution to Problem 3 is given by computing the Hilbert function hI.

Fact: hI(t) = max( 0 , t - (t1 + ... + tn + n - 1)).
Proof: I is just (g), where g(x) = (x-x1)t1+1...(x-xn)tn+1, so there are no polynomials in I of degree less than t1 + ... + tn + n, and if t is t1 + ... + tn + n or more, the polynomials in I of degree t are exactly those of the form m(x)g(x), where m(x) is any polynomial of degree t - (t1 + ... + tn + n). Now one just needs to note for t >= (t1 + ... + tn + n) that the set of polynomials of degree t - (t1 + ... + tn + n) is a vector space of dimension t - (t1 + ... + tn + n - 1).

Fact: hI is independent of the points xj.

The Main Problem

Problem 4: Let's ask the same problem as Problem 3, but now our n points will be points (x1,y1), ... , (xn,yn) of the plane k x k = k2.

Solution: Formally, the CRT is exactly the same: H : R -> R/I1 x ... x R/In is surjective with kernel I, except now R = k[x,y] and Ij = (x - xj, y - yj)t1+1. Thus our solution is again given by computing hI.

Facts: Open Problem 1: Given I as in Problem 4, what is the minimum achievable value of hI(t) for each t, allowing the points to move around? (For a nice survey of this problem, see Rick Miranda's recent article, "Linear Systems of Plane Curves", in the February, 1999 AMS Notices.)

Conjectural Answer: I first published in 1986 [CMS Conf Proc v. 6] a conjectural solution to this problem. Various equivalent formulations of this conjecture have appeared since, such as the one given in Rick's article. Here I'll give a version of the conjecture in a special case.

The solution to the problem with n = 1 is easy. In this case hI(t) is the number of all polynomials of degree t or less (i.e., the binomial coefficient Binom(t+2,2), or t+2 choose 2) less those that have degree t1 or less (i.e., less Binom(t1+2,2)). For n more than 1, we eliminate a space of dimension Binom(tj+2,2) at each of j points so:

hI(t) >= Binom(t+2,2) - Binom(t1+2,2) - ... - Binom(t1+2,2).

The reason for the inequality is that the spaces eliminated may overlap (as they do, for example, for n=2, t1=t2=1).

Conjecture 1 (special case of 1986 conjecture): Suppose we take tj = m for all j, and n > 9. Then
hI(t) = max ( 0 , Binom(t+2,2) - n(Binom(m+2,2))) if the n points are sufficiently general.
[Note: Ciliberto-Miranda (1998) have now proved this for m<=11.]

Open Problem 2: With I as in Conjecture 1, find the least N such that (I)N generates I.

Based on work done last summer jointly with S. Fitchett and S. Holay, we have:

Conjecture 2: If I is as in Conjecture 1 with n an even square and m sufficiently large, then (I)a generates I, where a is the least t such that hI(t) > 0.

Aside: Conjecture 1 implies Conjecture 2.