# 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_{1}, ... , x_{n} of k and values
v_{1}, ... , 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
_{1})...(x-x_{n})
- Let g
_{i}(x) = g(x)/(x-x_{i}) [This is a polynomial.]
- Then f
_{L}(x) =
(v_{1}/g_{1}(x_{1}))g_{1}(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_{1}, ... , v_{n})
of R/I_{1} x ... x R/I_{n}, find all elements
f of R mapping to v under the homomorphism H : f -> (f_{1}, ... , 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_{1} x ... x R/I_{n}
is surjective with kernel I=I_{1}...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_{1}F_{1}+...+u_{n}F_{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})^{tj+1} for each j.

Solution: The solution is formally the same as before
if we merely redefine I_{j} to be (x-x_{j})^{tj+1}.
The CRT again gives us H : R -> R/I_{1} x ... x R/I_{n}
with kernel I = I_{1}...I_{n}, again there is a unique solution f_{L},
now of degree at most t_{1} + ... + 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_{1} + ... + t_{n} + n - 1)).

Proof: I is just (g), where g(x) =
(x-x_{1})^{t1+1}...(x-x_{n})^{tn+1},
so there are no polynomials in I of degree less than t_{1} + ... + t_{n} + n,
and if t is t_{1} + ... + 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_{1} + ... + t_{n} + n).
Now one just needs to note for t >= (t_{1} + ... + t_{n} + n) that
the set of polynomials of degree t - (t_{1} + ... + t_{n} + n)
is a vector space of dimension t - (t_{1} + ... + 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_{1},y_{1}), ... , (x_{n},y_{n})
of the plane k x k = k^{2}.

Solution: Formally, the CRT is exactly the same:
H : R -> R/I_{1} 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})^{t1+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_{1} + ... + 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_{1} or less
(i.e., less Binom(t_{1}+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_{1}+2,2) - ... - Binom(t_{1}+2,2).

The reason for the inequality is that the spaces eliminated may overlap
(as they do, for example, for n=2, t_{1}=t_{2}=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.