Shift Equivalence of P-finite Sequences(4)

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库Shift Equivalence of P-finite Sequences(4)在线全文阅读。