From algebraic sets to monomial linear bases by means of combinatorial algorithms.

L. Cerlienco and M. Mureddu

Summary. Let K be a field; let P ⊂ K^{n} be a finite set and let ℑ(P) ⊂ K[x_{1}, …, x_{n}] be the ideal of P. A purely combinatorial algorithm to obtain a linear basis of the quotient algebra K[x_{1}, …, x_{n}]/ℑ(P) is given. Such a basis is represented by an n-dimensional Ferrers diagram of monomials which is minimal with respect to the inverse lexicographical order ⪯_{i.l.}. It is also shown how this algorithm can be extended to the case in which P is an algebraic multiset. A few applications are stated (among them, how to determine a reduced Gröbner basis of ℑ(P) with respect to ⪯_{i.l.} without using Buchberger’s algorithm).

1 Introduction

1.1 Let N be the monoid of non-negative integers. Denote by i := (i_{1}, …, i_{n}) an arbitrary element in the power N^{n}. The usual order on N, as well as the partial order it induces on N^{n}, will be denoted by ≤.

Define an n-dimensional Ferrers diagram to be any finite ideal of the poset N^{n}, i.e. any non-empty finite subset F ⊆ N^{n} such that j < i ∈ F ⟹ j ∈ F. An element i = (i_{1}, …, i_{n}) ∉ F is said to be a co-minimal element for the Ferrers diagram F if it is a minimal element of the complementary filter N^{n} \ F, i.e. if (i_{1}, …, i_{r−1}, i_{r} − 1, i_{r+1}, …, i_{n}) ∈ F for each r such that i_{r} ≥ 1. Of course, i ∉ F is a co-minimal element iff F′ := {i} ∪ F is a Ferrers diagram.

We will write ⪯ for any term-ordering on N^{n}, i.e. a linear ordering which is compatible with the monoid structure on N^{n}:

0 ≺ i for every i ≠ 0 in N^{n},

i ⪯ j ⟹ i + r ⪯ j + r for every i, j, r ∈ N^{n}.

It is well known that every term-ordering on N^{n} is also a well-ordering.

1.2 Let K be a field and let X := {x_{1}, x_{2}, …, x_{n}} be a given set of indeterminates. Let us consider the usual polynomial algebra K[X] := K[x_{1}, …, x_{n}]. Denote by M_{X} ⊆ K[X] the free abelian monoid on X. The elements of M_{X} (i.e. the monic monomials) will be called terms of K[X] and denoted by x^{i} := x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}} with i := (i_{1}, …, i_{n}) ∈ N^{n}. The orders ≤ and ⪯ on N^{n}, as well as the notion of Ferrers diagram, extend to M_{X} in an obvious way.

An ideal J of the algebra K[X] is said to be cofinite if

codim(J) := dim (K[X]/J) < ∞.

Given a finite set P := {P_{1}, …, P_{N}} ⊆ K^{n}, the ideal

ℑ(P) := {p ∈ K[X] | (∀P ∈ P)(p(P) = 0)}

of the algebraic set P is cofinite. More generally, when K is algebraically closed, from the Nullstellensatz it follows that an ideal J ⊆ K[X] is a cofinite ideal iff the algebraic set of J, i.e.

V(J) := {P ∈ K^{n} | (∀p ∈ J)(p(P) = 0)} ,

is finite. In this case we have #V(J) = codim(\sqrt{J}) ≤ codim(J) (cfr. [5] p.23).

For a given ideal J, any linear basis L_{J} of the quotient algebra K[X]/J whose elements are of the form [x^{i}]_{J} := x^{i} + J will be called a monomial basis. If L_{J} = {x^{i} + J | i ∈ L ⊆ N^{n}} is a monomial basis, we shall say that {x^{i} | i ∈ L} is a system of representatives for the monomial basis L_{J}. Obviously, if L_{J} = {x^{i} + J | i ∈ L} is a monomial basis of K[X]/J, then any polynomial p ∈ K[X] is congruent modulo J to exactly one polynomial of the form ∑_{i∈L} a_{i}x^{i}, a_{i} ∈ K. Given an arbitrary term-ordering ⪯ on M_{X}, a monomial basis L_{J} = {x^{i_{1}} + J, …, x^{i_{N}} + J} with x^{i_{1}} ≺ … ≺ x^{i_{N}} is said to be minimal with respect to ⪯ if for any other monomial basis L′_{J} = {x^{i′^{1}} + J, …, x^{i′^{N}} + J} with x^{i′^{1}} ≺ … ≺ x^{i′^{N}} we have x^{i_{j}} ⪯ x^{i′^{j}} for j = 1, …, N. Equivalently, L_{J} = {x^{i_{1}} + J, …, x^{i_{N}} + J}, x^{i_{1}} ≺ … ≺ x^{i_{N}}, is minimal with respect to ⪯ if every term x^{i}, such that x^{i} ≺ x^{i_{j}}, is linearly dependent (modulo J) on x^{i_{1}}, …, x^{i_{j−1}}. Of course, both L_{J} and L′_{J}, L_{J} ≠ L′_{J}, could be minimal with respect to different term-orderings. It is not hard to prove that if L_{J} = {x^{i_{j}} +J | j = 1, …, N} is a minimal monomial basis then L = {i_{1}, …, i_{N}} ⊆ N^{n} is an n-dimensional Ferrers diagram. In fact, if x^{i} ∉ L_{J}, then

x^{i} = ∑_{x^{i_{j}} ≺x^{i}} λ_{j}x^{i_{j}} modulo J.

Thus,

x^{i+r} = ∑_{x^{i_{j}} ≺x^{i}} λ_{j}x^{i_{j}+r} modulo J

where r ∈ N^{n} and x^{i_{j}} ≺ x^{i_{j}+r} ≺ x^{i+r} as ⪯ is a term-ordering. Since either x^{i_{j}+r} + J belongs to L_{J} or x^{i_{j}+r} + J is a linear combination of smaller elements in L_{J}, from the above congruence we deduce that the same is true for x^{i+r} + J:

x^{i+r} = ∑_{x^{i_{j}} ≺x^{i+r}} μ_{j}x^{i_{j}} modulo J.

Hence, i ∉ L ⇒ i + r ∉ L, i.e. i + r ∈ L ⇒ i ∈ L; thus, L is a Ferrers diagram.

