COMBINATORIAL-ALGEBRAIC TECHNIQUES

IN GRÖBNER BASES THEORY

by

L. Cerlienco, M. Mureddu and F. Piras

Dipartimento di Matematica Università di Cagliari Via Ospedale 72 - 09124 Cagliari(Italy)

      cerlienco@vaxca1.unica.it, mureddu@vaxca1.unica.it,
                     piras@vaxca1.unica.it

§ 0. Preliminary notations and main definitions.

𝕂[X]  K[x_{1}, …, x_{n}] ≃ 𝕂^{(ℕ^{n})}

ℕ, ℤ, ℚ, ℝ, ℂ natural, integral, rational, real, complex numbers

i := (i_{1}, …, i_{n})  an arbitrary element of ℕ^{n}
i!  i_{1}! ⋯ i_{n}!
\binom{h}{i}  \binom{h_{1}}{i_{1}} ⋯ \binom{h_{n}}{i_{n}}
P, Q  arbitrary elements of ℝ^{n}

≤ the usual order on ℕ, as well as the product order it induces on ℕ^{n}

F an n-dimensional Ferrers diagram, i.e. any finite ideal of the poset N^{n}: j < i ∈ F ⟹ j ∈ F

⪯ a term-ordering on ℕ^{n}, i.e. a linear ordering which is compatible with the additive monoid structure on ℕ^{n}

⪯_{ℤ}, ⪯_{ℚ}, ⪯_{ℝ} extensions of the term-ordering ⪯ on ℕ^{n} to ℤ^{n}, ℚ^{n} and ℝ^{n}

⪯^{ℝ} a linear ordering on ℝ^{n} which is compatible with the structure of ℝ-vector space

𝕂  an arbitrary field

𝕂[x] ≃ 𝕂^{(ℕ)} the usual identification of the space 𝕂[x] of polynomials in the indeterminate x with the space 𝕂^{(ℕ)} of the finite support sequences

p(x) = ∑_{i=0}^{m} p_{i}x^{i} =

= (p_{0}, …, p_{m}, 0, …)_{−1}  an element of 𝕂[x] ≃ 𝕂^{(ℕ)}

𝕂[x]^{∗} ≃ 𝕂[[x]] ≃ 𝕂^{ℕ} the usual identification of the dual space 𝕂[x]^{∗} of 𝕂[x] with both the space 𝕂[[x]] of the formal power series and the space 𝕂^{ℕ} of all sequences

v = ∑_{i=0}^{∞} v_{i}x^{i} = (v_{i})_{i∈ℕ}  an element of 𝕂[x]^{∗} ≃ 𝕂[[x]] ≃ 𝕂^{ℕ}

E the shift operator E: 𝕂^{ℕ} → 𝕂^{ℕ}, (v_{i})_{i∈ℕ} ↦ (v_{i+1})_{i∈ℕ}

𝔸 = (𝕂[x], m, u) the usual polynomial algebra; m: 𝕂[x] ⊗ 𝕂[x] → 𝕂[x], multiplication; u: 𝕂 → 𝕂[x], unity map

B = (𝕂[x], m, u, Δ, ε) the usual polynomial bialgebra; the maps Δ (comultiplication or diagonalization) and ε (counity map or augmentation) are defined as follows:

Δ: 𝕂[x] ⟶ 𝕂[x] ⊗ 𝕂[x] ≃ 𝕂[x, y]
p(x) ↦ p(x + y),
ε: 𝕂[x] ⟶ 𝕂
p(x) ↦ p(0).
𝕂[X]  K[x_{1}, …, x_{n}] ≃ 𝕂^{(ℕ^{n})}

𝕂[x]^{∘} ⊂ 𝕂[x]^{∗} the set of all the forms in 𝕂[x]^{∗} whose kernel contains an ideal of 𝕂[x]

B^{∘} = (𝕂[x]^{∘}, Δ^{∘}, ε^{∘}, m^{∘}, u^{∘}) the dual bialgebra of the polynomial bialgebra B; the maps Δ^{∘}, ε^{∘}, m^{∘} and u^{∘} are defined as follows:

Δ^{∘}:  𝕂[x]^{∘} ⊗ 𝕂[x]^{∘}  ⟶  𝕂[x]^{∘}  (multiplication)
((v_{i})_{i∈ℕ}), (w_{j})_{j∈ℕ}) ⟼ (∑_{i+j=k} \binom{k}{i}v_{i}w_{j})_{k∈ℕ}
ε^{∘}:  𝕂  ⟶  𝕂[x]^{∘}  (unity map)
a  ↦  a(δ_{j}^{0})_{j∈ℕ}
m^{∘}:  𝕂[x]^{∘}  ⟶ 𝕂[x]^{∘} ⊗ 𝕂[x]^{∘} ⊆ 𝕂^{ℕ×ℕ} (diagonalization)
(v_{i})_{i∈ℕ}  ⟼ (w_{ij} := v_{i+j})_{(i,j)∈ℕ×ℕ}
u^{∘}:  𝕂[x]^{∘}  ⟶  𝕂  (augmentation)
(v_{i})_{i∈ℕ}  ↦  v_{0}.

𝕂[X]  K[x_{1}, …, x_{n}] ≃ 𝕂^{(ℕ^{n})}
X := {x_{1}, x_{2}, …, x_{n}}  a given set of indeterminates

