Suites récurrentes linéaires, exemples¶
Définitions¶
Définition simple
Soit \(P(x)=\sum_{i=0}^d c_i x^i\) un polynôme, tel que \(c_d=1\). Alors pour tout \(d\)-uplet de valeurs initiales \(u_0,\dots u_{d-1}\) on définit une suite \((u_n)\) par la relation de récurrence
En d’autres termes, pour \(n\geq d\),
Ci-dessous, on calcule les \(n\) premiers termes de la suite \((u_n)\) dont \(c(x)\) est un annulateur. Par commodité, on peut entrer les premiers termes \(u_0,\dots u_{d-1}\) et le polynômes \(c_0,\dots c_d\) comme vecteur ou comme polynôme.
linrec(u0,c,n) = { if(type(c)=="t_POL",c=Vecrev(c)); d = #c - 1; if(type(u0)=="t_POL",u0=Vecrev(u,d)); v = Vec(u0,n); for(k=d+1,n, v[k] = -sum(i=0,d-1,v[k-d+i]*c[i+1])); v; }
Quelle sont les périodes des suites suivantes ?
linrec([1,0,0,1,0],[1,0,0,0,0,1],40)%2
linrec([1,1,1,1,1],[1,0,0,1,0,1],40)%2
Calculs¶
Construction¶
Proposition
Soit \((u)\) une suite récurrente de polynôme minimal \(P_u\). Alors \((u)\) est périodique de période \(\ell\) ssi \(P_u \mid x^\ell-1\). Plus précisément, on a l’équivalence
la période de \((u)\) est exactement \(\ell\)
l’ordre de \(x\) modulo \(P_u(x)\) vaut \(\ell\).
En particulier si \(P\) est le minimal d’un élément d’ordre \(l\) (ie si \(P\) divise le cyclotomique \(\Phi_l\)), alors \((u)\) a période \(l\).
Construire une suite récurrente de période 127.
En construire une de période \(5^{10}-1\).
Algorithme de résolution¶
Système linéaire¶
Si l’on connaît \(2d\) termes d’une suite de degré \(d\), on retrouve un polynôme annulateur en écrivant le système vérifié par ses coefficients
annul_lin(u,d) = { my(m=matrix(d,d)); for(i=1,d,for(j=1,i, m[j,i-j+1]=u[i]; m[d-j+1,d-i+j] = u[2*d-i]; )); Polrev(matsolve(m,-Col(u[d+1..d+d])))+x^d; }
annul_lin([1,1,2,3],2)
On peut procéder beaucoup plus efficacement, cf cours, mais cette technique élémentaire fournit déjà un algorithme polynomial.