J. Symbolic Computation (1999) 11, 1–000

Computing Ideals of Points ^{†}^{‡}

J. ABBOTT^{∗}, A. BIGATTI^{∗}, M. KREUZER^{∗∗}, AND L. ROBBIANO^{∗}

∗Department of Mathematics, University of Genova, Italy ∗∗ Department of Mathematics, University of Regensburg, Germany

(Received 14 May 1999)

We address the problem of computing ideals of polynomials which vanish at a finite set of points. In particular we develop a modular Buchberger-Möller algorithm, best suited for the computation over ℚ, and study its complexity; then we describe a variant for the computation of ideals of projective points, which uses a direct approach and a new stopping criterion. The described algorithms are implemented in CoCoA, and we report some experimental timings.

1. Introduction

The easiest geometric object in affine or projective space is a single rational point. It has no secrets, in particular its defining ideal, i.e. the set of all the polynomials which vanish at the point, is straightforward to describe. Namely, for an affine point with coordinates (a_{1}, …, a_{n}), the corresponding ideal is 𝔭 = (x_{1} − a_{1}, …, x_{n} − a_{n}); while for a projective point with coordinates (a_{0} : …: a_{n}), the corresponding homogeneous ideal is 𝔓 = (a_{i}x_{1} − a_{1}x_{i}, …, a_{i}x_{n} − a_{n}x_{i}) for any i such that a_{i} ≠ 0. But obviously the matter becomes more complicated if we want the algebraic description of the vanishing ideal of a finite set of points. Let K be a field, and let 𝔸_{K}^{n} and ℙ_{K}^{n} denote respectively the n-dimensional affine and projective spaces over K. Then let 𝕏 := {P_{1}, …, P_{s}} be a finite set of s rational points, that is points having coordinates in the field K. Why are we interested in the defining ideal I(𝕏)? And how do we compute it?

We answer the first question by listing just a few examples we know of where ideals of points have been used in different fields of mathematics.

1) They encode fundamental properties of algebraic varieties of which they are linear sections (see for instance Geramita et al. (1993) and the references indicated there).

2) They are the basis for interpolation problems of numerical analysis (see Moeller (1998)).

3) They are used in coding theory (see Sakata (1998)).

4) They have been recently introduced into the realm of statistics, where finite sets of points are called designs and fractions (see Robbiano (1998)).

† Partially supported by the Consiglio Nazionale delle Ricerche (CNR)

  ‡ abbott,bigatti,robbiano@dima.unige.it   martin.kreuzer@mathematik.uni-regensburg.de

0747–7171/90/000000 + 00 $03.00/0 \begin{matrix}c \\ ◯ \end{matrix} 1999 Academic Press Limited

As to the second question, we observe that I(𝕏) = ⋂_{i=1}^{s} I(P_{i}), hence there is an obvious answer: it is possible to use a well-known byproduct of Buchberger’s Algorithm to compute the intersection. However, this approach is not efficient from the computational point of view and to remedy this an algorithm (called BM-algorithm) of low complexity was presented in Buchberger and Möller (1982); moreover, this algorithm has good performance (see for instance Marinari et al. (1993)). Several generalizations have since been proposed for instance to the cases of points with multiplicity, and of points described by differential conditions. A variant for determining a minimal set of generators in the projective case has been given in Cioffi (1998).

So what is left to do? The increasing demand for strong computational tools, in particular in statistics, pushed us to investigate the problem from several points of view.

First of all, previous complexity analyses referred to a model where the cost of operations in the base field is constant, but experience has shown that this is inappropriate, for instance, when the base field is ℚ. So the first achievement of this paper is a modular BM-algorithm, a variant of the classical one, where we use a modular technique to tame the problem of coefficient growth. Our analysis of complexity given in Section 4 takes into account the varying cost of field operations, and agrees with experimental evidence.

Another important matter we address is that of points in projective space. If 𝕏, the set of points, resides in projective space then the task of efficiently computing a Gröbner basis of I(𝕏) is more complicated. Let us see where the difficulties arise. Assume that the polynomial ring is K[x_{0}, …, x_{n}] and suppose that the hyperplane x_{0} = 0 does not meet 𝕏. Then it is well-known that we may proceed by considering the affine space given by x_{0} = 1. We compute a Gröbner basis G of the ideal corresponding to the affine image of 𝕏 with respect to some degree compatible term ordering, and then homogenize the elements of G to get a Gröbner basis of I(𝕏) with respect to a DegRevLex-type term ordering having x_{0} as smallest indeterminate. Now one has to use a variant of the FGLM-algorithm to obtain the Gröbner basis with respect to the desired term ordering.

But what happens if x_{0} = 0 meets 𝕏? The usual suggestion is to perform a suitable linear change of coordinates to achieve that property. Then compute a Gröbner basis as described above of the transformed points, and finally reconstruct the Gröbner basis for I(𝕏). This approach was studied in Marinari et al. (1993).

Greater care is needed if the projective space is over a finite field. In this case it is clear that a finite set of points can meet every hyperplane, so that no linear change of coordinates is available to do the trick. A way around this obstacle could be to consider a field extension K(α) of the base field K, work in K(α)[x_{0}, …, x_{n}], and then come back to K. This approach is clearly more demanding from the computational point of view.

These considerations suggest looking for a direct approach which avoids any change of coordinates. Indeed in Marinari et al. (1993) such a variant of the classical BM-algorithm was suggested. The main difficulty is that, unlike for the affine case, in the projective case ideals of points are one dimensional, so that there is a need of an efficient stopping criterion. Unfortunately the key Lemma 12.1 in their paper is flawed and admits counterexamples (e.g. see Example 3.7). Our Section 3 is entirely devoted to the discussion of the projective case. In particular we introduce a well behaved stopping criterion, which relies on combinatorial tools (see Theorem 3.10).