𝕂[X] 𝕂[x_{1}, …, x_{n}] ≃ 𝕂^{(ℕ^{n})} the usual identification of the space 𝕂[X] of polynomials in the indeterminates x_{1}, …, x_{n} with the space 𝕂^{(ℕ^{n})} of the finite support functions ℕ^{n} → 𝕂

I, J  ideals of 𝕂[x] or 𝕂[x_{1}, …, x_{n}]

M_{X} ⊆ K[X] the free abelian monoid on

X := {x_{1}, x_{2}, …, x_{n}}

x^{i}  x^{i} := x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}} ∈ M_{X}, the terms of K[X]
p(X) = ∑ p_{i}x^{i}  an element of 𝕂[X] ≃ 𝕂^{(ℕ^{n})}

𝕂[X]^{∗} ≃ 𝕂[[X]] ≃ 𝕂^{ℕ^{n}} the usual identification of the dual space 𝕂[X]^{∗} of 𝕂[X] with both the space 𝕂[[X]] of formal power series and the space 𝕂^{ℕ^{n}} of all functions ℕ^{n} → 𝕂

f = ∑_{i∈ℕ^{n}} f_{i}x^{i} = (f_{i})_{i∈ℕ^{n}}  an element of 𝕂[X]^{∗} ≃ 𝕂[[X]] ≃ 𝕂^{ℕ^{n}}

E^{j} the shift operator E^{j}: 𝕂^{ℕ^{n}} → 𝕂^{ℕ^{n}}, (f_{i})_{i∈ℕ^{n}} ↦ (f_{i+j})_{i∈ℕ^{n}}

p(E) for p(X) = ∑ p_{i}x^{i} ∈ 𝕂[X], the operator p(E) := ∑ p_{i}E^{i} ∈ 𝕂[X]^{∗}

B_{n} = (𝕂[X], m_{n}, u_{n}, Δ_{n}, ε_{n}) the multivariate polynomial bialgebra; the definition of the maps m_{n}, u_{n}, Δ_{n}, ε_{n} is analogous to that of m, u, Δ, ε

𝕂[X]^{∘} ⊂ 𝕂[X]^{∗} the set of all the forms in 𝕂[X]^{∗} whose kernel contains a cofinite ideal of 𝕂[X]

B_{n}^{∘} = (𝕂[X]^{∘}, Δ_{n}^{∘}, ε_{n}^{∘}, m_{n}^{∘}, u_{n}^{∘}) the dual bialgebra of the multivariate polynomial bialgebra B_{n}

v_{P} v_{P}: 𝕂[X] → 𝕂, p ↦ p(P), the evaluation map at the point P ∈ 𝕂^{n}:

D_{i} the linear map D_{i}: 𝕂[X] → 𝕂[X] , x^{h} ↦ \binom{h}{i}x^{h−i}; we have the formula D_{i}(fg) = ∑_{h+k=i} D_{h}(f)D_{k}(g). Moreover, when the field 𝕂 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}}}.

v_{P}^{i} the composition v_{P} ∘ D_{i}, i.e. v_{P}^{i}: 𝕂[X] → 𝕂 , p ↦ (D_{i}p)(P)

℘ {(P_{1}, F_{1}), …, (P_{N}, F_{N})} each element (P_{j}, F_{j}) ∈ ℘ consists of a point P_{j} of ℝ^{n} together with an n-dimensional Ferrers diagram F_{j} ⊂ ℕ^{n}

(P, i) ∈ ℘ this notation stands for P = P_{j} and i ∈ F_{j} for some j ∈ {1, …, N}

ℑ(℘) the cofinite ideal

ℑ(℘) := {p ∈ 𝕂[X] | (∀j)(∀i ∈ F_{j}) (v_{P_{j}}^{i}(p) = 0)}
associated to ℘ = {(P_{1}, F_{1}), …, (P_{N}, F_{N})}

§ 1. Introduction.

1.1 Since the generalization to the multivariate case of the notion of linearly recursive sequence (l.r.s.) plays a big part in what follows, it is convenient to assume this notion as a starting-point.

Let us recall that a sequence v = (v_{i})_{i∈ℕ}, is said to be a I-l.r.s., I ideal of 𝕂[x], if, for every p ∈ I, we have p(E)(v) = 0 (E shift operator). Every element p ∈ I is said to be a characteristic polynomial and the generator g of I = (g) the minimal polynomial of the I-l.r.s. v.

An I-l.r.s. v is completely determined by its minimal polynomial g and by its initial values v_{i}, 0 ≤ i < k = deg(g), that is the values which the form v takes on the monomials x^{0}, …, x^{k−1} whose residue classes form a linear basis — in fact, the smallest one (among all monomial bases) with respect to the usual order on monomials — of the quotient algebra 𝕂[x]/I. As a consequence, the set S(I) of all the I-l.r.s. is a k-dimensional 𝕂-vector space (k = deg(g), I = (g)). Morover, S(I) is a cyclic 𝕂[x]-submodule of the 𝕂[x]-module 𝕂[x]^{∗}, where the scalar product is defined by 𝕂[x] × 𝕂[x]^{∗} ⟶ 𝕂[x]^{∗}, (p, v) ⟼ p(E)(v) (equivalently, (p, v) ⟼ [q ↦ v(pq)]). A generator of S(I) as 𝕂[x]-module is any I-l.r.s. v = (v_{i}) such that no proper divisor of the generator g of I is a characteristic polynomial for v; for instance, the I-l.r.s. v whose first k terms are v_{0} = v_{1} = ⋯ = v_{k−2} = 0, v_{k−1} = 1.

