Computational Aspects of Zero-Dimensional Schemes

K field ℙ^{n} projective n-space over K 𝕏 = {P_{1}, …, P_{s}} set of s K-rational points P_{i} = (p_{i0} : …: p_{in}) with p_{ij} ∈ K A = K[x_{0}, …, x_{n}] polynomial ring over K I_{𝕏} ⊆ A homogeneous vanishing ideal of X R = A/I_{𝕏} homogeneous coordinate ring of 𝕏 HF_{𝕏} : ℤ ⟶ ℕ (i ↦ dim_{K}(R_{i})) Hilbert function of 𝕏 𝕋^{n+1} set of terms (power products, monomials) in A σ term ordering on 𝕋^{n+1} 1 Computing the Homogeneous Vanishing Ideal

Problem. Given the coordinates p_{ij} of the points, compute the homogeneous vanishing ideal I_{𝕏} = I_{P_{1}} ∩ ⋯ I_{P_{s}} Classical Solution. Since we know

I_{P_{i}} = (p_{ij}x_{k} − p_{ik}x_{j} | 0 ≤ j < k ≤ n)

we can use Gröbner bases to compute the intersection I_{P_{1}} ∩ ⋯ ∩ I_{P_{s}}.

But for s >> 0, this is computationally expensive, because the Gröbner bases become huge. Idea. The classical Buchberger-Möller algorithm gives us a way to compute the vanishing ideal of an affine set of points using linear algebra. It is very efficient.

We want to mimick the procedure and compute the intersection of the 1-dimensional ideals I_{P_{1}}, …, I_{P_{s}} degree by degree. In each degree we are dealing with a finite-dimensional vector space and linear algebra methods apply.

Definition 1.1. For a computation which proceeds degree by degree, a stopping criterion is a logical condition which depends only on the data obtained in the computation up to the current degree d, and which, if satisfied, guarantees that the result computed so far is complete.

Proposition 1.2 (Primitive Stopping Criterion) If we have computed a σ-Gröbner basis of I_{𝕏} up to degree s, the result is complete.

Theorem 1.3 (The Projective BM-Algorithm) Assume that there exists a function StoppingCriterion(G) which returns TRUE if the set G computed so far is a σ-Gröbner basis of I_{𝕏} = I_{P_{1}} ∩ ⋯ ∩ I_{P_{s}}, and FALSE otherwise.

Consider the following sequence of instructions. PBM1 Start with empty lists G = [ ], H = [ ], a list L = [1], and

d = 0. PBM2 Apply the function StoppingCriterion(G). If it returns

TRUE, return the list G and stop. Otherwise increase d by one, set M = (m_{ij}) to be a matrix over K with zero rows and s columns, and let L be the list of all terms of degree d which are not multiples of any element of {LT_{σ}(g) | g ∈ G}.

PBM3 If L = ∅, go to step PBM2. Otherwise choose the term

t = min_{σ}(L) and remove it from L. PBM4 Compute the vector v = (t(P_{1}), …, t(P_{s})) ∈ K^{s} and reduce

it against the rows of M to obtain

v^{∗} = v − ∑_{i} a_{i} (m_{i1}, …, m_{is}) with a_{i} ∈ K

PBM5 If v^{∗} = (0, …, 0), then append the polynomial t−∑_{i} a_{i}h_{i} to the list G, where h_{i} is the i^{th} element of the list H. Continue with step PBM3.

PBM6 Otherwise v^{∗} ≠ 0, so append v^{∗} as a new row to M and t−∑_{i} a_{i}h_{i} as a new element to H. Continue with step PBM3.

This is an algorithm which returns the reduced σ-Gröbner basis G of the ideal I_{𝕏} = I_{P_{1}} ∩ ⋯ ∩ I_{P_{s}}.

Problem. We need a better stopping criterion!

Definition 1.4. Let 𝕋_{d}^{n+1} be the set of power products of degree d in K[x_{0}, …, x_{n}], and let Q ⊆ 𝕋_{d}^{n+1}. We say that two power products t, t′ are connected in Q if there is a sequence of power products t_{0}, t_{1}, …, t_{r} ∈ Q with t_{0} = t and t_{r} = t′ such that for each i = 1, …, r there exist α, β ∈ {0, …, n} satisfying t_{i} = t_{i−1} · x_{α}/x_{β}. The intuitive meaning of this notion is that one can pass from one t_{i} to the next by replacing one indeterminate by another.

