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