1.2 Peterson and Taft [1] showed that the set 𝕂[x]^{∘} = ⋃ S(I) (I cofinite ideal) of all l.r.s. is the underlying set of the dual bialgebra B^{∘} of the usual polynomial bialgebra B.

In [2], the authors of the present note assumed the same bialgebraic point of view in order to generalize to the multivariate case the notion of Il.r.s.. Let now B_{n} = (𝕂[X], m_{n}, u_{n}, Δ_{n}, ε_{n}) be the multivariate polynomial bialgebra. The elements of the dual bialgebra B_{n}^{∘} ⊂ 𝕂[X]^{∗} are precisely those linear forms f : 𝕂[X] → 𝕂 whose kernel contains a cofinite ideal I ⊆ 𝕂[X], that is an ideal I such that dim(𝕂[X]/I) < ∞. Any such form f is called an I-linearly recursive function.

Contrary to the univariate case, in the present one a few calculation problems arise, due essentially to the simultaneous apparence of three new facts: (i) 𝕂[X] is not a principal domain, (ii) not every ideal of 𝕂[X] is cofinite and (iii) there are infinitely many different term orderings ⪯ on the monoid M_{X} ⊂ 𝕂[X].

1.3 The previous remarks require some more words. Let us consider the fact that in order to give in an effective way a linearly recursive function f = ∑_{i∈ℕ^{n}} f_{i}x^{i} ∈ B_{n}^{∘} we need (a) a cofinite ideal I = (g_{1}, …, g_{s}) ⊆ 𝕂[X] and (b) a monomial basis (x^{j} + I)_{j∈L}, L ⊆ ℕ^{n}, for the quotient algebra 𝕂[X]/I. In fact, the I-linearly recursive function f is completely determined by its “initial values” f_{j}, j ∈ L, all the other values f_{i}, i ∉ L, being computed by means of the generators g_{1}, …, g_{s} of the ideal I. The idea is to use g_{1}, …, g_{s} as “scales of recurrence”.

Nevertheless, in practice this is not yet enough. What we really need is (a′) a reduced Gröbner basis RGB(I) = (h_{1}, …, h_{t}) for the ideal I relative to the fixed term ordering ⪯ and (b′) a monomial basis (x^{j} + I)_{j∈L} which is minimal with respect to ⪯, that is a basis (x^{j}+I)_{j∈L} = {x^{j_{1}} +I, …, x^{j_{h}} +I}, with x^{j_{1}} ≺ x^{j_{2}} ≺ … ≺ x^{j_{h}}, such that for every other monomial basis (x^{j′} +I)_{j′∈L′} = {x^{j′^{1}} +I, …, x^{j′^{h}} +I}, with x^{j′^{1}} ≺ x^{j′^{2}} ≺ … ≺ x^{j′^{h}}, we have x^{j_{r}} ≺ x^{j′^{r}} for every r = 1, …, h. It is easy to check that a monomial basis (x^{j} + I)_{j∈L} is a minimal monomial basis only if L ⊆ ℕ^{n} is an n-dimensional Ferrers diagram.

Notice that the minimal (with respect to ⪯) monomial basis (x^{j} +I)_{j∈L} is determined by RGB(I) = (h_{1}, …, h_{t}) in the following way. Let x^{j_{r}}, r = 1, …, t, be the leading term (with respect to ⪯) of the polynomial h_{r} ∈ RGB(I) and let \overline{L} ⊆ ℕ^{n} be the poset filter of ℕ^{n} (ordered by the usual product order ≤) generated by j_{1}, …, j_{t}; then L is the complementary ideal L = ℕ^{n} \ \overline{L}.

1.4 The above remarks seemingly indicate that Gröbner bases theory be able to satisfy our computational needs. Unfortunatly, that theory provides no device to make sure in advance whether a given set of polynomials (g_{1}, …, g_{s}) generates a cofinite ideal. In [3] (see also [4]) a combinatorial algorithm producing cofinite ideals is described. More precisely, given a finite set ℘ := {(P_{1}, F_{1}), …, (P_{N}, F_{N})} (P_{j} ∈ 𝕂^{n}; F_{j} ⊂ ℕ^{n} is n-dimensional Ferrers diagram), it is not difficult to prove that the set

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

associated to {v_{P}^{i} | (P, i) ∈ ℘} ⊂ 𝕂^{ℕ^{n}} is a cofinite ideal. Notice that codim(ℑ(℘)) = ∑_{j=1}^{N} #F_{j} and that {P_{1}, …, P_{N}} is the affine variety of ℑ(℘). The algorithms described in [3] produce first the monomial basis for 𝕂[x]/ℑ(℘) which is minimal with respect to the inverted lexicographical order ⪯_{i.l.} and then a reduced Gröbner basis of ℑ(℘).

