Portal de Periódicos da CAPES

On n-Dimensional Sequences. I

1995; Elsevier BV; Volume: 20; Issue: 1 Linguagem: Inglês

10.1006/jsco.1995.1039

1095-855X

Graham H. Norton,

Polynomial and algebraic computation

Let R be a commutative ring and let n ≥ 1. We study Γ(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) · Γ(s)(X-11,…,X-1n) as a partitioned sum. That is, we give (i) a 2n-fold "border" partition (ii) an explicit expression for the product as a 2n-fold sum; the support of each summand is contained in precisely one member of the partition. A key summand is βo(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[Xi] contain an fi (Xi) for 1 ≤ i ≤ n. In this case, we show that Ann(s) is the ideal quotient (∑ni=1(fi) : βo(f, s)/(X1 … Xn )). When R and R[[X1, X2 ,…, Xn]] are factorial domains (e.g. R a principal ideal domain or F [X1,…, Xn]), we compute the monic generator γi of Ann(s) ∩ R[Xi] from known fi ϵ Ann(s) ∩ R[Xi] or from a finite number of 1-dimensional linear recurring sequences over R. Over a field F this gives an O(∏ni=1 δγ3i) algorithm to compute an F-basis for Ann(s).