At this point the reader presumably wants to see some practical achievements of our work. All the algorithms described in this paper have been implemented in CoCoA 3.6 (available from http://cocoa.dima.unige.it). Some experimental data based on our implementations are reported in section 5.

In the paper we use repeatedly the notion of Gröbner basis. Needless to say this is now one of the main ingredients in Computational Algebra. The layout of the theory of Gröbner bases can be found in the original papers by Buchberger inserted in the bibliography.

2. A Modular Version of the Classical Buchberger-Möller Algorithm

Let us recall the classical version of the Buchberger-Möller Algorithm, as introduced in the paper Buchberger and Möller (1982). We are given a set of points 𝕏 = {P_{1}, …, P_{s}} in an n-dimensional affine space 𝔸^{n} over a field K via their coordinates, i.e. we have s tuples P_{i} = (p_{i1}, …, p_{in}) ∈ K^{n}. Our goal is to compute the ideal I of all polynomials in K[x_{1}, …, x_{n}] which vanish at all points of 𝕏.

Remark 2.1. Here we explain precisely what we mean by “row reduction” in a matrix. The most important aspect is that an ordering must be imposed on the columns of the matrix: the most natural is left-to-right, and by permuting the columns we may assume that this is indeed the chosen ordering. In a matrix M we say that a row whose first nonzero element occurs in column c is a reducer for column c; a zero row is not a reducer for any column. In Algorithm C below the matrix M is constructed so that every row is a reducer, and no column has more than one associated reducer. A row vector may then be reduced against M by repeatedly subtracting suitable multiples of the reducers in M to kill the first non-zero element in the vector. The process ends when the vector becomes zero or when there is no reducer in M for the column in which the first non-zero entry lies.

Algorithm C: Classical Buchberger-Möller Algorithm

Let K be a field, let n ≥ 1, let σ be a term ordering on the power products 𝕋^{n} of K[x_{1}, …, x_{n}], and let P_{i} = (p_{i1}, …, p_{in}) ∈ K^{n} for i = 1, …, s. Consider the following sequence of instructions.

C1 Start with empty lists G = [ ], Q = [ ], S = [ ], a list L = [1], and a matrix

M = (m_{ij}) over K, with s columns and initially zero rows. C2 If L = [ ], return the pair [G, Q] and stop. Otherwise, choose the power product

t = min_{σ}(L), the smallest according to the ordering σ. Delete t from L. C3 Compute the evaluation vector (t(P_{1}), …, t(P_{s})) ∈ K^{s}, and reduce it against the

rows of M to obtain

(v_{1}, …, v_{s}) = (t(P_{1}), …, t(P_{s})) − ∑_{i} a_{i}(m_{i1}, …, m_{is}) a_{i} ∈ K

C4 If (v_{1}, …, v_{s}) = (0, …, 0) then append the polynomial t − ∑_{i} a_{i}s_{i} to the list G, where s_{i} is the i^{th} element of S. Remove from L all multiples of t. Continue with step C2.

C5 If (v_{1}, …, v_{s}) ≠ (0, …, 0), then add (v_{1}, …, v_{s}) as a new row to M, and t−∑_{i} a_{i}s_{i} as a new element to S. Append the power product t to Q, and add to L those elements of {x_{1}t, …, x_{n}t} which are neither multiples of an element of L nor of LT_{σ}(G). Continue with step C2.

Theorem 2.2. Algorithm C stops after finitely many steps. It returns the reduced σ - Gröbner basis G of the ideal I of all polynomials vanishing on 𝕏 = {P_{1}, …, P_{s}}, and the list of power products Q whose residue classes form a K -basis of K[x_{1}, …, x_{n}]/I.

Proof. See Marinari et al. (1993). ⊓ ⊔

With only a slight change, Algorithm C can also yield the separators f_{i} of the points P_{i}, i.e. polynomials such that f_{i}(P_{i}) = 1 and f_{i}(P_{j}) = 0 whenever i ≠ j. To do this replace step C2 by the following:

C2 bis If L = [ ], reduce M to an identity matrix by row operations mimicking these row operations on the elements of S, and then return the triple [G, Q, S] and stop. Otherwise, choose the power product t = min_{σ}(L) and delete it from L.

Corollary 2.3. Algorithm C with step C2 bis additionally computes a set of separators for the points P_{i}; these separators are reduced with respect to the Gröbner basis G.

Proof. Observe that throughout Algorithm C the matrix M and list S are related as follows: row i of M is just (s_{i}(P_{1}), s_{i}(P_{2}), …, s_{i}(P_{s})) where s_{i} is the i^{th} element of the list S. Moreover, the last time step C2 bis is entered M is a non-singular s × s matrix. The linear combinations of the rows of M yielding the identity matrix clearly also convert the elements of S into separators. ⊓ ⊔

Conceptually, Algorithm C can be split into two principal tasks: determining the quotient basis Q (and implicitly LT (G)), and then computing G from LT (G) by linear algebra.

Algorithm C works well when the field K is finite but is less well-suited to the case K = ℚ where growth of the entries of M becomes a problem. For this reason we present a modular version of the algorithm: a commonly used paradigm for avoiding intermediate expression swell. Before describing the algorithm we recall some useful facts.

The Chinese Remainder Algorithm (CRA) converts a collection of residue-modulus pairs {r_{i} mod p_{i} : i = 1, 2, …, e} into a single number R such that R ≡ r_{i} (mod p_{i}) for all i provided the moduli p_{i} are pairwise coprime. R is determined uniquely modulo ∏_{1}^{e} p_{i}. In particular, if the r_{i} are known to be the residues of some integer bounded in absolute value by B then the integer value can be determined trivially from R provided ∏_{1}^{e} p_{i} > 2B.

A rational number can also be recovered from its image modulo a sufficiently large modulus. There are two ways to do this. If we can compute a multiple of its denominator then we can clear the denominator and find the integral numerator as above. Otherwise, if no (reasonable) multiple of the denominator is known then we can use the rational recovery algorithm of Wang et al. (1982) which was later refined in Collins and Encarnación (1995). Applying either of these approaches when the modulus is not big enough will produce some “meaningless” rational number (or a warning that no suitable rational exists).

The question of how many primes to use can be resolved in two ways: determine a priori bounds on the numerators and denominators and then deduce how many primes to use, or speculatively recover the rationals after including information from each prime and check whether the result is correct. The second approach is useful when no good bound is available and the result can easily be checked for correctness; this is the method we use.

Remark 2.4. The main loop of the algorithm has repeatedly to select a new prime p for the modular computation, but the prime has to be suitable. The conditions p is to satisfy are:

1) p must be different from the primes chosen so far;

2) the coordinates of the points P_{1}, …, P_{s} should have reductions modulo p, i.e. the prime p must not divide any of their denominators;

3) the reductions \overline{P}_{1}, …, \overline{P}_{s} ∈ 𝔽_{p}^{n} should be pairwise distinct points.

Algorithm M: Modular Version of the Buchberger-Möller Algorithm

Let n ≥ 1, let σ be a term ordering on 𝕋^{n}, and let P_{i} = (p_{i1}, …, p_{in}) ∈ ℚ^{n} for i = 1, …, s. Consider the following sequence of instructions.

M1 Let Q = [ ], G = [ ] and G_{m} = [ ] be empty lists, and let m = 1. M2 Pick a new prime number p (see Remark 2.4). M3 Apply Algorithm C (the classical Buchberger-Möller Algorithm) to K = 𝔽_{p} and the

set of points \{\overline{P}_{1}, …, \overline{P}_{s}\}, where \overline{P}_{i} = (p̄_{i1}, …, p̄_{in}) ∈ 𝔽_{p}^{n} is the reduction of P_{i}.

Denote the result by [G_{p}, Q_{p}].

M4 Compare Q_{p} with Q (see Remark 2.5). If Q is better than Q_{p} then continue with step M2. 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 M2.

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

