ON LINEAR DIFFERENCE EQUATIONS OVER RINGS AND MODULES

PII. S0161171204302085 http://ijmms.hindawi.com

© Hindawi Publishing Corp.

ON LINEAR DIFFERENCE EQUATIONS OVER RINGS AND MODULES

JAWAD Y. ABUHLAIL Received 8 February 2003

We develop a coalgebraic approach to the study of solutions of linear difference equations over modules and rings. Some known results about linearly recursive sequences over base fields are generalized to linearly (bi)recursive (bi)sequences of modules over arbitrary com- mutative ground rings.

2000 Mathematics Subject Classification: 16W30, 39A99.

1. Introduction. Although the theory of linear difference equations over base fields is well understood, the theory over arbitrary ground rings and modules is still under development. It is becoming more interesting and is gaining increasingly special impor- tance mainly because of recent applications in coding theory and cryptography (e.g., [10,15]).

In a series of papers, Taft et al. (e.g., [17, 22, 24]) developed a coalgebraic aspect for the study of linearly recursive sequences over fields. Moreover, Grünenfelder et al.

studied in [8,9] the linearly recursive sequences overfinite-dimensionalvector spaces.

Linearly recursive (bi)sequences over arbitrary rings and modules were studied inten- sively by Nechaev et al. (e.g., [16,20,21]); however, the coalgebraic approach in their work was limited to the field case. Generalization to the case of arbitrary commuta- tive ground rings was studied by several authors including Kurakin [12,13, 14] and eventually Abuhlail, Gómez-Torrecillas, and Wisbauer [4].

In this paper, we develop a coalgebraic aspect for the study of solutions of linear difference equations overarbitrary rings and modules. For some of our results, we assume that the ground ring is Artinian. Besides the new results, this paper extends results in [4] and “Kapitel 4” of my doctoral thesis [2]. A standard reference for the theory of linearly recursive sequences over rings and modules is the comprehensive work of Mikhalev et al. [16]. For the theory of Hopf algebras, the reader may refer to any of the classical references (e.g., [1,19,23]).

By R we denote a commutative ring with 1R≠0R and withU (R)= {r ∈R|r is invertible}the group ofunits ofR. The category ofR-(bi)modules will be denoted by ᏹR. For anR-moduleM, we call anR-submoduleK⊂Mpure(in the sense of Cohn) if for everyR-moduleN, the induced mapιk⊗idN:K⊗RN→M⊗RNis injective.

For anR-algebraAand anA-moduleM, we call anA-submoduleK⊂M R-cofinite ifM/K is finitely generated inᏹR. For anR-algebraA, we denote by᏷A the class of R-cofinite ideals. IfA is an R-algebra with ᏷A a filter, then we define for every left

A-moduleMthefinite dualrightA-module M^◦:=

f∈M^∗|Ke(f )⊃IM

for someA-idealIwithA/Ifinitely generated overR

. (1.1)

ByN(resp.,Z) we denote the set of natural numbers (resp., the ring of integers). More- over, we setN0:= {0,1,2,3, . . .}. For ann×nmatrixMoverR, we denote the charac- teristic polynomial byχ(M). The identity matrix of ordernoverR is denoted byEn. For anm×nmatrixAand ak×lmatrixB, theKronecker product(tensor product) of AandBis themk×nlmatrix

A⊗B:=









a11·B a12·B ··· ··· a1n·B a21·B a22·B ··· ··· a2n·B

... ... ... ... ... am1·B am2·B ··· ··· amn·B







. (1.2)

2. Preliminaries. LetMbe anR-module and M[x]:=M x1, . . . , xk

, M x,x⁻¹

:=M x1, x₁⁻¹, . . . , xk, x_k⁻¹

. (2.1)

We consider thepolynomial ringR[x]and thering of Laurent polynomialsR[x,x⁻¹]as commutativeR-algebras with the usual multiplication and the usual unity. For everyR- moduleM,M[x](resp.,M[x,x⁻¹]) is anR[x]-module (resp., anR[x,x⁻¹]-module) with action induced from theR-module structure onM and we have, moreover, canonical R-module isomorphisms

M[x]M⊗RR[x]M^(Nk0), M x,x⁻¹

M⊗RR x,x⁻¹

M^(Zk). (2.2) Forn=(n1, . . . , nk)∈N^k0 (resp.,z=(z1, . . . , zk)∈Z^k), we setxⁿ:=xⁿ₁¹, . . . , xⁿ_k^k (resp., x^z:=x^z₁¹, . . . , x_k^zk).

2.1. LetM be anR-module,l=(l1, . . . , lk)∈N^k0, and consider thesystem of linear difference equations(SLDE)

x_n+(l1,0,...,0)+

l₁

i=1

