    In "J.Symbolic Computation (1995), Vol. 20, 71-92."

ON $n$–DIMENSIONAL SEQUENCES. I 111Research supported by Science and
Engineering Research Council Grant GR/H15141. Current Address: School of
Mathematics and Physics, University of Queensland, Brisbane, Queensland 4072,
Australia, Email<EMAIL_ADDRESS>ORCID 0000-0003–518-5833.)

GRAHAM NORTON

Centre for Communications Research, University of Bristol, England.

Dedicated to Professor Peter J. Hilton on his retirement.

###### Abstract

Let $R$ be a commutative ring and let $n\geq 1.$ We study $\Gamma(s)$, the
generating function and Ann$(s)$, the ideal of characteristic polynomials of
$s$, an $n$–dimensional sequence over $R$.

We express $f(X_{1},\ldots,X_{n})\cdot\Gamma(s)(X_{1}^{-1},\ldots,X_{n}^{-1})$
as a partitioned sum. That is, we give (i) a $2^{n}$–fold “border” partition
(ii) an explicit expression for the product as a $2^{n}$–fold sum; the support
of each summand is contained in precisely one member of the partition. A key
summand is $\beta_{0}(f,s)$, the “border polynomial” of $f$ and $s$, which is
divisible by $X_{1}\cdots X_{n}$.

We say that $s$ is eventually rectilinear if the elimination ideals
Ann$(s)\cap R[X_{i}]$ contain an $f_{i}(X_{i})$ for $1\leq i\leq n$. In this
case, we show that $\mbox{Ann}(s)$ is the ideal quotient
$(\sum_{i=1}^{n}(f_{i})\ :\ \beta_{0}(f,s)/(X_{1}\cdots X_{n})).$

When $R$ and $R[[X_{1},X_{2},\ldots,X_{n}]]$ are factorial domains (e.g. $R$ a
principal ideal domain or ${{F}}[X_{1},\ldots,X_{n}]$), we compute the monic
generator $\gamma_{i}$ of $\mbox{Ann}(s)\cap R[X_{i}]$ from known
$f_{i}\in\mbox{Ann}(s)\cap R[X_{i}]$ or from a finite number of
$1$–dimensional linear recurring sequences over $R$. Over a field ${{F}}$ this
gives an $O(\prod_{i=1}^{n}\delta\gamma_{i}^{3})$ algorithm to compute an
${{F}}$–basis for $\mbox{Ann}(s)$.

AMS subject classifications (1991). Primary: 13P10, 68Q40; secondary: 94B15,
94B35.

##  1 Introduction

Linear recurring sequences (lrs) have a long and useful history; see for
example Cerlienco et al. (1987), Zierler (1959) and the works cited there.
Sequences over the integers and over finite fields are applied inter alia in
the Analysis of Algorithms (Greene & Knuth (1982)), Telecommunications
(McEliece (1987)), Coding Theory (Peterson & Weldon (1972), Fitzpatrick &
Norton (1991)) and Cryptography (Rueppel (1986)).

Applications of more general sequences have also appeared in the recent
literature: sequences over ${{Z}}/4{{Z}}$ (Boztaş, Hammons and Kumar (1992)),
over the Gaussian integers (Fan & Darnell (1994)) and $2$–dimensional lrs over
a field (i.e. lrs indexed by ${{N}}^{2}$); see for example Homer & Goldmann
(1985) and the works cited there, Lin & Liu (1988), Prabhu & Bose (1982) and
Sakata (1978, 1981, 1990), Fitzpatrick & Norton (1990), Chabanne & Norton
(1994)), Norton (1995b).

We consider $n$–dimensional ($n$–D) sequences over an arbitrary commutative
ring $R$, where $n\geq 1$. In Section 2 we set up our basic framework and
develop some preliminary properties of (i) the ideal Ann$(s)$ of
characteristic polynomials and (ii) $\Gamma(s)$, the generating function of an
$n$–D sequence $s$. Section 3 begins with a certain “border” partition and
studies the resulting decomposition of the product
$f(X_{1},\ldots,X_{n})\cdot\Gamma(s)(X_{1}^{-1},\ldots,X_{n}^{-1})$. Finally,
some properties of $\Gamma(s)$ and Ann$(s)$ for an “eventually rectilinear
(EVR)” sequence are given in Section 4.

In more detail, we study sequences over $R$ indexed negatively i.e. by
$-{{N}}^{n}$. The traditional approach to studying $\Gamma(s)$ and Ann$(s)$ is
to index sequences by ${{N}}^{n}$ and to regard $\Gamma(s)$ as an element of
the power series ring $R[[X_{1},\ldots,X_{n}]]$; in this way,
$R[X_{1},\ldots,X_{n}]$ acts by left–shifting. This approach complicates the
theory and proofs unnecessarily however. For example, it forces use of the
reciprocal $f^{\ast}$ of a polynomial $f$ (for $f^{\ast}\Gamma(s)$ to be in
the power series ring), resulting in a characteristic polynomial $f$ being
characterized in terms of $\Gamma(s)$, its degree and $f^{\ast}$. Compare also
Corollaries 2.9, 2.12 and 3.9, 3.10 below.

Instead, we let $f\circ s$ denote $f\in R[X_{1},\ldots,X_{n}]$ acting on $s$
by right–shifting (defined in Section 2) and let $\mbox{Ann}(s)$ denote the
annihilator ideal of $s$ with respect to right–shifting. We use the ring of
Laurent series $R((X_{1}^{-1},\ldots,X_{n}^{-1}))$ — rather than power series
— as the ambient ring. This is a much more natural approach: the ring of
Laurent series contains $R[X_{1},\ldots,X_{n}]$ as standard
$R[X_{1},\ldots,X_{n}]$–submodule, as well as the product $f\cdot\Gamma(s)$.

Section 2 defines a partial order on ${{Z}}^{n}$ and generalizes standard
interval notation to ${{Z}}^{n}$. We give the basic definitions, various
examples of $n$–D lrs, define EVR sequences and give some preliminary results
relating Ann$(s)$ and $\Gamma(s).$ For example, we show that $\Gamma(f\circ
s)$ is a summand of $f\cdot\Gamma(s).$

In Section 3, we define the border partition and the “border polynomial”
$\beta_{0}(f,s)$ of $f$ and $s$, a key summand of $f\cdot\Gamma(s)$, which is
divisible by $X_{1}\cdots X_{n}$. The remaining $2^{n}-2$ summands are “border
Laurent series”. We also show how these border summands can be rewritten using
a generalized Newton divided difference operator. Section 3 concludes with our
decomposition formula for $f\cdot\Gamma(s).$

Section 4 concentrates on EVR sequences over commutative rings, characterizing
their generating functions and exhibiting Ann$(s)$ as an ideal quotient. This
requires looking at the elimination ideals $\mbox{Ann}(s)\cap R[X_{i}],\
(1\leq i\leq n)$ via some ancillary results on 1–D sequences and 1–D
“associated sequences”.

We call $R$ potential if for all $n\geq 1,R[[X_{1},X_{2},\ldots,X_{n}]]$ is a
factorial — unique factorisation — domain. In this case, we show that the
above elimination ideals have a unique monic generator, and give two ways of
finding them: Theorem 4.13 and Corollary 4.16. We also generalize a result of
Cerlienco & Piras (1991) to sequences over potential domains (Theorem 4.18).

Finally, we show that if $s$ is EVR with $f_{i}\in\mbox{Ann}(s)\cap R[X_{i}]$,
then Ann$(s)$ is the ideal quotient $(\sum_{i=1}^{n}(f_{i})\ :\
\beta_{0}(f,s)/(X_{1}\cdots X_{n})).$ Algorithm 4.22 below shows how to
compute the corresponding basis for $\mbox{Ann}(s)$. There are known methods
(Buchberger (1985) and Cox et al. (1991)) for finding a basis of an ideal
quotient. The former yields a linear system of size
$\prod_{i=1}^{n}\delta\gamma_{i}$ and the latter yields a groebner basis for
$\mbox{Ann}(s)$ (with respect to the lexicographic term order).

Our original goals were two–fold: to try and simplify the Commutative Algebra
used in some early papers on the structure of 2–D cyclic codes (Imai & Arakaki
(1974), Ikai, Kosako & Kojima (1975, 1976), Imai (1977), Sakata (1978, 1981))
and secondly, to better understand Sakata (1988). It seemed that this would be
helped by undertaking a fundamental study of $n$–D sequences per se. (Even
though our principal application is the case $n=2$, we found that formulating
and proving our results for all $n\geq 1$ improved and simplified the theory.)
For some preliminary applications of this work to $n$–D cyclic codes and their
duals, see Norton (1995b). An application to simplified encoding of $n$–D
cyclic codes was presented in Norton (1995c).

We would suggest that the use of right–shifting and
$R((X_{1}^{-1},\ldots,X_{n}^{-1}))$ sharpens and simplifies the theory of both
finite and linear recurring sequences: (i) Theorem 4.19 generalizes the
treatment of rectilinear sequences over a field studied in Fitzpatrick &
Norton (1990) to EVR sequences over an arbitrary commutative ring and does not
require the “Reduction Lemma” of Fitzpatrick & Norton (1990) (ii) a
division–free analogue of the Berlekamp–Massey algorithm in $R((X^{-1}))$,
which computes a “minimal realization” $(f,\beta_{0}(f,s))$ of a finite
sequence $s$ over a domain $R$ appears in Norton (1995a), together with some
new applications of minimal realization (iii) a theory of division–free
minimal realizations of a finite $n$–D sequence over a domain will appear in
Norton (1995e); cf. Sakata (1988, 1990).

The results of this paper have been applied in Chabanne & Norton (1994). In
fact, the $n$–D key equation (loc. cit., Theorem 2.4) is a special case of
Corollary 4.14 over a finite field: $f_{i}$ is the error–locator
$X_{i}$–polynomial and $\beta_{0}(\prod_{i=1}^{n}f_{i},s)/(X_{1}\cdots X_{n})$
is the error–evaluator polynomial. Indeed, the minimal realization algorithm
of Norton (1995a) applied to the 1–D version of our key equation gives a
simpler way of decoding a $t$–error correcting Reed–Solomon code in at most
$t(10t+1)$ multiplications, without using Forney’s procedure to compute the
error magnitudes for example, Norton (1995d). It seems likely that our work
will also apply to decoding geometric Goppa codes.

Finally, our approach was partly suggested by the formulation for $1$–D
sequences given in Ferrand (1988), which uses $R((X))$ as the ambient ring. We
note that ${{F}}((X^{-1}))$, where ${{F}}$ denotes a field, was used in Welch
& Scholtz (1979) in the context of decoding BCH codes, and in Niedereiter
(1988).

###  1.1 Notation

In general, we use lower case Roman letters for elements, Greek letters for
functions and short names for sets. ${{N}}=\\{0,1,2,\ldots\\}$ and
${{Z}}=\\{0,\pm 1,\pm 2,\ldots\\}$.

Notation | Meaning
---|---
n |  $\\{1,2,\ldots,n\\}$.
$\pi_{i}$ | Projection of ${{Z}}^{n}$ onto the $i^{th}$ component, $i\in\hbox{\bf n}$.
$\hbox{\bf\it X}^{a}$ | Monomial $X_{1}^{a_{1}}X_{2}^{a_{2}}\ldots X_{n}^{a_{n}}$, where $a_{i}\in{{Z}},i\in\hbox{\bf n}$.
$\mathaccent 866{\bf X}_{i}$ | Variables $X_{1},X_{2},\ldots,X_{n}$, excluding $X_{i},i\in\hbox{\bf n}$.
$P_{n}$ | Polynomials over $R$ in $X_{1},\ldots,X_{n}$
$L_{n}$ | Laurent series over $R$ in $X_{1}^{-1},\ldots,X_{n}^{-1}.$
$S_{n}$ | Power series over $R$ in $X_{1}^{-1},\ldots,X_{n}^{-1}.$
$\delta_{i}g$ | Degree of $g\in L_{n}$ as Laurent series in $X_{i}^{-1},i\in\hbox{\bf n}$.
$\delta g$ | Degree of $g\in L_{n}$ i.e. an $n$–vector.
$S^{n}(R)^{-}$ |  $n$–dimensional sequences over $R$, indexed by $-{{N}}^{n}$.
$f\circ s$ | Polynomial $f$ acting on sequence $s$ by shifting.
$\beta_{0}(f,s)$ | Border polynomial of $f$ and $s$.
$\mbox{Ann}(s)$ | Characteristic ideal of $s$.
$\gamma(s)$ | Primitive generator of $\mbox{Ann}(s)$, $s\in S^{1}(R)^{-},R$ factorial.
$s^{(i,\ast)}$ |  $s$ regarded as an element of $S^{1}(R[[\mathaccent 866{\bf X}_{i}^{-\hbox{\bf\scriptsize 1}}]])^{-}$.
$\Gamma(s)$ | Generating function of $s$, as element of $S_{n}.$

We equate sums and products over the empty set to $0$ and $1$ respectively.

##  2 Preliminaries

###  2.1  ${{Z}}^{n}$

Throughout the paper, $n\geq 1$ and $\hbox{\bf n}=\\{1,2,\ldots,n\\}$.
Addition and negation in ${{Z}}^{n}$ are componentwise; thus we can write
$-{{N}}^{n}=(-{{N}})^{n}.$ We let $\hbox{\bf 0},\hbox{\bf 1}$ be the points in
${{Z}}^{n}$ with all components $0,1$ respectively.

For $i\in\hbox{\bf n},\ \pi_{i}:{{Z}}^{n}\rightarrow{{Z}}$ is the projection
onto the $i^{th}$ factor; for $a\in{{Z}}^{n}$, we also write $a_{i}$ for
$\pi_{i}a$.

