iii. Le polynôme minimal $\rho_g$ de la multiplication par un polynôme $g$ de $R$ dans

$$E_Y := k(X_0, \dots, X_{r-1}, Y)[X_{r+1}, \dots, X_n]/I'_Y$$

a ses coefficients dans $A_{r-1}[Y]$, où $I'_Y$ représente l'extension de $I_Y$ dans

$$k(X_0, \dots, X_{r-1}, Y)[X_{r+1}, \dots, X_n];$$

iv. $R_Y/I_Y$ est un $A_{r-1}[Y]$-module sans torsion.

*Démonstration.* Supposons qu'il existe un polynôme $P$ non nul dans $A_{r-1}[T]$ tel que $P(f) \in I$, et choisissons $P$ de plus petit degré possible en $T$ avec cette propriété. On obtient alors $P(0) \in I + (f)$. La position de Noether de $I + (f)$ implique $P(0) = 0$. En posant $\hat{P}(T) = P(T)/T$, on déduit $\hat{P}(f)f \in I$, puis $\hat{P}(f) \in I$ puisque $f$ est non diviseur de 0 dans $B_r$. Ceci conduit à une contradiction avec le choix de $P$ de degré minimal en $T$, et achève la preuve de l'assertion (i).

La Proposition 27.9 et le Lemme 27.11 assurent que $\mu_f$ définit une relation entière pour $X_r$ sur $A_{r-1}[Y]$ modulo $I_Y$. Le Lemme 27.2 implique alors l'assertion (ii).

L'idéal $I_Y$ n'étant pas homogène en général, l'assertion (iii) ne découle pas de la Proposition 27.9. Il faut étendre légèrement les arguments utilisés. D'une part la première partie de la preuve du Théorème 26.5 s'adapte aisément pour montrer que $E_Y$ est une $k(X_0, \dots, X_{r-1}, Y)$-algèbre de dimension finie. Le polynôme minimal $\rho_g$ est ainsi bien défini.

Nous adaptons enfin le début de la preuve de la Proposition 27.9. Il existe un polynôme unitaire $Q \in A_{r-1}[Y][T]$ tel que $Q(g) \in I_Y$. Par le lemme de Gauss (Théorème 21.2) tous les facteurs irréductibles de $Q$ ont leurs coefficients dans $A_{r-1}[Y]$ et sont unitaires. Comme $\rho_g$ divise $Q$ dans $k(X_0, \dots, X_{r-1}, Y)[T]$ et qu'il est unitaire, $\rho_g$ a forcément ses coefficients dans $A_{r-1}[Y]$. Cela achève la preuve de (iii). Mentionnons que nous n'aurons pas besoin de borner les degrés des coefficients de $\rho_g$ dans la suite.

Examinons la torsion de $R_Y/I_Y$. Soient $a$ un polynôme non nul de $A_{r-1}[Y]$, et $g$ un polynôme de $A_{r-1}[Y, X_{r+1}, \dots, X_n]$ tels que $ag$ soit dans $I_Y$. On examine le résultant en $Y$ suivant :

$$b(X_0, \dots, X_r) = \mathrm{Res}_Y(a(X_0, \dots, X_{r-1}, Y), \mu_f(X_0, \dots, X_r, Y)).$$

D'une part $b$ appartient à $A_r$, et d'autre part la Proposition 6.7 assure l'existence de polynômes $U(X_0, \dots, X_r, Y)$ et $V(X_0, \dots, X_r, Y)$ tels qu'on ait la relation de Bézout

$$b(X_0, \dots, X_r) = U(X_0, \dots, X_r, Y)a(X_0, \dots, X_{r-1}, Y) + V(X_0, \dots, X_r, Y)\mu_f(X_0, \dots, X_r, Y).$$

Rappelons que $b$ est le déterminant de la matrice de Sylvester (Section 6.2) de $a$ et $\mu_f$ vus comme polynômes en la variable $Y$. Comme $a$ ne dépend pas de la variable $X_r$, comme $\mu_f$ est unitaire, homogène, et de coefficient constant $\mu_f(0)$ unitaire en $X_r$, un simple examen de cette matrice montre que le coefficient de plus haut degré en $X_r$ est proportionnel sur $k$ à $ct_Y(a)^{\deg \mu_f}$ (où $ct_Y(a)$ est le coefficient de tête de $a$ vu dans $A_{r-1}[Y]$). Par conséquent $b$ est non nul. En combinant $ag \in I_Y$ et $\mu_f(X_0, \dots, X_r, Y) \in I_Y$ avec la relation de Bézout, on obtient $bg \in I_Y$. En substituant $f$ à $Y$ et en utilisant l'absence de torsion de $B_r$, on déduit que $g(X_0, \dots, X_{r-1}, f)$ appartient à $I$ et donc que $g$ appartient à $I_Y$. ■
Nous arrivons maintenant à l'énoncé clé suivant, qui passe d'un module sans torsion à un suivant, obtenu en ajoutant un non diviseur de zéro à l'idéal :

**Proposition 27.13** Soit I un idéal homogène radical de dimension $r > 0$ en position de Noether, et soit $f$ un polynôme homogène de R qui n'est pas diviseur de zéro dans $B_r$ et tel que $I + (f)$ est en position de Noether. Si $B_r$ est un $A_r$-module sans torsion, alors le $A_{r-1}$-module $R/\sqrt{I + (f)}$ est sans torsion.

*Démonstration.* On a déjà vu dans la preuve du Lemme 27.11, que $I + (f)$ est de dimension $r - 1$. Soient $b \in R$ et $a \in k[X_0, \dots, X_{r-1}] \setminus \{0\}$ tels que $ab$ appartienne à $\sqrt{I + (f)}$. On veut montrer que $b$ appartient à $\sqrt{I + (f)}$. Il existe un entier $e$ tel que $(ab)^e$ appartienne à $I + (f)$. On note $g$ un polynôme tel que $a^e b^e - gf$ appartient à $I$.

On utilise maintenant le lemme précédent, avec les mêmes notations. Les polynômes minimaux des endomorphismes de multiplication par $g$ et par $b^e$ dans $E_Y$, notés respectivement $\rho_g(T)$ et $\rho_{b^e}(T)$, appartiennent à $A_{r-1}[Y][T]$. Écrivons $\rho_g(T) = T^m + \rho_{g,m-1} T^{m-1} + \dots + \rho_{g,0}$. Comme $a^e b^e - gY$ appartient à $I_Y$, et que $a^e$ et $Y$ sont dans $A_{r-1}[Y]$, le polynôme minimal $\rho_{b^e}(T)$ est

$$ \rho_{b^e}(T) = \left(\frac{Y}{a^e}\right)^m \rho_g\left(\frac{a^e T}{Y}\right) = T^m + \rho_{g,m-1} \frac{Y}{a^e} T^{m-1} + \dots + \rho_{g,0} \left(\frac{Y}{a^e}\right)^m $$

Par conséquent $a^j e$ divise $\rho_{g,m-j} Y^j$ et donc $\rho_{g,m-j}$ dans $k[X_0, \dots, X_{r-1}, Y]$, pour tout $j \in \{0, \dots, m-1\}$. L'assertion (iv) du lemme précédent assure que $\rho_{b^e}(b^e)$ appartient à $I_Y$. En substituant $Y$ par $f$, on en déduit que $b^{em}$ appartient à $I + (f)$, et ainsi $b \in \sqrt{I + (f)}$. ■

Nous pouvons enfin conclure.

*Fin de la démonstration du Théorème 27.10.* On commence par appliquer la proposition précédente avec $I = R$ et $f = f_1$. On obtient que $R/\sqrt{(f_1)}$ est un $A_{n-1}$-module sans torsion. On utilise ensuite à nouveau la proposition précédente avec $I = \sqrt{(f_1)}$ et $f = f_2$. Il s'ensuit que $R/\sqrt{\sqrt{(f_1)} + (f_2)}$ est un $A_{n-2}$-module sans torsion. Il est aisé de vérifier que $\sqrt{\sqrt{(f_1)} + (f_2)}$ coïncide avec $\sqrt{(f_1, f_2)}$. On continue de la même manière à prouver par récurrence que $R/\sqrt{(f_1, \dots, f_i)}$ n'a pas de $A_{n-i}$-torsion, jusqu'à $i = n - r$. ■

**Corollaire 27.14** Soit I un idéal homogène radical engendré par une suite régulièrligne $f_1, \dots, f_{n-r}$ en position de Noether simultanée, et soit $f$ un polynôme homogène non nul. Alors, le polynôme caractéristique $\chi_f$ et minimal $\mu_f$ de $f$ dans $E_r$ satisfont :

i. $\mu_f(f) = \chi_f(f) = 0$ dans $B_r$;

ii. $\mu_f(0) = 0$ si et seulement si $\chi_f(0) = 0$, si et seulement si $f$ divise zéro dans $B_r$.
**Démonstration.** La première assertion est une conséquence de la Proposition 27.9 et du Théorème 27.10. Pour la deuxième assertion, si $\mu_f(0) = 0$, alors on a $v_f(f)f = 0$ avec $v_f(T) = \mu_f(T)/T$ et $v_f(f) \neq 0$ dans $B_r$ (par minimalité de $\mu_f$). Par conséquent, $f$ est diviseur de zéro. Réciproquement, si $f$ est diviseur de zéro, alors il existe $g \in I$ tel que $fg \in I$. De $g\mu_f(f) \in I$ on déduit $\mu_f(0)g \in I$. L'absence de torsion implique $\mu_f(0) = 0$. Finalement, comme $\chi_f$ et $\mu_f$ ont les mêmes facteurs irréductibles, l'annulation de $\chi_f(0)$ est équivalente à celle de $\mu_f(0)$. ■

**Exemple 27.9** On considère l'idéal $I = (f_1, f_2)$ de l'Exemple 27.3. Comme $f_1$ est non nul, il n'est pas diviseur de zéro dans $R$. De plus, $(f_1)$ est bien en position de Noether puisque $f_1$ est unitaire en $X_3$. Une base de $R/(f_1)$ est $\{1, X_3\}$. Dans cette base, on peut calculer la matrice de multiplication par $f_2$ et obtenir ainsi le coefficient constant de son polynôme caractéristique :

$$ \chi_{f_2}(0) = X_2^4 + 2X_1^2X_2^2 - 2X_0^2X_2^2 + X_1^4 - 2X_0^2X_1^2 + X_0^4. $$

Par le corollaire précédent, on en déduit d'abord que $f_2$ n'est pas diviseur de zéro dans $R/(f_1)$. Ensuite, comme $\chi_{f_2}(0)$ est unitaire en $X_2$ à coefficients dans $k[X_0, X_1]$ et appartient à $I$, il s'ensuit que $I$ en position de Noether.

<figure><img src="image_78.png" /></figure>

Supposer I engendré par une suite régulière n'est pas une hypothèse habituelle. Il est plus naturel de considérer des idéaux I de dimension pure (unmixed enoglais), ce qui signifie que tous les premiers associés de I sont de même dimension. Ces considérations dépassent le cadre de cette partie, dont l'objectif se limite principalement à établir une preuve complète de l'algorithme de résolution géométrique du chapitre suivant.

## 27.4 Paramétrisation en dimension quelconque

Nous continuons de supposer I radical de dimension $r$ engendré par une suite régulière, et conservons les notations de la section précédente. Les calculs de polynômes minimaux servent à obtenir des paramétrisations par élément primitif de $I'$. Si $k$ est de caractéristique nulle ou bien $> \delta = \dim_K E_r$, alors on peut utiliser la Proposition 25.10 : pour tout $(\lambda_0 : \dots : \lambda_n)$ à l'extérieur d'une variété projective propre de $\mathbb{P}^n$, la forme linéaire $u = \lambda_{r+1}X_{r+1} + \dots + \lambda_nX_n$ est primitive pour $I'$. Le polynôme minimal $\mu_u$ de $u$ dans $E_r$ est homogène de degré total $\delta$. Nous montrons maintenant que les autres polynômes de la paramétrisation sous forme de Kronecker (Définition 25.5) ont aussi degré $\delta$.

Revenons à la construction des paramétrisations en dimension 0 de la Section 25.2. Il nous faut introduire les variables $\Lambda_{r+1}, \dots, \Lambda_n$, et les notations suivantes :

$$ \begin{align*} k_{\Lambda} &= k(\Lambda_{r+1}, \dots, \Lambda_n), \\ A_{\Lambda, r} &= k_{\Lambda}[X_0, \dots, X_r], \\ B_{\Lambda, r} &= R_{\Lambda, r}/I_{\Lambda}, \end{align*} $$