p(1,l₁−i)(n)x_n+(l1−i,0,...,0)=g1(n),

x_n+(0,l2,0,...,0)+

l₂

i=1

p(2,l₂−i)(n)x_n+(0,l2−i,0,...,0)=g2(n), ...

xn+(0,...,0,lk)+

l_k

i=1

p(k,l_k−i)(n)xn+(0,...,0,lk−i)=gk(n),

(2.3)

where thepjl’s areR-valued functions and thegj’s areM-valued functions defined for alln∈N^k0. If thegj’s are identically zero, then (2.3) is said to be ahomogenousSLDE.

If thepjl’s are constants, then (2.3) is said to be an SLDEwith constant coefficients.

2.2. For anR-moduleMandk≥1, let

᏿^kM :=

u:N^k0 →M

M^Nk0 (2.4)

be theR-module ofk-sequencesoverM. IfM(resp.,k) is not mentioned, then we mean thatM=R(resp.,k=1). Forf (x)=

iaixⁱ∈R[x]andw∈᏿M^k, define f (x) w=u∈᏿M^k, u(n):=

i

aiw(n+i)∀n∈N^k0. (2.5)

With this action,᏿M^k is anR[x]-module. For subsetsI⊂R[x]andL⊂᏿M^k, consider the annihilator submodules

An_᏿k M (I)=

w∈᏿^kM |f w=0 for everyf∈I , AnR[x](L)=

h∈R[x]|h u=0 for everyu∈L

. (2.6)

Note that An_᏿^k_M(I)⊂᏿M^kis anR[x]-submodule and AnR[x](L) R[x]is an ideal.

2.3. A polynomialf (x)∈R[x]is called monic if its leading coefficient is 1R. For every monic polynomialf (x)=x^l+a_l−1x^l−1+ ··· +a1x+a0∈R[x], thecompanion matrixoffis defined to be thel×lmatrix

Sf :=













0R 0R ··· 0R −a0

1R 0R ··· 0R −a1

0R 1R ··· 0R −a2

... ... ... ... ... 0R 0R ··· 1R −a_l−1













. (2.7)

In factSf is a matrix that hasf (x)as its characteristic polynomial as well as its mini- mum polynomial (see [11, Theorem 4.18]).

Definition2.1. An idealI R[x]will be calledmonic, if it contains a nonempty subset of monic polynomials

fj

xj

=x^l_j^j+a^(j)_l

j−1x_j^lj−1+···+a^(j)₁ xj+a^(j)₀ |j=1, . . . , k

. (2.8)

In this case, the polynomials (2.8) are calledelementary polynomials and(f1(x1), . . . , fk(xk)) R[x] an elementary ideal. A monic polynomial q(x)∈ R[x] is called re- versibleifq(0)∈U (R). An idealI R[x,x⁻¹]will be calledreversibleif it contains a subset of reversible polynomials{q1(x1), . . . , qk(xk)}.

2.4. LetMbe anR-module. We callu∈᏿^kM alinearly recursivek-sequence(resp., a linearly birecursivek-sequence) if AnR[x](u)is a monic ideal (resp., a reversible ideal).

Note that ak-sequenceu∈᏿M^k is linearly recursive if and only if it is a solution of a homogenous SLDE with constant coefficients of the form (2.3). If AnR[x](u)contains a set of monic polynomials{f1(x1), . . . , fk(xk)}, wherefj(xj)is of ordermj,j=1, . . . , k, then these are calledelementary characteristic polynomialsofu, anduis said to have orderm:=(m1, . . . , mk). Characteristic polynomials ofuof least degreenj,j=1, . . . , k,

are calledminimal polynomialsofuandn:=(n1, . . . , nk)is called therank ofu. The subsetsᏸ^kM ⊆᏿^kM of linearly recursivek-sequences andᏮ^kM ⊆᏿^kM of linearly birecur- sivek-sequences are obviouslyR[x]-submodules.

2.5. Thelexicographical linear order()onN^k0is defined as follows: fori=(i1, . . . , ik) andn=(n1, . . . , nk)∈N^k0, we sayinif the first number in the sequence of integers

n1+···+nk

−

i1+···+ik

, n1−i1, . . . , nk−ik (2.9) that is different from zero is positive (see [18, page 170]).

LetMbe anR-module,F:= {f1(x1), . . . , fk(xk)} ⊂R[x]a subset of monic polynomials with deg(fj(xj))=ljforj=1, . . . , k,l:=(l1, . . . , lk),1:=(1, . . . ,1), andIF:=(f1, . . . , fk) R[x]. Note that the natural order “≤” onN0 induces on N^k0 a partial order and we define thepolyhedronΠF=Π(l):= {i∈N^k0|i≤l−1}. Theinitial polyhedron of values ofω∈᏿M^k is defined asω(ΠF):= {ω(i)|i∈ΠF}. Forl=l1, . . . , lk, the points of the polyhedronΠFbuild a chain0=i0i1 ··· i_l−1and we can writeω(ΠF)as aninitial vector of values(ω(0), ω(i1), . . . , ω(i_l−1))∈M^l.