M6 If G′ ≠ G then replace G by G′ and continue with step M2. M7 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 M2. Otherwise return [G, Q] and stop.

Remark 2.5. The list Q constructed by Algorithm C is generated in increasing order with respect to σ, and always contains exactly s power products at the end of the algorithm. If we have two such lists Q = [q_{1}, q_{2}, …] and Q′ = [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}. The idea behind this definition is that the only way for the computation modulo p to go wrong is to obtain a zero vector after the reduction in step C3 when the same computation over K = ℚ would not have found a zero vector at that point, and in this case the corresponding power product t is missing from Q_{p}. We justify this idea in Lemma 2.6.

Lemma 2.6. Let P_{1}, …, P_{s} ∈ ℚ^{n} be distinct points. Let G be the Gröbner basis produced by applying Algorithm C over the field ℚ to these points, and let D be the determinant of the matrix M just before the algorithm terminated. Let p be a prime which does not divide any denominator appearing in the points, and let G_{p} be the Gröbner basis produced by applying Algorithm C over the field 𝔽_{p} to the modular reductions of the points. Then G ≡ G_{p} mod p if and only if D ≢ 0 mod p.

Proof. First we claim that p cannot divide the (minimal) denominator of D. Consider the computation over ℚ. The matrix M built up during Algorithm C is just a triangularization of the matrix E whose rows are the evaluation vectors of the quotient basis; moreover the reduction to triangular form is achieved via a unimodular matrix. So det(M) = ± det(E), and by clearing denominators in the rows of E we see that p does not divide the (minimal) denominator of det(E), thus proving the claim. Note that in the special case where P_{1}, …, P_{s} ∈ ℤ^{n} we have D ∈ ℤ.

Furthermore, by Cramer’s rule we see that the solution \underline{x} to any linear system M\underline{x} = \underline{b} has least common denominator not divisibile by p whenever the least common denominator of \underline{b} is not divisibile by p. This implies that p does not divide the least common denominator of any element of G (nor of any separator).

First we show that LT (G) = LT (G_{p}) if and only if D ≢ 0 mod p. Now LT (G) = LT (G_{p}) if and only if Q = Q_{p} where Q are Q_{p} are the respective quotient bases since Q uniquely determines LT (G) and vice versa. Now, Q and Q_{p} will differ only if the reduction in step C3 produces a zero vector modulo p where a non-zero vector was obtained over ℚ, and this implies that modulo p there is a linear dependency amongst the rows of M, i.e. D ≡ 0 mod p.

Now we show that LT (G) = LT (G_{p}) if and only if G ≡ G_{p} mod p. Since the elements of G and G_{p} are monic, the reverse implication is trivial. So suppose that LT (G) = LT (G_{p}). Then necessarily Q = Q_{p}, and G is obtained from LT (G) by representing the evaluation vectors of each element of LT (G) as a linear combination of the rows of E. G_{p} is obtained analogously. Now we have just seen that each element of G can be reduced modulo p. This gives a representation modulo p of the evaluation vector of some element of LT (G) as a linear combination of the rows of E_{p} (the matrix whose rows are the evaluation vectors modulo p of the quotient basis), but E_{p} is invertible modulo p, so the representation is unique, and thus coincides with an element of G_{p}. ⊓ ⊔

Theorem 2.7. Algorithm M stops after finitely many steps. It returns the reduced σ - Gröbner basis G of the vanishing ideal I of 𝕏 = {P_{1}, …, P_{s}} and a list of power products Q whose residue classes form a K -basis of K[x_{1}, …, x_{n}]/I.

Proof. We shall prove termination and correctness together. Let [G^{∗}, Q^{∗}] denote the result Algorithm C would have produced given the same input, and let M^{∗} be the final value of the matrix used there (but not returned).

In step M3 we can have Q_{p} ≠ Q^{∗} only finitely many times since by Lemma 2.6 it implies that p divides det(M^{∗}). Furthermore, once a prime has been found for which Q_{p} = Q^{∗} then in Algorithm M we will have Q = Q^{∗} ever after.

Algorithm M cannot return with Q^{∗} ≠ Q. For suppose we manage to reach step M7 with Q^{∗} ≠ Q. Then G contains an element, g, with leading term outside LT(G^{∗}), hence g itself lies outside the ideal generated by G^{∗}, and consequently the verification will fail. So we will eventually pick a prime p with Q_{p} = Q^{∗}.

Now assume that Q^{∗} = Q. Any prime for which Q_{p} ≠ Q^{∗} will be discarded by step M4; so assume also that Q_{p} = Q^{∗}. By Lemma 2.6 we must also have G ≡ G_{p} mod p. Hence once we have Q = Q^{∗}, then G_{m} in step M5 will be the reduction modulo m of G, and so for sufficiently large m the rational recovery will yield G, at which point the verification in step M7 will succeed. ⊓ ⊔ Corollary 2.8. Algorithm M can easily be adapted to compute the separators as well (using the variant of Algorithm C).

Proof. Note that the final verification in step M7 must check the values at each point of both the Gröbner basis elements and the separators.

Recall that the separators are obtained by representing the vectors (1, 0, 0, 0, …), (0, 1, 0, 0, …), etc., as linear combinations of the evaluation vectors of the quotient basis. Now it is easy to extend the proof of Theorem 2.7. ⊓ ⊔

3. Computing the Ideal of Points in Projective Spaces

Here we describe the direct approach, as promised in the introduction. In the affine case, the ideal of a set of points is 0-dimensional, and hence the algorithm works on a finite set of power products. In the projective case, the ideal of a set of points is 1dimensional, so we do not have an “obvious” way to deduce when the computation of the Gröbner basis is completed.

The first step towards a stopping criterion comes from the theory of Hilbert functions of sets of points in ℙ^{n}. We recall some definitions and results (see Mora and Robbiano (1993) and Geramita et al. (1993)).

Definition 3.1. Let A = K[x_{0}, …, x_{n}], let I be a homogeneous ideal in A. The Hilbert function of A/I is defined as H_{A/I} : ℕ ⟶ ℕ with H_{A/I}(d) = dim_{K}(A/I)_{d}.

Theorem 3.2. (Hilbert Function) Let 𝕏 = {P_{1}, …, P_{s}} be a set of K -rational points in ℙ_{K}^{n}, and let I ⊆ A = K[x_{0}, …, x_{n}] be the homogeneous vanishing ideal of 𝕏.

1) There exists a ≥ −1 such that H_{A/I}(d) < H_{A/I}(d+1) for all d ≤ a, and H_{A/I}(d) = s for all d > a. In particular, since H_{A/I}(0) = 1, he have H_{A/I}(d) = s for all d ≥ s − 1.

2) For any term ordering σ on A we have H_{A/I} = H_{A/ LT_{σ}(I)} .

