We present an algorithm which decides the shift equivalence problem for Pfinite sequences. A sequence is called P-finite if it satisfies a homogeneous linear recurrence equation with polynomial coefficients. Two sequences are called shift equivalent if shi
De nition4ForA=a0(n)+a1(n)E+···+ar(n)Er∈k(n)[E]ands∈k,wede ne
A(s)=a0(n+s)+a1(n+s)E+···+ar(n+s)Er.
Withthisde nition,wecanformulatethefollowinggeneralizationofLemma1.Lemma3Letf1,f2:→kbeannihilatedbyL1,L2∈k(n)[E],respectively.
1.Foralls∈andallL∈k(n)[E],wehaveL·f1=0ifandonlyifL(s)·(Es·f1)=0.
2.Ifthereexistssomes∈(s)gcrd(L1,L2).
Proof.
1.Lets∈withf1=Es·f2,thenL·f1=L·f2=0forL:=andL=l0(n)+l1(n)E+···+lr(n)Er∈k(n)[E].Then
L·f1=0 n∈
n∈
n∈:l0(n)f1(n)+···+lr(n)f1(n+r)=0:l0(n+s)f1(n+s)+···+lr(n+s)f1(n+s+r)=0
:l0(n+s)(Es·f1)(n)+···+lr(n+s)(Es·f1)(n+r)=0
L(s)·(Es·f1)=0.
2.Lets∈suchthatf1=Esf2.Then,bypart1,L2·f1=0.Byassumption,
(s)L1·f1=0,hence(SL1+TL2)·f1=0foranyS,T∈k(n)[E].Asitispossible
(s)tochooseS,T∈k(n)[E]suchthatSL1+TL2=L,itfollowsthatL·f1=0.For
thesamereason,L·f2=0. (s)
4.1ThedegenerateCase
LetL1,L2∈k(n)[E]begiven.Wemayextendtheground eldkbyanewtranscen-dentalelements,commutingwithE,andconsiderL1,L2aselementsofk(s)(n)[E],
(s)withcoe cientsfreeofs.InthissettingwecanformL2forsymbolicsandconsider(s)L:=gcrd(L1,L2).Itturnsoutthatthecoe cientsofLneithercontainsnorn:
Lemma4LetL1,L2∈k(n)[E].
1.deg(gcrd(L1,L2))>0forin nitelymanys∈ifandonlyifdeg(gcrd(L1,L2))>
(s)0whereL1,L2areviewedaselementsofk(s)(n)[E].(s)(s)
2.IfL1,L2tok[E].
Proof.(s)areviewedaselementsofk(s)(n)[E],thenL:=gcrd(L1,L2)belongs(s)
theelectronicjournalofcombinatorics13(2006),#R0012