Shift Equivalence of P-finite Sequences(13)

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

1.Considertheresultantres(L1,L2)∈k(s)(n).ByProp.1,anontrivialgcrdappearspreciselyforthosevaluesofswheretheresultantvanishes.Sincetheresultantisarationalfunctioninsovera eldofcharacteristiczero,itcanonlyhavein nitelymanyintegerrootsifitisidenticallyzero.Then,however,alreadythegcrdoverk(s)(n)mustbenontrivial,againbyProp.1.

2.SinceLisarightdivisorofL1andL1doesnotinvolves,alsoLisfreeofs.( s)(s)( s)Furthermore,wehavethatL( s)=gcrd(L1,(L2)( s))=gcrd(L1,L2)isarightdivisorofL2∈k(n)[E]andthereforeitisfreeofs,too.ButLandL( s)canbesimulaniouslyfreeofsonlyiftheyarealsofreeofn.

ThedegeneratecasehappensifL:=gcrd(L1,L2)(computedink(s)(n)[E])isalreadyanannihilatorforbothf1,f2.Inthiscase,thesequencesf1,f2areC- niteandwecanproceedwithAlgorithm3.(s)(s)

4.2ThenondegenerateCase

(s)ThenondegeneratecasehappensifL:=gcrd(L1,L2)(computedink(s)(n)[E])isnot

anannihilatoroff1,f2.Inthiscase,inviewofLemma3,part2,itisnecessaryforevery(s)solutions∈oftheshiftequivalenceproblemthatgcrd(L1/L,L2/L)isnontrivial.ByProp.1,thishappenspreciselyfortheintegerrootsof

res(rquo(L1,L),rquo(L2,L))∈k(s,n),

whererquo(A,B)denotestherightquotientofA∈k(s)(n)[E]byB∈k(s)(n).ByLemma4,itfollowsthattheresultantisnotidenticallyzero,forotherwiseLwouldnot(s)bethegreatestcommonrightdivisorofL1andL2.Thustheresultantcanonlyhave nitelymanyrootsintheintegers,andtheshiftequivalenceproblemcanbesolvedbytryingeachofthem.(s)Alternatively,thevaluessforwhichrquo(L1,L)andrquo(L2,L)haveanontrivialgreatestcommonrightdivisorcouldalsobeobtainedbyane cientalgorithmduetoGlotov[11].(s)

4.3Summary

Puttingthingstogether,weobtainthefollowingalgorithmforsolvingtheshiftequivalenceproblemforP- nitesequences.

Algorithm4

INPUT:f1,f2:→k,speci edbyannihilatingoperatorsL1,L2∈k(n)[E]andsu -cientlymanyinitialvalues.

OUTPUT:alls∈suchthatf1=Esf2

1function

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