Definition 3.3. For 𝕏 = {P_{1}, …, P_{s}} a set of K -rational points in ℙ_{K}^{n}, we define a_{𝕏} to be the integer a of Theorem 3.2.

In the following proposition we use a term ordering σ of x_{0} -DegRevLex type, meaning a degree compatible term ordering σ such that if t, t′ ∈ 𝕋^{n+1} , deg(t) = deg(t′), x_{0} does not divide t, and x_{0} divides t′, then t >_{σ} t′. Consequently, for a term ordering of x_{0} -DegRevLex type, if x_{0} | LT_{σ}(f), then x_{0} | f.

Proposition 3.4. (Simple Stopping Criterion) Let 𝕏 ⊆ ℙ_{K}^{n} be a set of K -rational points with homogeneous vanishing ideal I ⊆ A = K[x_{0}, …, x_{n}]. Suppose that the hyperplane H = Z(x_{0}) contains no point of 𝕏, and that the term ordering σ is of x_{0} -DegRevLex type. Then the leading term ideal LT_{σ}(I) is generated in degrees ≤ a_{𝕏} + 2.

Proof. First we show that there is an isomorphism (A/ LT_{σ}(I))_{a_{𝕏}+1} → (A/ LT_{σ}(I))_{a_{𝕏}+2} defined by the multiplication by x_{0} . This follows from the fact that the two vector spaces have the same dimension and x_{0} is not a zero-divisor modulo LT_{σ}(I), as we have remarked above. Now the proof of the proposition proceeds in the usual way. If f ∈ LT_{σ}(I)_{a_{𝕏}+3} , we can write f = ∑_{i=0}^{n} x_{i}f_{i} with f_{0}, …, f_{n} ∈ A_{a_{𝕏}+2} . By what we just saw, we can write f_{i} = x_{0}g_{i} + h_{i} with g_{i} ∈ A_{a_{𝕏}+1} and h_{i} ∈ LT_{σ}(I)_{a_{𝕏}+2} . Then f = x_{0} ∑_{i=0}^{n} x_{i}g_{i} + ∑_{i=0}^{n} x_{i}h_{i} implies x_{0} ∑_{i=0}^{n} x_{i}g_{i} ∈ LT_{σ}(I)_{a_{𝕏}+3} , and therefore ∑_{i=0}^{n} x_{i}g_{i} ∈ LT_{σ}(I)_{a_{𝕏}+2} . Altogether, f ∈ A_{1} LT_{σ}(I)_{a_{𝕏}+2} proves the claim. ⊓ ⊔

Our next examples show that this stopping criterion fails in general.

Example 3.5. Consider the set of 6 points 𝕏 = {(0, 2, 5), (0, 1, 2), (1, 3, 1), (4, 3, 4), (2, 5, 4), (1, 4, 4)} in ℙ_{ℚ}^{2} . The values of its Hilbert function are 1, 3, 6, 6, . . .. Hence a_{𝕏} = 1, there are separators for all 6 points in degree d for each d ≥ 2, and I is generated in degrees ≤ 3. However, if σ = DegRevLex, the leading term ideal of I is (xyz, xz^{2}, yz^{2}, z^{3}, xy^{3}). Thus there is one Gröbner basis elements in degree 4 > a_{𝕏} + 2. This failure depends on the fact that x_{0} divides zero modulo I. Indeed two points are on the line x_{0} = 0.

Example 3.6. Consider the set of 5 points 𝕏 = {(4, 1, 1), (5, 2, −1), (85, 4, 1), (455, 8, −1), (4369, 16, 1)} in ℙ_{ℚ}^{2} . The values of its Hilbert functions are 1, 3, 5, 5, . . .. Thus a_{𝕏} = 1 again, but using σ = DegLex we conclude from LT_{σ}(I) = (x^{2}, xz^{2}, xy^{2}, y^{5}) that there is an element in the reduced σ -Gröbner basis of I of degree 5. This failure depends on the fact that σ is not of x_{0} -DegRevLex type.

The example below shows that during the execution of the algorithm the fact that the Hilbert function attains its maximum in some degree does not imply that the Gröbner basis is complete (or nearly complete). In particular it shows that the key Lemma 12.1 of Marinari et al. (1993) is incorrect.

Example 3.7. Consider the set of 15 points 𝕏 = {(n, m, 1)}_{n,m∈{−1,0,1,2}} \ {(2, 2, 1)} in ℙ_{ℚ}^{2} . The values of its Hilbert function are 1, 3, 6, 10, 13, 15, 15, . . .. We have that H(5) = 15, there is no generator of LT_{DegRevLex}(I) in degree 5, and the generators of degree < 5 generate an ideal of dimension 1 (projective dimension 0). But there is another generator of the ideal in degree 6. In fact, the ideal I is minimally generated by {y^{4} −2y^{3}z −y^{2}z^{2} + 2yz^{3}, x^{4} − 2x^{3}z − x^{2}z^{2} + 2xz^{3}, x^{3}y^{3} − x^{3}yz^{2} − xy^{3}z^{2} + xyz^{4}}.

So we need some better tool in order to construct an efficient stopping criterion.

Definition 3.8. Let 𝕋_{d}^{n+1} be the set of power products in K[x_{0}, …, x_{n}] of degree d. Two power products t, t′ are called connected in Q ⊆ 𝕋_{d}^{n+1} 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 i = 1, …, r there exist α, β ∈ \{0, …, n\} such that t_{i} = \frac{t_{i−1}·x_{α}}{x_{β}} . The intuitive meaning of this notion is that one can pass from one power product in the sequence to the next by replacing one indeterminate by another one.

We can speak of connected components in Q which are clearly disjoint. A connected component of a power product t is empty if t ∉ Q.

For example, in ℚ[x, y, z], let Q := {x^{3}, x^{2}z, xz^{2}, yz^{2}, y^{3}}. In Q we have that x^{3} is connected to yz^{2} , a sequence is x^{3}, x^{2}z, xz^{2}, yz^{2} . The power product y^{3} is connected only to itself.

Lemma 3.9. (Disconnection Lemma) Let J be a monomial ideal in A := K[x_{0}, …, x_{n}] and Q_{δ} := 𝕋_{δ}^{n+1} \ J_{δ} for every δ ∈ ℕ. Suppose that there exists d ∈ ℕ such that:

1) H_{A/J}(d) = s, i.e. |Q_{d}| = s;

2) for all i ∈ {0, 1, …, n}, every power product in the connected component of x_{i}^{d} in Q_{d} is divisible by x_{i};

3) H_{A/J}(δ) ≥ s for all δ ≥ d. Then H_{A/J}(δ) = s for all δ ≥ d.

Proof. Let C_{i} be the connected component of x_{i}^{d} in Q_{d}. It is empty only if x_{i}^{δ} ∈ J. By hypothesis (2) these components are distinct, hence disjoint, therefore ∑_{i=0}^{n} |C_{i}| ≤ s.

