On $n$-Dimensional Sequences. I

Let $R$ be a commutative ring and let $n\ge 1.$ We study $\mathrm{\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,\dots ,X_n)\cdot \mathrm{\Gamma }(s)(X_1^{-1},\dots ,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 $β_0(f,s)$, the border polynomial’’ of $f$ and $s$, which is divisible by $X_1\cdots X_n$. We say that $s$ is {\em eventually rectilinear} if the elimination ideals Ann$(s)\cap R[X_i]$ contain an $f_i(X_i)$ for $1\le i\le n$. In this case, we show that $Ann(s)$ is the ideal quotient $({\sum }_{i=1}^n(f_i):{\beta }_0(f,s)\mathrm{/}(X_1\cdots X_n))\mathrm{.}$ When $R$ and $R[[X_1,X_2,\dots ,X_n]]$ are factorial domains (e.g. $R$ a principal ideal domain or $\mathbb{F}[X_1,\dots ,X_n]$), we compute {\em the monic generator} ${\gamma }_i$ of $Ann(s)\cap R[X_i]$ from known $f_i\in Ann(s)\cap R[X_i]$ or from a finite number of $1$–dimensional linear recurring sequences over $R$. Over a field $\mathbb{F}$ this gives an $O({\prod }_{i=1}^n\delta {\gamma }_i^3)$ algorithm to compute an $\mathbb{F}$–basis for $Ann(s)$.