1.5 Bearing in mind on the one hand that the forms v_{P}^{i} , P ∈ 𝕂^{n}, i ∈ ℕ^{n}, are a linear basis of the dual bialgebra B_{n}^{∘} (see [2], Prop. 6 and its Corollary) and on the other hand that not every cofinite ideal I is of the form ℑ(℘), the following question naturally arises: under what general conditions a system of independent linear combinations of forms v_{P}^{i} may generate a subspace H ⊂ B_{n}^{∘} which determines a cofinite ideal I as the maximal ideal contained in the kernel of all the forms in H (in other words, H = S(I) for some cofinite ideal I ⊂ 𝕂[X])? For instance, it is easy to prove that H must be both a finitely generated 𝕂[X]-submodule of the 𝕂[X]-module 𝕂[X]^{∗} and a finite dimensional 𝕂-subspace of 𝕂[X]^{∘}. The search for such necessary and sufficient conditions is a matter of a work-in-progress by Cerlienco and Mureddu.

1.6 From a more general point of view, analogous questions can be asked for general (i.e. not necessarily cofinite) ideals. This led Piras [5] to the notion of Macaulay’s inverse system. This notion has been introduced by F. S. Macaulay [7] in the attempt to find linear conditions for solving the Ideal Membership Problem for a polymomial in ℂ[x_{1}, …, x_{n}].

According to Macaulay (yet he made use of a very cumbersome old-style language) the inverse system of an ideal I is the space of all the ℂ-linear forms f: ℂ[x_{1}, …, x_{n}] → ℂ whose kernel contains I. An immediate consequence of this definition is that the inverse system of an ideal I is isomorphic, as a ℂ-vector space, to the linear dual of ℂ[x_{1}, …, x_{n}]/I. Therefore the dimension of the inverse system (in the original sense of Macaulay) of a non-cofinite ideal I is strictly greater than the dimension of ℂ[x_{1}, …, x_{n}]/I, which is countable.

This trivial observation points to a contradiction in the theory of inverse systems as developed by Macaulay. In fact Macaulay has given an incorrect proof of two propositions (cfr. [7] p. 75 and p. 91) which imply that the dimension of an inverse system is at most countable. These two propositions played a central role in Macaulay’s construction and their falsity would have devastating effects on the theory of inverse systems. However, the two properties seem to hold for proper subspaces of an inverse system. This fact has led Piras to modify Macaulay’s definition in order to recover his main results. This modified definition of inverse system, as well as its main properties, are the subject of §2.

1.7 In the Gröbner bases computational framework, another question which has a combinatorial flavour naturally arises. When we are looking for a Gröbner basis for a given ideal, we have previously to fix a term ordering ⪯ on ℕ^{n}. Moreover, in the applications some particular term ordering is often needed. In the usual computer algebra systems which contain a Gröbner bases package (for instance, Maple, Mathematica, Reduce, Macaulay; see [12, Appendix C], [13]) only a few term orderings are allowed. This is, at the best of our knowledge, because a convenient representation of term orderings is not known. Even the interesting results of Robbiano [14] are not completely satisfactory from our point of view; in particular, Robbiano’s representation does not permit an easy comparison between two such representations in order to decide whether they both represent the same term ordering (or not). In §3 a handy canonical representation of term orderings by which all these problems can be easily solved is given.

§ 2. Inverse systems.

2.1 We will consider 𝕂[X]^{∗} with its 𝕂[X]-module structure defined by 𝕂[X] × 𝕂[X]^{∗} → 𝕂[X]^{∗}, (p, f) ↦ p·f, where p·f = p(E)(f), equivalently, (p·f)(q) = f(pq). If Y ⊆ 𝕂[X]^{∗} we will put

P(Y) = {p ∈ 𝕂[X] | p·f = 0 for all f ∈ Y }.

Let I be an ideal of 𝕂[X]. Any submodule H of 𝕂[X]^{∗} such that P(H) = I will be said an inverse system of I. According to Macaulay (see [7], p. 68) \underline{the} inverse system of the ideal I is the set

S(I) = {f ∈ 𝕂[X]^{∗} | (p·f)(1) := f(p) = 0 for every p ∈ I} .

S(I) is also an inverse system according to our definition.

Prop. 1 S(I) is a 𝕂[X]-submodule of 𝕂[X]^{∗} which is an inverse system according to our definition as well, i. e. P(S(I)) = I. Moreover, S(I) is a 𝕂-vectorspace isomorphic to the dual 𝕂-vectorspace of 𝕂[X]/I. □

From Prop. 1 we deduce:

• S(I) is a finite-dimensional vector space iff I is a cofinite ideal. When I is not cofinite, S(I) has non-countable dimension.

• With respect to a fixed term ordering on 𝕂[X], let us denote by Lt(I) the ideal of 𝕂[X] generated by the leading terms of the elements of I; an element f of S(I) is fully determined by its values on the monomials x^{i} ∉ Lt(I), since the (x^{i} + I)’s are a basis for 𝕂[X]/I.

The last remark allows us to describe some families of elements of S(I) that generate inverse systems with countable dimension as vectorspaces. For instance, consider the family of linear forms

R_{L} = {f_{i} | f_{i}(x^{j}) = δ_{i}^{j} and i, j ∈ L} ⊆ S(I)

(where L = {i ∈ ℕ^{n} | x^{i} ∉ Lt(I)}, and δ_{i}^{j} = δ_{i_{1}}^{j_{1}} ⋯ δ_{i_{n}}^{j_{n}} is the multivariate Kronecker symbol).

Prop. 2 For every polynomial p ∈ 𝕂[X] and every form f_{i} ∈ R_{L} we have:

p ≡ ∑_{i∈L} f_{i}(p)x^{i}  (mod I).  □