First we prove that (1) and (2) imply Q_{δ} ⊆ ⋃_{i=0}^{n} x_{i}^{δ−d}C_{i} for all δ ≫ d:

Let J′ be the ideal generated by J_{d} ∪ C_{0} ∪ ⋯ ∪ C_{n}. Obviously J′ contains all x_{i}^{d}, hence J′_{δ} = 𝕋_{δ}^{n+1} for all δ ≫ d (in particular for all δ ≥ (n + 1)d).

Now we prove that for each i we have {x_{0}, …, x_{n}}·C_{i} ⊆ J ∪ x_{i}C_{i}. Namely, if t ∈ C_{i}, then t′ = \frac{t·x_{j}}{x_{i}} is either in J or in C_{i}, being connected to t in Q_{d}. From this we have x_{j} · t = x_{i} · t′ ∈ J ∪ x_{i}C_{i}.

Therefore J′_{d+1} = J_{d+1}∪(⋃_{i}{x_{0}, …, x_{n}}C_{i}) equals J_{d+1}∪(⋃_{i} x_{i}C_{i}), and by induction it easily follows that J′_{δ} = J_{δ} ∪ (⋃_{i} x_{i}^{δ−d}C_{i}) for all δ ≥ d. This means that Q_{δ}, the complement of J_{δ}, is all contained in ⋃_{i} x_{i}^{δ−d}C_{i} for all δ ≫ d.

Now we prove that |Q_{δ}| = s for all δ ≥ d:

Let δ̄ ≫ d. From what we have proved and hypothesis (3) it follows ∑_{i=0}^{n} |C_{i}| ≥ |Qδ̄| ≥ s and therefore ∑_{i=0}^{n} |C_{i}| = s, which implies Q_{d} = ⋃_{i=0}^{n} C_{i}. Thus J′_{d} = 𝕋_{d}^{n+1} and then J′_{δ} = 𝕋_{δ}^{n+1} for all δ ≥ d, hence Q_{δ} ⊆ ⋃_{i=0}^{n} x_{i}^{δ−d}C_{i} for all δ ≥ d.

This and hypothesis (3) imply |Q_{δ}| = s for all δ ≥ d, which is exacly what we wanted to prove. ⊓ ⊔

Theorem 3.10. (Stopping criterion) Let 𝕏 be a set of K -rational points in ℙ_{K}^{n}, let I be the homogeneous vanishing ideal of 𝕏, and let σ be a term ordering on A = K[x_{0}, …, x_{n}]. Assume that there exists d such that

1) H_{A/ LT_{σ}(I)}(d) equals the number of points in 𝕏,

2) for all i, every power product in the connected component of x_{i}^{d} in 𝕋_{d}^{n+1} \ LT_{σ}(I)

is divisible by x_{i}. Then the elements of the reduced σ -Gröbner basis of I have degrees ≤ d.

Proof. Let s be the number of points in 𝕏 and let J be the ideal generated by the leading power products of the elements of the reduced σ -Gröbner basis of I of degree ≤ d. We want to prove J = LT_{σ}(I).

Applying Theorem 3.2 to our hypothesis, we have

H_{A/J}(δ) ≥ H_{A/ LT_{σ}(I)}(δ) = H_{A/I}(δ) = s for all δ ≥ d

Hence, by Lemma 3.9, we have H_{A/J}(δ) = s = H_{A/I}(δ) for all δ ≥ d and then H_{A/J}(δ) = H_{A/ LT_{σ}(I)}(δ) for all δ ∈ ℕ. This and the fact that J ⊆ LT_{σ}(I) imply J = LT_{σ}(I). ⊓ ⊔

Based on this theorem we define the function StoppingCriterion(Q) which returns “TRUE” only if Q contains s elements of maximal degree d and the connected components of every x_{i}^{d} in Q satisfy condition (2).

Algorithm CP: Projective Version of the Classical Buchberger-Möller Algorithm

Let K be a field, let n ≥ 1, let σ be a term ordering on the monoid 𝕋^{n+1} of power products of K[x_{0}, …, x_{n}], and let P_{i} = (p_{i0} : …: p_{in}) ∈ ℙ^{n}(K) for i = 1, …, s. Consider the following sequence of instructions.

CP1 Start with empty lists G = [ ], Q = [ ], S = [ ], a list L = [1], a matrix M = (m_{ij})

over K with s columns and initially zero rows, and with d = 0. CP2 If the function StoppingCriterion(Q) defined above yields TRUE then return the

pair [G, Q] and stop. Otherwise increase d by one, reset M to be a matrix over K with zero rows and s columns, reset Q = [ ], and let L be the list of all power products of degree d which are not multiples of a leading power product (w.r.t. σ) of an element of G.

CP3 If L is empty, go to step CP2; otherwise choose the power product t = min_{σ}(L)

and remove it from L. CP4 Compute the evaluation vector (t(P_{1}), …, t(P_{s})) ∈ K^{s}, and reduce it against the

rows of M, to obtain

(v_{1}, …, v_{s}) = (t(P_{1}), …, t(P_{s})) − ∑_{i} a_{i}(m_{i1}, …, m_{is}) a_{i} ∈ K

CP5 If (v_{1}, …, v_{s}) = (0, …, 0) then append the polynomial t − ∑_{i} a_{i}s_{i} to the list G,

where s_{i} is the i^{th} element of the list S. Continue with step CP3. CP6 If (v_{1}, …, v_{s}) ≠ (0, …, 0) then add (v_{1}, …, v_{s}) as a new row to M and t−∑_{i} a_{i}s_{i}

as a new element to S. Append the power product t to Q. Continue with step CP3.

Remark 3.11. The value Q returned by Algorithm CP is normally of little utility; we return it only to simplify the enunciation of Algorithm MP (below).

Theorem 3.12. Algorithm CP stops after finitely many steps and returns the reduced σ -Gröbner basis G of the homogeneous vanishing ideal I of 𝕏 = {P_{1}, …, P_{s}}.

Proof. First we show finiteness of the algorithm: in particular we prove that the algorithm never goes beyond degree s. From the construction it is clear that the number of power products in the list Q at the end of processing some degree d is just H_{A/I}(d). From Theorem 3.2.1 we have that H_{A/I}(d) = s for all degrees d ≥ s − 1. Let us consider the case d = s. We have seen that there are precisely s power products of degree s in Q, that is condition (1) of the stopping criterion. Also condition (2) is satisfied: If a power product t is connected to x_{i}^{s} in Q, we have x_{i} | t, since otherwise any connection between x_{i}^{s} and t would pass through at least one power product exactly divided by x_{i}^{j} for every j = 0, … s, hence through at least s + 1 power products in Q. Hence the Stopping Criterion applies.