1.3 In the search for a minimal monomial basis L_{P}, in the following section we present a purely combinatorial algorithm to get it from P. In fact, making use of the Algorithm MB below, we associate a Ferrers diagram MB(P) = {d_{1}, …, d_{N}} ⊆ N^{n} to any finite set P := {P_{1}, …, P_{N}} ⊆ K^{n}. The Ferrers diagram MB(P) gives the monomial basis L_{P} = {x^{d} + ℑ(P) | d ∈ MB(P)} which is minimal with respect to the inverse lexicographical ordering ⪯_{i.l.} with x_{1} ≺_{i.l.} x_{2} ≺_{i.l.} … ≺_{i.l.} x_{n} .

The implementation of Algorithm MB, as well as that of its applications described in section 4, presents no serious difficulties.

2 The Algorithm MB

2.1 Let P := {P_{1}, …, P_{N}} ⊆ K^{n}. For 1 ≤ j ≤ N and for 0 ≤ s ≤ n, put \underline{P} := (P_{1}, …, P_{N}); d_{j} = (d_{j,1}, …, d_{j,n}) ∈ N^{n}; π_{s}: K^{n} ⟶ K^{s}, (x_{1}, …, x_{n}) ↦ (x_{1}, …, x_{s}) (π_{0}(P) is assumed to be the empty sequence); π^{s}: K^{n} ⟶ K^{n−s+1}, (x_{1}, …, x_{n}) ↦ (x_{s}, …, x_{n}).

Given a list \underline{P} := (P_{1}, …, P_{N}) of points, we determine an ordered set \underline{F} := (d_{1}, …, d_{N}).

MB1. [Initialize.] Set d_{1} ← d_{2} ← … d_{N} ← (0, …, 0); i ← 1. (In the beginning the coordinates of all the elements of \underline{F} are zero.)

MB2. [Put the first i points of the list \underline{P} in Q.] Set Q ← {P_{j} | 1 ≤ j ≤ i}.

MB3. [Find which coordinate of d_{i+1} has to be changed, say d_{i+1,s}.] Set s ← max{k ≥ 1 | π_{k−1}(P_{j}) = π_{k−1}(P_{i+1}), for some P_{j} ∈ Q}. (s − 1 is the length of the longest initial segment shared by P_{i+1} and some point P_{j} ∈ Q. If s > 1, then in successive steps this value decreases.)

MB4. [Find the points that determine the s-th coordinate of d_{i+1}.] Set E ← {j | P_{j} ∈ Q, π_{s−1}(P_{j}) = π_{s−1}(P_{i+1}), π^{s+1}(d_{j}) = π^{s+1}(d_{i+1})}. (E contains the indices of the points of Q which have the first s − 1 coordinates equal to those of P_{i+1} and whose corresponding elements in \underline{F} have the n − s rightmost coordinates equal to those of d_{i+1}. E is always non-empty.)

MB5. [Assign the value to the s-th coordinate of d_{i+1}.] Set d_{i+1,s} ← (1 + max{d_{j,s} | j ∈ E}).

MB6. [Did you determine the first coordinate of d_{i+1}?] If s > 1

MB6.1. [Find the points that determine another coordinate of d_{i+1}.] Set Q ← {P_{j} | 1 ≤ j ≤ i, π^{s}(d_{j}) = π^{s}(d_{i+1}) = (d_{i+1,s}, …, d_{i+1,n})}. (Q contains the points of \underline{P} different from P_{i+1} whose corresponding elements in \underline{F} have the n − s + 1 rightmost coordinates equal to those of d_{i+1}.)

MB6.2. [Is Q empty?] If Q ≠ ∅, return to step MB3.

MB7. [Increase i.] Set i ← i + 1. If i < N, return to step MB2.

MB8. [Done.] Terminate the algorithm.

2.2 Let \underline{P} := (P_{1}, …, P_{N}) and \underline{F} := (d_{1}, …, d_{N}) as in 2.1. We put: MB(P) := \{d_{1}, …, d_{N}\}; δ\underline{P}: P → MB(P), P_{i} ↦ d_{i}. Notice that now and in the following notations such as \underline{P} and \underline{F} always denote ordered sets whose underlying sets are P and F, respectively; moreover, the order on \underline{F}, as well as the map δ\underline{P}, depends on both the ordered set \underline{P} and the Algorithm MB. One could think that MB(P) is ill-defined, namely that it depends on the order which has been used for arranging the points P_{1}, …, P_{N} when starting Algorithm MB (i.e. on the list \underline{P}) rather than on the set P = \{P_{1}, …, P_{N}\} itself. Well, this is not true. In fact, the following properties hold.

Lemma 1 Let \underline{P} := (P_{1}, …, P_{i}, P_{i+1}, …, P_{N}), \underline{P′} := (P_{1}, …, P_{i+1}, P_{i}, …, P_{N}). Let \underline{F} := (d_{1}, …, d_{i}, d_{i+1}, …, d_{N}) and \underline{F′} := (d′_{1}, …, d′_{i}, d′_{i+1}, …, d′_{N}) be the lists associated by Algorithm MB with \underline{P} and \underline{P′} respectively. Then, {d_{1}, …, d_{N}} = {d′_{1}, …, d′_{N}}.

Proof. Consider

P_{i} = (a_{i,1}, …, a_{i,r−1}, a_{i,r}, …, a_{i,n}),
P_{i+1} = (a_{i+1,1}, …, a_{i+1,r−1}, a_{i+1,r}, …, a_{i+1,n}),

d_{i} = (d_{i,1}, …, d_{i,r−1}, d_{i,r}, …, d_{i,n}),
d_{i+1} = (d_{i+1,1}, …, d_{i+1,r−1}, d_{i+1,r}, …, d_{i+1,n})

where r is such that d_{i,r} ≠ d_{i+1,r}, d_{i,r+1} = d_{i+1,r+1}, …, d_{i,n} = d_{i+1,n}. It may happen that either i) (a_{i,1}, …, a_{i,r−1}) ≠ (a_{i+1,1}, …, a_{i+1,r−1}) (in which case d′_{i} = d_{i+1} and d′_{i+1} = d_{i}), or ii) (a_{i,1}, …, a_{i,r−1}) = (a_{i+1,1}, …, a_{i+1,r−1}) (in which case we have a_{i,r} ≠ a_{i+1,r}, since otherwise d_{i,r+q} ≠ d_{i+1,r+q} for some q ≥ 1. From this we deduce d′_{i} = d_{i} and d′_{i+1} = d_{i+1}). First notice that obviously d_{1} = d′_{1}, …, d_{i−1} = d′_{i−1}. We prove that we also have d_{i+2} = d′_{i+2}, …, d_{N} = d′_{N} by distinguishing the case i) from the case ii). In the first case the proof is easy. In fact, when calculating d_{i+t} and/or d′_{i+t}, the set E defined in MB4 cannot contain both i and i + 1 since π^{s+1}(d_{i}) ≠ π^{s+1}(d_{i+1}) for every s ≤ r and π_{s−1}(P_{i}) ≠ π_{s−1}(P_{i+1}) for every s > r. In case ii), suppose that d_{i+2} = d′_{i+2}, …, d_{N−1} = d′_{N−1}; consider d_{N} = (d_{N,1}, …, d_{N,t−1}, d_{N,t} ≠ 0, d_{N,t+1} = 0, …, d_{N,n} = 0), so that (a_{N,1}, …, a_{N,t−1}) is the longest initial segment of the coordinates that P_{N} shares with some P_{j}, j < N. By arguing separately in the three cases t = r, t < r and t > r, it is not difficult to prove that d′_{N} = d_{N}. □