${{Z}}^{n}$ is partially ordered by the relation $\leq$ on each component:
$a\leq b\mbox{ iff }a_{i}\leq b_{i}$ for all $i\in\hbox{\bf n}$; $a\geq b$ is
synonymous with $b\leq a$. We write $a\not\geq b$ to mean that $a\geq b$ is
false, that is, for some $i\in\hbox{\bf n}$, $a_{i}<b_{i}$.

We generalize the usual interval notation in ${{Z}}$ to describe certain
subsets of ${{Z}}^{n}$:
for $a,b\in{{Z}}^{n},$

$(-\infty,a]=\\{c\in{{Z}}^{n}\ :\ c\leq a\\}\mbox{ and
}[a,\infty)=\\{c\in{{Z}}^{n}\ :\ a\leq c\\}$ $[a,b]=\\{c\in{{Z}}^{n}\ :\ a\leq
c\leq b\\}=\prod_{i=1}^{n}[a_{i},b_{i}]$ $(a,b]=\\{c\in{{Z}}^{n}\ :\ a\not\geq
c\leq b\\}=(-\infty,b]\setminus(-\infty,a]$ $[a,b)=\\{c\in{{Z}}^{n}\ :\ a\leq
c\not\geq b\\}=[a,\infty)\setminus[b,\infty).$

###  2.2 Polynomials and Laurent series

$R$ is a commutative ring with $1\neq 0$ and $P_{n}$ denotes the ring of
$R$–polynomials in $X_{1},\ldots,X_{n}$; $L_{n}$ denotes the ring of Laurent
series in $X_{1}^{-1},\ldots,X_{n}^{-1}$, which contains $P_{n}$. Indeed,
$L_{n}$ is a $P_{n}$–module which has $P_{n}$ as standard $P_{n}$–submodule,
where the action of $X_{i}$ is a shift to the right. $S_{n}\subseteq L_{n}$
denotes the ring of $R$–power series in $X_{1}^{-1},\ldots,X_{n}^{-1}.$

For $a\in{{Z}}^{n}$, we abbreviate $X_{1}^{a_{1}}X_{2}^{a_{2}}\ldots
X_{n}^{a_{n}}$ to $\hbox{\bf\it X}^{a}$. For $i\in\hbox{\bf n},\ \mathaccent
866{\bf X}_{i}$ denotes the variables $X_{1},\ldots,X_{n}$, excluding $X_{i}$.

For $G\in L_{n}\setminus\\{0\\},\ G_{a}$ denotes a coefficient of $G$, and
$\mbox{Supp}(G)=\\{a\in{{Z}}^{n}:G_{a}\neq 0\\}$ is called the support of $G;\
\mbox{Supp}(0)=\emptyset$. If $G\in L_{n}$ and $A\subseteq{{Z}}^{n}$, then
$G|A=\sum_{a\in A\cap{\scriptsize Supp}(G)}G_{a}\hbox{\bf\it X}^{a}$.

We use the (exponential) valuation on $R((X^{-1}))$, which extends the degree
function on $R[X]$. For convenience, we also denote it by $\delta;\ \delta
0=-\infty$. Thus for $G\in R((X^{-1}))\setminus\\{0\\}$, $\delta
G=\max\mbox{Supp}(G)$ and for $G,H\in R((X^{-1})),\delta(GH)\leq\delta
G+\delta H$.

For $G\in L_{n}$ and $i\in\hbox{\bf n}$, we let $\delta_{i}G$ be the $i^{th}$
partial degree of $G$, that is, the degree of $G$ regarded as a Laurent series
in $X_{i}^{-1}$; $\delta G$ is the $n$–vector with components $\delta_{i}G$.
We have $\mbox{Supp}(G)\subseteq(-\infty,\delta G]$.

The letter $f$ will always mean an element of $P_{n}$ and we write
$f=f(\hbox{\bf\it X})=\sum_{a\in{\scriptsize Supp}(f)}f_{a}\ \hbox{\bf\it
X}^{a}.$

Supp$(f)\subseteq[\hbox{\bf 0},\delta f]$, and so for $a\in\mbox{Supp}(f),\
\delta f-a$ is a well-defined point in ${{N}}^{n}.$ If $f\neq 0$, the
reciprocal of $f$ is $f^{*}=\hbox{\bf\it X}^{\delta f}\ f(\hbox{\bf\it
X}^{\,\hbox{\bf\scriptsize-1}})=\sum_{a\in{\scriptsize Supp}(f)}f_{a}\
\hbox{\bf\it X}^{\delta f-a}$ and $0^{*}=0.$ It is easy to verify that
$f=\hbox{\bf\it X}^{\delta f-\delta f^{*}}f^{**}.$

###  2.3 Linear recurring sequences

$S^{n}(R)^{-}$ denotes the set of functions $-{{N}}^{n}\rightarrow R$ i.e. the
set of $R$–sequences indexed by $-{{N}}^{n};$ the value $s(a)$ is written
$s_{a}.$ The letter $s$ will always denote a sequence in $S^{n}(R)^{-}$, and
to avoid trivial cases, we assume that $s$ is non–zero. With addition and
scalar product defined componentwise, $S^{n}(R)^{-}$ becomes a unitary
$R$–module. Further, the unit sequence and the Hadamard product make
$S^{n}(R)^{-}$ into a commutative $R$–algebra with $1$. In particular, its
ideals are algebra ideals. There is a right shift action of $P_{n}$ on
$S^{n}(R)^{-}$ given by

$\left(\sum_{\hbox{\bf\scriptsize 0}\leq a\leq\delta f}f_{a}\hbox{\bf\it
X}^{a}\circ s\right)_{b}=\sum_{\hbox{\bf\scriptsize 0}\leq a\leq\delta
f}f_{a}s_{b-a}$

where $b\leq\hbox{\bf 0}$. This makes $S^{n}(R)^{-}$ into a $P_{n}$–module.

###### Definition 2.1

The annihilator or characteristic ideal of (characteristic polynomials) of $s$
is $\mbox{Ann}(s)=\\{f\in P_{n}:f\circ s=0\\}.$ We say that $s$ is a
(homogeneous) $n$–dimensional linear recurring sequence ($n$–D lrs) if
$\mbox{Ann}(s)\neq\\{0\\}$.

###### Example 2.2

(a) Let $a\geq\hbox{\bf 0}$. Then $s_{b}=0$ for
$b\leq-a\Longleftrightarrow\hbox{\bf\it X}^{a}\in\mbox{Ann}(s)$.

(b) Let $r\in R\setminus\\{0\\},\ a\leq\hbox{\bf 0}$ and
$s_{a}=r^{-\sum_{i=1}^{n}a_{i}}$. Then $\hbox{\bf\it
X}-r^{n}\in\mbox{Ann}(s)$.

(c) If $s\in S^{2}(R)^{-}$ then $s_{a-1,b}=s_{a,b}=s_{a,b-1}\mbox{ for
}a,b\leq\hbox{\bf 0}\Longleftrightarrow X_{1}-1,X_{2}-1\in\mbox{Ann}(s)$.

(d) We say that $s$ is $n$–periodic if for some $d\geq\hbox{\bf
1},s_{a-d_{i}}=s_{a}$ for all $a\leq\hbox{\bf 0}$ and $i\in\hbox{\bf n}$ i.e.
$s$ is $n$–periodic iff for some $d\geq\hbox{\bf 1}$,
$X_{i}^{d_{i}}-1\in\mbox{Ann}(s)$ for all $i\in\hbox{\bf n};\ s$ is eventually
$n$–periodic if for some $d\geq\hbox{\bf 1},e\geq\hbox{\bf 0},\
X_{i}^{e_{i}}(X_{i}^{d_{i}}-1)\in\mbox{Ann}(s)$ for all $i\in\hbox{\bf n}.$

We now generalize the notion of a rectilinear $n$-D lrs over a field ${{F}}$
from Fitzpatrick & Norton (1990). (Recall that $s$ is rectilinear if for all
$i\in\hbox{\bf n}$, there is an $f_{i}\in\mbox{Ann}(s)\cap{{F}}[X_{i}]$ with
$\delta f_{i}\geq 1$ and $f_{i}(0)\neq 0$.)

###### Definition 2.3

We say that $s$ is eventually rectilinear (EVR) if for all $i\in\hbox{\bf n}$,
there is an $f_{i}\in\mbox{Ann}(s)\cap R[X_{i}]$ with $\delta f_{i}\geq 1$.

If $R$ is a domain and $s$ is non–zero, then $s$ is EVR
$\Longleftrightarrow\mbox{Ann}(s)\cap R[X_{i}]\neq\\{0\\}$ for all
$i\in\hbox{\bf n}.$

EVR sequences include $1$–D lrs over a commutative ring, eventually periodic
lrs (Nerode (1958)), rectilinear lrs over a field (Fitzpatrick & Norton
(1990)) and “$n$–linearly recursive functions over a field” (Cerlienco & Piras
(1991)). If $s$ is EVR and $g\in P_{n}$, then $g\circ s$ is EVR since
$f\circ(g\circ s)=(fg)\circ s=g\circ(f\circ s)$.

###### Example 2.4

(a) Let $s\in S^{2}(R)^{-}$ satisfy $s_{0,j}=1$ for $j\leq 0$ and $s_{i,j}=0$
otherwise. Then $X_{1},\ X_{2}-1\in\mbox{Ann}(s)$, so that $s$ is EVR. It is
easy to check that $\mbox{Ann}(s)\cap R[X_{1}]=(X_{1})$, so that $s$ is not
rectilinear.

(b) Let $s^{\prime}\in S^{2}(R)^{-}$ satisfy $s^{\prime}_{a,b}=1$ if $a=b$ and
$s^{\prime}_{a,b}=0$ otherwise. Then $X_{1}X_{2}-1\in\mbox{Ann}(s^{\prime})$
but $\mbox{Ann}(s^{\prime})\cap R[X_{i}]=\\{0\\}$ for $i=1,\ 2$:

if $f=\sum_{a=0}^{\delta f}f_{a}X_{1}^{a}\in R[X_{1}]$ and $f\circ
s^{\prime}=0$ then for $0\leq b\leq\delta f$,

$f_{b}=\sum_{a=0}^{\delta f}f_{a}s^{\prime}_{-a,-b}=\left(\sum_{a=0}^{\delta
f}f_{a}X_{1}^{a}\circ s^{\prime}\right)_{0,-b}=0.$

Similarly, $\mbox{Ann}(s^{\prime})\cap R[X_{2}]=\\{0\\}$. Thus $s^{\prime}$ is
not EVR. In particular, a 2–D lrs over GF(2) need not be 2–periodic (in
contrast to the 1–D situation).

In the literature, the standard approach to $n$–D lrs is to regard
$S^{n}(R)=\\{s:{{N}}^{n}\rightarrow R\\}$ as a $P_{n}$–module via left
shifting (which we also denote by $\circ$ ):

$\left(\sum_{\hbox{\bf\scriptsize 0}\leq a\leq\delta f}f_{a}\hbox{\bf\it
X}^{a}\circ s\right)_{b}=\sum_{\hbox{\bf\scriptsize 0}\leq a\leq\delta
f}f_{a}s_{b+a}$

where $b\geq\hbox{\bf 0}$.

###### Proposition 2.5

The map ${}^{-}:S^{n}(R)\rightarrow S^{n}(R)^{-}$ given by
$(s^{-})_{a}=s_{-a}$ for $a\leq\hbox{\bf 0}$ is a $P_{n}$–module map.

Proof.  Let $s\in S^{n}(R),\ b\leq\hbox{\bf 0}$ and
$f=\sum_{\hbox{\bf\scriptsize 0}\leq a\leq\delta f}f_{a}\hbox{\bf\it X}^{a}\in
P_{n}$. Then

$(f\circ s)^{-}_{b}=(f\circ s)_{-b}=\sum_{\hbox{\bf\scriptsize 0}\leq
a\leq\delta f}f_{a}s_{-b+a}=\sum_{\hbox{\bf\scriptsize 0}\leq a\leq\delta
f}f_{a}s^{-}_{b-a}=(f\circ s^{-})_{b}$

so that $(f\circ s)^{-}=f\circ s^{-}$. It is trivial that - preserves
addition, so - is a $P_{n}$–module map. $\bullet$

There is an obvious two–sided inverse of -, so that $S^{n}(R)^{-}$ and
$S^{n}(R)$ are isomorphic $P_{n}$–modules, $s$ is an lrs iff $s^{-}$ is an
lrs, and - induces an isomorphism of $\mbox{Ann}(s)$ and $\mbox{Ann}(s^{-})$.

###  2.4 Ann(s) and generating functions

The generating function of $s$ is

$\Gamma(s)=\sum_{a\leq\hbox{\bf\scriptsize 0}}s_{a}\hbox{\bf\it X}^{a}\in
S_{n}.$

Strictly speaking, the definition of $\Gamma(s)$ should incorporate a linear
(total) ordering on $-{{N}}^{n}$; this has been omitted since the enumeration
will either be clear or not used. Thus for Example 2.4,
$\Gamma(s)=X_{2}/(X_{2}-1)$ and
$\Gamma(s^{\prime})=X_{1}X_{2}/(X_{1}X_{2}-1).$

Since $\delta(f\Gamma(s))\leq\delta f$, we have
$\mbox{Supp}(f\Gamma(s))\subseteq(-\infty,\delta f]$.

###### Proposition 2.6

$(f\Gamma(s))|(-\infty,\hbox{\bf 0}]=\Gamma(f\circ s).$

Proof.  If $a\leq\hbox{\bf 0}$ and $f=\sum_{\hbox{\bf\scriptsize 0}\leq
b\leq\delta f}f_{b}\hbox{\bf\it X}^{b}$, then
$(f\Gamma(s))_{a}=\sum_{\hbox{\bf\scriptsize 0}\leq b\leq\delta
f}f_{b}s_{a-b}=(f\circ s)_{a}.$ $\bullet$

