ON N-DIMENSIONAL SEQUENCES .1.

Let R be a commutative ring and let n greater than or equal to 1. We s tudy Gamma(s), the generating function and Ann(s), the ideal of charac teristic polynomials of s, an n-dimensional sequence over R. We expres s f(X(1),...,X(n)).Gamma(s)(X(1)(-1),...,X(n)(-1)) as a partitioned su m. That is, we give (i) a 2(n)-fold ''border'' partition (ii) an expli cit 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(o)(f, s), the ''border polynomial'' of f and s, which is divisible by X(1)...X(n). We say that s is eventually rectilinear i f the elimination ideals Ann(s)boolean AND R[X(i)] contain an f(i)(X(i )) for 1 less than or equal to i less than or equal to n. In this case , we show that Ann(s) is the ideal quotient (Sigma(i=1)(n)(f(i)) : bet a(o)(f, s)/(X(1)...X(n))). When R and R[[X(1),X(2),...,X(n)]] are fact orial domains (e.g. R a principal ideal domain or F[X(1),...,X(n)]), w e compute the monic generator gamma(i) of Ann(s)boolean AND R[X(i)] fr om known f(i) is an element of Ann(s)boolean AND R[X(i)] or from a fin ite number of 1-dimensional linear recurring sequences over R. Over a field F this gives an O(Pi(i=1)(n) delta gamma(i)(3)) algorithm to com pute an F-basis for Ann(s).