To show correctness we prove that LT_{σ}(I) is generated by LT_{σ}(G). Consider the end of step CP2. The new list L contains all power products of degree d which are not in the ideal generated by LT_{σ}(G). Since by construction all elements of G vanish on 𝕏, we have G ⊆ I, hence LT_{σ}(G) ⊆ LT_{σ}(I). We have already remarked that the number of power products in the list Q at the end of processing some degree d is just H_{A/I}(d). Therefore H_{A/(LT_{σ}(G))} = H_{A/I}. This implies that H_{A/(LT_{σ}(G))} = H_{A/ LT_{σ}(I)} , which, together with LT_{σ}(G) ⊆ LT_{σ}(I), yields the desired conclusion. ⊓ ⊔

The following example shows that the stopping criterion is not always optimal.

Example 3.13. Consider the set of points 𝕏 = {(1, 1, 1), (0, 1, 1), (0, 1, 0), (1, 1, 0)} in ℙ_{ℚ}^{2} . The leading term ideal w.r.t. σ = DegRevLex of its homogeneous vanishing ideal I is LT_{σ}(I) = (yz, x^{2}). In degree 2, the stopping criterion is not satisfied, because z^{2} is connected to xy via [z^{2}, xz, xy]. In degree 3, the stopping criterion is satisfied, but there is no new σ -Gröbner basis element in that degree.

Definition 3.14. Let A = K[x_{0}, …, x_{n}], let I be a homogeneous ideal in A, and let 𝕏 = {P_{1}, …, P_{s}} ⊆ ℙ^{n}(K) be a set of K -rational points. A homogeneous polynomial f ∈ A is called a separator of P_{i}, if f(P_{i}) ≠ 0 and f(P_{j}) = 0 for j ≠ i. A separator of minimal degree is also called a minimal separator.

Remark 3.15. As earlier for Algorithm C we may easily adapt Algorithm CP to compute separators. The initial value for d in step CP1 should be −1 to handle correctly the case of just a single input point. In step CP6 we must additionally use the newly added row to bring M into reduced row echelon form. Then in step CP2 once the stopping criterion has been fulfilled we obtain the separators as a subset of the list S: if row i in M contains exactly one non-zero entry, in column j say, then s_{i} is a separator for the point P_{j}; if there are several separators for the same point, we take the one of lowest degree. In this way we get minimal separators.

Algorithm MP: Modular Version of the Projective Buchberger-Möller Algorithm

This is identical to Algorithm M except that it calls Algorithm CP in step MP3 where Algorithm C was called in step M3.

Theorem 3.16. Algorithm MP stops after finitely many steps. It returns the reduced σ -Gröbner basis G of the vanishing ideal I of 𝕏 = {P_{1}, …, P_{s}}.

Proof. This is entirely analogous to the proof of Theorem 2.7. ⊓ ⊔

Corollary 3.17. Algorithm MP can be adapted to compute the separators as well (using the variant of Algorithm CP described in Remark 3.15).

Proof. The adaptation is straightforward, as for Algorithm M, except for two points which do not arise in the affine case. The projective separators are defined only up to multiplication by a non-zero field element. So that the separators can be recovered from their modular images we must eliminate this ambiguity: we do this by scaling the separators so that they evaluate to 1 at their own points.

The other matter is that of recognising “bad” separators. It is possible that the minimal separator modulo p of some point has lower degree than the minimal separator over ℚ. In such a case the “false modular image” must be discarded as it would otherwise inhibit recovery of the separators over ℚ. One wasteful approach is to compare the degrees of the separators for the “current prime” with the degrees of the separators built up by Chinese Remaindering: if some separator modulo p has degree lower than the corresponding lifted separator then discard all information from that prime; otherwise if some separator modulo p has degree higher than the corresponding lifted separator then discard all lifted values and start anew from the current prime. Other less wasteful approaches can be used instead. ⊓ ⊔

4. Complexity Issues

In this section we determine a worst case complexity for Algorithm M to compute both the separators of the points and the Gröbner basis for their ideal. We also determine the complexity for “generic” points with the term ordering DegRevLex; by “generic” we mean random points whose behaviour is as that of true generic points.

As in the paper Marinari et al. (1993) the parameters we shall use to express the complexity are:

s the number of points; n the number of variables (i.e. the dimension of the ambient affine space); g the number of elements in the Gröbner basis.

Our Algorithm C is the same as algorithm 1 presented in section 5 of that paper. We recall the result of their analysis which showed that the complexity of applying Algorithm C with K = 𝔽_{p} is O(s^{2}(g + s)(log p)^{2} + s^{2}n^{2}) where the cost of an arithmetic operation in 𝔽_{p} is O((log p)^{2}). Our result is encapsulated in the following theorem.

Theorem 4.1. For the case K = ℚ, where all points have integral coordinates, and assuming that the largest coordinate X satisfies log(X) ∈ O(log s), i.e. X is bounded by some polynomial in s, then Algorithm M has worst case bit complexity

O(s^{4}(g + s)(log s)^{2} + s^{4}n^{2})

Furthermore, for “generic” points with the DegRevLex ordering, Algorithm M has bit complexity

O(s^{2}d(g + s)(log s)^{2} + s^{2}dn^{2})

where d is such that \binom{n+d−1}{d} = s + g; this is better than the worst case complexity by a factor of s/d.

Proof. We start by estimating how many bad primes we could encounter. Consider the s × s matrix, M, whose columns are indexed by the points in 𝕏 and whose rows are indexed by the power products in the basis of the quotient R/I; the entries being the value of the power product at the point. By definition this matrix is non-singular; moreover, by Lemma 2.6 a prime is “bad” if and only if it divides det(M). Now we estimate the greatest possible value for this determinant using Hadamard’s bound on the rows. In any row corresponding to a power product of total degree d no entry can exceed X^{d} in absolute value. Using d_{1}, d_{2}, …, d_{s} to denote the degrees of the power products for the rows in our matrix, we see that Hadamard’s bound does not exceed X^{D}\sqrt{s^{s}} where D = d_{1} + ⋯ + d_{s}. Since our quotient basis contains every factor of every element of the basis, we deduce that D ≤ 1 + 2 + ⋯ + s = s(s + 1)/2. This worst case is realised with generic points and the Lex ordering; in contrast, generic points with the DegRevLex ordering will typically give a much smaller exponent of D = sd where d is the highest degree of a Gröbner basis element. Here we note that the logarithm of Hadamard’s bound in the worst case is: O(s^{2} log X + s log s).

For any positive integer r the product of the first r primes clearly exceeds r!, and this we can estimate using Stirling’s asymptotic approximation: log(r!) = r log r − r + o(r).

Whence we see that the number of bad primes is O(s^{2}); in practice it appears that bad primes are typically fairly uncommon.