We note that Lemma 4.1 of Fitzpatrick & Norton (1990) is an analogue of the
preceding result for left–shifting.

###### Proposition 2.7

The following are equivalent:

(a) $f\in\mbox{Ann}(s)$

(b) $(f\Gamma(s))|(-\infty,\hbox{\bf 0}]=0$

(c) $\mbox{Supp}(f\Gamma(s))\subseteq(\hbox{\bf 0},\delta f]$

(d) $\exists G\in L_{n}$ such that $f\Gamma(s)=\hbox{\bf\it X}G$ and
$\mbox{Supp}(G)\subseteq(-\hbox{\bf 1},\delta f-\hbox{\bf 1}]$.

Proof.  We omit the proof that (a) $\Longleftrightarrow$ (b)
$\Longleftrightarrow$ (c). (c) $\Longleftrightarrow$ (d): It is a
straightforward exercise that $\mbox{Supp}(f\Gamma(s))\subseteq(\hbox{\bf
0},\delta f]\ \Longleftrightarrow\mbox{Supp}(\hbox{\bf\it
X}^{-\hbox{\bf\scriptsize 1}}f\Gamma(s))\subseteq(-\hbox{\bf 1},\delta
f-\hbox{\bf 1}]$. $\bullet$

Setting $n=1$ in Proposition 2.7, we obtain a simple characterization of
$\mbox{Ann}(s)$ which does not use use $\delta f$ or the reciprocal of $f$
(cf. Niederreiter (1988), Lemmas 1, 2 when $R$ is a field):

###### Corollary 2.8

Let $s\in S^{1}(R)^{-}$. Then $f\in\mbox{Ann}(s)\Longleftrightarrow
f\Gamma(s)\in XR[X].$

###### Corollary 2.9

Let $s$ be an lrs. Then $\Gamma(s)=\hbox{\bf\it X}G/f$ for some non–zero
$f\in\mbox{Ann}(s)$ and $G\in L_{n}$ such that
$\mbox{Supp}(G)\subseteq(-\hbox{\bf 1},\delta f-\hbox{\bf 1}]$.

Conversely, if $f$ is monic, $G\in L_{n}$ and
$\mbox{Supp}(G)\subseteq(-\hbox{\bf 1},\delta f-\hbox{\bf 1}]$, then
$\hbox{\bf\it X}G/f\in S_{n}$ and $s$ defined by $\Gamma(s)=\hbox{\bf\it
X}G/f$ is an lrs with $f\in\mbox{Ann}(s)$.

Proof.  If $f$ is monic, then $u=\hbox{\bf\it X}^{-\delta f}f$ is a unit in
$S_{n}$. Writing $G=\sum_{a\in(-\hbox{\bf\scriptsize 1},\delta
f-\hbox{\bf\scriptsize 1}]}G_{a}\hbox{\bf\it X}^{a}$, we obtain

$\hbox{\bf\it X}Gu=f\ \sum_{a\in(-\hbox{\bf\scriptsize 1},\delta
f-\hbox{\bf\scriptsize 1}]}G_{a}\ \hbox{\bf\it X}^{a+\hbox{\bf\scriptsize
1}-\delta f}=f\sum_{b\in(-\delta f,\hbox{\bf\scriptsize
0}]}G_{b-\hbox{\bf\scriptsize 1}+\delta f}\ \hbox{\bf\it X}^{b}=fH$

say, where $H\in S_{n}$ and so $\hbox{\bf\it X}G/f=H/u\in S_{n}.$ The result
now follows from Proposition 2.7. $\bullet$

“Rational lrs” are an important special case of Corollary 2.9:

###### Definition 2.10

We will say that $s$ is a rational lrs if for some $f\in
P_{n}\setminus\\{0\\},\ f\cdot\Gamma(s)\in\hbox{\bf\it X}P_{n}.$

Certainly every 1–D lrs is rational, but this fails for $n\geq 2$: if
$G(X_{1}^{-1})\in S_{1}$ is not a rational function, $f\in P_{n},\ \delta
f\geq\hbox{\bf 1}$, and $s$ is defined by $\Gamma(s)=\mathaccent 866{\bf
X}_{1}G/f$, then $f\in\mbox{Ann}(s)$, but $s$ is not rational. Example 2.4(b)
shows that for $n\geq 2$, not all rational lrs are EVR. We will see in Theorem
4.9 below that EVR lrs are always rational.

For completeness, we now give an analogue of Corollary 2.9 for sequences
indexed by ${{N}}^{n}$ which use left–shifting (Corollary 2.12 below). This
analogue could have been deduced from Propositions 2.5, 2.7 and an analogue of
Proposition 2.7, but it is easier to appeal directly to the definitions:

###### Lemma 2.11

Let $a\geq\hbox{\bf 0}$ and $s:{{N}}^{n}\rightarrow R$ (so that $\Gamma(s)\in
R[[\hbox{\bf\it X}]]$). Then

$\hbox{\bf\it
X}^{a}f^{\ast}\in\mbox{Ann}(s)\Longleftrightarrow\mbox{Supp}(f\Gamma(s))\subseteq[\hbox{\bf
0},a+\delta f).$

In particular, if $\mbox{Supp}(f\Gamma(s))\subseteq[\hbox{\bf 0},\delta f)$,
then $f^{\ast}\in\mbox{Ann}(s)$.

Proof.  For any $b\geq\hbox{\bf 0}$,

$\displaystyle\left(\hbox{\bf\it X}^{a}f^{\ast}\circ s\right)_{b}$
$\displaystyle=$ $\displaystyle\left(\sum_{c\in Supp(f)}\ f_{c}\hbox{\bf\it
X}^{a+\delta f-c}\circ\ s\right)_{b}$ $\displaystyle=$
$\displaystyle\sum_{c\in Supp(f)}f_{c}s_{b+a+\delta
f-c}=(f\Gamma(s))_{a+b+\delta f}$

and so

$\hbox{\bf\it
X}^{a}f^{\ast}\in\mbox{Ann}(s)\Longleftrightarrow(f\Gamma(s))|[a+\delta
f,\infty)=0\Longleftrightarrow\mbox{Supp}(f\Gamma(s))\subseteq[\hbox{\bf
0},a+\delta f).$

$\bullet$

###### Corollary 2.12

Let $s:{{N}}^{n}\rightarrow R$ be an lrs. Then $\Gamma(s)=G/f^{*}$ for some
non–zero $f\in Ann(s)$ and $G\in R[[\hbox{\bf\it X}]]$ such that
Supp$(G)\subseteq[\hbox{\bf 0},\delta f).$

Conversely, suppose that $f(\hbox{\bf 0})=1$ and $G\in R[[\hbox{\bf\it X}]]$
satisfies $\ \mbox{Supp}(G)\subseteq[\hbox{\bf 0},d)$ for some
$d\in{{N}}^{\hbox{\bf\scriptsize n}}\setminus\\{\hbox{\bf 0}\\}$. Define
$m\in{{N}}^{n}$ by

$\pi_{i}m=\max\\{0,d_{i}-\delta_{i}f\\}.$

If $s$ is the $n$–D lrs with $\Gamma(s)=G/f$ and $a\geq m$, then $\hbox{\bf\it
X}^{a}f^{\ast}\in\mbox{Ann}(s)$.

Proof.  The first part is an easy consequence of Lemma 2.11 applied to
$f=\hbox{\bf\it X}^{\delta f-\delta f^{\ast}}(f^{\ast})^{\ast}$.

For the converse, if $a\geq m$, then $a\geq\hbox{\bf 0}$ and $d\leq a+\delta
f$. Therefore $[\hbox{\bf 0},d)\subseteq[\hbox{\bf 0},a+\delta f)$, so the
result follows from Lemma 2.11. $\bullet$

Here, rational lrs correspond to $\Gamma(s)=g/f^{\ast}$, where $f,g\in P_{n},\
\delta f\geq\hbox{\bf 1}$ and $\delta g\leq\delta f-\hbox{\bf 1}$; in this
case, we can take $d=\delta g+\hbox{\bf 1}$ in Corollary 2.12. If in addition
$n=1$ in Corollary 2.12, we obtain Fitzpatrick & Norton (1995), Theorem 4.1.

##  3 A decomposition formula for $f\cdot\Gamma(s)$

###  3.1 The border partition

For $d\geq\hbox{\bf 1},\ (-\infty,d]=\prod_{i=1}^{n}(-\infty,d_{i}]$ and so

$\beta(-\infty,d]=\prod_{i=1}^{n}\\{(-\infty,0],[1,d_{i}]\\}$

is a partition of $(-\infty,d]$. We will abbreviate $\beta(-\infty,d]$ to
$\beta$ when $d$ is understood.

It is convenient to use binary notation to index the $2^{n}$ members of the
product partition $\beta(-\infty,d]$: for $0\leq k\leq 2^{n}-1$, we write the
($n$–bit) binary representation of $k$ with the most significant bit
$b_{n}(k)$ of $k$ on the right (so that the bit ordering is the same as the
ordering of the components of ${{Z}}^{n}$) and index the $k^{th}$ member
$\beta_{k}(-\infty,d]$ of $\beta(-\infty,d]$ by

$b_{i}(k)=1\mbox{ iff }\pi_{i}(\beta_{k}(-\infty,d])=(-\infty,0].$

For example, if $n=2,\ \beta_{0}=\beta_{00}=[1,d_{1}]\times[1,d_{2}],\
\beta_{1}=\beta_{10}=[1,d_{1}]\times(-\infty,d_{2}],\
\beta_{2}=\beta_{01}=(-\infty,d_{1}]\times[1,d_{2}]$ etc.; notice that
$\beta_{0}\cup\beta_{1}\cup\beta_{2}$ ”borders” $\beta_{3}=(-\infty,\hbox{\bf
0}]$ in $(-\infty,d].$

We will call $\bigcup\\{\beta_{k}(-\infty,d]\ :0\leq k<2^{n}-1\\}$ the border
of $(-\infty,\hbox{\bf 0}]$ in $(-\infty,d]$ and $\beta(-\infty,d]$ the border
partition of $(-\infty,d]$.

###  3.2 The border polynomial

###### Definition 3.1

Let $\delta f\geq\hbox{\bf 1}$ and let $\beta$ be the border partition of
$(-\infty,\delta f].$ For $0\leq k\leq 2^{n}-1$, we define $\beta_{k}(f,s)\in
L_{n}$ by

$\beta_{k}(f,s)=(f\cdot\Gamma(s))\ |\ \beta_{k}.$

###### Proposition 3.2

Let $\delta f\geq\hbox{\bf 1}$ and let $\beta$ be the border partition of
$(-\infty,\delta f].$ Then

$f\cdot\Gamma(s)=\sum_{k=0}^{2^{n}-1}\beta_{k}(f,s)$

where $Supp(\beta_{k}(f,s))\subseteq\beta_{k}$ for $0\leq k\leq 2^{n}-1$ and
$\beta_{2^{n}-1}(f,s)=\Gamma(f\circ s).$

Proof.  This follows immediately from the fact that $\beta$ is a partition of
$(-\infty,\delta f]$ and from Proposition 2.6. $\bullet$

Since $\beta_{0}(f,s)\in P_{n}$, we call it the border polynomial of $f$ and
$s$. We will express $\beta_{0}(f,s)$ in terms of $s$ and generalized Newton
divided differences of $f$. Recall Newton’s divided difference operator $\nu$
for $n=1:$

$\nu:R[X]\rightarrow R[X]$ is $\nu f=(f-f_{0})/X$, and for $a\geq 1,\ \nu^{a}$
is defined iteratively by $\nu^{0}f=f\mbox{ and }\nu^{a}=\nu\nu^{a-1}.$ It is
easy to see that if $d\geq 1$ and $f=f_{0}+f_{1}X+\ldots+f_{d}X^{d}$ , then
for $0\leq a\leq d$,

$\nu^{a}f=f_{a}\ +\ f_{a+1}\ X+\ldots+\
f_{d}X^{d-a}=\sum_{b=a}^{d}f_{b}X^{b-a}$

whereas $\nu^{a}f=0$ if $a>\delta f.$ Thus $\delta(\nu^{a}f)=\delta f-a$ if
$0\leq a\leq\delta f$.

###### Definition 3.3

For $n\geq 1,\ a\geq\hbox{\bf 0}$ and $f\in P_{n}$, we define

$\nu^{a}f=\left(f\ |\ [a,\delta f]\right)/\hbox{\bf\it X}^{a}.$

Clearly $\nu^{\hbox{\bf\scriptsize 0}}f=f$ and the numerator is divisible by
$\hbox{\bf\it X}^{a}$. Indeed, if $\hbox{\bf 0}\leq a\leq\delta f$, then
$\nu^{a}f=\sum_{a\leq b\leq\delta f}f_{b}\hbox{\bf\it X}^{b-a}$ and
$\delta(\nu^{a}f)\leq\delta f-a$. For example, if $\delta f=(2,3)$ then

$\nu^{(1,1)}f=f_{1,1}+f_{1,2}X_{2}+f_{2,1}X_{1}+f_{1,3}X_{2}^{2}+f_{2,2}X_{1}X_{2}+f_{2,3}X_{1}X_{2}^{2}.$

On the other hand, if $a\geq\delta f+\hbox{\bf 1}$, then $\nu^{a}f=0.$ When
$n=1,\ \nu^{a}$ coincides with Newton’s operator.

###### Lemma 3.4

If $\delta f\geq\hbox{\bf 1}$, then

$\beta_{0}(f,s)=\hbox{\bf\it X}\sum_{\hbox{\bf\scriptsize 0}\leq a\leq\delta
f-\hbox{\bf\scriptsize 1}}s_{-a}\ \nu^{a+\hbox{\bf\scriptsize 1}}f.$

Proof.