As a straightforward consequence of Lemma 1 we obtain the following proposition.

Prop. 1 Let \underline{P} and \underline{F} be as in Lemma 1. Let \underline{F′} := (d′_{1}, …, d′_{N}) be the list associated by Algorithm MB with the list of points \underline{P′} = (P_{σ(1)}, …, P_{σ(N)}), where σ ∈ S_{N}. (S_{N} is the symmetric group.) Then, for some τ ∈ S_{N} we have (d′_{1}, …, d′_{N}) = (d_{τ(1)}, …, d_{τ(N)}). □

Corollary 1 If P ⊆ Q, then MB(P) ⊆ MB(Q). □

Prop. 2 Let \underline{P} and \underline{F} be as in Lemma 1. It is possible to rearrange the points P_{1}, …, P_{N} in a suitable list \underline{P′} = (P_{σ(1)}, …, P_{σ(N)}) such that the elements in the corresponding list \underline{F′} = (d_{τ(1)}, . . . . . . , d_{τ(N)}) are in inverse lexicographical order ⪯_{i.l.}: s < t ⇒ d_{τ(s)} ≺_{i.l.} d_{τ(t)}.

Proof. Let P_{j} = (a_{j,1}, …, a_{j,r−1}, a_{j,r}, …, a_{j,n}), d_{j} = (d_{j,1}, …, d_{j,r−1}, d_{j,r}, …, d_{j,n}), j = 1, …, N. It suffices to observe that if, for some i, d_{i+1} := δ\underline{P}(P_{i+1}) ≺_{i.l.} d_{i} := δ\underline{P}(P_{i}) (i.e. d_{i,r} > d_{i+1,r}, d_{i,r+1} = d_{i+1,r+1}, …, d_{i,n} = d_{i+1,n} for some r ≤ n), then we have necessarily the case i) considered in the proof of Lemma 1. □

Lemma 2 Let \underline{P} and \underline{F} be as in Lemma 1. Let d_{N} = (d_{N,1}, …, d_{N,n}). If d_{N,i} ≠ 0, then there is some k < N such that d_{k} = (d_{N,1}, …, d_{N,i−1}, d_{N,i} − 1, d_{N,i+1}, …, d_{N,n}).

Proof. When calculating the first i − 1 coordinates d_{N,1}, …, d_{N,i−1} of d_{N} = δ\underline{P}(P_{N}), we have to consider the set \{P_{j_{1}}, …, P_{j_{s}}, P_{j_{s+1}} = P_{N}\} ⊆ P, j_{1} < … < j_{s} < N, of all points P_{j_{r}} ∈ P such that π^{i}(δ\underline{P}(P_{j_{r}})) = (d_{N,i}, …, d_{N,n}). Putting \underline{P̃} := (π_{i−1}(P_{j_{1}}), …, π_{i−1}(P_{j_{s}}), π_{i−1}(P_{N})), we have π_{i−1}(δ\underline{P}(P_{N})) = δ\underline{P̃}(π_{i−1}(P_{N})) = (d_{N,1}, …, d_{N,i−1}). For every r ∈ \{1, …, s+1\}, there is a point P_{j′_{r}} ∈ P, j′_{r} < j_{r}, such that d_{j′_{r},i} = d_{j_{r},i} − 1 = d_{N,i} − 1, d_{j′_{r},i+1} = d_{j_{r},i+1} = d_{N,i+1}, …, d_{j′_{r},n} = d_{j_{r},n} = d_{N,n} and π_{i−1}(P_{j′_{r}}) = π_{i−1}(P_{j_{r}}). Up to a suitable rearrangement of the points in \underline{P}, we may assume that j′_{1} < … < j′_{s+1}. In order to calculate π_{i−1}(δ\underline{P}(P_{j′_{s+1}})) we have to consider the set Q := \{P_{l} ∈ P | l ≤ j′_{s+1}, π^{i}(d_{l}) = (d_{j′_{s+1},i}, …, d_{j′_{s+1},n}) = (d_{N,i} − 1, d_{N,i+1} …, d_{N,n})}. Of course P_{j′_{r}} ∈ Q. Let Q̃ := {π_{i−1}(P) | P ∈ Q} ⊆ K^{i−1}; we have P̃ ⊆ Q̃. Hence MB(P̃) ⊆ MB(Q̃) ⊆ N^{i−1}; in particular (d_{N,1}, …, d_{N,i−1}) ∈ MB(Q̃). It follows that there exists a point P_{k} ∈ Q such that δ\underline{P}(P_{k}) = (d_{N,1}, …, d_{N,i−1}, d_{N,i} − 1, d_{N,i+1} …, d_{N,n}). □

As a straightforward consequence of Lemma 2 we get:

Prop. 3 The set MB(P) is an n-dimensional Ferrers diagram. □

Prop. 4 The set L_{P} = {x^{d} + ℑ(P) | d ∈ MB(P)} is a monomial linear basis for K[X]/ℑ(P).

Proof. By induction on the dimension n of K^{n}.

For n = 1, we have P = {ρ_{1}, …, ρ_{N}}, ρ_{i} ∈ K, and ℑ(P) = (g), with g = Π_{i=1}^{N}(x − ρ_{i}). Algorithm MB gives MB(P) = {0, 1, …, N − 1}; hence L_{P} = {x^{d} + ℑ(P) | d ∈ MB(P)} = {1 + (g), x + (g), …, x^{N−1} + (g)}, which is a monomial basis for K[X]/(g).

