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
Asinthecommutativecase,SandTcanbechosensuchthatdeg(S)≤deg(B)anddeg(T)≤deg(A).Li[16,17]hasshownthatthesubresultanttheoryfore cientcom-putationofgcdscanbegeneralizedtogcrdsink(n)[E]aswell.ThisgeneralizesearlierresultsofChardin[5]fordi erentialoperators.Weneedherethefollowingresultantcri-terion,whichisclassicforcommutativepolynomials,andwhichiscontainedinLi’sworkforskewpolynomials.
De nition3LetA,B∈k(n)[E],withcoe cients
A=a0(n)+a1(n)E+···+ar(n)Er,
Thenwecall
ar(n+s 1)0 ar 1(n+s 1)ar(n+s 2) . ..ar 1(n+s 2) .. . a0(n+s 1) 0a0(n+s 2) .... .. 0···B=b0(n)+b1(n)E+···+bs(n)Es. 0 . .. 0 bs(n) . .. ... b1(n) b0(n) ···.........0...0ar(n)bs(n+r 1)0···...............b1(n+r 1).ar 1(n)b0(n+r 1)........0............
0a0(n)0···....0..
theresultantofAandB(withrespecttoE),anddenotethevalueofthatdeterminantres(A,B).
TheresultantoftwooperatorsA,B∈k(n)[E]belongstok(n).Notethatnononcom-mutativearithmeticisrequiredforitscomputation.
Proposition1[17,Prop.9.1(1,2)]LetA,B∈k(n)[E]\k(n).Thenres(A,B)=0ifandonlyifdeg(gcrd(A,B))>0.
→k,thensoisALIfL∈k(n)[E]isanannihilatingoperatorofasequencef:
foranyA∈k(n)[E].Inparticular,bychoosinganappropriateA∈k(n),wecanalwaysreplaceLbyanequivalentoperatorwhosecoe cientsbelongtok[n]insteadofk(n).IfL∈k(n)[E]issuchanoperator,i.e.,
L=l0(n)+l1(n)E+···+lr(n)Er
withl0,...,lr∈k[n],thenfisuniquelyde nedbyLandsu cientlymanyinitialvalues.Thenumberofinitialvaluesnecessarytode nefisgivenbymax(0,n0)+r,wheren0isthegreatestintegerrootoflr.(Setn0:=0iflrdoesnothaveanyintegerroots.)Giventhisdata,manyquestionsaboutfcanbeansweredalgorithmically[23,18],inparticular,itcanbedecidedwhetheralreadyarightdivisorDofLannihilatesf.
theelectronicjournalofcombinatorics13(2006),#R004