We define the connected components in Q in the obvious way; they are clearly disjoint. The connected component of a power product t ∉ Q is empty.

Theorem 1.5 (Projective Stopping Criterion) In the setting of the projective BM-algorithm, suppose we have computed homogeneous polynomials whose leading terms generate (LT_{σ}(I_{𝕏})_{≤d}) for some degree d ≥ 1 and that the following conditions hold:

a) HF_{A/ LT_{σ}(I_{𝕏})}(d) = s or d > 0 and HF_{A/ LT_{σ}(I_{𝕏})}(d) = HF_{A/ LT_{σ}(I_{𝕏})}(d − 1)

b) For i = 0, …, n, every power product in the connected component of x_{i}^{d} in (𝕋^{n+1} \ LT_{σ}(I_{𝕏}))_{d} is divisible by x_{i}. Then the homogeneous polynomials computed so far are a σ-

Gröbner basis of I_{𝕏}.

Problem. The projective BM-algorithm works fine over finite fields, but for K = ℚ the coefficients in the matrix M become too large and even linear algebra is slow.

Theorem 1.6 (The Modular BM-Algorithm) Let n ≥ 1, let σ be a term ordering on 𝕋^{n} and P_{i} = (p_{i1}, …, p_{in}) ∈ ℚ^{n} for i = 1, …, s. Consider the following instructions.

MBM1 Let Q = [ ], G = [ ] and G_{m} = [ ] be empty lists, and let m = 1.

MBM2 Pick a new prime number p, different from the previous ones and such that the points P_{i} have distinct reductions \overline{P}_{i} modulo p

MBM3 Apply the classical Buchberger-Möller Algorithm to K = 𝔽_{p} and the set of points \{\overline{P}_{1}, …, \overline{P}_{s}\}. Denote the result by [G_{p}, Q_{p}].

MBM4 Compare Q_{p} with Q in the following way:

for Q = [q_{1}, q_{2}, …] and Q_{p} = [q′_{1}, q′_{2}, …], we say that Q is better than Q′ if for some index j we have q_{i} = q′_{i} for i = 1, 2, …, j − 1 and q_{j} <_{σ} q′_{j}. If Q is better than Q_{p} then continue with step MBM2. If Q_{p} is better than Q then replace Q by Q_{p}, set m equal to p, put G_{p} in G_{m}, then continue with step MBM2.

MBM5 At this point we have Q_{p} = Q. Replace m by mp. Update G_{m} by combining it with G_{p} using the Chinese Remainder Theorem. Perform rational recovery on G_{m} with modulus m, and call the result G′.

MBM6 If G′ ≠ G then replace G by G′ and continue with MBM2.

MBM7 Now G′ = G. Check whether all polynomials in G vanish at all points of the set {P_{1}, …, P_{s}}. If they do not, go back to step MBM2. Otherwise return [G, Q] and stop.

This is an algorithm which returns the reduced σ-Gröbner basis G of I_{𝕏} and a list of terms Q whose residue classes form a K-basis of K[x_{1}, …, x_{n}]/I_{𝕏}.

Application: Design of Experiments

Problem. For some experiment, several parameters λ_{1}, …, λ_{n} can take finitely many values λ_{i} ∈ {α_{i1}, …, α_{iν_{i}}} ⊆ ℚ each. The set of all tuples (α_{1 j_{1}}, …, α_{n j_{n}}) ∈ ℚ^{n} such that 1 ≤ j_{1} ≤ ν_{1}, …, 1 ≤ j_{n} ≤ ν_{n} is called the full design 𝔻.

There is an (unknown) function f : 𝔻 ⟶ ℚ, called the model. We would like to choose a small subset 𝔽 ⊆ 𝔻, called a fraction in such a way that we can reconstruct the function f from its restriction f|_{𝔻} : 𝔽 ⟶ ℚ and some additional information about f. (One says that we want to identify the model.) Mathematical solution method.

a) Since the model f : 𝔻 ⟶ ℚ is defined on a finite set 𝔻, it is a polynomial function. The corresponding polynomial F ∈ ℚ[x_{1}, …, x_{n}] is unique up to addition of elements of I_{𝔻}.

b) The set 𝔻 is a very special set of points (a complete intersection), and we know its vanishing ideal