Next we find out how many good primes we need to be able to reconstruct the answer. To do this we must estimate the sizes of every coefficient of every separator and Gröbner basis element. Again we use the matrix M from above, and shall apply Cramer’s rule for obtaining the solutions to a linear system since our coefficients effectively arise from solving linear systems. It is immediate that the determinant of M is a common denominator for both separators and Gröbner basis elements. Hadamard’s bound applied to the numerators given by Cramer’s rule shows that no numerator exceeds X^{s+1} det(M). From this we see that the logarithm of the product of the good primes may have to become as large as O(s^{2} log X + s log s) in the worst case. Thus the total number of primes, both good and bad, which could be necessary is O(s^{2}) — experiments suggest that random points in 𝔸^{2} with coordinates in the range [−2s^{2}, 2s^{2}] achieve this complexity. The situation is far more favourable for generic points with DegRevLex ordering: the same reasoning shows that the total number of primes needed is only O(sd).

So we call Algorithm C up to O(s^{2}) times at a total cost of O(s^{4}(g +s)(log s)^{2} +s^{4}n^{2}) where the factor of (log s)^{2} allows for the fact that an arithmetic operation modulo an sbit prime costs O((log s)^{2}). Following the same line of reasoning we can also deduce that for generic points using DegRevLex ordering the total cost of the calls to Algorithm C is O(s^{2}d(g + s)(log s)^{2} + s^{2}dn^{2}).

We comment that the cost of the calls to Algorithm C is at least that of of Chinese Remaindering and verification combined. Combining O(s^{2}) modular values (each of size O(log s)) into a single value using iterative Chinese Remaindering costs O(s^{3}(log s)^{2}), and we must do this for s(s + g) coefficients, giving a total cost of O(s^{4}(g + s)(log s)^{2}). Verifying the answer by evaluation costs no more than O(s^{4}g(log s)^{2}): the s power products can each be evaluated at the s points once only at a total cost of O(s^{4} log s), and then each polynomial in the Gröbner basis has no more than s + 1 terms and can be evaluated in time O(s^{4}(log s)^{2}). It can similarly be shown that, in the case of generic points with the DegRevLex ordering, the overall complexity is the same as that of the calls to Algorithm C. ⊓ ⊔

Now we determine the complexity for Algorithm MP (for the field ℚ). We continue to use the same parameters but observe that now n is one greater than the dimension of the ambient projective space. Following the reasoning in Marinari et al. (1993) we find the worst case complexity of Algorithm CP running over the field K = 𝔽_{p} to be

O(s(n + s)(g + s^{2})(log s)^{2} + s^{2}n^{2} log(ns))

where again we have assumed that each arithmetic operation in 𝔽_{p} costs O((log p)^{2}). Superficially this formula appears different from the one they published. Our result for Algorithm MP is encapsulated in the following theorem.

Theorem 4.2. For the case K = ℚ, where all points have integral coordinates, and assuming that the largest coordinate X satisfies log(X) ∈ O(log s), i.e. X is bounded by some polynomial in s, then Algorithm MP has worst case bit complexity

O(s^{4}(n + s)(g + s^{2})(log s)^{2} + s^{5}n^{2} log(ns))

Furthermore, for “generic” points with the DegRevLex ordering, Algorithm MP has bit complexity

O(s^{2}d(n + s)(g + sd)(log s)^{2} + s^{3}dn^{2} log(ns))

where d is such that \binom{n+d−1}{d} = s + g; this is better than the worst case complexity by a factor of about s^{2}/d.

Proof. This proof is largely analogous to that of Theorem 4.1. In place of the single matrix M considered in that proof we must consider several matrices M_{1}, M_{2}, … M_{d} where the rows of M_{r} are indexed by those power products of degree r..... Since we never need to go beyond degree s we have that d ≤ s. Each of these matrices is, by definition, of full rank, and a prime is “bad” if and only if at least one M_{r} is no longer of full rank modulo p; i.e. p divides the determinant of every maximal minor of at least one M_{r}. Hadamard’s bound for the determinant of a maximal minor of M_{r} gives X^{r^{2}} \sqrt{r^{r}}. Thus all bad primes must divide a number of size not exceeding log ∏_{r=1}^{s}(X^{r^{2}} \sqrt{r^{r}}) ∈ O(s^{3} log X +s^{2} log s). Whence there can be at most s^{3} bad primes.

The maximum number of “good” primes we could ever need remains O(s^{2}) since we never need to go beyond degree s: we have to consider solving linear systems corresponding to the matrices M_{1}, M_{2}, … M_{d}, and arguing as previously Cramer’s Rule and Hadamard’s bound prove that the logarithm of the product of the good primes need never exceed O(s^{2} log X + s log s) in the worst case.

The argument that the cost of the main loop dominates remains valid for this case. Since we may have to execute the main loop up to O(s^{3}) times the overall complexity is just s^{3} times the complexity of the call to Algorithm CP.

We note that the case of generic points with the DegRevLex ordering permits a much more favourable analysis. All elements of the Gröbner basis have degree d−1 or d (where d ∈ O(log(s)/ log(n))). We shall show that a prime p is “bad” if and only if at least one of M_{d−2} , M_{d−1} or M_{d} is not of full rank modulo p; as in the proof of Theorem 4.1 we can now deduce that the total number of primes to be tried is O(sd), and thus the complexity in this case is just sd times the complexity of a call to Algorithm CP, i.e. O(s(n + s)(g + s^{2})(log s)^{2} + s^{2}n^{2} log(ns)).

Now we prove that to characterize “bad” primes it suffices to consider only the three matrices M_{d−2} , M_{d−1} and M_{d}. Let p be a “bad” prime for which the matrix M_{r} does not have full rank for some r < d − 2. This implies that there is a polynomial f of degree r which vanishes (modulo p) at every point of 𝕏. Now consider the polynomial x^{d−r−2}f; this has degree d−2 and clearly vanishes (modulo p) at every point of 𝕏. But the rows of M_{d−2} are indexed by all power products of degree d − 2, hence there is a non-trivial linear combination of the rows of M_{d−2} ; i.e. the rank of M_{d−2} is not full. ⊓ ⊔

Remark 4.3. Our proof suggests that we could waste a large proportion of computation time encountering “bad” primes. In numerous actual computations we have never seen an example where the number of “bad” primes encountered exceeded the number of “good” ones, but with the DegLex ordering we have observed as many as 20% of all primes being “bad”. The matrices M_{i} in the proof are far from independent, and it could be that our estimate of the number of “bad” primes is too crude.

5. Implementation Issues and Timings

Algorithm M as described admits a number of implementation refinements. For instance, at step M4 the comparison of the lists Q and Q_{p} can be effected inside Algorithm C as the list is generated; Algorithm C can also terminate prematurely if a worse Q is being generated.