Letω∈An

᏿^kM (f1(x1), . . . , fk(xk)), wherefj(xj)is monic forj=1, . . . , nand write, for everyn=(n1, . . . , nk)∈N^k0,

x_j^nj=hj xj

fj xj

+rj xj

, deg rj

xj

< lj. (2.10) If we set

g⁽ⁿ⁾(x):= k j=1

rj

xj

=

i∈ΠF

a⁽ⁿ⁾_i xⁱ, v:=xⁿ ω=g⁽ⁿ⁾(x) ω, (2.11)

then

ω(n)=v(0)=

i∈ΠF

a⁽ⁿ⁾_i ω(i) for everyn∈N^k0. (2.12)

Consequently,ωis completely determined by the initial polyhedron of valuesω(ΠF).

Fort∈ΠF, define the sequenceet^F∈An_᏿k

R (IF)with initial polyhedron of valueset^F(i)= δi,tfor alli∈ΠF. The sequencee^F_l−1is called theimpulse sequenceof An_᏿k

R (IF).

3. Examples. We now give some examples of linearly recursive sequences. For more examples, the reader may refer to [16].

Example3.1(geometric progression). LetM be anR-module,m∈M,r ∈R, and considerw∈᏿M given by

w(n):=rⁿm for everyn∈N0. (3.1) Thenw∈ᏸMwith initial conditionw(0)=mand elementary characteristic polynomial f (x)=x−r. Moreover, AnR[x](w)=R[x](x−r )+R[x]AnR(r ).

Example3.2(arithmetic progression). LetMbe anR-module,{p, q} ⊂M, and con- siderw∈᏿M given by

w(n):=p+nq for everyn∈N0. (3.2) Thenw∈ᏸM with initial vector(p, p+q)and elementary characteristic polynomial f (x)=(x−1)². If AnR(q)=0, thenf (x) is a unique minimal polynomial of w. If r∈AnR(q), thenfr(x)=(x−1)²+r (x−1)is another minimal polynomial ofw.

Remark3.3. An example of a nonrecursive sequence overZis the sequence of prime positive numbers{2,3,5,7, . . .}.

Example3.4. LetE= {f1(x), . . . , fk(x)} ⊂R[x]be a subset of monic polynomials.

(1) LetM be anR-module,ui ∈An_᏿M(fi) fori=1, . . . , k, and consider u:=u1

+·

···+^·uk∈᏿M^k defined byu(n)=u1(n1)+ ··· +uk(nk). Thenu∈An_᏿k

M (g1(x1), . . . , gk(xk)), where fori=1, . . . , k,

gi

xi

=



 fi

xi

, fi

1R

=0R, fi

xi xi−1R

, otherwise. (3.3)

(2) LetM1, . . . , Mk beR-modules,ui∈An_᏿Mi(fi)fori=1, . . . , k,M:=M1⊕ ··· ⊕Mk, and consideru∈᏿^kM defined byu(n):=(u1(n1), . . . , uk(nk)). Thenu∈An_᏿k

M (g1(x1), . . . , gk(xk)), where thegi’s are defined as in (3.3).

(3) Let ui ∈ An_᏿R(fi) for i= 1, . . . , k and consider u ∈ ᏿R^k defined by u(n):= u1(n1), . . . , uk(nk). Thenu∈An_᏿k

R (f₁(x1), . . . , fk(xk))and An_᏿k

R

f1

x1

, . . . , fk

xk

An_᏿R f1

⊗R···⊗RAn_᏿R fk

. (3.4)

(4) LetM1, . . . , MkbeR-modules,ui∈An_᏿Mi(fi)fori=1, . . . , k,M:=M1⊗R···⊗RMk, and consideru∈᏿M^kdefined byu(n):=u1(n1)⊗···⊗uk(nk). Thenu∈An_᏿k

M (f1(x1), . . . , fk(xk))and

An_᏿k M

f1

x1

, . . . , fk

xk

An_᏿M

1

f1

⊗R···⊗RAn_᏿Mk fk

. (3.5)

4. AdmissibleR-bialgebras and HopfR-algebras. For everyR-coalgebra(C,∆C, εC), there is adualR-algebraC^∗:=HomR(C, R)with the so-calledconvolution productmul- tiplication

(f∗g)(c):= f

c1

g c2

∀f , g∈C^∗, c∈C, (4.1)