I_{𝔻} = ((x_{1} − α_{1 1}) ⋯ (x_{1} − α_{1 ν_{1}}, …, (x_{n} − α_{n 1}) ⋯ (x_{n} − α_{n ν_{n}}))

c) The additional information about the model we have usually concerns the support of F and tells us what the size of 𝔽 should be.

d) Try many subsets 𝔽 ⊆ 𝔻 of the appropriate size. Everytime compute I_{𝔽} using the modular BM-algorithm and check (using simple linear algebra) whether 𝔽 allows us to identify the model.

Literature. 1) J. Abbott, A. Bigatti, M. Kreuzer, and L. Robbiano, Computing ideals of points, J. Symb. Comp. 30 (2000), 341–356

2) L. Robbiano, Gröbner bases and statistics, in: B. Buchberger and F. Winkler (eds.), Gröbner Bases and Applications, LMS Lecture Notes 251, Cambridege University Press 1998, pp. 179–204

3) J. Abbott, M. Kreuzer, and L. Robbiano, Computing zero-dimen-sional schemes, J. Symb. Comp. (to appear)

Application: Implicitization

Problem. Suppose we are given f_{1}, …, f_{s} ∈ K[x_{1}, …, x_{n}]. We want to compute the ideal of all polynomials g ∈ K[y_{1}, …, y_{s}] such that g(f_{1}, …, f_{s}) = 0. Classical Solution. Form the ideal

J = (y_{1} − f_{1}, …, y_{s} − f_{s}) ⊆ K[x_{1}, …, x_{n}, y_{1}, …, y_{s}]

and compute a Gröbner basis of J with respect to some elimination ordering for {x_{1}, …, x_{n}}.

Except for small examples, this method leads to very hard Gröbner basis computations!

New Method. In the spirit of the BM-algorithm, one can proceed as follows.

1) Reduce the computation to the case where all polynomials f_{1}, …,f_{s} are homogeneous of the same degree d.

2) Let deg(x_{i}) = 1 and deg(y_{j}) = d. Then J is a homogeneous ideal with respect to this grading. For a suitable term ordering, (y_{1}, …, y_{s}) is the leading term ideal of J. Hence we know the Hilbert function of J.

3) Compute the kernel of the K-algebra homomorphism

φ : K[y_{1}, …, y_{s}] ⟶ K[x_{1}, …, x_{n}]

which is defined by φ(y_{i}) = f_{i} for i = 1, …, s. To this end, proceed degree by degree and apply the method of the projective BM-algorithm. Since we know the Hilbert function, we have a stopping criterion.

2 Checking Uniformity Conditions

𝕏 = {P_{1}, …, P_{s}} set of K-rational points in ℙ^{n} R = A/I_{𝕏} homogeneous coordinate ring of 𝕏 HF_{𝕏} : ℤ ⟶ ℕ Hilbert function of 𝕏 0 = HF_{𝕏}(−1) < 1 = HF_{𝕏}(0) < ⋯ < HF_{𝕏}(a_{𝕏}) <

s = HF_{𝕏}(a_{𝕏} + 1) = HF_{𝕏}(a_{𝕏} + 2) = ⋯

Definition 2.1. Let 1 ≤ i ≤ s and 1 ≤ j ≤ a_{𝕏}. The scheme 𝕏 is called (i,j)-uniform if every subscheme 𝕐 ⊆ 𝕏 consisting of s − i points satisfies HF_{𝕐}(j) = HF_{𝕏}(j).

Example 2.2. a) The scheme 𝕏 has the Cayley-Bacharach property iff 𝕏 is (1, a_{𝕏})-uniform.

b) Suppose that 𝕏 spans ℙ^{n}. Then 𝕏 is in linearly general position iff 𝕏 is (s − n − 1, 1)-uniform.

c) 𝕏 is in uniform position iff 𝕏 is (i, j)-uniform for all i, j.

d) The Gale transform of 𝕏 is well-defined iff 𝕏 is (2, 1)-uniform. More generally, the i^{th} canonical transform of 𝕏 is well-defined iff 𝕏 is (2, i)-uniform.

e) The Eisenbud-Green-Harris conjecture asks whether any zerodimensional complete intersection of quadrics is (2^{n−j} − 1, j)-uniform for 1 ≤ j ≤ a_{𝕏}.

Remark 2.3. a) If 𝕏 is (i, j)-uniform, then 𝕏 is (k, ℓ)-uniform for all 1 ≤ k ≤ i and all 1 ≤ j ≤ ℓ.

