Équation P-récursive - P-recursive equation

En mathématiques, une équation P-récursive est une équation linéaire de séquences où les séquences de coefficients peuvent être représentées sous forme de polynômes . Les équations p-récursives sont des équations de récurrence linéaire (ou des relations de récurrence linéaire ou des équations de différence linéaire ) avec des coefficients polynomiaux . Ces équations jouent un rôle important dans différents domaines des mathématiques, notamment en combinatoire . Les suites qui sont solutions de ces équations sont dites holonomiques , P-récursives ou D-finies.

À partir de la fin des années 1980, les premiers algorithmes ont été développés pour trouver des solutions à ces équations. Sergei A. Abramov, Marko Petkovšek et Mark van Hoeij ont décrit des algorithmes pour trouver des solutions polynomiales, rationnelles, hypergéométriques et d'Alembertiennes.

Définition

Soit un corps de caractéristique zéro (par exemple ), des polynômes pour , une suite et une suite inconnue. L'équation${\textstyle \mathbb {K} }$${\textstyle \mathbb {K} =\mathbb {Q} }$${\textstyle p_{k}(n)\in \mathbb {K} [n]}$${\textstyle k=0,\dots ,r}$${\textstyle f\in \mathbb {K} ^{\mathbb {N} }}$${\textstyle y\in \mathbb {K} ^{\mathbb {N} }}$

est appelée une équation de récurrence linéaire avec des coefficients polynomiaux (toutes les équations de récurrence de cet article sont de cette forme). Si et sont tous deux non nuls, alors est appelé l'ordre de l'équation. Si est nul l'équation est dite homogène, sinon elle est dite inhomogène. ${\textstyle p_{0}}$${\textstyle p_{r}}$${\textstyle r}$${\textstyle f}$

Cela peut également être écrit comme où est un opérateur de récurrence linéaire avec des coefficients polynomiaux et est l'opérateur de décalage, c'est-à-dire . ${\textstyle Ly=f}$${\textstyle L=\sum _{k=0}^{r}p_{k}N^{k}}$${\styletexte N}$${\textstyle N\,y(n)=y(n+1)}$

Solutions sous forme fermée

Soit ou de manière équivalente une équation de récurrence à coefficients polynomiaux. Il existe plusieurs algorithmes qui calculent les solutions de cette équation. Ces algorithmes peuvent calculer des solutions polynomiales, rationnelles, hypergéométriques et d'Alembertiennes. La solution d'une équation homogène est donnée par le noyau de l'opérateur de récurrence linéaire : . En tant que sous-espace de l'espace des séquences, ce noyau a une base . Soit une base de , alors la somme formelle des constantes arbitraires est appelée la solution générale du problème homogène . Si est une solution particulière de , c'est-à-dire , alors est également une solution du problème inhomogène et on l'appelle la solution générale du problème inhomogène. ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$${\textstyle Ly=f}$${\textstyle \ker L=\{y\in \mathbb {K} ^{\mathbb {N} }\,:\,Ly=0\}}$${\textstyle \{y^{(1)},y^{(2)},\dots ,y^{(m)}\}}$${\textstyle \ker L}$${\textstyle c_{1}a^{(1)}+\dots +c_{m}a^{(m)}}$${\textstyle c_{1},\dots ,c_{m}\in \mathbb {K} }$${\textstyle Ly=0}$${\textstyle {\tilde {y}}}$${\textstyle Ly=f}$${\textstyle L{\tilde {y}}=f}$${\textstyle c_{1}a^{(1)}+\dots +c_{m}a^{(m)}+{\tilde {y}}}$

Solutions polynomiales

À la fin des années 1980, Sergei A. Abramov a décrit un algorithme qui trouve la solution polynomiale générale d'une équation de récurrence, c'est -à- dire avec un membre de droite polynomial . Il (et quelques années plus tard Marko Petkovšek ) a donné un degré lié aux solutions polynomiales. De cette façon, le problème peut être simplement résolu en considérant un système d'équations linéaires . En 1995, Abramov, Bronstein et Petkovšek ont ​​montré que le cas polynomial peut être résolu plus efficacement en considérant la solution en série entière de l'équation de récurrence dans une base de puissance spécifique (c'est-à-dire pas la base ordinaire ). ${\textstyle y(n)\in \mathbb {K} [n]}$${\textstyle f(n)\in \mathbb {K} [n]}$${\textstyle (x^{n})_{n\in \mathbb {N} }}$

Les autres algorithmes pour trouver des solutions plus générales (par exemple des solutions rationnelles ou hypergéométriques) reposent également sur des algorithmes qui calculent des solutions polynomiales.

Solutions rationnelles

En 1989, Sergei A. Abramov a montré qu'une solution rationnelle générale , c'est-à-dire , avec le membre de droite polynomial , peut être trouvée en utilisant la notion de dénominateur universel. Un dénominateur universel est un polynôme tel que le dénominateur de chaque solution rationnelle se divise . Abramov a montré comment ce dénominateur universel peut être calculé en utilisant uniquement le premier et le dernier coefficient polynôme et . La substitution de ce dénominateur universel au dénominateur inconnu de toutes les solutions rationnelles peut être trouvée en calculant toutes les solutions polynomiales d'une équation transformée. ${\textstyle y(n)\in \mathbb {K} (n)}$${\textstyle f(n)\in \mathbb {K} [n]}$${\textstyle u}$${\textstyle u}$${\textstyle p_{0}}$${\textstyle p_{r}}$${\style d'affichage y}$

