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
4
5
6whileifr:=r 1else//nowvr=0
ifreturn
10
11r=1then{s∈:ur/vr=αs}s:=α(ur 1/ur vr 1/vr)
ifu=Jsvthen{s}else
ThecorrectnessofAlgorithms1and2shouldbeclearbytheabovediscussion.Severalrestrictions,however,havetobemadeforthe eldkinorderthateverystepinthesealgorithmscanbecarriedoutalgorithmically.Ofcourse,itisnecessarythatkisacom-putable,i.e.,thateveryelementhasa niterepresentation,thatthearithmeticoperations+, ,·,/arecomputable,andthatzeroequivalencecanbedecided.Furthermore,forthecomputationofaJordandecomposition(Line2inAlg.1),weneedtobeabletocompute¯alsohasabsolutefactorizationsofunivariatepolynomialsink[X].Thealgebraicclosurek
tobeacomputable eld.Line11ofAlgorithm2requirestodecidewhetheranelement¯isaninteger.Alltheserequirementscanbeaccommodatedformost eldskthatofk
mightbeofinterest.Morerestrictiveisthe nalrequirement,originatingfromline9:We¯.Analgorithmhavetobeabletocomputetheset{s∈:a=bs}forgivena,b∈k
forthispurposewasgivenbyAbramovandBronstein[1].Thisalgorithmisapplicablewheneverkissuchthatitcanbedecidedforanygivenx∈kwhetherxistranscendentaloralgebraicover,andthatforanytwoelementsx,y∈kitcanbedecidedwhethertheseelementsarealgebraicallyindependentover.Ge’salgorithm[8]givesrisetoane cientalternativeifkisasinglealgebraicextensionof,i.e.,ifk=(α)forsomealgebraicnumberα.
3.3Summary
Lemma2reducestheshiftequivalenceproblemforC- nitesequencetosolvingamatrixequation,andthismatrixequationcanbesolvedbymeansofAlgorithm1.Puttingthingstogether,wethusobtainthefollowingalgorithmforsolvingtheshiftequivalenceproblemforC- nitesequences.
Algorithm3
INPUT:f1,f2:→kC- nite,speci edbyannihilatingoperatorsL1,L2∈k[E]andinitialvalues
OUTPUT:alls∈suchthatf1=Esf2
1function
L·f1=0orreturn