b) If 𝕏 is (i, j)-uniform, then we have i ≤ s − HF_{𝕏}(j).

Problem. How can one compute the region of uniformity efficiently? Answer. In general, this is impossible. The problem is known to be NP-complete. Thus we can only try to find efficient algorithms for special cases.

Proposition 2.4 (Geramita – K – Robbiano) Let 1 ≤ i ≤ Δ = s − HF_{𝕏}(a_{𝕏}). Moreover, let f_{1}, …, f_{s} ∈ A_{a_{𝕏}+1} be polynomials whose residue classes in R are the separators of 𝕏, i.e. such that f_{j}(P_{k}) = δ_{jk} for j, k = 1, …, s. Then the following conditions are equivalent:

a) 𝕏 is (i, a_{𝕏})-uniform.

b) The images of any Δ elements of {f_{1}, …, f_{s}} in R_{a_{𝕏}+1} are K-linearly independent.

c) If one chooses a K-basis b_{1}, …, b_{Δ} of R_{a_{𝕏}+1} and forms the matrix B whose columns are the coordinate tuples of \overline{f}_{1}, …, \overline{f}_{s} in that basis, then the maximal minors of B are all different from zero.

The last condition can be checked efficiently using a recent algorithm of Krammer and K. which uses certain versions of Bareiss’ algorithm to compute many maximal minors simultaneously.

Proposition 2.5 Let 1 ≤ j ≤ a_{𝕏}. The following conditions are equivalent.

a) 𝕏 is (s − HF_{𝕏}(j), j)-uniform.

b) The multiplicaiton map μ_{j} : R_{j}⊗(ω_{R})_{−j} ⟶ (ω_{R})_{0} is 1-generic, i.e. we have μ_{j}(r ⊗ w) = 0 ⇒ r = 0 or w = 0.

Here ω_{R} is the canonical module of R and can be computed efficiently using the algorithm of Beck – K. Moreover, the second condition can be checked efficiently.

Proposition 2.6 (Geramita – K – Robbiano) Let 1 ≤ j ≤ a_{𝕏}, and suppose that 𝕏 is (s − HF_{𝕏}(j), j)-uniform. Choose a zero-dimensional complete intersection 𝕍 = Z(g_{1}, …, g_{n}) containing 𝕏 (for instance a full design!). The set of points 𝕐 = 𝕍\𝕏 defined by I_{𝕐} = I_{𝕍} :_{A} I_{𝕏} is called the residual scheme of 𝕏 in 𝕍. Let α = min{j | (I_{𝕍})_{j} ⊂ (I_{𝕐})_{j}} be its initial degree in 𝕍. Then the following conditions are equivalent.

a) 𝕏 is (s − HF_{𝕏}(j) + 1, j − 1)-uniform.

b) We have [I_{𝕍} : (I_{𝕐})_{α+a_{𝕏}−j+1}]_{j−1} = (I_{𝕏})_{j−1}.

The last condition can be checked efficiently using two truncated Gröbner basis computations. This result has been implemented by T. Eisenmann. Literature. 1) A.V. Geramita, M. Kreuzer and L. Robbiano, Cayley-Bacharach schemes and their canonical modules, TAMS 339 (1993), 163–189

2) B. Krammer, Algorithmic linear algebra for polynomial matrices (in German), diplom thesis, Regensburg University 2001

3) M. Kreuzer, On the canonical module of a 0-dimensional scheme, Can. J. Math. 46 (1994), 357–379

4) M. Kreuzer, On the canonical ideal of a set of points, Boll. UMI 1-B 8 (2000), 221–261

5) S. Beck and M. Kreuzer, How to compute the canonical module of a set of points, in: L. Gonzales-Vega and T. Recio (eds.), Algorithms in Algebraic Geometry and Applications, Progress in Math. 143, Birkhäuser Verlag 1996, pp. 51–78

6) T. Eisenmann, Implementation and optimization of algorithms for zero-dimensional schemes (in German), diplom thesis, Regensburg University 2002 Application: Coding Theory

p prime number, e > 0, q = p^{e}

K = 𝔽_{q} finite field having q elements

