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
2.fiscalledC- niteifthereexistconstantsa0,...,ar∈ksuchthat
a0f(n)+a1f(n+1)+···+arf(n+r)=0(n∈).
Inthissection,werecallsomeknownfactsaboutP- niteandC- nitesequencesthatwillbeneededinthesequel.
2.1AnnihilatingOperators
Letk(n)bethe eldofunivariaterationalfunctionsoverk,andletk(n)[E]betheunivariateskewpolynomialringoverk(n)withthecommutationrulesEn=(n+1)EandEc=cEforeachc∈k.ThisisaspecialinstanceofanOrering[20].Itactsontheringkofsequencesvia
((a0+a1E+···+arEr)·f)(n):=a0(n)f(n)+a1(n)f(n+1)+···+ar(n)f(n+r).Inviewofthisaction,wewillrefertotheelementsofk(n)[E]asoperators.Ifasequencef:→kisP- nite,thenthereexistsanoperatorL∈k(n)[E]suchthatL·f=0.Thesetofallsuchoperatorsformsaleftidealofk(n)[E],theannihilatingidealoff.OccasionallywewillallowalsonegativepowersofE,naturallyinterpretingthemasbackwardsshift.Fors<0,weunderstandthatthesequenceEs·fisde nedonlyforn> s,butweprefertosuppressthisdetailinordertokeepthenotationsimple.
Annihilatingoperatorsareheavilyusedinsymboliccomputationalgorithmsforspecialfunctions.Forathoroughaccountonannihilatingoperators,wereferto[26,6]andthereferencesgiventhere.
Wewritedeg(L)forthedegreeofL∈k(n)[E]withrespecttoE,i.e.,themaximumindexr∈suchthatthecoe cientofErinLisnonzero.Furtherwede nedeg(0):= ∞.Inviewoftheoperatorinterpretation,weshallusethewords“order”and“degree”assynonymsforthedegreeofskewpolynomials.
Weneedsomeelementaryfactsabouttheringk(n)[E].
De nition2LetA,B,D∈k(n)[E].IfthereexistA ,B ∈k(n)[E]suchthatA=A DandB=B DthenDiscalledacommonrightdivisorofAandB.IfDisacommonrightdivisorofmaximumdegree,thenDiscalledagreatestcommonrightdivisorofAandB,writtenD=gcrd(A,B).
ThegreatestcommonrightdivisoroftwooperatorsA,B∈k(n)[E]isuniquelyde-termineduptomultiplicationbyelementsoftheground eldk(n).ThemonicgreatestcommonrightdivisorofAandBiscalledthegreatestcommonrightdivisor(gcrd).Thegcrdofanytwospeci coperatorscanbecomputedbyamodi edversionoftheEuclideanalgorithm[4,Sect.3].Also,byamodi cationoftheextendedEuclideanalgorithm,onecancomputeforanyA,B∈k(n)[E]cofactoroperatorsS,Twith
SA+TB=gcrd(A,B).
theelectronicjournalofcombinatorics13(2006),#R003