$\displaystyle\beta_{0}(f,s)$ $\displaystyle=$
$\displaystyle\sum_{\hbox{\bf\scriptsize 1}\leq a\leq\delta
f}\left(f\Gamma(s)\right)_{a}\hbox{\bf\it X}^{a}$ $\displaystyle=$
$\displaystyle\sum_{\hbox{\bf\scriptsize 1}\leq a\leq\delta
f}\left(\sum_{a\leq b\leq\delta f}f_{b}s_{a-b}\right)\hbox{\bf\it X}^{a}$
$\displaystyle=$ $\displaystyle\sum_{\hbox{\bf\scriptsize 1}\leq a\leq\delta
f}\left(\sum_{\hbox{\bf\scriptsize 0}\leq c\leq\delta
f-a}f_{a+c}s_{-c}\hbox{\bf\it X}^{a}\right)$ $\displaystyle=$
$\displaystyle\sum_{\hbox{\bf\scriptsize 0}\leq c\leq\delta
f-\hbox{\bf\scriptsize 1}}s_{-c}\left(\sum_{\hbox{\bf\scriptsize 1}\leq
a\leq\delta f-c}f_{a+c}\hbox{\bf\it X}^{a}\right)$ $\displaystyle=$
$\displaystyle\sum_{\hbox{\bf\scriptsize 0}\leq c\leq\delta
f-\hbox{\bf\scriptsize 1}}s_{-c}\left(\sum_{c+\hbox{\bf\scriptsize 1}\leq
d\leq\delta f}f_{d}\hbox{\bf\it X}^{d-c}\right)$ $\displaystyle=$
$\displaystyle\hbox{\bf\it X}\sum_{\hbox{\bf\scriptsize 0}\leq c\leq\delta
f-\hbox{\bf\scriptsize 1}}s_{-c}\left(\sum_{c+\hbox{\bf\scriptsize 1}\leq
d\leq\delta f}f_{d}\hbox{\bf\it X}^{d-(c+\hbox{\bf\scriptsize 1})}\right)$
$\displaystyle=$ $\displaystyle\hbox{\bf\it X}\sum_{\hbox{\bf\scriptsize
0}\leq c\leq\delta f-\hbox{\bf\scriptsize 1}}s_{-c}\
\nu^{c+\hbox{\bf\scriptsize 1}}f.$

$\bullet$

Setting $n=1$, we obtain the following result (cf. Ferrand (1988), Section
1.3):

###### Corollary 3.5

If $n=1$ and $\delta f\geq 1$, then

$f\Gamma(s)=X\sum_{a=0}^{\delta f-1}s_{-a}\ \nu^{a+1}f\ +\Gamma(f\circ s).$

###  3.3 The Border Laurent Series

We have determined the summands $\beta_{k}(f,s)$ of $f\cdot\Gamma(s)$ in
Proposition 3.2 for $k=0,\ 2^{n}-1.$ In this subsection, we determine the
remaining summands (when $n\geq 2$).

If $0<k<2^{n}-1,$ then for some $i,j,\ 1\leq i,j\leq n,\ b_{i}(k)=0$ and
$b_{j}(k)=1$, so that for these $i,j,\ \beta_{k}(f,s)$ involves polynomials in
$X_{i}$ and power series in $X_{j}^{-1}$. For this reason, we call
$\\{\beta_{k}(f,s)\ :\ 0<k<2^{n}-1\\}$ the border Laurent series of $f$ and
$s$.

In order to discuss these series, we need to extend some of our earlier
definitions:

i denotes a subset of $\hbox{\bf n}=\\{1,2,\ldots,n\\}$ with cardinality
$|\hbox{\bf i}|$ and $\hbox{\bf i}^{\prime}=\hbox{\bf n}\setminus\hbox{\bf
i};\ \hbox{\bf i}\ll\hbox{\bf n}$ means that i is a proper subset of
$\hbox{\bf n}.$ If $\hbox{\bf i}\ll\hbox{\bf n}$ and
$a\in{{N}}^{\hbox{\bf\scriptsize i}},\ X_{\hbox{\bf\scriptsize i}}^{a}$ has
the obvious meaning and for $1\leq i\leq n$, we write $X_{i}$ for
$X_{\\{i\\}}$. We let $\pi_{\hbox{\bf\scriptsize i}}$ be the projection of
${{Z}}^{n}$ onto ${{Z}}^{\hbox{\bf\scriptsize i}}$. If
$a\in{{Z}}^{\hbox{\bf\scriptsize i}}$ and
$a^{\prime}\in{{Z}}^{\hbox{\bf\scriptsize i}^{\prime}}$, then $(a,a^{\prime})$
is the unique element of ${{Z}}^{n}$ with $\pi_{\hbox{\bf\scriptsize
i}}(a,a^{\prime})=a$ and $\pi_{\hbox{\bf\scriptsize
i}^{\prime}}(a,a^{\prime})=a^{\prime}$. Lastly, for $\delta f\geq\hbox{\bf
1},\ \delta_{\hbox{\bf\scriptsize i}}f=\pi_{\hbox{\bf\scriptsize i}}\delta f.$

###### Definition 3.6

Let $n\geq 2$ and $\hbox{\bf i}\ll\hbox{\bf n}$.

(a) For $a\in-{{N}}^{\hbox{\bf\scriptsize i}}$, the $a$–section of $s$ is
$s^{(a)}\in S^{|\hbox{\bf\scriptsize i}^{\prime}|}(R)$ given by

$s^{(a)}_{\ a^{\prime}}=s_{(a,a^{\prime})}$

for $a^{\prime}\in-{{N}}^{\hbox{\bf\scriptsize i}^{\prime}}$.

(b) For $\hbox{\bf 0}\leq a\leq\delta_{\hbox{\bf\scriptsize i}}f$, the
$a$–section of $f$ is $f^{(a)}\in R[X_{\hbox{\bf\scriptsize i}^{\prime}}]$
given by

$f^{(a)}(X_{\hbox{\bf\scriptsize i}^{\prime}})=\sum_{\hbox{\bf\scriptsize
0}^{\prime}\leq a^{\prime}\leq\delta_{\hbox{\bf\scriptsize
i}^{\prime}}f}f_{(a,a^{\prime})}X_{\hbox{\bf\scriptsize
i}^{\prime}}^{a^{\prime}}.$

Clearly $\delta f^{(a)}\leq\delta_{\hbox{\bf\scriptsize i}^{\prime}}f$ and for
$\hbox{\bf 0}^{\prime}\leq a^{\prime}\leq\delta(f^{(a)}),\ f^{(a)}_{\
a^{\prime}}=f_{(a,a^{\prime})}.$

We will simplify the main result of this subsection by using the following
technical definition:

###### Definition 3.7

Let $n\geq 2$ and $\delta f\geq\hbox{\bf 1}.$ For $\hbox{\bf i}\ll\hbox{\bf
n}$, let $\delta=\delta_{\hbox{\bf\scriptsize i}}f$ and
$\delta^{\prime}=\delta_{\hbox{\bf\scriptsize i}^{\prime}}f.$ We will write
the sum of “cross–products of sections”

$X_{\hbox{\bf\scriptsize i}^{\prime}}\sum_{\hbox{\bf\scriptsize 0}\leq
a\leq\delta}\ \sum_{\hbox{\bf\scriptsize 0}^{\prime}\leq
a^{\prime}\leq\delta^{\prime}-\hbox{\bf\scriptsize
1}^{\prime}}\left(\nu^{a^{\prime}+\hbox{\bf\scriptsize
1}^{\prime}}f^{(a)}\right)(X_{\hbox{\bf\scriptsize
i}^{\prime}})\cdot\Gamma\left(X_{\hbox{\bf\scriptsize i}}^{a}\circ
s^{(-a^{\prime})}\right)(X_{\hbox{\bf\scriptsize i}}^{-\hbox{\bf\scriptsize
1}})$

as $\beta^{\times}_{\hbox{\bf\scriptsize i}}(f,s)(X_{\hbox{\bf\scriptsize
i}}^{-\hbox{\bf\scriptsize 1}},X_{\hbox{\bf\scriptsize i}^{\prime}})$ for
short.

Notice that $\beta^{\times}_{\hbox{\bf\scriptsize
i}}(f,s)(X_{\hbox{\bf\scriptsize i}}^{-\hbox{\bf\scriptsize
1}},X_{\hbox{\bf\scriptsize i}^{\prime}})\in L_{n}$. In fact it belongs to
$\left(R[X_{\hbox{\bf\scriptsize i}^{\prime}}]\right)[[X_{\hbox{\bf\scriptsize
i}}^{-\hbox{\bf\scriptsize 1}}]]$. We will also abbreviate
$\beta^{\times}_{\hbox{\bf\scriptsize i}}(f,s)(X_{\hbox{\bf\scriptsize
i}}^{-\hbox{\bf\scriptsize 1}},X_{\hbox{\bf\scriptsize i}^{\prime}})$ to
$\beta^{\times}_{\hbox{\bf\scriptsize i}}(f,s).$

For $n=2$ and continuing the notation of the definition, $\hbox{\bf
i}=\\{1\\}\mbox{ or }\ \\{2\\}$, and

$\beta^{\times}_{\\{1\\}}(f,s)(X_{1}^{-1},X_{2})=X_{2}\sum_{a=0}^{\delta}\sum_{a^{\prime}=0}^{\delta^{\prime}-1}\left(\nu^{a^{\prime}+1}f^{(a)}\right)(X_{2})\cdot\Gamma\left(X_{1}^{a}\circ
s^{(-a^{\prime})}\right)(X_{1}^{-1})$
$\beta^{\times}_{\\{2\\}}(f,s)(X_{2}^{-1},X_{1})=X_{1}\sum_{a=0}^{\delta}\sum_{a^{\prime}=0}^{\delta^{\prime}-1}\left(\nu^{a^{\prime}+1}f^{(a)}\right)(X_{1})\cdot\Gamma\left(X_{2}^{a}\circ
s^{(-a^{\prime})}\right)(X_{2}^{-1})$

where $\nu$ denotes the usual divided difference operator.

For $0<k<2^{n}-1$, we define $\hbox{\bf i}(k)=\\{i\in\hbox{\bf n}\ :\
b_{i}(k)=1\\}\ll\hbox{\bf n}$. Thus if $\delta f\geq\hbox{\bf 1},\ \hbox{\bf
i}(k)$ is the set of $i$ for which $\pi_{i}\beta_{k}(-\infty,\delta f]$ is
infinite.

###### Theorem 3.8

Let $n\geq 2,\ 0<k<2^{n}-1$, and let $\hbox{\bf i}=\hbox{\bf i}(k)$. Then for
$\delta f\geq\hbox{\bf 1}$, the $k^{th}$ border Laurent series of $f$ and $s$
is

$\beta_{k}(f,s)=\beta^{\times}_{\hbox{\bf\scriptsize
i}}(X_{\hbox{\bf\scriptsize
i}}^{\hbox{\bf\scriptsize-1}},X_{\hbox{\bf\scriptsize i}^{\prime}}).$

Proof.

