%File Tex \input amssym.def \input amssym \magnification=1200 \hsize 11.55cm \hoffset .8cm \let\sy\Bbb \overfullrule=0pt \font\tit=cmr10 scaled \magstep3 \font\aut=cmr10 scaled \magstep2 \font\dip=cmr12 \def\nn{{\sy N}} \def\zz{{\sy Z}} \def\qq{{\sy Q}} \def\rr{{\sy R}} \def\kk{{\sy K}} \def\aa{{\sy A}} \def\aan{{{\sy A}_n}} \def\po{\kk[x]} \def\su{\kk[x]^*} \def\pon{\kk[X]} \def\sun{\kk[X]^*} \def\s#1{#1^\perp} \def\sr{$I$-l.r.s.} \def\qed{\ifhmode\unskip\nobreak\fi\ifmmode\ifinner\else\hskip5truept\fi\fi \hfill\hbox{$\square$}} \hbox{} \vskip0.5in plus 5pt minus 5pt \centerline{COMBINATORIAL-ALGEBRAIC TECHNIQUES} \vskip5pt plus 2pt minus 2pt \centerline{IN GR\"OBNER BASES THEORY} \vskip20pt plus 4pt minus 4pt \centerline{\tenrm by} \vskip5pt plus 2pt minus 2pt \centerline{\bf L. Cerlienco, M. Mureddu and F. Piras} \vskip8pt plus 2pt minus 2pt \centerline{Dipartimento di Matematica} \centerline{Universit\`{a} di Cagliari} \centerline{Via Ospedale 72 - 09124 Cagliari(Italy)} \vskip4pt plus 2pt minus 2pt \centerline{\tt cerlienco@vaxca1.unica.it, mureddu@vaxca1.unica.it,} \centerline{\tt piras@vaxca1.unica.it} \vskip30pt plus 5pt minus 5pt \noindent \S\ {\bf 0}. \indent {\bf Preliminary notations and main definitions.} \bigskip \halign{#\hfil\quad&\vtop{\hsize 7cm \noindent\strut\parindent=0pt #\hfil}\cr $\pon$&$K[x_1,\ldots ,x_n]\simeq{\kk}^{(\nn^n)}$\cr \noalign{\medskip} $\nn$, $\zz$, $\qq$, $\rr$, $\sy C$&natural, integral, rational, real, complex numbers\cr \noalign{\medskip} ${\bf i}:=(i_1,\ldots ,i_n)$&an arbitrary element of $\nn^n$ \cr \noalign{\medskip} ${\bf i!}$&$i_1!\cdots i_n!$\cr \noalign{\medskip} ${{\bf h}\choose {\bf i}}$&${ h_1\choose i_1}\cdots { h_n\choose i_n}$ \cr \noalign{\medskip} ${\bf P},{\bf Q}$&arbitrary elements of $\rr^n$ \cr \noalign{\medskip} $\leq$ &the usual order on $\nn$, as well as the product order it induces on $\nn^n$ \cr \noalign{\medskip} ${\cal F}$&an {\it n-dimensional Ferrers diagram}, i.e. any finite ideal of the poset ${\bf N}^n$: $\;$ ${\bf j}<{\bf i}\in {\cal F}\Longrightarrow {\bf j}\in {\cal F}$ \cr \noalign{\medskip} $\preceq$&a {\it term-ordering} on $\nn^n$, i.e.\ a linear ordering which is compatible with the additive monoid structure on $\nn^n $\cr \noalign{\medskip} $\preceq_\zz$, $\preceq_\qq$, $\preceq_\rr$&extensions of the term-ordering $\preceq$ on $\nn^n$ to $\zz^n$, $\qq^n$ and $\rr^n$\cr \noalign{\medskip} $\preceq^\rr$&a linear ordering on $\rr^n$ which is compatible with the structure of $\rr$-vector space\cr \noalign{\medskip} $\kk$&an arbitrary field\cr \noalign{\medskip} $\po\simeq{\kk}^{(\nn)}$&the usual identification of the space $\po$ of polynomials in the indeterminate $x$ with the space ${\kk}^{(\nn)}$ of the finite support sequences \cr \noalign{\medskip} $p(x)=\sum_{i=0}^m p_ix^i=$&\cr $=(p_0,\ldots,p_m,0,\ldots)_{-1}$&an element of $\po\simeq{\kk}^{(\nn)}$\cr \noalign{\medskip} $\su\simeq\kk[[x]]\simeq{\kk}^{\nn}$&the usual identification of the dual space $\su$ of $\kk[x]$ with both the space $\kk[[x]]$ of the formal power series and the space ${\kk}^{\nn}$ of all sequences\cr \noalign{\medskip} $v=\sum_{i=0}^\infty v_ix^i=(v_i)_{i\in\nn}$&an element of $\su\simeq\kk[[x]]\simeq{\kk}^{\nn}$\cr \noalign{\medskip} $E$&the {\it shift operator} $E\colon {\kk}^{\nn}\to {\kk}^{\nn}$,\hfil\break $(v_i)_{i\in\nn}\mapsto (v_{i+1})_{i\in\nn}$\cr \noalign{\medskip} $\aa=(\po,m,u)$&the usual polynomial algebra; \hfil\break $m\colon\po\otimes\po\rightarrow\po$, {\it multiplication};\hfil\break $u\colon\kk\rightarrow\po$, {\it unity map}\cr \noalign{\medskip} ${\cal B}=(\po,m,u,\Delta,\varepsilon)$&the usual polynomial bialgebra; the maps $\Delta$ ({\it comultiplication} or {\it diagonalization}) and\hfil\break $\varepsilon$ ({\it counity map} or {\it augmentation}) are defined as follows:\hfil\break \vbox{\halign{ $#\,$\hfil&\hfil$\,#\,$\hfil&\hfil$\,#\,$\hfil& $\,#\,$\hfil\cr \noalign{\smallskip} \Delta\colon\,& \po &\longrightarrow &\po\otimes \po \simeq \kk [x,y]\cr & p(x) & \mapsto & p(x+y), \cr \varepsilon\colon\,& \po &\longrightarrow & \kk\cr \ & p(x) & \mapsto & p(0). \cr}}\cr \noalign{\medskip} $\pon$&$K[x_1,\ldots ,x_n]\simeq{\kk}^{(\nn^n)}$\cr \noalign{\medskip} $\kk[x]^\circ\subset \kk[x]^*$&the set of all the forms in $\kk[x]^*$ whose kernel contains an ideal of $\kk[x]$ \cr \noalign{\medskip} ${\cal B}^\circ=(\kk[x]^\circ,\Delta^\circ,\varepsilon^\circ,m^\circ, u^\circ)$&the dual bialgebra of the polynomial bialgebra ${\cal B}$; the maps $\Delta^\circ$, \cr &$\varepsilon^\circ$, $m^\circ$ and $u^\circ$ are defined as follows:\cr } $$ \matrix{ \Delta^\circ\colon\,& \po^\circ\otimes \po^\circ &\longrightarrow &\po^\circ&\hbox{({\it multiplication})} \cr &((v_i)_{i\in\nn}),(w_j)_{j\in\nn}) & \longmapsto &(\sum_{i+j=k}{k\choose i} v_i w_j)_{k\in\nn}& \cr &&&&\cr \varepsilon^\circ\colon\,& \kk &\longrightarrow & \po^\circ &\hbox{({\it unity map})} \cr \ & a & \mapsto & a(\delta^0_j)_{j\in\nn}& \cr &&&&\cr m^\circ\colon\,& \po^\circ &\longrightarrow & \po^\circ\otimes\po^\circ\subseteq \kk^{\nn\times\nn}&\hbox{({\it diagonalization})} \cr \ & (v_i)_{i\in\nn} & \longmapsto & (w_{ij}:=v_{i+j})_{(i,j)\in\nn\times\nn}&\cr &&&&\cr u^\circ\colon\,& \po^\circ &\longrightarrow & \kk &\hbox{({\it augmentation})} \cr &(v_i)_{i\in\nn} & \mapsto &v_0.& \cr} $$ \halign{#\hfil\quad&\vtop{\hsize 7cm \noindent\strut\parindent=0pt #\hfil}\cr $\pon$&$K[x_1,\ldots ,x_n]\simeq{\kk}^{(\nn^n)}$\cr $X:=\{x_1,x_2,\ldots ,x_n\}$&a given set of indeter\-minates\cr \noalign{\medskip} $\pon$&$\kk[x_1,\ldots ,x_n]\simeq{\kk}^{(\nn^n)}$ the usual identification of the space $\pon$ of polynomials in the indeterminates $x_1,\ldots,x_n$ with the space ${\kk}^{(\nn^n)}$ of the finite support functions $\nn^n\to\kk$\cr \noalign{\medskip} $I$, $J$&ideals of $\kk[x]$ or $\kk[x_1,\ldots ,x_n]$\cr \noalign{\medskip} $M_X\subseteq K[X]$&the free abelian monoid on\hfil\break $X:=\{x_1,x_2,\ldots ,x_n\}$\cr ${\bf x^i}$&${\bf x^i}:=x_1^{i_1}\cdots x_n^{i_n}\in M_X$, the {\it terms} of $K[X]$ \cr \noalign{\medskip} $p(X)=\sum p_{\bf i}{\bf x^i}$&an element of $\pon\simeq{\kk}^{(\nn^n)}$\cr \noalign{\medskip} $\kk[X]^*\simeq\kk[[X]]\simeq{\kk}^{\nn^n}$&the usual identification of the dual space\hfil\break $\kk[X]^*$ of $\kk[X]$ with both the space $\kk[[X]]$ of formal power series and the space ${\kk}^{\nn^n}$ of all functions $\nn^n\to\kk$\cr \noalign{\medskip} ${\bf f}=\sum_{{\bf i}\in \nn^n} f_{\bf i} {\bf x^i}= (f_{\bf i})_{{\bf i}\in \nn^n}$&an element of $\kk[X]^*\simeq\kk[[X]]\simeq{\kk}^{\nn^n}$\cr \noalign{\medskip} ${\bf E^j}$&the {\it shift operator} ${\bf E^j} \colon {\kk}^{\nn^n}\to {\kk}^{\nn^n}$, $(f_{\bf i})_{{\bf i}\in \nn^n}\mapsto (f_{\bf {i+j}})_{{\bf i}\in \nn^n}$\cr \noalign{\medskip} $p({\bf E})$&for $p(X)=\sum p_{\bf i}{\bf x^i}\in \kk[X]$, the operator\hfil\break $p({\bf E}):=\sum p_{\bf i}{\bf E^i}\in \kk[X]^*$\cr \noalign{\medskip} ${\cal B}_n=(\kk[X],m_n,u_n,\Delta_n,\varepsilon_n)$&the multivariate polynomial bialgebra;\hfil\break the definition of the maps $m_n,u_n,\Delta_n,\varepsilon_n$ is analogous to that of $m,u,\Delta,\varepsilon$\cr $\kk[X]^\circ\subset \kk[X]^*$&the set of all the forms in $\kk[X]^*$ whose kernel contains a cofinite ideal of $\kk[X]$\cr \noalign{\medskip} ${\cal B}_n^\circ=(\kk[X]^\circ,\Delta_n^\circ,\varepsilon_n^\circ, m_n^\circ,u_n^\circ)$&the dual bialgebra of the multivariate polynomial bialgebra ${\cal B}_n$\cr \noalign{\medskip} $v_{\bf P}$&$v_{\bf P}\colon \kk[X] \rightarrow \kk$, $p \mapsto p({\bf P})$, the evaluation map at the point ${\bf P}\in \kk^n$:\cr \noalign{\medskip} ${\bf D_i}$&the linear map $\;{\bf D_i}\colon \, \kk[X] \rightarrow \kk[X]\;$, ${\bf x^h} \mapsto {{\bf h}\choose {\bf i}}{\bf x^{h-i}}$; we have the formula\hfil\break ${\bf D_i}(fg)= \sum_{{\bf h}+{\bf k}={\bf i}} {\bf D_h}(f){\bf D_k}(g)$. Moreover, when the field $\kk$ has characteristic zero, then ${\bf D_i}=\displaystyle{1\over {\bf i!}}{\bf D^i}:= {1\over {\bf i!}} {{\partial^{i_1+\cdots +i_n}}\over {\partial x_1^{i_1}\cdots \partial x_n^{i_n}}}$.\cr \noalign{\medskip} $v_{\bf P}^{\bf i}$&the composition $v_{\bf P}\circ{\bf D_i}$,$\;$ i.e.\ $v_{\bf P}^{\bf i}\colon\; \kk[X] \rightarrow \kk\;$, $p \mapsto ({\bf D_i}p)({\bf P})$\cr \noalign{\medskip} } \halign{#\hfil\qquad\quad&\vtop{\hsize 8cm \noindent\strut\parindent=0pt #\hfil}\cr $\wp$&$\{({\bf P}_1,{\cal F}_1),\ldots,({\bf P}_N,{\cal F}_N)\}$\hfil\break each element $({\bf P}_j,{\cal F}_j)\in \wp$ consists of a point ${\bf P}_j$ of $\rr^n$ together with an $n$-dimensional Ferrers diagram ${\cal F}_j\subset\nn^n$\cr \noalign{\medskip} $({\bf P},{\bf i})\in\wp$&this notation stands for ${\bf P}={\bf P}_j$ and ${\bf i}\in {\cal F}_j$ for some $j\in\{1,\ldots,N\}$\cr \noalign{\medskip} $\Im(\wp)$&the cofinite ideal\hfil\break $\Im(\wp):=\left\{ p\in\kk[X]\,\big| \;(\forall j)(\forall {\bf i}\in {\cal F}_j)\left( v^{\bf i}_{{\bf P}_j}(p)=0\right)\right\}$\hfil\break associated to $\wp=\{({\bf P}_1,{\cal F}_1),\ldots,({\bf P}_N,{\cal F}_N)\}$\cr } \bigskip \noindent \S\ {\bf 1}. \indent {\bf Introduction.} \vskip .1in \noindent {\bf 1.1}\indent 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\in\nn}$, is said to be a \sr, $I$ ideal of $\po$, if, for every $p\in I$, we have $p(E)(v)=0$ ($E$ shift operator). Every element $p\in I$ is said to be a {\it characteristic polynomial\/} and the generator $g$ of $I=(g)$ the {\it minimal polynomial\/} of the \sr\ $v$. An \sr\ $v$ is completely determined by its minimal polynomial $g$ and by its initial values $v_i$, $0\leq i< k=\hbox{deg}(g)$, that is the values which the form $v$ takes on the monomials $x^0,\ldots,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 $\po/I$. As a consequence, the set ${\cal S}(I)$ of all the \sr\ is a $k$-dimensional $\kk$-vector space ($k=\hbox{deg}(g)$, $I=(g)$). Morover, ${\cal S}(I)$ is a cyclic $\po$-submodule of the $\po$-module $\su$, where the scalar product is defined by $ \po\times\su \longrightarrow\su,\; (p,v)\quad \longmapsto p(E)(v)\; $ (equivalently, $(p,v)\longmapsto [q\mapsto v(pq)]$). A generator of ${\cal S}(I)$ as $\po$-module is any \sr\ $v=(v_i)$ such that no proper divisor of the generator $g$ of $I$ is a characteristic polynomial for $v$; for instance, the \sr\ $v$ whose first $k$ terms are $v_0=v_1=\cdots=v_{k-2}=0$, $v_{k-1}=1$. \vskip .1in \noindent {\bf 1.2}\indent Peterson and Taft [1] showed that the set $\kk[x]^\circ=\bigcup {\cal S}(I)$ ($I$ cofinite ideal) of all l.r.s.\ is the underlying set of the dual bialgebra ${\cal B}^\circ$ of the usual polynomial bialgebra ${\cal 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 \sr. Let now ${\cal B}_n=(\kk[X],m_n,u_n,\Delta_n,\varepsilon_n)$ be the multivariate polynomial bialgebra. The elements of the dual bialgebra ${\cal B}_n^\circ\subset\kk[X]^*$ are precisely those linear forms ${\bf f}:\kk[X]\to\kk$ whose kernel contains a cofinite ideal $I\subseteq\kk[X]$, that is an ideal $I$ such that $\hbox{dim}{(\kk[X]/I)}<\infty$. Any such form ${\bf f}$ is called an $I$-{\it 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)$ $\kk[X]$ is not a principal domain, $(ii)$ not every ideal of $\kk[X]$ is cofinite and $(iii)$ there are infinitely many different {\it term orderings} $\preceq$ on the monoid $M_X\subset\kk[X]$. \vskip .1in \noindent {\bf 1.3}\indent 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 ${\bf f}=\sum_{{\bf i}\in\nn^n}f_{\bf i}{\bf x^i}\in{\cal B}_n^\circ$ we need $(a)$ a cofinite ideal $I=(g_1,\ldots,g_s)\subseteq\kk[X]$ and $(b)$ a monomial basis $({\bf x^j}+I)_{{\bf j}\in L}$, $L\subseteq \nn^n$, for the quotient algebra $\kk[X]/I$. In fact, the $I$-linearly recursive function ${\bf f}$ is completely determined by its ``initial values'' $f_{\bf j}$, ${\bf j}\in L$, all the other values $f_{\bf i}$, ${\bf i}\not\in L$, being computed by means of the generators $g_1,\ldots,g_s$ of the ideal $I$. The idea is to use $g_1,\ldots,g_s$ as ``scales of recurrence''. Nevertheless, in practice this is not yet enough. What we really need is $(a')$ a reduced Gr\"obner basis $\hbox{RGB}(I)=(h_1,\ldots,h_t)$ for the ideal $I$ relative to the fixed term ordering $\preceq$ and $(b')$ a monomial basis $({\bf x^j}+I)_{{\bf j}\in L}$ which is {\it minimal\/} with respect to $\preceq$, that is a basis $({\bf x^j}+I)_{{\bf j}\in L} =\{ {\bf x}^{{\bf j}_1}+I, \ldots, {\bf x}^{{\bf j}_h}+I\}$, with ${\bf x}^{{\bf j}_1}\prec {\bf x}^{{\bf j}_2}\prec \ldots \prec {\bf x}^{{\bf j}_h}$, such that for every other monomial basis $({\bf x^{j'}}+I)_{{\bf j'}\in L'} =\{ {\bf x}^{{\bf j'}_1}+I, \ldots, {\bf x}^{{\bf j'}_h}+I\}$, with ${\bf x}^{{\bf j'}_1}\prec {\bf x}^{{\bf j'}_2}\prec \ldots \prec {\bf x}^{{\bf j'}_h}$, we have ${\bf x}^{{\bf j}_r}\prec {\bf x}^{{\bf j'}_r}$ for every $r=1,\ldots,h$. It is easy to check that a monomial basis $({\bf x^j}+I)_{{\bf j}\in L}$ is a {\it minimal} monomial basis only if $L\subseteq\nn^n$ is an $n$-dimensional Ferrers diagram. Notice that the minimal (with respect to $\preceq$) monomial basis $({\bf x^j}+I)_{{\bf j}\in L}$ is determined by $\hbox{RGB}(I)=(h_1,\ldots,h_t)$ in the following way. Let ${\bf x}^{{\bf j}_r}$, $r=1,\ldots,t$, be the leading term (with respect to $\preceq$) of the polynomial $h_r\in\hbox{RGB}(I)$ and let $\overline{L}\subseteq\nn^n$ be the poset filter of $\nn^n$ (ordered by the usual product order $\leq$) generated by ${\bf j}_1,\ldots,{\bf j}_t$; then $L$ is the complementary ideal $L=\nn^n\setminus \overline{L}$. \vskip .1in \noindent {\bf 1.4}\indent The above remarks seemingly indicate that Gr\"obner bases theory be able to satisfy our computational needs. Unfortunatly, that theory provides no device to make sure {\it in advance} whether a given set of polynomials $(g_1,\ldots,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 $\wp:=\{({\bf P}_1,{\cal F}_1),\ldots,({\bf P}_N,{\cal F}_N)\}$ (${\bf P}_j\in\kk^n$; ${\cal F}_j\subset\nn^n$ is $n$-dimensional Ferrers diagram), it is not difficult to prove that the set $$ \Im(\wp):=\left\{ p\in\kk[X]\,\big| \;(\forall j)(\forall {\bf i}\in {\cal F}_j)\left( v^{\bf i}_{{\bf P}_j}(p)=0\right)\right\}. $$ associated to $\{v^{\bf i}_{\bf P}\mid ({\bf P},{\bf i})\in \wp\}\subset \kk^{\nn^n}$ is a cofinite ideal. Notice that ${\rm codim}(\Im(\wp))=\sum_{j=1}^N\#{\cal F}_j$ and that $\{P_1,\ldots,P_N\}$ is the affine variety of $\Im(\wp)$. The algorithms described in [3] produce first the monomial basis for $\po/\Im(\wp)$ which is minimal with respect to the inverted lexicographical order $\preceq_{i.l.}$ and then a reduced Gr\"obner basis of $\Im(\wp)$. \vskip .1in \noindent {\bf 1.5}\indent Bearing in mind on the one hand that the forms $v^{\bf i}_P$, $P\in \kk^n, {\bf i}\in \nn^n$, are a linear basis of the dual bialgebra ${\cal B}^\circ_n$ (see [2], Prop.~6 and its Corollary) and on the other hand that not every cofinite ideal $I$ is of the form $\Im(\wp)$, the following question naturally arises: under what general conditions a system of independent linear combinations of forms $v^{\bf i}_P$ may generate a subspace $H\subset {\cal B}^\circ_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={\cal S}(I)$ for some cofinite ideal $I\subset\kk[X]$)? For instance, it is easy to prove that $H$ must be both a finitely generated $\kk[X]$-submodule of the $\kk[X]$-module $\kk[X]^*$ and a finite dimensional $\kk$-subspace of $\kk[X]^\circ$. The search for such necessary and sufficient conditions is a matter of a work-in-progress by Cerlienco and Mureddu. \vskip .1in \noindent {\bf 1.6}\indent 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 {\it 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 ${\sy C}[x_1,\ldots,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 $\sy C$-linear forms $f\colon {\sy C}[x_1,\ldots,x_n]\to {\sy C}$ whose kernel contains $I$. An immediate consequence of this definition is that the inverse system of an ideal $I$ is isomorphic, as a ${\sy C}$-vector space, to the linear dual of ${\sy C}[x_1,\ldots,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 ${\sy C}[x_1,\ldots,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 \S {\bf 2}. \vskip .1in \noindent {\bf 1.7}\indent In the Gr\"obner bases computational framework, another question which has a combinatorial flavour naturally arises. When we are looking for a Gr\"obner basis for a given ideal, we have previously to fix a term ordering $\preceq$ on $\nn^n$. Moreover, in the applications some particular term ordering is often needed. In the usual computer algebra systems which contain a Gr\"obner 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 \S 3 a handy canonical representation of term orderings by which all these problems can be easily solved is given. \vskip .2in \noindent \S\ {\bf 2}. \indent {\bf Inverse systems.} \vskip .1in \font\sc=cmcsc10 \noindent {\bf 2.1}\indent We will consider $\kk[X]^*$ with its $\kk[X]$-module structure defined by $\kk[X]\times\kk[X]^*\to\kk[X]^*$, $(p,f)\mapsto p{\cdot}\bf f$, where $p{\cdot}{\bf f}=p({\bf E})({\bf f})$, equivalently, $(p{\cdot}{\bf f})(q)={\bf f}(pq)$. If $Y\subseteq\kk[X]^*$ we will put $$ {\cal P}(Y)=\{p\in\kk[X]\mid p{\cdot}{\bf f}=0 \hbox{ for all ${\bf f}\in Y$}\}. $$ Let $I$ be an ideal of $\kk[X]$. Any submodule $H$ of $\kk[X]^*$ such that ${\cal P}(H)=I$ will be said an {\it inverse system\/} of $I$. According to Macaulay (see [7], p.\ 68) \underbar{the} inverse system of the ideal $I$ is the set $$ {\cal S}(I)=\left\{{\bf f}\in\kk[X]^*\biggm| \bigl(p{\cdot}{\bf f}\bigr)(1) :={\bf f}(p)=0 \hbox{ for every $p\in I$}\right\}. $$ ${\cal S}(I)$ is also an inverse system according to our definition. \vskip5pt plus 2pt minus 2pt\noindent {\bf Prop. 1} {\it ${\cal S}(I)$ is a $\kk[X]$-submodule of\ \ $\kk[X]^*$ which is an inverse system according to our definition as well, i.\ e.\ ${\cal P}({\cal S}(I))=I$. Moreover, ${\cal S}(I)$ is a $\kk$-vectorspace isomorphic to the dual $\kk$-vectorspace of $\kk[X]/I$.} \qed \vskip5pt plus 2pt minus 2pt From {\bf Prop. 1} we deduce: \item{$\bullet$} ${\cal S}(I)$ is a finite-dimensional vector space iff $I$ is a cofinite ideal. When $I$ is not cofinite, ${\cal S}(I)$ has non-countable dimension. \item{$\bullet$} With respect to a fixed term ordering on $\kk[X]$, let us denote by $\hbox{\sc Lt}(I)$ the ideal of $\kk[X]$ generated by the leading terms of the elements of $I$; an element $\bf f$ of ${\cal S}(I)$ is fully determined by its values on the monomials ${\bf x^i}\not\in\hbox{\sc Lt}(I)$, since the $({\bf x^i}+I)$'s are a basis for $\kk[X]/I$. \vskip5pt plus 2pt minus 2pt\noindent The last remark allows us to describe some families of elements of ${\cal S}(I)$ that generate inverse systems with countable dimension as vectorspaces. For instance, consider the family of linear forms $$ {\cal R}_L=\bigl\{{\bf f_i}\mid {\bf f_i}({\bf x^j})=\delta^{\bf j}_{\bf i} \hbox{ and } {\bf i,j}\in L\bigr\}\subseteq{\cal S}(I) $$ (where $L=\{{\bf i}\in\nn^n\mid {\bf x^i}\notin\hbox{\sc Lt}(I)\}$, and $\delta^{\bf j}_{\bf i}=\delta^{j_1}_{i_1}\cdots\delta^{j_n}_{i_n}$ is the multivariate Kronecker symbol). \vskip5pt plus 2pt minus 2pt\noindent {\bf Prop. 2} {\it For every polynomial $p\in\kk[X]$ and every form ${\bf f_i}\in{\cal R}_L$ we have: $$ p\equiv \sum_{{\bf i}\in L}{\bf f_i}(p){\bf x^i}\quad\pmod I.\eqno\qed $$} \vskip5pt plus 2pt minus 2pt Note that using {\bf Prop. 2} we can easily compute the values of the functionals $\bf f_i$. For every ${\bf j}\in\nn^n$, ${\bf f_i}({\bf x^j})$ is the coefficient of $\bf x^i$ in the remainder of $\bf x^j$ on division by the reduced Gr\"obner basis with respect to the fixed monomial ordering (i.\ e.\ ${\bf f_i}({\bf x^j})=a_{\bf i}$ where ${\bf x^j}\equiv \sum_{{\bf i}\in L}{\bf a_i}{\bf x^i}\;\pmod I$). \vskip5pt plus 2pt minus 2pt\noindent {\bf Corollary 1.} {\sl The $\kk[X]$-module $H_L$, generated by ${\cal R}_L$, is an inverse system of the ideal $I$}. \vskip5pt plus 2pt minus 2pt\noindent {\bf Corollary 2.} {\sl ${\bf f}\in{\cal S}(I)\quad\hbox{if and only if}\quad {\bf f}=\sum_{{\bf i}\in L}{\bf f}({\bf x^i}){\bf f_i}$}. \vskip5pt plus 2pt minus 2pt\noindent {\bf Corollary 3.} {\sl Let $I$ be a cofinite ideal of $\kk[X]$; then ${\cal S}(I)=H_L$}. \vskip5pt plus 2pt minus 2pt 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]. \vskip5pt plus 2pt minus 2pt\noindent {\bf Prop. 3} {\it For every ideal $I\subseteq\kk[X]$, there is an inverse system which is finitely generated as $\kk[X]$-module}.\qed \vskip5pt plus 2pt minus 2pt In particular, it can be proved that every irreducible ideal has a cyclic inverse system. \vskip.1in \noindent {\bf 2.2}\indent In this section we generalize the results in {\bf 2.1} to the case of some power $\kk[X]^l$. The $\kk$-vectorspace $\kk[X]^l$ and $(\kk[X]^*)^l$ will be regarded also as $\kk[X]$-modules. The scalar product is given by $$\eqalign{ \kk[X]\times\kk[X]^l\;\;&\longrightarrow\kk[X]^l\cr \Bigl(p,\,(p_1,\ldots,p_l)\Bigr)&\longmapsto (pp_1,\ldots,pp_l)\cr} $$ and, respectively, by $$\eqalign{ \kk[X]\times(\kk[X]^*)^l\;&\longrightarrow(\kk[X]^*)^l\cr \Bigl(p,\,({\bf f}_1,\ldots,{\bf f}_l)\Bigr)&\longmapsto (p{\cdot}{\bf f}_1,\ldots,p{\cdot}{\bf f}_l).\cr} $$ For every $Y\subseteq(\kk[X]^*)^l$, we put $$\displaylines{\quad {\cal P}(Y)=\Bigl\{(p_1,\ldots,p_l)\in\kk[X]^l\biggm| p_1{\cdot}{\bf f}_1+\cdots+p_l{\cdot}{\bf f}_l=0\hfill\cr \hfill \hbox{for all $({\bf f}_1,\ldots,{\bf f}_l)\in Y$}\Bigr\}.\quad\cr} $$ ${\cal P}(Y)$ is clearly a submodule of $\kk[X]^l$; conversely, we want to show that for every submodule $M$ of $\kk[X]^l$ there is a subset $Y$ of $(\kk[X]^*)^l$ such that ${\cal P}(Y)=M$. Any such subset $Y$ will be called an {\it inverse system\/} of the submodule $M$. For the purposes of our discussion here, we first denote by $e_j(p)$ the element $(0,\ldots,p,\ldots,0)$ of $\kk[X]^l$. Moreover, denote by $\cal G$ the reduced Gr\"obner basis of $M$ with respect to a fixed term ordering $\preceq$ on $\kk[X]^l$ and by ${\rm Red}_\preceq(p_1,\ldots,p_l)$ the unique element obtained by reducing $(p_1,\ldots,p_l)$ modulo $\cal G$. (Concerning Gr\"obner bases theory relative to polynomial modules see [8].) The set $$ \left\{e_j({\bf x^p})+M\biggm| e_j({\bf x^p})\not\in\hbox{\sc Lt}(M)\right\} $$ (where $\hbox{\sc Lt}(M)$ is the $\kk[X]$-module generated by the leading terms of the elements of $M$) is a basis of the $\kk$-vectorspace $\kk[X]^l/M$. Let $$ L=\left\{({\bf p},j)\in\nn^n\times\{1,\ldots,l\}\biggm| e_j({\bf x^p})\not\in\hbox{\sc Lt}(M)\right\}. $$ For every $({\bf p},j)\in L$ and every $1\leq i\leq l$, let ${\bf f}_{{\bf p},i}^j$ be the $\kk$-linear map from $\kk[X]$ to $\kk$ defined by $$ {\bf f}_{{\bf p},i}^j(p)=\hbox{coeff.\ of $(e_j({\bf x^p})+M)$ occurring in $(e_i(p)+M)$}.\leqno(1) $$ \vskip5pt plus 2pt minus 2pt\noindent {\bf Prop. 4} {\it Let ${\cal R}_L(M)$ be the submodule of $(\kk[X]^*)^l$ generated by the $l$-tuples $({\bf f}_{{\bf p},1}^j,\ldots,{\bf f}_{{\bf p},l}^j)$, $({\bf p},j)\in L$. Then ${\cal R}_L(M)$ is an inverse system of the submodule $M$, i.\ e.\ ${\cal P}({\cal R}_L(M))=M$.} \vskip.1in \noindent {\bf Proof:} See [6].\qed \vskip5pt plus 2pt minus 2pt Next we describe the maximal inverse system of the submodule $M\subseteq\kk[X]^l$. Let $\langle(q_{1,1},\ldots,q_{1,l}),\ldots,(q_{k,1},$ $\ldots,q_{k,l})\rangle$ be a system of generators of $M$ and let ${\cal S}(M)$ be the set of the $l$-tuples $({\bf f}_1,\ldots,{\bf f}_l)$ of $(\kk[X]^*)^l$ which are solutions of the linear system: $$ \left\{\matrix{q_{1,1}{\cdot}w_1+&\cdots&+q_{1,l}{\cdot}w_l&=&0\cr \multispan5\dotfill\cr q_{k,1}{\cdot}w_1+&\cdots&+q_{k,l}{\cdot}w_l&=&0.\cr}\right. \leqno(2) $$ \vskip5pt plus 2pt minus 2pt\noindent {\bf Prop. 5} {\it For every submodule $M$ of\/ $\kk[X]^l$, we have $$ ({\bf f}_1,\ldots,{\bf f}_l)\in{\cal S}(M)\iff (\forall i)\left( {\bf f}_i=\sum_{({\bf p},j)\in L}{\bf f}_j({\bf x^p}){\bf f}_{{\bf p},i}^j \right). $$ Thus, ${\cal P}({\cal S}(M))=M$}. \vskip.1in \noindent {\bf Proof:} See [6].\qed \vskip5pt plus 2pt minus 2pt\noindent This proposition enables us to compute the general solution of the system $(2)$. It is of the form $$ \Bigl(\sum_{({\bf p},j)\in L}b_{{\bf p},j}{\bf f}_{{\bf p},1}^j,\ldots, \sum_{({\bf p},j)\in L}b_{{\bf p},j}{\bf f}_{{\bf p},l}^j\Bigr). $$ where the linear forms ${\bf f}_{{\bf p},i}^j$ are defined as in (1) and $(b_{{\bf p},j})_{({\bf p},j)\in L}$ is an arbitrary family of elements of $\kk$. When $\kk$ 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: $$ \left\{\matrix{q_{1,1}({\partial\over\partial u_1},\ldots, {\partial\over\partial u_n}) \varphi_1+\cdots+ q_{1,l}({\partial\over\partial u_1},\ldots, {\partial\over\partial u_n}) \varphi_l=0\cr \multispan1\dotfill\cr q_{k,1}({\partial\over\partial u_1},\ldots, {\partial\over\partial u_n}) \varphi_1+\cdots+ q_{k,l}({\partial\over\partial u_1},\ldots, {\partial\over\partial u_n}) \varphi_l=0.\cr}\right. \leqno(3) $$ In fact, making use of {\bf Prop. 6} below, it is sufficient to observe that system (2) is mapped into (3) by the $\kk$-linear isomorphism $$\eqalign{ {\cal E}:\kk[X]^*&\longrightarrow\kk[[{\bf u}]]\cr {\bf f}&\longmapsto\sum_{\bf h}{\bf f}({\bf x^h}){{\bf u^h}\over{\bf h}!}. \cr} $$ \vskip5pt plus 2pt minus 2pt\noindent {\bf Prop. 6} {\it Let $\kk$ be a field of characteristic zero. For every polynomial $p=\sum_{\bf i}a_{\bf i}{\bf x^i}\in\kk[X]$ and every linear form ${\bf f}\in\kk[X]^*$ we have: $$ {\cal E}(p{\cdot}{\bf f})= \Bigl(\sum_{\bf i}a_{\bf i}{\partial^{|{\bf i}|}\over\partial{\bf u^i}}\Bigr) \bigl({\cal E}({\bf f})\bigr),\quad |{\bf i}|=i_1+\cdots+i_n. $$} \vskip.1in \noindent {\bf Proof:} See [6].\qed \vskip5pt plus 2pt minus 2pt In explicit terms, if $M$ is the $\kk[X]$-module generated by the set $$\{(q_{1,1},\ldots,q_{1,l}),\ldots,(q_{k,1},\ldots,q_{k,l})\},$$ then we have $$\displaylines{\quad q_{1,1}({\partial\over\partial u_1},\ldots, {\partial\over\partial u_n}) \Bigl(\sum_{\bf h}{\bf f}_1({\bf x^h}) {{\bf u^h}\over{\bf h}!}\Bigr)\hfill\cr \hfill{}+\cdots+ q_{1,l}({\partial\over\partial u_1},\ldots,{\partial\over\partial u_n}) \Bigl(\sum_{\bf h}{\bf f}_l({\bf x^h}){{\bf u^h}\over{\bf h}!}\Bigr)=0\quad\cr \dotfill\cr \quad q_{k,1}({\partial\over\partial u_1},\ldots,{\partial\over\partial u_n}) \Bigl(\sum_{\bf h}{\bf f}_1({\bf x^h}){{\bf u^h}\over{\bf h}!}\Bigr) \hfill\cr \hfill{}+\cdots+ q_{k,l}({\partial\over\partial u_1},\ldots,{\partial\over\partial u_n}) \Bigl(\sum_{\bf h}{\bf f}_l({\bf x^h}) {{\bf u^h}\over{\bf h}!}\Bigr)=0,\quad\cr} $$ if and only if $({\bf f}_1,\ldots,{\bf f}_l)\in{\cal S}(M)$. Thus, the general solution of (3) is $$ \left( \sum_{\bf h}\Bigl( \sum_{({\bf p},j)\in B}b_{{\bf p},j}{\bf f}_{{\bf p},1}^j({\bf x^h})\Bigr) {{\bf u^h}\over{\bf h}!},\; \ldots, \; \sum_{\bf h}\Bigl( \sum_{({\bf p},j)\in B}b_{{\bf p},j}{\bf f}_{{\bf p},l}^j({\bf x^h})\Bigr) {{\bf u^h}\over{\bf h}!}\right). $$ \vskip .2in \noindent \S\ {\bf 3}. \indent {\bf Canonical matrix representation of term orderings.} \vskip .1in \noindent {\bf 3.1}\indent Let $\preceq$ be a {\it term ordering} on $\nn^n$, that is a linear order which is compatible with the monoid structure of $\nn^n$: $0\preceq {\bf i}, \quad {\bf i} \prec {\bf j} \Rightarrow {\bf i}+{\bf h} \prec {\bf j}+{\bf h}$. It is easily seen that $\preceq$ can be uniquely extended to a linear order on $\zz^n$ (resp.: $\qq^n$) compatible with the structure of $\zz$-module (resp.: $\qq$-vectorspace). It can be also proved (see [11]) that any term ordering $\preceq$ is the restriction to $\nn^n$ of at least one linear order $\preceq^\rr$ on $\rr^n$ which is compatible with the structure of $\rr$-vectorspace. In the following, such an order will be simply referred as a {\it c.l.order}. As an example, consider the c.l.order $\preceq_{\overline{\bf b}}$ determined by a given basis $\overline{\bf b}=({\bf b}_1,\ldots,{\bf b}_n)$ of $\rr^n$ in the following way: $$ {\bf P} \prec_{\overline{\bf b}} {\bf Q} \quad \Longleftrightarrow \quad \left(\matrix{\alpha^1 \cr \vdots \cr \alpha^n\cr}\right) \prec_{lex} \left(\matrix{\beta^1 \cr \vdots \cr \beta^n\cr}\right) $$ where ${\bf P}=\sum_{i=1}^n \alpha^i {\bf b}_i$, ${\bf Q} =\sum_{i=1}^n \beta^i {\bf b}_i$ and $\preceq_{lex}$ is the usual lexicographic order. Equivalently, $$ {\bf P} \prec_{\overline{\bf b}} {\bf Q} \quad \Longleftrightarrow \quad C {\bf P} \prec_{lex} C {\bf Q } $$ where $C^{-1}=B=(b^i_j)_{(i,j)\in {\bf n}^2}$ with ${\bf b}_j=(b^i_j)_{i\in {\bf n}}$ and ${\bf n}=\{1,\ldots,n\}$. It is not difficult to check that two different bases $\overline{\bf b}=({\bf b}_1,\ldots, {\bf b}_n)$, $\overline{\bf b}'=({\bf b}'_1,\ldots, {\bf b}'_n)$ determine the same c.l.order ($\preceq_{\overline{\bf b}} \; = \; \preceq_{\overline{\bf b}'}$) iff $$ B'=B\cdot \Lambda \qquad \hbox{(equivalently, }\quad C'=\Lambda^{-1}C \hbox{)} $$ where $\Lambda = (\lambda^i_j)$ is a lower triangular matrix with $\lambda^i_i > 0$. The following fundamental result is due to Erd\H{o}s [9] (see also [10], [11]). \vskip.1in \noindent {\bf Theorem} (Erd\H{o}s) {\it Let $\preceq^{\rr}$ be a c.l.order on $\rr^n$; then, there is a basis (in fact, infinitely many bases) $\overline{\bf b}=({\bf b}_1,\ldots, {\bf b}_n)$ of $\rr^n$ such that $\preceq^{\rr} \; = \; \preceq_{\overline{\bf b}}.$ } \vskip.1in In other words, (i) any c.l.order $\preceq^{\rr}$ on $\rr^n$ can be represented by a non-singular matrix $C$ for which we have $$ {\bf P} \prec^\rr {\bf Q} \quad \Longleftrightarrow \quad C{\bf P} \prec_{lex} C{\bf Q}, \leqno(4) $$ and (ii) any two matrices $C$, $C'$ which represent the same c.l.order $\preceq^\rr$ satisfy the equivalence relation $$ C'=\Lambda^{-1}C. \leqno(5) $$ We want to determine a {\it canonical matrix representation} of $\preceq^\rr$. To this aim, let us define a {\it lexicographic matrix} to be an $m$ by $n$ matrix $A=(a^i_j)$ $(m\leq n)$ of the form $$ \left( \matrix{ 0 & \ldots & 0 & \pm 1 & * & * & \ldots & * \cr 0 & \ldots & 0 & 0 & 0 & \pm 1 & \ldots & * \cr 0 & \ldots & \pm 1 & 0 & * & 0 & \ldots & * \cr \cdot & \ldots & \cdot & \cdot & \cdot & \cdot & \ldots & \cdot \cr \pm 1 & \ldots & 0 & 0 & * & 0 & \ldots & * \cr 0 & \ldots & 0 & 0 & \pm 1 & 0 & \ldots & * \cr } \right), $$ 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^i_{j(i)}$ the first non-zero entry in the i-th row of $A$, then $a^i_{j(i)}$ is either $1$ or $-1$; (c) for each $i=1,\ldots,n$ and for each $i'> i$ we have $a^{i'}_{j(i)}=0$. Notice that the rank of a $m \times n$ lexicographic matrix $A$ is $m$. \vskip5pt plus 2pt minus 2pt\noindent \noindent {\bf Prop. 7} {\it For every c.l.order $\preceq^\rr$ on $\rr^n$, there is one and only one $n \times n$ lexicographic matrix $C$ for which (4) is true.} \vskip.1in \noindent {\bf Proof:} The statement is a straightforward consequence of the Erd\H{o}s Theorem and of (5).\qed \vskip.1in \noindent {\bf 3.2}\indent Consider now a term ordering $\preceq$ on $\qq^n$. Let $\preceq^\rr$ be any c.l.order on $\rr^n$ whose restriction is $\preceq$. Let $\overline{\bf b}=({\bf b}_1,\ldots,{\bf b}_n)$, $B=(b^i_j)$, $C=(c^i_j)=B^{-1}$ and $\Lambda$ have the same meaning as in {\bf 3.1}. Let $T_{n-i}:=({\bf b}_{i+1},\ldots,{\bf b}_n) \subseteq \rr^n =: T_n$, that is the $(n-i)$--dimensional subspace defined by the linear system $$ \left\{\matrix{ c^1_1 x^1 + \cdots + c^1_n x^n = 0 \cr \multispan1 \dotfill \cr c^i_1 x^1 + \cdots + c^i_n x^n = 0 \cr} \right.\; , \qquad \qquad \left(\matrix{x^1\cr \vdots\cr x^n\cr}\right)\in \rr^n. $$ Observe that the hyperplane $\pi_{i+1}:=({\bf b}_{1},\ldots {\bf b}_{i}, {\bf b}_{i+2},\ldots,{\bf b}_n) \subseteq \rr^n $ (whose equation is $c^{i+1}_1 x^1 + \cdots + c^{i+1}_n x^n = 0 $) divides $T_{n-i}$ into three parts: the intersection $T_{n-i-1}=T_{n-i}\cap \pi_{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 $\preceq^\rr$ to $\preceq$, it may happen that all rational points of $T_{n-i}$ belong to $\pi_{i+1}$ as well, so that $$ \sum c^1_j x^j = \ldots = \sum c^i_j x^j = 0 \quad \Rightarrow \quad \sum c^{i+1}_j x^j = 0 $$ for every rational point $(x^1,\ldots,x^n)_{-1} \in \qq^n$ or, which is the same, the two n-tuples of vectors $$ \left( \matrix {c^1_1 \cr \vdots \cr c^i_1 \cr} \right), \;\ldots, \; \left( \matrix {c^1_n \cr \vdots \cr c^i_n \cr} \right) $$ and $$ \left( \matrix {c^1_1 \cr \vdots \cr c^i_1 \cr c^{i+1}_1 \cr} \right), \;\ldots , \; \left( \matrix {c^1_n \cr \vdots \cr c^i_n \cr c^{i+1}_n \cr} \right) $$ 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 {\bf Prop.~7} we deduce the following results. \vskip5pt plus 2pt minus 2pt \noindent {\bf Prop. 8} {\it Let $C=(c^i_j)$ be an $m\times n$ matrix ($m\leq n$) and let $\preceq$ be the order on $\nn^n$ defined by $$ {\bf i}\prec{\bf j} \quad \Longleftrightarrow \quad C{\bf i}\prec_{lex}C{\bf j}\qquad \forall {\bf i},{\bf j}\in \nn^n. \leqno(6) $$ Then, $\preceq$ is a term ordering iff the columns of $C$ are rationally independent.}\qed \vskip5pt plus 2pt minus 2pt \noindent {\bf Prop. 9} {\it For every term ordering $\preceq$ on $\nn^n$, there is one and only one $m \times n$ lexicographic matrix $C=(c^i_j)$ satisfying (6) such that for every $i=1,\ldots,m-1$ the rational dimension of the vectors $$ \left( \matrix {c^1_1 \cr \vdots \cr c^i_1 \cr} \right), \;\ldots ,\; \left( \matrix {c^1_n \cr \vdots \cr c^i_n \cr} \right) $$ is strictly less than the rational dimension of the vectors $$ \left( \matrix {c^1_1 \cr \vdots \cr c^i_1 \cr c^{i+1}_1 \cr} \right), \;\ldots ,\; \left( \matrix {c^1_n \cr \vdots \cr c^i_n \cr c^{i+1}_n \cr} \right). $$}\qed \vskip.1in \noindent {\bf 3.3} \indent Let $\preceq$ be the term ordering on $\nn^n$ represented by the $m\times n$ matrix $$ \hat C = \left( \matrix{c^{\iota_1}_1 & \ldots & c^{\iota_1}_n \cr \cdot & \ldots & \cdot \cr c^{\iota_m}_1 & \ldots & c^{\iota_m}_n \cr} \right) \qquad (m \leq n). $$ For $h=1,\ldots,m$, let us denote by $d_h$ the rational dimension of the $n$ vectors $$ \left(\matrix {c^{\iota_1}_1\cr\vdots\cr c^{\iota_h}_1\cr}\right) \ldots \left(\matrix {c^{\iota_1}_n\cr\vdots\cr c^{\iota_h}_n\cr}\right). \leqno(7) $$ We shall say that the matrix $\hat C$ is {\it rationally reduced} if $d_11$, let $$ \left( \matrix{c^1_1 & \ldots & c^1_n \cr \cdot & \ldots & \cdot \cr c^{i_{h-1}}_1 & \ldots & c^{i_{h-1}}_n \cr } \right) \leqno(8) $$ 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^{i_{h-1}+1}_j), \ldots , (c^{i_h}_j)$ chosen as follows. The first $k:=d_{h-1}-d_{h-2}-1$ of these rows form the lexicographic matrix $\Gamma$ for which: (a) the entries of the first $d_{h-2}+1$ columns of $\Gamma$ are zero; (b) the subsequent $k=d_{h-1}-d_{h-2}-1$ columns form the $k \times k$ matrix $(a^r_s\,:=\, \delta^r_{k-s+1})\;$ ($\delta^r_t$ 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^{i_h}_j := c^{\iota_h}_j$ $\;$ ($j=1,\ldots,n$; $\; i_{h}=d_{h-1}+1$). \vfill\eject \centerline{\bf References} \vskip .4in \item{[1]} B.\ Peterson, E.J.\ Taft, {\sl The Hopf algebra of linearly recursive sequences}, Aeq.\ Math.\ 20 (1980), 1-17 \item{[2]} L.\ Cerlienco, F.\ Piras, {\sl On the Continuous Dual of a Polynomial Bialgebra}, Communications in Alg.\ 19(10) (1991), 2707-2727 \item{[3]} L.\ Cerlienco, M.\ Mureddu, {\sl From algebraic sets to monomial linear bases by means of combinatorial algorithms}, Discrete Math.\ 139 (1995) (also in the ``Actes du $4^e$ Colloque {\it S\'eries formelles et combinatoire alg\'ebrique}, Montr\'eal, 1992) \item{[4]} L.\ Cerlienco, M.\ Mureddu, {\sl Algoritmi combinatori per l'interpolazione polinomiale in dimensione $\geq 2$}, Publ.\ I.R.M.A. Strasbourg, 1993, 461/S-24 Actes $24^e$ S\'eminaire Lotharingien, p.39-76 \item{[5]} F.\ Piras, {\sl 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 \item{[6]} F.\ Piras, {\sl Duals of polynomial modules and derivations in the formal power series algebras}, Rapporto interno n.\ 13, Dipartimento di Matematica, Cagliari (1994) \item{[7]} F.\ S.\ Macaulay. {\sl The Algebraic Theory of Modular Systems}, Cambridge Univ.\ Press, Cambridge, 1916. \item{[8]} H.\ M.\ M\"oller, F.\ Mora. {\sl New Constructive Methods in Classical Ideal Theory}, J.\ of Alg.\ {\bf 100} (1986), 138-178. \item{[9]} J.\ Erd\H{o}s, {\sl On the structure of ordered real vector spaces}, Publ.\ Math.\ Debrecen, 4 (1956), 334-343 \item{[10]} L.\ Fuchs, {\sl Partially Ordered Algebraic Systems}, Pergamon Press, 1994 \item{[11]} L.\ Cerlienco, M.\ Mureddu, {\sl Rappresentazione matriciale degli ordini l.c.\ su $\rr^n$ e su $\nn^n$}, Rapporto interno n.\ 16, Dipartimento di Matematica, Cagliari (1994) \item{[12]} D.~Cox, J.~Little, D.~O'Shea, {\sl Ideals, Varieties and Algorithms}, Springer-Verlag, New York, 1992 \item{[13]} M.Stillman, M.Stillman, D.Bayer {\sl Macaulay User Manual}, 1994 \item{[14]} L.Robbiano, {\sl Term Orderings on the Polynomial Ring}, Proceedings of EUROCAL 85. Springer Lec.\ Notes Comp.\ Sci.\ 204, 513--517 \item{[15]} L.~Robbiano, {\sl Introduzione all'algebra computazionale.} Appunti per il corso INDAM. (Roma 1986/87) \bye