$$ \begin{align*} R_{\Lambda} &= k_{\Lambda}[X_0, \dots, X_n], \\ K_{\Lambda, r} &= k_{\Lambda}(X_0, \dots, X_r), \\ E_{\Lambda, r} &= K_{\Lambda, r}[X_{r+1}, \dots, X_n]/I_{\Lambda}' \end{align*} $$
où $I_Λ$ (resp. $I'_Λ$) représente l'extension de I dans $R_Λ$ (resp. dans $K_{Λ,r}[X_{r+1},...,X_n]$). En fait cette extension avec les $Λ_i$ ne change pas grand chose à la situation, comme précisé dans le lemme suivant :

**Lemme 27.15** Soit I un idéal homogène radical engendré par une suite régulière $f_1,...,f_{n-r}$ en position de Noether simultanée. On suppose $k$ de caractéristique nulle ou bien $> \delta = \dim_{K_r} E_r$. Alors on a

- la suite $f_1,...,f_n$ est régulière dans $R_Λ$;

- $I_Λ$ est radical;

- $\dim I_Λ = \dim I = r$, et $\deg I_Λ = \deg I$.

De plus, le polynôme minimal $\mu_{u_Λ}(T)$ de $u_Λ = \Lambda_{r+1}X_{r+1} + \cdots + \Lambda_nX_n$ dans $E_{Λ,r}$ satisfait les propriétés suivantes :

- $\mu_{u_Λ}(T)$ est un polynôme homogène sans carré de $K_Λ[X_0,...,X_{r-1},T]$ de degré total $\delta$;

- $\mu_{u_Λ}(T)$ appartient à $k[\Lambda_{r+1},...,\Lambda_n, X_0,...,X_r, T]$, et $\mu_{u_Λ}(u_Λ)$ appartient à l'extension $I^\Lambda$ de I à $R^\Lambda = k[\Lambda_{r+1},...,\Lambda_n, X_0,...,X_n]$.

*Démonstration.* Le fait que la suite $f_1,...,f_r$ est régulière dans $R_Λ$ provient du Corollaire 26.12. Puis le Lemme 25.14 assure que $I_Λ$ est radical. Pour la dimension et le degré de $I_Λ$, on peut soit utiliser le Corollaire 26.8, ou bien constater que I et $I_Λ$ ont mêmes bases standard (les calculs de base standard ne dépendent que du corps engendré par les coefficients des polynômes en entrée).

La Proposition 27.9 utilisée avec $K_Λ$ assure que $\mu_{u_Λ}$ est homogène en $X_0,...,X_r, T$, sans carré, et de degré total $\delta$. Pour la dernière assertion, on utilise le Corollaire 27.14, en voyant $f_1,...,f_{n-r}$ comme une suite régulière engendrant $I^\Lambda$: en effet il est aisé de vérifier que la position de Noether simultanée est conservée, et que $I^\Lambda$ est radical de dimension $n$. ■

**Théorème 27.16** Soit I un idéal homogène radical engendré par une suite régulière $f_1,...,f_{n-r}$ en position de Noether simultanée. On suppose $k$ de caractéristique nulle ou bien $> \delta = \dim_{K_r} E_r$. Soit $u = \lambda_{r+1}X_{r+1} + \cdots + \lambda_nX_n$ un élément primitif pour l'extension $I'$ de I dans $K_r[X_{r+1},...,X_n]$, et soit $q = \mu_u, w_{r+1},...,w_n$ les polynômes de la paramétrisation associée sous forme de Kronecker :

$$I' = (q(u),q'(u)X_{r+1} - w_{r+1}(u),...,q'(u)X_n - w_n(u)).$$

Alors, les polynômes $q, w_{r+1},...,w_n$ sont homogènes de degrés totaux $\delta$. De plus, on a l'inclusion

$$(q(u),q'(u)X_{r+1} - w_{r+1}(u),...,q'(u)X_n - w_n(u)) \subseteq I. \quad (27.4)$$

*Démonstration.* Tout d'abord, d'après le Corollaire 25.16, le polynôme minimal $\mu_u = q$ est la spécialisation en $\Lambda_{r+1} = \lambda_{r+1},...,\Lambda_n = \lambda_n$ du polynôme minimal $\mu_{u_\Lambda}$ de $u_\Lambda = \Lambda_{r+1}X_{r+1} + \cdots + \Lambda_nX_n$ de l'extension $I'_\Lambda$. Aussi, chaque polynôme $w_i$ est la spécialisation de $-\partial\mu_{u_\Lambda}/\partial\Lambda_i$. Le lemme précédent assure ainsi que $q, w_{r+1},...,w_n$ sont homogènes
de degrés totaux $\delta$. De plus ce lemme permet d'écrire $\mu_{u_\Lambda}(u_\Lambda)$ sous la forme

$$ \mu_{u_\Lambda}(u_\Lambda) = g_1 f_1 + \cdots + g_{n-r} f_{n-r}, $$

avec des $g_i$ dans $R^\Lambda$. Par conséquent $\frac{\partial \mu_{u_\Lambda}}{\partial T}(u_\Lambda)X_i + \frac{\partial \mu_{u_\Lambda}}{\partial \Lambda_i}(u_\Lambda)$ appartient aussi à $I^\Lambda$, pour tout $i$ de $r+1$ à $n$. On peut enfin spécialiser les variables $\Lambda_i$ sans risque, pour obtenir la dernière inclusion du théorème. ■

**Exemple 27.10** En général l'inclusion des idéaux (27.4) du théorème précédent est stricte, comme le montre l'exemple suivant. On prend $n=2$,

$$ f_1 = X_2^2 + X_1 X_2 + X_0^2, \quad f_2 = X_0 X_2 - X_1^2 + X_0 X_1. $$

Pour l'ordre 1 ex induit par $X_0 < X_1 < X_2$, une base standard est formée de $f_1, f_2$ et

$$ X_1^4 - X_0 X_1^3 + X_0^4, \quad X_1^2 X_2 + X_0^3. $$

Les monômes de tête sont donc $\{X_2^2, X_0X_2, X_1^2X_2, X_1^4\}$. On déduit de cette base la paramétrisation sous forme de Kronecker pour l'élément primitif $X_1$ :

$$ \begin{aligned} q(T) &= T^4 - X_0 T^3 + X_0^4, & w_1(T) &= q'(T)T \mod q(T) = X_0 T^3 - 4X_0^4, \\ w_2(T) &= -q'(T)T^{-2}X_0^3 \mod q(T) = -4X_0^3 T + 3X_0^4. \end{aligned} $$

Un nouveau calcul de base standard, pour l'idéal engendré par $q(X_1)$, $q'(X_1)X_1 - w_1(X_1)$ et $q'(X_1)X_2 - w_2(X_1)$, donne les monômes de tête assez différents

$$ \{X_1^4, X_1^3 X_2, X_0^2 X_1^2 X_2, X_0^4 X_1 X_2, X_0^6 X_2\}. $$

On en déduit par exemple que le polynôme $f_2$ n'est pas dans l'idéal.

## Interprétation géométrique

Revenons à l'interprétation géométrique de la position de Noether de la Proposition 27.4. Soit I un idéal homogène radical de dimension $r$. On note $\pi$ la projection de centre $V_{\bar{k}}(X_0, \dots, X_r)$ et de base $V_{\bar{k}}(X_{r+1}, \dots, X_n)$. Alors la restriction de $\pi$ à $V_{\bar{k}}(I)$ est bien définie et surjective. La question que nous abordons ici est le calcul d'une paramétrisation des points de $\pi^{-1}(a)$ pour un point $a$ donné.

**Proposition 27.17** Soit I un idéal homogène radical engendré par une suite régulièr $f_1, \dots, f_{n-r}$ en position de Noether simultanée. On suppose $k$ de caractéristique nulle ou bien $> \delta = \dim_{\bar{k}} E_r$. Considérons une paramétrisation sous forme de Kronecker $q, w_{r+1}, \dots, w_n$ de $I'$ pour un élément primitif $u = \lambda_{r+1} X_{r+1} + \cdots + \lambda_n X_n$. Soit $(a_0 : \cdots : a_r)$ un point de $\mathbb{P}^r$, et notons

$$ Q(T) := q(a_0, \dots, a_r, T), W_{r+1}(T) := w_{r+1}(a_0, \dots, a_r, T), \dots, W_n(T) := w_n(a_0, \dots, a_r, T). $$
Alors, il existe une variété projective propre Z de $\mathbb{P}^r$ telle que pour tout choix de $(a_0 : \cdots : a_r)$ à l'extérieur de Z on a les propriétés suivantes :

i. $I_a = I+(X_0-a_0, \dots, X_r-a_r)$ est un idéal non homogène radical de dimension 0;

ii. $Q, W_{r+1}, \dots, W_n$ forment une paramétrisation sous forme de Kronecker par l'élément primitif $u$ pour $I_a \cap k[X_{r+1}, \dots, X_n]$.

**Démonstration.** D'abord, on utilise l'inclusion des idéaux (27.4) du Théorème 27.16. Pour toute spécialisation $X_0 = a_0, \dots, X_r = a_r$, pour laquelle $Q$ est sans carré, on a

$$(Q(u), Q'(u)X_{r+1} - W_{r+1}(u), \dots, Q'(u)X_n - W_n(u)) \subseteq I_a,$$

ce qui implique que les puissances de $u$ forment une famille génératrice de $R/I_a$, et que $I_a$ est un idéal non homogène radical de dimension 0.

Ensuite, on considère l'inclusion dans l'autre sens. Pour tout $i$ de 1 à $n-r$, il existe des polynômes $h_{i,j}$ homogènes dans $R$, et un polynôme homogène non nul $b$ dans $A_r$ tels que

$$bf_i = h_{i,0}q(u) + \sum_{j=r+1}^{n} (q'(u)X_j - w_j(u))h_{i,j}.$$

Pour toute spécialisation $X_0 = a_0, \dots, X_r = a_r$ n'annulant pas $b$ on a donc l'inclusion en sens inverse

$$(Q(u), Q'(u)X_{r+1} - W_{r+1}(u), \dots, Q'(u)X_n - W_n(u)) \supseteq I_a.$$

Finalement, en notant $c$ le discriminant de $q$ en $T$ (qui est homogène) on peut prendre $V_{\bar{k}}(b) \cup V_{\bar{k}}(c)$ pour $Z$. ■

En dimension 0, on obtient le résultat intuitif suivant, disant que les situations affines et projectives de dimension 0 sont les mêmes.

**Corollaire 27.18** Soit I un idéal homogène radical engendré par une suite régulière $f_1, \dots, f_n$ en position de Noether simultanée. On suppose $k$ de caractéristique nulle ou bien $> \delta = \dim_{K_0} E_0$. Considérons une paramétrisation homogène $q, v_1, \dots, v_n$ de $I'$ pour un élément primitif $u = \lambda_1 X_1 + \dots + \lambda_n X_n$. Alors $V_{\bar{k}}(I)$ n'a aucun point à l'infini, et la spécialisation de la paramétrisation en $X_0 = 1$ est une paramétrisation de l'idéal non homogène $(I + (X_0 - 1)) \cap k[X_1, \dots, X_n]$.

**Démonstration.** L'absence de point à l'infini découle juste de la Proposition 27.4. Le reste est une conséquence de la proposition précédente. ■

À ce stade, étant donnée une paramétrisation de $I'$, la Proposition 27.17 fournit une paramétrisation de $\pi^{-1}(a_0, \dots, a_r)$ pour presque tout point $(a_0 : \cdots : a_r)$ de $\mathbb{P}^r$. Pour les autres points, il est aussi possible de décrire $\pi^{-1}(a_0, \dots, a_r)$ en utilisant le théorème suivant.

**Théorème 27.19** Soit I un idéal homogène radical engendré par une suite régulière $f_1, \dots, f_{n-r}$ en position de Noether simultanée. On suppose $k$ de caractéristique nulle ou bien $> \delta = \dim_K E_r$. Considérons donnée une paramétrisation
$q, w_{r+1}, \dots, w_n$ de $I'$ pour un élément primitif $u = \lambda_{r+1} X_{r+1} + \dots + \lambda_n X_n$. Alors, pour tout point $(a_0 : \dots : a_r)$ de $\mathbb{P}^r$ tel que $u$ est primitif pour l'idéal non homogène $I_a = \sqrt{I + (X_0 - a_0, \dots, X_r - a_r)}$, on note $\tilde{Q}(T) = q(a_0, \dots, a_r, T)$ et $\tilde{W}_i(T) = w_i(a_0, \dots, a_r, T)$, et on obtient :

— $P = \gcd(\tilde{Q}, \tilde{Q}')$ divise chaque $\tilde{W}_i(T)$,

— $Q = \tilde{Q}/\tilde{P}$, $W_i = (\tilde{W}_i/P)(\tilde{Q}'/P)^{-1}$ mod $Q$ pour $i$ de $r+1$ à $n$ forment une paramétrisation de $I_a \cap k[X_{r+1}, \dots, X_n]$.

Nous ne donnons pas la preuve de ce résultat, qui n'est pas utilisé par la suite, et renvoyons le lecteur aux notes ci-dessous pour une référence.

## Notes

Le point de vue utilisé dans ce chapitre pour la normalisation de Noether provient essentiellement de l'article de Giusti de 1988, qui décrit un algorithme de complexité polynomiale en $d^{n^2}$, où $d$ est le maximum des degrés des générateurs de l'idéal [Giu88]. Cet algorithme a ensuite été amélioré en collaboration avec Heintz [GH93] pour obtenir une complexité non uniforme polynomiale en $d^n$.

Lorsque le cardinal de $k$ est infini, ou en tout cas suffisamment grand, Giusti, Hägele, Lecerf, Marchand et Salvy ont implanté cet algorithme de normalisation, et ont analysé la probabilité de tirer au hasard un changement de variables qui met un idéal en position de Noether [Giu+00].

La mise en position de Noether est un ingrédient majeur de l'algorithme de résolution géométrique, présenté dans le chapitre suivant, et qui permet de résoudre des systèmes d'équations polynomiales sans calculer de bases standard. Les techniques de preuve de la Section 27.3, sur les paramétrisations des variétés projectives, sont issues de l'article de Durvye et Lecerf [DL07].

## Bibliographie

DL07 DURVYE, Clémence et Grégoire LECERF (2007). « A concise proof of the Kronecker polynomial system solver from scratch ». In : *Expositiones Mathematicae*, vol. 26, n°2, p. 101-139.

GH93 GIUSTI, Marc et Joos HEINTZ (1993). « La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial ». In : *Computational algebraic geometry and commutative algebra* (Cortona, 1991). Vol. XXXIV. Sympos. Math. Cambridge : Cambridge Univ. Press, p. 216-256.

Giu+00 GIUSTI, Marc, Klemens Hägele, Grégoire Lecerf, Joël Marchand et Bruno Salvy (2000). « The Projective Noether Maple package : computing the dimension of a projective variety ». In : *Journal of Symbolic Computation*, vol. 30, n°3, p. 291-307.

Giu88 GIUSTI, Marc (1988). « Combinatorial dimension theory of algebraic varieties ». In : *Journal of Symbolic Computation*, vol. 6, n°2-3. Special issue on Computational aspects of commutative algebra, p. 249-265.
# 28. Résolution géométrique

## Résumé

Dans ce chapitre nous présentons une version simplifiée de l'algorithmme de résolution géométrique, qui permet de résoudre efficacement une suite régulière réduite de polynômes homogènes à coefficients dans un corps de caractéristique zéro ou suffisamment grande. L'algorithmhe s'exprime simplement ; il repose sur les paramétrisations sous forme de Kronecker d'idéaux de dimensions quelconques présentées au chapitre précédent; il est indépendant de tout calcul de base standard et peut tirer parti d'un programme évaluant efficacement le système donné en entrée.

## 28.1 Introduction

Tout au long de ce chapitre le corps de base, noté $k$, est supposé être de caractéristique zéro ou suffisamment grande. Nous n'entrerons pas dans ces détails pour alléger la présentation. Le système à résoudre est noté $f_1 = \cdots = f_n = 0$, où $f_i$ est un polynôme homogène de $R = k[X_0, \dots, X_n]$ de degré total $d_i$. On suppose que $f_1, \dots, f_n$ forment une suite régulière (Définition 26.10), et que les idéaux intermédiaires $I_i = (f_1, \dots, f_i)$ sont radicaux, pour tout $i$ de 1 à $n$. On dit que $f_1, \dots, f_n$ forment une suite régulière réduite.

Sous ces hypothèses, nous décrivons ici l'algorithmme dit de *résolution géométrique*, qui résout un tel système de façon indépendante des méthodes par bases standard vues dans les chapitres précédents. En général, sur des problèmes concrets, l'algorithmme de résolution géométrique s'avère être asymptotiquement plus rapide que les méthodes par bases standard; la discussion est délicate à ce stade et reportée en fin de chapitre.

Une fois les positions de Noether acquises, à chaque idéal intermédiaire $I_i$ est associée son extension $I'_i$ dans l'anneau $K_{n-i}[X_{n-i+1}, \dots, X_n]$, avec $K_{n-i} = k(X_0, \dots, X_{n-i})$. Cette construction a été abordée en Section 27.3. Le Théorème 27.16 assure que $I'_i$
est un idéal radical non homogène de dimension zéro (dans le cadre affine de la Définition 25.2) et qu'une paramétrisation par un élément primitif linéaire homogène est possible avec de bonnes propriétés. En particulier, la fin de Section 27.4 explique en quoi une telle paramétrisation constitue une représentation de $V_k(I_i)$. Cette représentation est utilisée par l'algorithme pour représenter chaque $I'_i$. La résolution est effectuée de manière incrémentale, c'est-à-dire en ajoutant les équations une par une : l'algorithme calcule ainsi une paramétrisation pour $I'_1$, puis $I'_2$, $I'_3$, etc, jusqu'à $I'_n$.

Le reste de cette introduction est consacrée aux aspects probabilistes liés à l'algorithme, à quelques exemples montrant les objets manipulés en cours d'exécution, et aux structures de données utilisées pour représenter les polynômes en entrée. Dans la prochaine section nous décrivons les principales formules qui sont au cœur de l'approche incrémentale de résolution. Ensuite nous verrons comment rendre cette approche efficace : le principe méthodologique utilisé s'apparente aux méthodes par évaluation et interpolation du Chapitre 5, mais où les phases d'interpolation sont confiées à un opérateur de Newton.

## Aspects probabilistes

Sous les hypothèses décrites, la dimension de l'idéal intermédiaire $I_i$ est $n-i$, par le Corollaire 26.8. L'algorithme de résolution géométrique commence par choisir un changement linéaire de coordonnées qui met les idéaux intermédiaires $I_i$ en position de Noether simultanée (Définition 27.2). En pratique on peut choisir un tel changement de variables au hasard avec une très forte probabilité de succès grâce au Corollaire 27.7. Pour cette raison, l'algorithme de résolution géométrique est probabiliste. D'autres aspects probabilistes comme les choix d'éléments primitifs interviennent aussi.

Il est néanmoins légitime de se demander dès maintenant s'il est possible de garantir qu'un résultat calculé par l'algorithme de résolution est correct ou non. Une condition suffisante facile à tester fait l'objet du résultat suivant, que nous admettrons.

**Lemme 28.1** Soient $f_1, \dots, f_n$ des polynômes homogènes de R de degrés respectifs $d_1, \dots, d_n$. Considérons donnés une forme linéaire $u = \lambda_1 X_1 + \dots + \lambda_n X_n$ et des polynômes $q, v_1, \dots, v_n$ de $k(X_0)[T]$ tels que :

- $q$ est sans carré de degré $d_1 \cdots d_n$;

- pour tout $i$ de 1 à $n$, l'évaluation de $f_i(X_0, v_1(T), \dots, v_n(T))$ se réduit à 0 modulo $q(T)$;

- $J(X_0, v_1(T), \dots, v_n(T))$ est inversible modulo $q(T)$, où $J(X_0, X_1, \dots, X_n)$ représente le déterminant de la matrice jacobienne $\left(\frac{\partial f_i}{\partial X_j}\right)_{1 \le i \le n, 1 \le j \le n}$.

Alors, $I = (f_1, \dots, f_n)$ est en position de Noether, radical, de dimension 0, et les polynômes $q, v_1, \dots, v_n$ forment la paramétrisation de I par l'élément primitif $u$.

Le résultat calculé peut donc toujours être vérifié. Néanmoins, lorsque la vérification échoue, cela peut signifier que des mauvais choix ont été faits, ou bien que le système n'admet pas $d_1 \cdots d_n$ solutions distinctes. Ce second cas peut être conforté en multipliant le nombre d'exécutions de l'algorithme pour différents choix aléatoires. Nous
<figure><img src="image_79.png" /><figcaption>FIGURE 28.1 – Les quatre points d’intersection d’une sphère, d’un cylindre, et d’un plan, matérialisés par des petites sphères. Leurs projections orthogonales sur la droite portant les valeurs de l’élément primitif sont représentées par des petits tétraèdres.</figcaption></figure>

abordons très brièvement en fin de chapitre la question de certifier que $f_1, \dots, f_n$ n’est pas une suite régulière réduite.

Exemple

Jusqu’à la fin de cette section, nous utilisons l’exemple suivant, où $n = 3$.

**Exemple 28.1** On considère les polynômes

$$f_1 = X_1^2 + X_2^2 + X_3^2 - 2X_0^2, \quad f_2 = X_1^2 + X_2^2 - X_0^2, \quad f_3 = X_1 - 3X_2 + X_3.$$

Les solutions du système $f_1 = f_2 = f_3 = 0$, précisément $V_{\bar{k}}(I_3)$, sont particulièrement simples dans cet exemple et peuvent être explicitées :

$$V_{\bar{k}}(I_3) = \{(1:1:0:-1), (1:-1:0:1), (1:\frac{4}{5}:\frac{3}{5}:1), (1:-\frac{4}{5}:-\frac{3}{5}:-1)\}.$$

Cette variété n’a pas de point à l’infini, et sa partie affine est la variété affine $V_{\bar{k}}(I_3 + (X_0 - 1))$, présentée Figure 28.1.

L’algorithme de résolution présente $V_{\bar{k}}(I_3)$ sous la forme d’une paramétrisation
par élément primitif sous forme de Kronecker (Définition 25.5) :

$$ 
\begin{gather*}
u = X_1 + 2X_2 - 3X_3, \quad q(T) = T^4 - 17T^2X_0^2 + 16X_0^4 = 0, \\
X_1 = \frac{8}{5}X_0^2 \frac{4T^2 + 11X_0^2}{q'(T)}, \quad X_2 = -\frac{6}{5}X_0^2 \frac{T^2 - 16X_0^2}{q'(T)}, \quad X_3 = -10X_0^2 \frac{T^2 - 4X_0^2}{q'(T)}.
\end{gather*}
$$

Ainsi, en substituant $X_0$ par 1 dans cette paramétrisation, le polynôme $q(T)$ admet quatre racines complexes, et pour chacune d'entre elles, les coordonnées $X_1, X_2, X_3$ ne peuvent prendre qu'une valeur, donnée par les trois dernières équations de la paramétrisation. Le Corollaire 27.18 assure que les solutions du système sont toutes obtenues de cette manière.

Le polynôme $q(T)$ est ici le polynôme minimal de l'élément primitif $u$, c'est-à-dire que ses racines sont les valeurs que prend l'élément primitif en chacun des points de $V_k(I_3)$. Cette propriété est illustrée dans la Figure 28.1, qui montre la partie affine d'une droite orthogonale au plan d'équation $X_1 + 2X_2 - 3X_3 = 0$, ainsi que les projections orthogonales, distinctes, des points de $V_k(I_3)$ sur cette droite.

Pour parvenir à la paramétrisation de $I'_3$ ci-dessus, l'algorithme repose sur les paramétrisations par élément primitif de l'idéal $I'_1$ engendré par $f_1$ dans $k(X_0, X_1, X_2)[X_3]$, puis de l'idéal $I'_2$ engendré par $f_1, f_2$ dans $k(X_0, X_1)[X_2, X_3]$ et enfin de $I'_3$ l'extension de $I_3$ dans $k(X_0)[X_1, X_2, X_3]$.

**Exemple 28.2** Explicitement, ces paramétrisations intermédiaires sont

$$ 
\begin{array}{ll}
I'_1: & u = -3X_3, \\
\\
I'_2: & u = 2X_2 - 3X_3,
\end{array}
\quad
\left\{
\begin{aligned}
q(T) &= T^2 - 9(2X_0^2 + X_1^2 + X_2^2), \\
q'(T)X_3 &= 6(-2X_0^2 + X_1^2 + X_2^2), \\
q(T) &= T^4 - (26X_0^2 - 8X_1^2)T^2 + (5X_0^2 + 4X_1^2)^2, \\
q'(T)X_2 &= 8(X_0^2 - X_1^2)(T^2 + 5X_0^2 + 4X_1^2), \\
q'(T)X_3 &= -12X_0^2(T^2 - 5X_0^2 - 4X_1^2).
\end{aligned}
\right.
$$

Une première approche, calculant effectivement ces paramétrisations, est présentée en Section 28.2. Cependant, les paramétrisations faisant intervenir les variables libres deviennent rapidement grosses, et l'algorithme de résolution évite de les calculer. L'idée part de la Proposition 27.17, qui assure que pour presque toutes les valeurs $a_0, a_1$ et $a_2$ prises respectivement par les variables $X_0, X_1$ et $X_2$, les spécialisations de ces paramétrisations donnent des paramétrisations des variétés affines de dimension 0 des idéaux $I_1 + (X_0 - a_0, X_1 - a_1, X_2 - a_2)$ puis $I_2 + (X_0 - a_0, X_1 - a_1)$. L'algorithme principal, décrit en Section 28.4, prend donc en entrée un tel point $(a_0, a_1, a_2)$ et calcule juste ces spécialisations.

**Exemple 28.3** Avec le choix $(a_0, a_1, a_2) = (1, 1/2, 0)$, les calculs intermédiaires de
<figure><img src="image_80.png" /><figcaption>FIGURE 28.2 – Les paramétrisations de ($f_1, X_0 - 1, X_1 - 1/2, X_2$) et ($f_1, f_2, X_0 - 1, X_1 - 1/2$).</figcaption></figure>

l'algorithme produisent donc simplement

$$
\begin{align*}
I'_1 : u = -3X_3, \quad \begin{cases} q(T) = T^2 - \frac{63}{4}, \\ q'(T)X_3 = -\frac{21}{2}, \end{cases} & \qquad I'_2 : u = 2X_2 - 3X_3, \quad \begin{cases} q(T) = T^4 - 24T^2 + 36, \\ q'(T)X_2 = 6T^2 + 36, \\ q'(T)X_3 = -12T^2 - 72. \end{cases} \\
\\
I'_3 : u = X_1 + 2X_2 - 3X_3, & \quad \begin{cases} q(T) = T^4 - 17T^2 + 16 = 0, \\ q'(T)X_1 = \frac{8}{5}(4T^2 + 11), \\ q'(T)X_2 = -\frac{6}{5}(T^2 - 16), \\ q'(T)X_3 = -10(T^2 - 4). \end{cases}
\end{align*}
$$

Les variétés calculées lors de ces étapes intermédiaires sont données en Figure 28.2.

L'étape incrémentale permettant le passage d'une telle paramétrisation à la suivante nécessite de « dé-spécialiser » la dernière variable libre, ce qui est réalisé par une itération de Newton, décrite en Section 28.3.

**Exemple 28.4** À partir de la spécialisation de la paramétrisation de $I'_1$, l'algorithme de remontée obtient une paramétrisation de $I_1 + (X_1 - X_0/2)$, que l'on peut montrer être un idéal de dimension 1 : la partie affine de la variété correspondante est un cercle tracé sur la sphère dans la partie gauche de la Figure 28.2. Les points de $I_2 + (X_0 - 1, X_1 - 1/2)$ sont alors l'intersection de ce cercle avec le cylindre défini par la deuxième équation $f_2 = 0$. Pour continuer la résolution, l'algorithme remonte la variable $X_1$ pour obtenir une paramétrisation de $I_2$, dont la partie affine correspond aux deux cercles de l'intersection de la sphère et du cylindre dans la
partie droite de la Figure 28.2. Finalement les solutions du système $f_1 = f_2 = f_3 = 0$ sont l'intersection de ces deux cercles avec le plan d'équation $f_3 = 0$.

Structures de données pour les polynômes en entrée

Jusqu'ici dans les algorithmes de cette partie, les polynômes étaient donnés dans leur représentation dense, qui consiste à stocker le degré total et la liste de tous les coefficients (même nuls) des monômes de degrés plus petits. Par exemple, pour un polynôme homogène de degré $d$ en $n$ variables, on doit stocker $\binom{d+n}{n}$ coefficients. L'inconvénient de cette représentation est qu'elle oublie toute structure du calcul qui a mené à la construction du polynôme.

**Exemple 28.5** En mécanique il est fréquent que des normes de vecteurs interviennent dans les équations. Si $(p_1, p_2, p_3)$ est un vecteur dont les coordonnées sont des expressions polynomiales $p_i$, il est préférable de ne pas développer le carré de la norme $p_1^2 + p_2^2 + p_3^2$, afin de pouvoir évaluer numériquement cette norme pour une spécialisation donnée des variables.

Dans l'étude des équilibres chimiques, les équations provenant des lois d'action de masse possèdent très peu de monômes non nuls, et une représentation dense n'est pas bien adaptée pour évaluer ces équations.

Les méthodes de résolution numérique des systèmes polynomiaux, par subdivision, ou à l'aide de l'opérateur de Newton, passent l'essentiel de leur temps de calcul à évaluer les polynômes en entrée sur des valeurs numériques. Plus les polynômes s'évaluent bien, plus la résolution est rapide. La représentation dense n'est alors pas appropriée. D'une manière symbolique analogue, l'algorithme de résolution géométrique décrit dans ce chapitre passe aussi son temps à évaluer les équations en entrée en des points appartenant à des algèbres.

Afin de conserver leurs propriétés naturelles en terme d'évaluation, les polynômes $f_1, \dots, f_n$ en entrée de l'algorithme de résolution sont donnés sous forme de DAG, pour *Directed Acyclic Graph* en anglais et graphe orienté acyclique en français (Définition 12.1). Les nœuds du graphe sont binaires et représentent les opérations arithmétiques $(+, -, \times)$. Les feuilles (les nœuds sans arête sortante) sont des éléments de $k$ ou des variables $X_i$. Les nœuds sans parent sont les sorties du calcul représentant les polynômes $f_1, \dots, f_n$. La taille du graphe (nombre de nœuds) définit la *complexité d'évaluation* du calcul. Il s'agit du nombre d'opérations arithmétiques nécessaires pour évaluer les polynômes en entrée sur un point.

Notons que cette structure de donnée présente l'avantage de partager les sous-expressions communes, et permet ainsi d'éviter d'évaluer plusieurs fois une même expression sur des valeurs identiques.

**Exemple 28.6** Tout polynôme peut être représenté par un DAG. Par exemple, le schéma de Horner consiste à calculer $P = \sum_{i=0}^{d} a_i X^i$ par $P = ((a_d X + a_{d-1})X + a_{d-2})\cdots)X + a_0$. Il code tout polynôme à une variable de degré $d$ par un DAG de complexité d'évaluation en $O(d)$. À l'inverse, le polynôme $(X+1)^{2^d}$ se code
beaucoup mieux par le DAG (................((X + 1)²)²)²...² que par sa représentation sur la base monomiale.

**Définition 28.1** La complexité d'évaluation d'un polynôme est le minimum des complexités d'évaluation des DAG qui le représentent.

**Lemme 28.2** Un polynôme homogène de R de degré $d$ a une complexité d'évaluation $O((d+n)^n)$.

*Démonstration.* La borne correspond à l'évaluation du polynôme en utilisant naïvement sa représentation dense qui est justement de taille $\binom{n+d}{n}$.

**Exemple 28.7** Soit $M = (X_{i,j})$ la matrice générique carré de taille $n$ (c'est-à-dire que ses coefficients sont des variables distinctes). Alors le polynôme déterminant de $M$ se code mal par sa représentation sur la base monomiale car il a $n!$ monômes. Par contre, il se code en complexité d'évaluation $O(n^4)$ par l'algorithme de Berkowitz (Théorème 8.9). Cette exemple est important car il illustre que les polynômes d'élimination, dont le déterminant est un bon représentant, s'évaluent bien.

La complexité de l'algorithme de résolution géométrique s'exprime en terme du produit des degrés $d_i$ des polynômes $f_i$, du nombre de variables homogènes $n$, et de la complexité d'évaluation, notée $L$, du DAG utilisé pour représenter $f_1, \dots, f_n$.

Soulignons que pour obtenir une position de Noether, il suffit d'appliquer un changement de variables linéaire aux polynômes en entrée, ce qui augmente la complexité d'évaluation de $O(n^2)$, et reste négligeable sur le coût total de l'algorithme.

## 28.2 Approche incrémentale

L'algorithme développé dans ce chapitre procède de manière incrémentale, en ajoutant une nouvelle équation à chaque étape. Informellement, on résout d'abord l'équation $f_1 = 0$, puis le système $f_1 = f_2 = 0$, puis $f_1 = f_2 = f_3 = 0$, etc. Les ensembles de solutions sont représentés par éléments primitifs. Dans l'Exemple 28.2, l'étape incrémentale décrite dans cette section permet ainsi le calcul de la paramétrisation de $I'_2$ à partir de celle de $I'_1$.

### Hypothèses et notations

Jusqu'à la fin du chapitre nous travaillons sous les hypothèses suivantes :

(H₁) la suite $f_1, \dots, f_n$ est régulière;

(H₂) la suite $f_1, \dots, f_n$ est réduite, c'est-à-dire que chacun des idéaux $I_i$ est radical;

(H₃) la suite $f_1, \dots, f_n$ est en position de Noether simultanée (Définition 27.2).
Nous utilisons les notations suivantes, pour $i \in \{0, \dots, n\}$ :

$$ 
\begin{aligned}
r &= n - i, \\
A_r &= k[X_0, \dots, X_r], \\
B_r &= R/I_i,
\end{aligned}
 $$

$$ 
\begin{aligned}
I_i &= (f_1, \dots, f_i), \\
K_r &= k(X_0, \dots, X_r), \\
E_r &= K_r[X_{r+1}, \dots, X_n]/I_i'
\end{aligned}
 $$

où $I'_i$ représente l'extension de $I_i$ à $K_r[X_{r+1}, \dots, X_n]$.

## Entrée et sortie de l'étape

À l'étape *i* de la résolution, la paramétrisation de $I'_i$ sous forme de Kronecker est constituée de :

- l'élément primitif $u = \lambda_{r+1}X_{r+1} + \dots + \lambda_nX_n$;

- le polynôme minimal $q(T) \in A_r[T]$ de la multiplication par $u$ dans $E_r$;

- les polynômes $w_{r+1}, \dots, w_n$ de $A_r[T]$ tels que

$$ I'_i = (q(u), q'(u)X_{r+1} - w_{r+1}(u), \dots, q'(u)X_n - w_n(u)). $$

On note $v_j(T) = q'(T)^{-1}w_j(T)$ mod $q(T)$. En d'autres termes, l'application

$$ 
\begin{gathered}
E_r \to K_r[T]/(q(T)) \qquad (28.1) \\
X_j \mapsto v_j(T) \quad \text{pour } r+1 \le j \le n
\end{gathered}
 $$

est un isomorphisme de $K_r$-algèbres. En particulier le degré de $q$ est $\delta_i = \dim_{K_r} E_r$.

Comme $f_1, \dots, f_n$ forment une suite régulière, le Théorème 26.7 donne $\deg I_i = d_1 \cdots d_i$. Par ailleurs, le Théorème 26.5 assure que ce degré est également la dimension de $E_r$ :

$$ \delta_i = \deg I_i. \qquad (28.2) $$

On considère ensuite l'équation suivante $f_{i+1} = 0$. Le but de cette section est de décrire un algorithme qui calcule la paramétrisation par l'élément primitif $U = \lambda_r X_r + \dots + \lambda_n X_n$ de $I'_{i+1}$. Les polynômes de la nouvelle paramétrisation sous forme de Kronecker sont notés $Q, W_r, \dots, W_n$. Pour alléger les notations, l'indice *i* n'apparaît pas dans les paramétrisations : la paramétrisation de l'étape *i* est notée en minuscules, et celle de l'étape *i* + 1 en majuscules. (Le nombre de polynômes de la paramétrisation indique bien sûr l'idéal intermédiaire $I_i$ concerné).

## Élément primitif générique

Le calcul de la nouvelle paramétrisation est réalisé avec la technique de l'élément primitif « générique » de la Section 25.2. Nous introduisons donc les nouvelles variables $\Lambda_1, \dots, \Lambda_n$, et les notations suivantes :

$$ 
\begin{aligned}
k_{\Lambda} &= k(\Lambda_1, \dots, \Lambda_n), & R_{\Lambda} &= k_{\Lambda}[X_0, \dots, X_n], \\
A_{\Lambda, r} &= k_{\Lambda}[X_0, \dots, X_r], & K_{\Lambda, r} &= k_{\Lambda}(X_0, \dots, X_r), \\
B_{\Lambda, r} &= R_{\Lambda}/I_{\Lambda, i}, & E_{\Lambda, r} &= K_{\Lambda, r}[X_{r+1}, \dots, X_n]/I'_{\Lambda, i}
\end{aligned}
 $$

où $I_{\Lambda, i}$ (resp. $I'_{\Lambda, i}$) représente l'extension de $I_i$ dans $R_{\Lambda}$ (resp. dans $K_{\Lambda, r}[X_{r+1}, \dots, X_n]$). Aussi, on note $I_i^{\Lambda}$ l'extension de $I_i$ dans $R^{\Lambda} = k[\Lambda_1, \dots, \Lambda_n, X_0, \dots, X_n]$.

Cette extension avec les $\Lambda_i$ ne change pas grand chose à la situation, grâce au Lemme 27.15 qui montre les propriétés suivantes :
— la suite $f_1, \dots, f_n$ est régulière dans $\mathbb{R}_\Lambda$;

— $I_{\Lambda,i}$ est radical pour tout $i \in \{1, \dots, n\}$;

— pour tout $i \in \{1, \dots, n\}$, on a $\dim I_{\Lambda,i} = \dim I_i = r$, et $\deg I_{\Lambda,i} = \deg I_i = \delta_i = \dim_{\mathbb{K}_{\Lambda,r}} E_r$.

La paramétrisation de $I'_i$ est donc aussi une paramétrisation de $I'_{\Lambda,i}$ :

$$I'_{\Lambda,i} = (q(u), q'(u)X_{r+1} - w_{r+1}(u), \dots, q'(u)X_n - w_n(u)).$$

De façon équivalente, l'application

$$ \begin{gathered} E_{\Lambda,r} \to K_{\Lambda,r}[T]/(q(T)) \tag{28.3} \\ X_j \mapsto v_j(T) \quad \text{pour } r+1 \le j \le n \end{gathered} $$

est un isomorphisme de $K_{\Lambda,r}$-algèbres.

## Remontée de l'élément primitif générique et de la paramétrisation

Pour calculer la paramétrisation « générique » de $I'_{\Lambda,i}$, c'est-à-dire par l'élément primitif $u_\Lambda = \Lambda_{r+1}X_{r+1} + \dots + \Lambda_nX_n$, une première solution consiste à calculer le polynôme caractéristique $q_\Lambda$ de $u_\Lambda$ dans $K_{\Lambda,r}[T]/(q(T))$ par la formule

$$q_{\Lambda}(T) = \mathrm{Res}_{S}(q(S), T - u_{\Lambda}(v_{r+1}(S), \dots, v_{n}(S))).$$

De là on déduit les paramétrisations par $w_{\Lambda,j}(T) = -\partial q_{\Lambda}(T)/\partial \Lambda_j$; le Lemme 27.15 donne alors :

$$I'_{\Lambda,i} = (q_{\Lambda}(u_{\Lambda}), q'_{\Lambda}(u_{\Lambda})X_{r+1} - w_{\Lambda,r+1}(u_{\Lambda}), \dots, q'_{\Lambda}(u_{\Lambda})X_{n} - w_{\Lambda,n}(u_{\Lambda})),$$

et

$$I_i^{\Lambda} \supseteq (q_{\Lambda}(u_{\Lambda}), q'_{\Lambda}(u_{\Lambda})X_{r+1} - w_{\Lambda,r+1}(u_{\Lambda}), \dots, q'_{\Lambda}(u_{\Lambda})X_{n} - w_{\Lambda,n}(u_{\Lambda})).$$

Cependant, plutôt que de calculer avec des fractions rationnelles en les $\Lambda_j$, il est possible de se contenter de développements en séries au premier ordre au voisinage de $(\lambda_1, \dots, \lambda_n)$. Il est commode d'introduire l'idéal maximal

$$\mathcal{L} = (\Lambda_1 - \lambda_1, \dots, \Lambda_n - \lambda_n).$$

Pour calculer $q_\Lambda$ modulo $\mathcal{L}^2$ il suffit d'utiliser le Corollaire 25.16 : au signe près, les paramétrisations $w_i$ sont les coefficients des termes linéaires en $(\Lambda_i - \lambda_i)$, fournissant sans calcul

$$q_{\Lambda}(T) = q(T) - (\Lambda_{r+1} - \lambda_{r+1})w_{r+1}(T) - \dots - (\Lambda_n - \lambda_n)w_n(T) \mod \mathcal{L}^2.$$

Il faut également calculer les paramétrisations $v_{\Lambda,j} = w_{\Lambda,j}/q'_\Lambda$. Pour cela, on peut interpréter le calcul précédent en terme de remontée de Hensel : en posant

$$\Delta(T) = q'(T)^{-1}(q_{\Lambda}(T) - q(T)) \mod q(T) \mod \mathcal{L}^2$$

on a $q(T + \Delta(T)) = 0 \mod q_\Lambda(T) \mod \mathcal{L}^2$. Par ailleurs, de $q'(u)X_j - w_j(u) \in I_i$ on déduit que $X_j - v_j(u_\Lambda + \Delta(u_\Lambda))$ appartient à l'extension de $I_i$ à

$$(k[\Lambda_1, \dots, \Lambda_n]/\mathcal{L}^2)(X_0, \dots, X_r)[X_{r+1}, \dots, X_n].$$
On obtient ainsi la formule

$$v_{\Lambda,j}(T) = v_j(T) + (v'_j(T)\Delta(T) \text{ mod } q(T)) \text{ mod } \mathcal{L}^2,$$

puis

$$w_{\Lambda,j}(T) = q'_{\Lambda}(T)v_{\Lambda,j}(T) \text{ mod } q_{\Lambda}(T) \text{ mod } \mathcal{L}^2.$$

## Calcul de la paramétrisation suivante

Pour expliquer comment la paramétrisation suivante est calculée, commençons par montrer que le calcul du polynôme minimal P de la multiplication par $X_r$ dans $E_{r-1}$, lorsque $X_r$ est primitif, peut s'obtenir par la formule

$$P(X_r) = \mathrm{Res}_T(q(T), f_{i+1}(X_0, \dots, X_r, v_{r+1}(T), \dots, v_n(T))).$$

En effet, l'isomorphisme (28.1) et le Lemme 6.9 assurent que P est le coefficient constant du polynôme caractéristique de la multiplication par $f_{i+1}$ dans $E_r$. En particulier, par la Proposition 27.9, ce polynôme P est homogène de degré total $d_{i+1}\delta_i = \delta_{i+1}$. Le Lemme 27.11 donne ensuite que P est unitaire en $X_r$. Et enfin le Corollaire 27.14 assure que P appartient à $I_{i+1}$. Par conséquent, si $X_r$ est primitif pour $I'_{i+1}$ alors P est bien le polynôme minimal de la multiplication par $X_r$ dans $E_{r-1}$.

**Exemple 28.8** Dans l'Exemple 28.2, en partant de la paramétrisation de $I'_2$, ce calcul de P commence par la réduction modulo $q(T)$ de $f_3$ évalué en

$$\left( X_0, X_1, \frac{8(X_0^2 - X_1^2)(T^2 - 2X_1T + 5X_0^2 + 5X_1^2)}{q'(T)}, \frac{-12X_0^2(T^2 - 2X_1T - 5X_0^2 - 4X_1^2)}{q'(T)} \right),$$

ce qui donne

$$\frac{-7T^3 + (127X_0^2 - 100X_1^2)T^2 + 12X_1(5X_0^2 + 4X_1^2)}{12(5X_0^2 + 4X_1^2)}.$$

Malgré le dénominateur, le raisonnement ci-dessus affirme que le résultant avec $q(T)$ est un polynôme, et en effet, le calcul fournit

$$P(X_1) = 100X_1^4 - 164X_1^2X_0^2 + 64X_0^4,$$

qui est sans carré, de degré 4 = 4×1, et redonne bien le terme constant du polynôme minimal de $f_3$ trouvé à l'Exemple 27.4.

Pour obtenir une paramétrisation de $E_{r-1}$, nous partons de cette idée, mais en « déformant » la variable $X_r$ de sorte à obtenir le polynôme minimal de $U_\Lambda = \Lambda_r X_r + u_\Lambda$ dans $E_{r-1}$ à la place de P.
**Proposition 28.3** Sous les hypothèses $(H_1)-(H_3)$, soient

$$
\begin{align*}
\tilde{q}_{\Lambda}(T) &= q_{\Lambda}(T)|_{X_r \mapsto (Y-T)/\Lambda_r}, \\
\tilde{p}_{\Lambda}(T) &= (q'_{\Lambda}(T))|_{X_r \mapsto (Y-T)/\Lambda_r}^{-1} \mod \tilde{q}_{\Lambda}(T), \\
\tilde{w}_{\Lambda,j}(T) &= w_{\Lambda,j}(T)|_{X_r \mapsto (Y-T)/\Lambda_r}, \quad \text{pour } r+1 \le j \le n, \\
\tilde{v}_{\Lambda,j}(T) &= \tilde{p}_{\Lambda}(T)\tilde{w}_{\Lambda,j}(T) \mod \tilde{q}_{\Lambda}(T), \quad \text{pour } r+1 \le j \le n, \\
\tilde{h}(T) &= f_{i+1}(X_0, \dots, X_{r-1}, (Y-T)/\Lambda_r, \tilde{v}_{\Lambda,r+1}(T), \dots, \tilde{v}_{\Lambda,n}(T)) \mod \tilde{q}_{\Lambda}(T),
\end{align*}
$$

alors le résultant $Q_{\Lambda}(Y) = \mathrm{Res}_{T}(\tilde{q}_{\Lambda}(T), \tilde{h}(T))$ est le polynôme minimal de la multi-
plication par $U_{\Lambda} = \Lambda_{r}X_{r} + u_{\Lambda}$ dans $E_{\Lambda, r-1}$. Il est de degré total $\delta_{i+1}$, unitaire en $Y$,
sans carré, et satisfait $Q_{\Lambda}(U_{\Lambda}) \in I_{i+1}^{\Lambda}$.

Démonstration. Nous utilisons des « ~ » pour noter les objets obtenus après le changement de variable $X_r \mapsto (Y - u_\Lambda)/\Lambda_r$. On note donc $\tilde{f}_{\Lambda,i} = f_i|_{X_r \mapsto (Y-u_\Lambda)/\Lambda_r}$, et $\tilde{I}_{\Lambda,i} = (\tilde{f}_{\Lambda,1}, \dots, \tilde{f}_{\Lambda,i})$, et on décline les notations en conséquence :

$$
\begin{align*}
\tilde{R}_{\Lambda} &= k_{\Lambda}[X_0, \dots, X_{r-1}, Y, X_{r+1}, \dots, X_n], \\
\tilde{A}_{\Lambda,r} &= k_{\Lambda}[X_0, \dots, X_{r-1}, Y], & \tilde{K}_{\Lambda,r} &= k_{\Lambda}(X_0, \dots, X_{r-1}, Y), \\
\tilde{B}_{\Lambda,r} &= \tilde{R}_{\Lambda}/\tilde{I}_{\Lambda,i}, & \tilde{E}_{\Lambda,r} &= \tilde{K}_{\Lambda,r}[X_{r+1}, \dots, X_n]/\tilde{I}'_{\Lambda,i},
\end{align*}
$$

où $\tilde{I}'_{\Lambda,i}$ est l'extension de $\tilde{I}_{\Lambda,i}$ dans $\tilde{K}_{\Lambda,r}[X_{r+1}, \dots, X_n]$.

La suite $\tilde{f}_{\Lambda,1}, \dots, \tilde{f}_{\Lambda,n}$ reste régulière dans $\tilde{R}_{\Lambda}$ et les idéaux intermédiaires sont radicaux. Par ailleurs, appliquer le changement de variable inversible $X_r \mapsto (Y - u_{\Lambda})/\Lambda_r$ conserve les dimensions des $k_{\Lambda}$-espaces vectoriels $(B_{\Lambda,r})_l$ pour tout $l > 1$. Par conséquent $\tilde{I}_{\Lambda,i}$ a la même dimension et le même degré que $I_i$.

Une relation $P_u(X_0, \dots, X_r, u_\Lambda) \in I_{\Lambda,i}$ de dépendance entière de $u_\Lambda$ sur $A_{\Lambda,r}$ donne
une relation de dépendance entière $P_u(X_0, \dots, X_{r-1}, (Y-u_\Lambda)/\Lambda_r, u_\Lambda) \in \tilde{I}_{\Lambda,i}$ de $u_\Lambda$ sur
$\tilde{A}_{\Lambda,r}$ modulo $\tilde{I}_{\Lambda,i}$. Ensuite une relation $P_j(X_0, \dots, X_r, X_j) \in I_i$ de dépendance entière de
$X_j$, pour $j \ge r+1$, sur $A_r$ donne une relation de dépendance entière $P_j(X_0, \dots, X_{r-1}, (Y-u_\Lambda)/\Lambda_r, X_j) \in \tilde{I}_{\Lambda,i}$ de $X_j$ sur $k_\Lambda[X_0, \dots, X_{r-1}, Y, u_\Lambda]$. La position de Noether de $\tilde{I}_{\Lambda,i}$
découle alors de la Proposition 27.2. En combinant à nouveau les Théorèmes 26.5 et 26.7 pour la suite régulière $\tilde{f}_{\Lambda,1}, \dots, \tilde{f}_{\Lambda,i}$, on obtient que la dimension de $\tilde{E}_{\Lambda,r}$ est
encore $\delta_i$.

Du Théorème 27.16 on a l'inclusion

$$
(q(u), q'(u)X_{r+1} - w_{r+1}(u), \dots, q'(u)X_n - w_n(u)) \subseteq I_i.
$$

Comme le discriminant de $q$ en $T$ est non nul, le discriminant de $q_{\Lambda}$ en $T$ est non
nul (en utilisant la Proposition 6.8 avec la spécialisation $\Lambda_{r+1} = \lambda_{r+1}, \dots, \Lambda_n = \lambda_n$). Le
même argument donne aussi que $q'(T)|_{X_r \mapsto (Y-T)/\Lambda_r}$ est inversible modulo $\tilde{q}_{\Lambda}$, et on
obtient ainsi

$$
(\tilde{q}_{\Lambda}(u_{\Lambda}), X_{r+1} - \tilde{v}_{\Lambda,r+1}(u_{\Lambda}), \dots, X_n - \tilde{v}_{\Lambda,n}(u_{\Lambda})) \subseteq \tilde{I}_{\Lambda,i}.
$$
Comme la dimension de $\tilde{\mathbb{E}}_{\Lambda,r}$ coïncide avec $\deg q$, on obtient que $u_{\Lambda}$ est primitif pour $\tilde{I}'_{\Lambda,i}$ et que la paramétrisation associée donne l'isomorphisme

$$ \begin{aligned} \tilde{\mathbb{E}}_{\Lambda,r} & \rightarrow \tilde{\mathbb{K}}_{\Lambda,r}[T]/(\tilde{q}_{\Lambda}(T)) \\ X_j & \mapsto \tilde{v}_{\Lambda,j}(T), \quad \text{pour } r+1 \le j \le n. \end{aligned} $$

Le Lemme 6.9 implique que $Q_{\Lambda}$ est le coefficient constant du polynôme caractéristique de multiplication par $\tilde{f}_{\Lambda,i+1}$ dans $\tilde{\mathbb{E}}_{\Lambda,r}$. En particulier $Q_{\Lambda}$ est un polynôme homogène de $k_{\Lambda}[X_0, \dots, X_{r-1}, Y]$ de degré total $d_{i+1} \delta_i = \delta_{i+1}$, par la Proposition 27.9. Le Corol- laire 27.14 donne $Q_{\Lambda}(Y) \in \tilde{I}_{\Lambda,i+1}$. Par le Lemme 27.11, on a aussi que $Q_{\Lambda}$ est unitaire un Y. En remplaçant Y par $\Lambda_r X_r + u_{\Lambda}$ on obtient finalement que $Q_{\Lambda}$ est le polynôme minimal de $U_{\Lambda}$ modulo $I'_{\Lambda,i+1}$. La dernière inclusion provient du Lemme 27.15. ■

## Calcul du résultant

La Proposition 28.3 prouve que le résultant calculé est un polynôme en Y dont on connaît le degré, mais, comme dans l'Exemple 28.8, les polynômes dont on calcule le résultant ont pour coefficients des fractions rationnelles en Y qui ne sont généra- lement pas des polynômes. Le calcul avec ces fractions peut mener à des fractions de numérateurs et dénominateurs de hauts degrés qui ne se simplifient qu'en fin de calcul, menant à une complexité élevée. Le calcul rapide par évaluation-interpolation n'est pas non plus une solution immédiate, puisqu'il faut éviter les valeurs qui an- nulent un dénominateur. La solution adoptée dans l'Algorithme 28.3, qui résume la méthode pour calculer la nouvelle paramétrisation, est de calculer ce résultant en série à précision plus grande que le degré, au voisinage d'un point b donné en argument.

Dans l'algorithmme, la spécialisation des variables $\Lambda_1, \dots, \Lambda_n$ en les valeurs $\lambda_1, \dots, \lambda_n$ est notée $\Lambda_{1:n} \mapsto \lambda_{1:n}$.

## Spécialisations

Nous dirons qu'un algorithmme *commute avec la spécialisation d'une variable* X en la valeur a si la spécialisation de la sortie de l'algorithmme coïncide avec la sortie de l'algorithmme appliqué aux entrées spécialisées. Pour simplifier les analyses de complexité on utilise volontairement la notation $\tilde{O}$ (Section 1.2). On rappelle qu'en degré d des polynômes à une variable sur un anneau peuvent être multipliés et divisés en coûts quasi-linéaires (Chapitres 2 et 3).

Les algorithmes de ce chapitre dépendent de plusieurs choix aléatoires. D'une part la mise en position de Noether, incluse dans les hypothèses pour simplifier la présentation, sous-entend qu'un changement de variable linéaire pris au hasard a déjà été appliqué. Ensuite, nous utilisons explicitement un point $(\lambda_1, \dots, \lambda_n)$ de $k^n$ pour construire les éléments primitifs, et un autre point $(a_0, \dots, a_{n-1}) \in k^n$ pour spécialiser les variables libres dans la prochaine section. Sur le même plan, un point auxiliaire $b \in k$ intervient pour effectuer des calculs de résultats rapides de polynômes à deux variables.
**Entrée** $f_1, \dots, f_{i+1}$ satisfaisant les hypothèses $(H_1)-(H_3)$, $(\lambda_1, \dots, \lambda_n) \in k^n$, $b \in k$, et la paramétrisation sous forme de Kronecker $q, w_{r+1}, \dots, w_n$ de $I'_i$ par l'élément primitif $u = \lambda_{r+1}X_{r+1} + \dots + \lambda_n X_n$.

**Sortie** La paramétrisation sous forme de Kronecker de $I_{i+1}$ par l'élément primitif $U = \lambda_r X_r + \dots + \lambda_n X_n$.

1. Calculer la paramétrisation $q_\Lambda, v_{\Lambda,r+1}, \dots, v_{\Lambda,n}$ de $I_{\Lambda,i}$ pour l'élément primitif $u_\Lambda = \Lambda_{r+1}X_{r+1} + \dots + \Lambda_{r+1}X_{r+1}$ modulo $\mathcal{L}^2$ où $\mathcal{L} = (\Lambda_1 - \lambda_1, \dots, \Lambda_n - \lambda_n)$ :

$$ - q_{\Lambda}(T) = q(T) - \sum_{i=r+1}^{n} (\Lambda_i - \lambda_i) w_i(T) \mod \mathcal{L}^2; $$

$$ - \Delta(T) = (q_{\Lambda}(T) - q(T))/q'(T) \mod q(T) \mod \mathcal{L}^2; $$

$$ - \text{pour } j = r+1, \dots, n, $$

$$ - v_j(T) = w_j(T)/q'(T) \mod q(T); $$

$$ - v_{\Lambda,j}(T) = v_j(T) + (v'_j(T)\Delta(T) \mod q(T)) \mod \mathcal{L}^2, $$

$$ - w_{\Lambda,j}(T) = q'_{\Lambda}(T)v_{\Lambda,j}(T) \mod q_{\Lambda}(T) \mod \mathcal{L}^2. $$

2. Effectuer le changement de variable mod $\mathcal{L}^2$ et $(Y-b)^{\delta_{i+1}+1}$ :

$$ - \tilde{q}_{\Lambda}(T) = q_{\Lambda}(T)|_{X_r \mapsto (Y-T)/\Lambda_r}; $$

$$ - \tilde{p}_{\Lambda}(T) = (q'_{\Lambda}(T))|_{X_r \mapsto (Y-T)/\Lambda_r}^{-1} \mod \tilde{q}_{\Lambda}(T); $$

$$ - \text{pour } j = r+1, \dots, n, $$

$$ - \tilde{w}_{\Lambda,j}(T) = w_{\Lambda,j}(T)|_{X_r \mapsto (Y-T)/\Lambda_r}; $$

$$ - \tilde{v}_{\Lambda,j}(T) = \tilde{p}_{\Lambda}(T)\tilde{w}_{\Lambda,j}(T) \mod \tilde{q}_{\Lambda}(T). $$

3. Calculer le résultant :

$$ - \tilde{h}(T) = f_{i+1}(X_0, \dots, X_{r-1}, (Y-T)/\Lambda_r, \tilde{v}_{\Lambda,r+1}(T), \dots, \tilde{v}_{\Lambda,n}(T)) \mod q_{\Lambda}(T), \mathcal{L}^2 \text{ et } (Y-b)^{\delta_{i+1}+1}; $$

$$ - Q_{\Lambda}(Y) = \mathrm{Res}_{T}(\tilde{q}_{\Lambda}(T), \tilde{h}(T)) \mod \mathcal{L}^2 \mod (Y-b)^{\delta_{i+1}+1}. $$

4. Renvoyer

$$ Q_{\Lambda}(T)|_{\Lambda_{1:n} \mapsto \Lambda_{1:n}}, - \left. \frac{\partial Q_{\Lambda}(T)}{\partial \Lambda_r} \right|_{\Lambda_{1:n} \mapsto \Lambda_{1:n}}, \dots, - \left. \frac{\partial Q_{\Lambda}(T)}{\partial \Lambda_n} \right|_{\Lambda_{1:n} \mapsto \Lambda_{1:n}}. $$

**Algorithme 28.3** – Calcul de la paramétrisation suivante.

**Proposition 28.4** Sous les hypothèses $(H_1)-(H_3)$, il existe une variété algébrique propre $Z_i$ de $\mathbb{A}^n$ telle que pour tout $(\lambda_1, \dots, \lambda_n)$ pris hors de $Z_i$, il existe un sous-ensemble fini $Z_{\lambda,i}$ de $k$ tel que pour tout $b$ pris hors de $Z_{\lambda,i}$, on a :

- l'Algorithme 28.3 est correct;

- il existe une variété algébrique propre $Z_{\lambda,b,i}$ de $\mathbb{A}^r$ telle que l'algorithme com-mute avec la spécialisation des variables $X_0, \dots, X_{r-1}$ en $a_0, \dots, a_{r-1}$ pris hors de $Z_{\lambda,b,i}$. Dans ce cas, le calcul spécialisé utilise $(nL + n^2)\mathcal{O}(\delta_i \delta_{i+1})$ opérations dans $k$, où $L$ est la complexité d'évaluation du DAG représentant $f_1, \dots, f_{i+1}$.

*Démonstration.* Si on oublie le « modulo $\mathcal{L}^2$ », alors les étapes (1)–(3) suivent juste la
proposition précédente. En dérivant $Q_{\Lambda}(U_{\Lambda}) \in I_{i+1}^{\Lambda}$ en $\Lambda_j$ on obtient

$$Q'_{\Lambda}(T)X_j + \frac{\partial Q_{\Lambda}(T)}{\partial \Lambda_j} \in I_{i+1}^{\Lambda}.$$

Le discriminant de $Q_{\Lambda}(T)$ est un polynôme de $k[\Lambda_r, \dots, \Lambda_n][X_0, \dots, X_r]$ : on peut prendre n'importe quel coefficient non nul de ce discriminant pour définir une variété affine notée $Z'_i$. Pour tout point $(\lambda_1, \dots, \lambda_n)$ hors de $Z'_i$ on peut spécialiser les $\Lambda_j$. En posant

$$Q(T) = Q_{\Lambda}(T)|_{\Lambda_{1:n} \mapsto \lambda_{1:n}}, \quad W_j(T) = \left. \frac{\partial Q_{\Lambda}(T)}{\partial \Lambda_r} \right|_{\Lambda_{1:n} \mapsto \lambda_{1:n}},$$

on obtient

$$(Q(U), Q'(U)X_r - W_r(U), \dots, Q'(U)X_n - W_n(U)) \subseteq I_{i+1}.$$

Comme $Q$ est sans carré de degré $\delta_{i+1}$, on obtient ainsi une paramétrisation sous forme de Kronecker de $I'_{i+1}$.

À ce stade, la variété $Z'_i$ conviendrait à faire fonctionner l'algorithmie si on utilisait des calculs de résultant sans division (par exemple en combinant sa définition sous forme de déterminant vue en Section 6.2 à l'algorithme de Berkowitz du Théorème 8.9). Mais ceci nous conduirait à une complexité bien plus élevée que souhaitée. Pour que l'algorithme soit efficace il doit utiliser l'algorithme d'Euclide rapide vu en Section 6.3, qui a un coût quasi-linéaire.

Une fois fixé un algorithme rapide pour le résultant, on peut prendre pour $Z_i$ la réunion de $Z'_i$ et d'une variété contenant les valeurs $(\lambda_1, \dots, \lambda_n)$ qui ne commutent pas avec la spécialisation $\Lambda_{1:n} \mapsto \lambda_{1:n}$ lors du calcul de $Q_{\Lambda}(Y) = \text{Res}_T(\tilde{q}_{\Lambda}(T), \tilde{h}(T))$. Une fois $(\lambda_1, \dots, \lambda_n)$ fixés, on exclut ensuite les valeurs de $b$ telles que ce calcul ne commute pas avec la spécialisation $Y \mapsto b$. Avec de bonnes valeurs des $\lambda_i$ et de $b$ ce calcul de résultant peut donc s'effectuer modulo $\mathcal{L}^2$ et $(Y-b)^{\delta_{i+1}+1}$. Cette dernière précision est suffisante puisque $Q(Y)$ est de degré $\delta_{i+1}$. Sous ces conditions le résultat renvoyé par l'algorithme est correct.

Une fois $(\lambda_1, \dots, \lambda_n)$ et $b$ fixés, on prend pour $Z_{\lambda,b,i}$ la variété définie par tous les dénominateurs et tests à zéro en les $X_0, \dots, X_{r-1}$ intervenant dans les calculs.

On analyse maintenant le coût de l'algorithme pour un calcul spécialisé. Les variables restant en jeu sont $X_r, \dots, X_n, Y, T$ et les $\Lambda_j$. Tout d'abord, l'étape (1) requiert $n^2 \tilde{O}(\delta_i^2)$ opérations dans $k$.

Les calculs de l'étape (2) peuvent aussi être réalisés en coût $n^2 \tilde{O}(\delta_i^2)$. Car d'une part un changement de variable

$$P(X_r, T)|_{X_r \mapsto (Y-T)/\Lambda_r}$$

s'obtient comme

$$P((Y-T)/\lambda_r, T) - \frac{\partial P}{\partial X_r}((Y-T)/\lambda_r, T)(\Lambda_r - \lambda_r) \mod \mathcal{L}^2.$$

Et d'autre part, le calcul de $P((Y-T)/\lambda_{r+1}, T)$ se décompose en les calculs de $P_l((Y-1)/\lambda_{r+1}, 1)$ pour chaque composante homogène $P_l$ de P. Il s'agit donc d'appliquer une
**Entrée** $f_1, \dots, f_n$ satisfaisant les hypothèses $(H_1)-(H_3)$, $(\lambda_1, \dots, \lambda_n) \in k^n$, et $b \in k$.

**Sortie** La paramétrisation sous forme de Kronecker de $I_n$ par l'élément primitif $\lambda_1 X_1 + \dots + \lambda_n X_n$.

1. Construire la paramétrisation sous forme de Kronecker de $I_1$ par $\lambda_n X_n$ comme $q(T) = f_1|_{X_n \mapsto T/\lambda_n}$ et $w_n(T) = q'(T)T/\lambda_n$ mod $q(T)$.

2. Pour $i$ de 1 à $n-1$, utiliser l'Algorithmme 28.3 avec $f_1, \dots, f_{i+1}$, $(\lambda_1, \dots, \lambda_n)$ et $b$ pour calculer la paramétrisation de $I_{i+1}$ pour l'élément primitif $\lambda_r X_r + \dots + \lambda_n X_n$, à partir de la paramétrisation de $I_i$.

**Algorithmme 28.4** – Calcul incrémental de paramétrisations.

translation et une dilatation à chaque $P_l(X_r, 1)$. Cette opération requiert un coût quasi-linéaire, par exemple en utilisant les algorithmes d'évaluation et interpolation rapides du Chapitre 5. Au total, pour chaque polynôme $P$ de degré total $\le \delta_i$, le changement de variables $X_r \mapsto (Y-T)/\Lambda_r$ requiert $\tilde{O}(\delta_i^2)$ opérations dans $k$. L'étape (2) accumule essentiellement $O(n^2)$ fois ce coût.

Pour l'étape (2), l'inversion modulaire pour obtenir $\tilde{\rho}_\Lambda$ requiert $n \tilde{O}(\delta_i \delta_{i+1})$ opérations dans $k$ avec l'algorithme de résultant rapide. L'évaluation de $f_{i+1}$ coûte ensuite $n \tilde{O}(\delta_i \delta_{i+1})$. Le résultant pour obtenir $\Lambda$ fait aussi intervenir $n \tilde{O}(\delta_i \delta_{i+1})$ opérations dans $k$. La dernière étape de l'algorithme n'effectue pas vraiment de calcul. ■

## Vue d'ensemble de l'approche incrémentale

La résolution incrémentale complète est détaillé dans l'Algorithmme 28.4 : on calcule des paramétrisations successives pour $I'_1, I'_2, I'_3$, etc.

**Proposition 28.5** Sous les hypothèses $(H_1)-(H_3)$, il existe une variété algébrique propre $Z$ de $\mathbb{A}^n$ telle que pour tout $(\lambda_1, \dots, \lambda_n)$ pris hors de $Z$, il existe un sous-ensemble fini $Z_\Lambda$ tel que pour tout $b$ pris hors de $Z_\Lambda$ l'Algorithmme 28.4 est correct.

*Démonstration.* La preuve découle de la Proposition 28.4, en prenant pour $Z$ la réunion des $Z_i$, et pour $Z_\Lambda$ la réunion des $Z_{\Lambda,i}$.

En terme d'efficacité, l'Algorithmme 28.4 est clairement pénalisé par les calculs avec les fractions rationnelles en les variables $X_1, \dots, X_{r-1}$ à l'étape $i$ de la boucle. Le reste de ce chapitre consiste à raffiner cet algorithme pour s'affranchir de ces fractions rationnelles.

## 28.3 Remontée d'une paramétrisation

Pour contenir la croissance des expressions faisant intervenir un grand nombre de variables libres dans l'Algorithmme 28.4, l'idée suivante est de construire incrémentalement non pas les paramétrisations des $I'_i$ mais leurs spécialisations en les
variables libres. Plus précisément, on considère un point $a = (a_0, \dots, a_{n-1})$ de $k^n$, et la spécialisation d'une paramétrisation de $I'_i$ où les variables $X_0, \dots, X_r$ sont respectivement remplacées par $a_0, \dots, a_r$. D'une façon plus compacte nous notons cette spécialisation $X_{0;r} \mapsto a_{0;r}$. Nous avons vu dans la Proposition 27.17, que si $a$ est choisi en dehors d'une variété algébrique propre de $\mathbb{A}^n$, alors l'idéal non homogène $I_{a,i} = I_i + (X_0 - a_0, \dots, X_r - a_r)$ est radical de dimension 0, et que

$$q_a(T) = q(T)|_{X_{0;r} \to a_{0;r}}, w_{a,r+1}(T) = w_{r+1}(T)|_{X_{0;r} \to a_{0;r}}, \dots, w_{a,n}(T) = w_n(T)|_{X_{0;r} \to a_{0;r}}$$

constituent une paramétrisation de $I_{a,i}$. Le problème que nous examinons est la remontée de la paramétrisation $q, w_{r+1}, \dots, w_n$ de $I_i$ par l'élément primitif $u$ à partir de sa spécialisation $q_a, w_{a,r+1}, \dots, w_{a,n}$. Implicitement, nous avons supposé que $q_a$ est sans carré, et cela nous permet de quitter la représentation de Kronecker. Nous notons alors $v_j(T) = w_j(T)/q'(T)$ mod $q(T)$, et $v_{a,j}(T) = w_{a,j}(T)/q'_a(T)$ mod $q_a(T)$ pour $r+1 \le j \le n$.

## Itération de Newton

La remontée repose sur un calcul de développement en séries de $q$ et des $v_j$ dans $\mathcal{A}_{a,r} = k[[X_0 - a_0, \dots, X_r - a_r]]$. On note m l'idéal maximal

$$m = (X_0 - a_0, \dots, X_r - a_r).$$

L'algorithme construit successivement des polynômes $q_{[m]} = q \bmod m^m$ et $v_{[m],j} = v_j \bmod m^m$, en partant de $q_{[1]} = q_a$ et $v_{[1],j} = v_{a,j}$, et en procédant récursivement par doublement de précision $m$.

L'idée principale est d'utiliser une itération de Newton pour le système $f_1 = \dots = f_i = 0$ comme dans le Théorème 3.12 p. 70. On note

$$J = \left( \frac{\partial F_j}{\partial X_k} \right)_{\substack{1 \le j \le i \\ r+1 \le k \le n}}$$

la matrice jacobienne de $f_1, \dots, f_i$ par rapport aux variables $X_{r+1}, \dots, X_n$. Pour garder les notations compactes dans l'opérateur de Newton, $v_{[m],r+1:n}$ représente le $(n-r)$-uplet $v_{[m],r+1}, \dots, v_{[m],n}$. On commence par calculer

$$\hat{v}_{[2m],r+1:n}(T) = v_{[m],r+1:n}(T) - J^{-1} f_{1:i} \big|_{X_{r+1:n} \to v_{[m],r+1:n}(T)} \bmod q_{[m]}(T) \bmod m^{2m},$$

ce qui est possible du fait du résultat suivant :

**Lemme 28.6** Sous les hypothèses $(H_1)-(H_3)$, si $q_a$ est sans carré, alors la matrice jacobienne $J$ de $(f_1, \dots, f_i)$ par rapport aux variables $X_{r+1}, \dots, X_n$ est inversible modulo $I_{a,i}$.

*Démonstration.* On considère à nouveau le polynôme minimal $q_\Lambda$ de $u_\Lambda = \Lambda_{r+1}X_{r+1} + \dots + \Lambda_n X_n$. D'après le Lemme 27.15, le polynôme $q_\Lambda$ est sans carré, et $q_\Lambda(u_\Lambda)$ appartient à $I_i^\Lambda$. Il existe donc des polynômes $g_1, \dots, g_i$ de $\mathbb{R}^\Lambda$ tels que

$$q_\Lambda(u_\Lambda) = g_1 f_1 + \dots + g_i f_i.$$
En dérivant par rapport à $X_j$ on obtient

$$ \Lambda_j q'_{\Lambda}(u_{\Lambda}) = g_1 \frac{\partial f_1}{\partial X_j} + \dots + g_i \frac{\partial f_i}{\partial X_j} \mod I_i^{\Lambda}. $$

On peut spécialiser les $\Lambda_j$ en les $\lambda_j$ pour $r+1 \le j \le n$ et les $X_j$ en les $a_j$ pour $0 \le j \le r$ :

$$ \lambda_j q'_{a}(u) = g_1 \frac{\partial f_1}{\partial X_j} + \dots + g_i \frac{\partial f_i}{\partial X_j} \mod I_{a,i}. $$

Comme $q'_a(u)$ est inversible modulo $I_{a,i}$, pour tout choix de vecteur $\lambda = (\lambda_{r+1}, \dots, \lambda_n)$ en dehors d'une variété propre de $\mathbb{A}^{n-r}$, ces équations fournissent un vecteur $g = (g_1, \dots, g_i)$ tel que $J \cdot g = \lambda \mod I_{a,i}$, ce qui prouve l'inversibilité de J modulo $I_{a,i}$. ■

## Déformation du paramètre

Il existe un unique polynôme $\Delta(T) \in \mathcal{A}_{a,r}[T]$ de degré < deg $q$ et à coefficients dans $\mathfrak{m}$ tel que

$$ q_{[2m]}(T + \Delta(T)) = 0 \mod q_{[m]}(T) \mod \mathfrak{m}^{2m}, $$

qui est déterminé par le développement

$$ q_{[2m]}(T + \Delta(T)) = q_{[2m]}(T) + q'_{[m]}(T)\Delta(T) \mod q_{[m]}(T) \mod \mathfrak{m}^{2m}. $$

Ensuite, pour $1 \le j \le i$, on déduit de $f_j(X_0, \dots, X_r, v_{r+1}(T), \dots, v_n(T)) = 0 \mod q(T)$ que

$$ f_j(X_0, \dots, X_r, v_{[2m],r+1}(T+\Delta(T)), \dots, v_{[2m],n}(T+\Delta(T))) = 0 \mod q_{[m]}(T) \mod \mathfrak{m}^{2m}. $$

Par unicité de la remontée par opérateur de Newton, on obtient alors

$$ v_{[2m],j}(T + \Delta(T)) = \hat{v}_{[2m],j}(T) \mod q_{[m]}(T) \mod \mathfrak{m}^{2m}. $$

Ensuite, à partir de

$$ u(v_{[2m],r+1}(T+\Delta(T)), \dots, v_{[2m],n}(T+\Delta(T))) = T + \Delta(T) \mod q_{[m]}(T) \mod \mathfrak{m}^{2m} $$

on obtient ainsi une façon de calculer $\Delta$ :

$$ \Delta(T) = u(\hat{v}_{[2m],r+1}(T), \dots, \hat{v}_{[2m],n}(T)) - T. $$

Finalement on vient de voir, qu'à partir des $\hat{v}_{[2m],j}$, il est aisé d'en déduire $\Delta$ puis $q_{[2m]}$, $v_{[2m],r+1}, \dots, v_{[2m],n}$ :

$$ q_{[2m]}(T) = q_{[m]}(T) - (q'_{[m]}(T)\Delta(T) \mod q_{[m]}(T)) \mod \mathfrak{m}^{2m}, $$

$$ v_{[2m],j}(T) = \hat{v}_{[2m],j}(T) - (v'_{[m],j}(T)\Delta(T) \mod q_{[m]}(T)) \mod \mathfrak{m}^{2m}. $$
**Entrée** $f_1, \dots, f_i$ satisfaisant les hypothèses $(H_1)-(H_3)$, $(\lambda_1, \dots, \lambda_n) \in k^n$, $(a_0, \dots, a_r) \in k^r$, et la spécialisation de la paramétrisation $q_a, w_{a,r+1}, \dots, w_{a,n}$ sous forme de Kronecker de $I_i$ pour l'élément primitif $u = \lambda_{r+1}X_{r+1} + \dots + \lambda_n X_n$.

**Sortie** La paramétrisation $q, w_{r+1}, \dots, w_n$ de $I_i$ sous forme de Kronecker pour $u$.

1. Initialiser $m = 1$ et $q_{[1]} = q_a$, et $v_{[1],j} = (q'_a)^{-1}w_{a,j} \mod q_a$ pour $r+1 \le j \le n$.

2. Tant que $m \le \delta_i$ faire :

a. calculer $\hat{v}_{[2m],r+1:n} = v_{[m],r+1:n} - J^{-1}f_{1:i}|_{X_{r+1:n} \mapsto v_{[m],r+1:n}} \text{ modulo } q_{[m]} \text{ et } m^{2m}$;

b. calculer $\Delta(T) = u(\hat{v}_{[2m],r+1}(T), \dots, \hat{v}_{[2m],n}(T)) - T$;

c. calculer $q_{[2m]} = q_{[m]} - (q'_{[m]}) \Delta \mod q_{[m]} \mod m^{2m}$;

d. pour $r+1 \le j \le n$, calculer
$$v_{[2m],j} = \hat{v}_{[2m],j} - (v'_{[m],j}) \Delta(T) \mod q_{[m]} \mod m^{2m};$$

e. remplacer $m$ par $2m$.

3. Renvoyer $q_{[m]}$, $q'_{[m]}v_{[m],r+1} \mod q_{[m]} \mod m^m, \dots, q'_{[m]}v_{[m],n} \mod q_{[m]} \mod m^m$, vus comme polynômes de $A_r[T]$.

Algorithme 28.5 – Remontée de Hensel d'une paramétrisation.

## Fin de la remontée

Une fois obtenus $q_{[m]}$, $v_{[m],r+1}, \dots, v_{[m],n}$ à la précision $m = \delta_i + 1$, on obtient immédiatement $q$ puisqu'il est de degré total $\delta_i$. Ensuite on calcule $w_j$ comme $q'_{[m]}v_{[m],j} \mod q_{[m]} \mod m^m$ puisqu'il est lui aussi de degré total $\delta_i$. La méthode complète de remontée de Hensel se résume donc en l'Algorithme 28.5. Dans l'algorithme principal de la section suivante la remontée ne concerne que la dernière variable libre $X_r$. Les autres $X_j$ pour $1 \le j \le r-1$ restent spécialisées à $a_j$.

**Proposition 28.7** Sous les hypothèses $(H_1)-(H_3)$, l'Algorithme 28.5 est correct. L'algorithme commute avec les spécialisations $X_{0;r-1} \mapsto a_{0;r-1}$, tant que $a_{0;r}$ maintient $q_a$ sans carré. Si $f_1, \dots, f_i$ est donné par un DAG de complexité d'évaluation L, alors le calcul spécialisé coûte $(nL + n^4)\tilde{O}(\delta_i^2)$ opérations dans $k$.

*Démonstration.* La correction découle de la discussion qui précède. On analyse maintenant le coût de l'algorithme sur des entrées spécialisées. Les variables en jeu sont donc $X_r, \dots, X_n$ et T. D'une façon générale, pour évaluer un polynôme $g(Z_1, \dots, Z_l)$ et ses dérivées partielles en un point $z_1, \dots, z_l$, il suffit d'évaluer $g(z_1 + \epsilon_1, \dots, z_l + \epsilon_l) \text{ modulo } (\epsilon_1, \dots, \epsilon_l)^2$, ce qui implique un surcoût de $O(l)$ par rapport à la seule évaluation $g(z_1, \dots, z_l)$. Par conséquent, évaluer les $f_j$ et leurs dérivées partielles en précision $m$ requiert $nL\tilde{O}(m\delta_i)$ opérations dans $k$.

Pour inverser la matrice $J_{[2m]}(T) = J_{[X_{r+1:n} \mapsto V_{[2m],r+1:n}(T)]} \mod q_{[2m]}(T) \mod m^{2m}$, on procède par récurrence, à partir de l'inverse $J_{[m]}^{-1}(T)$ de $J_{[m]}(T)$ à la précision $m^m$.
**Entrée** $f_1, \dots, f_n$, satisfaisant les hypothèses $(H_1)-(H_3)$, et $(\lambda_1, \dots, \lambda_n) \in k^n$, $b \in k$, $(a_0, \dots, a_{n-1}) \in k^n$.

**Sortie** La paramétrisation de $I_n$ par $u = \lambda_1 X_1 + \dots + \lambda_n X_n$ spécialisée en $X_0 \mapsto a_0$.

1. Calculer la paramétrisation de $I_1$ par $u = \lambda_n X_n$ spécialisée en $X_{0:n-1} \mapsto a_{0:n-1}$, c'est-à-dire $q_a(T) = f_1|_{X_{0:n-1}} \mapsto a_{0:n-1}$, $X_n \mapsto T/\lambda_n$, $w_{a,n-1}(T) = T q'_a(T)$ mod $q_a(T)$.

2. Pour $i$ de 1 à $n-1$ :

a. utiliser l'Algorithme 28.5 avec $f_1, \dots, f_i$, $(\lambda_1, \dots, \lambda_n)$, et $(a_0, \dots, a_r)$ pour remonter la spécialisation de la paramétrisation de $I_i$ en $X_{0:r-1} \mapsto a_{0:r-1}$;

b. utiliser l'Algorithme 28.3 avec $f_1, \dots, f_{i+1}$, $(\lambda_1, \dots, \lambda_n)$, et $b$, pour en déduire la spécialisation de la paramétrisation de $I_{i+1}$ en $X_{0:r-1} \mapsto a_{0:r-1}$.

3. Renvoyer la paramétrisation de $I_n$ spécialisée en $X_0 \mapsto a_0$.

**Algorithme 28.6** – Algorithme de résolution géométrique.

Au départ, lorsque $m=1$, on utilise l'algorithme de Berkowitz, qui prend $n^4 \tilde{O}(\delta_i)$ opérations dans $k$ (Théorème 8.9 page 177). Ensuite on utilise la formule classique d'inversion par itération de Newton :

$$J_{[2m]}^{-1}(T) = J_{[m]}^{-1}(T) - J_{[m]}^{-1}(T)(J_{[2m]}(T)J_{[m]}^{-1}(T) - Id) \mod q_{[2m]}(T) \mod m^{2m},$$

qui demande $n^3 \tilde{O}(m\delta_i)$ opérations dans $k$. Notons que pour le calcul de l'étape (2.a) il est suffisant de connaître $J_{[m]}^{-1}(T)$.

En précision $2m$, les autres calculs demandent $n \tilde{O}(m\delta_i)$ opérations additionnelles dans $k$. Le coût total s'obtient de la même manière que pour les analyses de complexité similaires du Chapitre 3 : comme la précision double à chaque étape, le coût total est essentiellement dominé par le coût de la dernière étape. ■

## 28.4 Algorithme principal

En appliquant successivement étapes de remontée et d'ajout d'une nouvelle équation, on parvient finalement à un algorithme travaillant sur les spécialisations de paramétrisations. La méthode est synthétisée dans l'Algorithme 28.6.

**Théorème 28.8** Soit $k$ un corps de caractéristique zéro, et soient $f_1, \dots, f_n$ des polynômes homogènes de R, de degrés respectifs $d_i \ge 2$, et satisfaisant $(H_1)-(H_3)$. Il existe une variété algébrique propre $Z$ de $\mathbb{A}^n$, telle que pour tout point $(\lambda_1, \dots, \lambda_n)$ hors de $Z$, il existe un sous-ensemble fini $Z_\lambda$ de $k$ tel que pour tout $b$ pris hors de $Z_\lambda$, il existe une variété algébrique propre $Z_{\lambda,b}$ de $\mathbb{A}^n$ telle que pour tout point $(a_0, \dots, a_{n-1})$ hors de $Z_{\lambda,b}$, l'Algorithme 28.6 renvoie un résultat correct, et utilise $(nL + n^4) \tilde{O}(\delta_n^2)$ opérations dans $k$, où $\delta_n = d_1 \cdots d_n$.
Démonstration. Tout d'abord on choisit pour Z et Z_λ ceux de la Proposition 28.5. Un fois les λ_j et b fixés, l'Algorithme 28.4 s'exécute correctement. Les bonnes valeurs des a_j permettent de faire fonctionner l'Algorithme 28.3 correctement selon la Proposition 28.4. On adjoint aux mauvaises valeurs de (a_0, ..., a_{n-1}) celles qui empêchent le bon fonctionnement de l'Algorithme 28.5 de remontée. Ceci détermine Z_{λ,b}. Avec ces choix, la correction de l'algorithme et son coût sont des conséquences des propositions 28.4 et 28.7. ■

## Comparaison avec les bases de Gröbner

Arrivé à la fin de cette partie, nous disposons de deux méthodes, et d'estimations de complexité fournies par le théorème ci-dessus et par le Théorème 26.15 et son Corollaire 26.16. Il est naturel de souhaiter comparer ces résultats. Il faut cependant prendre des précautions : tout d'abord on ne compare que des bornes supérieures de complexité, et non la complexité réelle du calcul. Ensuite, ces deux résultats de complexité ne sont pas établis dans le même modèle de calcul : dans le cas des bases standard, le résultat est toujours correct et le système de polynômes est donné en représentation dense, alors que pour la résolution géométrique le comportement est probabiliste mais on peut tirer parti d'un DAG calculant efficacement les polynômes en entrée. Il faut donc garder à l'esprit que, si d est une borne sur les degrés de f_1, ..., f_n, la complexité d'évaluation L peut varier de O(1) à s fois le nombre $\binom{n+d}{d}$ de monômes homogènes de degré d en n + 1 variables.

Une fois ceci posé, on peut se placer dans la situation simplifiée où les degrés des polynômes (f_1, ..., f_n) sont tous égaux à un d ≥ 2 fixé, et considérer les logarithmes des bornes de complexité pour n → ∞. L'estimation de complexité des bases standard de la Section 26.6 donne

$$ \theta n(d \log d - (d-1)\log(d-1)) + O(\log n) $$

qu'il s'agit de comparer à celle du théorème précédent

$$ 2 \log \delta_n + \log L + O(\log n) = 2n \log d + O(\log n), $$

puisque $\log \binom{n+d}{d} = d \log n + O(1)$. Les ordres de grandeurs sont donc les mêmes, mais dans ce régime asymptotique, cette seconde estimation est légèrement inférieure à la première, même si $\theta = 2$, comme on le voit en utilisant $\log(d-1) < \log d$.

## Test à zéro des DAG

Le Lemme 28.1 donne une condition pour garantir qu'un résultat calculé par l'algorithme de résolution géométrique est correct. Si la condition n'est pas satisfaite, alors on peut soupçonner la suite des polynômes en entrée de ne pas être régulière réduite, avec une forte probabilité. Il est possible de borner cette probabilité, et renvoyons le lecteur aux notes de fin de chapitre. Il est bien sûr possible de vérifier les hypothèses avec des calculs de base standard, mais avec un coût qui dépasse celui de l'algorithme de résolution géométrique. Nous abordons ici une facette du problème, qui soulève à l'heure actuelle toujours d'importantes questions théoriques.

Pour savoir si $f_1, \dots, f_n$ est une suite régulière, la première question à se poser est de savoir si $f_1$ est nul ou non. Afin de simplifier un peu la présentation, nous
avons considéré connus les degrés des polynômes. Néanmoins déterminer le degré d'un polynôme représenté par un DAG n'est pas une tâche aisée. En fait, sous réserve de connaître une borne sur le degré, elle se ramène au test à zéro d'un autre DAG. Pour déterminer si $f_2$ est diviseur de zéro ou non modulo $(f_1)$, sous réserve d'avoir la position de Noether pour $(f_1)$, on est ramené à tester si le résultant $\text{Res}_{X_n}(f_1, f_2)$ est nul ou non (voir le Corollaire 27.14). Si $f_1$ et $f_2$ sont donnés par un DAG de complexité L et que les degrés $d_1$ et $d_2$ sont connus, alors ce résultant peut être représenté par un DAG de complexité $\text{LO}(d_1 + d_2) + O((d_1 + d_2)^4)$ en utilisant l'algorithme de Berkowitz (Théorème 8.9). Et on est ainsi ramené au test à zéro d'un DAG de complexité qui dépend de L et des degrés $d_i$. Plus généralement, on peut penser qu'on exécute l'algorithme de résolution géométrique en conservant les $\lambda_j$ et les $a_j$ comme des variables et en utilisant des DAG pour représenter tous les polynômes. On peut alors montrer que la vérification des hypothèses $(H_1)-(H_3)$ se ramène à des tests à zéro de DAG de tailles $L(n\delta_n)^{O(1)}$.

**Définition 28.2** Soient $\mathcal{P} \subseteq k[X_1, \dots, X_n]$ un ensemble de polynômes et $\mathcal{Q} \subseteq k^n$. On dit que l'ensemble $\mathcal{Q}$ est *questeur* pour $\mathcal{P}$ si aucun polynôme de $\mathcal{P}$ non nul ne s'annule identiquement sur $\mathcal{Q}$. Ceci revient à dire que l'évaluation sur $\mathcal{Q}$ est un test à zéro pour les polynômes de $\mathcal{P}$.

Ainsi, la question du test à zéro des DAG est résolue si on peut trouver des ensembles questeurs de taille convenable. Une première famille d'ensembles questeurs, dont la taille est malheureusement exponentielle en $n$, est donnée par le résultat suivant.

**Proposition 28.9** Soient $\mathcal{E}_1, \dots, \mathcal{E}_n \subseteq k$ des parties de cardinal supérieur à $d+1$. Alors $\mathcal{Q} = \mathcal{E}_1 \times \dots \times \mathcal{E}_n \subseteq k^n$ est un ensemble questeur pour les polynômes de $k[X_1, \dots, X_n]$ de degrés au plus $d$.

*Démonstration.* Procédons par récurrence sur $n$. Pour $n=1$, un polynôme de degré au plus $d$ qui admet $d+1$ racines est nul. Remarquons que ceci est vrai généralement pour les polynômes à coefficients dans un anneau unitaire car la démonstration repose sur la division euclidienne par $X-x$ si $x$ est une racine. Supposons le résultat vrai au rang $n-1$. Écrivons le $p = \sum p_i X_n^i$ avec $p_i \in k[X_1, \dots, X_{n-1}]$. Soit $x \in \mathcal{E}_n$, alors $p(X_1, \dots, X_{n-1}, x)$ est nul car il s'annule sur $\mathcal{E}_1 \times \dots \times \mathcal{E}_{n-1}$. Le polynôme $p$ a au moins $d+1$ racines en $X_n$ donc il est nul. ■

Pour des polynômes creux (c'est-à-dire dont peu de monômes ont un coefficient non nul), on peut trouver d'autres ensembles questeurs plus adaptés. Soit $\mathcal{A} \subseteq \mathbb{N}^n$, et considérons $W_{\mathcal{A}} = \{\sum_{a \in \mathcal{A}} c_a X^a \mid c_a \in \mathcal{K}\}$, l'ensemble des polynômes de $k[X_1, \dots, X_n]$ à supports dans $\mathcal{A}$. On a le résultat suivant que nous ne prouvons pas :

**Proposition 28.10** L'ensemble $2^{\mathcal{A}} = \{(2^{a_1}, \dots, 2^{a_n}) \mid (a_1, \dots, a_n) \in \mathcal{A}\}$ est questeur pour $W_{\mathcal{A}}$.

Par ailleurs, mentionnons qu'il est conjecturé que $\mathcal{A}$ est un ensemble questeur pour
$W_A$. Pour conclure, mentionnons qu'il existe des ensembles questeurs de tailles polynomiales. Cependant on ne sait pas les construire efficacement d'une façon déterministe.

**Proposition 28.11** Soit $W(D, n, L)$ l'ensemble des polynômes en $n$ variables de degré au plus $D$ et de complexité d'évaluation au plus $L$. Fixons $\Gamma \subset k$ de cardinal $2L(D+1)^2$ et $m = 6(L+1)(L+n+1)$. Soient $\tau(D, n, L, \Gamma)$ l'ensemble des $m$-uplets de $n$-uplets d'éléments de $\Gamma$ et $\xi(D, n, L, \Gamma)$ celui des éléments de $\tau(D, n, L, \Gamma)$ qui ne sont pas questeurs pour $W(D, n, L)$. Alors on a :

$$ \frac{|\xi(D, n, L, \Gamma)|}{|\Gamma|^{nm}} \le \frac{1}{|\Gamma|^{m/6}} $$

Notons que le membre droit de cette dernière inégalité est majoré par $1/264000$ dans les cas non triviaux. Les algorithmes utilisant des DAG peuvent alors faire intervenir deux types de complexité. D'une façon informelle, la *complexité non uniforme* revient à dire, « au prix d'un précalcul, la complexité est ... ». Ce précalcul revient dans le cas présent à trouver un ensemble questeur. L'autre complexité, dite probabiliste, revient à dire « si on choisit un ensemble questeur au hasard ... ». Des études détaillées de ce aspects se trouvent dans les travaux mentionnés ci-dessous.

## Notes

L'algorithme de résolution géométrique est aussi appelé parfois l'algorithme *Kronecker* en hommage aux travaux de Kronecker sur la résolution des systèmes algé-briques [Kro82]. Ce chapitre simplifie une version déjà simplifiée présentée dans l'article de Durvye et Lecerf [DL07]. Une présentation plus détaillée dans le cas af-fine, comprenant des exemples et des illustrations, se trouve aussi dans la thèse de Durvye [Dur08]. L'analyse de complexité reprend celle de l'article de Giusti, Lecerf et Salvy [GLS01]. Une implémentation en C++ est disponible dans la librairie `GEOM-SOLVEX` de `MATHEMAGIX`. Les résultats présentés dans ce chapitre sont en fait le fruit d'une série de travaux initiés par Giusti, Heintz, Morais et Pardo au début des années 90 [FGS95; GH93; GHS93; Giu+95; Giu+97; Giu+98; Hei+00; HMW01; KP96]. Une présentation historique est donnée dans l'introduction de l'article de Durvye et Lecerf [DL07].

Dans le cas où $k = \mathbb{Q}$ et $f_1, \dots, f_n$ une suite régulière réduite, une bonne stratégie de calcul consiste à appliquer d'abord l'algorithme de résolution géométrique modulo un nombre premier suffisamment grand pour ne pas annuler les dénominateurs des nombres intervenant lors du calcul sur $\mathbb{Q}$, mais pas trop grand non plus pour que l'arithmétique modulaire soit rapide. Ensuite il est possible d'adapter l'algorithme de remontée de Hensel pour remonter des entiers $p$-adiques et reconstruire la résolution géométrique sur $\mathbb{Q}$. Nous renvoyons à l'article de Giusti, Lecerf et Salvy [GLS01] ainsi qu'à la thèse de Schost [Sch01] pour plus de détails.

Si la suite n'est pas régulière, l'ensemble des solutions du système doit être dé-composé en une union de variétés de différentes dimensions. On parle alors de *décomposition équidimensionnelle*. Si la suite n'est pas réduite, alors il faut utiliser des
généralisations de la méthode de Newton en présence de racines multiples, comme par exemple des techniques dites de déflation. Plusieurs articles traitent de ces questions [Jer+04; JPS01; JS00; JS02; Lec00; Lec02; Lec03]. Une courte description de ces travaux de généralisation se trouve aussi dans l'introduction de l'article de Durvye et Lecerf [DL07].

La preuve originale de la Proposition 28.10 se trouve dans l'article de Risler et Ronga [RR90]. Celle de la Proposition 28.11 peut être trouvée dans l'article de Heintz et Schnorr [HS82].

Bibliographie

DL07 DURVYE, Clémence et Grégoire LECERF (2007). « A concise proof of the Kronecker polynomial system solver from scratch ». In : *Expositiones Mathematicae*, vol. 26, n°2, p. 101-139.

Dur08 DURVYE, Clémence (2008). « Algorithmes pour la décomposition primaire des idéaux polynomiaux de dimension nulle donnés en évaluation ». Thèse de doctorat. Université de Versailles Saint-Quentin-en-Yvelines.

FGS95 FITCHAS, N., M. GIUSTI et F. SMIETANSKI (1995). « Sur la complexité du théorème des zéros ». In : *Approximation and optimization in the Caribbean, II (Havana, 1993)*. Vol. 8. Approximation & optimization. Frankfurt am Main : P. Lang, p. 274-329.

GH93 GIUSTI, Marc et Joos HEINTZ (1993). « La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial ». In : *Computational algebraic geometry and commutative algebra (Cortona, 1991)*. Vol. XXXIV. Sympos. Math. Cambridge : Cambridge Univ. Press, p. 216-256.

GHS93 GIUSTI, Marc, Joos HEINTZ et Juan SABIA (1993). « On the efficiency of effective Nullstellensätze ». In : *Computational Complexity*, vol. 3, n°1, p. 56-95.

Giu+95 GIUSTI, M., J. HEINTZ, J. E. MORAIS et L. M. PARDO (1995). « When polynomial equation systems can be "solved" fast? » In : *Applied algebra, algebraic algorithms and error-correcting codes (Paris, 1995)*. Vol. 948. Lecture Notes in Computer Science. Springer-Verlag, p. 205-231.

Giu+97 GIUSTI, M., K. HÄGELE, J. HEINTZ, J. L. MONTAÑA, J. E. MORAIS et L. M. PARDO (1997). « Lower bounds for Diophantine approximations ». In : *Journal of Pure and Applied Algebra*, vol. 117/118, p. 277-317.

Giu+98 GIUSTI, M., J. HEINTZ, J. E. MORAIS, J. MORGENSTERN et L. M. PARDO (1998). « Straight-line programs in geometric elimination theory ». In : *Journal of Pure and Applied Algebra*, vol. 124, n°1-3, p. 101-146.

GLS01 GIUSTI, Marc, Grégoire LECERF et Bruno SALVY (2001). « A Gröbner free alternative for polynomial system solving ». In : *Journal of Complexity*, vol. 17, n°1, p. 154-211.

Hei+00 HEINTZ, Joos, Teresa KRICK, Susana PUDDU, Juan SABIA et Ariel WAISSBEIN (2000). « Deformation techniques for efficient polynomial equation solving ». In : *Journal of Complexity*, vol. 16, n°1, p. 70-109.
HMW01 HEINTZ, Joos, Guillermo MATERA et Ariel WAISSBEIN (2001). « On the time-space complexity of geometric elimination procedures ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 11, n°4, p. 239-296.

HS82 HEINTZ, J. et C.-P. SCHNORR (1982). « Testing polynomials which are easy to compute ». In : *Logic and algorithmic (Zurich, 1980)*. Vol. 30. Monograph. Enseign. Math. Geneva : Univ. Genève, p. 237-254.

Jer+04 JERONIMO, Gabriela, Teresa KRICK, Juan SABIA et Martín SOMBRA (2004). « The computational complexity of the Chow form ». In : *Foundations of Computational Mathematics*, vol. 4, n°1, p. 41-117.

JPS01 JERONIMO, Gabriela, Susana PUDDU et Juan SABIA (2001). « Computing Chow forms and some applications ». In : *Journal of Algorithms*, vol. 41, n°1, p. 52-68.

JS00 JERONIMO, Gabriela et Juan SABIA (2000). « Probabilistic equidimensional decomposition ». In : *Comptes Rendus des Séances de l'Académie des Sciences. Série I. Mathématique*, vol. 331, n°6, p. 485-490.

JS02 — (2002). « Effective equidimensional decomposition of affine varieties ». In : *Journal of Pure and Applied Algebra*, vol. 169, n°2-3, p. 229-248.

KP96 KRICK, T. et L. M. PARDO (1996). « A computational method for Diophantine approximation ». In : *Algorithms in algebraic geometry and applications (Santander, 1994)*. Vol. 143. Progress in Mathematics. Birkhäuser, p. 193-253.

Kro82 KRONECKER, Leopold (1882). « Grundzüge einer arithmetischen Theorie der algebraischen Grössen ». In : *Journal für die Reine und Angewandte Mathematik*, vol. 92, p. 1-122.

Lec00 LECERF, Grégoire (2000). « Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions ». In : *ISSAC'00 : International Symposium on Symbolic and Algebraic Computation*. ACM, p. 209-216.

Lec02 — (2002). « Quadratic Newton iteration for systems with multiplicity ». In : *Foundations of Computational Mathematics*, vol. 2, n°3, p. 247-293.

Lec03 — (2003). « Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers ». In : *Journal of Complexity*, vol. 19, n°4, p. 564-596.

RR90 RISLER, Jean-Jacques et Felice RONGA (1990). « Testing polynomials ». In : *Journal of Symbolic Computation*, vol. 10, n°1, p. 1-5.

Sch01 SCHOST, Éric (2001). « Sur la résolution des systèmes polynomiaux à paramètres ». Thèse de doctorat. Palaiseau, France : École polytechnique.
# VI

## Sommation et intégration de suites et fonctions spéciales

29 Sommation hypergéométrique, solutions hypergéométriques ... 527

29.1 Sommation hypergéométrique indéfinie. Algorithme de Gosper

29.2 Sommation hypergéométrique définie. Algorithme de Zeilberger

29.3 Solutions hypergéométriques. Algorithme de Petkovšek

30 Équations fonctionnelles linéaires et polynômes tordus ... 543

30.1 Polynômes non commutatifs comme opérateurs linéaires

30.2 Morphismes entre anneaux de polynômes tordus

30.3 Division euclidienne

30.4 Recherche de solutions et factorisation d'opérateurs

30.5 Algorithme d'Euclide

30.6 Relations de contiguïté

31 Algèbres de Ore ... 561

31.1 Algèbres de Ore rationnelles

31.2 Idéal annulateur et module quotient

31.3 Bases de Gröbner pour les idéaux à gauche

31.4 Module quotient et dimension de l'espace des solutions

31.5 Les fonctions $\partial$-finies et leurs clôtures

32 Sommation et intégration symboliques des fonctions spéciales ... 579

32.1 Expression du télescopage créatif

32.2 L'algorithme de sommation $\partial$-finie définie sur un exemple

32.3 Description des algorithmes de sommation et intégration $\partial$-finies

32.4 Bases de Gröbner de modules et découplage de systèmes
<figure><img src="image_81.png" /></figure>
# 29. Sommation hypergéométrique et solutions hypergéométriques de récurrences

## Résumé

Le Chapitre 16 a indiqué comment un petit noyau d'algorithmes relativement simples permet de trouver les solutions polynomiales et rationnelles de récurrences linéaires. Nous appliquons ici tout cet ensemble d'algorithmes au calcul de sommes indéfinies et définies de suites hypergéométriques et à la recherche de solutions hypergéométriques de récurrences linéaires. La suite de cet ouvrage prolongera les méthodes de ce chapitre aux questions de sommation et d'intégration de suites et fonctions spéciales plus générales, solutions de systèmes d'équations différentielles et de relations de récurrence d'ordre quelconque.

Voici deux sommes classiques, la première due à Gauss, la seconde à Dixon, dont le traitement algorithmique est détaillé dans ce chapitre :

$$ 
\begin{gather*}
\sum_{k=0}^{\infty} \frac{(a)_k (b)_k}{(c)_k k!} = \frac{\Gamma(c-a-b)\Gamma(c)}{\Gamma(c-a)\Gamma(c-b)}, \\
\sum_{k \in \mathbb{Z}} (-1)^k \binom{a+b}{a+k} \binom{a+c}{c+k} \binom{b+c}{b+k} = \frac{(a+b+c)!}{a! b! c!}.
\end{gather*}
$$

Dans la première identité, valide pour $\text{Re}(c-a-b) > 0$ pour assurer la convergence de la série, $(x)_n$ représente le produit $x(x-1)\cdots(x-n+1)$ et $\Gamma(s)$ est la fonction obtenue par prolongement analytique à partir de la formule

$$ \Gamma(x) = \int_{0}^{\infty} t^{x-1} e^{-t} dt \quad \text{pour } \text{Re} x > 0. $$

Pour la seconde identité, on adopte la convention que les coefficients binomiaux $\binom{n}{m}$ sont nuls lorsque $m < 0$ ou $m > n$.
Pour justifier de telle sommes définies — où toutes les valeurs possibles de l'indice de sommation sont parcourues —, il serait agréable de pouvoir faire appel, comme dans le cas de l'intégration où l'on recherche une primitive, à une somme indéfinie — c'est-à-dire vue comme fonction de sa borne supérieure — et de voir la somme définie comme différence de deux évaluations. Un cadre simple serait celui où, tout comme les sommants dans ces deux exemples, une telle somme indéfinie serait hypergéométrique — solution d'une récurrence linéaire d'ordre 1, voir la Définition 29.1 ci-dessous. Cependant, pour nos deux exemples, il n'existe pas de somme indéfinie hypergéométrique, et c'est le cas général. Les deux sommes définies peuvent néanmoins être calculées automatiquement, si l'on prend la peine de rechercher une suite auxiliaire qui, elle, admet une somme indéfinie hypergéométrique.

Une chaîne complète d'algorithmes permettant de trouver les membres droits des identités ci-dessus est détaillée dans ce chapitre : l'algorithme de Gosper de la Section 29.1 décide de l'existence d'une somme indéfinie hypergéométrique pour un sommant hypergéométrique ; en modifiant convenablement un sommant hypergéométrique, l'algorithme de Zeilberger de la Section 29.2 trouve, quand il en existe une, une récurrence vérifiée par une somme hypergéométrique définie. Pour ne pas s'arrêter sur une récurrence et revenir à une forme explicite, l'algorithme de Petkovšek de la Section 29.3 obtient toutes les solutions d'une récurrence linéaire qui sont données comme combinaisons linéaires de termes hypergéométriques.

## 29.1 Sommation hypergéométrique indéfinie. Algorithme de Gosper

La recherche de formes closes pour la sommation est souvent naturellement posée en termes de suites hypergéométriques. Après quelques définitions et propriétés de ces suites, nous abordons leur sommation indéfinie.

### Suites hypergéométriques

**Définition 29.1** On dit qu'une suite $(u_n)$ est hypergéométrique s'il existe deux polynômes non nuls P et Q tels que pour tout $n \in \mathbb{N}$,

$$Q(n)u_{n+1} = P(n)u_n. \qquad (29.1)$$

Autrement dit, elle est polynomiallement récurrente et vérifie une récurrence linéaire d'ordre 1.

Cette définition mérite quelques observations :

- $u_{n+1}$ est totalement déterminé par $u_n$ dès lors que $Q(n) \neq 0$.

- Il n'est pas exigé que $pgcd(P, Q) = 1$ : en particulier, si un entier $n_0$ est zéro commun de P et Q, les termes $u_{n_0}$ et $u_{n_0+1}$ sont indépendants l'un de l'autre.

- Si P s'annule sur un entier $n_0$ sans que Q ne s'annule sur aucun entier $n \ge n_0$, alors $u_n = 0$ dès lors que $n > n_0$.

**Exercice 29.1** — Vérifier que la suite définie pour tout $n \in \mathbb{N}$ par $u_n = \binom{5}{n}$ satisfait
pour tout $n \in \mathbb{N}$ la relation de récurrence

$$ (n+1)u_{n+1} = (5-n)u_n. \qquad (29.2) $$

— Considérer la suite définie pour $n \ge 6$ par $v_6 = 1$ et l'équation (29.2). Calculer $v_7, v_8$ et $v_9$.

— On prolonge $v$ par $v_0 = \cdots = v_5 = 1$. Donner une relation de récurrence de la forme (29.1) montrant que $v$ est hypergéométrique.

— Même question pour la suite $w$ définie par $w_n = u_n$ si $n \le 5$ et $w_n = v_n$ si $n \ge 6$.

La récurrence (29.1) étant d'ordre 1, il est facile d'en écrire la solution générale au moins lorsque $Q$ n'a pas de racine entière positive :

$$ u_n = u_0 \left( \frac{\ln(P)}{\ln(Q)} \right)^n \frac{\prod_{P(\alpha)=0} (-\alpha)(-\alpha+1)\cdots(-\alpha+n-1)}{\prod_{Q(\beta)=0} (-\beta)(-\beta+1)\cdots(-\beta+n-1)}, $$

où $\ln(p)$ désigne le coefficient de tête du polynôme $p$ et où chaque produit doit être compris avec répétition des racines selon leurs multiplicités. Ici, on peut sans perte de généralité supposer pgcd($P, Q$) = 1.

Lorsque $Q$ n'a pas de zéro dans $\mathbb{N}$, la solution $(u_n)$ de l'équation (29.1) est totalement déterminée par la valeur $u_0$, qui joue le rôle de condition initiale. Sinon, la suite $(u_n)$ est déterminée par ses valeurs en $n=0$ et en les $n \in \mathbb{N}$ tels que $Q(n-1) = 0$.

Les suites hypergéométriques jouent un rôle important en analyse classique, où elles apparaissent comme coefficients de Taylor des séries introduites par la définition suivante.

**Définition 29.2** On appelle série hypergéométrique généralisée et on note

$$ {}_pF_q\left(\begin{array}{c} a_1, \dots, a_p \\ b_1, \dots, b_q \end{array} \middle| x \right) $$

la série

$$ \sum_{n \ge 0} \frac{(a_1)_n \cdots (a_p)_n}{(b_1)_n \cdots (b_q)_n} \frac{x^n}{n!}, $$

où la notation $(a)_n$ représente le produit $a(a-1)\cdots(a-n+1)$, appelé symbole de Pochhammer, qui s'exprime aussi comme $\Gamma(a+n)/\Gamma(a)$.

Des cas particuliers de séries qui s'expriment à l'aide de séries hypergéométriques généralisées sont les séries $\exp(x)$, $\log(1+x)$, les dilogarithmes et polylogarithmes, les fonctions $J_v(x)$ de Bessel, les fonctions d'Airy $Ai(x)$, etc. Ainsi :

$$ \exp(x) = {}_0F_0\left(\begin{array}{c} -1 \\ -1 \end{array}\middle| x\right), $$

$$ \log(1+x) = {}_2F_1\left(\begin{array}{c} 1, 1 \\ 2 \end{array}\middle| -x\right), $$
$$J_v(x) = \left(\frac{x}{2}\right)^v \frac{1}{\Gamma(v+1)} {}_0F_1\left(-v+1 \middle| x\right),$$ $$\mathrm{Ai}(x) = -\frac{x^{\frac{3}{2}}\Gamma(2/3)}{2\pi} {}_0F_1\left(-\frac{x^3}{9} \middle| x\right) + \frac{\sqrt{3}}{3\Gamma(2/3)} {}_0F_1\left(-\frac{x^3}{2/3} \middle| x\right).$$

**Exercice 29.2** Récrire l'identité de Dixon à l'aide de l'évaluation d'une série $_3F_2$ en 1.

## Terme hypergéométrique

La définition suivante permet de donner une idéalisation algébrique commode des suites numériques.

**Définition 29.3** Un *anneau à différence* est un anneau commutatif A muni d'un endomorphisme d'anneau $\sigma$. Un *corps à différence* est un anneau à différence qui est un corps.

**Exemple 29.1** Un exemple simple est le corps usuel de fractions rationnelles $\mathbb{Q}(g)$ muni du morphisme donné par $\sigma(g) = g+1$: le terme $g$ s'identifie à la suite de terme général $n$. Cet exemple se prolonge sur le corps $\mathbb{Q}(g, h)$ des fractions rationnelles en deux variables, en étendant le morphisme $\sigma$ par $\sigma(h) = (g+1)h$: le terme $h$ s'identifie à la suite de terme général $n!$, puisque $(n+1)! = (n+1)n!$.

**Exercice 29.3** Donner une construction analogue d'un corps à différence permettant de représenter la suite $H_n$ de terme général $1 + \frac{1}{2} + \cdots + \frac{1}{n}$.

Dans la suite de cet ouvrage, nous préférons noter les éléments d'anneaux à différence à l'aide de la notation par indice utilisée pour les suites (ou encore à l'aide de la notation parenthésée pour les applications générales). Nous mentionnons soigneusement lorsqu'il ne s'agira pas de suites : ainsi, nous parlerons de $\mathbb{Q}(n, n!, H_n)$ et écrirons $H_{n+5}$ plutôt que $\sigma^5(H)$. Nous avons alors la définition suivante, à comparer avec la définition d'une *suite hypergéométrique*.

**Définition 29.4** Soit A un anneau à différence contenant $\mathbb{Q}(n)$. Un élément $t_n$ de A est dit *terme hypergéométrique* s'il existe une fraction rationnelle non nulle $R(n)$ telle que $t_{n+1}/t_n = R(n)$.

**Exemple 29.2** Considérons la récurrence de la forme (29.1) obtenue pour $Q(n) = n(n-1)(n-2)$ et $P(n) = Q(n)(n-2)$. Toutes les suites $(u_n)$ solutions sont hypergéométriques, et de la forme

$$u_n = \begin{cases} \lambda_n & \text{si } n = 0, \dots, 2, \\ \lambda_3(n-3)! & \text{si } n \ge 3, \end{cases}$$
pour des constantes arbitraires $\lambda_0, \dots, \lambda_3$. L'égalité $u_{n+1}/u_n = P(n)/Q(n) = n - 2$ n'est valable en général que pour $n \ge 3$. Cependant, toutes ces suites solutions correspondent au même terme hypergéométrique $h$ obtenu dans le corps à différence $\mathbb{Q}(g, h)$, donné par le morphisme $\sigma$ satisfaisant à $\sigma(g) = g + 1$ et $\sigma(h)/h = g - 2$, sans notion de domaine de validité pour la formule.

## Algorithme de Gosper

Étant donnée une suite hypergéométrique notée $(u(n))$, le problème de sommation indéfinie hypergéométrique de $u(n)$ consiste à déterminer s'il existe une autre suite hypergéométrique $(U(n))$ telle que $U(n+1) - U(n) = u(n)$, et si oui, la calculer. Nous commençons par résoudre le problème analogue pour les termes hypergéométriques. Une observation simple est formulée dans le lemme suivant.

**Lemme 29.1** Si $U(n)$ est un terme hypergéométrique et L un opérateur de récurrence linéaire à coefficients polynomiaux, alors il existe une fraction rationnelle $r(n)$ telle que $(L \cdot U)(n) = r(n)U(n)$.

*Démonstration.* Si $U(n)$ est hypergéométrique, par définition, il existe une fraction rationnelle $R(n)$ telle que $U(n+1) = R(n)U(n)$ et donc par récurrence $U(n+k) = R(n+k-1)\dots R(n)U(n)$ pour tout $k$. Le résultat s'en déduit en additionnant les contributions. ■

Ce lemme entraîne qu'une somme hypergéométrique $U(n)$ de $u(n)$ doit être le produit de $u(n)$ par une fraction rationnelle $R(n)$. En effet, dans ce cas, le Lemme 29.1 a pour conséquence l'égalité $u(n) = U(n+1) - U(n) = \bar{R}(n)U(n)$ pour une fraction rationnelle $\bar{R}$; il suffit ensuite de considérer $R(n) = 1/\bar{R}(n)$. La division terme à terme de la relation de récurrence $U(n+1) - U(n) = u(n)$ par $u(n)$ réduit alors le calcul à celui de la recherche de solutions rationnelles de l'équation inhomogène d'ordre 1

$$R(n+1) \frac{u(n+1)}{u(n)} - R(n) = 1, \qquad (29.3)$$

problème traité au Chapitre 16, particulièrement en Section 16.4. Cette méthode, connue sous le nom d'algorithmme de Gosper, est résumée dans l'Algorithme 29.1. Notons que puisque nous disposons d'un algorithme de décision pour la résolution rationnelle, nous obtenons un algorithme de décision aussi pour la sommation indéfinie hypergéométrique : lorsque l'algorithmme renvoie $\#$, c'est une preuve qu'aucune somme hypergéométrique n'existe.

**Exercice 29.4** Montrer qu'il y a unicité de la somme indéfinie hypergéométrique d'un terme $u_n$ si et seulement si $u_n$ n'est pas rationnel. ■

**Exemple 29.3** Nous voulons calculer une somme indéfinie hypergéométrique du
**Entrée** Un terme hypergéométrique $f(n)$.

**Sortie** Un terme hypergéométrique $g(n)$ tel que $g(n+1) - g(n) = f(n)$, ou le symbole $\neq$.

1. Soit $\rho(n)$ la fraction rationnelle $f(n+1)/f(n)$.

2. Résoudre la récurrence $\rho(n)R(n+1) - R(n) = 1$ par l'Algorithme 16.7.

3. Si la résolution fournit une solution, renvoyer $R(n)f(n)$, sinon renvoyer $\neq$.

**Algorithme 29.1** – Algorithme de Gosper pour la sommation hypergéométrique indéfinie.

terme $\frac{2^n(n-1)}{n(n+1)}$. Pour ceci, nous résolvons (29.3), qui prend ici la forme

$$2n^2 R(n+1) - (n-1)(n+2)R(n) = (n-1)(n+2),$$

et recherchons ses solutions rationnelles. Nous utilisons l'algorithme d'Abramov, en commençant par l'Algorithme 16.6 pour une borne sur les dénominateurs possibles. Ici, le coefficient de tête décalé vers l'arrière de l'ordre $1, (n-1)^2$, ne peut avoir de pgcd commun avec le coefficient de queue décalé vers l'avant de $h \in \mathbb{N}$, $(n+h-1)(n+h+2)$, que pour $h=0$. Nous avons donc, sans calcul de résultant, que l'Algorithme 16.6 trouve $m=1, h_1=0$, et renvoie $Q(n) = n-1$. Écrivons $R(n) = P(n)/(n-1)$ pour un polynôme $P$ à déterminer. Par changement de fonction inconnue, la récurrence devient

$$2nP(n+1) - (n+2)P(n) = (n-1)(n+2).$$

Comme $n+2$ divise deux des termes polynomiaux, il divise le troisième, si bien que $P$ s'écrit sous la forme $P(n) = (n+1)Q(n)$ pour un polynôme $Q$ à déterminer. Par un second changement de fonction inconnue, la récurrence devient

$$2nQ(n+1) - (n+1)Q(n) = n-1.$$

Si $Q(n) \sim \lambda n^\alpha$ à l'infini, alors $\lambda n^{\alpha+1} \sim n$, et donc $\alpha = 0$, $Q(n) = \lambda = 1$. Nous avons donc finalement trouvé $R(n)$ sous la forme $(n+1)/(n-1)$, ce qui fournit la somme indéfinie hypergéométrique $2^n/n$.

## Lien avec la sommation des suites

L'Algorithme 29.3, que nous allons décrire, donne la somme indéfinie hypergéométrique, quand elle existe, d'un terme hypergéométrique. Tout d'abord nous faisons le lien avec le problème initial sur les suites hypergéométriques, dont les termes hypergéométriques ne sont qu'une idéalisation. En particulier, nous allons rectifier l'image selon laquelle une somme hypergéométrique se réduit à un multiple rationnel de la suite sommée.
Pour une suite $(u_n)_{n \in \mathbb{N}}$ solution de (29.1), introduisons la fraction rationnelle $\rho = P/Q \in \mathbb{Q}(n)$, dont les pôles sont des zéros du polynôme $Q(n)$. Soit $R$ la fraction rationnelle calculée dans l'Algorithme 29.1 de Gosper. En réinterprétant les fractions rationnelles comme des fonctions, nous avons :

- $u_{n+1} = \rho(n)u_n$ si $Q(n) \neq 0$,

- $\rho(n)R(n+1) - R(n) = 1$ si $n$ est dans l'intersection des domaines de définition de $\rho(n)$, $R(n)$ et $R(n+1)$.

Définissons une suite $\tilde{U}$ par

$$ \tilde{U}_n = \begin{cases} R(n)u_n & \text{si } n \text{ est dans le domaine de définition de } R, \\ 0 & \text{sinon.} \end{cases} $$

Nous avons alors :

$$ \tilde{U}_{n+1} - \tilde{U}_n = R(n+1)u_{n+1} - R(n)u_n = (\rho(n)R(n+1) - R(n))u_n = u_n, $$

où la première égalité est vérifiée si $n$ et $n+1$ sont dans le domaine de définition de $R$, et où les suivantes le sont si de plus $Q(n) \neq 0$. Soit $S$ l'ensemble (fini) des zéros de $Q(n)$ et des pôles de $R(n)$ et de $R(n+1)$ dans $\mathbb{N}$, si bien qu'en résumé :

$$ \tilde{U}_{n+1} - \tilde{U}_n = u_n \quad \text{si } n \in \mathbb{N} \setminus S. $$

Définissons deux suites $(\phi_n)$ et $(\Phi_n)$ par

$$ \phi_n = \begin{cases} u_n - (\tilde{U}_{n+1} - \tilde{U}_n) & \text{si } n \in S, \\ 0 & \text{sinon,} \end{cases} $$

et $\Phi_n = \sum_{i=0}^{n-1} \phi_i$. Cette dernière suite est constante par morceaux et la partition de $\mathbb{N}$ servant à sa définition est finie et calculable. Posons finalement

$$ U_n = \tilde{U}_n + \Phi_n, $$

de sorte que pour tout $n \in \mathbb{N}$, la relation $U_{n+1} - U_n = \tilde{U}_{n+1} - \tilde{U}_n + \phi_n = u_n$ est vérifiée : cette suite $(U_n)$ est une somme indéfinie sur tout $\mathbb{N}$ de $(u_n)$. Le résultat qui suit résume cette discussion.

**Proposition 29.2** Si une suite hypergéométrique $(u_n)_{n \in \mathbb{N}}$ admet une somme indéfinie hypergéométrique $(U_n)_{n \in \mathbb{N}}$ sur tout $\mathbb{N}$, cette dernière s'écrit sous la forme

$$ U_n = [[R(n)u_n]] + \Phi_n $$

où :

- la notation $[[\dots]]$ est utilisée pour étendre en une suite totale sur $\mathbb{N}$ une suite partiellement définie, en la prolongeant par 0,

- la suite $(\Phi_n)_{n \in \mathbb{N}}$ est une suite constante par morceaux définie sur une partition finie de $\mathbb{N}$ obtenue à l'aide des pôles de $R$ et zéros de $Q$.
**Exemple 29.4** L'Algorithme 29.1 de Gosper permet également de donner des réponses négatives. Voici en détail comment il permet de prouver par l'absurde que la suite des $S(n) := \sum_{k=1}^{n} 1/k!$ n'est pas hypergéométrique.

Supposons que $S(n)$ est hypergéométrique. Alors, elle doit être le produit de $1/n!$ par une fraction rationnelle $r(n)$. Cette fraction est donc solution de la récurrence

$$S(n+1) - S(n) = \frac{1}{(n+1)!} = \frac{r(n+1)}{(n+1)!} - \frac{r(n)}{n!}.$$

En chassant les dénominateurs, il reste $r(n+1) - (n+1)r(n) = 1$. Le résultat de l'Algorithme 16.6 d'Abramov page 304 montre que $r$ doit être un polynôme : les pôles de plus petite partie réelle de $r$ doivent être des zéros du pgcd, trivial, de 1 et $n+1$. Enfin, $r$ ne peut pas non plus être un polynôme : son terme de plus haut degré ne disparaît pas par évaluation de la récurrence.

## Sommation paramétrée

Soient des termes $u_1(n), \dots, u_s(n)$ hypergéométriques et deux à deux similaires, au sens où tous les rapports $u_i(n)/u_j(n)$ sont rationnels. Il s'agit de déterminer, s'ils existent, un terme hypergéométrique $S(n)$ et des constantes $\lambda_1, \dots, \lambda_s$ telles que

$$S(n+1) - S(n) = \lambda_1 u_1(n) + \dots + \lambda_s u_s(n).$$

Comme toutes les $u_i$ sont similaires à une même suite $u(n)$, le membre droit de (29.3) peut être remplacé par une combinaison linéaire des $\lambda_i$ à coefficients des fractions rationnelles et la méthode de la Section 16.4 page 306 pour les récurrences linéaires inhomogènes paramétrées s'applique.

## 29.2 Sommation hypergéométrique définie. Algorithme de Zeilberger

L'algorithme considéré dans cette section s'applique à des suites $u(n,k)$ dites hypergéométriques en deux variables, c'est-à-dire pour lesquelles

$$\frac{u(n+1,k)}{u(n,k)} \quad \text{et} \quad \frac{u(n,k+1)}{u(n,k)}$$

sont deux fractions rationnelles en $n$ et $k$, au moins en dehors du lieu d'annulation d'un polynôme non nul fixé $Z(n,k)$.

**Exercice 29.5** Vérifier que la suite $u(n,k) = \binom{n}{k}$ est hypergéométrique en ce sens. ■

**Exercice 29.6** Soit une suite hypergéométrique ($u_{n,k}$), donnée par les rapports rationnels $a(n,k) = u_{n+1,k}/u_{n,k}$ et $b(n,k) = u_{n,k+1}/u_{n,k}$. Montrer que les fractions rationnelles $a$ et $b$ vérifient une relation que l'on explicitera. ■

Le problème de sommation définie hypergéométrique est de déterminer si pour une telle suite $(u(n))$, la nouvelle suite de terme général

$$U(n) = \sum_{k} u(n,k)$$
vérifie une récurrence linéaire et si oui, la calculer. L'absence de bornes explicites de sommation signifie que la somme porte en fait sur toutes les valeurs $k \in \mathbb{Z}$, étant entendu que, bien souvent, ces sommes ont en fait un support fini. Bien souvent aussi, l'intervalle de sommation s'arrête aux bornes naturelles de sommation, c'est-à-dire aux indices où par construction la suite et toutes ses décalées par rapport à l'autre indice, n, s'annulent.

**Exemple 29.5** Des sommes simples sont

$$ \sum_k \binom{n}{k} = 2^n \quad \text{et} \quad \sum_k \binom{n}{k}^2 = \binom{2n}{n}. $$

Dans ces deux exemples, pour $k$ en dehors de $\{0, \dots, n\}$, les binomiaux sont nuls. Ainsi, les bornes 0 et $n$ sont naturelles.

Un cas très favorable pour obtenir des sommations explicites est celui où $U(n)$ est elle-même hypergéométrique. Mais pour bien des applications, il est tout aussi utile de trouver une récurrence linéaire à laquelle $U(n)$ obéit. C'est ce que réalise l'algorithme de Zeilberger, par une approche dite de **télescopage créatif**. Cette approche ne garantit cependant pas d'obtenir une relation de récurrence d'ordre minimal pour la somme; elle ne détecte donc pas directement si la somme est elle aussi hypergéométrique. Un test de cette dernière situation se ramène à la recherche de solutions hypergéométriques de récurrences linéaires, problème qui est traité par l'algorithme de Petkovšek en Section 29.3.

### Principe du télescopage créatif

Désignons par $S_n$ et $S_k$ les opérateurs de décalage en $n$ et $k$, de sorte que $(S_n \cdot u)(n,k) = u(n+1,k)$ et $(S_k \cdot u)(n,k) = u(n,k+1)$. On cherche un opérateur de la forme

$$ P(n, S_n) - (S_k - 1)Q(n, k, S_n, S_k), \qquad (29.4) $$

polynomial en $S_n$ et $S_k$, et qui annule la suite $(u(n,k))$ à sommer. Une fois un tel opérateur trouvé, la sommation sur $k$ est aisée, et, sous l'hypothèse simplificatrice de bornes naturelles, conduit à l'égalité

$$ (P(n, S_n) \cdot U)(n) = 0. \qquad (29.5) $$

**Exemple 29.6** En suivant ce modèle, voici une preuve compliquée que

$$ U(n) = \sum_k \binom{n}{k} = 2^n. \qquad (29.6) $$
Le point de départ est l'identité du triangle de Pascal

$$ \binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k}, $$

qui s'interprète en l'opérateur annulateur

$$ S_n S_k - S_k - 1. \qquad (29.7) $$

Ce dernier se récrit

$$ (S_n - 2) + (S_k - 1)(S_n - 1), $$

opérateur qui traduit la relation explicite

$$ \left( \binom{n+1}{k} - 2\binom{n}{k} \right) + \left( \binom{n+1}{k+1} - \binom{n+1}{k} \right) - \left( \binom{n}{k+1} - \binom{n}{k} \right) = 0. $$

En sommant sur $k \in \mathbb{Z}$, les premiers termes se télé scopent deux à deux, et il reste

$$ ((S_n - 2) \cdot U)(n) = U(n+1) - 2U(n) = 0. $$

La fin de la preuve se ramène à vérifier la condition initiale $S(0) = 1$.

Notons que les coefficients de l'opérateur (29.7) obtenu pour cet exemple sont constants, mais que dans le cas de sommations plus générales qui nous occupent dans ce chapitre, ils pourront être des fractions rationnelles en $n$ et $k$.

En l'absence de bornes naturelles, l'équation (29.5) s'écrit plutôt

$$ (P \cdot U)(n) = (Q \cdot u)(n, b+1) - (Q \cdot u)(n, a). $$

Les opérations de clôture vues au Chapitre 14 fournissent alors un opérateur $\tilde{P}(n, S_n)$ qui annule le membre droit de l'égalité ci-dessus. On obtient ainsi une équation homogène, sous la forme

$$ (\tilde{P}P) \cdot U = 0. $$

## Algorithme de Zeilberger

Il reste à voir comment trouver les opérateurs P et Q de l'équation (29.4) dans le cas général. L'idée de Zeilberger est que cette équation,

$$ (P(n, S_n) \cdot u)(n, k) = ((S_k - 1)Q(n, k, S_n, S_k) \cdot u)(n, k), $$

signifie que $Q \cdot u$ est une somme hypergéométrique indéfinie de $P(n, S_n) \cdot u$ par rapport à $k$. Comme $u$ est supposée hypergéométrique, $Q \cdot u$ est en fait de la forme $q(n, k)u(n, k)$ pour une fraction rationnelle $q$: si P était connu, l'Algorithme 29.1 de Gosper suffirait pour trouver $q$.

La méthode conçue par Zeilberger procède alors incrémentalement sur le degré de P en $S_n$. Pour $r = 0, 1, \dots$, elle cherche s'il existe des coefficients $\lambda_i(n)$ pour P tels que

$$ \lambda_0(n)u(n, k) + \lambda_1(n)u(n + 1, k) + \dots + \lambda_r(n)u(n + r, k) $$
**Entrée** Un terme hypergéométrique $u(n,k)$ et un entier $m \in \mathbb{N}$.

**Sortie** Une famille $(\lambda_i(n))_{0 \le i \le r}$ de fractions rationnelles, avec $r \le m$, et une fraction rationnelle $R(n,k)$ telles que

$$ \lambda_r(n)u_{n+r,k} + \cdots + \lambda_0(n)u_{n,k} = R(n, k+1)u_{n,k+1} - R(n,k)u_{n,k}, $$

ou le symbole $\nexists$.

1. Pour $r$ de $0$ à $m$ :

a. fixer $n$ comme un paramètre et introduire les termes hypergéométriques $u_i(k) = u(n+i,k)$, pour $0 \le i \le r$;

b. par l'algorithme de la Section 29.1, résoudre

$$ S(k+1) - S(k) = \lambda_0 u_0(k) + \cdots + \lambda_r u_r(k) $$

en un terme hypergéométrique $S(k) = R(n,k)u(k)$ pour une fraction rationnelle $R$ et en des fractions rationnelles $\lambda_i = \lambda_i(n)$ indépendantes de $k$;

c. si la résolution fournit une solution, renvoyer la fa-mille $(\lambda_i)_{i=0}^r$ et $R(n,k)$.

2. Renvoyer $\nexists$.

**Algorithme 29.2** – Algorithme de Zeilberger pour la sommation hypergéométrique définie.

ait une somme hypergéométrique. L'algorithme pour cela est la variante paramétrée de l'algorithme de Gosper, présentée en Section 29.1.

**Exercice 29.7** Exécuter l'algorithme de Zeilberger sur la somme (29.6) de l'Exemple 29.6. Comparer les résultats des calculs et les preuves de l'identité selon l'approche utilisant la relation du triangle de Pascal et celle utilisant l'algorithme de Zeilberger. ■

**Exercice 29.8** Évaluer la somme hypergéométrique

$$ {}_2F_1\left(\begin{array}{c} -n, b \\ c \end{array} \middle| 1\right) $$

en termes du symbole de Pochhammer $(x)_n$ donné par la Définition 29.2. ■

**Exercice 29.9** On veut montrer, pour tout $n \in \mathbb{N}$, l'identité

$$ {}_2F_1\left(\begin{array}{c} -2n, 2n + 2\alpha + 1 \\ \alpha + 1 \end{array} \middle| \frac{1-x}{2}\right) = {}_2F_1\left(\begin{array}{c} -n, n + \alpha + \frac{1}{2} \\ \alpha + 1 \end{array} \middle| 1 - x^2\right). $$

Indiquer (sans faire les calculs) comment on peut utiliser l'algorithme de Zeilberger pour arriver à ce résultat. ■
## Terminaison

La méthode incrémentale appliquée avec un degré $r$ de P non borné ne termine pas en général, d'où le paramètre $m$ en entrée de l'Algorithme 29.2. Wilf et Zeilberger ont été les premiers à délimiter une classe importante, celle des suites (respectivement termes) proprement hypergéométriques sur lesquelles la terminaison et par conséquent le succès de la méthode sont garantis. Ces suites (respectivement termes) sont de la forme

$$u(n,k) = P(n,k)Z^k \prod_{\ell=1}^{L} (a_\ell n + b_\ell k + c_\ell)!^{e_\ell}, \quad (29.8)$$

où les $a_\ell$, $b_\ell$ et $e_\ell$ sont des entiers, $L$ est un entier positif, P un polynôme et Z une constante.

**Proposition 29.3** Une variante sans borne $m$ en entrée de l'Algorithme 29.2 de Zeilberger termine si l'entrée $u(n,k)$ est proprement hypergéométrique.

*Démonstration.* La preuve repose sur un résultat légèrement plus fort, à savoir l'existence d'un polynôme non nul $A(n, S_k, S_n)$ qui ne dépend pas de $k$ et annule $u(n,k)$; l'existence d'un tel polynôme $A$ est justifiée par le Lemme 29.4 ci-après. Par la suite, des divisions euclidiennes successives de l'opérateur $A$ par $S_k - 1$, sous la forme $A = (S_k - 1)^p [(S_k - 1)\tilde{Q}(n, S_k, S_n) + \tilde{P}(n, S_n)]$ avec $\tilde{P} \neq 0$, vont fournir un couple $(P, Q)$ avec $P \neq 0$ tel que l'opérateur (29.4) annule $u(n,k)$ et l'opérateur $Q$ ne dépend pas de $k$. En effet, en appliquant $A$ à $u(n,k)$ et en multipliant par $k(k-1)\cdots(k-p+1)$ à gauche, on obtient

$$k(k-1)\cdots(k-p+1)A \cdot u(n,k)$$

qui vaut

$$(-1)^p p! \tilde{P} \cdot u(n,k) + (S_k - 1) \cdot v(n,k)$$

pour un nouveau terme $v(n,k)$. Comme le P obtenu, c'est-à-dire $(-1)^p p! \tilde{P}$, est non nul, la recherche exhaustive par degré croissant en $S_n$, telle que mise en place par l'Algorithme 29.2, doit terminer. ■

**Lemme 29.4** Pour un terme proprement hypergéométrique $u(n,k)$ de la forme (29.8), soient

$$\alpha = \sum_{\ell=1}^{L} |e_{\ell} a_{\ell}| \quad \text{et} \quad \beta = \sum_{\ell=1}^{L} |e_{\ell} b_{\ell}|.$$

Il existe un opérateur annulateur $A(n, S_n, S_k)$ non nul d'ordres de décalage relativement à $n$ et $k$ respectivement bornés par

$$r = 2\beta \quad \text{et} \quad s = 2(2\alpha - 1)\beta + \deg_k P + 1. \quad (29.9)$$

*Démonstration.* Pour $0 \le i \le r$ et $0 \le j \le s$, le décalage $u(n+i, k+j)$ fait intervenir des factorielles de la forme $(a_\ell n + b_\ell k + c_\ell + \delta)!$ pour un décalage $\delta$ borné en valeur absolue par $\sigma_\ell = |a_\ell|r + |b_\ell|s$. Pour $e_\ell > 0$, observons que $(a_\ell n + b_\ell k + c_\ell + \delta)!(a_\ell n + b_\ell k + c_\ell - \sigma_\ell)!$
est un polynôme en $k$ de degré au plus $2\sigma_\ell$; pour $e_\ell < 0$, observons qu'il en est de même de $(a_\ell n + b_\ell k + c_\ell + \sigma_\ell)!/(a_\ell n + b_\ell k + c_\ell + \delta)!$. Ainsi, pour les $(r+1)(s+1)$ choix de $(i,j)$,

$$ \frac{\prod_{1 \le l \le L, e_l < 0} (a_l n + b_l k + c_l + \sigma_l)! \ u(n+i, k+j)}{\prod_{1 \le l \le L, e_l > 0} (a_l n + b_l k + c_l - \sigma_l)! \ u(n,k)} $$

est un polynôme en $k$ de degré au plus $\deg_k P + 2 \sum_{\ell=1}^L |e_\ell|\sigma_\ell \le \deg_k P + 2(\alpha r + \beta s)$. Il s'ensuit qu'il existe pour $r$ et $s$ assez grand une relation de dépendance linéaire entre les $u(n+i, k+j)$, à coefficients dans $\mathbb{C}(n)$. C'est plus précisément le cas dès que $(r+1)(s+1) > \deg_k P + 2(\alpha r + \beta s) + 1$, qui est réalisé dès qu'on a (29.9). La relation de dépendance linéaire fournit A. ■

## 29.3 Solutions hypergéométriques. Algorithme de Petkovšek

Si $(L \cdot u)(n) = 0$ avec $u(n)$ hypergéométrique, il existe deux polynômes $P$ et $Q$ vérifiant

$$ u(n+1) = \frac{P(n)}{Q(n)} u(n), $$

et on peut prendre $Q$ unitaire. Il s'ensuit que

$$ u(n + \ell) = \frac{P(n + \ell - 1)}{Q(n + \ell - 1)} \cdots \frac{P(n)}{Q(n)} u(n). $$

Pour une récurrence donnée par un opérateur $L = a_r S_n^r + \cdots + a_0$, une condition nécessaire et suffisante d'existence de solution hypergéométrique s'écrit

$$ \begin{aligned} & a_r(n)P(n+r-1)P(n+r-2)\cdots P(n) + \\ & a_{r-1}(n)Q(n+r-1)P(n+r-2)\cdots P(n) + \cdots \\ & a_1(n)Q(n+r-1)\cdots Q(n-1)P(n) + \\ & a_0(n)Q(n+r-1)\cdots Q(n) = 0. \end{aligned} \quad (29.11) $$

Si on savait prédire que $\text{pgcd}(P(n), Q(n+i)) = 1$ pour $i = 0, \dots, r-1$, alors on en déduirait facilement que $P(n)$ divise $a_0(n)$ et $Q(n+r-1)$ divise $a_r(n)$. Ceci nous donnerait un algorithme : toute paire de facteurs unitaires de $a_0(n)$ et $a_r(n-r+1)$ donnerait un candidat pour $Q(n)$ et un candidat pour $P(n)$ à une constante près; il suffirait alors d'injecter ces candidats dans (29.11) et de chercher s'il existe une constante satisfaisant à l'équation. En itérant sur les facteurs de $a_0$ et $a_r$, le travail serait terminé.

En général, il se peut très bien que $P(n)$ et $Q(n+i)$ aient des facteurs communs. La solution trouvée par Petkovšek consiste à recourir à une décomposition plus forte de la fraction rationnelle. On cherche une solution telle que

$$ \frac{u(n+1)}{u(n)} = Z \frac{A(n)}{B(n)} \frac{C(n+1)}{C(n)}, $$

où $Z$ est une constante, $A, B, C$ sont des polynômes unitaires, $\text{pgcd}(A(n), C(n)) = 1$, $\text{pgcd}(B(n), C(n+1)) = 1$ et $\text{pgcd}(A(n), B(n+i)) = 1$ pour tout $i \in \mathbb{N}$. Cette décomposition des fractions rationnelles est appelée décomposition de Gosper-Petkovšek.
**Entrée** Une équation de récurrence $a_r(n)u(n+r)+\cdots+a_0(n)u(n)=0$ à coefficients $a_i(n)$ polynomiaux.

**Sortie** L'ensemble des termes hypergéométriques $t_n$ solutions de la récurrence.

1. Initialiser S avec l'ensemble vide.

2. Factoriser les polynômes $a_0$ et $a_r$.

3. Pour chaque polynôme $A(n)$ divisant $a_0(n)$ et pour chaque polynôme $B(n)$ divisant $a_r(n-r+1)$ :

a. extraire le coefficient dominant $d(Z)$ de

$$ \sum_{i=0}^{r} Z^i a_i(n) B(n+r-1) \cdots B(n+i+1) A(n+i) \cdots A(n) C(n+i); \qquad (29.10) $$

b. factoriser $d(Z)$;

c. pour chaque facteur irréductible $p(Z)$ de $d(Z)$ :

i. fixer $\zeta$ vérifiant $p(\zeta) = 0$ en étendant au besoin le corps de constantes,

ii. calculer les polynômes $C(n)$ annulant la récurrence (29.10) par l'Algorithme 16.5 de résolution page 302.

iii. pour chaque solution $C$ obtenue, définir un terme hypergéométrique $t_n$ par

$$ t_{n+1}/t_n = \zeta \frac{A(n)}{B(n)} \frac{C(n+1)}{C(n)} $$

et ajouter ces termes à $S$;

4. Renvoyer S.

**Algorithme 29.3** – Algorithme de Petkovšek pour la recherche des solutions hypergéométriques d'une équation de récurrence linéaire.

**Exercice 29.10** Montrer que toute fraction rationnelle peut se décomposer sous la forme ci-dessus. Donner un algorithme calculant les polynômes $A, B, C$ et les constantes $Z$ correspondant à une fraction rationnelle donnée en entrée. On pourra représenter $Z$ par son polynôme annulateur minimal. (Indice : s'inspirer de l'Algorithme 16.6 d'Abrahamov.) ■

Avec cette décomposition, l'équation (29.11) devient

$$ \begin{aligned} & Z^r a_r(n)A(n+r-1)\cdots A(n)C(n+r)+ \\ & Z^{r-1}a_{r-1}(n)B(n+r-1)A(n+r-2)\cdots A(n)C(n+r-1)+\cdots+ \\ & Za_1(n)B(n+r-1)\cdots B(n-1)A(n)C(n+1)+ \\ & a_0(n)B(n+r-1)\cdots B(n)C(n)=0. \end{aligned} \qquad (29.12) $$
Les contraintes de la décomposition permettent de déduire immédiatement

$$A(n) | a_0(n), \quad B(n+r-1) | a_r(n).$$

L'algorithmme de Petkovšek s'en déduit : pour chaque paire (A, B) de facteurs de $a_0$ et $a_r$, le coefficient de tête du polynôme au membre gauche de (29.12) donne une équation polynomiale sur Z. Une fois Z ainsi fixé, il reste à chercher les solutions polynomiales C de l'équation, s'il en existe. La méthode est résumée dans l'Algorithmme 29.3.

**Exercice 29.11** Utiliser l'Algorithmme 29.3 pour résoudre

$$ (n-1)u(n+2) - (n^2 + 3n - 2)u(n+1) + 2n(n+1)u(n) = 0, \\ u(n+2) - (2n+1)u(n+1) + (n^2 - 2)u(n) = 0. $$

■

On peut noter que la recherche de solutions hypergéométriques de récurrences linéaires inhomogènes n'est pas difficile : le membre droit doit être hypergéométrique et, outre les solutions hypergéométriques de la partie homogène, la solution doit être le produit du membre droit par une fraction rationnelle. Ceci ramène le problème à la recherche de solutions rationnelles.

## Notes

Le livre de Petkovšek, Wilf et Zeilberger intitulé A = B [PWZ96] est une bonne introduction aux questions abordées dans ce chapitre. L'algorithmme de Petkovšek possède une extension intéressante [AP94], par réduction de l'ordre, à une plus grande classe de solutions, appelées solutions d'Alembertiennes.

La présentation traditionnelle [Gos78] de l'Algorithmme 29.1 de Gosper est un peu différente en ce qu'elle ne fait pas appel à un algorithme général de résolution rationnelle : la description usuelle développe directement la prédiction d'un facteur du numérateur (voir la fin de la Section 16.4).

Le traitement de la Section 29.1 s'inspire de la présentation élémentaire par Kauers et Paule [KP11, Section 3.5.4]; il a sa source dans des travaux d'Abramov et Petkovšek [AP05], qui montrent de plus que la somme indéfinie $U_n$ pourra être prise directement comme le produit $R(n)u_n$, sans apparition du terme $\Phi_n$ de la Proposition 29.2 et juste après un éventuel prolongement par continuité, à chaque fois que la suite $(u_n)$ sera donnée comme évaluation aux entiers d'une fonction de la variable complexe analytique au voisinage de $\mathbb{N}$ [AP07].

La Proposition 29.3 ne donne qu'une condition suffisante pour l'existence d'un $P(n, S_n)$ et conséquemment pour la terminaison de l'algorithmme de Zeilberger. Il existe des suites qui ne sont pas proprement hypergéométriques et pour lesquelles la méthode fonctionne quand même. Cela a donné lieu à une série de travaux, et le dernier mot revient à un travail d'Abramov [Abr03] qui donne un test algorithmique de terminaison de l'algorithmme.

De nombreuses généralisations de l'algorithmme de Zeilberger sont possibles : par exemple la suite à sommer peut ne pas être hypergéométrique, tout en étant polynomialement récurrente, ou il peut s'agir d'une suite de fonctions différentiellement
finies et l'on cherche une équation différentielle satisfaite par la somme définie, etc. Ces questions seront abordées au Chapitre 32.

L'algorithme de Petkovšek permet aussi de décrire l'espace des solutions d'une équation de récurrence linéaire qui sont combinaisons linéaires de termes hypergéométriques sans être elles-mêmes réduites à de simples termes hypergéométriques [Pet92].

Bibliographie

Abr03 ABRAMOV, S. A. (2003). « When does Zeilberger's algorithm succeed? » In : *Advances in Applied Mathematics*, vol. 30, n°3, p. 424-441.

AP05 ABRAMOV, S. A. et M. PETKOVŠEK (2005). « Gosper's algorithm, accurate summation, and the discrete Newton-Leibniz formula ». In : *ISSAC'05 : International Symposium on Symbolic and Algebraic Computation*. ACM, New York, p. 5-12.

AP07 ABRAMOV, Sergei A. et Marko PETKOVŠEK (2007). « Analytic solutions of linear difference equations, formal series, and bottom summation ». In : *Computer Algebra in Scientific Computing, 10th International Workshop, CASC 2007, Bonn, Germany, September 16-20, 2007, Proceedings*, p. 1-10.

AP94 — (1994). « D'Alembertian solutions of linear differential and difference equations ». In : *ISSAC'94 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 169-174.

Gos78 GOSPER, R. William (1978). « Decision procedure for indefinite hypergeometric summation ». In : *Proceedings of the National Academy of Sciences USA*, vol. 75, n°1, p. 40-42.

KP11 KAUERS, Manuel et Peter PAULE (2011). *The concrete tetrahedron*. Texts and Monographs in Symbolic Computation. Symbolic sums, recurrence equations, generating functions, asymptotic estimates. Springer, Vienna.

Pet92 PETKOVŠEK, Marko (1992). « Hypergeometric solutions of linear recurrences with polynomial coefficients ». In : *Journal of Symbolic Computation*, vol. 14, n°2-3, p. 243-264.

PWZ96 PETKOVŠEK, Marko, Herbert S. WILF et Doron ZEILBERGER (1996). A = B. A. K. Peters.
# 30. Équations fonctionnelles linéaires et polynômes tordus

## Résumé

Une certaine variété de polynômes non commutatifs fournit une représentation unifiée pour une large classe d'équations fonctionnelles linéaires. Celle-ci s'avère bien adaptée pour les calculs. Nous réinterprétons de ce point de vue nombre des algorithmes vus dans les chapitres précédents.

## 30.1 Polynômes non commutatifs pour calculer avec des opérateurs linéaires

Dans cette section, nous présentons un cadre unifié pour la manipulation de systèmes linéaires liant des dérivées $f_i^{(j)}(x)$, des décalées $f_i(x + j)$, ou les substitutions $f_i(q^j x)$ de fonctions inconnues $f_i(x)$. À cette fin, nous introduisons de nouvelles familles de polynômes en une indéterminée ayant la propriété que cette indéterminée ne commute pas avec les coefficients des polynômes. Ce défaut de commutativité reflète une sorte de loi de Leibniz.

Rappelons la relation de Leibniz pour deux fonctions quelconques $f$ et $g$ :

$$ (fg)'(x) = f'(x)g(x) + f(x)g'(x). $$

En notant D l'opérateur de dérivation, M celui qui à une fonction $f$ associe la fonction donnée par $M(f)(x) = xf(x)$, id l'opérateur identité sur les fonctions, et ◦ la composition d'opérateurs, la règle de Leibniz donne, pour $f(x) = x$ et $g$ quelconque,

$$ (D \circ M)(g) = D(M(g)) = M(D(g)) + g = (M \circ D + \text{id})(g). $$

L'identité étant vérifiée par toute fonction $g$, on obtient l'égalité $D \circ M = M \circ D + \text{id}$ entre opérateurs linéaires différentiels. D'autres opérateurs vérifient des analogues de
la règle de Leibniz : l'opérateur $\Delta$ de différence finie, défini par $\Delta(f)(x) = f(x+1) - f(x)$; l'opérateur $S = \Delta + \text{id}$ de décalage, défini par $S(f)(x) = f(x+1)$; pour une constante $q$ fixée autre que 0 et 1, l'opérateur $H$ de dilatation, défini par $H(f)(x) = f(qx)$. On a les relations :

$$ 
\begin{aligned}
\Delta(fg)(x) &= f(x+1)\Delta(g)(x) + \Delta(f)(x)g(x), \\
(fg)(x+1) &= f(x+1)g(x+1), \\
(fg)(qx) &= f(qx)g(qx),
\end{aligned}
 $$

qui mènent aux relations $\Delta \circ M = (M+\text{id}) \circ \Delta + \text{id}$, $S \circ M = (M+\text{id}) \circ S$, $H \circ M = Q \circ M \circ H$ entre opérateurs linéaires, après avoir introduit un nouvel opérateur $Q$ donné par $Q(f)(x) = qf(x)$. La définition suivante fournit un même cadre algébrique pour ces différents contextes d'opérateurs.

**Définition 30.1** Soit A un anneau commutatif intègre de caractéristique zéro, que nous supposons muni d'un endomorphisme injectif $\sigma$ et d'une $\sigma$-dérivation $\delta$, au sens où pour tout $a$ et tout $b$ de A,

$$ \sigma(a+b) = \sigma(a) + \sigma(b), \quad \sigma(ab) = \sigma(a)\sigma(b), \quad \delta(ab) = \sigma(a)\delta(b) + \delta(a)b. $$

Pour une nouvelle indéterminée $\partial$, on appelle *anneau de polynômes tordus* l'algèbre sur A engendrée par $\partial$ et les relations, pour tout $a$ de A,

$$ \partial a = \sigma(a)\partial + \delta(a). $$

On note cet anneau $A\langle\partial; \sigma, \delta\rangle$.

Une conséquence immédiate de la définition est que tout élément $f$ d'un anneau de polynômes tordus admet une récriture canonique de la forme

$$ f = a_r \partial^r + \cdots + a_0 $$

pour des $a_i$ dans A, avec $a_r$ non nul sauf si la somme ne comprend aucun terme (et alors $f = 0$). Les $a_i$ et l'entier $r$ ainsi définis (sauf pour $f = 0$) sont uniques et $r$ a les propriétés d'un degré. En particulier, le degré d'un produit est la somme des degrés de ses facteurs. Ceci résulte de l'injectivité de $\sigma$ et de l'intégrité, par la formule

$$ (a\partial^r + \cdots)(b\partial^s + \cdots) = a\sigma^r(b)\partial^{r+s} + \cdots $$

car $a\sigma^r(b)$ est nul si et seulement si $a$ ou $b$ l'est.

Des choix adéquats de $\sigma$ et $\delta$ nous font retrouver les quelques exemples donnés plus haut. Pour simplifier la notation, nous supposons que A peut s'identifier à un bon espace de fonctions. En notant $0$ l'application qui a toute fonction associe la fonction constante nulle, on trouve en particulier les exemples de la Figure 30.1. Toutes les algèbres d'opérateurs de cette figure sont à coefficients dans $\mathbb{Q}(x)$; on dispose aussi d'analogues pour $A = \mathbb{Q}[x]$ et, quand $\sigma \neq \text{id}$, pour $A = \mathbb{Q}[x, x^{-1}]$.

On fera attention à la notation. Si la composition entre opérateurs est notée par $\circ$, nous ne ferons qu'une simple juxtaposition pour le produit de polynômes tordus, et
<table><caption>FIGURE 30.1 – Algèbres d'opérateurs linéaires représentés par les anneaux de polynômes tordus les plus courants.</caption><thead><tr><th>Anneau de polynômes tordus</th><th>Natures d'opérateurs représentés</th></tr></thead><tbody><tr><td>Q(x)⟨∂; id, D⟩</td><td>opérateurs différentiels linéaires</td></tr><tr><td>Q(x)⟨∂; S, 0⟩</td><td>opérateurs de récurrence</td></tr><tr><td>Q(x)⟨∂; S, Δ⟩</td><td>opérateurs de différence finie</td></tr><tr><td>Q(x)⟨∂; H, 0⟩ (q ∈ Q \ {0, 1, -1})</td><td>opérateurs de q-dilatation</td></tr><tr><td>Q(x)⟨∂; id, 0⟩</td><td>polynômes commutatifs usuels de Q(x)[∂]</td></tr></tbody></table>

<table><caption>FIGURE 30.2 – Règles de commutation pour les anneaux de polynômes tordus les plus courants.</caption><thead><tr><th>Anneau</th><th>Commutation avec x</th><th>Commutation avec u ∈ Q(x)</th></tr></thead><tbody><tr><td>Q(x)⟨∂; id, D⟩</td><td>∂x = x∂ + 1</td><td>∂u = u∂ + u'</td></tr><tr><td>Q(x)⟨∂; S, 0⟩</td><td>∂x = (x + 1)∂</td><td>∂u = u(x + 1)∂</td></tr><tr><td>Q(x)⟨∂; S, Δ⟩</td><td>∂x = (x + 1)∂ + 1</td><td>∂u = u(x + 1)∂ + u(x + 1) - u(x)</td></tr><tr><td>Q(x)⟨∂; H, 0⟩</td><td>∂x = qx∂</td><td>∂u = u(qx)∂</td></tr><tr><td>Q(x)⟨∂; id, 0⟩</td><td>∂x = x∂</td><td>∂u = u∂</td></tr></tbody></table>

nous noterons 1 l'élément neutre pour le produit de polynômes tordus. Néanmoins, nous ferons l'abus de notation de noter la dérivation par rapport à x de la même façon, $D_x$, quel que soit l'anneau A, et id, sans indice, pour l'identité de n'importe quel A. De plus, nous noterons simplement x pour M. Nous obtenons ainsi les règles de commutations données explicitement en Figure 30.2.

Le cas $\delta = 0$ est fréquent, et on écrit alors $A⟨\partial; \sigma⟩$, sans référence au 0. De même que dans le cas commutatif on définit les polynômes de Laurent, dont l'algèbre est notée $A[X, X^{-1}]$, et dans laquelle $X^{X^{-1}} = X^{-1}X = 1$, le cas où $\sigma$ est inversible et autre que l'identité permet de représenter des opérateurs qui possèdent un inverse. Dans ce cas, on notera $A⟨\partial, \partial^{-1}; \sigma⟩$ l'algèbre où $\partial a = \sigma(a)\partial$, $\partial^{-1}a = \sigma^{-1}(a)\partial^{-1}$, $\partial\partial^{-1} = \partial^{-1}\partial = 1$.

## Idéaux, modules, actions

Les anneaux de polynômes tordus ont été définis par leur règle de commutation, sans faire référence à quelque opérateur que ce soit. Leur interprétation comme algèbres d'opérateurs, ainsi que les propriétés des calculs dans les sections et chapitres qui suivent, s'expriment mieux en termes de quelques structures algébriques non commutatives que nous définissons dans cette section.

Les structures algébriques qui vont servir se placent dans le cadre des anneaux généraux, c'est-à-dire, non commutatifs : un *anneau* R est la donnée d'un ensemble muni d'une première loi interne + appelée *addition*, qui en fait un groupe commutatif de neutre 0, ainsi que d'une deuxième loi interne appelée *multiplication* et dénotée par juxtaposition, qui en fait un monoïde de neutre 1 et est distributive à gauche et à droite sur l'addition. Les « anneaux commutatifs » déjà utilisés dans les chapitres précédents et dans la Définition 30.1 des « anneaux de polynômes tordus » sont des
anneaux (au sens général qui vient d'être indiqué) dont on exige que la multiplication soit commutative. Un anneau de polynômes tordus est bien un anneau particulier.

Tout comme les anneaux commutatifs ont des idéaux, définis comme des sousensembles clos par multiplication à gauche et à droite par tout élément de l'anneau, les anneaux généraux ont des idéaux, mais on ne s'intéresse en général qu'à la clôture d'un unique côté. Un *idéal à gauche* I d'un anneau R est un sous-groupe de R (pour l'addition) tel que $fg \in I$ pour tout $f \in R$ et tout $g \in I$. Une notion d'idéal à droite pourrait être définie de façon analogue; dans tout ce qui suit, nous dirons simplement idéal pour idéal à gauche. Pour une famille finie $g_1, \dots, g_s$ d'éléments de R, les sommes $f_1g_1 + \dots + f_sg_s$ pour des coefficients $f_i \in R$ constituent un idéal noté $Rg_1 + \dots + Rg_s$, appelé *idéal engendré par* $g_1, \dots, g_s$. Tout anneau R peut être vu comme idéal de lui-même car $R = R1$.

De même, la notion de module sur un anneau commutatif, notion déjà utilisée pour décrire les approximants de Padé–Hermite (Chapitre 7), la réduction de réseau (Chapitre 20), et dans toute la partie sur les systèmes polynomiaux, se généralise au cadre des anneaux généraux. Un *module à gauche* M sur un anneau R est un groupe additif muni d'une addition $+$ et d'un neutre 0, stable sous l'action d'une loi externe $\cdot$ de multiplication à gauche par les éléments de R, appelée *multiplication scalaire*, distributive à gauche sur l'addition de R et à droite sur l'addition de M, et telle que pour tous $r$ et $s$ de R et $m$ de M, $(rs) \cdot m = r \cdot (s \cdot m)$ et $1 \cdot m = m$. Une notion de module à droite pourrait être définie de façon analogue; dans tout ce qui suit, nous dirons simplement module pour module à gauche. Cette notion généralise celle d'idéal : tout idéal I de R est un module sur R, obtenu en prenant la multiplication de R comme multiplication scalaire. Pour une famille finie $g_1, \dots, g_s$ d'éléments d'un module M fixé, les sommes $f_1g_1 + \dots + f_sg_s$ pour des coefficients $f_i \in R$ constituent un module S noté $Rg_1 + \dots + Rg_s$, appelé *module engendré par* $g_1, \dots, g_s$. C'est un *sous-module* de M sur R, au sens où c'est un module sur R obtenu par restriction à S de l'addition de M et de la multiplication scalaire. On appelle encore *action de R sur M* la loi de multiplication scalaire d'un module M.

Pour un module donné M sur R, soit G une famille $(g_i)_{i \in I}$ d'éléments de M. La famille G est un système de générateurs de M si pour tout $m \in M$, il existe une sousfamille finie $g'_1, \dots, g'_s$ de G et des coefficients $f_i \in R$ tels que $m = f_1g'_1 + \dots + f_sg'_s$. La famille G est libre si toute relation de dépendance linéaire $f_1g'_1 + \dots + f_sg'_s = 0$ obtenue pour une sous-famille finie $g'_1, \dots, g'_s$ de G implique que tous les $f_i$ sont nuls. La famille G est une base de M si c'est un système de générateurs et si elle est libre. Un module est dit libre s'il possède une base. Pour les anneaux R qui nous intéressent, à savoir les anneaux commutatifs et les anneaux de polynômes tordus à coefficients dans un anneau commutatif, si un module libre sur R possède une base, le cardinal de cette base est indépendant du choix de la base. Dans le cas de bases finies, ce cardinal est appelé *rang* du module. Un cas particulier important est celui du produit cartésien $R^n$ pour $n \in \mathbb{N}$, qui fournit un module pour l'addition coordonnée à coordonnée et pour la multiplication scalaire obtenue en multipliant chaque coordonnée par le même élément de R. C'est un module libre de rang $n$, de base constituée par les éléments $e_i = (0, \dots, 0, 1, 0, \dots, 0)$, où l'unique 1 est en position $i$.

Pour relier anneaux de polynômes tordus et algèbres d'opérateurs, nous faisons maintenant agir les anneaux de polynômes tordus sur les espaces de fonctions, au
sens de l'action d'un anneau sur un module. Mais un anneau de polynômes tordus n'a pas d'action unique sur un espace de fonctions donné, aussi adoptons-nous les conventions, en vigueur dans toute la suite du texte :

— un anneau de la forme $A\langle\partial; \sigma\rangle$ agit par $\partial \cdot f = \sigma(f)$ pour une extension convenable de $\sigma$,

— un anneau de la forme $A\langle\partial; \sigma, \delta\rangle$ agit par $\partial \cdot f = \delta(f)$ pour une extension convenable de $\delta$,

— les coefficients dans A agissent par simple multiplication, $a \cdot f = af$.

Remarquons que l'algèbre des suites $A^N$ ne peut pas être vue comme un module sur l'anneau $A\langle\partial, \partial^{-1}; \sigma\rangle$ quand $\sigma$ est le décalage avant. En effet, l'action de $\partial$ sur la suite valant 1 en 0 et nulle ensuite donne la suite nulle : l'action de $\partial$ ne peut donc pas être inversée. Ce problème technique peut être contourné en considérant les classes de suites identifiées lorsqu'elles sont égales après un certain rang (qui dépend des deux suites). (On parle de « germe de suite à l'infini ».) Mais on perd alors la possibilité d'exprimer certaines suites, celles à support fini, justement.

## 30.2 Morphismes entre anneaux de polynômes tordus

Dans cette section, nous sommes amenés à considérer simultanément des fonctions de $x$ et des fonctions d'une autre variable. Aussi indiquerons-nous en indice de D, S, $\partial$, $\sigma$, $\delta$, etc, la variable à laquelle ces objets font référence. De plus, les anneaux A qui servent à construire les anneaux de polynômes tordus sont de la forme $\mathbb{Q}[x]$ ou $\mathbb{Q}[x, x^{-1}]$.

### Série génératrice différentiellement finie et suite polynomialement récurrente associée

On a déjà vu que lorsqu'une série $f = \sum_{n \ge 0} u_n x^n$ est différentiellement finie, ses coefficients vérifient une relation de récurrence finie. Autrement dit, la suite $u = (u_n)_{n \ge 0}$ est polynomialement récurrente. La preuve repose sur les identités

$$xf = \sum_{n \ge 1} u_{n-1} x^n = \sum_{n \ge 1} (\partial_n^{-1} \cdot u)(n) x^n$$

et

$$D_x(f) = f' = \sum_{n \ge 0} (n+1)u_{n+1}x^n = \sum_{n \ge 0} ((n+1)\partial_n \cdot u)(n)x^n,$$

où nous avons introduit l'anneau $\mathbb{Q}[n]\langle\partial_n, \partial_n^{-1}; S_n\rangle$. Par récurrence, ceci donne

$$x^{\alpha} D_{x}^{\beta}(f) = \sum_{n \ge \alpha} (\partial_{n}^{-\alpha}((n+1)\partial_{n})^{\beta} \cdot u)(n) x^{n} = \sum_{n \ge \alpha} ((n+1-\alpha)\cdots(n+\beta-\alpha)\partial_{n}^{\beta-\alpha} \cdot u)(n) x^{n}.$$

Pour une série $f$ solution de l'équation différentielle

$$a_r(x)f^{(r)}(x) + \cdots + a_0(x)f(x) = 0$$
où les $a_i$ sont dans $\mathbb{Q}[x]$, nous obtenons ainsi une récurrence sur $u$, valable pour des $n$ assez grands. Cette récurrence s'exprime en termes de polynômes tordus de la façon suivante. On représente l'opérateur différentiel associé à l'équation par le polynôme tordu $L = a_r(x)\partial_x^r + \cdots + a_0(x)$ dans $\mathbb{Q}[x]\langle\partial_x; \mathrm{id}, D_x\rangle$ sur $\mathbb{Q}$. De la sorte, l'équation différentielle s'écrit $L \cdot f = 0$. On introduit aussi l'algèbre $\mathbb{Q}[n]\langle\partial_n, \partial_n^{-1}; S_n\rangle$ et le morphisme d'algèbres $\mu$ défini par $\mu(x) = \partial_n^{-1}$ et $\mu(\partial_x) = (n+1)\partial_n$. Alors, la suite $u$ des coefficients est solution pour $n$ assez grand de la récurrence représentée par l'image $\mu(L)$. Pour comprendre pour quels $n$ cette récurrence est valide, écrivons

$$\mu(L) = b_p(n)\partial_n^p + \cdots + b_q(n)\partial_n^q$$

pour $p \le q$ et $b_p b_q \ne 0$, de sorte que la récurrence prend la forme

$$(\mu(L) \cdot u)(n) = b_p(n)u_{n+p} + \cdots + b_q(n)u_{n+q} = 0$$

et est vérifiée pour tout $n$ si $p \ge 0$ et pour tout $n \ge -p$ si $p < 0$.

De façon duale, une suite polynomialement récurrente $u$ a une série générale $f = \sum_{n \ge 0} u_n x^n$ différentiellement finie, ce que nous allons retrouver en termes de polynômes tordus. Pour ce point, nous supposons en fait que la suite $u$ est prolongée aux indices négatifs par $u_n = 0$ pour $n < 0$, et qu'elle est polynomialement récurrente sur $\mathbb{Z}$ tout entier. Ceci ne constitue aucune perte de généralité : une récurrence valable pour la suite initiale devient valable pour la suite prolongée après multiplication par un polynôme de la forme $(n+1)(n+2)\cdots(n+r)$. Les formules

$$\sum_{n \in \mathbb{Z}} nu_n x^n = x \partial_x f \quad \text{et} \quad \sum_{n \in \mathbb{Z}} u_{n+1} x^n = x^{-1} f$$

donnent par récurrence

$$\sum_{n \ge 0} n^\alpha u_{n+\beta} x^n = (x \partial_x)^\alpha x^{-\beta} \cdot f = x^{-\beta} (x \partial_x - \beta)^\alpha \cdot f,$$

et fournissent un autre morphisme, $v$, de $\mathbb{Q}[n]\langle\partial_n; S_n\rangle$ dans $\mathbb{Q}[x, x^{-1}]\langle\partial_x; \mathrm{id}, D_x\rangle$, donné par $v(n) = x\partial_x$ et par $v(\partial_n) = x^{-1}$. Pour une suite $u$ solution sur $\mathbb{Z}$ de l'équation de récurrence

$$b_p(n)u_{n+p} + \cdots + b_0(n)u_n = 0$$

où les $b_i$ sont dans $\mathbb{Q}[n]$, nous introduisons le polynôme tordu $P = b_p(n)\partial_n^p + \cdots + b_0(n)$ de $\mathbb{Q}[n]\langle\partial_n; S_n\rangle$. Pour obtenir une relation différentielle sur la série générale $f$, nous considérons $v(P)$ que nous écrivons

$$v(P) = a_0(x) + \cdots + a_r(x) \partial_x^r.$$

Alors, comme $\sum_{n \in \mathbb{Z}} (P \cdot u)(n) x^n = 0$, la série $f$ vérifie la relation différentielle

$$a_0(x)f(x) + \cdots + a_r(x)f^{(r)}(x) = 0.$$

Algébriquement, les propriétés précédentes s'expriment par le fait que $\mu$ s'étend en un isomorphisme d'algèbres entre $\mathbb{Q}[x, x^{-1}]\langle\partial_x; \mathrm{id}, D_x\rangle$ et $\mathbb{Q}[n]\langle\partial_n, \partial_n^{-1}; S_n\rangle$, dont l'inverse étend $v$. Ce morphisme vérifie $\mu(x^i) = \partial_n^{-i}$ et

$$\mu(\partial_x^i) = ((n+1)\partial_n)^i = (n+1)\cdots(n+i)\partial_n^i.$$
Les deux algèbres isomorphes peuvent être vues comme agissant naturellement sur $\mathbb{Q}((x)) = \{x^{-r}f \mid r \in \mathbb{N}, f \in \mathbb{Q}[[x]]\}$, qui n'est autre que l'algèbre des suites sur $\mathbb{Z}$ nulles pour les indices $n$ strictement inférieurs à un entier $-r$ (dépendant de la suite considérée).

## Séries binomiales

**Exercice 30.1** Une série binomiale est une série de la forme $\sum_{n \ge 0} u_n(x)$. Montrer que les solutions en série binomiale d'une équation fonctionnelle à différence

$$a_r(x)f(x+r) + \cdots + a_0(x)f(x) = 0$$

ont des coefficients $u_n$ qui vérifient une récurrence et expliciter le morphisme entre algèbres de polynômes tordus correspondant. ■

## Changements de variables

Lorsqu'une série différentiellement finie $f(x)$ est solution d'une équation différentielle $L \cdot f = 0$ donnée par un polynôme tordu

$$L = L(x, \partial_x) = a_r(x)\partial_x^r + \cdots + a_0(x),$$

pour toute constante $\lambda \neq 0$ la série $g(x) := f(\lambda x)$ vérifie $g^{(i)}(x) = \lambda^i f^{(i)}(\lambda x)$ pour chaque $i \in \mathbb{N}$. En substituant $\lambda x$ pour $x$ dans $L \cdot f = 0$, on obtient que $g$ est solution de l'équation différentielle associée à

$$L(\lambda x, \lambda^{-1} \partial_x) = a_r(\lambda x) \lambda^{-r} \partial_x^r + \cdots + a_0(\lambda x).$$

C'est encore le résultat d'un morphisme d'algèbres, $\Lambda$, défini cette fois par $\Lambda(x) = \lambda x$ et $\Lambda(\partial_x) = \lambda^{-1} \partial_x$.

Lorsque $f$ est une fonction différentiellement différentiellement finie, la fonction $z \mapsto f(1/z)$ est elle aussi différentiellement finie, en $z$ cette fois, pour autant que la fonction composée ait un sens. En effet, pour toute fonction $g$, notons $\tilde{g}(z) = g(1/z)$ (avec la même réserve de définition). Puisque $g(x) = \tilde{g}(1/x)$, par dérivation on a $g'(x) = -\tilde{g}'(1/x)/x^2$, ce qui est l'évaluation en $z = 1/x$ de $-z^2 \partial_z \cdot \tilde{g}$. Autrement dit, on a $\tilde{g}' = -z^2 \partial_z \cdot \tilde{g}$, d'où par récurrence $\tilde{g}^{(\beta)} = (-z^2 \partial_z)^\beta \cdot \tilde{g}$. Ainsi, $\tilde{f}$ est différentiellement finie, donnée comme vérifiant l'équation différentielle associée à l'image de $L$ par le morphisme de $\mathbb{Q}[x]\langle \partial_x; \text{id}, D_x \rangle$ dans $\mathbb{Q}[z, z^{-1}]\langle \partial_z; \text{id}, D_z \rangle$ qui envoie $x$ sur $z^{-1}$ et $\partial_x$ sur $-z^2 \partial_z$.

**Exercice 30.2** Plus généralement, la fonction obtenue par substitution rationnelle de la variable, donnée par $h(u) = f(r(u))$, est encore différentiellement finie. Nous laissons en exercice le soin de montrer ce résultat par la même approche dans le cas où la dérivée $r'$ s'exprime comme une fraction rationnelle en $r$. ■

## 30.3 Division euclidienne

Dans cette section et les suivantes, nous nous appuyons sur des propriétés particulières des anneaux de polynômes tordus quand l'anneau $A$ de la construction est un
corps, que nous prendrons de la forme $\mathbb{Q}(x)$.

La commutation $\partial a = \sigma(a)\partial + \delta(a)$ dans $\mathbb{Q}(x)\langle\partial; \sigma, \delta\rangle$ permet d'écrire tout polynôme tordu sous la forme $a_0(x) + \cdots + a_r(x)\partial^r$, pour des fractions rationnelles $a_i$ de $\mathbb{Q}(x)$ uniques. Une conséquence de l'injectivité de $\sigma$ est l'existence d'un degré en $\partial$ bien défini : l'entier $r$ de l'écriture précédente lorsque $a_r$ est non nulle. En particulier, le degré d'un produit $L_1L_2$ de polynômes tordus est la somme des degrés des $L_i$. Il s'ensuit que la division euclidienne du cas commutatif, et toute la théorie qui en découle, se transpose avec peu d'altérations dans le cas tordu.

## Procédé de division

La différence principale avec le cas commutatif est qu'on distingue division euclidienne à gauche et division euclidienne à droite. Vu notre interprétation en termes d'opérateurs linéaires, nous ne considérerons que la division à droite, qui se fait en retranchant des multiples à gauche. Soit à diviser $A = a_r(x)\partial^r + \cdots + a_0(x)$ de degré $r$ par $B = b_s(x)\partial^s + \cdots + b_0(x)$ de degré $s$. On suppose $s \le r$. Alors,

$$ \partial^{r-s} B = \sigma^{r-s}(b_s(x))\partial^r + \text{termes d'ordres inférieurs,} $$

où la puissance de $\sigma$ représente une itération (par composition), et ainsi

$$ A - a_r(x)\sigma^{r-s}(b_s(x))^{-1}\partial^{r-s}B $$

est de degré strictement inférieur à $r$. Cette étape de réduction est l'étape élémentaire de la division euclidienne. En itérant le procédé, on aboutit à un reste $R$ de degré strictement inférieur à $s$. En regroupant les facteurs gauches, on obtient un quotient à gauche $Q$ tel que $A = QB + R$.

**Exemple 30.1** On considère l'anneau $\mathbb{Q}(n)\langle\partial_n; S_n\rangle$ des polynômes tordus représentant les opérateurs de décalage. La division de $A = (n^2 - 1)\partial_n^2 - (n^3 + 3n^2 + n - 2)\partial_n + (n^3 + 3n^2 + 2n)$, qui annule les combinaisons linéaires de $n!$ et $n$, par $B = n\partial_n^2 - (n^2 + 3n + 1)\partial_n + (n^2 + 2n + 1)$, qui annule les combinaisons linéaires de $n!$ et $1$, s'écrit

$$ A = n^{-1}(n^2 - 1)B - n^{-1}(n^2 + n + 1)(\partial_n - (n + 1)). $$

Le reste est multiple de $\partial_n - (n + 1)$, qui représente la récurrence $u_{n+1} = (n + 1)u_n$, vérifiée par la factorielle.

Notons une propriété de cette division : si $A$ est multiplié à gauche par un facteur $m(x)$ sans que $B$ ne soit changé, alors $Q$ et $R$ sont multipliés à gauche par le même facteur $m(x)$. Ceci ne vaut plus (en général) pour un facteur faisant intervenir $\partial$.

## Réduction d'une puissance de $\partial$

La division euclidienne nous donne une nouvelle interprétation du calcul du N-ième terme d'une suite polynomialement récurrente $u = (u_n)$ relativement à l'anneau $\mathbb{Q}(n)\langle\partial_n; S_n\rangle$. Supposons que $u$ soit solution de l'équation de récurrence

$$ a_r(n)u_{n+r} + \cdots + a_0(n)u_n = 0. \qquad (30.1) $$
En déroulant la récurrence, on voit que $u_N$ peut, pour tout N sauf annulation malvenue de $a_r$, se mettre sous la forme $\alpha_{r-1,N}u_{r-1} + \cdots + \alpha_{0,N}u_0$. Plus généralement, on a une relation qui récrit $u_{n+N}$ en termes de $u_{n+r-1}, \dots, u_n$. Pour l'obtenir, associons à la récurrence sur $u$ le polynôme tordu $P = a_r(n)\partial_n^r + \cdots + a_0(n)$. Pour un N donné, la division euclidienne de $\partial_n^N$ par P s'écrit

$$ \partial_n^N = Q_N(n)P + \alpha_{r-1,N}(n)\partial_n^{r-1} + \cdots + \alpha_{0,N}(n) $$

pour des fractions rationnelles $\alpha_{i,N}(n)$. Après application sur $u$ et évaluation en $n$, nous obtenons

$$ u_{n+N} = 0 + \alpha_{r-1,N}(n)u_{n+r-1} + \cdots + \alpha_{0,N}(n)u_n, $$

d'où le résultat annoncé pour $\alpha_{i,N} = \alpha_{i,N}(0)$.

**Exemple 30.2** Dans le cas particulier d'une relation de récurrence (30.1) d'ordre 1, définissant donc une suite $u(n)$ hypergéométrique, nous obtenons par linéarité la relation $(L \cdot u)(n) = r(n)u(n)$, où la fraction rationnelle $r(n)$ est le reste de la division euclidienne de L par $\partial_n - a_0(n)/a_1(n)$. Nous retrouvons ainsi le Lemme 29.1.

**Exercice 30.3** Nous laissons le lecteur se convaincre que la récriture d'une dérivée $f^{(N)}$ d'une fonction différentiellement finie $f$ décrite par une équation différentielle d'ordre $r$ en termes de ses dérivées d'ordre strictement inférieur à $r$ s'interprète de façon analogue comme le calcul d'un reste de division euclidienne. ■

### Clôture par addition

Le même ingrédient se retrouve dans l'algorithme donnant la clôture par addition de deux fonctions différentiellement finies ou de deux suites polynomiallement récurrentes : pour deux objets $f$ et $g$ à additionner, décrits comme solutions des équations respectives $L_f \cdot f = 0$ et $L_g \cdot g = 0$ pour des polynômes tordus de degrés respectifs $r$ et $s$ dans un anneau adéquat $A \langle \partial; \sigma, \delta \rangle$, l'algorithme exprime, pour des $i$ successifs, $\partial^i \cdot (f + g)$ sous la forme $(\partial^i \text{ mod } L_f) \cdot f + (\partial^i \text{ mod } L_g) \cdot g$, où la notation $A \text{ mod } B$ note le reste de la division euclidienne à droite de $A$ par $B$. Lorsque suffisamment de $i$ ont été considérés, l'algorithme qui a été donné au Chapitre 14 calcule par de l'algèbre linéaire des cofacteurs $a_0, \dots, a_{r+s}$ tels que, simultanément,

$$ \sum_{i=0}^{r+s} a_i (\partial^i \text{ mod } L_f) = 0 \quad \text{et} \quad \sum_{i=0}^{r+s} a_i (\partial^i \text{ mod } L_g) = 0. $$

Notons que $P = \sum_{i=0}^{r+s} a_i \partial^i$ est un multiple commun à gauche de $L_f$ et de $L_g$, puisque $P \text{ mod } L_f = P \text{ mod } L_g = 0$. Puisque l'algorithme fonctionne en recherchant un $P$ d'ordre minimal, l'algorithme de clôture par addition est donc un algorithme de calcul de ppcm (à gauche).

## 30.4 Recherche de solutions et factorisation d'opérateurs

Comme pour les anneaux de polynômes commutatifs usuels, une notion de factorisation est présente pour les anneaux de polynômes tordus. Une nuance importante
réside dans le lien entre les « zéros » des polynômes tordus et la position des facteurs. Nous allons voir que la factorisation de polynômes tordus se relie aux algorithmes vus dans cet ouvrage pour la recherche de solutions polynomiales, rationnelles, et hypergéométriques dans le cas de récurrences. Par ailleurs, il n'y a plus d'unicité des facteurs, même à ordre près et modulo multiplication par des unités. Un exemple est donné dans le cas différentiel par l'infinité de factorisations

$$ \partial^2 = \left( \partial + \frac{1}{x+r} \right) \left( \partial - \frac{1}{x+r} \right) $$

quand $r$ est une constante.

Dans le cas d'un polynôme commutatif $w$ se factorisant sous la forme $uv$ pour des facteurs polynomiaux de degré au moins 1, tout zéro de $u$ et tout zéro de $v$ est zéro de $w$; à l'inverse, quitte à se placer dans une clôture algébrique, tout zéro $\alpha$ de $w$ en fournit un facteur $x - \alpha$ et un quotient exact $u(x)$ tel que $w(x) = u(x)(x - \alpha)$. Le phénomène est différent dans le cas tordu, comme attesté par l'inégalité

$$ \partial^2 \neq \left( \partial - \frac{1}{x+r} \right) \left( \partial + \frac{1}{x+r} \right) $$

quand $r$ est une constante.

Plus généralement, une factorisation $L = PQ$ dans $A\langle\partial; \sigma, \delta\rangle$ (où $A$ est un corps) a des propriétés différentes selon le facteur : une solution $f$ de l'équation $Q \cdot f = 0$ est encore solution de $L \cdot f = 0$, car $L \cdot f = P \cdot (Q \cdot f) = P \cdot 0 = 0$; mais une solution $g$ de $P$ ne donne lieu à des solutions $f$ de $L$ que par la relation $Q \cdot f = g$. Inversement, une solution $f$ de $L$ donne lieu à un facteur droit d'ordre 1 de $L$, à condition d'étendre $A$ par $f$ et tous ses itérés par $\sigma$ et $\delta$. Ce facteur est de la forme $\partial - (\partial \cdot f)/f$, c'est-à-dire $\partial - \delta(f)/f$ ou $\partial - \sigma(f)/f$ selon l'action de l'anneau de polynômes tordus sur les fonctions.

Les algorithmes de recherche de solutions dans des classes particulières fournissent donc implicitement, pour chaque solution trouvée, un facteur droit d'ordre 1. Ils interviennent donc naturellement comme base d'algorithmes de factorisation. Plus précisément, dans le cas différentiel, une solution polynomiale ou rationnelle $f$ d'une équation $L \cdot f = 0$ pour $L$ dans l'anneau $\mathbb{Q}(x)\langle\partial_x; \text{id}, D_x\rangle$ fournit un facteur droit $D = \partial_x - (D_x \cdot f)/f$ où $(D_x \cdot f)/f$ est rationnel; dans le cas à récurrence, une solution polynomiale, rationnelle ou hypergéométrique $f$ d'une équation $L \cdot f = 0$ pour $L$ dans l'anneau $\mathbb{Q}(x)\langle\partial_x; S_x\rangle$ fournit un facteur droit $D = \partial_x - S_x(f)/f$ où $S_x(f)/f$ est rationnel. Dans les deux cas, le quotient $Q$ tel que $L = QD$ est aussi à coefficients rationnels.

**Exemple 30.3** Un exemple simple, en réalité sans extension stricte de $A$, est donné dans $A = \mathbb{Q}[x]\langle\partial_x; \text{id}, D_x\rangle$ par l'opérateur

$$ L = x^2(4x^2 + 5)\partial_x^3 - x(8x^4 + 14x^2 - 5)\partial_x^2 - (4x^4 + 17x^2 + 5)\partial_x - 2x^3(4x^2 + 9), $$

dont une solution particulière est $f = \exp x^2$. Cette solution se vérifie à partir de
$D_x \cdot f = 2xf$, $D_x^2 \cdot f = (4x^2 + 2)f$ et $D_x^3 \cdot f = (8x^3 + 12x)f$, en établissant la nullité de
$x^2(4x^2 + 5)(8x^3 + 12x) - x(8x^4 + 14x^2 - 5)(4x^2 + 2) - (4x^4 + 17x^2 + 5)(2x) - 2x^3(4x^2 + 9).$

Par division euclidienne, on trouve

$$
L = (x^2(4x^2 + 5)\partial_x^2 - x(4x^2 - 5)\partial_x + 4x^4 + 13x^2 - 5)(\partial_x - 2x).
$$

On montre que L n'a pas d'autre facteur droit non trivial unitaire ; l'Exercice 30.4
fournit les facteurs gauches d'ordre 1, en réalité un seul sur cet exemple :

$$
L = (x(4x^2 + 5)\partial_x - (2x^2 + 5)(4x^2 + 1))(x\partial_x^2 + \partial_x + x).
$$

**Exemple 30.4** L'opérateur $L = 2(2x + 3)\partial_x^2 + 3(5x + 7)\partial_x + 9(x + 1)$ fournit un autre exemple, pour $A = \mathbb{Q}[x](\partial_x; S_x)$. Comme une solution particulière est $(-3)^x$, ce qui s'obtient par l'algorithme de Petkovšek et peut s'établir simplement en observant la nullité de L en $\partial_x = -3$, un facteur droit de L est $\partial_x + 3$, et une division euclidienne montre

$$
L = (2(2x + 3)\partial_x + 3(x + 1))(\partial_x + 3).
$$

On montre que L n'a pas d'autre facteur droit non trivial unitaire.

**Exercice 30.4** Un antimorphisme $\phi$ entre anneaux est une application $\mathbb{Q}$-linéaire qui renverse les produits : $\phi(PQ) = \phi(Q)\phi(P)$. Montrer l'existence d'antimorphismes

$$
\mu : \mathbb{Q}(x)\langle \partial_x ; \mathrm{id}, D_x \rangle \to \mathbb{Q}(u)\langle \partial_u ; \mathrm{id}, D_u \rangle
$$

et

$$
\nu : \mathbb{Q}(x)\langle \partial_x ; S_x \rangle \to \mathbb{Q}(u)\langle \partial_u ; S_u \rangle,
$$

définis par les relations

$$
\mu(x) = u, \quad \mu(\partial_x) = -\partial_u, \quad \text{et} \quad \nu(x) = -u, \quad \nu(\partial_x) = \partial_u.
$$

Expliquer comment ces antimorphismes fournissent des facteurs gauches d'ordre 1
de polynômes tordus.

**30.5 Algorithme d'Euclide**

Il est classique que les anneaux commutatifs euclidiens — ceux dans lesquels l'existence d'un degré permet une division euclidienne — sont principaux : tout idéal peut être engendré par un unique générateur. C'est le cas des anneaux de polynômes commutatifs à coefficients dans un corps. Le pgcd *p* de deux polynômes *f* et *g* est alors l'unique polynôme unitaire engendrant l'idéal (*f*, *g*), somme des idéaux (*f*) et (*g*). Il se calcule comme dernier reste non nul par l'algorithme d'Euclide.

Pour un anneau de polynômes tordus $A = K\langle\partial; \sigma, \delta\rangle$ sur un corps $K$, la situation est la même si on prend soin de ne considérer que des idéaux à gauche, c'est-à-dire
**Entrée** F et F' dans A = K⟨∂; σ, δ⟩.

**Sortie** Un pgcdd G de F et F', les cofacteurs U et V d'une relation de Bézout G = UF + VF', des cofacteurs R et S donnant un ppcmg RF = -SF'.

1. P₀ := F; U₀ := 1; V₀ := 0; P₁ := F'; U₁ := 0; V₁ := 1; i := 1.

2. Tant que Pᵢ est non nul :

a. calculer le quotient Qᵢ₋₁ et le reste Pᵢ₊₁ de la division euclidienne à droite de Pᵢ₋₁ par Pᵢ, de sorte que Pᵢ₋₁ := Qᵢ₋₁Pᵢ + Pᵢ₊₁;

b. Uᵢ₊₁ := Uᵢ₋₁ - QᵢUᵢ; Vᵢ₊₁ := Vᵢ₋₁ - QᵢVᵢ;

c. i := i + 1.

3. Renvoyer G = Rᵢ₋₁, (U, V) = (Uᵢ₋₁, Vᵢ₋₁) et (R, S) = (Uᵢ, Vᵢ).

Algorithme 30.3 – Algorithme d'Euclide étendu dans un anneau de polynômes tordus.

avec la clôture par multiplication à gauche par les éléments de A. Les notions qui en découlent sont celles de divisions euclidiennes à droite et de plus grands communs diviseurs à droite (pgcdd). Soient P₀ et P₁ deux polynômes de A. Si P₁ n'est pas nul, on écrit la division euclidienne de P₀ par P₁, sous la forme P₀ = Q₀P₁ + P₂. Tant que Pᵢ₊₂ n'est pas nul, on itère en divisant Pᵢ₊₁ par Pᵢ₊₂. Soit j la valeur finale de i, telle que Pᵢ₊₂ ≠ 0 et Pᵢ₊₂ = 0. Alors :

$$ \begin{pmatrix} P_0 \\ P_1 \end{pmatrix} = \begin{pmatrix} Q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} P_1 \\ P_2 \end{pmatrix} = \cdots = \begin{pmatrix} Q_0 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} Q_j & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} P_{j+1} \\ 0 \end{pmatrix}, $$

d'où on déduit que Pᵢ₊₁ divise P₀ et P₁ à droite : P₀ = FPᵢ₊₁ et P₁ = GPᵢ₊₁ pour des polynômes tordus F et G adéquats. Puis en inversant les matrices

$$ \begin{pmatrix} P_{j+1} \\ 0 \end{pmatrix} = \begin{pmatrix} U & V \\ R & S \end{pmatrix} \begin{pmatrix} P_0 \\ P_1 \end{pmatrix} \quad \text{pour} \quad \begin{pmatrix} U & V \\ R & S \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & -Q_j \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & -Q_0 \end{pmatrix}. $$

En particulier, Pᵢ₊₁ = UP₀ + VP₁ est élément de l'idéal à gauche AP₀ + AP₁. Un élément quelconque L = MP₀ + NP₁ de cet idéal est aussi multiple de Pᵢ₊₁ : L = (MF + NG)Pᵢ₊₁. En normalisant Pᵢ₊₁ pour le rendre unitaire, on obtient donc un pgcdd distingué de P₀ et P₁. Par ailleurs, le polynôme tordu RP₀ = -SP₁ est un plus petit multiple commun à gauche (ppcmg) de P₀ et P₁, par le même argument que dans le cas commutatif, en suivant de près les degrés tout au long de l'algorithme.

Cette discussion aboutit à l'Algorithme 30.3, que le lecteur comparera aux algorithmes d'Euclide et d'Euclide étendu du Chapitre 6, aux pages 113 et 116.

On a vu que les algorithmes de clôture par addition entre fonctions différentiellement finies ou entre suites polynomialement récurrentes renvoient un multiple commun à gauche des polynômes tordus Lᵣ et Lₛ décrivant les deux objets f et g à additionner. Comme ces algorithmes opèrent par degrés croissants, le polynôme renvoyé est de degré minimal en ∂, parmi ceux qui annulent la somme f + g. Le polynôme annulateur de la somme f + g renvoyé par ces algorithmes est donc le ppcmg de Lᵣ et de Lₛ.
**Exemple 30.5** Nous repartons des polynômes A et B de l'Exemple 30.1 pour en calculer un pgcdd et un ppcmg. On pose $P_0 = A$, $P_1 = B$; on a déjà calculé $P_2 = -n^{-1}(n^2 + n + 1)(\partial_n - (n + 1))$ avec $P_0 = n^{-1}(n^2 - 1)P_1 + P_2$. Il vient ensuite

$$P_1 = \left( - \frac{n(n+1)}{n^2 + 3n + 3} \partial_n + \frac{n(n+1)}{n^2 + n + 1} \right) P_2 + 0.$$

Ainsi, le pgcdd unitaire est $\partial_n - (n + 1)$. Remarquons qu'il annule les solutions communes de A et B, à savoir les multiples de $n!$. Le ppcmg unitaire s'obtient par renormalisation de $RP_0 = -SP_1$ quand $R = -Q_1$ et $S = Q_1Q_0$ :

$$\partial_n^3 - \frac{n^3 + 6n^2 + 8n + 5}{n^2 + n + 1} \partial_n^2 + \frac{2n^3 + 9n^2 + 13n + 7}{n^2 + n + 1} \partial_n - \frac{(n^2 + 3n + 3)(n + 1)}{n^2 + n + 1}.$$

Notons que ses solutions sont toutes les solutions de A et B : les combinaisons linéaires de $n!$, $n$ et $1$.

## 30.6 Relations de contiguïté

Un grand nombre de fonctions spéciales sont en fait des fonctions $f_n(x)$ d'une variable continue $x$ et d'une variable discrète $n$. Les familles de telles fonctions dont l'intérêt a été révélé, par exemple par la physique mathématique, sont telles que la dépendance en $x$ est liée à la dépendance en $n$. Il apparaît que très fréquemment, la fonction $f_{n+\alpha}(x)$, pour $\alpha = \pm 1$, est reliée à la fonction $f_n(x)$ et à ses dérivées. C'est le cas pour la classe importante des fonctions hypergéométriques, c'est-à-dire, pour les fonctions de l'analyse données par les séries hypergéométriques introduites au Chaitre 29, Section 29.1, et pour des fonctions limites de fonctions hypergéométriques, dont un certain nombre de familles de polynômes orthogonaux classiques.

Dans cette section, nous considérons des fonctions differentiellement finies paramétrées et résolvons algorithmiquement des problèmes tels que la détermination d'une relation de la forme

$$f_{n+1}(x) = \sum_{i=0}^{r-1} a_i(x) f_n^{(i)}(x)$$

pour la suite de polynômes

$$f_n(x) = \sum_{k=0}^{n} (-1)^k \binom{n}{k}^2 \binom{n+k}{k} x^k.$$

Ici, la relation explicite est

$$\begin{aligned} f_{n+1}(x) = 12 \frac{x^3(x+1)}{(n+1)^3} f_n'''(x) &+ 4 \frac{x^2(2n+2xn+11+14x)}{(n+1)^3} f_n''(x) \\ &- 4 \frac{x(5xn^2-n^2-4n-6+2xn-9x)}{(n+1)^3} f_n'(x) - \frac{16xn-n-1+4x}{n+1} f_n(x). \end{aligned}$$
L'opérateur différentiel linéaire implicitement au membre droit s'appelle un opérateur de montée; un opérateur qui donnerait $f_{n-1}(x)$ s'appelle un opérateur de descente. Une relation linéaire entre les decalées $f_{n+i}(x)$ et ne faisant intervenir aucune dérivation s'appelle une relation de contiguïté.

## Fonction hypergéométrique de Gauss

La plus simple des fonctions hypergéométriques est la fonction hypergéométrique de Gauss, définie par

$$F(a, b; c; x) = {}_2F_1\left(\begin{array}{c} a, b \\ c \end{array}\middle| x\right) = \sum_{k \ge 0} \frac{(a)_k (b)_k}{(c)_k} \frac{x^k}{k!} \quad (30.2)$$

La notation ${}_2F_1$ a déjà été introduite au Chapitre 29, ainsi que le symbole de Pochhammer

$$(s)_n = s(s+1)\cdots(s+n-1) = \frac{\Gamma(s+n)}{\Gamma(s)},$$

lequel vérifie

$$\frac{(s)_{n+1}}{(s)_n} = s + n \quad \text{et} \quad \frac{(s+1)_n}{(s)_n} = \frac{s+n}{s}.$$

Oublions la dépendance en $b$ et $c$ du coefficient de $x^k$ dans la somme (30.2), coefficient que nous notons $u_{a,k}$. Nous avons

$$u_{a,k+1} = \frac{(a+k)(b+k)}{(c+k)(k+1)} u_{a,k} \quad \text{et} \quad u_{a+1,k} = \left(\frac{k}{a} + 1\right) u_{a,k}.$$

La première de ces identités nous fournit le polynôme tordu

$$(c+k)(k+1)\partial_k - (a+k)(b+k) \in \mathbb{Q}(a,b,c)[k]\langle\partial_k; S_k\rangle$$

qui annule $u$. Pour $k = -1$, cette récurrence impose $u_{a,-1} = 0$, ce qui permet d'étendre la suite $u$ à toute valeur $k \in \mathbb{Z}$ tout en continuant de vérifier la récurrence. Par le morphisme vu en Section 30.2 pour effectuer le passage à la série génératrice, nous obtenons

$$(c + x\partial_x)(x\partial_x + 1)x^{-1} - (a + x\partial_x)(b + x\partial_x) \\ = ((x\partial_x)^2 + (c+1)x\partial_x + c)x^{-1} - ((x\partial_x)^2 + (a+b)x\partial_x + ab) \\ = x(1-x)\partial_x^2 + (c - (a+b+1)x)\partial_x - ab \in \mathbb{Q}(a,b,c)[x, x^{-1}]
\langle\partial_x; \text{id}, D_x\rangle.$$

Notons $L$ ce polynôme tordu en $\partial_x$. La deuxième identité sur $u$ donne, après somma-
tion, $F(a+1, b; c; x) = (a^{-1}x\partial_x + 1) \cdot F(a, b; c; x)$; c'est-à-dire qu'un opérateur de montée est donné par le polynôme tordu $L_\uparrow = a^{-1}x\partial_x + 1$.

Définissons $G(a, b; c; x)$ comme étant $F(a+1, b; c; x)$. Supposons qu'il existe un in-
verse à gauche $V$ de $L_\uparrow$ modulo $L$ à droite. Alors $VL_\uparrow - 1$ est un multiple à gauche de $L$,
qui annule donc $F$. Ainsi, $F = VL_\uparrow \cdot F = V \cdot G$, autrement dit, $V$ représente un opérateur
de descente de G. On obtient un opérateur de descente pour F par un simple décalage arrière de $a$ dans V. Pour un calcul effectif, la division euclidienne

$$L = Q(a^{-1}x\partial_{x} + 1) - (c - a - 1)ax^{-1} \quad \text{où} \quad Q = a(1-x)\partial_{x} + (c-a-1)ax^{-1} - ab$$

donne l'opérateur de descente après avoir décalé $a$ dans $(c - a - 1)^{-1}a^{-1}xQ$ par

$$L_{\downarrow} = \frac{x(1-x)}{a-c}\partial_{x} - \frac{bx}{a-c} - 1.$$

Notre objectif est maintenant de calculer une relation de contiguïté pour F. Nous avons obtenu $L_{\uparrow}(a) \cdot F = \partial_{a} \cdot F$, où nous avons noté explicitement la dépendance en $a$ du polynôme tordu $L_{\uparrow}$. Il s'ensuit la relation

$$\partial_{a}^{i} \cdot F = L_{\uparrow,i}(a) \cdot F \quad \text{où} \quad L_{\uparrow,i}(a) = L_{\uparrow}(a+i-1) \cdots L_{\uparrow}(a+1)L_{\uparrow}(a),$$

dans laquelle nous pouvons, comme toujours, remplacer un polynôme agissant sur la fonction F par le reste de la division euclidienne de ce polynôme par L, qui annule F. Ainsi, une relation de contiguïté s'obtient en recherchant une combinaison linéaire à coefficients dans $\mathbb{Q}(a, b, c, x)$ des restes modulo L à droite des $L_{\uparrow,i}(a)$ pour $i = 0, 1, 2$.

**Exercice 30.5** Terminer ce calcul pour retrouver :

$$(a+1)(1-x)F(a+2,b;c;x) + (c-xb + (a+1)(x-2))F(a+1,b;c;x) \\ + (a-c+1)F(a,b;c;x) = 0.$$

### Extension aux séries partiellement hypergéométriques

Nous considérons maintenant des sommes

$$f_n(x) = \sum_{k \ge 0} u_{n,k} x^k$$

dans lesquelles $u$ n'est hypergéométrique qu'en $n$, mais est seulement polynomialement récurrente en $k$, et satisfait à la relation

$$a_p(n,k)u_{n,k+p} + \cdots + a_0(n,k)u_{n,k} = 0.$$

Comme dans le cas doublement hypergéométrique, cette relation fournit une relation purement différentielle sur $f$. Comme précédemment, aussi, la relation de récurrence du premier ordre en $n$ sur $u$ donne une expression de $f_{n+1}(x)$ comme combinaison linéaire de dérivées. On procède donc comme dans la section précédente pour calculer opérateurs de montée, de descente, et relations de contiguïté.

**Exercice 30.6** — Assez calculatoire. Calculer l'opérateur de montée annoncé dans l'introduction de cette section.
## Notes

La structure d'anneau de polynômes tordus a été introduite et étudiée par Ore dans les années 1930 [Ore33], avec le dessein explicite de traiter des systèmes fonctionnels linéaires [Ore31]. Dans ces travaux, les polynômes tordus sont simplement appelés « non commutatifs ». Dans la littérature moderne, on parle souvent de « polynômes » ou d'« opérateurs de Ore », et encore d'« opérateurs pseudo-linéaires » [BP96].

Notre terminologie de « polynôme tordu » est la traduction de l'anglais « skew polynomial », où « skew » signifie « de biais », « oblique ». Certains auteurs ont proposé la traduction « polynôme gauche », où « gauche » a le sens de « voilé », par opposition à « plan ». Mais nous avons préféré éviter toute confusion avec des notions algébriques de multiple, module, fraction, etc, pour lesquelles « gauche » a le sens opposé de « droite ». De plus, la littérature note généralement les anneaux de polynômes tordus avec des crochets, par $A[\partial; \sigma, \delta]$, mais les chevrons nous semblent mieux évoquer que l'anneau en question est une algèbre sur $A$ donnée par le générateur $\partial$ et des relations induites par $\sigma$ et $\delta$, et n'est en général pas commutatif.

L'interprétation de la Section 30.2 du lien par morphisme entre série et suite de coefficients est implicite dans les travaux sur la théorie des D-modules (voir l'article de Cartier [Car92] pour une exposition simple). Elle a été utilisée de façon explicite pour le cadre binomial par Bostan, Chyzak, Cluzeau et Salvy [Bos+06a].

Les algorithmes de recherche de solutions rationnelles interviennent naturellement comme base des algorithmes de factorisation [BP94b; Bro92], dont est tiré l'Exercice 30.4.

Les questions de factorisation d'opérateurs linéaires et de résolution mènent à une théorie de Galois : la théorie de Galois différentielle [PS03; Sin07] comme celle à différence [PS97] étudient les applications linéaires qui échangent les solutions d'une équations fonctionnelle linéaire. Un succès de la théorie différentielle est l'étude des solutions dites « liouviliennes » d'une équation linéaire différentielle, données explicitement en termes de compositions d'opérations élémentaires (exponentiations, prises de logarithmes, extensions algébriques). La théorie fournit aussi des informations sur les développements asymptotiques des solutions, notamment en présence de singularités faisant intervenir des exponentielles.

Le résultant différentiel de deux équations différentielles a été défini par Berkovich et Tsirulik en 1986 [BT86]. Chardin [Cha91] a défini les sous-résultants de deux équations différentielles. Li [Li00; Li98] a étendu la définition aux polynômes de Ore. On trouve, dans les travaux de Grigoriev [Gri90] d'une part et de Li et Nemes [LN97] d'autre part, des algorithmes efficaces pour le calcul du pgcdd de deux opérateurs différentiels ; ces algorithmes ont été étendus aux sous-résultants par Li à la fin des années 1990 [Li00; Li98]. En 1991, Chardin a donné une expression du résultant de deux équations différentielles en termes de leurs solutions [Cha91]. Cela a été ensuite généralisé au cadre des polynômes de Ore par Hong [Hon01a; Hon01b].

La question du calcul algorithmique de relations de contiguïté a été abordée d'abord dans le cas purement hypergéométrique par Takayama [Tak89], puis dans le cas partiellement hypergéométrique par Chyzak et Salvy [CS98].
Bibliographie

Bos+06a BOSTAN, A., F. CHYZAK, T. CLUZEAU et B. SALVY (2006). « Low complexity algorithms for linear recurrences ». In : *ISSAC'06 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 31–38.

BP94b BRONSTEIN, M. et M. PETKOVŠEK (1994). « On Ore rings, linear operators and factorisation ». In : *Programmirovanie*, vol. 1. Also available as Research Report 200, Informatik, ETH Zürich, p. 27–44.

BP96 BRONSTEIN, Manuel et Marko PETKOVŠEK (1996). « An introduction to pseudo-linear algebra ». In : *Theoretical Computer Science*, vol. 157, p. 3–33.

Bro92 BRONSTEIN, Manuel (1992). « Linear ordinary differential equations : breaking through the order 2 barrier ». In : *ISSAC'92 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 42–48.

BT86 BERKOVICH, L. M. et V. G. TSIRULIK (1986). « Differential resultants and some of their applications ». In : *Differentsial'nye Uravneniya*, vol. 22, n°5. English translation in : *Differential Equations*, Plenum Publ. Corp., Vol. 22, no. 5, pp. 530–536. NY Plenum 1986, p. 750–757, 914.

Car92 CARTIER, Pierre (1992). « Démonstration “automatique” d'identités et fonctions hypergéométriques (d'après D. Zeilberger) ». In : *Astérisque*, vol. 1991/92, n°206. Séminaire Bourbaki, Exp. No. 746, 3, 41–91.

Cha91 CHARDIN, Marc (1991). « Differential resultants and subresultants ». In : *Fundamentals of computation theory*. Vol. 529. Lecture Notes in Computer Science. Gosen : Springer-Verlag, p. 180–189.

CS98 CHYZAK, Frédéric et Bruno SALVY (1998). « Non-commutative elimination in Ore algebras proves multivariate holonomic identities ». In : *Journal of Symbolic Computation*, vol. 26, n°2, p. 187–227.

Gri90 GRIGORIEV, D. Yu. (1990). « Complexity of factoring and calculating the GCD of linear ordinary differential operators ». In : *Journal of Symbolic Computation*, vol. 10, n°1, p. 7–37.

Hon01a HONG, Hoon (2001). « Ore principal subresultant coefficients in solutions ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 11, n°3, p. 227–237.

Hon01b — (2001). « Ore subresultant coefficients in solutions ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 12, n°5, p. 421–428.

Li00 LI, Ziming (2000). « Greatest common right divisors, least common left multiples, and subresultants of Ore polynomials ». In : *Mathematics localization and applications*. San Diego, CA : Academic Press, p. 297–324.

Li98 — (1998). « A subresultant theory for Ore polynomials with applications ». In : *ISSAC'98 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 132–139.

LN97 LI, Z. et I. NEMES (1997). « A modular algorithm for computing greatest common right divisors of Ore polynomials ». In : *ISSAC'97 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 282–289.

Ore31 ORE, Oystein (1931). « Linear equations in non-commutative fields ». In : *Annals of Mathematics*, vol. 32, p. 463–477.
Ore33 ORE, Oystein (1933). « Theory of non-commutative polynomials ». In : *Annals of Mathematics*, vol. 34, n°3, p. 480-508.

PS03 PUT, Marius van der et Michael F. SINGER (2003). *Galois theory of linear differential equations*. Vol. 328. Grundlehren der Mathematischen Wissenschaften. Springer-Verlag.

PS97 — (1997). *Galois theory of difference equations*. Vol. 1666. Lecture Notes in Mathematics. Springer-Verlag.

Sin07 SINGER, M. F. (2007). « Introduction to the Galois theory of linear differential equations ». url : https://arxiv.org/abs/0712.4124.

Tak89 TAKAYAMA, Nobuki (1989). « Gröbner basis and the problem of contiguous relations ». In : *Japan Journal of Applied Mathematics*, vol. 6, n°1, p. 147-160.
# 31. Algèbres de Ore et fonctions spéciales de plusieurs variables

## Résumé

Les polynômes tordus univariés du Chapitre 30 se généralisent à plusieurs indéterminées pour bien modéliser des opérateurs linéaires agissant sur des fonctions et suites à plusieurs variables ou indices. Cette représentation polynomiale ouvre la voie à une théorie algorithmique de leurs idéaux à gauche, qui sont vus comme idéaux annulateurs de fonctions et suites, maintenant représentés comme solutions implicites de systèmes fonctionnels linéaires. Une extension non commutative de l’algorithmique des bases de Gröbner fournit les briques de base pour calculer avec cette nouvelle représentation : les notions de fonctions différentiellement finies (univariées) et de suites polynomialement récurrentes (à un indice) se fondent dans la généralité des fonctions $\partial$-finies.

## 31.1 Algèbres de Ore rationnelles

Une généralisation à plusieurs dérivations et décalages de la notion d’anneau de polynômes tordus du chapitre précédent est donnée par la définition qui suit.

**Définition 31.1 — Algèbre de Ore.** Étant donnés

- un corps (commutatif) $k(x) = k(x_1, \dots, x_r)$ de fractions rationnelles,

- $r$ endomorphismes $\sigma_i$ de $k$-algèbre de $k(x)$, injectifs et commutant deux à deux,

- pour chaque $i$ une $\sigma$-dérivation $\delta_i$ relative à $\sigma_i$, c’est-à-dire pour chaque $i$ un endomorphisme linéaire pour lequel $\delta_i(ab) = \sigma_i(a)\delta_i(b) + \delta_i(a)b$ dès que $a$ et $b$ sont dans $k(x)$, toutes ces $\sigma$-dérivations commutant deux à deux et $\delta_i$ commutant avec $\sigma_j$ chaque fois que $i \neq j$,
— r indéterminées $\partial_i$,
l'algèbre de Ore (rationnelle) notée $k(x_1, \dots, x_r)\langle\partial_1, \dots, \partial_r; \sigma_1, \dots, \sigma_r, \delta_1, \dots, \delta_r\rangle$ ou plus simplement $k(x)\langle\partial; \sigma, \delta\rangle$ est la $k(x)$-algèbre associative engendrée par les $\partial_i$ modulo les relations

$$ \partial_i a = \sigma_i(a)\partial_i + \delta_i(a), \quad \partial_i\partial_j = \partial_j\partial_i, $$

quand $a$ est dans $k(x)$. On note plus simplement $k(x_1, \dots, x_r)\langle\partial_1, \dots, \partial_r; \sigma_1, \dots, \sigma_r\rangle$ ou encore $k(x)\langle\partial; \sigma\rangle$ le cas où tous les $\delta_i$ sont nuls.

**Exemple 31.1** En notant $x$ l'opérateur de multiplication par $x$ et $n$ celui de multiplication par $n$, on vérifie l'existence d'une algèbre de Ore

$$ A = \mathbb{C}(n, x)\langle\partial_n, \partial_x; S_n, \mathrm{id}, 0, D_x\rangle $$

avec $S_n(n) = n + 1$, $S_n(x) = x$, $D_x(n) = 0$, $D_x(x) = 1$, et plus généralement $S_n(a) = a(n+1, x)$ et $D_x(a) = da/dx$ quand $a = a(n, x) \in \mathbb{C}(n, x)$.

## 31.2 Idéal annulateur et module quotient

Les éléments des algèbres de Ore représentent des opérateurs linéaires, différents, de récurrence, ou autres, et agissent donc sur des fonctions, suites, suites de fonctions, etc. Pour montrer que ces objets sont une bonne représentation polynomiale des opérateurs linéaires, l'exemple de la famille des polynômes orthogonaux de Laguerre va nous servir pour toute la suite du chapitre.

Pour chaque paramètre strictement positif $\alpha$, l'intégrale

$$ (f | g) = \int_{0}^{\infty} f(x)g(x)x^{\alpha}e^{-x} dx $$

définit un produit scalaire sur les fonctions polynomiales réelles. Par orthogonalisation de Gram-Schmidt (voir la Section 20.2), on déduit l'existence de bases orthogonales échelonnées en degré. On a par exemple la base des polynômes orthogonaux de Laguerre, donnée par

$$ L_n^{(\alpha)}(x) = \frac{1}{n!} x^{-\alpha} e^x \left(\frac{d}{dx}\right)^n (e^{-x} x^{n+\alpha}) = \frac{1}{n!} \sum_{k=0}^{n} (-1)^k \binom{n}{k} (\alpha + k + 1) \cdots (\alpha + n) x^k. $$

On vérifie que ces polynômes vérifient les relations (linéaires)

$$ \begin{align*} (n+2)L_{n+2}^{(\alpha)} - (2n+\alpha+3-x)L_{n+1}^{(\alpha)} + (n+\alpha+1)L_n^{(\alpha)} &= 0, \\ xL_n^{(\alpha)'} - (n+1)L_{n+1}^{(\alpha)} + (n+\alpha+1-x)L_n^{(\alpha)} &= 0, \\ xL_n^{(\alpha)''} + (\alpha+1-x)L_n^{(\alpha)'} + nL_n^{(\alpha)} &= 0, \end{align*} $$
avec les conditions initiales $L_0^{(\alpha)} = 1$ et $L_1^{(\alpha)} = \alpha + 1 - x$. Dans l'algèbre de Ore A introduite par l'Exemple 31.1 ci-dessus, ces équations se recodent en les polynômes tordus suivant, qui annulent la suite de fonctions polynomiales $L^{(\alpha)}$ :

$$p_1 = (n+2)\partial_n^2 - (2n + \alpha + 3 - x)\partial_n + (n + \alpha + 1),$$

$$p_2 = x\partial_x - (n+1)\partial_n + (n + \alpha + 1 - x),$$

$$p_3 = x\partial_x^2 + (\alpha + 1 - x)\partial_x + n.$$

Ces trois polynômes engendrent un idéal à gauche dans A (voir la définition en Section 30.1) et cet idéal est appelé l'idéal annulateur de $L^{(\alpha)}$ dans A. Cette stabilité reflète le fait que l'addition terme à terme de deux relations linéaires vérifiées par $L^{(\alpha)}$ est une nouvelle relation linéaire vérifiée par $L^{(\alpha)}$, de même qu'en appliquant un opérateur linéaire sur une relation linéaire vérifiée par $L^{(\alpha)}$, on retrouve une relation linéaire vérifiée par $L^{(\alpha)}$.

**Exemple 31.2** En partant de la troisième équation donnée pour caractériser les polynômes de Laguerre, un décalage avant de $n$ et une dérivation par rapport à $x$ donnent respectivement

$$xL_{n+1}^{(\alpha)}'' + (\alpha + 1 - x)L_{n+1}^{(\alpha)}' + (n+1)L_{n+1}^{(\alpha)} = 0$$

et

$$xL_n^{(\alpha)'''} + (\alpha + 2 - x)L_n^{(\alpha)''} + (n - 1)L_n^{(\alpha)'} = 0.$$

L'addition de ces deux équations donne l'équation fonctionnelle linéaire

$$xL_n^{(\alpha)'''} + (\alpha + 2 - x)L_n^{(\alpha)''} + (n - 1)L_n^{(\alpha)'} + xL_{n+1}^{(\alpha)''} + (\alpha + 1 - x)L_{n+1}^{(\alpha)'} + (n + 1)L_{n+1}^{(\alpha)} = 0,$$

laquelle correspond au polynôme tordu

$$(\partial_x + \partial_n)p_3 = x\partial_x^3 + (\alpha + 2 - x)\partial_x^2 + (n - 1)\partial_x + x\partial_x^2\partial_n + (\alpha + 1 - x)\partial_x\partial_n + (n + 1)\partial_n.$$

Dans le cas commutatif, le quotient d'une algèbre A de polynômes par l'un de ses idéaux (bilatères) I reste munie d'un produit canonique et est donc une algèbre. Cette propriété n'est plus réalisée dans le cas d'une algèbre de Ore $A = k(x)(\partial; \sigma, \delta)$ et d'un idéal à gauche I. Néanmoins, le quotient A/I conserve une addition canonique, ainsi que la stabilité par multiplication à gauche par tout élément de A, ce qui fait de ce quotient un module à gauche sur A et en particulier un espace vectoriel sur $k(x)$.

Dans le cas commutatif, un cadre particulier important est celui d'un quotient de dimension finie comme espace vectoriel, car il représente une famille finie de points solutions (voir la Section 25.2). Le cas d'un quotient d'une algèbre de Ore qui est un espace vectoriel sur $k(x)$ de dimension finie est lui-aussi important; dans l'interprétation en opérateurs linéaires, il correspond en règle générale à un espace vectoriel de solutions de dimension finie sur $k$.

Dans la Section 31.4, nous détaillerons ce lien dans le cas d'opérateurs différentiels;
d'autres cadres fournissent le même genre de résultats. Nous irons plus loin sur le sujet dans la Section 31.5 sur les fonctions $\partial$-finies.

Toute autre famille de polynômes orthogonaux classiques se traiterait de la même manière et aurait pu servir de support à ce chapitre. La même nature de système linéaire avec une dérivation sur une variable et un décalage sur une autre permet de traiter de la même façon nombre de familles de fonctions spéciales paramétrées, telles les fonctions de Bessel, de Hankel, etc.

## 31.3 Bases de Gröbner pour les idéaux à gauche

La propriété essentielle qui fait fonctionner toute la théorie des bases de Gröbner et l'algorithme de Buchberger dans le cadre de polynômes commutatifs est que le monôme de tête d'un produit de polynômes est le produit des monômes de tête des termes du produit. Cette propriété reste vérifiée sur des polynômes non commutatifs sujets aux relations de définition des algèbres de Ore rationnelles, dès lors qu'on considère des ordres monomiaux sur les $\partial_i$. En refaisant la théorie en s'efforçant de faire toutes les combinaisons linéaires avec des facteurs à gauche, on obtient le résultat suivant (cf. le Chapitre 23 et la Section 24.3 sur les bases de Gröbner classiques) :

**Théorème 31.1** Soit A une algèbre de Ore rationnelle.

i. Tout idéal à gauche I de A admet pour chaque ordre monomial (admissible) sur les $\partial_i$ une unique base de Gröbner minimale réduite G, au sens où l'une quelconque des propriétés équivalentes suivantes est vérifiée :

1. la partie stable du monoïde des monômes en les $\partial_i$ engendrée par les monômes de tête des éléments de G est égale à celle engendrée par ceux de I;

2. tout $f$ non nul de I est réductible par G;

3. pour tout $f$ dans A, il existe un unique $r$ dans A dont aucun monôme ne soit divisible par un monôme de tête d'un élément de G et tel que $f-r$ soit dans l'idéal I;

4. pour tout $f$ dans I, le reste de la division (à droite) de $f$ par G est nul.

ii. Soit $P = \{p_k\}_{1 \le k \le r}$ un système de générateurs non nuls d'un idéal à gauche I de A. Tous les S-polynômes Spoly($p_i$, $p_j$) (définis par des combinaisons linéaires à gauche) se réduisent à 0 par P si et seulement si P est une base de Gröbner de l'idéal.

iii. Une variante de l'algorithme de Buchberger termine et renvoie une base de Gröbner de tout idéal à gauche I de A.

*Démonstration.* Nous nous cantonnons ici à montrer l'équivalence des quatre propriétés du point i, par une preuve cyclique. Supposons 1. et soit $f$ non nul de I : le monôme de tête $f$ est donc multiple d'un monôme de tête d'un élément de G, et $f$ est ainsi réductible par G. Supposons 2., soit $f$ dans A, et soit $r$ le reste de la division multivariée non commutative de $f$ par G. Alors $r$ remplit les conditions d'existence demandées par le point 3. ; si $r'$ remplit les mêmes conditions, alors $r-r' = (f-r')-(f-r)$ est dans I. Si cette différence est non nulle, alors par l'hypothèse 2. elle est réductible par G : son monôme de tête, qui doit être un monôme de $r$ ou de $r'$, est divisible par un monôme de tête de G, ce qui est une contradiction. Donc $r = r'$, prouvant
ainsi l'unicité. Supposons 3. et soit $f$ dans $I$: l'hypothèse 3. s'applique pour $r=0$, qui est donc le reste nécessaire de la division multivariée non commutative de $f$ par G. Supposons enfin 4. et considérons un monôme $m$ élément de la partie stable engendrée par les monômes de tête de $I$. Cet $m$ est donc multiple (à gauche) d'un monôme de tête d'un élément de G. La partie stable engendrée par les monômes de tête des éléments de G inclut donc celle engendrée par ceux de $I$; l'autre inclusion étant évidente vu que les éléments de G sont dans $I$, il y a égalité. ■

Une spécificité du cas non commutatif réside dans le calcul des S-polynômes. Considérons le cas commutatif et faisons l'hypothèse que les calculs, pour des raisons d'efficacité, écrivent tous les polynômes en chassant les dénominateurs. (Ceci suppose donc que le corps des coefficients peut être vu comme l'anneau des fractions d'un certain anneau, en règle générale $\mathbb{Z}[\alpha, \dots]$ pour des paramètres $\alpha, \dots$) Le S-polynôme de deux polynômes non nuls $f_1$ et $f_2$ se définit alors par

$$ \operatorname{Spoly}(f_1, f_2) = \frac{c_2}{\operatorname{pgcd}(c_1, c_2)} \frac{m_2}{\operatorname{pgcd}(m_1, m_2)} f_1 - \frac{c_1}{\operatorname{pgcd}(c_1, c_2)} \frac{m_1}{\operatorname{pgcd}(m_1, m_2)} f_2, $$

où $c_i$ dénote le coefficient de tête de $f_i$ et $m_i$ son monôme de tête, pour $i=1,2$. Cette formule doit être adaptée dans le cas de polynômes tordus : $c_1$ et $c_2$ dénotent maintenant respectivement le coefficient de tête de

$$ \frac{m_2}{\operatorname{pgcd}(m_1, m_2)} f_1 \quad \text{et} \quad \frac{m_1}{\operatorname{pgcd}(m_1, m_2)} f_2, $$

qui peuvent dépendre des $\sigma_i$, mais où les notions divisions et pgcd sont vues comme si $m_1$ et $m_2$ étaient dans un monde commutatif. Plutôt que de poursuivre la théorie dans le détail, montrons le calcul sur un exemple.

**Exemple 31.3** En repartant des polynômes $p_1$ et $p_2$ qui annulent la suite des polynômes orthogonaux de Laguerre, montrons que le polynôme $p_3$ s'obtient par élimination de $\partial_n$ par un calcul pour l'ordre lexicographique induit par $\partial_n > \partial_x$. Pour cet ordre, le terme de tête de $p_1$ est $(n+2)\partial_n^2$, celui de $p_2$ est $-(n+1)\partial_n$. On calcule donc d'abord le S-polynôme de $p_1$ et de $p_2$, sous la forme

$$ \operatorname{Spoly}(p_1, p_2) = p_1 + \partial_n p_2 = x \partial_x \partial_n - (n+1)\partial_n + (n+\alpha+1). $$

Remarquons que ce S-polynôme n'est pas $(n+1)p_1 + (n+2)\partial_n p_2$, lequel aurait $(n+2)\partial_n^2$ comme terme de tête, et non pas $\partial_x \partial_n$ pour monôme de tête. Il est réductible par $p_2$; après multiplication par $(n+1)$ et ajout de $x\partial_x p_2$, on obtient

$$ -(n+1)^2 \partial_n + x^2 \partial_x^2 + (n+\alpha+2-x)x \partial_x + (n+1)(n+\alpha+1) - x. $$

Ce polynôme a $\partial_n$ pour monôme de tête et est réductible par $p_2$; après retranche-ment de $(n+1)p_2$, on aboutit à

$$ x^2 \partial_x^2 + (\alpha + 1 - x)x \partial_x + nx, $$

qui n'est autre que $xp_3$. En poursuivant, on montre que les S-polynômes de $p_1$ et $p_2$
avec $p_3$ se réduisent à 0 ; puisque le monôme de tête de $p_2$, $\partial_n$, divise celui de $p_1$, $\partial_n^2$, une base de Gröbner minimale pour l'ordre $\text{lex}(\partial_n, \partial_x)$ est $\{p_2, p_3\}$.

De façon analogue à l'exemple précédent, une base de Gröbner pour l'ordre $\text{lex}(\partial_x, \partial_n)$ de l'idéal engendré par $p_2$ et $p_3$ est $\{p_1, p_2\}$. Les bases de Gröbner permettent ainsi de déterminer la redondance du système $\{p_1, p_2, p_3\}$.

**Exercice 31.1** Calculer une base de Gröbner pour l'ordre $\text{lex}(\partial_x, \partial_n)$ de l'idéal engendré par $p_2$ et $p_3$ et vérifier le point ci-dessus. ■

Les polynômes $p_1, p_2, p_3$ qui annulent la suite des polynômes orthogonaux de Laguerre sont encore plus contraints qu'il n'y paraît jusqu'à présent : $p_2$ se déduit en fait de $p_1$. En effet, ne connaissant que $p_1$, on peut rechercher le polynôme $p_2$ sous la forme indéterminée

$$p_2 = \partial_x - u(n,x)\partial_n - v(n,x),$$

pour des fractions rationnelles à déterminer $u$ et $v$, et faire l'hypothèse heuristique que $\{p_1, p_2\}$ est une base de Gröbner pour l'ordre $\text{lex}(\partial_x, \partial_n)$. (Cette hypothèse heuristique est en fait naturelle dès qu'on sait qu'on a à faire à une famille de polynômes orthogonaux.) La contrainte d'être une base de Gröbner implique que le S-polynôme Spoly($p_1, p_2$) doit se réduire à 0 par $\{p_1, p_2\}$, ce qui impose certaines relations différentielles et à différence sur $u$ et $v$.

**Exercice 31.2** Utiliser la théorie des bases de Gröbner pour donner un système de récurrences linéaires sur $u$ et $v$ qui, après résolution, redonne le polynôme $p_2$. (Pour la résolution, on se souviendra des conditions initiales $L_0^{(\alpha)} = 1$ et $L_1^{(\alpha)} = \alpha + 1 - x$.) ■

## 31.4 Module quotient et dimension de l'espace des solutions

### Séries formelles solutions en un point ordinaire dans le cas différentiel

Considérons une algèbre de Ore

$$A = \mathbb{C}(x_1, \dots, x_r)\langle \partial_1, \dots, \partial_r ; \text{id}, \dots, \text{id}, \text{D}_{x_1}, \dots, \text{D}_{x_r} \rangle,$$

un idéal à gauche $I$ de cette algèbre, donné par un système différentiel linéaire. Nous voulons décrire les solutions séries annulées par tous les éléments de $I$, où une série est ici un élément de $\mathbb{C}[[x_1, \dots, x_r]]$, c'est-à-dire une combinaison linéaire formelle éventuellement infinie de monômes à exposants entiers positifs. Dans cet objectif, cette section fournit un analogue en plusieurs variables de la conversion entre équation différentielle décrivant une série différentiellement finie d'une variable et équation de récurrence vérifiée par la suite polynomialement récurrente des coefficients.

Fixons un ordre monomial sur les monômes en les $\partial_i$, puis, pour cet ordre, une base de Gröbner $B$ de $I$, donnée par des éléments de $A$ sans fractions, c'est-à-dire avec des coefficients polynomiaux. Cette base de Gröbner $B$ fournit un escalier; notons $S$ l'ensemble des multi-exposants $s = (s_1, \dots, s_r)$ des monômes $\partial^s = \partial_1^{s_1} \cdots \partial_r^{s_r}$ sous l'escalier, c'est-à-dire des monômes qui ne sont pas réductibles par $B$. Le module quotient $A/I$ a alors une base d'espace vectoriel sur $\mathbb{C}(x)$ constituée des $\partial^s + I$, les classes des $\partial^s$ modulo $I$, pour $s$ décrivant $S$. Soit $u$ le polynôme produit des coefficients
de tête des éléments de B et faisons l'hypothèse que $u$ ne s'annule pas pour $x_1 = \cdots = x_r = 0$. Nous affirmons qu'alors, l'idéal I admet un espace vectoriel de solutions séries dans $\mathbb{C}[[x_1, \dots, x_r]]$ de dimension le cardinal de S, c'est-à-dire la dimension sur $\mathbb{C}(x)$ de A/I vu comme espace vectoriel. On dit dans ce cas que le point $(0, \dots, 0)$ est régulier pour le système différentiel linéaire définissant l'idéal I.

En effet, pour tout multi-exposant $n = (n_1, \dots, n_r)$, la réduction du monôme $\partial^n$ par B fournit une combinaison linéaire $\sum_{s \in S} v_{n,s} \partial^s$ congrue à $\partial^n$ modulo I. Ceci généralise la récriture d'un $\partial^N$ faite en Section 30.3. Notons que par construction, les coefficients $v_{n,s}$ sont éléments de $\mathbb{C}[x_1, \dots, x_r, u^{-1}]$ et ont ainsi une évaluation bien définie en $x_1 = \cdots = x_r = 0$. Par suite, puisque chaque élément de I s'annule sur toute solution série

$$ \phi = \sum_{n_1 \in \mathbb{N}, \dots, n_r \in \mathbb{N}} c_{n_1, \dots, n_r} x_1^{n_1} \cdots x_r^{n_r}, $$

le monôme $\partial^n$ et la somme $\sum_{s \in S} v_{n,s} \partial^s$ ont la même action sur $\phi$ :

$$ \partial^n \cdot \phi = \sum_{s \in S} v_{n,s} \partial^s \cdot \phi. $$

Une évaluation en $x_1 = \cdots = x_r = 0$ donne la relation

$$ n_1! \cdots n_r! c_{n_1, \dots, n_r} = \sum_{s \in S} v_{n,s} (0, \dots, 0) s_1! \cdots s_r! c_{s_1, \dots, s_r}. $$

Autrement dit, la série $\phi$ est totalement déterminée par ses quelques premiers coefficients $c_s$ pour $s \in S$, en nombre donné par la dimension de A/I.

L'exemple des polynômes orthogonaux de Laguerre étend déjà légèrement le cadre purement différentiel qui précède. Posons

$$ L_n^{(\alpha)}(x) = \sum_{k=0}^{n} \ell_{n,k} x^k. $$

En multipliant chaque $p_i$ pour $i = 1, 2, 3$ par $\partial_x^k$, il vient

$$ \begin{aligned} \partial_x^k p_1 &= (n+2)\partial_n^2 \partial_x^k - (2n+\alpha+3-x)\partial_n \partial_x^k + k\partial_n \partial_x^{k-1} + (n+\alpha+1)\partial_x^k, \\ \partial_x^k p_2 &= x\partial_x^{k+1} - (n+1)\partial_n \partial_x^k + (n+\alpha+k+1-x)\partial_x^k - k\partial_x^{k-1}, \\ \partial_x^k p_3 &= x\partial_x^{k+2} + (\alpha+k+1-x)\partial_x^{k+1} + (n-k)\partial_x^k. \end{aligned} $$

Après application sur $L^{(\alpha)}$, évaluation en $x = 0$ et division par $k!$, on trouve les relations de récurrence sur la famille doublement indexée des $\ell_{n,k}$

$$ \begin{aligned} (n+2)\ell_{n+2,k} - (2n+\alpha+3)\ell_{n+1,k} + \ell_{n+1,k-1} + (n+\alpha+1)\ell_{n,k} &= 0, \\ -(n+1)\ell_{n+1,k} + (n+\alpha+k+1)\ell_{n,k} - \ell_{n,k-1} &= 0, \\ (k+1)(\alpha+k+1)\ell_{n,k+1} + (n-k)\ell_{n,k} &= 0. \end{aligned} $$

En décalant la dernière vers l'arrière en $k$ puis éliminant $\ell_{n,k-1}$ entre la relation obtenue et la deuxième récurrence ci-dessus, on obtient la récurrence

$$ (n+1-k)\ell_{n+1,k} - (n+\alpha+1)\ell_{n,k} = 0. $$

Ce jeu de récurrences permet de calculer tous les $\ell_{n,k}$.
## Solutions en séries des systèmes hypergéométriques de Gel’fand, Kapranov et Zelevinsky

Un exemple concret est donné par une généralisation à plusieurs variables des séries hypergéométriques de la Section 29.1. Considérons l’algèbre de Ore A engendrée par quatre indéterminées $∂_1, ..., ∂_4$ sur le corps $\mathbb{C}(x_1, ..., x_4)$, chaque $∂_i$ représentant l’opérateur de dérivation par rapport à $x_i$, et le système

$$ 
\begin{aligned}
p_1 &= \partial_2 \partial_3 - \partial_1 \partial_4, & p_2 &= x_1 \partial_1 - x_4 \partial_4 + (1-c), \\
p_3 &= x_2 \partial_2 + x_4 \partial_4 + a, & p_4 &= x_3 \partial_3 + x_4 \partial_4 + b, \quad (31.1)
\end{aligned}
$$

pour des paramètres complexes $a, b$ et $c$ génériques. L’objectif de l’exemple est de montrer que ce système admet un espace vectoriel de solutions formelles de dimension exactement 2, où par solution formelle nous entendons maintenant une série multivariée de la forme

$$ x_1^{a_1} \cdots x_4^{a_4} \sum_{n_1 \in \mathbb{Z}, \dots, n_4 \in \mathbb{Z}} c_{n_1, \dots, n_4} x_1^{n_1} \cdots x_4^{n_4}, $$

pour des $a_i$ et des coefficients complexes, ou une combinaison linéaire de telles séries. (Il y a bien un espace vectoriel sur $\mathbb{C}$ où vivent ces séries, mais pas de produit sur ces séries. En revanche, toute série peut être multipliée par un polynôme en les $x_i$ et leurs inverses $x_i^{-1}$, ainsi que dérivée formellement par rapport à chacune des indéterminées, tout en restant dans l’espace vectoriel.)

Soit I l’idéal engendré par le système $\{p_1, ..., p_4\}$ et calculons à partir de ce système une base de Gröbner de I pour l’ordre $\text{lex}(\partial_1, ..., \partial_4)$. Les monômes de tête respectifs de $p_1$ et $p_2$ sont $\partial_1 \partial_4$ et $\partial_1$. Le S-polynôme de $p_1$ et de $p_2$ est donc

$$ \text{Spoly}(p_1, p_2) = x_1 p_1 + \partial_4 p_2 = x_1 \partial_2 \partial_3 - x_4 \partial_4^2 - c \partial_4, $$

dont le monôme de tête est $\partial_2 \partial_3$; il est donc réductible par $p_3$. Après multiplication par $-x_2$ et ajout de $x_1 \partial_3 p_3$, on obtient

$$ x_1 x_4 \partial_3 \partial_4 + a x_1 \partial_3 + x_2 x_4 \partial_4^2 + c x_2 \partial_4. $$

Ce polynôme a $\partial_3 \partial_4$ pour monôme de tête et est donc réductible par $p_4$. Après multiplication par $x_3$ et retranchement de $x_1 x_4 \partial_4 p_4$, on aboutit à

$$ ax_1 x_3 \partial_3 + (x_2 x_3 - x_1 x_4) x_4 \partial_4^2 + (c x_2 x_3 - (b+1) x_1 x_4) \partial_4, $$

qui est encore réductible par $p_4$. Après retranchement de $ax_1 p_4$, on a finalement un polynôme qui n’est pas réductible par $\{p_1, ..., p_4\}$, à savoir

$$ p_5 = (x_2 x_3 - x_1 x_4) x_4 \partial_4^2 + (c x_2 x_3 - (a + b + 1) x_1 x_4) \partial_4 - ab x_1. $$

Par ailleurs, les S-polynômes entre les polynômes $p_2, p_3$ et $p_4$ pris deux à deux sont tous nuls, comme on le vérifie en observant que les $x_i \partial_i$ commutent deux à deux. En poursuivant les calculs sur les S-polynômes $\text{Spoly}(p_i, p_5)$, on montre que tous ces derniers se réduisent à 0 par $\{p_1, ..., p_5\}$. On obtient ainsi qu’une base de Gröbner minimale est $\{p_2, p_3, p_4, p_5\}$, avec les monômes de tête respectifs $\partial_1, \partial_2, \partial_3$ et $\partial_4^2$.

Le module quotient $A/I$ a donc une base d'espace vectoriel sur $\mathbb{C}(x_1, ..., x_4)$ constituée de $1 + I$ et $\partial_4 + I$, les classes respectives de 1 et $\partial_4$ modulo I. La structure de module est donnée explicitement par l'action des $\partial_i$ sur ces deux éléments de base.