Suppose now that the statement is true for every finite subset of K^{n′}, n′ < n, and prove it for P = {P_{1}, …, P_{N}} ⊂ K^{n}. As dim K[X]/ℑ(P) = N = #MB(P), it remains to prove that the residue classes modulo ℑ(P) of the monomials x^{d}, d ∈ MB(P), are linearly independent over K[X]/ℑ(P); in other words, we have to prove that any polynomial

p(x_{1}, …, x_{n}) = ∑_{d∈MB(P)} α_{d}x^{d}, α_{d} ∈ K (1)

belonging to ℑ(P) is the zero polynomial.

Putting F := MB(P), F_{r} := {d = (d_{1}, …, d_{n}) ∈ F | d_{n} = r} and P_{r} := \{P ∈ P | δ\underline{P}(P) ∈ F_{r}\}, it is easy to check that

MB(π_{n−1}(P_{r})) = π_{n−1}(F_{r}). (2)

Let us write polynomial (1) in the form

p(x_{1}, …, x_{n}) = ∑_{r=0}^{h} p_{r}(x_{1}, …, x_{n−1})x_{n}^{r} (3)

where h =max{d_{n} | d = (d_{1}, …, d_{n}) ∈ F} and

p_{r}(x_{1}, …, x_{n−1}) = ∑_{(d_{1},...,d_{n−1})∈π_{n−1}(F_{r})} α_{(d_{1},...,d_{n−1},r)}x_{1}^{d_{1}} ⋯ x_{n−1}^{d_{n−1}}. (4)

The polynomial p(x_{1}, …, x_{n}) ∈ ℑ(P) has to vanish at every point in P. Consider a point P = (a_{1}, …, a_{n}) ∈ P_{h} ⊆ P; because of MB5, there exists in P exactly h+1 points that have the same first n−1 coordinates as P = (a_{1}, …, a_{n}). It follows that the polynomial

p(a_{1}, …, a_{n−1}, x_{n}) = ∑_{r=0}^{h} p_{r}(a_{1}, …, a_{n−1})x_{n}^{r}

vanishes identically. In particular p_{h}(a_{1}, …, a_{n−1}) = 0 for every (a_{1}, …, a_{n−1}) ∈ ∈ Q_{h} := π_{n−1}(P_{h}). Hence

p_{h}(x_{1}, …, x_{n−1}) ∈ ℑ(Q_{h}) ⊆ K[x_{1}, …, x_{n−1}]. (5)

By (2) and (4) we have

p_{h}(x_{1}, …, x_{n−1}) = ∑_{(d_{1},...,d_{n−1})∈MB(Q_{h})} α_{(d_{1},...,d_{n−1},h)}x_{1}^{d_{1}} ⋯ x_{n−1}^{d_{n−1}}. (6)

Because of the inductive hypothesis, the set {x_{1}^{d_{1}} ⋯ x_{n−1}^{d_{n−1}} + ℑ(Q_{h}) | (d_{1}, … …, d_{n−1}) ∈ MB(Q_{h})} is a monomial basis for K[x_{1}, …, x_{n−1}]/ℑ(Q_{h}). ¿From this and from (5) we deduce that polynomial (6) vanishes identically. Hence

p(x_{1}, …, x_{n}) = ∑_{r=0}^{h−1} p_{r}(x_{1}, …, x_{n−1})x_{n}^{r}. (7)

Arguing for r = h − 1, h − 2, …, 1, 0 as for r = h, we conclude that p_{r}(x_{1}, …, x_{n−1}) is the zero polynomial for every r ∈ {0, …, h}. □

Prop. 5 The monomial linear basis L_{P} = {x^{d} + ℑ(P) | d ∈ MB(P)} for K[X]/ℑ(P) is minimal with respect to inverse lexicographical order ⪯_{i.l.} on M_{X}.

Proof. Let \underline{P} = (P_{1}, …, P_{N}), \underline{F} := \underline{MB(P)} = (d_{1}, …, d_{N}); d_{i} = (d_{i,1}, …, d_{i,n}), P_{i} = (a_{i,1}, …, a_{i,n}) for i = 1, …, N. Assume that d_{1} ≺_{i.l.} … ≺_{i.l.} d_{N}. Let N′ ≤ N and let d = (d_{1}, …, d_{n}) ≺_{i.l.} d_{N′}. We have to prove that x^{d} is linearly dependent (modulo ℑ(P)) on x^{d_{1}}, …, x^{d_{N′−1}}, i.e. there exists in ℑ(P) a non-zero polynomial p(x_{1}, …, x_{n}) of the form

p(x_{1}, …, x_{n}) = ∑_{i=1}^{N′−1} α_{i}x^{d_{i}} + αx^{d}. (8)

Obviously, we may assume that d_{N′−1} ≺_{i.l.} d. Because of MB6.1 of Algorithm MB, without loss of generality we may also assume that d_{n} < d_{N′,n}. Thus, h := d_{N′,n} > 0 and d_{j,n} < h for every j ∈ {1, …, N′ − 1}.

Let us first prove that there is a polynomial of the form (8) which belongs to ℑ(P′) ⊇ ℑ(P), where P′ = {P_{1}, …, P_{N′}}. Equivalently, let us show that the linear homogeneous system

∑_{i=1}^{N′−1} α_{i}a_{s,1}^{d_{i,1}} ⋯ a_{s,n}^{d_{i,n}} + αa_{s,1}^{d_{1}} ⋯ a_{s,n}^{d_{n}} = 0, (s = 1, …, N′) (9)

admits a non-zero solution (α_{1}, …, α_{N′−1}, α). In fact the N′ by N′ matrix A whose s − th row is

a_{s,1}^{d_{1,1}} ⋯ a_{s,n}^{d_{1,n}} … a_{s,1}^{d_{N′−1,1}} ⋯ a_{s,n}^{d_{N′−1,n}} a_{s,1}^{d_{1}} ⋯ a_{s,n}^{d_{n}}

(that is, the evaluation at P_{s} of the list of monomials x^{d_{1}}, …, x^{d_{N′−1}}, x^{d}) is a singular matrix. In order to prove this, consider the h + 1 points P_{t_{1}}, …, P_{t_{h}} and P_{t_{h+1}} = P_{N′} (1 ≤ t_{j} ≤ N′) which have the same n − 1 first coordinates as P_{N′} (MB5 ensures that P contains h+1 such points). Let A′ be the h+1 by N′ submatrix of A whose rows correspond to these points. It is enough to show that A′ has rank less than h+1. In fact, any h+1 by h+1 minor C of A′ has columns which correspond to monomials x^{i} = x_{1}^{i_{1}} ⋯ x_{n−1}^{i_{n−1}}x_{n}^{i_{n}}, i ∈ {d_{1}, …, d_{N′−1}, d}, so that i_{n} may assume only the h values 0, 1, …, h − 1; since the (n − 1)-tuples (a_{j,1}, …, a_{j,n−1}) are always the same for j ∈ {t_{1}, …, t_{h+1}}, we conclude that C = 0. This completes the proof that there is a polynomial p(x_{1}, …, x_{n}) of the form (8) which belongs to ℑ(P′).