Note that using Prop. 2 we can easily compute the values of the functionals f_{i}. For every j ∈ ℕ^{n}, f_{i}(x^{j}) is the coefficient of x^{i} in the remainder of x^{j} on division by the reduced Gröbner basis with respect to the fixed monomial ordering (i. e. f_{i}(x^{j}) = a_{i} where x^{j} ≡ ∑_{i∈L} a_{i}x^{i} (mod I)).

Corollary 1. The 𝕂[X]-module H_{L}, generated by R_{L}, is an inverse system of the ideal I.

Corollary 2. f ∈ S(I) if and only if f = ∑_{i∈L} f(x^{i})f_{i}.

Corollary 3. Let I be a cofinite ideal of 𝕂[X]; then S(I) = H_{L}.

An equivalent statement of the following proposition has been first stated by Macaulay in [7], p. 91. Unfortunately, Macaulay’s proof is not fully satisfactory. A correct proof is given in [6].

Prop. 3 For every ideal I ⊆ 𝕂[X], there is an inverse system which is finitely generated as 𝕂[X]-module. □

In particular, it can be proved that every irreducible ideal has a cyclic inverse system.

2.2 In this section we generalize the results in 2.1 to the case of some power 𝕂[X]^{l}. The 𝕂-vectorspace 𝕂[X]^{l} and (𝕂[X]^{∗})^{l} will be regarded also as 𝕂[X]-modules. The scalar product is given by

\begin{matrix}𝕂[X] × 𝕂[X]^{l} & ⟶ 𝕂[X]^{l} \\ (p, (p_{1}, …, p_{l})) & ⟼ (pp_{1}, …, pp_{l}) \end{matrix}

and, respectively, by

\begin{matrix}𝕂[X] × (𝕂[X]^{∗})^{l} & ⟶ (𝕂[X]^{∗})^{l} \\ (p, (f_{1}, …, f_{l})) & ⟼ (p·f_{1}, …, p·f_{l}). \end{matrix}

For every Y ⊆ (𝕂[X]^{∗})^{l}, we put

P(Y) = {(p_{1}, …, p_{l}) ∈ 𝕂[X]^{l} | p_{1}·f_{1} + ⋯ + p_{l}·f_{l} = 0

for all (f_{1}, …, f_{l}) ∈ Y }.

P(Y) is clearly a submodule of 𝕂[X]^{l}; conversely, we want to show that for every submodule M of 𝕂[X]^{l} there is a subset Y of (𝕂[X]^{∗})^{l} such that P(Y) = M. Any such subset Y will be called an inverse system of the submodule M.

For the purposes of our discussion here, we first denote by e_{j}(p) the element (0, …, p, …, 0) of 𝕂[X]^{l}. Moreover, denote by G the reduced Gröbner basis of M with respect to a fixed term ordering ⪯ on 𝕂[X]^{l} and by Red_{⪯}(p_{1}, …, p_{l}) the unique element obtained by reducing (p_{1}, …, p_{l}) modulo G. (Concerning Gröbner bases theory relative to polynomial modules see [8].) The set

{e_{j}(x^{p}) + M | e_{j}(x^{p}) ∉ Lt(M)}

(where Lt(M) is the 𝕂[X]-module generated by the leading terms of the elements of M) is a basis of the 𝕂-vectorspace 𝕂[X]^{l}/M. Let

L = {(p, j) ∈ ℕ^{n} × {1, …, l} | e_{j}(x^{p}) ∉ Lt(M)} .

For every (p, j) ∈ L and every 1 ≤ i ≤ l, let f_{p,i}^{j} be the 𝕂-linear map from 𝕂[X] to 𝕂 defined by

(1)  f_{p,i}^{j}(p) = coeff. of (e_{j}(x^{p}) + M) occurring in (e_{i}(p) + M).

Prop. 4 Let R_{L}(M) be the submodule of (𝕂[X]^{∗})^{l} generated by the ltuples (f_{p,1}^{j}, …, f_{p,l}^{j}), (p, j) ∈ L. Then R_{L}(M) is an inverse system of the submodule M, i. e. P(R_{L}(M)) = M.

Proof: See [6]. □

Next we describe the maximal inverse system of the submodule M ⊆ 𝕂[X]^{l}. Let ⟨(q_{1,1}, …, q_{1,l}), …, (q_{k,1}, …, q_{k,l})⟩ be a system of generators of M and let S(M) be the set of the l-tuples (f_{1}, …, f_{l}) of (𝕂[X]^{∗})^{l} which are solutions of the linear system:

(2)  \{ \begin{matrix}q_{1,1}·w_{1}+ & & ⋯ & & & +q_{1,l}·w_{l} & & & = & & 0 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ q_{k,1}·w_{1}+ & & ⋯ & & & +q_{k,l}·w_{l} & & & = & & 0. \end{matrix}

Prop. 5 For every submodule M of 𝕂[X]^{l}, we have

(f_{1}, …, f_{l}) ∈ S(M) ⟺ (∀i) (f_{i} = ∑_{(p,j)∈L} f_{j}(x^{p})f_{p,i}^{j}) .

Thus, P(S(M)) = M.

Proof: See [6]. □

This proposition enables us to compute the general solution of the system (2). It is of the form

( ∑_{(p,j)∈L} b_{p,j}f_{p,1}^{j}, …, ∑_{(p,j)∈L} b_{p,j}f_{p,l}^{j}).

where the linear forms f_{p,i}^{j} are defined as in (1) and (b_{p,j})_{(p,j)∈L} is an arbitrary family of elements of 𝕂.

When 𝕂 is a field of characteristic zero, the same result can be also used for computing the solutions of a homogeneous system of linear partial differential equations with constant coefficients:

(3)  \{ \begin{matrix}q_{1,1}(\frac{∂}{∂u_{1}} , …, \frac{∂}{∂u_{n}})φ_{1} + ⋯ + q_{1,l}(\frac{∂}{∂u_{1}} , …, \frac{∂}{∂u_{n}})φ_{l} = 0 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ q_{k,1}(\frac{∂}{∂u_{1}} , …, \frac{∂}{∂u_{n}})φ_{1} + ⋯ + q_{k,l}(\frac{∂}{∂u_{1}} , …, \frac{∂}{∂u_{n}})φ_{l} = 0. \end{matrix}

In fact, making use of Prop. 6 below, it is sufficient to observe that system (2) is mapped into (3) by the 𝕂-linear isomorphism

E : 𝕂[X]^{∗} ⟶ 𝕂[[u]]
f ⟼ ∑_{h} f(x^{h})\frac{u^{h}}{h!} .

Prop. 6 Let 𝕂 be a field of characteristic zero. For every polynomial p = ∑_{i} a_{i}x^{i} ∈ 𝕂[X] and every linear form f ∈ 𝕂[X]^{∗} we have:

E(p·f) = (∑_{i} a_{i} \frac{∂^{|i|}}{∂u^{i}} )(E(f)), |i| = i_{1} + ⋯ + i_{n}.

Proof: See [6]. □

In explicit terms, if M is the 𝕂[X]-module generated by the set

{(q_{1,1}, …, q_{1,l}), …, (q_{k,1}, …, q_{k,l})},

then we have

q_{1,1}(\frac{∂}{∂u_{1}} , …, \frac{∂}{∂u_{n}})(∑_{h} f_{1}(x^{h})\frac{u^{h}}{h!} )

+ ⋯ + q_{1,l}(\frac{∂}{∂u_{1}} , …, \frac{∂}{∂u_{n}})(∑_{h} f_{l}(x^{h})\frac{u^{h}}{h!} ) = 0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

q_{k,1}(\frac{∂}{∂u_{1}} , …, \frac{∂}{∂u_{n}})(∑_{h} f_{1}(x^{h})\frac{u^{h}}{h!} )

+ ⋯ + q_{k,l}(\frac{∂}{∂u_{1}} , …, \frac{∂}{∂u_{n}})(∑_{h} f_{l}(x^{h})\frac{u^{h}}{h!} ) = 0,

if and only if (f_{1}, …, f_{l}) ∈ S(M). Thus, the general solution of (3) is

(∑_{h}( ∑_{(p,j)∈B} b_{p,j}f_{p,1}^{j}(x^{h}))\frac{u^{h}}{h!} , …, ∑_{h}( ∑_{(p,j)∈B} b_{p,j}f_{p,l}^{j}(x^{h}))\frac{u^{h}}{h!} ) .

§ 3. Canonical matrix representation of term orderings.

3.1 Let ⪯ be a term ordering on ℕ^{n}, that is a linear order which is compatible with the monoid structure of ℕ^{n}: 0 ⪯ i, i ≺ j ⇒ i+h ≺ j+h. It is easily seen that ⪯ can be uniquely extended to a linear order on ℤ^{n} (resp.: ℚ^{n}) compatible with the structure of ℤ-module (resp.: ℚ-vectorspace).

It can be also proved (see [11]) that any term ordering ⪯ is the restriction to ℕ^{n} of at least one linear order ⪯^{ℝ} on ℝ^{n} which is compatible with the structure of ℝ-vectorspace. In the following, such an order will be simply referred as a c.l.order. As an example, consider the c.l.order ⪯\overline{b} determined by a given basis \overline{b} = (b_{1}, …, b_{n}) of ℝ^{n} in the following way:

P ≺\overline{b} Q ⟺ ( α^{1} ; ⋮ ; α^{n} ) ≺_{lex} ( β^{1} ; ⋮ ; β^{n} )

where P = ∑_{i=1}^{n} α^{i}b_{i}, Q = ∑_{i=1}^{n} β^{i}b_{i} and ⪯_{lex} is the usual lexicographic order.

Equivalently,

P ≺\overline{b} Q ⟺ CP ≺_{lex} CQ

where C^{−1} = B = (b_{j}^{i})_{(i,j)∈n^{2}} with b_{j} = (b_{j}^{i})_{i∈n} and n = {1, …, n}. It is not difficult to check that two different bases \overline{b} = (b_{1}, …, b_{n}), \overline{b}′ = (b′_{1}, …, b′_{n}) determine the same c.l.order (⪯\overline{b} = ⪯\overline{b}′) iff

B′ = B · Λ (equivalently, C′ = Λ^{−1}C)

where Λ = (λ_{j}^{i}) is a lower triangular matrix with λ_{i}^{i} > 0.

The following fundamental result is due to Erdős [9] (see also [10], [11]).

Theorem (Erdős) Let ⪯^{ℝ} be a c.l.order on ℝ^{n}; then, there is a basis (in fact, infinitely many bases) \overline{b} = (b_{1}, …, b_{n}) of ℝ^{n} such that ⪯^{ℝ} = ⪯\overline{b} .

In other words, (i) any c.l.order ⪯^{ℝ} on ℝ^{n} can be represented by a non-singular matrix C for which we have

(4)  P ≺^{ℝ} Q ⟺ CP ≺_{lex} CQ,

and (ii) any two matrices C, C′ which represent the same c.l.order ⪯^{ℝ} satisfy the equivalence relation

(5)  C′ = Λ^{−1}C.

We want to determine a canonical matrix representation of ⪯^{ℝ}. To this aim, let us define a lexicographic matrix to be an m by n matrix A = (a_{j}^{i}) (m ≤ n) of the form

( \begin{matrix}0 & … & 0 & ±1 & ∗ & ∗ & … & ∗ \\ 0 & … & 0 & 0 & 0 & ±1 & … & ∗ \\ 0 & … & ±1 & 0 & ∗ & 0 & … & ∗ \\ · & … & · & · & · & · & … & · \\ ±1 & … & 0 & 0 & ∗ & 0 & … & ∗ \\ 0 & … & 0 & 0 & ±1 & 0 & … & ∗ \end{matrix} ) ,

that is a matrix satisfying the following conditions: (a) in each row of A there is at least one non-zero entry; (b) if we denote by a_{j(i)}^{i} the first nonzero entry in the i-th row of A, then a_{j(i)}^{i} is either 1 or −1; (c) for each i = 1, …, n and for each i′ > i we have a_{j(i)}^{i′} = 0. Notice that the rank of a m × n lexicographic matrix A is m.

Prop. 7 For every c.l.order ⪯^{ℝ} on ℝ^{n}, there is one and only one n × n lexicographic matrix C for which (4) is true.

Proof: The statement is a straightforward consequence of the Erdős Theorem and of (5). □

3.2 Consider now a term ordering ⪯ on ℚ^{n}. Let ⪯^{ℝ} be any c.l.order on ℝ^{n} whose restriction is ⪯. Let \overline{b} = (b_{1}, …, b_{n}), B = (b_{j}^{i}), C = (c_{j}^{i}) = B^{−1} and Λ have the same meaning as in 3.1.

Let T_{n−i} := (b_{i+1}, …, b_{n}) ⊆ ℝ^{n} =: T_{n}, that is the (n − i)–dimensional subspace defined by the linear system

\{ \begin{matrix}c_{1}^{1}x^{1} + ⋯ + c_{n}^{1}x^{n} = 0 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ c_{1}^{i}x^{1} + ⋯ + c_{n}^{i}x^{n} = 0 \end{matrix} ,  ( x^{1} ; ⋮ ; x^{n} ) ∈ ℝ^{n}.

Observe that the hyperplane π_{i+1} := (b_{1}, … b_{i}, b_{i+2}, …, b_{n}) ⊆ ℝ^{n} (whose equation is c_{1}^{i+1}x^{1} + ⋯ + c_{n}^{i+1}x^{n} = 0) divides T_{n−i} into three parts: the intersection T_{n−i−1} = T_{n−i} ∩ π_{i+1} and the two half-spaces T_{n−i}^{+}, T_{n−i}^{−} each of which contains only positive, resp. negative points.

When passing from ⪯^{ℝ} to ⪯, it may happen that all rational points of T_{n−i} belong to π_{i+1} as well, so that

∑ c_{j}^{1}x^{j} = … = ∑ c_{j}^{i}x^{j} = 0 ⇒ ∑ c_{j}^{i+1}x^{j} = 0

for every rational point (x^{1}, …, x^{n})_{−1} ∈ ℚ^{n} or, which is the same, the two n-tuples of vectors

( c_{1}^{1} ; ⋮ ; c_{1}^{i} ) , …, ( c_{n}^{1} ; ⋮ ; c_{n}^{i} )

and

( c_{1}^{1} ; ⋮ ; c_{1}^{i} ; c_{1}^{i+1} ) , …, ( c_{n}^{1} ; ⋮ ; c_{n}^{i} ; c_{n}^{i+1} )

have the same rational dimension. In this case, when you are interested to rational points alone, the information contained in the (i + 1)-th row of the matrix C is useless, so that we can harmlessly cut that row off. From this and from Prop. 7 we deduce the following results.

Prop. 8 Let C = (c_{j}^{i}) be an m × n matrix (m ≤ n) and let ⪯ be the order on ℕ^{n} defined by

(6)  i ≺ j ⟺ Ci ≺_{lex} Cj  ∀i, j ∈ ℕ^{n}.

Then, ⪯ is a term ordering iff the columns of C are rationally independent.□

Prop. 9 For every term ordering ⪯ on ℕ^{n}, there is one and only one m × n lexicographic matrix C = (c_{j}^{i}) satisfying (6) such that for every i = 1, …, m − 1 the rational dimension of the vectors

( c_{1}^{1} ; ⋮ ; c_{1}^{i} ) , …, ( c_{n}^{1} ; ⋮ ; c_{n}^{i} )

is strictly less than the rational dimension of the vectors

( c_{1}^{1} ; ⋮ ; c_{1}^{i} ; c_{1}^{i+1} ) , …, ( c_{n}^{1} ; ⋮ ; c_{n}^{i} ; c_{n}^{i+1} ) .

□

3.3 Let ⪯ be the term ordering on ℕ^{n} represented by the m × n matrix

Ĉ = ( \begin{matrix}c_{1}^{ι_{1}} & … & c_{n}^{ι_{1}} \\ · & … & · \\ c_{1}^{ι_{m}} & … & c_{n}^{ι_{m}} \end{matrix} ) (m ≤ n).

For h = 1, …, m, let us denote by d_{h} the rational dimension of the n vectors

(7)  ( c_{1}^{ι_{1}} ; ⋮ ; c_{1}^{ι_{h}} ) … ( c_{n}^{ι_{1}} ; ⋮ ; c_{n}^{ι_{h}} ) .

We shall say that the matrix Ĉ is rationally reduced if d_{1} < d_{2} < … < d_{m} = n. It is clear that any matrix can be rationally reduced by cutting a few suitable rows off from it.

We give now an algorithm which associates a rationally reduced lexicographic matrix C̃ to any matrix Ĉ. This matrix C̃ is said to be the canonical lexicographic representation of the term ordering ⪯. Indeed, it can be proved (see [11]) that two different matrices Ĉ and D̂ represent the same term ordering on ℕ^{n} iff C̃ = D̃.

It is convenient to divide our algorithm into two parts. The first part is aimed to “capture” a c.l.order ⪯^{ℝ} (in fact, the most suitable one for our purposes) whose restriction to ℕ^{n} is ⪯; it consists in constructing an n × n matrix C = (c_{j}^{i}) by putting n − m new rows inside those of Ĉ, as described below. The second part of the algorithm consists in (i) reducing C in its lexicographic form C′ and then (ii) cutting the rows whose indices are different from 1, d_{1} + 1, …, d_{m−1} + 1 off from C′.

Without loss of generality we may assume that the given matrix Ĉ is rationally reduced and also that, for each h = 1, …, m, the first d_{h} vectors in (7) are rationally independent.

The first part of the algorithm is described by recursion on h ∈ {1, …, m}. For h = 1, simply put c_{j}^{1} = c_{j}^{ι_{1}}, j = 1, …, n. For h > 1, let

(8)  ( \begin{matrix}c_{1}^{1} & … & c_{n}^{1} \\ · & … & · \\ c_{1}^{i_{h−1}} & … & c_{n}^{i_{h−1}} \end{matrix} )

be the rows of C already determined. At this stage we have: (a) i_{h−1} = d_{h−2} + 1 (here we are conventionally assuming d_{0} := 0); (b) the columns in (8) whose indices are greater than d_{h−1} rationally depend on the first d_{h−1} columns (which are rationally independent). We add to the matrix (8) the d_{h−1} − d_{h−2} new rows (c_{j}^{i_{h−1}+1}), …, (c_{j}^{i_{h}}) chosen as follows. The first k := d_{h−1}−d_{h−2}−1 of these rows form the lexicographic matrix Γ for which:

(a) the entries of the first d_{h−2} +1 columns of Γ are zero; (b) the subsequent k = d_{h−1} − d_{h−2} − 1 columns form the k × k matrix (a_{s}^{r} := δ_{k−s+1}^{r}) (δ_{t}^{r} Kronecker symbol); (c) the columns whose indices are greater than d_{h−1} must satisfy the same rational relations which hold for the columns of (8). Finally, we put c_{j}^{i_{h}} := c_{j}^{ι_{h}} (j = 1, …, n; i_{h} = d_{h−1} + 1).

References

[1] B. Peterson, E.J. Taft, The Hopf algebra of linearly recursive sequences, Aeq. Math. 20 (1980), 1-17

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

[3] L. Cerlienco, M. Mureddu, From algebraic sets to monomial linear bases by means of combinatorial algorithms, Discrete Math. 139 (1995) (also in the “Actes du 4^{e} Colloque Séries formelles et combinatoire algébrique, Montréal, 1992)

[4] L. Cerlienco, M. Mureddu, Algoritmi combinatori per l’interpolazione polinomiale in dimensione ≥ 2, Publ. I.R.M.A. Strasbourg, 1993, 461/S-24 Actes 24^{e} Séminaire Lotharingien, p.39-76

[5] F. Piras, Some remarks on Macaulay’s inverse systems, Abstracts of the Talks of the “3rd International Symposium on effective methods in algebraic geometry”, Santander (Spain), April 5–9,1994

[6] F. Piras, Duals of polynomial modules and derivations in the formal power series algebras, Rapporto interno n. 13, Dipartimento di Matematica, Cagliari (1994)

[7] F. S. Macaulay. The Algebraic Theory of Modular Systems, Cambridge Univ. Press, Cambridge, 1916.

[8] H. M. Möller, F. Mora. New Constructive Methods in Classical Ideal Theory, J. of Alg. 100 (1986), 138-178.

[9] J. Erdős, On the structure of ordered real vector spaces, Publ. Math. Debrecen, 4 (1956), 334-343

[10] L. Fuchs, Partially Ordered Algebraic Systems, Pergamon Press, 1994 [11] L. Cerlienco, M. Mureddu, Rappresentazione matriciale degli ordini l.c.

su ℝ^{n} e su ℕ^{n}, Rapporto interno n. 16, Dipartimento di Matematica, Cagliari (1994)

[12] D. Cox, J. Little, D. O’Shea, Ideals, Varieties and Algorithms, Springer-Verlag, New York, 1992

[13] M.Stillman, M.Stillman, D.Bayer Macaulay User Manual, 1994

[14] L.Robbiano, Term Orderings on the Polynomial Ring, Proceedings of EUROCAL 85. Springer Lec. Notes Comp. Sci. 204, 513–517

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