Solution hypergéométrique

Une suite est dite hypergéométrique si le rapport de deux termes consécutifs est une fonction rationnelle dans , c'est- à -dire . C'est le cas si et seulement si la suite est la solution d'une équation de récurrence du premier ordre à coefficients polynomiaux. L'ensemble des suites hypergéométriques n'est pas un sous-espace de l'espace des suites car il n'est pas fermé par addition. ${\textstyle y(n)}$${\style d'affichage n}$${\textstyle y(n+1)/y(n)\in \mathbb {K} (n)}$

En 1992, Marko Petkovšek a donné un algorithme pour obtenir la solution hypergéométrique générale d'une équation de récurrence où le membre de droite est la somme des séquences hypergéométriques. L'algorithme utilise la forme normale de Gosper-Petkovšek d'une fonction rationnelle. Avec cette représentation spécifique, il suffit encore de considérer les solutions polynomiales d'une équation transformée. ${\style d'affichage f}$

Une approche différente et plus efficace est due à Mark van Hoeij. En considérant les racines du premier et du dernier polynôme à coefficients et – appelées singularités – on peut construire une solution étape par étape en utilisant le fait que chaque séquence hypergéométrique a une représentation de la forme${\textstyle p_{0}}$${\textstyle p_{r}}$${\textstyle y(n)}$

pour certains avec pour et . Dénote ici la fonction Gamma et la clôture algébrique du champ . Ensuite, les doivent être des singularités de l'équation (c'est-à-dire les racines de ou ). De plus, on peut calculer des bornes pour les exposants . Pour des valeurs fixes, il est possible de faire un ansatz qui donne des candidats pour . Pour un particulier, on peut à nouveau faire un ansatz pour obtenir la fonction rationnelle par l'algorithme d'Abramov. En considérant toutes les possibilités, on obtient la solution générale de l'équation de récurrence. ${\textstyle c\in \mathbb {K} ,z\in {\overline {\mathbb {K} }},s\in \mathbb {N} ,r(n)\in {\overline {\mathbb {K } }}(n),\xi _{1},\dots ,\xi _{s}\in {\overline {\mathbb {K} }}}$${\textstyle \xi _{i}-\xi _{j}\notin \mathbb {Z} }$${\textstyle i\neq j}$${\textstyle e_{1},\dots ,e_{s}\in \mathbb {Z} }$${\textstyle \Gamma (n)}$${\textstyle {\overline {\mathbb {K} }}}$${\textstyle \mathbb {K} }$${\textstyle \xi _{1},\dots ,\xi _{s}}$${\textstyle p_{0}}$${\textstyle p_{r}}$${\textstyle e_{i}}$${\textstyle \xi _{1},\dots ,\xi _{s},e_{1},\dots ,e_{s}}$${\styletexte z}$${\styletexte z}$${\styletexte r(n)}$

Solutions d'Alembertian

Une suite est appelée d'Alembertian si pour certaines suites hypergéométriques et signifie que où désigne l'opérateur de différence, c'est-à-dire . C'est le cas si et seulement s'il existe des opérateurs de récurrence linéaire du premier ordre avec des coefficients rationnels tels que . ${\style d'affichage y}$${\textstyle y=h_{1}\sum h_{2}\sum \cdots \sum h_{k}}$${\textstyle h_{1},\dots ,h_{k}}$${\textstyle y=\somme x}$${\textstyle \Delta y=x}$${\textstyle \Delta }$${\textstyle \Delta y=Ny-y=y(n+1)-y(n)}$${\textstyle L_{1},\dots ,L_{k}}$${\textstyle L_{k}\cdots L_{1}y=0}$

1994 Abramov et Petkovšek décrivent un algorithme qui calcule la solution d'Alembertienne générale d'une équation de récurrence. Cet algorithme calcule des solutions hypergéométriques et réduit l'ordre de l'équation de récurrence de manière récursive.

Exemples

Matrices de permutation signées

Le nombre de matrices de

permutation signées de taille peut être décrit par la séquence . Une matrice de permutation signée est une matrice carrée qui a exactement une entrée différente de zéro dans chaque ligne et dans chaque colonne. Les entrées différentes de zéro peuvent être . La séquence est déterminée par l'équation de récurrence linéaire avec des coefficients polynomiaux${\style d'affichage n\ fois n}$ ${\textstyle y(n)\in \mathbb {Q} ^{\mathbb {N} }}$${\textstyle \pm 1}$

