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
resultbyrestrictingthefi(n)tosuchsequencesandassuminginadditionthatthesum-mandinvolvesthesesequencesonlypolynomially.Forthissituation,theyhaveobtainedacompletesummationalgorithm.
Thesolutiontotheshiftequivalenceproblemisasteptowardsallowingnontrivialdenominatorsinthesummandexpression.Theproblemis,fortwogivensequencestodecidewhetheroneofthemcanbematchedtotheotherbyshiftingitanappropriatenumberoftimes.Formally,givenf,g:→k,wewanttodeterminealls∈suchthat,forallpossiblen,f(n)=g(n+s).
Severalsummationalgorithmsincludeasubroutinefordecidingthisproblemforsomeclassesofsequences.Gosper’salgorithm[12,21]forinde nitehypergeometricsummationrequiressolvingtheshiftequivalenceproblemforunivariatepolynomials,i.e.,givenp,q∈
[n],todetermines∈withp(n)=q(n+s).Alsothecomputationofagreatestfactorialfactorisation(GFF)requiressolvingshiftequivalenceproblems[21,9,10].Theproblemcanbesolvedforpolynomialsbyobservingthatallpossiblesolutionssmustbeamongtheintegerrootsofthepolynomialresn(p(n),q(n+s))∈[s],soinordertosolvetheproblemitsu cestocheckallthoseroots.Alternativealgorithmsareavailable,wereferto[2,19,22]forfurtherinformationaboutthiscase.
Karr’salgorithm[14,15]forsimplifyingnestedsumandproductexpressionsalsoin-cludesanalgorithmfordecidingshiftequivalence.InKarr’salgorithm,sequencesarerepresentedaselementsofcertaintypesofdi erence elds(k,E)[7].Theshiftequiva-lencealgorithmis,roughlystated,basedon ndingtheorbitsinthemultiplicativegroup{E(f)/f:f∈k\{0}}.See[3,24]fordetails.
Inthepresentpaper,wepresentasolutiontotheshiftequivalenceproblemforse-quencesf,g:→kwhicharede nedbyhomogeneouslinearrecurrenceequationswithpolynomialcoe cients(P- nitesequences).Thisissu cientlygeneralforsolvingtheshiftequivalenceproblemsarisinginsummation.There,wearegivenmultivariatepoly-nomialsp1,p2andatupleofP- nitesequencesf1,...,frandwehavetosolvetheshiftequivalenceproblemforf(n):=p1(f1(n),...,fr(n))andg(n):=p2(f1(n),...,fr(n)).AsthesetofP- nitesequencesisclosedunderadditionandmultiplication[25],alsofandgareP- niteandrecurrenceequationsforthemcanbeobtainedalgorithmicallyfromp1,p2andrecurrenceequationsforf1,...,fr[23,18].
2P- niteandC- niteSequences
Inalltheoreticalstatementsmadeinthispaper,itisassumedthatkisanarbitrary eldofcharacteristic0.Forthealgorithms,however,itisnecessarytochoosethe eldksuchthatcertainproblemscanbesolvedink.TheseareexplainedattheendofSection3.2below.
De nition1[26]Letf:→kbeasequence.
1.fiscalledP- niteifthereexistpolynomialsa0,...,ar∈k[n]suchthat
a0(n)f(n)+a1(n)f(n+1)+···+ar(n)f(n+r)=0
theelectronicjournalofcombinatorics13(2006),#R00(n∈).2