| Abstract | Let R be a commutative ring and let n equal or bigger 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(X1, ... ,Xn) . Gamma(s)(X^(-1)_1, ... , X^(-1)_n) 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 X1 ... Xn.
We say that s is eventually rectilinear if the elimination ideals Ann(s) ? R[X_i] contain an f_i(X_i) for 1 equal or bigger i equal or bigger n. In this case, we show that Ann(s) is the ideal quotient (Sum^n_(i=1) (f_i): beta_0(f,s)/(X_1 ... X_n)).
When R and R[[X_1, X_2, ... , X_n]] are factorial domains (e.g. R a principal ideal domain or F[X_1, ... , X_n]), we compute the monic generator n/i of Ann(s) ? R[X_i] from known f_i in Ann(s) ? R[X_i] or from a finite number of 1-dimensional linear recurring sequences over R. Over a field F this gives an O(Pi^n_(i=1) sigma gamma^3_i algorithm to compute an F-basis for Ann(s). |