$${\style d'affichage y(n)=4(n-1)^{2}\,y(n-2)+2\,y(n-1)}$$

et les valeurs initiales . En appliquant un algorithme pour trouver des solutions hypergéométriques, on peut trouver la solution hypergéométrique générale${\styletexte y(0)=1,y(1)=2}$

$${\displaystyle y(n)=c\,2^{n}n!}$$

pour une certaine constante . Compte tenu également des valeurs initiales, la séquence décrit le nombre de matrices de permutation signées. ${\textstyle c}$${\textstyle y(n)=2^{n}n !}$

Involutions

Le nombre d' involutions d'un ensemble avec des éléments est donné par l'équation de récurrence${\textstyle y(n)}$${\styletexte n}$

$${\style d'affichage y(n)=(n-1)\,y(n-2)+y(n-1).}$$

En appliquant par exemple l'algorithme de Petkovšek, il est possible de voir qu'il n'y a pas de solution polynomiale, rationnelle ou hypergéométrique pour cette équation de récurrence.

Applications

Une fonction est dite hypergéométrique si où désigne les fonctions rationnelles dans et . Une somme hypergéométrique est une somme finie de la forme où est hypergéométrique. L'algorithme de télescopage créatif de

Zeilberger peut transformer une telle somme hypergéométrique en une équation de récurrence avec des coefficients polynomiaux. Cette équation peut ensuite être résolue pour obtenir par exemple une combinaison linéaire de solutions hypergéométriques appelée solution de forme fermée de . ${\styletexte F(n,k)}$${\textstyle F(n,k+1)/F(n,k),F(n+1,k)/F(n,k)\in \mathbb {K} (n,k)}$${\textstyle \mathbb {K} (n,k)}$${\styletexte n}$${\textstyle k}$${\textstyle f(n)=\somme _{k}F(n,k)}$${\styletexte F(n,k)}$${\textstyle f}$

Les références

1. ^ Si les séquences sont considérées comme égales si elles sont égales dans presque tous les termes, alors cette base est finie. Vous trouverez plus d'informations à ce sujet dans le livre A=B de Petkovšek, Wilf et Zeilberger.
2. ^ Abramov, Sergueï A. (1989). « Problèmes de calcul formel liés à la recherche de solutions polynomiales d'équations différentielles et différentielles linéaires ». Mathématiques computationnelles et cybernétique de l'Université de Moscou . 3 .
3. ^ ^{un b} Petkovšek, Marko (1992). "Solutions hypergéométriques de récurrences linéaires à coefficients polynomiaux" . Journal de calcul symbolique . 14 (2-3): 243-264. doi : 10.1016/0747-7171(92)90038-6 . ISSN  0747-7171 .
4. ^ ^{A b c d} Petkovšek, Marko; Wilf, Herbert S.; Zeilberger, Doron (1996). A=B . AK Peters. ISBN 978-1568810638. OCLC  33898705 .
5. ^ Abramov, Sergueï A.; Bronstein, Manuel ; Petkovšek, Marko (1995). Sur les solutions polynomiales d'équations d'opérateurs linéaires . ISSAC '95 Actes du Symposium international de 1995 sur le calcul symbolique et algébrique . ACM. p. 290-296. CiteSeerX  10.1.1.46.9373 . doi : 10.1145/220346.220384 . ISBN 978-0897916998.
6. ^ Abramov, Sergueï A. (1989). « Solutions rationnelles d'équations différentielles et différentielles linéaires avec des coefficients polynomiaux ». URSS Mathématiques computationnelles et physique mathématique . 29 (6) : 7-12. doi : 10.1016/s0041-5553(89)80002-3 . ISSN  0041-5553 .
7. ^ van Hoeij, Marc (1999). "Singularités finies et solutions hypergéométriques d'équations de récurrence linéaire" . Journal d'algèbre pure et appliquée . 139 (1–3) : 109–131. doi : 10.1016/s0022-4049(99)00008-0 . ISSN  0022-4049 .
8. ^ Cluzeau, Thomas ; van Hoeij, Mark (2006). « Calcul des solutions hypergéométriques des équations de récurrence linéaire ». Algèbre applicable en ingénierie, communication et informatique . 17 (2) : 83-115. doi : 10.1007/s00200-005-0192-x . ISSN  0938-1279 .
9. ^ Abramov, Sergueï A.; Petkovšek, Marko (1994). Solutions d'alembertiennes des équations différentielles et aux différences linéaires . ISSAC '94 Actes du Symposium international sur le calcul symbolique et algébrique . ACM. p. 169-174. doi : 10.1145/190347.190412 . ISBN 978-0897916387.
10. ^ "A000165 - OEIS" . oeis.org . Récupéré le 02/07/2018 .