
%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_1<d_2<\ldots<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 $\tilde C$ to any matrix $\hat C$. This 
matrix $\tilde C$ is said to be the {\it canonical 
lexicographic representation} of the term ordering $\preceq$. 
Indeed, it can be proved (see [11]) that two different matrices 
$\hat C$ and $\hat D$ represent the same term ordering on 
$\nn^n$ iff $\tilde C=\tilde D$.

It is convenient to divide our algorithm into two parts. The first 
part is aimed to ``capture''  a c.l.order $\preceq^{\rr}$ (in 
fact, the most suitable one for our purposes)  whose 
restriction to $\nn^n$ is $\preceq$; it  consists in constructing 
an $n\times n$ matrix $C=(c^i_j)$ by putting $n-m$ new rows inside 
those of $\hat C$, 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,\ldots,d_{m-1}+1$ off from  $C'$. 

Without loss of generality we may assume that the given matrix 
$\hat C$ is rationally reduced and also that, for each 
$h=1,\ldots,m$, the first $d_h$ vectors in (7) are rationally 
independent. 

The first part of the algorithm is described by recursion on 
$h\in \{1,\ldots,m\}$. For $h=1$, simply put 
$c^1_j=c^{\iota_1}_j$, $j=1,\ldots,n$. For $h>1$, 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




 
