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
3ShiftEquivalenceofC- niteSequences
WenowintroduceanalgorithmforsolvingtheshiftequivalenceproblemfortwoC- nitesequences.ThealgorithmfortheP- nitecasecallsthisalgorithmasasubroutine.Letf1,f2:→kbeC- nitesequences,andsupposethatL1,L2∈k[E]aregivenwithL1·f1=L2·g2=0.Wewanttodeterminealls∈suchthatf1=Es·f2.Lemma1Letf1,f2:→kbeannihilatedbyL1,L2∈k[E],respectively.
1.Foralls∈andallL∈k[E],wehaveL·f1=0ifandonlyifL·(Es·f1)=0.
2.Ifthereexistssomes∈
gcd(L1,L2).
Proof.
1.Lets∈withf1=Es·f2,thenL·f1=L·f2=0forL:=andL=l0+l1E+···+lrEr∈k[E].Then
L·f1=0 n∈:l0f1(n)+l1f1(n+1)+···+lrf1(n+r)=0
n∈:l0f1(n+s)+l1f1(n+s+1)+···+lrf1(n+s+r)=0
n∈:l0(Esf1)(n)+l1(Esf1)(n+1)+···+lr(Esf1)(n+r)=0
L·(Es·f1)=0.
2.Lets∈besuchthatf1=Esf2.Then,bypart1,L2·f1=0.Byassumption,L1·f1=0,hence(SL1+TL2)·f1=0foranyS,T∈k[E].AsitispossibletochooseS,TsuchthatSL1+TL2=L,itfollowsthatL·f1=0.Forthesamereason,L·f2=0.
Inordertosolvetheshiftequivalenceproblemforf1,f2,putingL=gcd(L1,L2),weneedtocheckwhetherL·f1=0andL·f2=0,whichispossiblebyProp.2.IfoneorbothofthetwosequencesisnotannihilatedbyL,thenthereisnosolutiontotheshiftequivalenceproblem,andwereturntheemptyset.Otherwise,weproceedasdescribedintheremainderofthissection.Fromnowon,wemayassumethatL∈k[E]monicwithL·f1=L·f2=0isgiven.
3.1ReductiontoaMatrixEquation
Letr=deg(L)andletC∈kr×rbethecompanionmatrixofL.Writing
f1(n)f2(n) f1(n+1) f2(n+1) F1(n):= andF(n):= ..2.. ..
f1(n+r 1)f2(n+r 1)
theelectronicjournalofcombinatorics13(2006),#R00 , 6