The rational recovery and stability checks at steps M5 and M6 need only monitor a single coefficient most of the time, though eventually the full answer will be needed. It also is possible to try both rational recovery techniques until one of them yields a stable answer; this is what our implementation does.

The verification in step M7 need not actually evaluate any polynomials: we represent a polynomial with rational coefficients as f/D where D is the least common denominator, and f has integer coefficients; we know the polynomials are correct modulo m, so it suffices to verify that |f(P_{i})| < m for each point P_{i}, and this can be done quickly and easily (e.g. by bounding each term separately and summing these). This cheap verification test may require O(s) further iterations of the main loop, after the correct answer has been found, before it is able to succeed; in practice it works well.

These refinements remain applicable even when the separators are computed.

The following tables give the timings for the computation of the ideal of distinct random points, computed on a Digital Alpha, 192Mb RAM, 433 Mhz, compiled with gcc -O2.

DegRevLex  𝔸^{10}  𝔸^{20}  𝔸^{40}  ℙ^{9}  ℙ^{19}  ℙ^{39}  ℙ^{39}
40 small  0.3 s  0.7 s  3.0 s  0.4 s  0.8 s  3.1 s  14 digits
40 medium  1.7 s  2.8 s  8.1 s  2.9 s  5.2 s 12.0 s  45 digits
40 large  3.2 s  5.7 s 14.0 s  7.7 s 12.0 s 23.0 s 123 digits
40 extralarge  7.0 s 12.9 s 26.0 s 11.8 s 22.0 s 47.0 s 264 digits
80 small 3,7 s 5.6 s 14.0 s 2.7 s 5.6 s 17.0 s 39 digits
80 medium  22.0 s 24.0 s 66.0 s 42.0 s 46.0 s 96.0 s 157 digits
80 large  53.0 s 48.0 s 109.0 s 89.0 s 120.0 s 180.0 s 349 digits
80 extralarge 116.0 s 110.0 s 250.0 s 196.0 s 180.0 s 360.0 s 640 digits
Lex  𝔸^{10}  𝔸^{20}  𝔸^{40}
40 small  0.1 s  0.2 s  0.3 s
40 medium  0.4 s  0.6 s  0.9 s
40 large  3.3 s  4.0 s  5.4 s
40 extralarge 29.7 s 38.2 s 59.0 s
80 small  0.5 s  0.6 s  0.9 s
80 medium  2.5 s  2.6 s  4.3 s
80 large  24.0 s 27.0 s 36.0 s
80 extralarge 490.0 s 590.0 s 720.0 s

The first column indicates the number and the size of the points: small means that the coordinates are integers between −1 and 1, medium are between −9 and 9, large between −99 and 99, and extralarge between −9999 and 9999. The other columns give the dimension and type of space (affine or projective).

The last column gives the average size of the coefficients in the basis of points in ℙ_{ℚ}^{39} . This shows very clearly how the timings over ℚ depend on the size of the coordinates.

All these timings are given for computations over ℚ. The computation of these examples over finite fields is performed by comparison in negligible time; for example the ideal of 80 points in ℙ^{39} wrt DegRevLex over ℤ/(32003) is computed in 2.8 seconds.

Note the apparently surprising behaviour when comparing the orderings DegRevLex and Lex on the smaller examples. This is because we used random points from a relatively small range rather than generic points, so the Lex basis comes out “smaller than normal” (smaller coefficients and lower maximal degree of the leading terms of the basis). The “extralarge” rows show the expected behaviour.

References

Buchberger, B. (1965). An algorithm for finding a basis for the residue class ring of a zero-dimensional

polynomial ideal. PhD thesis, University of Innsbruck (Austria). (in German). Buchberger, B. (1970). An algorithmical criterion for the solvability of algebraic systems of equations.

Aequationes Math., 4(3):374–383. Buchberger, B. (1985). Groebner Bases: An Algorithmic Method in Polynomial Ideal Theory, chapter 6,

pages 184–232. N.K. Bose Ed., D. Reidel Publishing Co. Buchberger, B., Möller, H. M. (1982). The construction of multivariate polynomials with preassigned ze-

ros. In Calmet, J., editor, Proceedings of the European Computer Algebra Conference (EUROCAM ’82), volume 144 of Lecture Notes in Comp.Sci., pages 24–31, Marseille, France. Springer.

Capani, A., Niesi, G., Robbiano, L. (1998). CoCoA, a system for doing Computations in Commutative

Algebra. Available via anonymous ftp from cocoa.dima.unige.it, 3.6 edition. Cioffi, F. (1998) Minimally generating ideals of points in polynomial time using linear algebra. Ricerche

di Matematica, XLVII fasc. 2 (1998) Collins, G. E., Encarnación, M. J. (1995). Efficient rational number reconstruction. J. Symb. Comput.,

20(3):287–298. Geramita, A. V., Kreuzer, M., Robbiano, L. (1993). Cayley-Bacharach schemes and their canonical

modules. Trans. Amer. Math. Soc., 339:163–189. Lakshman, Y. (1991). A single exponential bound on the complexity of computing Gröbner bases of zero

dimensional ideals. In Mora, T., Traverso, C., editors, MEGA-90 (Castiglioncello/Italy), volume 94 of Progress in Math., pages 227–234, Boston. Birkhäuser.

Marinari, M., Moeller, H., Mora, T. (1993). Groebner bases of ideals defined by functionals with an

application to ideals of projective points. Appl. Alg. in Eng., Comm. and Comp., 4(2):103–145. Mora, T., Robbiano, L. (1993). Points in affine and projective spaces. In Eisenbud, D., Robbiano, L.,

editors, Computational Algebraic Geometry and Commutative Algebra, Cortona-91, volume XXXIV of Symposia Mathematica, pages 106–150. Cambridge University Press.

Möller, M. (1998). Gröbner Bases and Numerical Analysis. In B.Buchberger, F.Winkler, editors, Gröbner Bases and Applications (Proc. of the Conf. 33 Years of Gröbner Bases), volume 251 of London Mathematical Society Lecture Notes Series, pages 159–178. Cambridge University Press.

Robbiano, L. (1998). Gröbner Bases and Statistic. In B.Buchberger, F.Winkler, editors, Gröbner Bases and Applications (Proc. of the Conf. 33 Years of Gröbner Bases), volume 251 of London Mathematical Society Lecture Notes Series, pages 179–204. Cambridge University Press.

Sakata, S. (1998). Gröbner Bases and Coding Theory. In B.Buchberger, F.Winkler, editors, Gröbner Bases and Applications (Proc. of the Conf. 33 Years of Gröbner Bases), volume 251 of London Mathematical Society Lecture Notes Series, pages 205–220. Cambridge University Press.

Wang, P. S., Guy, M. J. T., Davenport, J. H. (1982). p-adic reconstruction of rational numbers. SIGSAM Bulletin (ACM Special Interest Group on Symbolic and Algebraic Manipulation), 16(2):2–3.