Hilbert Functions and the Chinese Remainder Theorem: Open Problems
- This 20 minute talk was given
February 27, 1999, at the UNL Regional Workshop.
- For this talk let k be any algebraically closed field.
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).]
- Let g(x) = (x-x1)...(x-xn)
- Let gi(x) = g(x)/(x-xi) [This is a polynomial.]
- Then fL(x) =
(v1/g1(x1))g1(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.
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.
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.
hI(t) = max( 0 , t - (t1 + ... + tn + n - 1)).
Proof: I is just (g), where g(x) =
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).
hI is independent of the points xj.
The Main Problem
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.
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
- There exists as before a solution fL of degree at most
t1 + ... + tn + 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.
- hI is no longer independent of the points: suppose I is the ideal
of all polynomials vanishing at 3 points. Then hI(1) is 0 if the
points don't lie on a line, and 1 if they do.
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,
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.