Let us now prove that we have p(P_{l}) = 0 for every P_{l} ∈ P \ P′. Let P_{l} = (a_{l,1}, …, a_{l,n−1}, a_{l,n}) be such a point; consider the polynomial

q_{l}(x_{n}) := p(a_{l,1}, …, a_{l,n−1}, x_{n}) = ∑_{s=0}^{h−1} q_{l,s}x_{n}^{s}.

Since d_{N′} ≺_{i.l.} d_{l}, i.e. h = d_{N′,n} ≤ d_{l,n}, there are in P′ at least h points which have the same n−1 first coordinates as P_{l}; it follows that the polynomial q_{l}(x_{n}) vanishes identically. Thus, p(P_{l}) = 0. □

2.3 In the case where n = 2 Algorithm MB can be given the following simplified form.

Assume that

P = {(a_{1}, b_{1,1}), …, (a_{1}, b_{1,h_{1}}), …, (a_{m}, b_{m,1}), …, (a_{m}, b_{m,h_{m}})}

with h_{1} + … + h_{m} = N, h_{1} ≥ … ≥ h_{m} and i ≠ j ⇒ a_{i} ≠ a_{j}. Then,

MB(P) = {(p, q) | 0 ≤ p < m, 0 ≤ q < h_{p}}.

3 Generalization to the algebraic multisets

3.1 All that we have stated up to now can be generalized to what we might call algebraic multisets in the following sense.

Consider the linear map

D_{i}: K[X] ⟶ K[X]
x^{h} ⟼ \binom{h}{i}x^{h−i}

where h = (h_{1}, …, h_{n}), i = (i_{1}, …, i_{n}) ∈ N and \binom{h}{i} := \binom{h_{1}}{i_{1}} · . . . · \binom{h_{n}}{i_{n}}. We have the formula

(10) D_{i}(fg) = ∑_{h+k=i} D_{h}(f)D_{k}(g).

Observe that when the field K has characteristic zero, then

D_{i} = \frac{1}{i!}D^{i} := \frac{1}{i!} \frac{∂^{i_{1}+···+i_{n}}}{∂x_{1}^{i_{1}} ⋯ ∂x_{n}^{i_{n}}}

where i! := i_{1}! ⋯ i_{n}!. Let v_{P} be the evaluation map at the point P:

v_{P}: K[X] ⟶ K
q ⟼ q(P).

Define the linear map v_{P}^{i} as the composition v_{P} ∘ D_{i}, i.e.

v_{P}^{i} : K[X] ⟶ K
q ⟼ (D_{i}q)(P).

For every ideal J of K[X] and every P ∈ V(J), put

F_{J}(P) := {i ∈ N^{n}| (∀p ∈ J) (v_{P}^{i} (p) = 0)} .

Prop. 6 i) F_{J}(P) is an n-dimensional Ferrers diagram; ii) if (g_{1}, …, g_{s}) is a system of generators of J, then F_{J}(P) is the largest n-dimensional Ferrers diagram contained in the set

{i ∈ N^{n}| v_{P}^{i} (g_{j}) = 0 for every 1 ≤ j ≤ s} .

Proof. Let P = (a_{1}, …, a_{n}). Let i ∈ F_{J}(P) and let j < i. Let us prove that j ∈ F_{J}(P). Let f := (x − P)^{i−j} = (x_{1} − a_{1})^{i_{1}−j_{1}} ⋯ (x_{n} − a_{n})^{i_{n}−j_{n}}. We have v_{P}^{h}(f) = (D_{h}f)(P) = δ_{h}^{i−j}. ¿From (10) we deduce that for every g ∈ J we have

0 = v_{P}^{i} (fg) = ∑_{h+k=i} v_{P}^{h}(f) · v_{P}^{k} (g) = v_{P}^{j} (g).

Hence j ∈ F_{J}(P). The second part of the statement is a straightforward consequence of i) and of (10). □

We define a finite n-dimensional algebraic multiset, or simply an algebraic multiset, to be a set ℘ := {(P_{1}, F_{1}), …, (P_{N}, F_{N})}; each element (P_{j}, F_{j}) ∈ ℘ consists of a point P_{j} of K^{n} together with an n-dimensional Ferrers diagram F_{j} ⊂ N^{n}, which will be called the algebraic diagram of the point P_{j}. We shall freely make use of the notation (P, i) ∈ ℘, or also P ∈ ℘, to mean that P = P_{j} and i ∈ F_{j} for some j ∈ {1, …, N}. To every algebraic multiset ℘ = {(P_{1}, F_{1}), …, (P_{N}, F_{N})} we associate the set

ℑ(℘) := {p ∈ K[X] | (∀j)(∀i ∈ F_{j}) (v_{P_{j}}^{i}(p) = 0)} .

It is not difficult to prove that ℑ(℘) is a cofinite ideal of K[X] and that F_{ℑ(℘)}(P_{j}) = F_{j} for every j ∈ {1, …, N}. Moreover, one can prove that

codim ℑ(℘) = #℘ := ∑_{j=1}^{N} #F_{j}.

The question now is: how do we get a monomial linear basis for K[X]/ℑ(℘)? Once more the problem can be solved by applying a slightly modified version of Algorithm MB (in fact Algorithm MB itself with a few obvious changes) to a suitable set R(℘) ⊂ (K × N)^{n} associated with the algebraic multiset ℘. The set R(℘) will be called the canonical representation of the algebraic multiset ℘. To be precise, consider the bijection

u: K^{n} × N^{n}  ⟶  (K × N)^{n}
((a_{1}, …, a_{n}), (i_{1}, …, i_{n})) ⟼ ((a_{1}, i_{1}), …, (a_{n}, i_{n})).

Put

R = R(℘) := {u(P, i) | (P, i) ∈ ℘}.

and

MB(℘) := MB(R).

