Suites récurrentes linéaires¶
Cas binaire : LFSR¶
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,n, v[k] = -sum(i=1,d,v[k-d+i]*c[i]));
v;
}
linrec([1,0,0,1,0],[1,0,0,0,1],40)
linrec([1,1,1,1,1],[1,0,0,1,0],40)
Par exemple, quelle est la période de la suite d’annulateur \(x^6+x+1\) et commençant par \(1,0,1,0,1,0\) ?
En termes de \(k[x]\)-module¶
Soit \(k\) un corps. On munit l’espace \(\cU=k^\N\) des suites à valeurs dans \(k\) d’une structure de \(k[x]\)-module via l’opérateur de décalage
Pour toute suite \((u_n)\), on a un idéal annulateur
Une suite récurrente est alors une suite \((u_n)\) dont l’idéal annulateur est non-nul. Les éléments non nuls de \(I_u\) sont appelés des polynômes annulateurs de la suite, et le générateur unitaire de \(I_u\) est appelé polynôme minimal de la suite (il n’a aucune raison d’être irréductible). On appelle ordre de la suite le degré de son polynôme minimal.
Suites périodiques¶
Une suite est périodique de période \(l\geq 1\) si pour tout \(n\geq 0\), \(u_{n+l}=u_n\), c’est-à-dire que \({x^l}\cdot (u) = (u)\), de sorte que \(x^l-1\in I_u\). Ainsi
Proposition
Soit \((u)\) une suite récurrente de polynôme minimal \(P_u\). Alors \((u)\) est périodique de période \(l\) ssi \(P_u \mid x^l-1\).
Plus précisément, on a l’équivalence entre
la période de \((u)\) est exactement \(l\)
l’ordre de \(x\) modulo \(P_u(x)\) vaut \(l\).
Cas de Fq, suites maximales¶
Si \(k=\F_q\) est fini, toute suite récurrente est ultimement périodique.
Proposition
Soit \((u_n)\) une suite récurrente linéaire d’ordre \(d\) sur \(\F_q\). Alors \((u_n)\) est ultimement périodique de période \(l\leq q^d-1\).
Démonstration
Appelons état une suite de \(d\) valeurs \((u_k,\dots u_{k+d-1})\). Alors les valeurs ultérieures de la suite sont déterminées par un état ; sur \(\F_q\) il n’existe que \(q^d\) états différents. Par conséquent, on recroise un état en au plus \(q^d\) étapes. Si l’on met de côté l’état nul qui engendre la suite nulle, la période maximale est même majorée par \(q^d-1\).
On peut d’autre part exhiber des suites maximales
Proposition
Soit \(d\geq 2\). La période maximale d’une suite de degré \(d\) sur \(\F_q\) est \(l=q^d-1\), et il existe de telles suites, obtenues en prenant pour polynôme annulateur le minimal d’un élément générateur de \(\F_{q^d}^\times\).
Un tel polynôme est dit primitif. De manière équivalente, ce sont les facteurs irréductibles de \(\Phi_{q^d-1}(X)\) sur \(\F_q\), il y en a \(\frac{\phi(q^d-1)}{d}\).
On construit une suite de période 63 d’une des deux manières suivantes :
u = ffgen([2,6],'u) \\ générateur algébrique, ie F64 = F2[u] a = ffprimroot(u) \\ élément d'ordre 63 p = minpoly(a)
ou bien
f = factormod(polcyclo(63),2) \\ factorisation p = f[1,1] \\ premier facteur
linrec([1,0,1,0,1,0],x^6+x+1,70)
Calcul des termes¶
Pour calculer directement le \(n\)-ième terme de la suite, on peut utiliser l’exponentiation rapide. En effet, si le polynôme \(m(x)\) annule la suite \((u_n)\),
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 \(d\times d\) vérifié par ses coefficients.
sys_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];
));m;
}
sys_lin(['u1,'u2,'u3,'u4,'u5,'u6,'u7],4)
u = [2,3,5,7,11,13,17,19,23,29]; s = sys_lin(u,5); Polrev(matsolve(s,-Col(u[6..10])))+x^5
Remarque
Il y a une solution si la suite est bien de degré \(d\). Et dans ce cas il ne peut y en avoir plusieurs sinon la différence des deux polynômes obtenus serait un annulateur de degré inférieur, de sorte que le système est bien inversible.
En revanche si la suite est de degré inférieur le système peut ne pas être inversible, dans ce cas on peut résoudre en degré inférieur, ou mieux, considérer le polynôme non nul de plus petit degré dans le noyau du système homogène d’inconnues \(a_0,\dots a_d\).
Approximants de Padé¶
On peut faire plus efficace que le système linéaire en écrivant le problème différemment.
Soit \((u_n)\) une suite récurrente linéaire, on construit la série formelle
Soit \(P(x)=\sum_i c_ix^i\) un annuleur de \((u_n)\). On exprime l’annulation de la récurrence en terme de produit de séries formelle via le polynôme réciproque
On a alors
où \(r(x)\) est un polynôme de degré inférieur ou égal à \(d-1\).
Réciproquement, la théorie des approximants de Padé affirme que pour tout couple \(m,n\), et toute série \(g(x)\) telle que \(g(0)\neq 0\), il existe une unique fraction rationnelle
avec \(\deg v\leq m\) et \(\deg r\leq n\).
Il suffit de considérer le système du résultant.
En outre, déterminer cette solution peut se faire en résolvant un système linéaire (en complexité \((n+m)^3\)), ou bien via l’algorithme d’Euclide étendu en complexité quadratique.
Dans le cas qui nous intéresse, si \((u_n)\) est une suite récurrente linéaire d’ordre \(d\), le théorème affirme que l’approximant de Padé de niveau \((d-1,d)\) de \(g(x)\bmod x^{2d}\) est égal au couple \((r(x),\tilde P(x))\).
minimal(u,d) = {
my(x='x);
g = sum(k=0,2*d-1,u[k+1]*x^k)+O(x^(2*d));
rv = bestapprPade(g,d);
polrecip(denominator(rv));
}
minimal(linrec([1,1],x^2-x-1,4),2)
Théorème
Il existe deux polynômes \(v,r\) de degrés inférieurs à \(d\) et \(d-1\) tels que