Hilbert Functions and the Chinese Remainder Theorem: Open Problems

Notes:

This 20 minute talk was given February 27, 1999, at the UNL Regional Workshop.
For this talk let k be any algebraically closed field.

Preliminary Problems

Problem 1: Given points x₁, ... , x_n of k and values v₁, ... , v_n of k, find all polynomials f(x) in k[x] such that f(x_i) = v_i for all i.
Solution: There exists a unique solution, f_L(x), of degree at most n-1; it is given by the Lagrange interpolation formula:

Let g(x) = (x-x₁)...(x-x_n)
Let g_i(x) = g(x)/(x-x_i) [This is a polynomial.]
Then f_L(x) = (v₁/g₁(x₁))g₁(x) + ... + (v_n/g_n(x_n))g_n(x)

The complete set of solutions is f_L(x) + (g); i.e., f_L(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 I_j to v_j, for all j, where I_j is the ideal (x-x_j) of the ring R=k[x]. I.e., given an element v = (v₁, ... , v_n) of R/I₁ x ... x R/I_n, find all elements f of R mapping to v under the homomorphism H : f -> (f₁, ... , f_n), where f_j is the image of f under the quotient R -> R/I_j. The Chinese Remainder Theorem (CRT) tells us that H : R -> R/I₁ x ... x R/I_n is surjective with kernel I=I₁...I_n; 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 u_j such that H(u_j) = ( 0, ... , 1, 0, ...,0), with the 1 in the jth spot. Then a solution is given by u₁F₁+...+u_nF_n, where F_j maps to f_j under the quotient R -> R/I_j.

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 t_j derivatives. I.e., we ask to recover an f, only being given f modulo I_j = (x-x_j)^t_j+1 for each j.
Solution: The solution is formally the same as before if we merely redefine I_j to be (x-x_j)^t_j+1. The CRT again gives us H : R -> R/I₁ x ... x R/I_n with kernel I = I₁...I_n, again there is a unique solution f_L, now of degree at most t₁ + ... + t_n + n - 1, given by a generalized Lagrange interpolation formula, and the complete solution set is f_L + 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 h_I(t), called the Hilbert function of I. But f_L 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 f_L, and otherwise it is just f_L + (I)_N, which we can regard as a space of dimension h_I(N). Thus the solution to Problem 3 is given by computing the Hilbert function h_I.

Fact: h_I(t) = max( 0 , t - (t₁ + ... + t_n + n - 1)).
Proof: I is just (g), where g(x) = (x-x₁)^t₁+1...(x-x_n)^t_n+1, so there are no polynomials in I of degree less than t₁ + ... + t_n + n, and if t is t₁ + ... + t_n + 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 - (t₁ + ... + t_n + n). Now one just needs to note for t >= (t₁ + ... + t_n + n) that the set of polynomials of degree t - (t₁ + ... + t_n + n) is a vector space of dimension t - (t₁ + ... + t_n + n - 1).

Fact: h_I is independent of the points x_j.

The Main Problem

Problem 4: Let's ask the same problem as Problem 3, but now our n points will be points (x₁,y₁), ... , (x_n,y_n) of the plane k x k = k².

Solution: Formally, the CRT is exactly the same: H : R -> R/I₁ x ... x R/I_n is surjective with kernel I, except now R = k[x,y] and I_j = (x - x_j, y - y_j)^t₁+1. Thus our solution is again given by computing h_I.

Facts:

There exists as before a solution f_L of degree at most t₁ + ... + t_n + n - 1, BUT it need no longer be unique: consider n = 2, our two points being (0,0) and (1,1), where we want polynomials which vanish at (0,0) and have value 1 at (1,1). Then x and y both give solutions of least degree.
h_I is no longer independent of the points: suppose I is the ideal of all polynomials vanishing at 3 points. Then h_I(1) is 0 if the points don't lie on a line, and 1 if they do.

Open Problem 1: Given I as in Problem 4, what is the minimum achievable value of h_I(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 h_I(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 t₁ or less (i.e., less Binom(t₁+2,2)). For n more than 1, we eliminate a space of dimension Binom(t_j+2,2) at each of j points so:

h_I(t) >= Binom(t+2,2) - Binom(t₁+2,2) - ... - Binom(t₁+2,2).

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

Conjecture 1 (special case of 1986 conjecture): Suppose we take t_j = m for all j, and n > 9. Then
h_I(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 h_I(t) > 0.

Aside: Conjecture 1 implies Conjecture 2.