It is possible (though by no means trivial) to prove that MB(℘) satisfies properties analogous to those of MB(P); in particular, i) MB(℘) is an n-dimensional Ferrers diagram and ii) the set L_{℘} := {x^{i} + ℑ(℘) | i ∈ MB(℘)} is a monomial linear basis of K[X]/ℑ(℘) which is minimal with respect to the inverse lexicographical order.

4 Applications

Both Algorithm MB and its generalization may come in handy for solving various problems. Let us examine a few of them.

4.1 First of all, let us see how to determine a system of generators (γ_{1}, …, γ_{r}) for the ideal ℑ(℘) of a finite algebraic multiset ℘ := {(P_{1}, F_{1}), …, (P_{N}, F_{N})}. In fact, the set {γ_{1}, …, γ_{r}} we shall obtain is also a reduced Gröbner basis of ℑ(℘) with respect to ⪯_{i.l.}. (The notion of reduced Gröbner basis as well as related topics can be found in [1], [3], [8].) It goes without saying that the same procedure works also when ℘ is a finite algebraic set.

Let L_{℘} := {x^{d} + ℑ(℘) | d ∈ MB(℘)} = {x^{d_{1}}, …, x^{d_{m}}}, where m = #℘ = codim(ℑ(℘)), be the monomial linear basis obtained in 3.1 and let {r_{1}, …, r_{r}} be the set of the co-minimal elements of the Ferrers diagram MB(℘). For each r_{i}, i = 1, …, s, define the polynomial γ_{i} ∈ K[X] to be the following determinant. The first row of γ_{i} is the list (x^{d_{1}}, …, x^{d_{m}}, x^{r_{i}}), while the successive rows are lists of the form (v_{P_{j}}^{i}(x^{d_{1}}), …, v_{P_{j}}^{i}(x^{d_{m}}), v_{P_{j}}^{i}(x^{r_{i}})), one for each (P_{j}, i) ∈ ℘. It can easily be proved that the list (γ_{1}, …, γ_{r}) is a reduced Gröbner basis of ℑ(℘) with respect to the inverse lexicographical order. Once the basis (γ_{1}, …, γ_{r}) has been found, a Gröbner basis with respect to a different term-ordering may be computed by making use of the methods given in [4].

4.2 Consider a linear form f ∈ K[X]^{∗} ≅ K[[X]]. If Ker(f) contains a cofinite ideal J of K[X], then f is said to be an n-linearly recursive function and J is called a characteristic ideal of f. This notion has been introduced in [2] as a generalization of that of linearly recursive sequence, to which it reduces when n = 1. An n-linearly recursive function f is uniquely determined by its characteristic ideal J and by its initial values, which are the values assumed by f on a system of representatives of a linear basis of K[X]/J. The set of n-linearly recursive functions may also be regarded as the dual bialgebra of the usual polynomial bialgebra on K[X]. When working on these subjects, it may happen that examples (perhaps, suitable examples) of n-linearly recursive functions are needed. How to construct them? It is convenient to divide the answer to this question into two parts. (A) Let us first suppose that we know a system of generators (g_{1}, …, g_{s}) of the characteristic ideal J of the n-linearly recursive functions we are considering. In this case we may calculate a reduced Gröbner basis G_{⪯} := RGB(g_{1}, …, g_{s}) of (g_{1}, …, g_{s}) with respect to some term-ordering ⪯ on M_{X}. Let G_{⪯} = (γ_{1}, …, γ_{r}), γ_{j} ∈ K[X], and let y_{j} ∈ M_{X} be the leading term (with respect to ⪯) of the polynomial γ_{j}. Then the set {x^{d} + J | x^{d} ∈ B}, where B = M_{X} \ ∪_{j=1}^{r}y_{j} · M_{X}, is a monomial linear basis for K[X]/J, which is minimal with respect to ⪯. It follows that any n-linearly recursive function whose characteristic ideal is J is uniquely determined by the set of its initial values {f(x^{d}) | x^{d} ∈ B}, all the other values f(x^{i}), x^{i} ∉ B, being calculated by making use of the polynomials γ_{j} ∈ G_{⪯} as scales of recurrence. (B) If instead the characteristic ideal is not given, we are quite unlikely to obtain one of them (remember it must be cofinite!) just choosing at random a set of generators: most of the time we would get a non-cofinite ideal or, when cofinite, a trivial one. The correct way to do this consists instead in choosing a finite algebraic multiset (possibly, a finite algebraic set) ℘ and then determining both the monomial linear basis L_{℘} of K[X]/ℑ(℘) and a set of generators for ℑ(℘) by means of the machinery described above.

4.3 Lastly, consider the following interpolation problem. Given a finite ndimensional algebraic multiset ℘ := {(P_{1}, F_{1}), …, (P_{N}, F_{N})} and a set of values {α_{j,i} | j = 1, …, N and i ∈ F_{j}} ⊂ K determine the unique polynomial p of the form ∑_{x^{i}∈B} a_{i}x^{i} (a_{i} ∈ K and B is a system of representatives of a monomial linear basis of K[X]/ℑ(℘)) such that v_{P_{j}}^{i}(p) = α_{j,i}.

This problem appears to be an n-dimensional natural generalization of the unidimensional one which is solved by means of the Lagrange-Hermite interpolation formula. Once more, the key point for solving this problem is to determine the monomial basis L_{℘}. Let L_{℘} = {x^{d_{1}} + ℑ(℘), …, x^{d_{m}} + ℑ(℘)} and let A be the m × m matrix whose rows are of the form (v_{P_{j}}^{i}(x^{d_{1}}), …, (v_{P_{j}}^{i}(x^{d_{m}})), one for each (P_{j}, i) ∈ ℘. Since L_{℘} is a linear basis of K[X]/ℑ(℘), the matrix A is non-singular. Consider the vector \overline{α} whose components are the values α_{j,i} = v_{P_{j}}^{i}(p) (arranged according to the order that has been used for the rows of A). The components of the vector \overline{β} := A^{−1} · \overline{α} are the coefficients of the desired polynomial.

Appendix.

1) Example of Algorithm MB for a 4-dimensional set.