$\displaystyle\beta_{k}(f,s)$ $\displaystyle=$
$\displaystyle\sum_{(a,a^{\prime})\in\beta_{k}(-\infty,\delta
f]\cap\mbox{\scriptsize
Supp}(f\Gamma)}\left(f\Gamma\right)_{(a,a^{\prime})}\hbox{\bf\it
X}^{(a,a^{\prime})}$ $\displaystyle=$
$\displaystyle\sum_{a\leq\hbox{\bf\scriptsize 0},\ \hbox{\bf\scriptsize
1}^{\prime}\leq a^{\prime}\leq\delta^{\prime}}\left(\sum_{(a,a^{\prime})\leq
b\leq(\delta,\delta^{\prime})}f_{b}\ s_{(a,a^{\prime})-b}\right)\hbox{\bf\it
X}^{(a,a^{\prime})}$ $\displaystyle=$
$\displaystyle\sum_{a\leq\hbox{\bf\scriptsize 0},\ \hbox{\bf\scriptsize
1}^{\prime}\leq
a^{\prime}\leq\delta^{\prime}}\left(\sum_{(\hbox{\bf\scriptsize
0},\hbox{\bf\scriptsize
0}^{\prime})\leq(c,c^{\prime})\leq(\delta,\delta^{\prime})-(a,a^{\prime})}f_{(a,a^{\prime})+(c,c^{\prime})}\
s_{-(c,c^{\prime})}\right)\hbox{\bf\it X}^{(a,a^{\prime})}$ $\displaystyle=$
$\displaystyle\sum_{a\leq\hbox{\bf\scriptsize 0},\ \hbox{\bf\scriptsize
0}^{\prime}\leq c^{\prime}\leq\delta^{\prime}-\hbox{\bf\scriptsize
1}^{\prime}}\left(\sum_{\hbox{\bf\scriptsize 0}\leq c\leq\delta-a,\
\hbox{\bf\scriptsize 1}^{\prime}\leq
a^{\prime}\leq\delta^{\prime}}f_{(a,a^{\prime})+(c,c^{\prime})}\
s_{-(c,c^{\prime})}\right)X_{\hbox{\bf\scriptsize
i}}^{a}X_{\hbox{\bf\scriptsize i}^{\prime}}^{a^{\prime}}$ $\displaystyle=$
$\displaystyle\sum_{d\leq\hbox{\bf\scriptsize 0},\ \hbox{\bf\scriptsize
0}^{\prime}\leq c^{\prime}\leq\delta^{\prime}-\hbox{\bf\scriptsize
1}^{\prime}}\left(\sum_{\hbox{\bf\scriptsize 0}\leq c\leq\delta-d,\
c^{\prime}+\hbox{\bf\scriptsize 1}^{\prime}\leq
d^{\prime}\leq\delta^{\prime}}f_{(c+d,d^{\prime})}\
s_{-(c,c^{\prime})}\right)X_{\hbox{\bf\scriptsize
i}}^{d}X_{\hbox{\bf\scriptsize i}^{\prime}}^{d^{\prime}-c^{\prime}}$
$\displaystyle=$ $\displaystyle X_{\hbox{\bf\scriptsize
i}^{\prime}}\sum_{d\leq\hbox{\bf\scriptsize 0},\ \hbox{\bf\scriptsize
0}^{\prime}\leq e^{\prime}\leq\delta^{\prime}-\hbox{\bf\scriptsize
1}^{\prime}}\left(\sum_{d\leq e\leq\delta,\ e^{\prime}+\hbox{\bf\scriptsize
1}^{\prime}\leq
d^{\prime}\leq\delta^{\prime}}f_{(e,d^{\prime})}X_{\hbox{\bf\scriptsize
i}^{\prime}}^{d^{\prime}}\ s_{(d-e,e^{\prime})}\right)X_{\hbox{\bf\scriptsize
i}}^{d}$ $\displaystyle=$ $\displaystyle X_{\hbox{\bf\scriptsize
i}^{\prime}}\sum_{\hbox{\bf\scriptsize 0}\leq e\leq\delta,\
\hbox{\bf\scriptsize 0}^{\prime}\leq
e^{\prime}\leq\delta^{\prime}-\hbox{\bf\scriptsize
1}^{\prime}}\left(\sum_{d\leq\hbox{{\bf\scriptsize 0}},\
e^{\prime}+\hbox{\bf\scriptsize 1}^{\prime}\leq
d^{\prime}\leq\delta^{\prime}}f_{(e,d^{\prime})}X_{\hbox{\bf\scriptsize
i}^{\prime}}^{d^{\prime}-(e^{\prime}+\hbox{\bf\scriptsize 1}^{\prime})}\
s_{(d-e,e^{\prime})}X_{\hbox{\bf\scriptsize i}}^{d}\right)$ $\displaystyle=$
$\displaystyle X_{\hbox{\bf\scriptsize i}^{\prime}}\sum_{\hbox{\bf\scriptsize
0}\leq e\leq\delta,\ \hbox{\bf\scriptsize 0}^{\prime}\leq
e^{\prime}\leq\delta^{\prime}-\hbox{\bf\scriptsize
1}^{\prime}}\left(\sum_{e^{\prime}+\hbox{\bf\scriptsize 1}^{\prime}\leq
d^{\prime}\leq\delta^{\prime}}f^{(e)}_{d^{\prime}}X_{\hbox{\bf\scriptsize
i}^{\prime}}^{d^{\prime}-(e^{\prime}+\hbox{\bf\scriptsize
1}^{\prime})}\right)\cdot\left(\sum_{d\leq\hbox{\bf\scriptsize
0}}\left(X_{\hbox{\bf\scriptsize i}}^{e}\circ
s^{(-e^{\prime})}\right)_{d}X_{\hbox{\bf\scriptsize i}}^{d}\right)$
$\displaystyle=$ $\displaystyle X_{\hbox{\bf\scriptsize
i}^{\prime}}\sum_{{\hbox{\bf\scriptsize 0}}\leq e\leq\delta,\
\hbox{\bf\scriptsize 0}^{\prime}\leq
e^{\prime}\leq\delta^{\prime}-\hbox{\bf\scriptsize
1}^{\prime}}\left(\nu^{e^{\prime}+\hbox{\bf\scriptsize
1}^{\prime}}f^{(e)}\right)(X_{\hbox{\bf\scriptsize
i}^{\prime}})\cdot\Gamma\left(X_{\hbox{\bf\scriptsize i}}^{e}\circ
s^{(-e^{\prime})}\right)(X_{\hbox{\bf\scriptsize
i}}^{\hbox{\bf\scriptsize-1}})$ $\displaystyle=$
$\displaystyle\beta^{\times}_{\hbox{\bf\scriptsize i}}(X_{\hbox{\bf\scriptsize
i}}^{\hbox{\bf\scriptsize-1}},X_{\hbox{\bf\scriptsize i}^{\prime}}).$

$\bullet$

Let $\delta f\geq\hbox{\bf 1}.$ To simplify the notation, we let

$\beta^{\times}_{\hbox{\bf\scriptsize i}(0)}(f,s)=\hbox{\bf\it
X}\sum_{\hbox{\bf\scriptsize 0}\leq a\leq\delta f-\hbox{\bf\scriptsize 1}}\
s_{-a}\ \nu^{a+\hbox{\bf\scriptsize 1}}f,$

which is just $\beta_{0}(f,s)$ by Lemma 3.4.

###### Corollary 3.9

Let $\delta f\geq\hbox{\bf 1}.$

(a)

$f\cdot\Gamma(s)=\sum_{k=0}^{2^{n}-2}\beta^{\times}_{\hbox{\bf\scriptsize
i}(k)}(f,s)+\Gamma(f\circ s)$

where Supp$(\beta^{\times}_{\hbox{\bf\scriptsize
i}(k)}(f,s))\subseteq\beta_{k}(-\infty,\delta f]$ for $0\leq k\leq 2^{n}-2.$

(b) $f\in Ann(s)$ if, and only if

$\Gamma(s)=\left(\sum_{k=0}^{2^{n}-2}\beta^{\times}_{\hbox{\bf\scriptsize
i}(k)}(f,s)\right)/f.$

(c) If $f$ is monic, $G\in L_{n}$ and $\mbox{Supp}(G)\subseteq(-\hbox{\bf
1},\delta f-\hbox{\bf 1}]$, then $\hbox{\bf\it X}G/f\in S_{n}$ and $s$ defined
by $\Gamma(s)=\hbox{\bf\it X}G/f$ is an lrs with $f\in\mbox{Ann}(s)$, and
$\hbox{\bf\it X}G=\sum_{k=0}^{2^{n}-2}\beta^{\times}_{\hbox{\bf\scriptsize
i}(k)}(f,s).$

Proof.  These are immediate consequences of Proposition 2.6, Corollary 2.9,
Lemma 3.4 and Theorem 3.8. $\bullet$

We now state an analogue of the previous corollary for sequences
${{N}}^{n}\rightarrow R$ and left–shifting. In this case,
$\prod_{i=1}^{n}\\{[-\delta_{i}f,-1],[0,\infty)\\}$ is to be used as the
“border partition” $\\{\beta_{k}[-\delta f,\infty):0\leq k\leq 2^{n}-1\\}$ of
$[-\delta f,\infty).$

###### Corollary 3.10

Let $\delta f\geq\hbox{\bf 1}$. If $s:{{N}}^{n}\rightarrow R$ (so that
$\Gamma(s)\in R[[\hbox{\bf\it X}]]$), then

(a)

$f^{\ast}\Gamma(s)=\sum_{k=0}^{2^{n}-2}\beta^{\star}_{\hbox{\bf\scriptsize
i}(k)}(f,s)+\hbox{\bf\it X}^{\delta f}\Gamma(f\circ s)$

where

$\beta^{\star}_{\hbox{\bf\scriptsize i}(0)}(f,s)=\hbox{\bf\it X}^{\delta f}\
\beta^{\times}_{\hbox{\bf\scriptsize i}(0)}(f,s)(\hbox{\bf\it
X}^{-\hbox{\bf\scriptsize 1}})\mbox{ and }\beta^{\star}_{\hbox{\bf\scriptsize
i}(k)}(f,s)=\hbox{\bf\it X}^{\delta f}\beta^{\times}_{\hbox{\bf\scriptsize
i}(k)}(f,s)(X_{\hbox{\bf\scriptsize i}},X_{\hbox{\bf\scriptsize
i}^{\prime}}^{-\hbox{\bf\scriptsize 1}})$

for $0\leq k\leq 2^{n}-2$ and Supp$(\beta^{\star}_{\hbox{\bf\scriptsize
i}(k)})\subseteq\\{a+\delta f\ :\ a\in\beta_{k}[-\delta f,\infty)\\}$ for
$0\leq k\leq 2^{n}-2.$

(b) If $f\in\mbox{Ann}(s)$, then

$\Gamma(s)=\left(\sum_{k=0}^{2^{n}-2}\beta_{\hbox{\bf\scriptsize
i}(k)}^{\star}(f,s)\right)/f^{\ast}$

where $\beta_{\hbox{\bf\scriptsize i}(0)}^{\star}(f,s)\in P_{n}.$ In fact,
$\delta\beta_{\hbox{\bf\scriptsize i}(0)}^{\star}(f,s)\leq\delta f-\hbox{\bf
1}$ and $\beta_{\hbox{\bf\scriptsize i}(0)}^{\star}(f,s)=\hbox{\bf\it
X}^{\delta f-\delta\beta_{0}(f,s)}\beta_{0}(f,s)^{\ast}.$

(c) If $f$ is monic and $G\in R[[\hbox{\bf\it X}]]$ satisfies
$\mbox{Supp}(G)\subseteq[\hbox{\bf 0},\delta f)$, then $s$ defined by
$G/f^{\ast}$ is an lrs with $f\in\mbox{Ann}(s)$ and

$G=\sum_{k=0}^{2^{n}-2}\beta^{\star}_{\hbox{\bf\scriptsize i}(k)}(f,s).$

Proof.  These are straightforward consequences of the previous result.
$\bullet$

##  4 EVR sequences

###  4.1 1–D sequences

It is convenient to begin with some results on 1–D sequences.

###### Proposition 4.1

Let $s\in S^{1}(R)^{-}$ and $\delta f\geq 1$.

(a) $f\Gamma(s)=\beta_{0}(f,s)+\Gamma(f\circ s)$

(b) $f\in\mbox{Ann}(s)\Longleftrightarrow f\Gamma(s)=\beta_{0}(f,s)$

(c) If $f\in\mbox{Ann}(s)$, then $\mbox{Ann}(s)=(f:\beta_{0}(f,s)/X).$

Proof.  (a): This is immediate from Proposition 3.2.

(b): $f\in\mbox{Ann}(s)\Longleftrightarrow f\circ
s=0\Longleftrightarrow\Gamma(f\circ s)=0\Longleftrightarrow
f\Gamma(s)=\beta_{0}(f,s).$

(c): If $g\in\mbox{Ann}(s)$, then
$g\beta_{0}(f,s)=gf\Gamma(s)=\beta_{0}(g,s)f$, so that
$g\in(f:\beta_{0}(f,s)/X)$. Conversely, if $g\beta_{0}(f,s)/X=hf$ for some
$h\in R[X]$, then $g\Gamma(s)=g\beta_{0}(f,s)/f=Xh$ and so by Corollary 2.8,
$g\in\mbox{Ann}(s).$ $\bullet$

The next result is a considerable generalization of Theorem 1 of Prabhu & Bose
(1982) and Theorem 4.11 of Fitzpatrick & Norton (1995), both of which use
left–shifting.

###### Lemma 4.2

Let $R$ be a factorial domain, $s\in S^{1}(R)^{-},\ f\in\mbox{Ann}(s)$ with
$\delta f\geq 1$. Put $d=\gcd(f,\beta_{0}(f,s)/X)$ and $g=f/d$. Then

(a) $g\in\mbox{Ann}(s)$

(b) $\beta_{0}(g,s)=\beta_{0}(f,s)/d$

(c) $\gcd(g,\beta_{0}(g,s)/X)=1$

(d) if $d=1$ and $h\in\mbox{Ann}(s)$ , then $\beta_{0}(f,s)|\beta_{0}(h,s)$
and $h=(\beta_{0}(h,s)/\beta_{0}(f,s))\cdot f$.

Proof.  (a) Since $f\in\mbox{Ann}(s),f\Gamma(s)=\beta_{0}(f,s)$ and so
$g\Gamma(s)=X\ (\beta_{0}(f,s)/X)/d\in XR[X]$. By Corollary 2.8,
$g\in\mbox{Ann}(s)$.

(b) $\beta_{0}(f,s)/d=f\Gamma(s)/d=g\Gamma(s)=\beta_{0}(g,s)$ by part (a)
since $g\in\mbox{Ann}(s)$.

(c) By part (b), $\gcd(g,\beta_{0}(g,s)/X)=\gcd(g,(\beta_{0}(f,s)/X)/d)=1$.

(d) From Proposition 4.1, $h\beta_{0}(f,s)/X=f\beta_{0}(h,s)/X$ and since
$d=1,\ \beta_{0}(f,s)/X$ divides $\beta_{0}(h,s)/X.$ $\bullet$

###### Remark 4.3

On the other hand, if $g\in\mbox{Ann}(s)\setminus\\{0\\}$ has minimal degree,
then $\gcd(g,\beta_{0}(g,s)/X)\in R$ — otherwise we can replace $g$ by a
characteristic polynomial of smaller degree by part (a) of the previous
result. If $g$ is also primitive, then since $d=\gcd(g,\beta_{0}(g,s)/X)\in
R,\ d|g_{0}$, and inductively, $d$ divides all the coefficients of $g$. Thus
$d=1$.

###### Theorem 4.4

Let $R$ be a factorial domain and Ann($s)\neq(0).$ Then

(a) $\mbox{Ann}(s)$ is generated by a primitive polynomial $g$, say.

(b) $g$ is unique up to a unit of $R$, and $\gcd(g,\beta_{0}(g,s)/X)=1.$

(c) $\delta g=\min\\{\delta f:f\in\mbox{Ann}(s)\setminus\\{0\\}\\}$.

Proof.  We need only prove (a). For any $f\in\mbox{Ann}(s)$ with $\delta f\geq
1,\ g=f/\gcd(f,\beta_{0}(f,s)/X)$ generates $\mbox{Ann}(s)$ by Lemma 4.2, and
we may take $g$ to be primitive. $\bullet$

###### Definition 4.5

If $R$ is a factorial domain and Ann$(s)\neq(0)$, we denote the primitive
generator of Ann($s$) (which is unique up to a unit of $R$) by $\gamma(s).$

