title: Algorithme d'Abramov
text: # Algorithme d'Abramov
  
  En mathématiques, en particulier en calcul formel, l'algorithme d'Abramov est un algorithme qui calcule toutes les solutions rationnelles d'une relation de récurrence linéaire à coefficients polynomiaux. L'algorithme a été publié par Sergei A. Abramov en $1989^,.$
  
  ## Dénominateur universel
  
  Le concept principal de l'algorithme d'Abramov est la notion de dénominateur universel. Soit $\mathbb {K}$ être un corps de caractéristique zéro. La dispersion $\operatorname {dis} (p,q)$ de deux polynômes $p,q\in \mathbb {K} [n]$ est par définition
  
      $\operatorname {dis} (p,q)=\max\{k\in \mathbb {N} \,:\,\deg(\operatorname {pgcd} (p(n),q(n+k)))\geq 1\}\cup \{-1\}$,
  
  où $\mathbb {N}$ désigne l'ensemble des entiers non négatifs. Ainsi, la dispersion est le plus grand entier $k\in \mathbb {N}$ tel que le polynôme $p$ et le polynôme $q$ décalé de $k$ ont un facteur commun. La dispersion est égale à $-1$ si un tel $k$ n'existe pas. La dispersion peut être calculée comme la plus grande racine entière non négative du résultant$\operatorname {res} _{n}(p(n),q(n+k))\in \mathbb {K} [k]$$^,.$
  
  Soit
  
      $\sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)$
  
  une relation de récurrence d'ordre $r$ à coefficients polynomiaux $p_{k}\in \mathbb {K} [n]$, avec $f\in \mathbb {K} [n]$ et soit $y(n)\in \mathbb {K} (n)$ une solution rationnelle. On pose $y(n)=p(n)/q(n)$ pour deux polynômes relativement premiers $p,q\in \mathbb {K} [n]$. Soit $D=\operatorname {dis} (p_{r}(n-r),p_{0}(n))$ et
  
      $u(n)=\operatorname {pgcd} ([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})$
  
  où
  
      $[p(n)]^{\underline {k}}=p(n)p(n-1)\cdots p(n-k+1)$
  
  désigne la factorielle décroissante d'une fonction. Alors $q(n)$ divise $u(n)$ . Par conséquent, le polynôme $u(n)$ peut être utilisé comme dénominateur pour toutes les solutions rationnelles $y(n)$ et c'est pourquoi on l'appelle un dénominateur universel.
  
  ## Algorithme
  
  Soit à nouveau
  
      $∑_{k=0}^rp_k(n)y(n+k)=f(n){\textstyle$ \sum _{k=0}^{r}p_{k}(n)\, y(n+k)=f(n)}
  
  une équation de récurrence à coefficients polynomiaux et soit u(n){\textstyle u(n)} un dénominateur universel. On pose y(n)=z(n)/u(n){\textstyle y(n)=z(n)/u(n)} pour un polynôme inconnu z(n)∈K[n]{\textstyle z(n)\in \mathbb {K} [n]} ; en notant
  
      ℓ(n)=ppcm⁡(u(n), …, u(n+r)){\textstyle \ell (n)=\operatorname {ppcm} (u(n), \dots , u(n+r))}
  
  l'équation de récurrence équivaut à
  
      $\sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n)$.
  
  Comme on peut simplifier par u(n+k){\textstyle u(n+k)}, on obtient une équation de récurrence linéaire avec des coefficients polynomiaux qui peut être résolue pour z(n){\textstyle z(n)}. Il existe des algorithmes pour trouver des solutions polynomiales. Les solutions pour z(n){\textstyle z(n)} peuvent ensuite être utilisées à nouveau pour calculer les solutions rationnelles y(n)=z(n)/u(n){\textstyle y(n)=z(n)/u(n)}.
  
  ## Exemple
  
  L'équation de récurrence homogène d'ordre 1{\textstyle 1}
  
      $(n-1)\,y(n)+(-n-1)\,y(n+1)=0$
  
  sur Q{\textstyle \mathbb {Q} } a une solution rationnelle. Elle peut être calculée en considérant la dispersion
  
      $D=\operatorname {dis} (p_{1}(n-1),p_{0}(n))=\operatorname {disp} (-n,n-1)=1$.
  
  Cela donne le dénominateur universel suivant:
  
      $u(n)=\operatorname {pgcd} ([p_{0}(n+1)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n$
  
  et
  
      $\ell (n)=\operatorname {ppcm} (u(n),u(n+1))=(n-1)n(n+1)$.
  
  En multipliant l'équation de récurrence d'origine par ℓ(n){\textstyle \ell (n)} et en posant y(n)=z(n)/u(n){\textstyle y(n)=z(n)/u(n)} on obtient :
  
      $(n-1)(n+1)\,z(n)+(-n-1)(n-1)\,z(n+1)=0$.
  
  Cette équation a la solution polynomiale
  
      z(n)=c{\textstyle z(n)=c}
  
  pour une constante arbitraire c∈Q{\textstyle c\in \mathbb {Q} }. En posant y(n)=z(n)/u(n){\textstyle y(n)=z(n)/u(n)} la solution rationnelle générale est
  
      $y(n)={\frac {c}{(n-1)n}}$
  
  pour un c∈Q{\textstyle c\in \mathbb {Q} } quelconque.
  
  