P  ⟷  F = MB(P)
P_{1} = (2, 3, 9, 4)  ⟷  d_{1} = (0, 0, 0, 0)
P_{2} = (2, 5, 7, 3)  ⟷  d_{2} = (0, 1, 0, 0)
P_{3} = (2, 3, 3, 2)  ⟷  d_{3} = (0, 0, 1, 0)
P_{4} = (2, 5, 5, 1)  ⟷  d_{4} = (0, 1, 1, 0)
P_{5} = (6, 1, 1, 3)  ⟷  d_{5} = (1, 0, 0, 0)
P_{6} = (2, 3, 3, 6)  ⟷  d_{6} = (0, 0, 0, 1)
P_{7} = (8, 3, 4, 0)  ⟷  d_{7} = (2, 0, 0, 0)
P_{8} = (6, 5, 6, 3)  ⟷  d_{8} = (1, 1, 0, 0)
P_{9} = (4, 7, 6, 6)  ⟷  d_{9} = (3, 0, 0, 0)
P_{10} = (4, 1, 7, 7)  ⟷  d_{10} = (2, 1, 0, 0)
P_{11} = (2, 5, 7, 8)  ⟷  d_{11} = (0, 1, 0, 1)
P_{12} = (4, 3, 0, 3)  ⟷  d_{12} = (0, 2, 0, 0)
P_{13} = (1, 1, 2, 5)  ⟷  d_{13} = (4, 0, 0, 0)
P_{14} = (2, 1, 9, 0)  ⟷  d_{14} = (1, 2, 0, 0)
P_{15} = (4, 1, 7, 6)  ⟷  d_{15} = (1, 0, 0, 1)
P_{16} = (8, 1, 8, 0)  ⟷  d_{16} = (3, 1, 0, 0)
P_{17} = (2, 1, 7, 6)  ⟷  d_{17} = (0, 2, 1, 0)
P_{18} = (4, 3, 3, 3)  ⟷  d_{18} = (1, 0, 1, 0)
P_{19} = (4, 1, 1, 0)  ⟷  d_{19} = (1, 1, 1, 0)
P_{20} = (8, 1, 2, 4)  ⟷  d_{20} = (2, 0, 1, 0)
P_{21} = (6, 3, 4, 8)  ⟷  d_{21} = (2, 2, 0, 0)
P_{22} = (2, 9, 6, 7)  ⟷  d_{22} = (0, 3, 0, 0)
P_{23} = (2, 3, 7, 1)  ⟷  d_{23} = (0, 0, 2, 0)
P_{24} = (2, 1, 7, 5)  ⟷  d_{24} = (0, 2, 0, 1)
P_{25} = (4, 1, 1, 2)  ⟷  d_{25} = (0, 0, 1, 1)
P_{26} = (2, 7, 6, 5)  ⟷  d_{26} = (0, 4, 0, 0)
P_{27} = (2, 5, 5, 4)  ⟷  d_{27} = (1, 0, 1, 1)
P_{28} = (2, 3, 7, 7)  ⟷  d_{28} = (0, 1, 1, 1)
P_{29} = (2, 3, 0, 2)  ⟷  d_{29} = (0, 0, 3, 0)
P_{30} = (2, 1, 1, 1)  ⟷  d_{30} = (0, 1, 2, 0)
P_{31} = (4, 3, 3, 7)  ⟷  d_{31} = (1, 1, 0, 1)
P_{32} = (8, 5, 6, 4)  ⟷  d_{32} = (3, 2, 0, 0)
P_{33} = (4, 5, 5, 2)  ⟷  d_{33} = (1, 3, 0, 0)
P_{34} = (2, 1, 1, 8)  ⟷  d_{34} = (0, 2, 1, 1)
P_{35} = (8, 1, 1, 1)  ⟷  d_{35} = (1, 0, 2, 0)
P_{36} = (4, 5, 5, 5)  ⟷  d_{36} = (1, 2, 0, 1)
P_{37} = (6, 1, 8, 8)  ⟷  d_{37} = (3, 0, 1, 0)
P_{38} = (2, 7, 8, 4)  ⟷  d_{38} = (0, 3, 1, 0)

The system of representatives for the corresponding monomial basis is given in the following table.

1  x_{1}  x_{1}^{2}  x_{1}^{3} x_{1}^{4}  x_{3}  x_{1}x_{3} x_{1}^{2}x_{3} x_{1}^{3}x_{3}
x_{2}  x_{1}x_{2} x_{1}^{2}x_{2} x_{1}^{3}x_{2}  x_{2}x_{3} x_{1}x_{2}x_{3}
x_{2}^{2}  x_{1}x_{2}^{2} x_{1}^{2}x_{2}^{2} x_{1}^{3}x_{2}^{2}  x_{2}^{2}x_{3}
x_{2}^{3}  x_{1}x_{2}^{3}  x_{2}^{3}x_{3}

x_{2}^{4}

x_{3}^{2}  x_{1}x_{3}^{2}  x_{3}^{3}

x_{2}x_{3}^{2}

x_{4}  x_{1}x_{4}  x_{3}x_{4} x_{1}x_{3}x_{4}
x_{2}x_{4} x_{1}x_{2}x_{4}  x_{2}x_{3}x_{4}
x_{2}^{2}x_{4} x_{1}x_{2}^{2}x_{4}  x_{2}^{2}x_{3}x_{4}

2) Example of Algorithm MB for a 3-dimensional algebraic multiset.

Consider the algebraic multiset ℘ given by

P_{1} = (0, 0, 0) F_{1} = [ \begin{matrix}(0, 0, 0) & (1, 0, 0) \\ (0, 1, 0) \end{matrix}  ^{(0, 0, 1) ]}

P_{2} = (0, 0, 1) F_{2} = [ (0, 0, 0) (1, 0, 0) (2, 0, 0)  (0, 0, 1) (1, 0, 1) ]

P_{3} = (1, 1, 0) F_{3} = [ \begin{matrix}(0, 0, 0) & (1, 0, 0) \\ (0, 1, 0) & (1, 1, 0) \end{matrix}  \begin{matrix}(0, 0, 1) & (1, 0, 1) \\ (0, 1, 1) \end{matrix}  \begin{matrix}(0, 0, 2) \\ (0, 1, 2) \end{matrix} ]

P_{4} = (1, 1, 1) F_{4} = [ \begin{matrix}(0, 0, 0) \\ (0, 1, 0) \end{matrix} ]

The canonical representation R = R(℘) of ℘ (whose elements are intentionally arranged at random) as well as the corresponding 3-dimensional Ferrers diagram MB(R) are as follows.

