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

\[\forall k\geq 0, \sum_{i=0}^d u_{k+i}c_i = 0.\]

En d’autres termes, pour \(n\geq d\),

\[u_n = - \sum_{i=0}^{d-1} c_iu_{n-d+i}\]

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.