We remark that $\gamma(s)$ may be computed using the minimal realization
algorithm of Norton (1995a); see loc. cit. Corollary 3.28. For an alternative
approach to $\gamma(s)$ using polynomial remainder sequences, see Fitzpatrick
& Norton (1995), Section 4.5.

###  4.2 Associated sequences

###### Definition 4.6

For $n\geq 2$ and $\hbox{\bf i}\ll\hbox{\bf n}$, let $s^{(\hbox{\bf\scriptsize
i},\ast)}\in S^{\mid\hbox{\bf\scriptsize i}\mid}(R[[X_{\hbox{\bf\scriptsize
i}^{\prime}}]])$ be given by

$s^{(\hbox{\bf\scriptsize i},\ast)}_{\
a}=\sum_{a^{\prime}\in-{{N}}^{\hbox{\bf\scriptsize
i}^{\prime}}}s_{(a,a^{\prime})}X^{\ a^{\prime}}_{\hbox{\bf\scriptsize
i}^{\prime}}$

for $a\in-{{N}}^{\hbox{\bf\scriptsize i}}$.

Thus for $\hbox{\bf i}\ll\hbox{\bf n}$, the superscript
${}^{(\hbox{\bf\scriptsize i},\ast)}$ is used to suggest summation over
$\hbox{\bf i}^{\prime}$ (whereas for $a\in-{{N}}^{\hbox{\bf\scriptsize i}}$,
the superscript (a) is used to denote a section). Special cases of these
associated sequences were used in Fitzpatrick & Norton (1990).

For $\hbox{\bf i}\ll\hbox{\bf n}$, we let $R[X_{\hbox{\bf\scriptsize i}}]$ act
on $n$–D sequences via:

$\left(\sum_{a\in{\scriptsize Supp(f)}}f_{a}X_{\hbox{\bf\scriptsize
i}}^{a}\circ s\right)_{b}=\sum_{a\in{\scriptsize Supp(f)}}f_{a}\
s_{b-(a,\hbox{\bf\scriptsize 0}^{\prime})}$

where $b\leq\hbox{\bf 0}$ and $\hbox{\bf
0}^{\prime}\in{{N}}^{\hbox{\bf\scriptsize i}^{\prime}}$.

###### Lemma 4.7

Let $n\geq 2,\hbox{\bf i}\ll\hbox{\bf n},f\in R[X_{\hbox{\bf\scriptsize
i}}],f^{\prime}\in R[X_{\hbox{\bf\scriptsize i}^{\prime}}]$ and
$a\in-{{N}}^{\hbox{\bf\scriptsize
i}},a^{\prime}\in-{{N}}^{\hbox{\bf\scriptsize i}^{\prime}}$. Then

(a) $(f^{\prime}\circ s^{(a)})_{a^{\prime}}=(f^{\prime}\circ
s)_{(a,a^{\prime})}$

(b) $s^{(\hbox{\bf\scriptsize
i},\ast)}_{a}=\Gamma(s^{(a)})(X_{\hbox{\bf\scriptsize
i}^{\prime}}^{-\hbox{\bf\scriptsize 1}})$

(c) $\Gamma(f\circ s^{(\hbox{\bf\scriptsize i},\ast)})(X_{\hbox{\bf\scriptsize
i}}^{-\hbox{\bf\scriptsize 1}})=\Gamma(f\circ s)(\hbox{\bf\it
X}^{-\hbox{\bf\scriptsize 1}})$.

Proof.  (a)

$\displaystyle(f^{\prime}\circ s^{(a)})_{a^{\prime}}$ $\displaystyle=$
$\displaystyle\sum_{d^{\prime}\in\mbox{{\scriptsize
Supp}}(f^{\prime})}f^{\prime}_{d^{\prime}}s^{(a)}_{a^{\prime}-d^{\prime}}=\sum_{d^{\prime}\in\mbox{\scriptsize
Supp}(f^{\prime})}f^{\prime}_{d^{\prime}}s_{(a^{\prime}-d^{\prime},a)}$
$\displaystyle=$ $\displaystyle\sum_{d^{\prime}\in\mbox{{\scriptsize
Supp}}(f^{\prime})}f^{\prime}_{d^{\prime}}s_{(a^{\prime},a)-(d^{\prime},\hbox{\bf\scriptsize
0})}=(f^{\prime}\circ s)_{(a^{\prime},a)}.$

(b), (c) These are also easy consequences of the definitions. $\bullet$

The characteristic ideals of associated sequences are related as follows:

###### Proposition 4.8

Let $n\geq 2$ and $\hbox{\bf i}\ll\hbox{\bf n}$. Then

$\bigcap_{a^{\prime}\in-{{N}}^{\hbox{\bf\scriptsize
i}^{\prime}}}\mbox{Ann}(s^{(a^{\prime})})=\mbox{Ann}(s)\cap
R[X_{\hbox{\bf\scriptsize i}}]=\mbox{Ann}(s^{(\hbox{\bf\scriptsize
i},\ast)}).$

Proof.  Let $f\in R[X_{\hbox{\bf\scriptsize i}}]$. By Lemma 4.7(a),

$\forall(a^{\prime}\in-{{N}}^{\hbox{\bf\scriptsize i}^{\prime}})(f\circ
s^{(a^{\prime})}=0)\Longleftrightarrow\forall(b\in-{{N}}^{n})((f\circ
s)_{b}=0)\Longleftrightarrow f\in\mbox{Ann}(s).$

To prove the second equality, note that $f\circ s=0\Longleftrightarrow f\circ
s^{(\hbox{\bf\scriptsize i},\ast)}=0$ by Lemma 4.7(c). $\bullet$

###  4.3 Some properties of EVR sequences

It follows from the previous subsection that for $n\geq 2$ and $i\in\hbox{\bf
n}$, there are $n$ associated sequences $s^{(i,\ast)}=s^{(\\{i\\},\ast)}\in
S^{1}(R[[\mathaccent 866{\bf X}_{i}^{-\hbox{\bf\scriptsize 1}}]])^{-}$ given
by

$s^{(i,\ast)}_{\ j}=\sum_{j^{\prime}\in-{{N}}^{\hbox{\bf\scriptsize
n}\setminus\\{i\\}}}s_{(j,j^{\prime})}\mathaccent 866{\bf X}_{i}^{\
j^{\prime}}$

for $j\leq 0,\ \mbox{Ann}(s^{(i,\ast)})=\mbox{Ann}(s)\cap R[X_{i}]$ and
$\Gamma(f_{i}\circ s^{(i,\ast)})(X_{i}^{-1})=\Gamma(f_{i}\circ s)(\hbox{\bf\it
X}^{-\hbox{\bf\scriptsize 1}}).$

The next result is a considerable generalization of Prabhu & Bose (1982),
Theorem 1 and Fitzpatrick & Norton (1990), Corollary 4.2:

###### Theorem 4.9

Let $f_{i}\in R[X_{i}]$ with $\delta f_{i}\geq 1$ for all $i\in\hbox{\bf n}$
and let $f=\prod_{i=1}^{n}f_{i}$. The following are equivalent:

(a) for all $i\in\hbox{\bf n},\ f_{i}\in\mbox{Ann}(s)$

(b) $f\Gamma(s)\in\hbox{\bf\it X}P_{n}$

(c) $f\Gamma(s)=\beta_{0}(f,s)$.

Proof.  (a) $\Longrightarrow$ (b): For all $i\in\hbox{\bf n}$ and $a_{i}\leq
0$, the coefficient of $X_{i}^{a_{i}}$ in $f\Gamma(s)$ is

$(f\Gamma(s))_{(a_{i},\hbox{\bf\scriptsize 0}^{\prime})}=(f\circ
s)_{(a_{i},\hbox{\bf\scriptsize 0}^{\prime})}$

which is zero since $f$ is a multiple of $f_{i}\in\mbox{Ann}(s).$ Hence
Supp$(f\Gamma(s))\subseteq[\hbox{\bf 1},\delta f].$

(b) $\Longrightarrow$ (a): Fix $i\in\hbox{\bf n}$. Put $t=s^{(i,\ast)}$ and
let $f\Gamma(s)=\hbox{\bf\it X}g$, where $g\in P_{n}.$ By Lemma 4.7,
$\Gamma(t)(X_{i}^{-1})=\Gamma(s)(\hbox{\bf\it X}^{-\hbox{\bf\scriptsize 1}}).$
Thus

$\delta_{i}(f_{i}\Gamma(t))=\delta_{i}(f\Gamma(t))=\delta_{i}(f\Gamma(s))=\delta_{i}\hbox{\bf\it
X}g\geq 1,$

whereas for $j\neq i,$

$\delta_{j}(f_{i}\Gamma(t))\leq\delta_{j}f_{i}+\delta_{j}\Gamma(t)\leq\delta_{j}\Gamma(t)\leq
0$

i.e. $f_{i}\Gamma(t)\in X_{i}(R[[\mathaccent 866{\bf
X}_{i}^{-\hbox{\bf\scriptsize 1}}]])[X_{i}].$ Thus by Corollary 2.8,
$f_{i}\in\mbox{Ann}(t)$ and by Lemma 4.7 again, $\Gamma(f_{i}\circ
s)=\Gamma(f_{i}\circ t)=0$ i.e. $f_{i}\in\mbox{Ann}(s)$.

(b) $\Longrightarrow$ (c): Let $f\Gamma(s)=\hbox{\bf\it X}g\in P_{n}$ where
$\delta g\leq\delta f-\hbox{\bf 1}$. Since (b) $\Longleftrightarrow$ (a),
$\Gamma(f\circ s)=0$ and so

$\hbox{\bf\it
X}g-\beta_{0}(f,s)=f\Gamma(s)-\beta_{0}(f,s)=\sum_{k=1}^{2^{n}-2}\beta_{k}(f,s).$

The support of the left–hand side is contained in $[\hbox{\bf 1},\delta f]$,
whereas the support of the right–hand side is contained in $(-\infty,\delta
f]\setminus[\hbox{\bf 1},\delta f]$ by construction. Therefore both sides
vanish and $f\Gamma(s)=\beta_{0}(f,s).$ $\bullet$

We now discuss $\mbox{Ann}(s)\cap R[X_{i}]$, which is an ideal of $R[X_{i}]$.
So when $R$ is a field, $\mbox{Ann}(s)\cap R[X_{i}]$ is principal and has a
monic generator. We will see that this is also true more generally.

For $n=1$, the following notion was introduced in Fitzpatrick & Norton (1995):

###### Definition 4.10

A factorial domain $R$ will be called potential if for all $n\geq 1,\ S_{n}$
is factorial.

In fact, for the known examples $R$ for which $R[[X]]$ is factorial, $S_{n}$
is also factorial. Principal ideal domains, $R[\hbox{\bf\it X}]$ (where $R$ is
a field or a discrete valuation ring) are potential domains, but not every
factorial domain is potential: see Bourbaki (1972), Exercise 8(c), p.566. We
refer the reader to Bourbaki (1972), Proposition 8, p.511 and Exercise 9(c),
p.566 and to Fossum (1973) for more details.

###### Lemma 4.11

Let $R$ be factorial and $s\in S^{1}(R)^{-}$. If $R[[X]]$ is factorial, we can
assume that $\gamma(s)$ is monic.

Proof.  Ann$(s)\cong Ann(s^{-})$, and so the result follows from Fitzpatrick &
Norton (1995), Corollary 4.8. $\bullet$

###### Theorem 4.12

If $R$ potential and $s$ is EVR, then for all $i\in\hbox{\bf
n},\mbox{Ann}(s)\cap R[X_{i}]$ is principal and has a unique monic generator.

Proof.  We can assume that $n\geq 2$. Fix $i$ and let $U=R[[\mathaccent
866{\bf X}_{i}^{-\hbox{\bf\scriptsize 1}}]]$ and $t=s^{(i,\ast)}\in
S^{1}(U)^{-}$. By Proposition 4.8, $\mbox{Ann}(s)\cap R[X_{i}]=\mbox{Ann}(t)$.
Also, $U$ and $U[[X_{i}^{-1}]]=S_{n}$ are factorial since $R$ is potential.
Thus the result follows from Lemma 4.11. $\bullet$

The next result simplifies and extends Fitzpatrick & Norton (1990), Theorem
4.3:

###### Theorem 4.13

Let $R$ be a potential domain and for all $i\in\hbox{\bf n}$, let
$f_{i}\in\mbox{Ann}(s)\cap R[X_{i}]$ with $\delta f_{i}\geq 1$. Put
$f=\prod_{i=1}^{n}f_{i}$ and $d_{i}=\gcd(f_{i},\beta_{0}(f,s)/X_{i})$. Then
for all $i\in\hbox{\bf n}$, there is a unit $u_{i}$ of $R$ such that
$u_{i}f_{i}/d_{i}$ is the monic generator of Ann$(s)\cap R[X_{i}].$

Proof.  For $i\in\hbox{\bf n}$, let $\gamma_{i}$ be the monic generator of
$\mbox{Ann}(s)\cap R[X_{i}]\mbox{ and }\gamma=\prod_{i=1}^{n}\gamma_{i}.$ By
Theorem 4.9,

$\gamma\beta_{0}(f,s)=\gamma f\Gamma(s)=f\beta_{0}(\gamma,s).$

Now $\gcd(\gamma,\beta_{0}(\gamma,s)/\hbox{\bf\it X})\in R$, otherwise we
could replace some $\gamma_{j}$ by a polynomial of smaller degree. Since
$P_{n}$ is factorial, $\gamma$ is primitive by Gauss’ Lemma and so
$\gcd(\gamma,\beta_{0}(\gamma,s)/\hbox{\bf\it X})=1$. Hence there is a unit
$u$ of $R$ with $\gamma=uf/\gcd(f,\beta_{0}(f,s)/\hbox{\bf\it X})$. Also,