and unity εC. Although every algebraA has a dual coalgebra, if the ground ring is hereditary Noetherian (e.g., a field), the existence of dual coalgebras of algebras over an arbitrary commutative ground ring is not guaranteed! One way to handle this problem is to restrict the class ofR-algebras for which the dualR-coalgebras are defined.

Definition 4.1. Let A be an R-algebra (resp., an R-bialgebra, a Hopf R-algebra).

ThenAis called

(1) anα-algebra(resp., anα-bialgebra, aHopf α-algebra) if᏷Ais a filter andA^◦⊂R^A is pure;

(2) cofinitaryif᏷Ais afilter and, for everyI∈᏷A, there exists anA-ideal ¯I⊆Iwith A/¯Ifinitely generated and projective.

4.1. LetHbe anR-bialgebra and consider the class ofR-cofiniteH-ideals᏷H. We call HanadmissibleR-bialgebraifHis cofinitary and᏷Hsatisfies the following axioms:

(A1) for allI, J∈᏷H, there existsL∈᏷H, such that∆H(L)⊆Im(I⊗RH)+Im(H⊗RJ), (A2) there existsI∈᏷H, such that Ke

εH

⊃I.

We call a HopfR-algebraH anadmissible Hopf R-algebra ifH is cofinitary and᏷H

satisfies (A1), (A2), and

(A3) for everyI∈᏷H, there existsJ∈᏷H, such thatSH(J)⊆I.

Remark4.2. It follows from the proof of [3, Proposition 4.2.] that every cofinitary R-algebra (resp.,R-bialgebra, HopfR-algebra) is anα-algebra (resp., anα-bialgebra, a Hopfα-algebra). By [2, Lemma 2.5.6.], every cofinitary bialgebra (Hopf algebra) over a Noetherianground ring is admissible.

Proposition4.3(see [2, Propositions 2.4.13 and 2.5.7]). (1)IfAis a cofinitaryR- algebra, thenA^◦is anR-coalgebra. IfHis an admissibleR-bialgebra (resp., an admissible HopfR-algebra), thenH^◦is anR-bialgebra (resp., a HopfR-algebra).

(2)LetRbe Noetherian. IfAis anα-algebra (resp., anα-bialgebra, a Hopfα-algebra), thenA^◦is anR-coalgebra (resp., anR-bialgebra, a HopfR-algebra).

Proposition4.4. LetAbe anα-algebra (resp., anα-bialgebra, a Hopfα-algebra), Ba cofinitaryR-algebra (resp.,R-bialgebra, HopfR-algebra), and consider the canonical mapσ:A^◦⊗RB^◦→(A⊗RB)^◦. Then

(1) σ is injective,

(2) ifRis Noetherian, thenσis an isomorphism ofR-coalgebras (resp.,R-bialgebras, HopfR-algebras).

Proof. (1) The proof is along the lines of the proof of [14, Proposition 5].

(2) The proof is along the lines of the proof of [3, Theorem 4.10].

The proof of [3, Lemma 4.12] can be generalized to prove the following lemma.

Lemma4.5. For any set of reversible polynomials{q1(x1), . . . , qk(xk)} ⊆R[x], there is an isomorphism ofR-algebras

R[x]/

q1 x1

, . . . , qk xk

R x,x⁻¹ /