C ⊆ K^{s} subvector space is called a linear code of length s d = dim_{K}(C) is called the dimension of C m(C) = min{#{i | c_{i} ≠ 0} | (c_{1}, …, c_{s}) ∈ C \ {0}} is called the

minimal distance of C

Proposition 2.7 (Singleton Bound) For every linear code C we have m(C) ≤ s − d + 1.

Proposition 2.8 (Hansen’s Construction) Let 𝕏 = {P_{1}, …, P_{s}} ⊆ ℙ^{n} be a set of K-rational points and let 1 ≤ j ≤ a_{𝕏}.

a) The image of the K-linear map Φ_{j} : R_{j} ⟶ K^{s} defined by f ↦ (f(P_{1}), …, f(P_{s})) is a linear code of length s and dimension d = HF_{𝕏}(j). It is called the j^{th} Reed-Muller code associated to 𝕏 and denoted by C_{j}(𝕏).

b) The minimal distance of C_{j}(𝕏) is

m(C_{j}(𝕏)) = max{i | 𝕏 is (i, j)-uniform } + 1

Consequently, computing the minimal distances of the Reed-Muller codes associated to 𝕏 is equivalent to computing the region of uniformity of 𝕏.

3 Computing Hilbert-Kunz Functions

K = 𝔽_{q} finite field having q = p^{e} elements

R = K[x_{0}, …, x_{n}]/I 1-dimensional standard graded K-algebra

Definition 3.1. The function HK_{R} : ℕ ⟶ ℕ defined by HK_{R}(i) = dim_{K} R/(x_{0}^{p^{i}}, …, x_{n}^{p^{i}}) is called the Hilbert-Kunz function of R.

Proposition 3.2 (P. Monsky) If dim(R) = 1 then there is a number c(R) ∈ ℕ and a periodic function φ : ℕ ⟶ ℕ such that HK_{R}(i) = c(R) · p^{i} + φ(i) for all i >> 0.

It is known that c(R) is the multiplicity of R. Thus it can be computed. Problems. 1) How can one compute φ? Is there a bound for the length of the period of φ?

2) How can we find N ∈ ℕ such that the formula of the proposition holds for i ≥ N? Easy Reductions. 1) By computing a reduced Gröbner basis of I, we may assume that K is the field of definition of I.

2) By computing J = H_{𝔪}^{0}(R) = {r ∈ R | 𝔪^{i}·r = 0 for some i ≥ 0}, where 𝔪 = (x_{0}, …, x_{n}), we may assume that I is saturated.

3) By passing to a finite extension field of K and by performing a linear change of coordinates, we may assume that x_{0} ∈ R_{1} is a nonzero divisor.

4) By enlarging K if necessary, we may assume that the support of 𝕏 = Proj(R) consists of K-rational points.

Proposition 3.3 Consider the following instructions.

1) If H_{𝔪}^{0}(R) ≠ 0, define M = max{i ∈ ℕ | (H_{𝔪}^{0}(R))_{i} ≠ 0} and replace R by R/H_{𝔪}^{0}(R).

2) Enlarge K to a field K′ = F_{q^{e′}} such that there is a linear nonzero divisor in R′ = K′⊗R and the support of 𝕏 = Proj(R′) consists of K′-rational points {P_{1}, …, P_{s}}.

3) For i = 1, …, s, compute the nilpotency index

e_{i} = min{k ∈ ℕ | (𝔪_{𝕏,P_{i}})^{k} = 0}

of 𝕏 at P_{i} and set N = max{e_{1}, …, e_{s}, M + 1}.

4) Return the pair (N, e′) and stop. This is an algorithm which computes numbers N, e′ such that

HK_{R}(i) = mult(R) p^{i} + φ(i) whenever p^{i} ≥ N

and such that φ is a periodic function whose period length divides e′.

This algorithm has been implemented by V. Augustin. For reduced zero-dimensional schemes one can easily prove HK_{R}(i) = sp^{i} − s + 1 for all i ≥ 0. But for non-reduced zero-dimensional schemes there are many open questions. For instance, the analogue of the theorem of Alexander-Hirschowitz (i.e. the Hilbert-Kunz function of generically chosen double points) is not known.

Literature. 1) P. Monsky, The Hilbert-Kunz function, Math. Ann. 263 (1983), 43–39

2) M. Kreuzer, Computing Hilbert-Kunz functions of 1-dimensional graded rings, preprint 2000

3) V. Augustin, Effective computation of Hilbert-Kunz functions (in German), diplom thesis, Regensburg University 2001