$\gcd(f,\beta_{0}(f,s)/\hbox{\bf\it X})=\gcd(\prod
f_{i},\beta_{0}(f,s)/\hbox{\bf\it
X})=\prod\gcd(f_{i},\beta_{0}(f,s)/X_{i})=\prod d_{i}$

since $f_{i}\in R[X_{i}]$. Thus $\prod\gamma_{i}=u\prod(f_{i}/d_{i})$ and
since $P_{n}$ is factorial, $\gamma_{i}=u_{i}f_{i}/d_{i}$ for some unit
$u_{i}$ of $R$. $\bullet$

We now combine Theorems 4.9 and 4.13 to characterize generating functions of
EVR lrs:

###### Corollary 4.14

Let $f_{i}\in R[X_{i}]$ with $\delta f_{i}\geq 1$ for $i\in\hbox{\bf n}$, and
put $f=\prod_{i=1}^{n}f_{i}$.

(a) If $R$ is potential and $f_{i}\in\mbox{Ann}(s)$ for all $i\in\hbox{\bf
n}$, then $\Gamma(s)=\beta_{0}(f,s)/f$ and we can assume that for all
$i\in\hbox{\bf n},f_{i}$ is monic, $\gcd(f_{i},\beta_{0}(f,s)/X_{i})=1$ and
$\mbox{Ann}(s)\cap R[X_{i}]=(f_{i})$.

(b) If for all $i\in\hbox{\bf n},f_{i}$ is monic, $g\in R[\hbox{\bf\it
X}],\delta g\leq\delta f-\hbox{\bf 1}$ and $\gcd(f_{i},g)=1$, then $s$ defined
by $\Gamma(s)=\hbox{\bf\it X}g/f$ is an (EVR) lrs with $\hbox{\bf\it
X}g=\beta_{0}(f,s)$ and $\mbox{Ann}(s)\cap R[X_{i}]=(f_{i})$.

Proof.  For each $i\in\hbox{\bf n},f_{i}$ can be chosen as the monic generator
of $\mbox{Ann}(s)\cap R[X_{i}]=\mbox{Ann}(s^{(i,\ast)})$ by Theorem 4.12.
Since

$f_{i}\Gamma(s^{(i,\ast)})=f_{i}\Gamma(s)=\beta_{0}(f,s)/\prod_{j\neq i}f_{j}$

we must have $d_{i}=\gcd(f_{i},\beta_{0}(f,s)/X_{i})\in R$ — for otherwise by
Lemma 4.2, we can replace $f_{i}$ by a characteristic polynomial of smaller
degree. Since $d_{i}$ divides each coefficient of $f_{i}$, which is monic,
$d_{i}=1$.

For the converse, we have $\hbox{\bf\it X}g=\beta_{0}(f,s)$ from Theorem 4.9.
Thus $\gcd(f_{i},\beta_{0}(f,s)/X_{i})=1$ and by Theorem 4.13,
$\mbox{Ann}(s)\cap R[X_{i}]=(f_{i}).$ $\bullet$

For completeness, we give an alternative way of finding the generator of
$\mbox{Ann}(s)\cap R[X_{i}]$ (Corollary 4.16 below), generalizing Fitzpatrick
& Norton (1990), Theorem 4.10.

###### Lemma 4.15

Let $n\geq 2$, $R$ be a domain, let $f_{i}\in\mbox{Ann}(s)\cap R[X_{i}]$ with
$\delta f_{i}\geq 1$ for all $i\in\hbox{\bf n}$, and put
$\Delta^{\prime}_{i}=\delta(\prod_{j=1,j\neq i}^{n}f_{j})-\hbox{\bf
1}^{\prime}\in{{N}}^{\hbox{\bf\scriptsize n}\setminus\\{i\\}}$. Then

$\bigcap_{a^{\prime}\in{-{N}}^{\hbox{\bf\scriptsize
n}\setminus\\{i\\}}}\mbox{Ann}(s^{(a^{\prime})})=\bigcap_{-\Delta^{\prime}_{i}\leq
a^{\prime}\leq\hbox{\bf\scriptsize 0}^{\prime}}\mbox{Ann}(s^{(a^{\prime})}).$

Proof.  By definition, $s^{(a^{\prime})}\in S^{1}(R)^{-}$ if
$a^{\prime}\in-{{N}}^{\hbox{\bf\scriptsize n}\setminus\\{i\\}}$. We show that
if $g\in R[X_{i}]$ satisfies $g\circ s^{(a^{\prime})}=0$ for
$-\Delta^{\prime}_{i}\leq a^{\prime}\leq\bf 0^{\prime}$, then $g\circ
s^{(a^{\prime})}=0$ for all $a^{\prime}$. Let $i=1$ and let $\lambda_{2}$ be
the leading coefficient of $f_{2}$. Suppose first that
$a^{\prime}=(-\delta_{2}f_{2},-\delta_{3}f_{3}+1,\ldots,-\delta_{n}f_{n}+1)$.
Since $f_{2}\in\mbox{Ann}(s)$, we can write

$\lambda_{2}s_{(a,a^{\prime})}=-\sum_{b^{\prime}=0}^{\delta_{2}f_{2}-1}(f_{2})_{b^{\prime}}s_{(a,-b^{\prime},c^{\prime})}$

for all $a\leq 0$, where
$c^{\prime}=(-\delta_{3}f_{3}+1,\ldots,-\delta_{n}f_{n}+1)$. Then for $a\leq
0,$

$(\lambda_{2}g\circ s^{(a^{\prime})})_{a}=\sum_{c=0}^{\delta
g}g_{c}\lambda_{2}s_{(a-c,a^{\prime})}=-\sum_{b^{\prime}=0}^{\delta_{2}f_{2}-1}(f_{2})_{b^{\prime}}\sum_{c=0}^{\delta
g}g_{c}s_{(a-c,-b^{\prime},c^{\prime})}$

and $\sum_{c=0}^{\delta g}g_{c}s_{(a-c,-b^{\prime},c^{\prime})}=(g\circ
s^{(-b^{\prime},c^{\prime})})_{a}=0$ since
$\Delta^{\prime}_{1}\leq(-b^{\prime},c^{\prime})\leq\hbox{\bf 0}^{\prime}$.
Thus for
$a^{\prime}=(-\delta_{2}f_{2},-\delta_{3}f_{3}+1,\ldots,-\delta_{n}f_{n}+1),\
\lambda_{2}g\circ s^{(a^{\prime})}=0$. The argument is similar for
$a^{\prime}=(a_{2},-\delta_{3}f_{3}+1,\ldots,-\delta_{n}f_{n}+1),\
a_{2}<-\delta_{2}f_{2}$; in this case,
$\lambda_{2}^{-a_{2}-\delta_{2}f_{2}}g\circ s^{(a^{\prime})}=0$. Since
$\lambda_{2}\in R$ and $R$ is a domain, $g\circ s^{(a^{\prime})}=0$ for all
$a_{2}\leq 0$.

Suppose inductively that the result is true for
$a^{\prime}=(a_{2},a_{3},\ldots,a_{k-1},-\delta_{k}f_{k}+1,\ldots,-\delta_{n}f_{n}+1)$
and
$a^{\prime}=(a_{2},a_{3},\ldots,a_{k},-\delta_{k+1}f_{k+1}+1,\ldots,-\delta_{n}f_{n}+1),a_{k}\leq-\delta
f_{k}$. An analogous argument using $f_{k}\in\mbox{Ann}(s)\cap R[X_{k}]$ shows
that $g\circ s^{(a^{\prime})}=0$. By induction $g\circ s^{(a^{\prime})}=0$ for
all $a^{\prime}\in-{{N}}^{\hbox{\bf\scriptsize n}\setminus\\{1\\}}$. It is
clear that the same argument applies to any $i\in\hbox{\bf n}$ and this
completes the proof. $\bullet$

###### Theorem 4.16

Let $n\geq 2$ and $R$ be potential. Suppose that for all $i\in\hbox{\bf
n},f_{i}\in\mbox{Ann}(s)\cap R[X_{i}],\ \delta f_{i}\geq 1$ and let
$\Delta^{\prime}_{i}=\delta(\prod_{j=1,j\neq i}^{n}f_{j})-\hbox{\bf
1}^{\prime}\in{{N}}^{\hbox{\bf\scriptsize n}\setminus\\{i\\}}$. Then for all
$i\in\hbox{\bf n}$,

$\mbox{Ann}(s)\cap
R[X_{i}]=\left(\mathrm{lcm}\\{\gamma(s^{(a^{\prime})}):-\Delta^{\prime}_{i}\leq
a^{\prime}\leq\hbox{\bf 0}^{\prime}\\}\right)$

Proof.  Fix $i\in\hbox{\bf n}$. For $a^{\prime}\in-{{N}}^{\hbox{\bf\scriptsize
n}\setminus\\{i\\}},\gamma(s^{(a^{\prime})})\in R[X_{i}]$ is well–defined (and
indeed monic) by Lemma 4.11. By Proposition 4.8 and Lemma 4.15

$\mbox{Ann}(s)\cap R[X_{i}]=\bigcap_{-\Delta^{\prime}_{i}\leq
a^{\prime}\leq\bf 0^{\prime}}\mbox{Ann}(s^{(a^{\prime})}).$

Since $R[X_{i}]$ is factorial, the intersection is non–empty and is generated
by $\mbox{lcm}\\{\gamma(s^{(a^{\prime})}):-\Delta^{\prime}_{i}\leq
a^{\prime}\leq\hbox{\bf 0}^{\prime}\\}$. $\bullet$

The least common multiple of Theorem 4.16 may be computed using Algorithm 3.30
of Norton (1995a). If $R$ is a field, it may also be computed using the
“Fundamental Iterative Algorithm” of Feng & Tzeng (1989).

We conclude this subsection by generalizing a result of Cerlienco & Piras
(1991) to sequences over domains.

###### Definition 4.17

We say that an ideal $I$ of $P_{n}$ is cofinite if $P_{n}/I$ is a finitely
generated $R$–module and that an $n$–D lrs over $R$ is cofinite if its
characteristic ideal contains a cofinite ideal.

It is well known that if $R$ is a field, then a cofinite ideal in
$R[X_{1},\ldots,X_{n}]$ has a finite zero set. Conversely, if $R$ is an
algebraically closed field, then an ideal in $R[X_{1},\ldots,X_{n}]$ with a
finite zero set is cofinite.

###### Theorem 4.18

If $s$ is a cofinite lrs over $R$, then $s$ is EVR. Conversely, if $R$ is
potential and $s$ is EVR, then $s$ is cofinite.

Proof.  Suppose that $\mbox{Ann}(s)\cap R[X_{i}]=\\{0\\}$ for some $i$. Then

$R[X_{i}]=R[X_{i}]/(\mbox{Ann}(s)\cap
R[X_{i}])\cong\left(R[X_{i}]+\mbox{Ann}(s)\right)/\mbox{Ann}(s)\subseteq
P_{n}/\mbox{Ann}(s)$

and so $P_{n}/\mbox{Ann}(s)$ is not finitely generated. Thus $\mbox{Ann}(s)$
contains no cofinite ideals $I$ (otherwise there would be a map of $P_{n}/I$
onto $P_{n}/\mbox{Ann}(s)$, implying that $P_{n}/\mbox{Ann}(s)$ is finitely
generated) i.e. $s$ is not cofinite.

If $R$ is potential and $s$ is EVR, then by Theorem 4.12 we may assume that
the $f_{i}\in\mbox{Ann}(s)$ are monic, and set $F=(f_{1},f_{2},\ldots,f_{n})$.
Then the monomials $\hbox{\bf\it X}^{a}\bmod F$ for $a\leq(\delta
f_{1}-1,\delta f_{2}-1,\ldots,\delta f_{n}-1)$ generate $P_{n}/F$. Thus
$F\subseteq\mbox{Ann}(s)$ is cofinite i.e. $s$ is cofinite. $\bullet$

In particular, if $R$ is a field, the two notions coincide (cf. Cerlienco &
Piras (1991), Section 4).

###  4.4 Ann(s) as Ideal Quotient

We generalize Proposition 4.1(c) and Fitzpatrick & Norton (1990), Theorem 5.1
to $n$–D sequences over $R$. (The first part of the proof generalizes the
proof for the case $n=1$ and the second part generalizes the minimal
counterexample idea of Fitzpatrick & Norton (1990), loc. cit.)

###### Theorem 4.19

If $f_{i}\in\mbox{Ann}(s)\cap R[X_{i}]$, with $\delta f_{i}\geq 1$ for all
$i\in\hbox{\bf n}$ and $f=\prod_{i=1}^{n}f_{i}$, then

$\mbox{Ann}(s)=\left(\sum_{i=1}^{n}(f_{i}):\beta_{0}(f,s)/\hbox{\bf\it
X}\right).$

Proof.  By Proposition 4.1(c), we can assume that $n\geq 2.$

$\supseteq$: Suppose that $g\in P_{n}\setminus\\{0\\}$ satisfies
$g\beta_{0}(f,s)=\hbox{\bf\it X}\sum_{i=1}^{n}f_{i}u_{i}$ for some $u_{i}\in
P_{n}$. By Theorem 4.9,

$g\Gamma(s)=g\beta_{0}(f,s)/f=\left(\hbox{\bf\it
X}\sum_{i=1}^{n}f_{i}u_{i}\right)/f=\hbox{\bf\it X}\sum_{i=1}^{n}\left(u_{i}\
/\prod_{j=1,j\neq i}^{n}f_{j}\right)$

and so for $a\leq\hbox{\bf 0}$,

$(g\circ s)_{a}=\sum_{i=1}^{n}\left(u_{i}\ /\prod_{j=1,j\neq
i}^{n}f_{j}\right)_{a-\hbox{\bf\scriptsize 1}}=0$

since each $u_{i}\in P_{n}$ i.e. $g\in\mbox{Ann}(s)$.