q1(x1 , . . . , qk

xk

. (4.2)

Lemma4.6(see [14, Proposition 1]). LetRbe anarbitrarycommutative ring.

(1)An idealI R[x]isR-cofinite if and only if it is monic. Consequently, everyR- cofiniteR[x]-ideal contains an idealI R[x]¯ such thatR[x]/I¯is free of finite rank. In particular,R[x]is cofinitary.

(2)An idealI R[x,x⁻¹]isR-cofinite if and only if it is reversible. Consequently, every R-cofiniteR[x,x⁻¹]-ideal contains an idealI R[x,x¯ ⁻¹]such thatR[x,x⁻¹]/¯I is free of finite rank. In particular,R[x,x⁻¹]is cofinitary.

5. Linearly (bi)recursive sequences. In this section, we study thelinearly(bi)recur- sivek-sequencesoverR-modules, whereRis an arbitrary commutative ground ring.

5.1. Let(G, µG, eG)be a (commutative) monoid. Considering the elements of the basis Gasgroup-like elements, the monoid algebraRGbecomes a (commutative) cocommu- tativeR-bialgebra(RG, µ, η,∆g, εg), where

∆g(x)=x⊗x, εg(x)=1R for everyx∈G. (5.1) IfGis a group, thenRGis a HopfR-algebra with antipode

Sg:RG →RG, x→x⁻¹ for everyx∈G. (5.2) 5.2. Bialgebra structures onR[x]. Consider the commutative monoidGgenerated by{xj|j=1, . . . , k}. ThenR[x]=RGhas the structure of acommutative cocommutative R-bialgebraR[x;g]=(R[x], µ, η,∆g, εg), where µis the usual multiplication, ηis the usual unity, and for alln≥0, j=1, . . . , k,

∆g:R[x]→R[x]⊗RR[x], x_jⁿ→xⁿ_j⊗xⁿ_j,

εg:R[x] →R, x_jⁿ→1R. (5.3)

On the other hand,R[x;p]=(R[x], µ, η,∆p, εp)is acommutative cocommutativeHopf R-algebra, whereµ is the usual multiplication,ηis the usual unity, and for alln≥0, j=1, . . . , k,

∆p:R[x]→R[x]⊗RR[x], x_jⁿ→ n t=0

n t

x_j^t⊗x_j^n−t, εp:R[x] →R, xⁿ_j →δn,0,

Sp:R[x] →R[x], xⁿ_j →(−1)ⁿxⁿ_j.

(5.4)

Remarks5.1. (1) LetRbe an integral domain, then it follows by [7, Theorem 1.3.6]

that for every setG, the class of group-like elements of theR-coalgebraRGisGitself.

Then one can show, as in the field case [6], thatR[x;g]andR[x;p]are the only possible R-bialgebra structures onR[x]with the usual multiplication and the usual unity.

(2) TheR-bialgebraR[x;g]has no antipode because the group-like elements in a Hopf R-algebra should be invertible.

The proof of the following result depends mainly on the arguments of [14, Theorem 2].

Proposition5.2. LetR be an arbitrary commutative ring. ThenR[x;g] is an ad- missibleR-bialgebra andR[x;p]is an admissible HopfR-algebra. Hence,R[x;g]^◦is an R-bialgebra andR[x;p]^◦is a HopfR-algebra.

Proof. Denote by(R[x],∆, ε)either of the cofinitaryR-bialgebrasR[x;g]andR[x;p].

LetI, J R[x]beR-cofinite ideals and assume without loss of generality thatR[x]/I andR[x]/Jare free of finite rank (seeLemma 4.6). Letβbe a basis of the freeR-module B:=R[x]/I⊗RR[x]/Jand consider theR-algebra morphism ¯∆:=(πI⊗πJ)◦∆:R[x]→ R[x]/I⊗RR[x]/J. Forj=1, . . . , k, letMjbe the matrix of theR-linear map

Tj:B →B, b→∆¯ xj

b, (5.5)

with respect toβ, andχj(λ)its characteristic polynomial. Thenχj(∆¯(xj))=0 forj= 1, . . . , k. Since ¯∆is an R-algebra morphism, it follows thatχj(xj)∈Ke(∆¯)=∆⁻¹(I⊗R

R[x]+R[x]⊗RJ)forj=1, . . . , k. If we setL:=(χ1(x1), . . . , χk(xk)) R[x], then∆(L)⊆ I⊗RR[x]+R[x]⊗RJ, that is, ᏷R[x] satisfies axiom (A1). Note that R[x]/Ke(ε)R, hence᏷R[x]satisfies axiom (A2). Consequently,R[x;g]andR[x;p]are admissibleR- bialgebras. Consider now the Hopf R-algebra R[x;p]with the bijectiveantipode Sp. For every ideal I R[x], S_p⁻¹(I) R[x;p] is an ideal and we have an isomorphism ofR-modulesR[x]/S_p⁻¹(I)R[x]/I, hence᏷R[x;p] satisfies axiom (A3). Consequently, R[x;p]is an admissible HopfR-algebra. The last statement follows now byProposition 4.3.

If M is an arbitrary R-module, then we have obviously an isomorphism ofR[x]- modules

ΦM:M[x]^∗ →᏿^kM^∗, → n→ m→ mxⁿ

, (5.6)

with inverseu[mxⁿu(n)(m)].

Proposition5.3. LetMbe anR-module. Then (5.6) induces an isomorphism ofR[x]- modules

M[x]^◦ᏸ^kM^∗. (5.7)

Proof. Consider theR[x]-module isomorphismM[x]^∗ΦM ᏿^kM^∗, see (5.6). Let∈ M[x]^◦. Then there exists anR-cofiniteR[x]-idealIsuch thatI =0. SoI ΦM()= ΦM(I )=0, that is,I⊂AnR[x](ΦM()). ByLemma 4.6(1),Iis monic, that is,ΦM()∈ ᏸM^k∗.

On the other hand, letu∈ᏸ_M^k∗. By definition,J:=AnR[x](u)is a monic ideal and it follows byLemma 4.6(1) thatJ R[x]isR-cofinite. For:=Φ⁻M¹(u), we haveJ = J Φ⁻¹M (u)=ΦM⁻¹(J u)=0, that is,∈M[x]^◦.

5.3. The coalgebra structure onᏸ^{k. By}Lemma 4.6(1),(R[x], µ, η)is a cofinitaryR- algebra, whereµis the usual multiplication andηis the usual unity. Hence,(R[x]^◦, µ^◦, η^◦)is (byProposition 4.3) anR-coalgebra, where

µ^◦:R[x]^◦ →R[x]^◦⊗RR[x]^◦, f→ x_i^s⊗x^t_j→f x_i^sx^t_j

, s, t≥0, i, j=1, . . . , k , η^◦:R[x]^◦ →R, f→f

1R

.

(5.8)

Soᏸ^kR[x]^◦has the structure of anR-coalgebra with counity

ε_ᏸk:ᏸ^k →R, u→u(0), (5.9)

and comultiplication described as follows (see [16, Proposition 14.16]).

Letu∈ᏸ^k,{f1(x1), . . . , fk(xk)} ⊆AnR[x](u)a subset of elementary characteristic polynomials with deg(fj(xj))=lj, andl:=(l1, . . . , lk). So we have for alln,i∈N^k0,

u(n+i)= xⁱ u

(n)=





t≤l−1

xⁱ u (t)·e^F_t



(n)=

t≤l−1

x^t u

(i)·e_t^F(n). (5.10)

The comultiplication ofᏸ^kis given then by

∆_ᏸk:ᏸ^k →ᏸ^k⊗Rᏸ^{k, u}→

t≤l−1

x^t u

⊗e^F_t. (5.11)

Example5.4. Consider the Fibonacci sequence=(0,1,1,2,3,5, . . .). Clearly, is given by

⁽⁰⁾=0, ⁽¹⁾=1, ⁽ⁿ+2)=⁽ⁿ+1)+⁽ⁿ⁾ ∀n≥0, (5.12) that is,∈ᏸZwith initial vector(0,1)and elementary characteristic polynomialf (x)= x²−x−1∈Z[x]. By (5.11), one can easily calculate