℘  ⟷  R  ⟷ F = MB(R)
(1, 1, 0), (0, 0, 2) ⟷ R_{1} = (10, 10, 02) ⟷ d_{1} = (0, 0, 0)
(1, 1, 0), (0, 1, 2) ⟷ R_{2} = (10, 11, 02) ⟷ d_{2} = (0, 1, 0)
(0, 0, 1), (1, 0, 1) ⟷ R_{3} = (01, 00, 11) ⟷ d_{3} = (1, 0, 0)
(1, 1, 0), (1, 0, 1) ⟷ R_{4} = (11, 10, 01) ⟷ d_{4} = (2, 0, 0)
(0, 0, 1), (0, 0, 1) ⟷ R_{5} = (00, 00, 11) ⟷ d_{5} = (3, 0, 0)
(1, 1, 0), (0, 0, 1) ⟷ R_{6} = (10, 10, 01) ⟷ d_{6} = (0, 0, 1)
(0, 0, 1), (2, 0, 0) ⟷ R_{7} = (02, 00, 10) ⟷ d_{7} = (4, 0, 0)
(0, 0, 0), (1, 0, 0) ⟷ R_{8} = (01, 00, 00) ⟷ d_{8} = (1, 0, 1)
(1, 1, 0), (0, 0, 0) ⟷ R_{9} = (10, 10, 00) ⟷ d_{9} = (0, 0, 2)
(0, 0, 0), (0, 1, 0) ⟷ R_{10} = (00, 01, 00) ⟷ d_{10} = (1, 1, 0)
(0, 0, 0), (0, 0, 0) ⟷ R_{11} = (00, 00, 00) ⟷ d_{11} = (2, 0, 1)
(0, 0, 0), (0, 0, 1) ⟷ R_{12} = (00, 00, 01) ⟷ d_{12} = (1, 0, 2)
(1, 1, 0), (0, 1, 0) ⟷ R_{13} = (10, 11, 00) ⟷ d_{13} = (0, 1, 1)
(1, 1, 0), (1, 0, 0) ⟷ R_{14} = (11, 10, 00) ⟷ d_{14} = (3, 0, 1)
(0, 0, 1), (0, 0, 0) ⟷ R_{15} = (00, 00, 10) ⟷ d_{15} = (0, 0, 3)
(1, 1, 0), (0, 1, 1) ⟷ R_{16} = (10, 11, 01) ⟷ d_{16} = (0, 1, 2)
(1, 1, 0), (1, 1, 0) ⟷ R_{17} = (11, 11, 00) ⟷ d_{17} = (2, 1, 0)
(0, 0, 1), (1, 0, 0) ⟷ R_{18} = (01, 00, 10) ⟷ d_{18} = (2, 0, 2)
(1, 1, 1), (0, 1, 0) ⟷ R_{19} = (10, 11, 10) ⟷ d_{19} = (1, 0, 3)
(1, 1, 1), (0, 0, 0) ⟷ R_{20} = (10, 10, 10) ⟷ d_{20} = (0, 1, 3)

Therefore, a monomial linear basis of K[X]/ℑ(℘) consists of the equivalence classes (modulo ℑ(℘)) of the following monomials

1  x_{1}  x_{1}^{2} x_{1}^{3} x_{1}^{4}  x_{3} x_{1}x_{3} x_{1}^{2}x_{3} x_{1}^{3}x_{3}
x_{2} x_{1}x_{2} x_{1}^{2}x_{2}  x_{2}x_{3}

x_{3}^{2} x_{1}x_{3}^{2} x_{1}^{2}x_{3}^{2}  x_{3}^{3} x_{1}x_{3}^{3}
x_{2}x_{3}^{2}  x_{2}x_{3}^{3}

The reduced Gröbner basis of ℑ(℘) with respect to ⪯_{i.l} consists of the following polynomials:

g_{1} = x^{5} − 2x^{4} + x^{3}; g_{2} = x^{3}y − 2x^{2}y + xy; g_{3} = y^{2} + 2x^{2}y − 4xy − 3x^{4} + 4x^{3}; g_{4} = x^{4}z − 2x^{3}z + x^{2}z − x^{4} + 2x^{3} − x^{2}; g_{5} = xyz − yz − x^{3}z + x^{2}z − x^{4} + 2x^{3} − x^{2}; g_{6} = x^{3}z^{2} − x^{2}z^{2} + x^{4} − 2x^{3} + x^{2}; g_{7} = x^{2}z^{3} − xz^{3} − 2x^{2}z^{2} + 2xz^{2} − x^{3}z + 2x^{2}z − xz − x^{4} + 2x^{3} − x^{2}; g_{8} = z^{4} + xz^{3} − 2z^{3} + x^{2}z^{2} − 2xz^{2} + z^{2} + x^{3}z − 2x^{2}z + xz + x^{4} − 2x^{3} + x^{2}.

Acknowledgements

The authors thank T.Mora, O.Murru, F.Piras and R.Pirastu for their advice during several discussions. We are also indebted to the referees of the “Acts the 4th Conference Formal Power Series and Algebraic Combinatorics, Montreal, 1992” for a few useful suggestions.

References

[1] B. Buchberger, An Algorithmic Method in Polynomial Ideal Theory, in “N. K. Bose (ed): Recent Trends in Multidimensional System Theory”, D. Reidel Publishing Co. , Dordrecht-Boston, 1985, pp. 184-232

[2] L. Cerlienco, F. Piras, On the Continuous Dual of a Polynomial Bialgebra, Communications in Algebra, 19(10), 2707–2727 (1991)

[3] D. Cox, J. Little, D. O’Shea, Ideals, Varieties and Algorithms, Springer-Verlag, New York, 1992 [4] J.C. Faugère, P. Gianni, D. Lazar, T. Mora, Efficient computation

of zero-dimensional-Gröbner bases by change of ordering, Submitted to J. Symb. Comp. Technical Report LITP 89-52 (1989)

[5] W. Fulton, Algebraic curves, The Benjamin/Cummings, Reading, Mass., 1981

[6] M.G. Marinari, H.M. Möller, T. Mora, Gröbner bases of ideals defined by functionals with an application to ideals of projective points, J. Appl. Alg. 4 (1993), 1-43

[7] H.M. Möller, B. Buchberger, The construction of multivariate polynomials with preassigned zeros, in “Computer Algebra (Marseille, 1982)”, Lecture Notes in Comp. Sci., 144, Springer, Berlin-New York, 1982, pp.24-31

[8] L. Robbiano, Introduzione all’algebra computazionale. Appunti per il corso INDAM. (Roma 1986/87)

Authors address: Luigi Cerlienco, Marina Mureddu Dipartimento di Matematica. Via Ospedale 72 — I-09124 Cagliari (Italy) Tel. 0039-070-6758529/36 — Fax 0039-070-6758511 e-mail: CERLIENCO@VAXCA1.UNICA.IT MUREDDU@VAXCA1.UNICA.IT