$\subseteq$: Let $g\in\mbox{Ann}(s)$ and $h=g\Gamma(s)\in L_{n}$. By
Proposition 2.7(c), $\mbox{Supp}(h)\subseteq(\hbox{\bf 0},\delta g]$. Let
$\wp=\\{\wp_{i}:1\leq i\leq n\\}$ be the following partition of $(\hbox{\bf
0},\delta g]$ :

$\wp_{1}=\\{a\in(\hbox{\bf 0},\delta g]:a_{1}>0\\}\mbox{ and
}\wp_{i}=\\{a\in(\hbox{\bf 0},\delta
g]\setminus\bigcup_{j=1}^{i-1}\wp_{j}:a_{i}>0\\}$

if $2\leq i\leq n$. It is clear that $\wp$ is a partition of $(\hbox{\bf
0},\delta g]$ and that for $1\leq i\leq n,\wp_{i}=\\{a\in(\hbox{\bf 0},\delta
g]:a_{j}\leq 0$ for $1\leq j\leq i-1$ and $a_{i}>0\\}$. Let $h_{i}=h|\wp_{i}$
and $p_{i}=h_{i}f/f_{i}$ for $i\in\hbox{\bf n}$. Then $h_{i}\in
X_{i}R((\mathaccent 866{\bf X}_{i}^{-\hbox{\bf\scriptsize 1}}))[X_{i}]$ for
all $i\in\hbox{\bf n}$ and

$g\beta_{0}(f,s)=gf\Gamma(s)=hf=\sum_{i=1}^{n}h_{i}f=\sum_{i=1}^{n}p_{i}f_{i}.$

So it suffices to show that $p_{i}\in\hbox{\bf\it X}P_{n}$ for all
$i\in\hbox{\bf n}$.

Suppose that for some $i\in\hbox{\bf n},p_{i}\not\in\hbox{\bf\it X}P_{n}$, and
let $k$ be the smallest such integer. Now $p_{k}/X_{k}$ is a polynomial in
$X_{k}$, and so for some $r\geq 1$, the coefficient of $X_{k}^{r}$ in $p_{k}$
is not in $R[\mathaccent 866{\bf X}_{k}]$. Letting $d=\delta f_{k}$, the
coefficient of $X_{k}^{d+r}$ in $h_{k}f=p_{k}f_{k}$ cannot therefore be in
$R[\mathaccent 866{\bf X}_{k}]$. But

$\sum_{i=1}^{n}h_{i}f=g\beta_{0}(f,s)\in\hbox{\bf\it X}P_{n}$

and so the coefficient of $X_{k}^{d+r}$ in $h_{k}f$ must cancel with other
coefficients of $X_{k}^{d+r}$ in the $h_{i}f$, for one or more $i\neq k$. If
$1\leq i<k$, the cancellation cannot take place by choice of $k$. If $k<i\leq
n$, the exponent of $X_{k}$ in $fh_{i}$ is at most $d$ by construction of
$h_{i}$. Thus cancellation of the coefficient of $X_{k}^{d+r}$ in $h_{k}f$
cannot take place and we conclude that $p_{i}\in\hbox{\bf\it X}P_{n}$ for all
$i\in\hbox{\bf n}$, as required. $\bullet$

###### Example 4.20

Let $s$ be as in Example 2.4(a). We know that $f_{1}=X_{1}$ and
$f_{2}=X_{2}-1$ belong to $\mbox{Ann}(s)$ and $\Gamma(s)=1/(X_{2}-1),\
\beta_{0}(f_{1}f_{2},s)=X_{1}X_{2}$. From Theorem 4.19,
$\mbox{Ann}(s)=((f_{1},f_{2}):1)=(f_{1},f_{2})=(X_{1},X_{2}-1)$. We remark
that Fitzpatrick & Norton (1990), Theorem 5.2 gives $\mbox{Ann}(s)=(X_{2}-1)$
if $R$ is a field.

###### Example 4.21

Let $s$ satisfy $s_{(i,0)}=1$ for $i\leq 0$, $s_{(0,j)}=1$ for $j\leq 0$ and
$s_{(i,j)}=0$ otherwise. Then $\Gamma(s)=(X_{1}X_{2}-1)/(X_{1}-1)(X_{2}-1)$,
so that by Theorem 4.19,
Ann$(s)=(X_{1}(X_{1}-1),X_{2}(X_{2}-1):X_{1}X_{2}-1).$

Combining Theorems 4.13, 4.16 and 4.19 now yields an algorithm for computing a
basis for $\mbox{Ann}(s)$:

###### Algorithm 4.22

(cf. Fitzpatrick & Norton (1990), Algorithm 3.8).

Input: An EVR $s\in S^{n}(R)^{-},R$ a potential domain.

Output: A basis for $\mbox{Ann}(s)$.

1\. For each $i\in\hbox{\bf n}$, find the monic generator $\gamma_{i}$ of
$\mbox{Ann}(s)\cap R[X_{i}]$ using Theorem 4.13 or Theorem 4.16.

2\. Compute $\gamma=\prod_{i=1}^{n}\gamma_{i}$ and
$\beta_{0}(\gamma,s)/\hbox{\bf\it X}$.

3\. Find a basis for the ideal quotient
$(\sum_{i=1}^{n}(\gamma_{i}):\beta_{0}(\gamma,s)/\hbox{\bf\it X}).$

###### Remark 4.23

Over a field ${{F}}$, Step 3 may be done in several ways:

(i) using the basis $\\{\hbox{\bf\it X}^{m}:m\leq\delta\gamma-\hbox{\bf 1}\\}$
for ${{F}}[\hbox{\bf\it X}]/(\gamma_{1},\gamma_{2},\ldots,\gamma_{n})$, find
an ${{F}}$-basis for solutions $f$ of the homogeneous equation

$f\beta_{0}(\gamma,s)/\hbox{\bf\it X}+\sum_{i=1}^{n}\gamma_{i}u_{i}=0$

where $u_{i}\in{{F}}[\hbox{\bf\it X}]$. Augmenting these solutions by
$\\{\gamma_{1},\gamma_{2},\ldots,\gamma_{n}\\}$ yields an ${{F}}$–basis for
$\mbox{Ann}(s)$.

This approach is an application of Buchberger (1985), Method 6.7, which
applies since $\\{\gamma_{1},\gamma_{2},\ldots,\gamma_{n}\\}$ is trivially a
(reduced) groebner basis for any term order. In this case, Algorithm 4.22 has
complexity $O(\prod_{i=1}^{n}\delta\gamma_{i}^{3})$. The ${{F}}$–basis found
can of course be converted to a reduced groebner basis with respect to any
given term order, if desired.

(ii) Cox et al. (1991), Sections 3.3, 3.4 reduce the computation of a basis
for an ideal quotient to computing a groebner basis (with respect to the
lexicographic term order) of an intersection of ideals. In this way, we obtain
a groebner basis for $\mbox{Ann}(s)$. This approach was applied to computing
an ideal basis of a $2$–D cyclic code and its dual in Norton (1995b).

Acknowledgements: The author would like to thank Aidan Schofield for a useful
conversation, the U.K. Science and Engineering Research Council for financial
support and the referees for helpful comments and suggestions. Thanks also to
Guy Chassé for a copy of Ferrand (1988).

Note added in proof: This paper combines two papers “On $n$–dimensional
sequences I,II” that were submitted to this journal. The first paper described
a border partition for left–shifting, gave an inductive proof of Corollary
3.10 and some applications of it. Lemma 3.4 (and right–shifting) appeared in
the second paper. The author also suggested a new proof of Corollary 3.10 (via
Lemma 3.4 and a direct, rather than inductive proof of Theorem 3.8) in the
second paper. This revised version adopts the new approach.

References

Bourbaki, N. (1972). Commutative Algebra. Hermann.

Boztaş, S., Hammons, A.R., Kumar, P.V. (1992). 4–Phase sequences with
near–optimum correlation properties. IEEE Trans. Information Theory 38,
1101–1113.

Buchberger, B. (1985). Groebner bases: an algorithmic method in polynomial
ideal theory. Multidimensional Systems Theory, N.K. Bose (ed.), 184–232.
Reidel, Dordrecht.

Cerlienco, L., Mignotte, M., Piras, F. (1987). Suites Récurrentes Linéaires.
L’Enseignement Mathématiques 33, 67–108.

Cerlienco, L., Piras, F. (1991). On the continuous dual of a polynomial
bialgebra. Communications in Algebra 19, 2707–2727.

Chabanne, H., Norton, G.H. (1994). The $n$–dimensional key equation and a
decoding application. IEEE Trans. Information Theory 40, 200 – 203.

Cox, D., Little, J. and O’Shea, D. (1991). Ideals, Varieties and Algorithms.
Springer.

Fan, P.Z., Darnell,M. (1994). Maximal length sequences over Gaussian integers.
Electronic Letters 30, 1286–1287.

Feng, G.L., Tzeng, K.K. (1989). A generalization of the Berlekamp–Massey
algorithm for multisequence shift register synthesis with applications to the
decoding of cyclic codes. IEEE Trans. Information Theory 37, 1274–1287.

Ferrand, D. (1988). Suites Récurrentes. IRMAR, Université de Rennes.

Fitzpatrick, P., Norton, G.H. (1990). Finding a basis for the characteristic
ideal of an $n$–dimensional linear recurring sequence. IEEE Transactions on
Information Theory 36, 1480–1487.

Fitzpatrick, P., Norton, G.H. (1991). Linear recurring sequences and the path
weight enumerator of a convolutional code. Electronic Letters 27, 98–99.

Fitzpatrick, P., Norton, G.H. (1995). The Berlekamp–Massey algorithm and
linear recurring sequences over a factorial domain. J. Applicable Algebra in
Engineering, Communications and Computing. 6, 309–323.

Fossum, R. (1973). The divisor class group of a Krull domain. Springer
Ergebnisse 74.

Greene, D.H. & Knuth, D.E. (1982). Mathematics for the Analysis of Algorithms,
2nd Edition. Birkhäuser, Boston.

Homer, S. and Goldman, J. (1985). Doubly periodic sequences and two-
dimensional recurrences. SIAM J. Alg. Disc. Math. 6, 360–370.

Ikai, T., Kosako, H., Kojima, Y. (1975). Two dimensional cyclic codes.
Electronics and Communications in Japan 57–A, 27–35.

Ikai, T., Kosako, H. and Kojima, Y. (1976). Basic theory of two–dimensional
cyclic codes. Electronics and Communications in Japan 59–A, 31–47.

Imai, H., Arakaki, M. (1974). A theory of two–dimensional cyclic codes.
National Convention Record of Institute of Electronics and Communication
Engineers, Japan, 1564. In Japanese.

Imai, H. (1977) A theory of two–dimensional codes. Inform. Control 34, 1–21.

Lidl, R., Niederreiter, H. (1983). Finite Fields, Encyclopedia of Mathematics
and its Applications 20. Addison–Wesley.

Lin, D. & Liu, M. (1988). Linear Recurring $m$-Arrays. Proceedings of
Eurocrypt 88. LNCS 330, 351–357. Springer.

Massey, J.L. (1969). Shift register synthesis and BCH decoding. IEEE Trans.
Information Theory 15, 122–127.

McEliece, R. (1987). Finite Fields for Computer Scientists and Engineers.
Kluwer Academic Press.

Nerode, A. (1958). Linear automaton transformations. Proc. Amer. Math. Soc. 9,
541–544.

Niederreiter, H. (1988). Sequences with almost perfect linear complexity
profile. In Advances in Cryptology– Eurocrypt ’87. LNCS 304, 37–51. Springer.

Norton, G.H. (1995a). On the minimal realizations of a finite sequence. J.
Symbolic Computation 20, 93–115.

Norton, G.H. (1995b). The solution module (of $n$–dimensional sequences) of an
ideal containing $(X_{1}^{M_{1}}-1,\ldots,X_{n}^{M_{n}}-1)$. Proc.
$\mbox{IV}^{\mbox{th}}$ I.M.A. Conference on Coding and Cryptography (P.G.
Farrell, ed.), Formara Ltd., 315–326.

Norton, G.H. (1995c). Encoding an $n$–dimensional cyclic code over a finite
field. Presented at Third International Conference on Finite Fields, Glasgow,
July 1995.

Norton, G.H. (1995d). Some decoding applications of minimal realization. Proc.
$V^{th}$ I.M.A. Conference on Coding and Cryptography LNCS 1025, 53–62.
Springer.

Norton, G.H. (1995e). On the minimal realizations of a finite $n$–D sequence.
In preparation.

Peterson W. W., & Weldon, E.J. (1972). Error Correcting Codes, 2nd Edition.
MIT Press. Cambridge, Massachusetts.

Prabhu, K.A. & Bose, N.K. (1982). Impulse Response Arrays of Discrete–Space
Systems over a Finite Field. IEEE Trans. Acoustics, Speech and Signal
Processing 30, 10–18.

Rueppel, R.A. (1986). Analysis and Design of Stream Ciphers. Springer.

Sakata, S. (1978). General theory of doubly periodic arrays over an arbitrary
finite field and its applications. IEEE Trans. Information Theory 24, 719–730.

Sakata, S. (1981). On determining the independent point set for doubly
periodic arrays and encoding two–dimensional cyclic codes and their duals.
IEEE Trans. Information Theory 27, 556–565.

Sakata, S. (1988). Finding a minimal set of linear recurring relations capable
of generating a given finite two–dimensional array. J. Symbolic Computation 5,
321–337.

Sakata, S. (1990). Extension of the Berlekamp–Massey algorithm to $n$
dimensions. Information and Computation  84, 207–239.

Welch, L.R., Scholtz, R.A. (1979). Continued fractions and Berlekamp’s
algorithm. IEEE Trans. Information Theory 25, 19–27.

Zierler, N. (1959). Linear recurring sequences. J. S.I.A.M. 7, 31–48.

email<EMAIL_ADDRESS>