∆ᏸZ(⁾=⊗Z(x ⁾+(x ⁾⊗Z−⊗Z^{. (5.13)} 5.4. TheR-bialgebra(ᏸ^kR ;g). Consider theR-bialgebraR[x;g]. Then᏿^kR^Nk0 R[x;g]^∗is anR-algebra with multiplication given by theHadamard product

∗g:᏿^k⊗R᏿^k →᏿^{k, u}⊗v→[n→u(n)v(n)], (5.14) and the unity

ηg:R →᏿^k, 1R→ n→1R

for everyn∈N^k0. (5.15)

By Propositions5.2and5.3,(ᏸ^kR ;g)R[x;g]^◦has the structure of anR-bialgebra with the coalgebra structure described inSection 5.3, the Hadamard product (5.14), and the unity (5.15).

5.5. The HopfR-algebra(ᏸR^k;p). Consider the HopfR-algebraR[x;p]. Then᏿^k R^Nk0R[x;p]^∗is anR-algebra with multiplication given by theHurwitz product

∗p:᏿^k⊗R᏿^k →᏿^k, u⊗v→

n→

t≤n

n t

u(t)v(n−t)

, (5.16)

and the unity

ηp:R →᏿^k, 1R→ n→δn,0

for everyn∈N^k0. (5.17)

By Propositions5.2and5.3,(ᏸR^k;p)R[x;p]^◦ has the structure of a HopfR-algebra with the coalgebra structure described inSection 5.3, the Hurwitz product (5.16), the unity (5.17), and the antipode

S_ᏸk:ᏸ^k →ᏸ^k, u→ i→(−1)ⁱu(i)

. (5.18)

Proposition5.5(see [14, Theorem 3]). Letuandvbe linearly recursive sequences overRof ordersm,nand with characteristic polynomialsf (x),g(x), respectively. Then (1) u∗gv is a linearly recursive sequence overR of orderm·nand characteristic

polynomialχ(Sf⊗Sg);

(2) u∗pv is a linearly recursive sequence overRof orderm·nand characteristic polynomialχ(Sf⊗En+Em⊗Sg).

Example5.6. LetR be any ring and let{xn}^∞n=0,{yn}^∞n=0∈᏿Rbe solutions of the difference equations

xn+3−xn+2+xn−1−xn=0; x0=0, x1=1, x2=2;

y_n+2−y_n+1+yn=0; y0=1, y1=0. (5.19) Then{xn}^∞_n=0is a linearly recursive sequence over R with characteristic polynomial f (x)=x³−x²+x−1 and{yn}^∞_n=0is a linearly recursive sequence overRwith charac- teristic polynomialg(x)=x²−x+1.

Notice that

Sf⊗Sg=







0 0 1

1 0 −1

0 1 1





⊗

0 −1

1 1

=













0 0 0 0 0 −1

0 0 0 0 1 1

0 −1 0 0 0 1

1 1 0 0 −1 −1

0 0 0 −1 0 −1

0 0 1 1 1 1











 .

(5.20)

Hence, {zn}^∞n=0 := {xn}^∞n=0∗g{yn}^∞n=0 is by Proposition 5.5 a linearly recursive se- quence overRwith characteristic polynomial

χ Sf⊗Sg

=x⁶−x⁵+x³−x+1, (5.21)

that is,{zn}^∞n=0is a solution of the difference equation

zn+6−zn+5+zn+3−zn+1+zn=0 with initial vector(0,0,−2,−1,0,1). (5.22) Table 5.1gives the first 11 terms of the sequence{zn}^∞n=0.

Table5.1

n 0 1 2 3 4 5 6 7 8 9 10

xn 0 1 2 1 0 1 2 1 0 1 2

yn 1 0 −1 −1 0 1 1 0 −1 −1 0

zn 0 0 −2 −1 0 1 2 0 0 −1 0

Example5.7. Consider the sequences{xn}^∞n=0and{yn}^∞n=0ofExample 5.6. Then

Sf⊗E2+E3⊗Sg=













0 −1 0 0 1 0

1 1 0 0 0 1

1 0 0 −1 −1 0

0 1 1 1 0 −1

0 0 1 0 1 −1

0 0 0 1 1 2













. (5.23)

ByProposition 5.5,{zn}^∞n=0= {xn}^∞n=0∗p{yn}^∞n=0:= {n j=0

_n

j

xj·y_n−j}^∞n=0is a linearly recursive sequence overRwith characteristic polynomial

χ

Sf⊗E2+E3⊗Sg

=x⁶−5x⁵+14x⁴−25x³+28x²−15x+3. (5.24) Hence,{zn}^∞n=0is a solution of the difference equation

zn+6−5zn+5+14zn+4−25zn+3+28zn+2−15zn+1+3zn=0 (5.25) with initial vector(0,1,2,−2,−16,−29).

Table 5.2gives the first 9 terms of the sequence{zn}^∞_n=0. Table5.2

n 0 1 2 3 4 5 6 7 8

xn 0 1 2 1 0 1 2 1 0

yn 1 0 −1 −1 0 1 1 0 −1

zn 0 1 2 −2 −16 −29 −12 29 0

5.6. Cofree comodules. Let C be an R-coalgebra. A right C-comodule (M, M) is calledcofreeif there exists anR-moduleKsuch that(M, M)(K⊗RC, idK⊗∆C)as rightC-comodules. Note that ifKR^(Λ), a freeR-module, thenMR^(Λ)⊗RCC^(Λ)as rightC-comodules (this is one reason for the terminologycofree).

As a direct consequence ofLemma 4.6, we get the following corollary.

Corollary5.8. LetMbe anR[x]-module. Then there are isomorphisms ofR[x]^◦- comodules

ᏸ^kM^∗M[x]^◦M^∗⊗RR[x]^◦M^∗⊗Rᏸ^kR . (5.26) In particular,M[x]^◦(ᏸM^k∗) is a cofreeR[x]^◦-comodule (ᏸR^k-comodule).

6. Linearly (bi)recursive bisequences. In this section, we consider thelinearly(bi)re- cursivek-bisequencesand thereversiblek-sequencesoverR-modules, whereRis an ar- bitrary commutative ground ring. We generalize the results of [16,17] concerning the bialgebra structure of the linearly recursive sequences over a base field to the case of arbitraryArtinianground rings.

6.1. LetM be anR-module,l=(l1, . . . , lk)∈N^k0, and consider the system of linear bidifference equations (SLBE):

x_z+(l1,0,...,0)+

l1

i=1

p(1,l₁−i)(z)x_z+(l1−i,0,...,0)=g1(z),

x_z+(0,l2,0,...,0)+

l₂

i=1

p(2,l₂−i)(z)x_z+(0,l2−i,0,...,0)=g2(z), ...

xz+(0,...,0,lk)+

l_k

i=1

p(k,l_k−i)(z)xz+(0,...,0,lk−i)=gk(z),

(6.1)

where thepjl’s areR-valued functions and thegj’s areM-valued functions defined for allz∈Z^k. If thegj’s are identically zero, then (6.1) is said to be ahomogenousSLBE.

If thepjl’s are constants, then (6.1) is said to be an SLBEwith constant coefficients.

6.2. Bisequences. For anR-moduleMandk≥0, let

᏿M^k:=

ν:Z^k →M

M^Zk (6.2)

be the R-module of k-bisequences over M. IfM (resp.,k) is not mentioned, then we meanM=R(resp.,k=1). Forw∈᏿M^kandf (x)=

iaixⁱ∈R[x,x⁻¹], define f (x) w=ν∈᏿M^k, whereν(z) :=

i

aiw(z+i)∀z∈Z^k. (6.3)

With this action,᏿^kM becomes anR[x,x⁻¹]-module. For subsetsI⊂R[x,x⁻¹]andY ⊂

᏿M^k, consider

An_᏿k M (I)=

w∈᏿M^k|g w=0 for everyg∈I , An_R[x,x−1](Y )=

h∈R x,x⁻¹

|h ν=0 for everyν∈Y

. (6.4)

Obviously, An_᏿k

M (I)⊂᏿^kM is anR[x,x⁻¹]-submodule and AnR[x,x−1](Y ) R[x,x⁻¹]is an ideal.

Definition 6.1. Let M be anR-module. We call w∈᏿M^k a linearly recursive k- bisequence(resp., alinearly birecursivek-bisequence) if AnR[x]( w)is a monic ideal (resp., a reversible ideal). Note that ak-bisequenceu∈᏿M^kis linearly recursive if and only if it is a solution of a homogenous SLBE with constant coefficients of the form (6.1).

The subsetsᏸ^kM ⊆᏿^kM of linearly recursivek-bisequences andᏮ^kM ⊆᏿^kM of linearly birecursivek-bisequences overMare obviouslyR[x,x⁻¹]-submodules.

7. Reversible sequences over modules

7.1. LetM be anR-module. Ak-bisequenceu is said to be areverseofu∈᏿M^k if

u|_N^k

0 =uand AnR[x](u) =AnR[x](u). A linearly recursivek-sequenceuwill be called reversibleifuhas a reverseu∈ᏸ^kM . With᏾^kM ⊂ᏸ^kM , we denote theR[x]-submodule of reversiblek-sequences overM.

Lemma7.1(cf. [16, Proposition 14.11]). LetRbeArtinian.

(1)Every monic idealI R[x]contains a subset of monic polynomials x_j^djqj

xj

|qj xj

is reversible forj=1, . . . , k

. (7.1)

(2)LetMbe anR-module. Then every linearly recursivek-bisequence overMis linearly birecursive (i.e.,Ꮾ^kM =ᏸ^kM ).

Proof. (1) By [5, Theorem 8.7] every commutative Artinian ring is (up to isomor- phism) a direct sum of local Artinian rings. Without loss of generality, letRbe a local Artinian ring. The Jacobson radical ofR,

J(R)= {r∈R|ris not invertible inR}, (7.2) is nilpotent, hence there exists a positive integern such that J(R)ⁿ =0. LetI be a monic ideal with a subset of monic polynomials{g1(x1), . . . , gk(xk)} ⊂I. Ifgj(xj)≡ fj(xj)(modJ(R)[xj])for j =1, . . . , k, thengj(xj)|fj(xj)ⁿ, where nis the index of nilpotency of the idealJ(R). Hence,fj(xj)ⁿ∈I. If we writefj(xj)ⁿ=x_j^djqj(xj)with (xj, qj(xj))=1, thenqj(0)∈U (R), that is,qj(xj)is a reversible polynomial forj= 1, . . . , k.

(2) Let u be a linearly recursivek-bisequence overM. IfR is Artinian, then by (1) AnR[x](u) contains a subset of monic polynomials{x_j^djqj(xj)|qj(xj)is reversible for j=1, . . . , k}. Then for everyz∈Z^k, we have(qj(xj) u)(z 1, . . . , zj, . . . , zk)=(x_j^djqj(xj) u)(z 1, . . . , zj−dj, . . . , zk) = 0. Hence, {qj(xj) | i= 1, . . . , k} ⊂ AnR[x](u), that is, AnR[x](u) is a reversible ideal.

7.2. Backsolving. LetMbe anR-module. Letube a linearly recursive sequence over Mand assume that AnR[x](u)contains some monic polynomial of the formx^dq(x)= x^d(a0+a1x+···+a_l−1x^l−1+x^l),a0∈U (R). Then

a0u(j+d)+a1u(j+d+1)+···+a_l−1u(j+d+l−1)+u(j+d+l)=0 ∀j≥0 (7.3) and we get bybacksolvingauniquelinearly birecursive bisequence u∈An_᏿M(q(x)) withu(n) =u(n)for alln≥d. In case l=0, The bisequenceu≡0 and is given for l≠0 by

u(z):=





u(z), z≥d,

−a⁻₀¹

a1u(z +1)+···+a_l−1u(z +l−1)+u(z +l)

, z < d. (7.4) If there are two bisequencesv, w∈An_᏿

M(q(x))withv(n) =u(n)=w(n)for alln≥d, then one can easily show by backsolving usingq(x)thatv=w. Moreover, we claim that