**Exercice 31.3** Donner l'expression explicite de cette action en récrivant chaque $\partial_i \cdot (1 + I)$ et chaque $\partial_i \cdot (\partial_4 + I)$ sur la base $(1 + I, \partial_4 + I)$. ■

Revenons sur les solutions séries du système (31.1). Le polynôme $p_2$ agit sur un monôme par

$$p_2 \cdot (x_1^{\lambda_1} \cdots x_4^{\lambda_4}) = (\lambda_1 - \lambda_4 + 1 - c)x_1^{\lambda_1} \cdots x_4^{\lambda_4}.$$

(Notons la distinction entre le produit dans $A$ noté $p_2 x_1^{\lambda_1} \cdots x_4^{\lambda_4}$ et l'opération de $p_2$, ici sur une serie $h$ en $x$, notée $p_2 \cdot h$; on comparera par exemple $\partial_1 x_1^5 = x_1^5 \partial_1 + 5x_1^4$ et $\partial_1 \cdot x_1^5 = 5x_1^4$.) Ainsi, un monôme $x_1^{\lambda_1} \cdots x_4^{\lambda_4}$ ne peut apparaître avec un coefficient non nul dans une série $\phi$ solution du système (31.1) que si $\lambda_1 - \lambda_4 + 1 - c$ est nul. En poursuivant ce type de raisonnement avec $p_3$ et $p_4$, on obtient de même les contraintes $\lambda_2 + \lambda_4 + a = 0$ et $\lambda_3 + \lambda_4 + a = 0$ et on aboutit à ce que les seuls monômes pouvant apparaître avec un coefficient non nul sont de la forme

$$x_1^{\lambda_4+c-1} x_2^{-\lambda_4-a} x_3^{-\lambda_4-b} x_4^{\lambda_4} = \frac{x_1^{c-1}}{x_2^a x_3^b} \left( \frac{x_1 x_4}{x_2 x_3} \right)^{\lambda_4},$$

et une solution $\phi$ est nécessairement de la forme

$$\phi = \frac{x_1^{c-1}}{x_2^a x_3^b} f\left(\frac{x_1 x_4}{x_2 x_3}\right),$$

pour une série formelle $f$ en $y$ à exposants entiers relatifs. Reste à exploiter que $\phi$ est solution de $p_1$, ou de manière équivalente de $p_5$, puisque sous la forme ci-dessus $\phi$ est déjà solution de $p_2$, $p_3$ et $p_4$. Après avoir évalué en $y = x_1 x_4 / x_2 x_3$, on a

$$0 = \frac{x_1^a x_3^b}{x_1^{c-2}} p_5 \cdot \phi = (1-y)yf''(y) + (c-(a+b+1)y)f'(y) - abf(y).$$

On reconnaît là l'équation hypergéométrique de Gauss, annulée par la série

$$f_1 = {}_2F_1\left(\begin{array}{c} a, b \\ c \end{array}\middle|y\right) = \sum_{n=0}^{\infty} \frac{(a)_n (b)_n}{(c)_n} \frac{y^n}{n!}$$

déjà rencontrée en Section 30.6. On vérifie qu'une solution formelle linéairement indépendante avec $f_1$ est $f_2 = y^{1-c} {}_2F_1\left(\begin{array}{c} a-c+1, b-c+1 \\ 2-c \end{array}\middle|y\right)$. On a ainsi obtenu deux solutions formelles linéairement indépendantes du système (31.1),

$$\phi_i = (x_1^{c-1} / x_2^a x_3^b) f_i(x_1 x_4 / x_2 x_3) \quad \text{pour } i = 1 \text{ et } i = 2.$$

Pour tout système différentiel représenté par un idéal I de $A$, un résultat d'analyse, le théorème de Cauchy-Kovalevskaya, affirme l'existence, au voisinage de tout point en dehors d'une certaine variété (algébrique affine) $S$, d'un $\mathbb{C}$-espace vectoriel de solutions analytiques de dimension celle sur $\mathbb{C}(x)$ de l'espace vectoriel A/I. Or, on
montre que cette variété S est incluse dans le lieu des zéros du produit des coefficients polynomiaux de tête d'une base de Gröbner à l'écrite sans fractions.

Dans le cas de notre exemple, la dimension de A/I est 2 et la variété S est incluse dans le lieu des zéros de $x_1 \cdots x_4(x_2x_3 - x_1x_4)$. Hors de ce lieu, y n'est ni nul, ni infini, ni égal à 1, et les fonctions $\phi_1$ et $\phi_2$ sont donc analytiques puisque, moyennant quelques hypothèses sur les paramètres $a, b$ et $c$, les deux séries solutions de l'équation de Gauss, $f_1$ et $f_2$, représentent des fonctions analytiques sur $\mathbb{C} \setminus \{0,1\}$. On a donc trouvé un espace de solutions analytiques de dimension 2, et par le théorème de Cauchy-Kovalevskaya, toutes les solutions analytiques du système (31.1) en dehors de sa variété S pour $a, b$ et $c$ génériques.

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

Nous poursuivons maintenant avec le cas particulier important des systèmes fonctionnels linéaires correspondant à des modules A/I de dimension finie sur $\mathbb{C}(x)$. L'objectif est ici de montrer que pour une algèbre A donnée, leurs solutions, que nous appellerons « fonctions $\partial$-finies », forment une algèbre sur $\mathbb{C}$. Nous allons donner un algorithme pour calculer les clôtures correspondantes. Voici tout de suite la définition, déjà motivée par les sections et chapitres précédents sur les fonctions différentiellement finies et les suites polynomialement récurrentes (en particulier, le Chapitre 14).

**Définition 31.2 — Fonction $\partial$-finie.** Étant donnée une algèbre de Ore (rationnelle)

$$A = \mathbb{C}(x_1, \dots, x_r)\langle \partial_1, \dots, \partial_r; \sigma_1, \dots, \sigma_r, \delta_1, \dots, \delta_r \rangle$$

agissant sur un $\mathbb{C}(x_1, \dots, x_r)$-espace vectoriel V, un élément $f$ de V est dit $\partial$-fini lorsque les conditions équivalentes suivantes sont vérifiées :

1. pour chaque $i$ entre 1 et $r$, il existe un polynôme $P_i = P_i(x_1, \dots, x_r, \partial_i)$ non nul dont l'action annule $f$;

2. la famille des $\partial^a \cdot f$, où $\partial^a$ décrit les monômes de A, engendre un espace vectoriel de dimension finie sur $\mathbb{C}(x)$;

3. le module quotient A/I où I note l'idéal annulateur de $f$ pour l'action de A est un espace vectoriel de dimension finie sur $\mathbb{C}(x)$.

**Démonstration.** Vérifions l'équivalence entre les trois points de la définition ci-dessus. Faisons d'abord l'hypothèse de la première condition, en notant $d_i$ le degré de $P_i$ en $\partial_i$. Alors, tout $\partial^a$ a un reste par division par les $P_i$ qui s'exprime comme combinaison linéaire des $\partial_1^{j_1} \cdots \partial_r^{j_r}$ pour $0 \le j_1 < d_1, \dots, 0 \le j_r < d_r$. Ainsi, la famille des $\partial^a \cdot f$ reste dans l'espace vectoriel engendré par les $\partial_1^{j_1} \cdots \partial_r^{j_r} \cdot f$ pour $0 \le j_1 < d_1, \dots, 0 \le j_r < d_r$, et la deuxième condition est prouvée. De manière réciproque, pour chaque $i$, la famille des $\partial_i^j \cdot f$ est une sous-famille de celle des $\partial^a \cdot f$ ; quand cette dernière engendre un espace vectoriel de dimension finie, la première est une famille liée, ce qui fournit un polynôme non nul $P_i$. Enfin, l'application linéaire sur A qui à P de A associe $P \cdot f$ dans l'espace vectoriel V engendré par les $\partial^a \cdot f$ est surjective, de noyau I. Les A-modules
V et A/I sont donc isomorphes, et ils le sont donc aussi en tant qu'espaces vectoriels sur $\mathbb{C}(x)$. Ceci prouve l'équivalence entre les deux dernières conditions. ■

Par commodité, nous appellerons « fonctions » les éléments de l'espace vectoriel V, ce quand bien même il ne s'agirait pas de fonctions au sens de l'analyse, mais afin d'éviter la terminologie plus lourde et moins imagée d'« éléments $\partial$-finis d'un module sur A » et celle plus répétitive de « fonctions, suites ou suites de fonctions ».

## Méthode du vecteur cyclique et généralisation à plusieurs variables

Les algorithmes envisagés pour les clôtures des fonctions $\partial$-finies s'appuient sur le calcul de vecteur cyclique, dont nous donnons d'abord la définition et en décrivons le calcul dans le cadre classique univarié commutatif. Étant donné un espace vectoriel V sur un corps $k$, sur lequel on suppose donnée une action de $k[X]$, un vecteur $v \in V$ est dit cyclique si la famille $\{X^i \cdot v\}$ engendre V comme $k$-espace vectoriel. Alors, $v$ engendre V comme $k[X]$-module. Pour calculer, on suppose que V est de dimension finie $d$ et que l'action de X est donnée sur une base $B = (b_1, \dots, b_d)$ de V par une matrice M telle que $X \cdot w = (a_1, \dots, a_d)M^t B$ pour tout vecteur $w = a_1 b_1 + \dots + a_d b_d = (a_1, \dots, a_d)^t B$. Pour tester si $v$ est cyclique et le cas échéant rendre explicite la structure de module de V, on range dans une matrice les lignes $(a_1, \dots, a_d)M^i$ pour $0 \le i \le m$ avec $m$ à déterminer et on cherche, par exemple par l'algorithme de Gauss, une dépendance linéaire entre les lignes de la matrice obtenue. En procédant successivement avec $m = 0, 1, 2, \dots$, la première dépendance linéaire fournit le polynôme minimal de $v$ sous l'action de X sur V; son degré $m$ vérifie $m \le d$.

Ce calcul s'étend au cadre commutatif de l'action d'une algèbre

$$k[X] = k[X_1, \dots, X_r]$$

de polynômes en plusieurs indéterminées. Chaque $X_i$ correspond alors à une matrice $M_i$ et la commutativité des $X_i$ dans $k[X]$ induit la commutativité entre les matrices $M_i$. Au lieu d'itérer sur les monômes $X^i$ par ordre croissant de $i$, on itère maintenant sur les monômes $X^\lambda = X_1^{\lambda_1} \cdots X_r^{\lambda_r}$ selon tout ordre qui assure qu'un monôme n'est considéré qu'après tous ses diviseurs. Soit $\lambda(0), \lambda(1), \dots$ l'ordre dans lequel les multi-exposants des monômes sont énumérés. À chaque étape, on recherche une dépendance linéaire entre des vecteurs

$$X^{\lambda(0)} \cdot v, \dots, X^{\lambda(m)} \cdot v,$$

obtenue en recherchant une dépendance linéaire entre les vecteurs de coefficients

$$(a_1, \dots, a_d)M^{\lambda(0)}, \dots, (a_1, \dots, a_d)M^{\lambda(m)}, \qquad (31.2)$$

où maintenant $M^{\lambda(j)}$ est le produit $M_1^{\lambda(j)_1} \cdots M_d^{\lambda(j)_d}$. En cas d'échec, on conserve ces $m+1$ vecteurs et on reprend la recherche après avoir ajouté le nouveau vecteur $X^{\lambda(m+1)} \cdot v$; en cas de succès, on retire le dernier vecteur introduit, $X^{\lambda(m)} \cdot v$, on évite par la suite tous les multiples du monôme $X^{\lambda(m)}$, et on introduit le nouveau vecteur $X^{\lambda(m+1)} \cdot v$ pour reprendre la recherche sur la famille

$$X^{\lambda(0)} \cdot v, \dots, X^{\lambda(m-1)} \cdot v, X^{\lambda(m+1)} \cdot v.$$
Ce calcul termine si et seulement si le quotient $k[X]/I$, vu comme $k$-espace vectoriel, est de dimension finie. Chaque dépendance linéaire calculée fournit un polynôme P tel que $P(X_1, \dots, X_r) \cdot v = 0$. Lorque l'itération sur les monômes $X^\lambda$ suit l'ordre croissant selon un ordre monomial (admissible), l'ensemble des polynômes annulateurs obtenus constitue une base de Gröbner de I pour l'ordre choisi, car l'itération maintient une famille de $X^\lambda$ qui sont tous strictement sous l'escalier, sauf au plus un élément qui est alors sur l'escalier. Par construction, les P obtenus ont cet élément sur un coin (rentrant vers l'origine) de l'escalier.

**Exemple 31.4** Soient V le $\mathbb{Q}$-espace vectoriel de dimension 4 et de base $(b_1, \dots, b_4)$, et $v = (0, 1, 1, 0)$ un élément particulier de V. Introduisons l'action de $\mathbb{Q}[X, Y]$ sur V donnée par $X \cdot w = aM_X$ et $Y \cdot w = aM_Y$ pour

$$ M_X = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 2 & 0 & 2 & 2 \\ -1/2 & 1/2 & 0 & -3/2 \\ 8 & -5 & -2 & 0 \end{pmatrix}, \quad M_Y = \begin{pmatrix} 0 & 0 & 1 & 0 \\ -1/2 & 1/2 & 0 & -3/2 \\ 0 & 0 & 0 & 1 \\ -11/2 & 7/2 & 1 & -1/2 \end{pmatrix} $$

quand $w = a_1b_1 + \dots + a_4b_4$. Un calcul direct donne $M_X M_Y = M_Y M_X$.

Choisissons d'abord l'ordre lexicographique pour lequel $Y < X$, si bien que les monômes à considérer sont d'abord $1, Y, Y^2$, etc, puis $X, XY, XY^2$, etc. Les familles successives (1), (1, Y), (1, Y, $Y^2$) et (1, Y, $Y^2$, $Y^3$) donnent toutes des familles (31.2) linéairement indépendantes. La famille (1, Y, $Y^2$, $Y^3$, $Y^4$) donne ensuite la relation

$$ (-1 + 6Y + 4Y^2 + Y^4) \cdot v = 0. $$

On remplace donc $Y^4$ par $X$ pour considérer la famille $(1, Y, Y^2, Y^3, X)$ qui donne la nouvelle relation

$$ (-11 + 2Y - Y^2 - 2Y^3 + 7X) \cdot v = 0. $$

Choisissons ensuite l'ordre gradué pour lequel $Y < X$, si bien que les monômes à considérer sont d'abord $1, Y, X, Y^2, XY, X^2, Y^3$, etc. Chaque famille préfixe de $(1, Y, X, Y^2)$ ne donne aucune relation de dépendance. La famille $(1, Y, X, Y^2, XY)$ donne ensuite la relation

$$ (1 - X + 3Y^2 + 2XY) \cdot v = 0, $$

puis la famille $(1, Y, X, Y^2, X^2)$ la relation

$$ (-2 - 2Y - 2Y^2 + X^2) \cdot v = 0, $$

et enfin la famille $(1, Y, X, Y^2, Y^3)$ la relation

$$ (11 - 2Y - 7X + Y^2 + 2Y^3) \cdot v = 0. $$
## Algorithmes de clôture des fonctions $\partial$-finies

Le procédé du vecteur cyclique s'étend au cas de l'action d'une algèbre de Ore (rationnelle) en présence de fonctions $\partial$-finies. Soit une algèbre de Ore

$$A = \mathbb{C}(x)\langle \partial_1, \dots, \partial_r; \sigma_1, \dots, \sigma_r, \delta_1, \dots, \delta_r \rangle,$$

pour laquelle nous faisons l'hypothèse que les $\sigma_\ell$ sont surjectifs. L'espace vectoriel utilisé est un module du type A/I, vu comme espace vectoriel sur $\mathbb{C}(x)$, ou même un module obtenu à partir de quelques constructions de base sur des modules de la forme A/I, comme on va le voir sur l'exemple plus bas. L'espace V étant d'une certaine dimension finie $d$ et une base $B = (b_1, \dots, b_d)$ de V étant fixée, l'action de chaque $\partial_i$ sur un vecteur $v = a_1 b_1 + \dots + a_d b_d = a^t B$ de coordonnées $a = (a_1, \dots, a_d)$ est donnée par une matrice $M_i$ indépendante de $v$ sous la forme

$$\partial_i \cdot v = \partial_i \cdot (a^t B) = (\sigma_i(a)M_i + \delta_i(a))^t B, \quad (31.3)$$

en adoptant une notation selon laquelle les $\sigma_i$ et $\delta_i$ agissent distributivement sur les coefficients de vecteurs ou de matrices. Pour le choix particulier $v = b_\ell$, c'est-à-dire $a_i = 1$ quand $i = \ell$ et $a_i = 0$ sinon, on observe que la $\ell$-ième ligne de $M_i$ n'est autre que le vecteur ligne des composantes de $\partial_i \cdot b_\ell$ sur la base $B$, de sorte que $\partial_i \cdot B = M_i B$ (avec encore une notation où $\partial_i$ agit distributivement sur les coefficients du vecteur).

En faisant maintenant agir $\partial_j$ sur (31.3) et en posant $a' = \sigma_i(a)M_i + \delta_i(a)$, on a

$$\begin{align*}
\partial_j \partial_i \cdot v &= \partial_j \cdot (a'^t B) = (\sigma_j(a')M_j + \delta_j(a'))^t B \\
&= (\sigma_j \sigma_i(a) \sigma_j(M_i) + \sigma_j \delta_i(a)) M_j + (\sigma_j \sigma_i(a) \delta_j(M_i) + \delta_j \sigma_i(a) M_j + \delta_j \delta_i(a))^t B \\
&= (\sigma_j \sigma_i(a) [\sigma_j(M_i) M_j + \delta_j(M_i)] + [\sigma_j \delta_i(a) M_j + \delta_j \sigma_i(a) M_i + \delta_j \delta_i(a)])^t B.
\end{align*}$$

Les commutations entre endomorphismes et $\sigma$-dérivations données par la définition des algèbres de Ore font que le dernier terme entre crochets est symétrique en $i$ et $j$; en tenant de plus compte, pour $i \neq j$, de la commutation $\partial_i \partial_j = \partial_j \partial_i$, on déduit la relation suivante, qui remplace la commutation entre les matrices $M_\ell$ du cas commutatif :

$$\sigma_j(M_i)M_j + \delta_j(M_i) = \sigma_i(M_j)M_i + \delta_i(M_j),$$

où la simplification par $\sigma_i \sigma_j(a)$ se justifie par l'hypothèse de surjectivité des $\sigma_\ell$. Lorsque de telles relations sont assurées, la même méthode de recherche de dépendances linéaires par la méthode de Gauss que dans le cas commutatif s'applique et fournit un calcul de l'addition et du produit de fonctions $\partial$-finies, ou même directement d'une expression polynomiale en des fonctions $\partial$-finies, en faisant le bon choix de V. Dans la pratique, les matrices $M_i$ sont le plus souvent obtenues à partir de bases de Gröbner : les $b_\ell$ correspondent à des points sous un escalier. Plutôt que de faire une présentation formelle de ces algorithmes, nous en donnons l'idée sur un exemple.
**Exemple 31.5** Considérons le calcul du produit des deux fonctions $f$ et $g$ en deux variables $x$ et $y$, données par $f(x,y) = \exp(xy)$ et $g(x,y) = J_\mu(x+y)$, où, pour un paramètre $\mu$ complexe, $J_\mu$ est la fonction de Bessel de première espèce, solution de l'équation différentielle

$$z^2 J_{\mu}''(z) + z J_{\mu}'(z) + (z^2 - \mu^2) J_{\mu}(z) = 0$$

qui admet à l'origine le développement asymptotique

$$J_{\mu}(z) \sim \frac{1}{2^{\mu}} \sum_{n=0}^{\infty} \frac{(-1)^n (z/2)^{2n}}{n! \Gamma(n + \mu + 1)}$$

Considérons l'algèbre de Ore $A = \mathbb{C}(\mu, x, y)\langle\partial_x, \partial_y; \text{id}, \text{id}, D_x, D_y\rangle$, où $\mu$ est maintenant un paramètre formel. Des bases de Gröbner des annulateurs I et J dans $A$ de $f$ et $g$ pour l'ordre $\text{lex}(\partial_y, \partial_x)$ sont respectivement

$$\{\partial_x - y, \partial_y - x\} \quad \text{et} \quad \{(x+y)^2 \partial_x^2 + (x+y)\partial_x + (x+y)^2 - \mu^2, \partial_y - \partial_x\}.$$

On désigne encore maintenant par $f$ et $g$ les vecteurs cycliques générateurs des modules A/I et A/J, avec un petit abus de notation. Pour pouvoir parler d'un produit entre ces objets a priori seulement algébriques, on introduit l'espace vectoriel sur $\mathbb{C}(\mu)$ de base $B = (f \otimes g, f \otimes (\partial_x \cdot g))$, où l'on voit le produit $h = f \otimes g$ comme donné par ses coordonnées (1,0). (On peut voir ce produit tensoriel comme un produit bilinéaire sans commutativité : en général, $u \otimes v \neq v \otimes u$, mais, pour tout $\lambda \in \mathbb{C}(\mu)$, $(\lambda u) \otimes v = u \otimes (\lambda v) = \lambda(u \otimes v)$, que l'on note donc par simplicité $\lambda u \otimes v$.) Sur cet espace de base $B$, qui n'est autre que $A/I \otimes A/J$, la dérivée d'un produit tensoriel est donnée par

$$\partial_x \cdot (u \otimes v) = (\partial_x \cdot u) \otimes v + u \otimes (\partial_x \cdot v),$$

ce que l'on peut résumer en disant que $\partial_x$ agit par $\partial_x \otimes \text{id} + \text{id} \otimes \partial_x$, pour des domaines de définitions adéquats. Cette action fait du produit tensoriel $A/I \otimes A/J$ un nouveau module sur $A$. Puisque

$$\partial_x \cdot (f \otimes g) = (\partial_x \cdot f) \otimes g + f \otimes (\partial_x \cdot g) = yf \otimes g + f \otimes (\partial_x \cdot g)$$

et

$$\begin{aligned} \partial_x \cdot (f \otimes (\partial_x \cdot g)) &= yf \otimes (\partial_x \cdot g) + f \otimes (\partial_x^2 \cdot g) \\ &= yf \otimes (\partial_x \cdot g) + \left( \frac{1}{(x+y)^2} \mu^2 - 1 \right) f \otimes g - \frac{1}{x+y} f \otimes (\partial_x \cdot g), \end{aligned}$$
et des relations similaires pour l'action de $\partial_y$, on trouve les matrices

$$M_x = \begin{pmatrix} y & 1 \\ \frac{\mu^2}{(x+y)^2} - 1 & y - \frac{1}{x+y} \end{pmatrix}$$

et

$$M_y = \begin{pmatrix} x & 1 \\ \frac{\mu^2}{(x+y)^2} - 1 & x - \frac{1}{x+y} \end{pmatrix}$$

Choisissons d'itérer selon un ordre raffinant le degré total en $\partial_x$ et $\partial_y$, pour lequel $1 < \partial_y < \partial_x < \partial_y^2 < \partial_x \partial_y < \partial_x^2$, etc. On fait d'abord agir $\partial_y$ pour trouver

$$\partial_y \cdot h = \left( (1,0)M_y + \frac{d}{dy}(1,0) \right)^{tB} = (x,1)^{tB},$$

qui avec $(1,0)^{tB}$ ne constitue pas une famille liée. Ensuite, on trouve par le même procédé $\partial_x \cdot h = (y,1)^{tB}$, ce qui fournit la liaison $p_1 \cdot h = 0$ pour $p_1 = \partial_x - \partial_y + (x-y)$. Pour la suite du calcul, on exclut alors tous les monômes divisibles par $\partial_x$; le monôme considéré suivant est $\partial_y^2$. Son action sur $h$ donne

$$\partial_y^2 \cdot h = \left( (x,1)M_y + \frac{d}{dy}(x,1) \right)^{tB} = \left( \frac{\mu^2}{(x+y)^2} + x^2 - 1, 2x - \frac{1}{x+y} \right)^{tB},$$

et l'on obtient un second annulateur de $h$,

$$p_2 = (x+y)^2 \partial_y^2 - (x+y)(2x^2 + 2xy - 1)\partial_y + (x+y)(x^3 + x^2y + y) - \mu^2.$$

Pour la suite du calcul, on exclut donc tous les monômes divisibles par $\partial_y^2$, si bien qu'il ne reste plus aucun monôme à considérer. L'idéal annulateur de $h$ est l'idéal $Ap_1+Ap_2$, dont $\{p_1, p_2\}$ est une base de Gröbner pour l'ordre $\text{deg}(\partial_y, \partial_x)$, de monômes de tête respectifs $\partial_x$ et $\partial_y^2$; le module A/I est donné comme $\mathbb{C}(x,y)$-espace vectoriel par sa base $(1+I, \partial_x+I)$.

Le calcul qui précède peut se revisiter en abandonnant l'écriture matricielle et en faisant apparaître plus explicitement les calculs de restes modulo une base de Gröbner.

**Exemple 31.6** On récrit d'abord $\partial_y \cdot h$ sous la forme

$$\partial_y \cdot h = (\partial_y \cdot f) \otimes g + f \otimes (\partial_y \cdot g) = xf \otimes g + f \otimes (\partial_x \cdot g),$$

après réductions par les bases de Gröbner pour I et J; ce vecteur et $h$ constituent une famille linéairement indépendante. On procède ensuite de même pour $\partial_x \cdot h$,
de façon à obtenir

$$ \partial_x \cdot h = (\partial_x \cdot f) \otimes g + f \otimes (\partial_x \cdot g) = yf \otimes g + f \otimes (\partial_x \cdot g); $$

on retrouve ainsi l'annulateur $p_1$. Le monôme considéré suivant est $\partial_y^2$, d'action sur $h$

$$ \partial_y^2 \cdot h = x^2 f \otimes g + 2xf \otimes (\partial_x \cdot g) - (x+y)^{-2} f \otimes ((x+y)\partial_x + (x+y)^2 - \mu^2)g; $$

ce vecteur, $h$ et $\partial_y \cdot h$ forment une famille linéairement liée, et l'on retrouve le second annulateur $p_2$. Le calcul se termine de la même manière.

Pour l'algorithme d'addition, les mêmes idées algorithmiques fonctionnent en calculant dans la somme directe $A/I \oplus A/J$ au lieu de $A/I \otimes A/J$.

## Notes

Le calcul de recherche de vecteur cyclique multivarié en Section 31.5 peut être vu comme une réminiscence de l'algorithme FGLM [Fau+93] pour le changement d'ordre dans les bases de Gröbner du cadre commutatif.

Les clôtures dans le cas à plusieurs variables ont été largement exploitées dans le traitement d'identités en fonctions spéciales, à la suite des travaux de Zeilberger [Zei90]. L'algorithmisation de ces méthodes s'est ensuite peu à peu fait jour, d'abord dans le cas différentiel [Tak92], puis dans le cas de polynômes tordus généraux [CS98], où la définition des fonctions $\partial$-finies a été posée. La présentation matricielle de la Section 31.5 nous a paru plus synthétique que la présentation classique à base de récriture par bases de Gröbner [CS98]. Les deux présentations trouvent leur inspiration dans l'algorithme FGLM [Fau+93].

Un autre cadre de bases de Gröbner est disponible pour des algèbres de Ore polynomiales, de la forme

$$ k[x_1, \dots, x_r](\partial_1, \dots, \partial_r; \sigma_1, \dots, \sigma_r, \delta_1, \dots, \delta_r) $$

et non

$$ k(x_1, \dots, x_r)(\partial_1, \dots, \partial_r; \sigma_1, \dots, \sigma_r, \delta_1, \dots, \delta_r). $$

Les ordres monomiaux garantissant la terminaison d'un algorithme de Buchberger sont alors sujet à plus de contraintes. Tout ceci est raconté de façon relativement accessible dans le livre de Saito, Sturmfels et Takayama [SST00], d'où est aussi tirée une partie de la Section 31.4. Le système différentiel de la Section 31.4 est un exemple d'une théorie développée par Gel'fand, Kapranov et Zelevinsky, connue sous le nom de système hypergéométrique GKZ.

## Bibliographie

* 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.
Fau+93 FAUGÈRE, J. C., P. GIANNI, D. LAZARD et T. MORA (1993). « Efficient computation of zero-dimensional Gröbner bases by change of ordering ». In : *Journal of Symbolic Computation*, vol. 16, n°4, p. 329-344.

SST00 SAITO, Mutsumi, Bernd STURMFELS et Nobuki TAKAYAMA (2000). *Gröbner deformations of hypergeometric differential equations*. Springer-Verlag.

Tak92 TAKAYAMA, Nobuki (1992). « An approach to the zero recognition problem by Buchberger algorithm ». In : *Journal of Symbolic Computation*, vol. 14, n°2-3, p. 265-282.

Zei90 ZEILBERGER, Doron (1990). « A holonomic systems approach to special functions identities ». In : *Journal of Computational and Applied Mathematics*, vol. 32, n°3, p. 321-368.
<figure><img src="image_82.png" /></figure>
## 32. Sommation et intégration symboliques des fonctions spéciales

### Résumé

Nous décrivons un algorithme qui peut se voir comme une extension de l'al-
gorithme de Zeilberger pour des sommants $\partial$-finis, et qui traite dans le même
formalisme sommation et intégration. Les quelques sommes et intégrales suivantes,
qui peuvent être traitées avec cet algorithme, montrent une variété d'applications
qui vont de la combinatoire à la physique mathématique en passant par la théorie
des fonctions spéciales :

$$
\begin{align*}
& \sum_{k=0}^{n} \left( \sum_{j=0}^{k} \binom{n}{j} \right)^3 = n 2^{3n-1} + 2^{3n} - 3 n 2^{n-2} \binom{2n}{n}, \\
& \sum_{n=0}^{\infty} H_n(x) H_n(y) \frac{u^n}{n!} = \frac{\exp\left(\frac{4u(xy-u(x^2+y^2))}{1-4u^2}\right)}{\sqrt{1-4u^2}}, \\
& \qquad \frac{1}{2} J_0(x)^2 + J_1(x)^2 + J_2(x)^2 + \dots = \frac{1}{2}, \\
& \qquad \int_{-1}^{+1} \frac{e^{-px} T_n(x)}{\sqrt{1-x^2}} dx = (-1)^n \pi I_n(p), \\
& \int_{0}^{+\infty} xe^{-px^2} J_n(bx) I_n(cx) dx = \frac{1}{2p} \exp\left(\frac{c^2-b^2}{4p}\right) J_n\left(\frac{bc}{2p}\right), \\
& \int_{0}^{+\infty} x J_1(ax) I_1(ax) Y_0(x) K_0(x) dx = - \frac{\ln(1-a^4)}{2\pi a^2}, \\
& \sum_{k=0}^{n} \frac{q^{k^2}}{(q;q)_k (q;q)_{n-k}} = \sum_{k=-n}^{n} \frac{(-1)^k q^{(5k^2-k)/2}}{(q;q)_{n-k} (q;q)_{n+k}}.
\end{align*}
$$

Ici, J, Y, I et K sont des variantes de fonctions de Bessel, lesquelles apparaissent
fréquemment pour décrire des modèles physiques à symétrie cylindrique ou
sphérique; H et T sont des familles de polynômes orthogonaux de Hermite et Tchebychev; $(q;q)_n$ représente le produit $(1-q)\cdots(1-q^n)$. La première identité intervient dans une discrétisation d'une question de probabilités sur la position du maximum de trois variables aléatoires gaussiennes; la dernière est une variante finie d'une des identités de Rogers-Ramanujan, en théorie des partitions.

## 32.1 Expression du télescopage créatif en termes d'algèbres de Ore rationnelles

La méthode du télescopage créatif a été exposée au Chapitre 29, Section 29.2, et appliquée à la sommation hypergéométrique définie, par une combinaison de l'algorithme de Gosper et d'une idée due à Zeilberger. Cette approche se généralise en des algorithmes de sommation et intégration pour les suites et fonctions $\partial$-finies.

Pour évaluer une somme paramétrée

$$F_n = \sum_{k=a}^{b} f_{n,k},$$

le principe du télescopage créatif est de déterminer une suite auxiliaire $g = (g_{n,k})$ ainsi que des coefficients $\eta_0, \dots, \eta_r$, fonctions de la variable $n$, tels que se trouve vérifiée la relation

$$\eta_r(n)f_{n+r,k} + \dots + \eta_0(n)f_{n,k} = g_{n,k+1} - g_{n,k}.$$

Ici, nous ne faisons pas plus d'hypothèses sur les $\eta_i$ et $g$ que celle de pouvoir évaluer la relation ci-dessus pour tout $n$ quand $k$ décrit les entiers de $a$ à $b$. Dans ce cas, une sommation sur $k$ fournit l'égalité

$$\eta_r(n)F_{n+r} + \dots + \eta_0(n)F_n = g_{n,b+1} - g_{n,a}.$$

Si le membre de droite n'est pas déjà nul, on recherche un opérateur annulateur de ce second membre; par composition, on obtient une récurrence homogène sur F. Dans certains cas, on sait prédire à partir de conditions analytiques sur $f$ la nullité du terme $g_{n,b+1} - g_{n,a}$.

Des algorithmes d'efficacités différentes ont été donnés selon le domaine de recherche des $\eta_i$ et de $g$, et selon le compromis choisi entre efficacité et richesse de la classe de suites $f$ en entrée. En particulier, l'Algorithme 29.2 de Zeilberger, page 537, optimisé pour une suite $f$ hypergéométrique, revient à rechercher des $\eta_i$ polynomiaux et une suite $g$ similaire à $f$, c'est-à-dire un multiple $\phi f$ pour une fraction rationnelle $\phi$ en $n$ et $k$. La suite $g = \phi f$ devant être une somme indéfinie, la recherche de $\phi$ et des $\eta_i$ se fait par une variante paramétrée de l'algorithme de Gosper (Section 29.1). Notons que le domaine de recherche de $g$ est l'espace vectoriel $\mathbb{C}(n,k)f$, qui n'est autre, dans le cas hypergéométrique, que le module engendré par $f$ sur l'algèbre de Ore $A = \mathbb{C}(n,k)(\partial_n, \partial_k; S_n, S_k)$.

Nous considérons ici la généralisation au cas où $f$ est une fonction $\partial$-finie et où le module $A \cdot f$ est un espace vectoriel de dimension finie sur $\mathbb{C}(n,k)$, mais pas forcément de dimension 1. Soit $v_1, \dots, v_d$ les éléments d'une base vectorielle de $A \cdot f$;
l'algorithme de Zeilberger étendu qui va être expliqué en Section 32.2 et donné comme Algorithme 32.2 recherche $g$ sous la forme indéterminée $\phi_1 v_1 + \cdots + \phi_d v_d$, pour des fractions rationnelles $\phi_i$ en $n$ et $k$. Cette recherche se fait par une extension $\partial$-finie de la variante paramétrée de l'algorithme de Gosper, l'Algorithme 32.1.

Tout ce qui a été dit se transpose au monde différentiel pour l'évaluation d'une intégrale paramétrée

$$F(x) = \int_{a}^{b} f(x, y) dy.$$

On cherche alors une relation

$$\eta_r(x) \frac{\partial^r f}{\partial x^r}(x, y) + \cdots + \eta_0(n) f(x, y) = \frac{\partial g}{\partial y}(x, y),$$

qui après intégration fournit l'égalité

$$\eta_r(n)F^{(r)}(x) + \cdots + \eta_0(n)F(x) = \int_a^b g(x, y) dy.$$

Un cas particulier important (par exemple pour la combinatoire) est celui dans lequel les « fonctions » $f$ et $F$ sont en réalité des séries formelles, car alors les questions de bonne définition des objets se simplifient. La même méthode permet aussi de traiter des sommations paramétrées continûment,

$$F(x) = \sum_{k=a}^{b} f_k(x),$$

et des suites d'intégrales de la forme

$$F_n = \int_a^b f_n(y) dy.$$

**Exercice 32.1** Formuler la relation entre $f$ et $g$ à rechercher dans ces deux derniers cas. ■

## 32.2 L'algorithme de sommation $\partial$-finie définie sur l'exemple $\frac{1}{2}J_0(x)^2 + J_1(x)^2 + J_2(x)^2 + \cdots = \frac{1}{2}$

Nous allons montrer que la famille paramétrée des fonctions de Bessel de première espèce, $J_v$, où chaque $J_v$ est une solution que nous allons préciser de l'équation de Bessel

$$x^2 y''(x) + xy'(x) + (x^2 - v^2)y(x) = 0, \quad (32.1)$$

a une somme $\frac{1}{2}J_0(x)^2 + J_1(x)^2 + J_2(x)^2 + \cdots$ qui s'évalue à $\frac{1}{2}$.

L'équation de Bessel et les fonctions de Bessel peuvent être considérées pour des valeurs complexes du paramètre $v$, mais vu la nature de la somme à étudier, nous nous limiterons dorénavant à des valeurs entières $v \in \mathbb{N}$. La traduction de l'équation
de Bessel selon la méthode de la Section 17.1, puis l'étude de son polynôme indiciel à l'origine (Définition 17.1), montrent qu'il existe pour chaque $v$ des solutions dans les séries formelles $\mathbb{C}[[x]]$ et que ces solutions constituent un espace vectoriel de dimension 1 sur $\mathbb{C}$ de séries. Une base de ces solutions formelles est donnée par la série de Bessel

$$J_v(x) = \left(\frac{x}{2}\right)^v \sum_{n=0}^{\infty} \frac{(-1)^n}{n!(n+v)!} \left(\frac{x}{2}\right)^{2n},$$

de valuation $v$. Vu la décroissance des coefficients, cette série s'interprète aussi pour chaque entier $v$ comme une série de fonctions convergente.

**Exercice 32.2** Vérifier ces résultats.

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

On vérifie par simple substitution et évaluation que ces fonctions $J_v$ satisfont en plus de (32.1) aux relations

$$x J'_{v}(x) + x J_{v+1}(x) - v J_{v}(x) = 0 \quad \text{et} \quad x J_{v+2}(x) - 2(v+1)J_{v+1}(x) + x J_{v}(x) = 0.$$

En introduisant l'algèbre de Ore $A = \mathbb{C}(v,x)\langle\partial_v, \partial_x; S_v, \text{id}, 0, D_x\rangle$ où $S_v$ est le décalage avant sur $v$ et $D_x$ est la dérivation par rapport à $x$, on a donc un système d'annulateurs pour $J$,

$$p_1 = x^2 \partial_x^2 + x \partial_x + x^2 - v^2,$$

$$p_2 = x \partial_x + x \partial_v - v,$$

$$p_3 = x \partial_v^2 - 2(v+1)\partial_v + x.$$

Les deux premiers forment une base de Gröbner de l'idéal engendré par $(p_1, p_2, p_3)$ pour l'ordre $\text{lex}(\partial_v, \partial_x)$; les deux derniers pour l'ordre $\text{lex}(\partial_x, \partial_v)$.

**Exercice 32.3** Pour chacun des idéaux $A p_1 + A p_2$ et $A p_2 + A p_3$, calculer la base de Gröbner minimale réduite pour chacun des deux ordres $\text{lex}(\partial_v, \partial_x)$ et $\text{lex}(\partial_x, \partial_v)$. ■

Ainsi, $J$ est une fonction $\partial$-finie. Le module $A \cdot J$ est donné, par exemple, comme l'espace vectoriel sur $\mathbb{C}(v,x)$ de base $(J, \partial_v \cdot J)$. Pour représenter le carré de $J$ en vue d'une sommation, on peut observer que, en tant qu'espace vectoriel, le module $A \cdot J^2$ admet la base $(J^2, J \times (\partial_v \cdot J), (\partial_v \cdot J)^2)$ et utiliser l'algorithme de clôture par produit pour obtenir une base de Gröbner. En fait, le calcul qui suit n'a même pas besoin d'une représentation aussi explicite de $f = J^2$: pour calculer la somme $\frac{1}{2}J_0(x)^2 + J_1(x)^2 + J_2(x)^2 + \cdots$ comme fonction de $x$, on recherche (quand on en vient à un ordre cible $r$ égal à 1) une fonction $\eta$ de $x$, indépendante de $v$, telle que $f' + \eta f$ soit la différence finie en $v$ d'un élément $g$ de $A \cdot J^2$. Pour la suite du calcul, nous fixons cet élément sous la forme indéterminée donnée par

$$g(v) = \phi_0(v)J_v^2 + \phi_1(v)J_{v+1}^2 + \phi_2(v)J_v J_{v+1},$$

où nous avons omis de faire référence à la variable $x$ dans les évaluations de $g$, des $\phi_i$ et de $J$, car cette variable ne va intervenir que comme paramètre dans le calcul des fractions rationnelles $\phi_i$. (On peut penser qu'on travaille temporairement dans l'algèbre de Ore $A' = \mathbb{C}(v,x)\langle\partial_v; S_v\rangle$.)
En supposant le problème résolu, on a alors par construction la relation $f' + \eta f = (\partial_v - 1) \cdot g$, puis, après réduction de chaque occurence des dérivées et décalées de J par la base de Gröbner $\{p_2, p_3\}$,

$$ 
\begin{aligned}
2J_v J'_v + \eta J_v^2 &= (\partial_v - 1) \cdot (\phi_0(v) J_v^2 + \phi_1(v) J_{v+1}^2 + \phi_2(v) J_v J_{v+1}) \\
&= \phi_0(v+1) J_{v+1}^2 - \phi_0(v) J_v^2 + \phi_1(v+1) x^{-2} (2(v+1)J_{v+1} - x J_v)^2 - \phi_1(v) J_{v+1}^2 \\
&\quad + \phi_2(v+1) x^{-1} J_{v+1} (2(v+1)J_{v+1} - x J_v) - \phi_2(v) J_v J_{v+1},
\end{aligned}
$$

laquelle se récrit

$$ 
\begin{aligned}
(2vx^{-1} + \eta)J_v^2 - 2J_v J_{v+1} &= (\phi_1(v+1) - \phi_0(v))J_v^2 - (4(v+1)x^{-1}\phi_1(v+1) + \phi_2(v+1) + \phi_2(v))J_v J_{v+1} \\
&\quad + (\phi_0(v+1) + 4(v+1)^2x^{-2}\phi_1(v+1) - \phi_1(v) + 2(v+1)x^{-1}\phi_2(v+1))J_{v+1}^2.
\end{aligned}
$$

De l'indépendance linéaire des fonctions $J_v^2, J_{v+1}^2$ et $J_v J_{v+1}$ sur $\mathbb{C}(v, x)$, on déduit les relations nécessaires

$$ 
\begin{aligned}
& -\phi_0(v) + \phi_1(v+1) = 2vx^{-1} + \eta, \\
& 4(v+1)x^{-1}\phi_1(v+1) + \phi_2(v) + \phi_2(v+1) = 2, \\
& \phi_0(v+1) - \phi_1(v) + 4(v+1)^2x^{-2}\phi_1(v+1) + 2(v+1)x^{-1}\phi_2(v+1) = 0.
\end{aligned}
$$

En résolvant les deux premières respectivement en $\phi_0$ et en $\phi_1$, puis en substituant dans la dernière, on trouve la récurrence

$$ 
\begin{aligned}
x^2(v+1)\phi_2(v+3) - (v+1)(4v^2 + 20v + 24 - x^2)\phi_2(v+2) \\
+ (v+3)(4v^2 + 12v + 8 - x^2)\phi_2(v+1) - x^2(v+3)\phi_2(v) = -4x(\eta v^2 + 4\eta v + 3\eta + x).
\end{aligned}
$$

Nous résolvons maintenant celle-ci en ses solutions rationnelles par l'algorithme d'Abromov (Section 16.4), dans sa variante paramétrée qui résoud en $\phi_2 \in \mathbb{C}(n, v)$ et simultanément en $\eta \in \mathbb{C}$, par l'algorithme de la Section 16.4 du même chapitre. Les coefficients extrêmes de la partie homogène indiquent que toute solution rationnelle doit être polynomiale, puisque le pgcd entre $(v-3)+1$ et $v+3+h$ vaut 1 pour tout $h \in \mathbb{N}$ (voir l'Algorithme 16.6, en page 304, pour le calcul d'un multiple du dénominateur). En faisant apparaître une différence finie dans la partie homogène, on montre que l'opérateur associé accroît de 2 le degré d'un polynôme. Le membre gauche de la récurrence se récrit en effet :

$$ 
\begin{aligned}
x^2(v+1)\phi_2(v+3) - (12v^2 + 60v + 72 - 3x^2)\phi_2(v+2) \\
- (\partial_v - 1) \cdot ((v+3)(4v^2 + 12v + 8 - x^2)\phi_2(v+1)) - x^2(v+3)\phi_2(v),
\end{aligned}
$$

où l'on voit que pour un polynôme $\phi_2(n)$, l'unique terme de plus haut degré est celui porté par $\phi_2(n+2)$. Le degré de la partie inhomogène étant 2, toute solution
**Entrée** Un terme $\partial$-fini $f(x)$ par rapport à $A = \mathbb{K}(x)\langle\partial; \sigma, \delta\rangle$, un opérateur annulateur L de $f$, d'ordre $s$.

**Sortie** Un terme $\partial$-fini $g(x)$ tel que, respectivement, $g'(x) = f(x)$ dans le cas différentiel, ou $g(x+1) - g(x) = f(x)$ dans le cas à récurrence, ou encore le symbole $\not\approx$.

1. Poser $\Phi = \phi_{s-1} \partial_x^{s-1} + \cdots + \phi_0$ pour des coefficients indéterminés $\phi_i \in \mathbb{K}(x)$.

2. Calculer le reste $Z$ de la division euclidienne par $L$ de, respectivement, $\partial_x \Phi - 1$ dans le cas différentiel, ou $(\partial_x - 1)\Phi - 1$ dans le cas à récurrence.

3. Extraire le système sur les $\phi_i$ obtenu en annulant les $s$ coefficients de $Z$.

4. Découpler le système et le résoudre en les $\phi_i$ par les algorithmes du Chapitre 16.

5. Si la résolution fournit une solution, renvoyer $\Phi \cdot f$, sinon renvoyer $\not\approx$.

**Algorithme 32.1** – Algorithme de sommation/intégration $\partial$-finie indéfinie.

rationnelle ne peut être qu'une constante. On trouve $\phi_2 = 1$ et $\eta = 0$, d'où après report $\phi_1 = 0$ et $\phi_0 = -2\nu/x$. Autrement dit, on a

$$ \partial_x \cdot J_v^2 = (\partial_v - 1) \cdot (J_v J_{v+1} - 2\nu x^{-1} J_v^2), $$

qui par sommation fournit

$$ \partial_x \cdot \sum_{v=0}^{N} J_v^2 = J_{N+1} (J_{N+2} - 2(N+1)x^{-1}J_{N+1}) - J_0 J_1. $$

Comme la série $J_N \in \mathbb{C}[[x]]$ a valuation N, le membre droit tend vers $-J_0J_1 = \frac{1}{2}\partial_x \cdot J_0^2$ quand N tend vers $\infty$ pour la topologie usuelle donnée par la métrique $|s| = 2^{-\nu}$ pour toute série non nulle $s$ de valuation $v$. On a donc

$$ \partial_x \cdot \left( \frac{1}{2} J_0(x)^2 + J_1(x)^2 + J_2(x)^2 + \cdots \right) = 0 $$

qui caractérise la somme par une condition initiale. Une simple évaluation en 0 montre que la somme vaut $\frac{1}{2}$, ce qui achève la preuve de l'identité annoncée.

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

L'Algorithme 29.1 de Gosper, page 532, pour la sommation hypergéométrique indéfinie, se généralise assez directement en un algorithme pour la sommation et l'intégration $\partial$-fini indéfinie, la différence essentielle étant que les objets du calcul ne sont plus paramétrés par une unique fraction rationnelle, mais maintenant par une collection de fractions rationnelles indicées par un escalier de base de Gröbner. L'Algorithme 32.1 en résulte.
**Entrée** Un terme $\partial$-fini $u(x, y)$ par rapport à

$A = \mathbb{K}(x, y)\langle\partial_x, \partial_y; \sigma_x, \sigma_y, \delta_x, \delta_y\rangle$, une base de Gröbner G de l'idéal annulateur de $u$ (pour un certain ordre monomial), un entier $m \in \mathbb{N}$.

**Sortie** Une famille $(\eta_i(x))_{0 \le i \le r}$ de fractions rationnelles de $\mathbb{K}(x)$, ainsi qu'une famille $\phi_{(\alpha, \beta)}(x, y)$ de fractions rationnelles de $\mathbb{K}(x, y)$, indexée par les monômes sous l'escalier de G, telles que

$$ \eta_r(x)\partial_x^r u(x, y) + \dots + \eta_0(x)u(x, y) = \Delta_y \sum_{\alpha, \beta} \phi_{\alpha, \beta}(x, y)\partial_x^\alpha \partial_y^\beta u(x, y), $$

(où $\Delta_y$ vaut $\partial_y$ dans le cas de l'intégration par rapport à $y$ et $\partial_y - 1$ dans le cas de la sommation sur $y$), ou alors, le symbole $\not\equiv$ pour indiquer qu'il n'existe pas de telle famille.

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

a. calculer le reste $H_i$ de la division de $\partial_x^i$ par $G$;

b. poser $\Phi = \sum_{\alpha, \beta} \phi_{\alpha, \beta}(y)\partial_x^\alpha \partial_y^\beta$ où $(\alpha, \beta)$ décrit les monômes sous l'escalier de $G$, pour des coefficients indéterminés $\phi_{\alpha, \beta} \in \mathbb{K}(x, y)$;

c. calculer le reste $Z$ de la division par $G$ de

$$ \Delta_y \Phi - \sum_{i=0}^{r} \eta_i(x) H_i(x, y, \partial_x, \partial_y); $$

d. extraire le système obtenu en annulant les coefficients de $\partial_x^\alpha \partial_y^\beta$ quand $(\alpha, \beta)$ décrit les monômes sous l'escalier de $G$;

e. découpler le système et le résoudre en les $\phi_{\alpha, \beta}$ et les $\eta_i$ par les versions paramétrées des algorithmes du Chpitre 16;

f. si la résolution fournit une solution, renvoyer la famille $(\eta_i(x))$ et la famille $(\phi_{\alpha, \beta}(x, y))$.

2. Renvoyer $\not\equiv$.

**Algorithme 32.2** – Algorithme de sommation/intégration $\partial$-finie définie.

À la différence du cas hypergéométrique, l'algorithme de Gosper étendu ne va pas être utilisé aussi directement dans l'algorithme de Chyzak pour la sommation et l'intégration $\partial$-finies définies, lequel est donné pour le cadre général par l'Algorithmme 32.2. Mais l'algorithme de Gosper étendu (Algorithme 32.1) peut être vu comme une version simplifiée des étapes (1.b)–(1.f) de l'Algorithmme 32.2 de Chyzak lorsque le dessous d'escalier est en fait donné par des monômes successifs en une
seule dérivation. Le découplage à l'étape (1.e) peut être effectué par calcul de base de Gröbner de modules, comme indiqué ci-dessous à la Section 32.4. Comme dans le cas de l'algorithme de Zeilberger, il est intéressant de discuter la question de la terminaison d'une variante de l'Algorithmme 32.2 à laquelle on ne fournirait pas de borne $m$ sur $r$: dans le cas différentiel, une solution $(\phi, \eta)$ existe toujours pour un certain $r$, l'algorithme avec une boucle ouverte termine toujours dans ce cas; pour les récurrences, une hypothèse supplémentaire est nécessaire pour garantir l'existence d'une solution, et l'algorithme présenté peut donc échouer en renvoyant $\nabla$, soit parce qu'il n'y a pas de solution, soit parce que la borne $m$ a été choisie trop petite.

## 32.4 Bases de Gröbner de modules et découplage de systèmes

Dans l'exemple qui précède, on a pour le moment effectué le découplage « à la main », mais un procédé systématique et automatique est disponible, par le biais des bases de Gröbner de modules, lesquelles généralisent la notion de base de Gröbner pour les idéaux. Cette notion existe tant dans le domaine des polynômes commutatifs que dans le cadre non commutatif des algèbres de Ore ; nous la présentons directement dans ce second cas.

Dans le cas d'un idéal I d'une algèbre de Ore A, les éléments de I s'interprètent comme autant d'équivalences vérifiées par une fonction inconnue $\phi$. Dans une perspective algorithmique, chaque idéal est donné par un nombre fini de générateurs. Une question naturelle est celle de systèmes linéaires sur un vecteur de fonctions inconnues $(\phi_1, \dots, \phi_d)$, à coefficients dans A. On considère des systèmes d'un nombre fini d'équations de la forme $g_i = g_{i,1} \cdot \phi_1 + \dots + g_{i,d} \cdot \phi_d$ pour des polynômes tordus $g_{i,j}$ de A. Un tel système se représente de façon compacte par une matrice $(g_{i,j})$ à entrées dans A. Les questions qui sont alors naturelles sont celles de l'algèbre linéaire pour ces matrices, dont en particulier celle de donner un algorithme du pivot de Gauss pour des coefficients dans A, c'est-à-dire non plus dans un corps, mais dans un anneau, et non commutatif de surcroît.

Pour ce faire, au lieu de considérer simplement un ordre monomial sur les monômes $\partial^a$ d'une algèbre de Ore $A = k(x)(\partial; \sigma, \delta)$, pour lequel tout idéal à gauche admet une base de Gröbner (voir le Théorème 31.1), on s'intéresse plus généralement à un module libre de rang fini sur A (voir la définition en Section 30.1), donné par une base sous la forme $A^d = Ae_1 + \dots + Ae_d$ et muni d'un ordre sur les $\partial^a e_i$, dans lequel on va étendre la notion de base de Gröbner pour des sous-modules à gauche de $A^d$. La notion d'ordre monomial conserve formellement la même définition, si ce n'est que les $e_i$ ne peuvent apparaître que linéairement dans les monômes $\partial^a e_i$ et qu'ils ne peuvent servir pour des multiplications à gauche. La notion de S-polynôme s'étend aussi mot pour mot, à ceci près que deux polynômes de monômes de tête $\partial^a e_i$ et $\partial^b e_j$ ont un S-polynôme nul dès lors que $i$ et $j$ sont différents. Les définitions et caractérisations équivalentes des bases de Gröbner d'idéaux restent alors valables pour les sous-modules du module libre $A^d$. L'algorithme de Buchberger, modifié pour suivre ces nouvelles définitions, termine sur tout sous-module en fournissant une base de Gröbner. Pour certains ordres, ce calcul correspond à l'algorithme de Gauss.
**Exercice 32.4** Donner des exemples d'ordres qui font que l'algorithme de Buchberger pour les modules simule une réduction par l'algorithme de Gauss. ■

Un point de vue presque équivalent, mais qui donne une variante des calculs avec un peu plus de réductions à zéro (calculs inutiles, donc), est que le calcul est celui d'une base de Gröbner dans l'anneau $A[e_1, \dots, e_d]$ des polynômes en les indéterminées commutatives $e_i$ à coefficients dans l'anneau $A$ pour l'idéal à gauche engendré par les $g_i$ initiaux et tous les produits $e_i e_j = 0$.

Reprenons l'exemple du découplage des relations entre les coordonnées $\phi_i$ donnant $g$ dans la section précédente sur la somme des carrés des fonctions de Bessel. Ces relations se recodent par les éléments

$$g_1 := -e_0 + \partial_v e_1 - (2v x^{-1} + \eta) e_3,$$

$$g_2 := 4(v+1)x^{-1}\partial_v e_1 + (\partial_v + 1)e_2 - 2e_3,$$

$$g_3 := \partial_v e_0 + (4(v+1)^2 x^{-2} \partial_v - 1)e_1 + 2(v+1)x^{-1} \partial_v e_2,$$

$$g_4 := (\partial_v - 1)e_3,$$

du module libre $A^4$ pour l'algèbre de Ore $A = \mathbb{C}(n,k)\langle\partial_n, \partial_k; S_n, S_k\rangle$. Ici, chaque $e_i$ représente la fonction rationnelle inconnue $\phi_i$, et on a représenté les second membres des équations inhomogènes d'origine comme multiples d'une nouvelle inconnue représentée par $e_3$ et contrainte par $g_4$ à être constante.

Le découplage effectué dans la section précédente revient au calcul d'une base de Gröbner pour l'ordre $1 \text{ex}(e_0, e_1, e_2, e_3, \partial_v)$. Les monômes de tête respectifs des $g_i$ sont $e_0, \partial_v e_1, \partial_v e_0$ et $\partial_v e_3$, si bien que le seul S-polynôme non nul est Spoly($g_1, g_3$). Il est donné par

$$ \begin{aligned} \text{Spoly}(g_1, g_3) &= \partial_v g_1 + g_3 \\ &= (\partial_v^2 + 4(v+1)^2 x^{-2} \partial_v - 1)e_1 + 2(v+1)x^{-1} \partial_v e_2 - (2(v+1)x^{-1} + \eta)\partial_v e_3. \end{aligned} $$

Après réductions par $g_2$ et $g_3$, ce polynôme devient

$$g_5 = -e_1 - \left( \frac{x}{4(v+2)} \partial_v^2 + \frac{x^2 - 4v^2 - 12v - 8}{4x(v+2)} \partial_v + \frac{v+1}{x} \right) e_2 + \left( \frac{x}{2(v+2)} - \eta \right) e_3,$$

qui est adjoint à la base de Gröbner en cours de calcul. L'unique nouvel S-polynôme à considérer est celui entre ce $g_5$ et $g_2$, qui est Spoly($g_2, g_4$) = $g_2 + 4(v+1)x^{-1}\partial_v g_5$ et a pour monôme de tête $\partial_v^3 e_2$. Après réduction par $e_3$ et renormalisation, le dernier polynôme introduit dans la base de Gröbner est

$$ \begin{aligned} &((v+1)x^2 \partial_v^3 + (v+1)(x^2 - 4v^2 - 20v - 24) \partial_v^2 \\ &\qquad - (v+3)(x^2 - 4v^2 - 12v - 8) \partial_v - (v+3)x^2)e_2 \\ &\qquad + 4((v^2 + 4v + 3)\eta + x)xe_3. \end{aligned} $$

Ce polynôme n'est autre qu'un recodage de l'équation inhomogène du troisième ordre qui a permis de déterminer $\phi_2$ dans la section précédente.
## Notes

Dans les implantations de l'Algorithme 32.2 de Chyzak [Chy00], le découplage effectué à l'étape (1.e) est une étape coûteuse et la cause de lenteurs dans la résolution qui suit. Une approche alternative qui n'a jamais été étudiée en profondeur serait l'utilisation d'algorithmes pour la résolution directe de systèmes en leurs solutions rationnelles [Bar99]. Malgré tout, il n'est pas clair qu'une telle approche directe doive être meilleure en complexité; un premier pas dans la direction d'une étude en complexité a été fait par Bostan, Chyzak et Panafieu avec l'analyse de la complexité du découplage [BCP13]. Une variante heuristique de l'algorithme de Chyzak a été donnée par Koutschan [Kou10]. Bien qu'elle ne garantisse pas de trouver un résultat (y compris dans le cas différentiel!), cette variante a plusieurs avantages : elle évite tout découplage et prédit très souvent en pratique les bons dénominateurs pour les solutions $\phi_{\alpha,\beta}$, tout en étant extrêmement efficace.

## Bibliographie

Bar99 BARKATOU, Moulay A. (1999). « On rational solutions of systems of linear differential equations ». In: *Journal of Symbolic Computation*, vol. 28, n°4-5. Differential algebra and differential equations, p. 547-567.

BCP13 BOSTAN, Alin, Frédéric CHYZAK et Élie de PANAFIEU (2013). « Complexity estimates for two uncoupling algorithms ». In: *ISSAC 2013, Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation*. ACM, New York, p. 85-92.

Chy00 CHYZAK, Frédéric (2000). « An extension of Zeilberger's fast algorithm to general holonomic functions ». In: *Discrete Mathematics*, vol. 217, n°1-3, p. 115-134.

Kou10 KOUTSCHAN, Christoph (2010). « A fast approach to creative telescoping ». In: *Mathematics in Computer Science*, vol. 4, n°2-3, p. 259-266.
# Annexes
<figure><img src="image_84.png" /></figure>
33. Exercices récapitulatifs

Sauf mention contraire, dans toute la suite, $\mathbb{K}$ désigne un corps effectif de caractéristique nulle.

**Exercice 33.1 — Équivalence de complexités de diverses opérations polynomiales.** Soit $\mathbb{K}$ un corps de caractéristique différente de 2 et soient $M(n), I(n), D(n)$ et $S(n)$ les complexités (mesurées en nombre d'opérations arithmétiques dans $\mathbb{K}$) pour calculer respectivement : le produit de deux polynômes de $\mathbb{K}[X]$ de degré $< n$, l'inverse modulo $X^n$ d'un polynôme de degré $< n$, le reste de la division d'un polynôme de degré $< 2n$ par un polynôme de degré $n$ et le carré d'un polynôme de degré $< n$. Le but de l'exercice est de prouver que les fonctions $M, I, D$ et $S$ ont le même ordre de grandeur.

1. Par quelle technique peut-on montrer que $I \in O(M)$ et $D \in O(M)$ ?

2. Prouver l'identité $y^2 = (y^{-1} - (y+1)^{-1})^{-1} - y$ et conclure que $S \in O(I)$.

3. Montrer que $M \in O(S)$, en utilisant l'égalité $2fg = (f+g)^2 - f^2 - g^2$.

4. Le polynôme réciproque d'un polynôme $b \in \mathbb{K}[X]$ de degré $n$ est noté $réc_n(b)$. Établir une relation entre $réc_n(b)^{-1}$ mod $X^n$ et le quotient de la division de $X^{2n}$ par $b$. En déduire que $I \in O(D)$.

5. Conclure que $O(M) = O(I) = O(S) = O(D)$.

■

**Exercice 33.2 — Décalage rapide de polynômes.**

1. Montrer que si $P$ est un polynôme dans $\mathbb{Q}[X]$ de degré au plus $n$, alors, quel que soit $a \in \mathbb{Q}$, on peut calculer les coefficients du « polynôme décalé » $Q(X) = P(X+a)$ en $O(M(n))$ opérations dans $\mathbb{Q}$.
Indication : commencer par prouver l'identité suivante dans $\mathbb{Q}[X]$ :

$$ \sum_{i=0}^{n} P^{(i)}(a)X^{n-i} = \left( \sum_{i=0}^{n} P^{(i)}(0)X^{n-i} \right) \times \left( \sum_{i=0}^{n} \frac{(aX)^i}{i!} \right) \mod X^{n+1}. $$

2. Montrer que les coefficients des numérateurs et des dénominateurs des fractions rationnelles

$$ R_0 = \frac{1}{X-1} + \frac{1}{X-2} + \cdots + \frac{1}{X-n} \quad \text{et} \quad R_1 = \frac{2}{X-1} + \frac{2}{X-2} + \cdots + \frac{n}{X-n} $$

peuvent être calculés en $O(M(n))$ opérations dans $\mathbb{Q}$.

Indication : pour $R_0$, donner un algorithme de type « diviser pour régner » basé sur l'algorithme de la question (1); pour $R_1$, en ramener le calcul à celui de $R_0$. La formule de Lagrange montre qu'il existe un unique polynôme $P(X) \in \mathbb{Q}[X]$ de degré strictement inférieur à $n$ tel que

$$ P(i) = (-1)^i \binom{n}{i-1}^{-1}, \quad \text{pour tout } i = 1, 2, \dots, n. $$

3. Exprimer $P$ en termes de $R_0$ et $R_1$ et donner un algorithme qui calcule les coefficients de $P$ en $O(M(n))$ opérations dans $\mathbb{Q}$. Ces coefficients sont supposés connus dans la suite de l'exercice.

4. Montrer que la suite d'éléments de $\mathbb{Q}$ de terme général $a_i = P(i)$ vérifie une récurrence linéaire d'ordre $n$ à coefficients constants.

5. En déduire un algorithme pour calculer les valeurs $P(n+1), \dots, P(2n)$ en $O(M(n))$ opérations dans $\mathbb{Q}$.

6. Montrer qu'on peut calculer $P(n+1), \dots, P(2n)$ en $O(n)$ opérations.

■

**Exercice 33.3 — Extrapolation sur une suite arithmétique.** Soit $P$ un polynôme inconnu de $\mathbb{K}[X]$. Le but de l'exercice est de montrer que, à partir de la donnée d'un élément $a \in \mathbb{K}$, d'une borne $d$ sur le degré de $P$, et des valeurs $P(0), P(1), \dots, P(d)$, il est possible de déterminer l'ensemble des valeurs $P(a), P(a+1), \dots, P(a+d)$ en $O(M(d))$ opérations dans $\mathbb{K}$.

1. Traiter d'abord le cas où $a$ appartient à l'ensemble $\{-d, -d+1, \dots, d-1, d\}$. Supposons dans la suite que $a \in \mathbb{K}$ est tel que tous les éléments $a-d, \dots, a+d$ sont non nuls. On rappelle la formule d'interpolation de Lagrange

$$ P(X) = \sum_{i=0}^{d} p_i \prod_{j=0, j \neq i}^{d} (X-j), \quad \text{où} \quad p_i = \frac{P(i)}{\prod_{j=0, j \neq i}^{d} (i-j)}. \qquad (L) $$

2. Montrer que les éléments $p_0, p_1, \dots, p_d$ peuvent être tous calculés en $O(d)$ opérations dans $\mathbb{K}$.
En substituant $X = a + k$ dans l'équation (L), on obtient l'égalité

$$P(a+k) = \Delta_k \cdot \sum_{i=0}^{d} \frac{p_i}{a+k-i}, \quad \text{où} \quad \Delta_k = \prod_{j=0}^{d} (a+k-j). \quad (\tilde{L})$$

3. Montrer que les éléments $\Delta_k$ pour $k = 0, \dots, d$, peuvent être tous calculés en $O(d)$ opérations dans $\mathbb{K}$.

4. Avec l'égalité (L), conclure que l'ensemble des valeurs $P(a), P(a+1), \dots, P(a+d)$ peut se calculer en $O(M(d))$ opérations dans $\mathbb{K}$.

■

**Exercice 33.4 — Décomposition en éléments simples.** On considère une fraction rationnelle

$$F(X) = \frac{P(X)}{Q_1^{\ell_1}(X) \cdots Q_k^{\ell_k}(X)},$$

où $P, Q_1, \dots, Q_k$ sont des polynômes de $\mathbb{Q}[X]$ et les $\ell_i$ sont des entiers strictement positifs tels que

(H1) $\deg(P) < \sum_{i=1}^k \ell_i \cdot \deg(Q_i) = n$, et

(H2) $Q_1, \dots, Q_k$ sont deux à deux premiers entre eux.

La décomposition en éléments simples de $F$ est une écriture

$$\frac{P(X)}{Q_1^{\ell_1}(X) \cdots Q_k^{\ell_k}(X)} = \sum_{i=1}^{k} \sum_{j=1}^{\ell_i} \frac{C_{i,j}(X)}{Q_i^{j}(X)},$$

où les $C_{i,j}$ sont des polynômes de $\mathbb{Q}[X]$ tels que $\deg(C_{i,j}) < \deg(Q_i)$ pour tous $i, j$. L'existence et l'unicité des polynômes $C_{i,j}$ est admise. On appelle DES$_n$ le problème du calcul des polynômes $C_{i,j}$ à partir des polynômes $P, Q_1, \dots, Q_k$ et des entiers $n, \ell_1, \dots, \ell_k$ satisfaisant aux hypothèses (H1) et (H2).

L'objectif de cet exercice est de montrer qu'il est possible de résoudre le problème DES$_n$ en $O(M(n) \log n)$ opérations. Ici, et dans toute la suite de l'exercice, par opération on entend opération arithmétique dans le corps $\mathbb{Q}$ et $M(n)$ représente une borne sur le nombre d'opérations suffisant à multiplier deux polynômes de $\mathbb{Q}[X]$ de degré au plus $n$.

1. Donner un algorithme simple, reposant sur de l'algèbre linéaire, qui résout le problème DES$_n$ et estimer le nombre d'opérations que cet algorithme utilise.

2. Dans le cas $k=1$, le problème DES$_n$ se spécialise au problème du calcul, à partir de deux polynômes $P, Q \in \mathbb{Q}[X]$ tels que $\deg(P) < \ell \cdot \deg(Q) = n$, des polynômes $C_1, \dots, C_\ell$ vérifiant

$$\frac{P(X)}{Q^{\ell}(X)} = \sum_{j=1}^{\ell} \frac{C_j(X)}{Q^j(X)}, \quad \text{et} \quad \deg(C_j) < \deg(Q) \text{ pour tout } j \ge 1.$$
Montrer que dans ce cas, le problème peut se résoudre en $O(M(n) \log n)$ opérations.

Le but des questions 3–9 ci-dessous est de montrer que le problème DES$_n$ avec $\ell_i = 1$ pour tout $i$ peut se résoudre en $O(M(n) \log n)$ opérations. Autrement dit, étant donnés les polynômes $P, R_1, \dots, R_k$ dans $\mathbb{Q}[X]$, avec $\deg(P) < \sum_{i=1}^k \deg(R_i) = n$ et $R_1, \dots, R_k$ deux à deux premiers entre eux, on veut calculer en $O(M(n) \log n)$ opérations les polynômes $C_1, \dots, C_k \in \mathbb{Q}[X]$ tels que

$$ \frac{P(X)}{R_1(X) \cdots R_k(X)} = \sum_{i=1}^{k} \frac{C_i(X)}{R_i(X)}, \quad \text{et } \deg(C_i) < \deg(R_i) \text{ pour tout } i \ge 1. $$

Pour ce faire, on introduit

$$ R(X) = \sum_{i=1}^{k} \left( \prod_{\substack{j=1 \\ j \neq i}}^{k} R_j(X) \right) $$

et pour $1 \le i \le k$, on considère le reste $D_i(X)$ de la division euclidienne de $R(X)$ par $R_i(X)$.

3. Donner un algorithme qui calcule le polynôme $R(X)$ en $O(M(n) \log k)$ opérations.

4. Montrer que les polynômes $D_1, \dots, D_k$ peuvent être calculés eux aussi en un nombre d'opérations en $O(M(n) \log k)$.

5. Montrer que pour tout $1 \le i \le k$, les polynômes $D_i$ et $R_i$ sont premiers entre eux.

6. En notant $E_i$ l'inverse de $D_i$ modulo $R_i$, montrer que $C_i$ est égal au reste de la division euclidienne de $P \cdot E_i$ par $R_i$.

7. Donner un algorithme pour le calcul des $E_i$ en $O(M(n) \log n)$ opérations.

8. Donner un algorithme pour le calcul des $C_i$, en $O(M(n) \log k)$ opérations.

9. Conclure qu'on peut résoudre le problème DES$_n$ avec $\ell_i = 1$ pour tout $i$ en coût $O(M(n) \log n)$.

10. Conclure qu'il est possible de résoudre le problème DES$_n$ en $O(M(n) \log n)$ opérations.

■

**Exercice 33.5 — Polynômes de Fibonacci.** Soit $F_n(X) \in \mathbb{K}[X]$ la suite des polynômes de Fibonacci, définie par les conditions initiales $F_0 = 1$, $F_1 = X$ et la récurrence $F_{n+1} = XF_n + F_{n-1}$ pour tout $n \ge 1$. Soit $N \ge 1$.

1. Estimer le coût d'un calcul direct de tous les coefficients de $F_N(X)$.

2. Montrer qu'il est possible de calculer tous les coefficients de $F_N(X)$ en utilisant $O(M(N))$ opérations dans $\mathbb{K}$.

3. Montrer qu'il est possible de calculer la somme des coefficients de $F_N$ en seulement $O(\log N)$ opérations dans $\mathbb{K}$.

4. Donner un algorithme qui permet le calcul des coefficients de $F_N$ en $O(N)$ opérations dans $\mathbb{K}$.

■
**Exercice 33.6 — Fonctions algébriques et résultats.** Soit $y(X)$ une fonction algébrique annulée par $P(X, Y) \in \mathbb{Q}[X, Y]$.

1. Montrer que la dérivée $y'(X)$ est aussi algébrique, en exhibant un polynôme résultant $R(X, Y)$ qui l'annule.

2. Déterminer un tel polynôme $R$ dans le cas où $P(X, Y) = XY^2 - Y + 1$.

3. Supposant que $P$ est de degré au plus $d$ en $X$ et en $Y$, estimer les degrés en $X$ et en $Y$ du polynôme $R$, puis proposer un algorithme pour son calcul.

4. Analyser la complexité de votre algorithme, mesurée en nombre d'opérations arithmétiques dans $\mathbb{Q}$. En utilisant les meilleurs algorithmes vus en cours pour les opérations fondamentales sur les polynômes et les matrices, à quel exposant aboutissez-vous ? Ici, par exposant on entend un réel $\alpha$ tel que votre algorithme a une complexité en $\tilde{O}(n^\alpha)$, c'est-à-dire linéaire en $n^\alpha$ à des facteurs logarithmiques près.

■

**Exercice 33.7 — Produit diamant.** On considère deux polynômes unitaires $f, g \in \mathbb{Q}[T]$, de degrés strictement plus petits que $n$. Étant donné $H \in \mathbb{Q}[X, Y]$, dont les degrés partiels par rapport à chacune des variables $X$ et $Y$ sont strictement inférieurs à $n$, le produit diamant $f \diamond_H g$ est le polynôme de degré $D = n^2$ défini par

$$f \diamond_H g = \prod_{f(\alpha)=0, g(\beta)=0} (T - H(\alpha, \beta)),$$

le produit étant pris sur les racines complexes de $f$ et de $g$ comptées avec multiplicités. On s'intéresse dans cet exercice au calcul efficace du produit diamant.

1. Montrer que le produit diamant peut s'exprimer à l'aide de résultats et que ses coefficients sont rationnels.

On note A l'algèbre quotient $\mathbb{Q}[X, Y]/(f(X), g(Y))$. Un élément $g \in A$ admet une écriture unique

$$g = \sum_{0 \le i,j < n} g_{i,j} x^i y^j$$

avec $g_{ij} \in \mathbb{Q}$, où $x$ et $y$ sont les images canoniques de $X$ et $Y$ dans $A$. On admet que si $P_1, P_2$ sont deux polynômes de $\mathbb{Q}[X, Y]$ de degrés au plus $d_X$ en $X$ et au plus $d_Y$ en $Y$, on peut calculer leur produit $P_1 P_2$ en $O(M(d_X d_Y))$ opérations dans $\mathbb{Q}$.

2. Montrer que $O(M(D))$ opérations suffisent pour effectuer le produit de deux éléments de $A$.

À tout polynôme $G$ de $\mathbb{Q}[X, Y]$ on associe l'application $\mathbb{Q}$-linéaire de multiplication par $G(x, y)$ dans $A$, définie par $v \in A \mapsto G(x, y)v \in A$. On admet que la trace, notée $\text{Tr}(G)$, de cette application linéaire est égale à $\sum_{\alpha, \beta} G(\alpha, \beta)$, la somme étant prise sur les racines complexes $\alpha$ de $f$ et $\beta$ de $g$ comptées avec multiplicités.

3. Montrer que, pour tout $s \in \mathbb{N}$, la trace $\text{Tr}(H^s)$ s'exprime comme la somme des puissances $s$-ièmes des racines de $f \diamond_H g$.

4. Expliciter pour $0 \le i < n$ ce que valent $\text{Tr}(X^i)$ et $\text{Tr}(Y^i)$.
On rappelle que tout polynôme unitaire $P \in \mathbb{Q}[T]$ de degré au plus $D$ peut être représenté soit par la suite de ces coefficients, soit par la suite des sommes des puissances $s$-ièmes de ses racines, pour $s = 0, \dots, D$, et qu'il est possible de passer d'une représentation à l'autre en $O(M(D))$ opérations.

5. Donner un algorithme pour le calcul des valeurs $\text{Tr}(X^i)$, $0 \le i < n$, en $O(M(n)) \subseteq O(D)$ opérations arithmétiques. Même question pour les valeurs $\text{Tr}(Y^i)$, $0 \le i < n$.

6. En déduire que l'ensemble des valeurs $\text{Tr}(X^i Y^j)$, pour $0 \le i, j < n$, peut être calculé en $O(D)$ opérations dans $\mathbb{Q}$.

7. Donner un algorithme qui, pour tout $N \ge 1$, calcule la suite

$$ \text{Tr}(1), \text{Tr}(H), \text{Tr}(H^2), \dots, \text{Tr}(H^{N-1}) $$

en $O(NM(D))$ opérations dans $\mathbb{Q}$.

8. En déduire un algorithme pour le calcul de $f \diamond_H g$ en $O(DM(D))$ opérations dans $\mathbb{Q}$.

■

**Exercice 33.8 — Multiplication polynomiale de complexité quasi-linéaire.** Le but de cet exercice est de montrer que la multiplication de polynômes de degré au plus $N$ à coefficients dans un corps $\mathbb{K}$ contenant $N$ éléments distincts en progression géométrique peut s'effectuer en complexité arithmétique quasi-linéaire par rapport à $N$.

Soit $A$ et $B$ deux polynômes de $\mathbb{K}[X]$, de degré strictement inférieurs à $N$. Soient $n$ et $d$ deux entiers tels que $N \le nd$ et écrivons

$$ A = A_0(X) + A_1(X)X^d + \dots + A_{n-1}(X)(X^d)^{n-1}, $$

$$ B = B_0(X) + B_1(X)X^d + \dots + B_{n-1}(X)(X^d)^{n-1}, $$

où les polynômes $A_i(X)$, $B_i(X) \in \mathbb{K}[X]$ ont degré au plus $d-1$. Soit $\mathcal{G}$ un sous-ensemble de $\mathbb{K}$ contenant $2d$ éléments distincts en progression géométrique.

1. Si $T$ opérations de $\mathbb{K}$ suffisent pour multiplier dans $\mathbb{K}[X, Y]$ les polynômes

$$ A(X, Y) = A_0(X) + A_1(X)Y + \dots + A_{n-1}(X)Y^{n-1} \quad \text{et} $$

$$ B(X, Y) = B_0(X) + B_1(X)Y + \dots + B_{n-1}(X)Y^{n-1}, $$

montrer qu'on peut multiplier $A(X)$ et $B(X)$ en $T + O(nd)$ opérations de $\mathbb{K}$.

Pour calculer $AB$, il suffit donc d'effectuer le produit $C(X, Y) = A(X, Y)B(X, Y)$, c'est-à-dire de calculer les coefficients $C_i(X) \in \mathbb{K}[X]$, avec $\text{deg}(C_i) < 2d$, de

$$ C(X, Y) = C_0(X) + C_1(X)Y + \dots + C_{2n-2}(X)Y^{2n-2}. $$

2. Montrer que le calcul du produit $AB$ se ramène à $O(d)$ multiplications de $\mathbb{K}[Y]$ en degré $< n$ et $O(n)$ évaluations/interpolations sur les points de $\mathcal{G}$.

Indication : utiliser l'égalité $A(g, Y)B(g, Y) = C(g, Y)$, valable pour $g \in \mathcal{G}$.
3. En déduire qu'il existe trois constantes $\alpha, \beta, \gamma \ge 1$, universelles (c'est-à-dire indépendantes de N, n, d), telles que la complexité arithmétique M de l'algorithme de (2) vérifie $M(\text{nd}) \le \alpha n M(d) + \beta d M(n) + \gamma \text{nd}$.

4. Écrire un algorithme récursif de multiplication dans $K[X]$ de complexité arithmétique $O(N(\log N)^{\log(\alpha\beta)})$ en degré N. ■

**Exercice 33.9 — Multiplication d'opérateurs différentiels.** Dans l'algèbre de polynômes non commutatifs $Q[X]\langle\Theta\rangle$ en les indéterminées X et $\Theta = \frac{d}{dX}$ satisfaisant à la règle de commutation $\Theta X = X\Theta + X$, on considère deux éléments A et B donnés sous la forme

$$A = \sum_{i=0}^{n} \sum_{j=0}^{n} a_{i,j} X^i \Theta^j \quad \text{et} \quad B = \sum_{i=0}^{n} \sum_{j=0}^{n} b_{i,j} X^i \Theta^j$$

avec $a_{i,j} \in Q$ et $b_{i,j} \in Q$. Le but de cet exercice est d'étudier la complexité arithmétique du calcul du produit $C = BA$, c'est-à-dire du calcul, à partir des constantes $a_{i,j}, b_{i,j} \in Q$, des constantes $c_{i,j} \in Q$ telles que

$$C = \sum_{i=0}^{n} \sum_{j=0}^{n} c_{i,j} X^i \Theta^j.$$

Les questions (1)–(3) qui suivent sont largement indépendantes.

1. a. Montrer que $\Theta^i X^\ell = X^\ell (\Theta + \ell)^i$ pour $i \ge 0$ et $\ell \ge 0$, et en déduire que le calcul du produit $\Theta^i X^\ell$ peut s'effectuer en $O(i)$ opérations arithmétiques dans $Q$.

b. Donner des bornes, en fonction de $n$, sur les degrés de C en X et en $\Theta$.

c. Proposer un algorithme naïf pour le calcul de C et estimer son coût arithmétique.

2. Montrer qu'il est possible de calculer C en $O(n^2 M(n))$ opérations dans $Q$, à l'aide d'un schéma itératif. On pensera à écrire B sous la forme

$$B = \sum_{i=0}^{n} b_i(X) \Theta^i, \quad \text{avec } b_i(X) \in Q[X].$$

Dans la suite, on montre comment améliorer les résultats des questions (1) et (2), grâce à un algorithme de type évaluation-interpolation.

3. a. Calculer $\Theta^j(X^k)$, pour $j \ge 0$ et $k \ge 0$. En déduire $P(\Theta)(X^k)$, pour $k \ge 0$ et $P \in Q[X]$.

b. Montrer que les coefficients de C sont uniquement déterminés par la suite des polynômes $C(X^0), C(X^1), \dots, C(X^{2n})$.

c. Donner un algorithme de complexité arithmétique $O(nM(n)\log n)$ pour le calcul de tous les polynômes $p_k := A(X^k)$, pour $0 \le k \le 2n$, et $q_i := B(X^i)$, pour $0 \le i \le 3n$.
d. Montrer que le calcul des polynômes $B(p_0),...,B(p_{2n})$ se ramène à une multiplication de matrices de tailles $(4n+1) \times (3n+1)$ et $(3n+1) \times (2n+1)$.

e. Montrer que, à partir de $C(X^0),...,C(X^{2n})$, il est possible de calculer les coefficients de $C$ en $O(nM(n)\log n)$ opérations arithmétiques.

f. Conclure en écrivant un algorithme complet pour le calcul de $C$ basé sur (c), (d) et (e). Estimer sa complexité.

Exercice 33.10 — Une famille d'intégrales. L'intégrale

$$c_{n,k} = \int_{0}^{+\infty} t^k K_0(t)^n dt,$$

où $K_0$ est une fonction de Bessel (voir ci-dessous), est intervenue récemment dans des études de physique liées au modèle d'Ising. Empiriquement, il est apparu que ces intégrales vérifient une récurrence de la forme

$$(k+1)^{n+1}c_{n,k} + \sum_{\substack{2 \le j < n \\ j \text{ pair}}} P_{n,j}(k)c_{n,k+j} = 0, \quad (R)$$

où les $P_{n,j}$ sont des polynômes de degré au plus $n+1-j$.

Le but de cet exercice est de prouver l'existence d'une telle récurrence et de développer un algorithme permettant de la calculer. Le point de départ est l'équation différentielle

$$\theta^2(y) - t^2 y = 0$$

vérifiée par $y = K_0(t)$. Dans cette équation, $\theta$ représente l'opérateur $t \frac{d}{dt}$. Ainsi, $\theta^2(y) = t(ty)'$. Il sera plus commode de travailler avec $\theta$ qu'avec $d/dt$, et on rappelle $\theta(uv) = u\theta(v) + \theta(u)v$.

On admettra que les intégrales $c_{n,k}$ convergent pour tous $n$ et $k$ entiers positifs, et que pour tout $i,j$ entiers positifs on a en outre

$$\lim_{t \to 0} t^j (K_0(t)^n)^{(i)} = \lim_{t \to \infty} t^j (K_0(t)^n)^{(i)} = 0.$$

1. Montrer que $K_0^2$ vérifie l'équation différentielle

$$\theta^3(y) - 4t^2\theta(y) - 4t^2y = 0.$$

2. Plus généralement, montrer que pour tout $n \in \mathbb{N}$, $K_0^n$ vérifie une équation différentielle linéaire. Donner une borne supérieure sur son ordre. Vérifier que cette borne donne la bonne valeur pour $n = 2$.

3. En déduire l'existence d'une récurrence linéaire vérifiée par les $c_{n,k}$, pour chaque $n$. Donner un algorithme calculant cette récurrence.
4. Montrer par exemple que la suite $c_{2,k}$ vérifie

$$k^3 c_{2,k-1} = 4(k+1)c_{2,k+1}.$$

5. Borner le degré des coefficients dans l'équation calculée en question (2).

6. En déduire une borne de complexité sur l'algorithme de (3) en nombre d'opérations dans $\mathbb{Q}$.

La suite de l'exercice montre comment accélérer ce calcul en tirant parti du fait que l'équation différentielle vérifiée par $K_0$ est d'ordre 2 seulement.

7. Soit $\phi_k := n(n-1)\cdots(n-k+1)K_0^{n-k}\Theta(K_0)^k$. Montrer que

$$\phi_{k+1}(t) = \Theta(\phi_k)(t) - k(n-k+1)t^2\phi_{k-1}(t).$$

8. Utiliser cette récurrence pour $n=2$ pour retrouver l'équation de la question (1), en récrivant $\phi_1, \phi_2, \dots$ au moyen de $\phi_0$.

9. Plus généralement, décrire un algorithme de calcul d'une équation différentielle linéaire vérifiée par $K_0^n$ à partir du résultat de la question (7).

10. Montrer que la complexité du calcul de l'équation différentielle par cette méthode est bornée par $O(n^3)$.

■

**Exercice 33.11** — Calcul rapide du polynôme caractéristique. On considère un réel $\theta > 2$ tel que la multiplication de deux matrices de $M_n(\mathbb{K})$ peut se faire en $MM(n) = n^\theta$ opérations dans $\mathbb{K}$. L'objectif de cet exercice est de prouver que le polynôme caractéristique d'une matrice « générique » de $M_n(\mathbb{K})$ peut être calculé en $O(MM(n))$ opérations de $\mathbb{K}$. Une matrice $F = (f_{ij})_{1\le i,j\le n}$ de $M_n(\mathbb{K})$ sera appelée « de type m-Frobenius » si ses $n-m$ premières colonnes ne contiennent que des éléments nuls, à l'exception des éléments $f_{m+1,1}, f_{m+2,2}, \dots, f_{n,n-m}$ qui valent tous 1. Par exemple, les matrices de type 1-Frobenius sont les matrices compagnon.

Dans la suite de l'exercice, on suppose que la taille $n$ est une puissance de 2 et on note $n = 2^r$. On associe à $A$ une suite de matrices $A_r = A, A_{r-1}, \dots, A_1, A_0$ qui lui sont toutes semblables (c'est-à-dire de la forme $P^{-1}AP$, avec $P$ inversible). Ces matrices sont définies de manière inductive. Pour passer de $A_{i+1}$ à $A_i$, on calcule $s_i = n/2^i$ matrices, notées $A_{i,1} = A_{i+1}, A_{i,2}, \dots, A_{i,s_i} = A_i$ et définies comme suit :

— On considère la matrice $U_{ij}$ de type $2^i$-Frobenius dont les $2^i$ dernières colonnes coïncident avec les $2^i$ dernières colonnes de $A_{ij}$. On suppose que $A$ est « suffisamment générique » pour que $U_{ij}$ soit inversible.

— On pose $A_{i,j+1} := U_{ij}^{-1} A_{i,j} U_{ij}$.

On admettra sans preuve que la matrice $A_i$ ainsi construite est de type $2^i$-Frobenius.

1. Montrer que tous les éléments de l'inverse $D = (d_{ij})$ d'une matrice compagnon $C = (c_{ij})$ avec $c_{1n} \neq 0$ sont nuls, à l'exception des éléments suivants

$$d_{1,2} = \cdots = d_{n-1,n} = 1, \quad d_{n,1} = c_{1,n}^{-1}, \quad d_{n-j+1,1} = -c_{j,n}, \quad d_{n,1} \text{, pour } 2 \le j \le n.$$
En déduire que les éléments de $\mathbb{D}$ peuvent se calculer en $O(n)$ opérations dans $\mathbb{K}$.

2. Étendre le résultat de la question (1), en montrant que l'inverse d'une matrice de type $m$-Frobenius peut se calculer en $O(nMM(m)/m)$ opérations de $\mathbb{K}$.

3. En déduire que le passage de $A_{i+1}$ à $A_i$ se fait en $O(n^2MM(2^i)/4^i)$ opérations de $\mathbb{K}$.

4. Conclure que le polynôme caractéristique de $A$ peut se calculer en utilisant $O(MM(n))$ opérations de $\mathbb{K}$.

■

**Exercice 33.12 — Résolution de systèmes de Vandermonde transposés.** Soient $a_0, a_1, \dots, a_n$ des éléments distincts de $\mathbb{K}$ et soit $V$ la matrice de Vandermonde $V = (a_i^j)_{0 \le i, j \le n}$. Le but de cet exercice est de montrer que, pour tout vecteur $b \in \mathbb{K}^{n+1}$, on peut calculer l'unique solution $x \in \mathbb{K}^{n+1}$ du système linéaire $^tV \cdot x = b$ en $O(M(n) \log n)$ opérations dans $\mathbb{K}$.

1. Donner un algorithme pour le calcul des coefficients du numérateur et du dénominateur de la fraction rationnelle $R = \sum_{i=0}^{n} \frac{1}{1-a_i X}$ en $O(M(n) \log n)$ opérations dans $\mathbb{K}$.

2. Montrer qu'à partir de $R$, on peut calculer en $O(M(n))$ opérations dans $\mathbb{K}$ les $2n$ premiers éléments de la suite $(z_i)_{i \ge 0}$ définie par $z_i = a_0^i + a_1^i + \dots + a_n^i$.

On rappelle que, par définition, une matrice de type Hankel est constante le long de toutes ses anti-diagonales. On rappelle le théorème suivant vu au Chapitre 10 :

*Si $H$ est une matrice de Hankel inversible de taille $n+1$, alors on peut résoudre le système linéaire $Hu = b$ en $O(M(n) \log n)$ opérations dans $\mathbb{K}$.*

3. Montrer que la matrice $H := {}^tV \cdot V$ vérifie l'hypothèse de ce théorème.

4. Utiliser (1) et (2) pour estimer la complexité du calcul des éléments de $H$.

5. Conclure.

6. (Bonus) Écrire un algorithme résolvant $^tV \cdot x = b$, obtenu par transposition (au sens du Chapitre 12) de l'algorithme d'interpolation rapide vu au Chapitre 5.

■

**Exercice 33.13 — Évaluation rapide de polynôme en une matrice.** On rappelle que le polynôme caractéristique d'une matrice arbitraire de $M_n(\mathbb{K})$ peut se calculer en $O(M(M(n) \log n))$ opérations de $\mathbb{K}$. Le but de cet exercice est d'étudier la complexité arithmétique du problème suivant :

*$\mathcal{E}(P, A)$ : étant donnés un polynôme $P = p_0 + p_1 X + \dots + p_D X^D$ de $\mathbb{K}[X]$ et une matrice $A \in M_n(\mathbb{K})$, calculer la matrice $P(A) = p_0 I_n + p_1 A + \dots + p_D A^D$.*

1. Montrer que $O(MM(n)\sqrt{D})$ opérations de $\mathbb{K}$ suffisent pour résoudre le problème $\mathcal{E}(P, A)$.
Indication : écrire $P(X)$ sous la forme $P_0(X) + P_1(X)X^d + P_2(X)(X^d)^2 + \dots$, avec $d$ bien choisi et $P_i(X)$ de degrés au plus $d-1$.

2. Montrer qu'on peut améliorer ce résultat à $O(M(M(n)\sqrt{n} + M(D)))$ opérations.
Indication : commencer par calculer le polynôme caractéristique de $A$.
3. Montrer qu'on peut résoudre $\mathcal{E}(X^D, A)$ en $O(\text{MM}(n)\sqrt{n} + \text{M}(n)\log D)$ opérations de $\mathbb{K}$.

4. Montrer que si $C$ est une matrice compagnon, alors il est possible de résoudre $\mathcal{E}(P, C)$ en $O(n^2 + \text{M}(D))$ opérations de $\mathbb{K}$.

5. Montrer que s'il existe un réel $\beta > 2$ tel que $\mathcal{E}(X^2, A)$ puisse se résoudre en $n^\beta$ opérations de $\mathbb{K}$ pour toute matrice $A$, alors la multiplication de deux matrices quelconques de $M_n(\mathbb{K})$ peut se faire en $O(n^\beta)$ opérations dans $\mathbb{K}$.

6. Montrer que si $A \in M_n(\mathbb{K})$ et $\text{deg}(P) = n$, la première colonne de $P(A)$ peut être calculée en $O(\text{MM}(n)\log n)$ opérations de $\mathbb{K}$.

Dans la suite, on suppose que la matrice $A$ est « suffisamment générique », en ce sens que la matrice $U \in M_n(\mathbb{K})$, dont la $\ell$-ième colonne coïncide avec la première colonne de $A^\ell$, est une matrice inversible.

7. Montrer que la matrice $C = \text{UAU}^{-1}$ est une matrice de type compagnon et qu'elle peut être calculée en $O(\text{MM}(n)\log n)$ opérations de $\mathbb{K}$.
Indication : remarquer que l'espace vectoriel $V = \mathbb{K}^n$ admet $\{A^\ell e\}_{1\le\ell\le n}$ comme base, où $e = {}^t(1, 0, \dots, 0) \in V$, et que $U$ est la matrice de passage entre cette base et la base canonique de $V$.

8. En déduire que, pour une matrice $A$ « suffisamment générique », le problème $\mathcal{E}(P, A)$ peut se résoudre en $O(\text{MM}(n)\log n + \text{M}(D))$ opérations de $\mathbb{K}$.

9. Montrer que, pour une matrice $A$ « suffisamment générique », on peut résoudre $\mathcal{E}(X^D, A)$ en $O(\text{MM}(n)\log n + \text{M}(n)\log D)$ opérations de $\mathbb{K}$.

**Exercice 33.14 — Somme de solutions d'équations différentielles linéaires. On considère deux équations différentielles**

$$a_r(X)y^{(r)}(X) + \dots + a_0(X)y(X) = 0 \qquad (E1)$$

et

$$b_s(X)y^{(s)}(X) + \dots + b_0(X)y(X) = 0 \qquad (E2)$$

et on recherche une équation différentielle vérifiée par toutes les sommes $h = f + g$ où $f$ est solution de (E1) et $g$ une solution de (E2). On suppose que les $a_i$ et les $b_i$ sont des polynômes de $\mathbb{Q}[X]$ tels que $\text{deg} a_i \le m$ et $\text{deg} b_i \le n$, et qu'aucun de $r, s, a_r$ et $b_s$ n'est nul. On note $R = r + s$ et $D = \max\{m, n\}$.

## Préambule

1. Montrer que $h$ est solution d'une équation $\mathcal{R}(y) = 0$ d'ordre au plus $R$.

Les équations (E1) et (E2) permettent de récrire toute dérivée d'ordre arbitraire de $f$ ou de $g$ comme combinaison linéaire des $r+s$ fonctions $f, \dots, f^{(r-1)}, g, \dots, \text{et } g^{(s-1)}$. L'espace vectoriel sur $\mathbb{Q}(X)$ engendré par les dérivées d'ordre arbitraire $f, f', g'', \dots, g, g', g'', \dots$, a donc dimension au plus $R$.
Dans cet espace vectoriel, $h, \dots, h^{(R)}$ sont liées, et une relation de liaison non triviale fournit $\mathcal{R}$ après avoir chassé les dénominateurs.

Première méthode : recombinaison des équations

Pour $i \in \mathbb{N}, j \in \mathbb{N}, k \in \{1, 2\}$, on note $M_{i,j}^{(k)}(y) = 0$ l'équation obtenue en dérivant $j$ fois l'équation (k) puis en multipliant le résultat par $X^i$. On voit $M_{i,j}^{(k)}$ comme une application de la variable $y$. Pour un entier $\delta \ge m+n$, on considère :

$$S^{(\mathrm{E1})} = \{ M_{i,j}^{(\mathrm{E1})} : i \le \delta - m, j \le s \} \quad \text{et} \quad S^{(\mathrm{E2})} = \{ M_{i,j}^{(\mathrm{E2})} : i \le \delta - n, j \le r \}.$$

2. Déterminer des bornes supérieures $d_{\max}$ et $r_{\max}$ telles que la famille des $X^i y^{(j)}$ pour $0 \le i \le d_{\max}$ et $0 \le j \le r_{\max}$ permette d'exprimer tous les $\mathcal{R}(y)$ quand $\mathcal{R}$ décrit $S^{(\mathrm{E1})} \cup S^{(\mathrm{E2})}$.

3. On veut résoudre

$$\sum_{\mathcal{R} \in S^{(\mathrm{E1})}} \lambda_{\mathcal{R}} \mathcal{R}(y) = \sum_{\mathcal{R} \in S^{(\mathrm{E2})}} \mu_{\mathcal{R}} \mathcal{R}(y) \qquad (\mathrm{R})$$

en des coefficients $\lambda$ et $\mu$ dans $\mathbb{Q}$. En égalant les coefficients sur la base des $X^i y^{(j)}$, compter le nombre d'équations et le nombre d'inconnues. Choisir $\delta$ pour assurer l'existence de solutions non triviales.

4. Donner un algorithme pour le calcul d'une équation pour les sommes $h = f + g$ et justifier sa correction.

5. Évaluer en termes de $R, D$ et avec des $O(\cdot)$ le coût arithmétique du calcul des $M_{i,j}^{(k)}(y)$ de proche en proche et celui de la résolution du système. Conclure sur la complexité arithmétique de la méthode.

Deuxième méthode : réductions par les équations

6. Pour une solution $f$ de (E1) et une combinaison linéaire $u = p_0 f + \cdots + p_{r-1} f^{(r-1)}$ à coefficients des polynômes de degré maximal $\delta$, montrer que $a_r u'$ s'exprime comme une combinaison linéaire de $f, \dots, f^{(r-1)}$ pour des coefficients polynomiaux dont on bornera le degré en fonction de $\delta$.

7. En déduire que pour tout entier $i \ge r-1$, le produit $a_r^{i+1-r} f^{(i)}$ s'exprime comme une combinaison linéaire $p_{i,0} f + \cdots + p_{i,r-1} f^{(r-1)}$ pour des polynômes $p_{i,j}$ dont on bornera le degré.

8. Énoncer un résultat analogue pour $b_s^{i+1-s} g^{(j)}$ et pour des polynômes $q_{i,j}$.

9. On veut résoudre

$$\sum_{i=0}^{R} c_i(X) f^{(i)} = 0 = \sum_{i=0}^{R} c_i(X) g^{(i)} \qquad (\mathrm{P})$$
pour des polynômes $c_i$ dans $\mathbb{Q}[X]$ communs aux deux équations. Montrer qu'en multipliant le membre de gauche de (P) par une puissance convenable de $a_r$ et le membre de droite par une puissance convenable de $b_s$, et en réduisant par les équations (E1) et (E2), on obtient un système d'équations linéaires sur les $c_i$ à coefficients polynomiaux. Indiquer les dimensions de ce système et borner le degré de ses coefficients en termes de R et D.

10. Donner un algorithme pour le calcul d'une équation pour les sommes $h = f + g$ et justifier sa correction.

11. Évaluer en termes de R, D et avec des $\tilde{O}(\cdot)$ (c'est-à-dire à des facteurs logarithmiques près) le coût arithmétique de cet algorithme.

12. Comparer avec la première méthode.

■

**Exercice 33.15** — Quartique de Macaulay. On considère l'idéal homogène I engendré par les quatre polynômes

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

dans $\mathbb{Q}[X_0, X_1, X_2, X_3]$. On ordonne les monômes par l'ordre lexicographique induit par $X_3 < X_2 < X_1 < X_0$ et on convient de prendre comme monôme dominant d'un polynôme non nul le *plus petit* de ses monômes.

Pour un entier $n > 0$, on identifie librement un monôme $X_0^{e_0} \cdots X_n^{e_n}$ et le $(n+1)$-uplet d'entiers $(e_0, \dots, e_n)$. Pour un idéal J de $\mathbb{Q}[X_0, \dots, X_n]$, on note $E(J)$ l'ensemble des monômes dominants des éléments non nuls de J, ou de façon équivalente, la partie stable correspondante dans $\mathbb{N}^{n+1}$.

1. Calculer une base standard de I relativement à l'ordre indiqué. Donner un système générateur minimal de $E(I) \subset \mathbb{N}^4$.

2. Rappelons que la fonction de Hilbert $\text{HF}_E$ associée à une partie stable E de $\mathbb{N}^{n+1}$ est définie par :

$$\text{HF}_E(s) = \text{card}\{(e_0, \dots, e_n) \in \mathbb{N}^{n+1} \mid (e_0, \dots, e_n) \notin E, e_0 + \dots + e_n = s\}.$$

Pour $i$ dans $\mathbb{N}$, on considère la partie de $E(I)$ constituée des éléments dont la première coordonnée $X_0$ vaut $i$ et on identifie cette partie à une partie $E_i$ de $\mathbb{N}^3$.

a. Donner un système générateur minimal de $E_0$ et dessiner $E_0$. Calculer la fonction de Hilbert, le polynôme de Hilbert, la dimension et le degré de $E_0$.

b. Que vaut $E_i$ pour un $i$ général ?

c. L'application induite par la multiplication par $X_0$ dans le quotient $\mathbb{Q}[X_0, X_1, X_2, X_3]/I$ est-elle injective ?

3. Calculer la fonction de Hilbert, le polynôme de Hilbert, la dimension et le degré de $E(I)$.

4. Rappelons que l'espace projectif $\mathbb{P}_{\mathbb{C}}^n$ s'identifie à l'ensemble des $(n+1)$-uplets non nuls $(u_0 : \dots : u_n)$ de $\mathbb{C}^{n+1}$ vus à multiplication près par un scalaire non nul.
On souhaite maintenant étudier le lieu des zéros Z(I) de l'idéal homogène I dans l'espace projectif $\mathbb{P}^3_C$. Dans cette question, on considère $X_1$ comme indéterminée d'homogénéisation, et non comme d'habitude $X_0$.

a. Quel est l'ensemble des zéros à l'infini, c'est-à-dire de la forme $(x_0 : 0 : x_2 : x_3)$ ?

b. Déshomogénéiser le système polynomial initial en faisant $x_1 = 1$ et décrire l'ensemble algébrique affine de $\mathbb{C}^3$ ainsi obtenu.

c. Conclure en décrivant Z(I) et comparer avec les invariants calculés dans la question 3.

**Exercice 33.16 — Diagonales de séries différentiellement finies.** Étant donnée une série double différentiellement finie

$$f = \sum_{i,j \in \mathbb{N}} c_{i,j} x^i y^j, \qquad (33.1)$$

cet exercice vise à donner un algorithme de calcul d'une équation différentielle pour la diagonale

$$\Delta(f) = \sum_{i \in \mathbb{N}} c_{i,i} t^i,$$

laquelle est aussi différentiellement finie. Par exemple, la série

$$\frac{1}{1-x-y} = \sum_{i,j \in \mathbb{N}} \binom{i+j}{i} x^i y^j, \qquad (33.2)$$

qui vérifie deux équations différentielles linéaires d'ordre 1, l'une en $x$, l'autre en $y$, a pour diagonale

$$\Delta\left(\frac{1}{1-x-y}\right) = \sum_{i \in \mathbb{N}} \binom{2i}{i} t^i = \frac{1}{\sqrt{1-4t}}, \qquad (33.3)$$

donnée par $(1-4t)y' - 2y = 0$.

En préambule, nous donnons quelques résultats à admettre et utiliser librement sur les deux natures de séries formelles un peu particulières utilisées dans cet énoncé. Ces résultats établissent que les séries considérées peuvent être manipulées formellement sans ambages (multiplications, dérivations, substitutions, identifications de termes).

Pour des coefficients $c_{i,j}$ dans un corps $C$, les séries du type (33.1) forment une $C$-algèbre notée $C[[x,y]]$, stable par les dérivations par $x$ et $y$, dont le corps des fractions $F_{x,y}$ contient celui des fractions rationnelles, $C(x,y)$, et est lui-même stable par les deux dérivations. Une série $f$ donnée par (33.1) étant aussi dans $F_{x,y}$, on dit qu'elle est différentiellement finie lorsque ses dérivées mixtes $\partial_x^i \partial_y^j(f)$ engendrent un sous-espace vectoriel de $F_{x,y}$ de dimension finie sur $C(x,y)$.
Les séries

$$g = \sum_{i \in \mathbb{Z}, j \in \mathbb{N}, i+j \ge k} c_{i,j} s^i t^j,$$

où $k \in \mathbb{Z}$ ne dépend que de $g$, forment une autre C-algèbre, notée $S_{s,t}$, stable par les dériva\^tions par $s$ et $t$, dont le corps des fractions $F_{s,t}$ contient celui des fractions rationnelles, $C(s,t)$, et est lui-même stable par les deux dériva\^tions. Une série $g$ est dite différentiellement finie lorsque ses dérivées mixtes $\partial_s^i \partial_t^j(f)$ engendrent un sous-espace vectoriel de $F_{s,t}$ de dimension finie sur $C(s,t)$.

On admet que la substitution $x = t/s$, $y = s$ donne une application bien définie de $C[[x,y]]$ dans $S_{s,t}$.

1. On considère l'application C-linéaire $\phi$ de $C[[x,y]]$ dans $S_{s,t}$ définie sur $f$ donnée par (33.1) par

$$\phi(f) = \frac{1}{s} f\left(\frac{t}{s}, s\right) = \sum_{i,j \in \mathbb{N}} c_{i,j} s^{j-i-1} t^i.$$

On note

$$\delta(f) = \sum_{i \in \mathbb{N}} c_{i,i} x^i y^i = \Delta(f)(xy).$$

Vérifier que

$$\phi(\delta(f)) = \frac{1}{s} \Delta(f).$$

2. Pour une série $f \in C[[x,y]]$, des fractions rationnelles $r_{i,j}(s,t)$ en nombre fini et un opérateur différentiel linéaire $L(t, \partial_t)$, on suppose vérifiée l'identité

$$L(t, \partial_t)(g) = \partial_s \left( \sum_{i,j} r_{i,j}(s,t) \partial_s^i \partial_t^j(g) \right)$$

quand $g = \phi(f)$. Montrer que $L$ annule la diagonale $\Delta(f)$.

3. Pour $g = \phi(f)$, exprimer $\partial_s(g)$ et $\partial_t(g)$ comme les images par $\phi$ d'expressions linéaires en $f$ et ses dérivées premières, qu'on exprimera sous la forme

$$\partial_s(g) = \phi(L_s(f)) \quad \text{et} \quad \partial_t(g) = \phi(L_t(f)).$$

Pour valider son résultat, on pourra observer que $L_s$ et $L_t$ commutent.

4. En déduire que si $f$ est différentiellement finie, il en est de même de $g$.

5. Proposer un algorithme qui, étant donné un idéal annulateur pour $f$, calcule un idéal annulateur pour $g$.

6. En déduire un algorithme à base de la version différentielle de l'algorithme de Zeilberger qui, étant donné un idéal annulateur pour $f$, calcule un polynôme tordu $L(t, \partial_t)$ annulateur de $\Delta(f)$.

7. Montrer que $g = \phi(f) = 1/(s-t-s^2)$.

8. Appliquer à $g$ l'algorithme de Zeilberger différentiel et produire une équation différentielle d'ordre 1 en $t$ sur la diagonale (33.3).

■
**Exercice 33.17 — Intégration définie de fractions rationnelles par réduction de Hermite.** À l'exclusion de la première question, d'ordre plus général et indépendante de la suite, cet exercice s'intéresse à l'intégration définie rapide de fractions rationnelles à deux variables.

Pour la première question seulement, on considère l'intégration de fonctions $f$ hyperexponentielles en deux variables $x$ et $y$, c'est-à-dire dont les deux dérivées logarithmiques sont données par des fractions rationnelles :

$$ \frac{\frac{\partial f}{\partial x}(x, y)}{f} \in \mathbb{Q}(x, y) \quad \text{et} \quad \frac{\frac{\partial f}{\partial y}(x, y)}{f} \in \mathbb{Q}(x, y). $$

1. Utiliser les algorithmes du cours pour décrire un analogue de l'algorithme de Zeilberger réalisant la création télescopique pour ce cadre, c'est-à-dire pour calculer un opérateur différentiel et une fraction rationnelle,

$$ L = \sum_{i=0}^{\rho} \eta_i(x) \partial_x^i \in \mathbb{Q}(x) \langle \partial_x; \mathrm{id}, d/dx \rangle \quad \text{et} \quad \phi \in \mathbb{Q}(x, y), $$

vérifiant la relation $L(f) = \partial_y(\phi f)$.

Observons que cette approche ne permet pas de calculer $L$ sans calculer $\phi$, alors que ce dernier n'est pas toujours utilisé dans les applications, et par ailleurs que la taille de ce $\phi$ s'avère souvent être le facteur limitant dans les calculs.

On s'intéresse maintenant à l'intégration dans le cas de fonctions $f$ qui soient des fractions rationnelles, afin d'obtenir un algorithme spécialisé de bonne complexité. Dorénavant, $f$ est une fraction rationnelle de la forme $p/q$ pour des polynômes non nuls $p$ et $q$ de $\mathbb{Q}[x, y]$ de degrés partiels en $x$ et $y$ bornés respectivement par $d_x$ et $d_y$ et tels que $\deg_y(p) < \deg_y(q)$. On suppose de plus que le polynôme $q \in \mathbb{Q}[x, y]$ est sans facteur carré (relativement à $y$), au sens où le pgcd de $q$ et $\partial q/\partial y$, dans $\mathbb{Q}(x)[y]$, est 1. On rappelle qu'il existe alors une relation de Bézout de la forme

$$ uq + v \frac{\partial q}{\partial y} = 1 $$

pour des polynômes à deux variables $u$ et $v$ dans $\mathbb{Q}(x)[y]$, vérifiant les contraintes $\deg_y(u) < d_y - 1$ et $\deg_y(v) < d_y$. La notation $\mathbb{Q}_{<d}[x]$, resp. $\mathbb{Q}_{\le d}[x]$, dénote l'ensemble des polynômes de degré strictement inférieur, resp. inférieur, à $d$. On admettra l'existence d'un algorithme qui, étant donnée une matrice $r \times r$ à coefficients polynomiaux de $\mathbb{Q}[x]$ de degré au plus $n$, calcule une base du noyau, constituée de vecteurs de polynômes, en $\mathbb{O}(r^\omega n)$ opérations dans $\mathbb{Q}$.

2. a. Pour $h \in \mathbb{Q}(x)[y]_{<2d_y}$, montrer l'existence de polynômes $A$ et $a$ dans $\mathbb{Q}(x)[y]_{<d_y}$ satisfaisant à

$$ \frac{h}{q^2} = \partial_y \left( \frac{A}{q} \right) + \frac{a}{q}. $$

b. Pour $\deg_y(h) < md_y$, généraliser ce résultat pour montrer l'existence de
polynômes $A \in \mathbb{Q}(x)[y]_{<(m-1)d_y}$ et $a \in \mathbb{Q}(x)[y]_{<d_y}$ satisfaisant à

$$ \frac{h}{q^m} = \partial_y \left( \frac{A}{q^{m-1}} \right) + \frac{a}{q}. $$

On admettra l'unicité de $a$ dans l'écriture précédente. Cette réduction de $h/q^m$ à $a/q$ est la réduction de Hermite.

3. On considère l'application $\phi$ qui à A et $a$ dans $\mathbb{Q}(x)[y]_{<d_y}$ associe

$$ \phi(A, a) = q \frac{\partial A}{\partial y} - \frac{\partial q}{\partial y} A + qa $$

dans $\mathbb{Q}(x)[y]_{<2d_y}$, ainsi que sa matrice $\mathcal{H}$ sur la base monomiale. Expliciter les dimensions de cette matrice $\mathcal{H}$ ainsi qu'une borne sur le degré en $x$ de ses coefficients.

4. On admettra que pour tout $h \in \mathbb{Q}[x,y]$ avec $\deg_y(h) < 2d_y$, l'équation $\phi(A,a) = h$ admet une unique solution $(A,a)$ pour des polynômes de $\mathbb{Q}(x)[y]$ vérifiant $\deg_y(A) < d_y$ et $\deg_y(a) < d_y$. Ces polynômes peuvent donc se récrire avec un dénominateur commun $\delta$ sous la forme $A = B/\delta$ et $a = b/\delta$. On pose $\mu = \deg_x(h)$. Utiliser les formules de Cramer pour expliciter un bon choix de $\delta$ et donner des bornes sur les degrés en $x$ de B, $b$ et $\delta$.

5. a. Donner un algorithme qui, étant donné un polynôme $h \in \mathbb{Q}[x,y]$ vérifiant $\deg_y(h) < 2d_y$, détermine B et $b$ dans $\mathbb{Q}(x)[y]$ en fonction de $h, u, v$ et $q$, de sorte que

$$ \frac{h}{q^2} = \partial_y \left( \frac{B}{\delta q} \right) + \frac{b}{\delta q}, $$

avec $\deg_y(b) < d_y$.

b. Estimer la complexité de cet algorithme en supposant que B est renvoyé sans nécessairement développer les sommes et les produits, mais que $b$ est renvoyé sous forme développée et réduite.

6. a. Par réduction de Hermite, chaque $\partial_x^i(f)$ peut s'écrire sous la forme

$$ \partial_x^i(f) = \partial_y(g_i) + \frac{r_i}{q} $$

pour $g_i \in \mathbb{Q}(x,y)$ et un unique $r_i \in \mathbb{Q}(x)[y]$ tels que $\deg_y(r_i) < \deg_y(q)$. Donner les étapes d'un algorithme incrémental donnant $r_{i+1}$ à partir de $r_i$ et expliciter le $g_{i+1}$ correspondant en fonction de $g_i$.

b. Donner un multiple explicite du dénominateur commun des coefficients de $r_i$ et établir une borne sur le degré en $x$ des numérateurs correspondants.

c. En déduire la complexité du calcul de tous les $r_i$ pour $0 \le i \le \rho$.

7. a. Montrer que $\{r_0, \dots, r_{d_y}\}$ est liée et en déduire un algorithme pour calculer un
opérateur différentiel et une fraction rationnelle,

$$
L = \sum_{i=0}^{\infty} \eta_i(x) \partial_x^i \in \mathbb{Q}(x) \langle \partial_x; \mathrm{id}, d/dx \rangle \quad \text{et} \quad g \in \mathbb{Q}(x, y),
$$

vérifiant la relation L(f) = ∂_y(g). Décrire l'algorithme complet.

b. Évaluer sa complexité.

**Exercice 33.18 — Rencontre entre une hyperbole et deux droites.** Soit I l'idéal de $\mathbb{Q}[x, y]$ engendré par les deux polynômes $y^2 - x^2$ et $xy - 1$. On ordonne les monômes de $\mathbb{Q}[x, y]$ d'abord par degré croissant, puis en cas d'égalité de degré, par degré croissant en $y$ :

$$
1 < x < y < x^2 < xy < y^2 < x^3 < x^2y < xy^2 < y^3 < \dots
$$

Le monôme dominant d'un polynôme non nul sera le plus grand pour cet ordre.

1. Calculer une base standard de I pour cet ordre et donner une base monomiale du $\mathbb{Q}$-espace vectoriel $\mathbb{Q}[x, y]/I$.

2. La multiplication par $x$ induit un endomorphisme linéaire de $\mathbb{Q}[x, y]/I$. Calculer sa matrice dans la base ci-dessus, puis son polynôme caractéristique et ses valeurs propres. Que représentent ces dernières ?

3. Soit J un idéal de $\mathbb{Q}[x_1, \dots, x_n]$ définissant une variété affine V de $\mathbb{C}^n$ de dimension zéro, de degré $r$, et composée de $r$ points distincts. Soit $f$ un polynôme de $\mathbb{C}[x_1, \dots, x_n]$ séparant les points de V, c'est-à-dire que les images par $f$ de deux points distincts de V restent distincts. On nomme $P(T)$ le polynôme caractéristique de l'endomorphisme linéaire $F$ de $\mathbb{Q}[x_1, \dots, x_n]/J$ induit par la multiplication par $f$, et $Q(T)$ le polynôme dont les racines sont les images par $f$ des points de V.

a. Quels sont les degrés de P et Q ?

b. Soit $x$ un point de $V$. Montrer que $f(x)$ est une valeur propre de $F$ en construisant explicitement un vecteur propre par interpolation.

**Exercice 33.19 — Problème des moments pour une suite hypergéométrique.**
Soit $(C_n)_{n \ge 0} = (1, 1, 2, 5, 14, 42, \dots)$ la suite de terme général $C_n = \frac{1}{n+1} \binom{2n}{n}$. Le but de cet exercice est de résoudre le problème des moments pour cette suite, c'est-à-dire de trouver deux réels $a$ et $b$, et une fonction continue $\mu : [a, b] \to \mathbb{R}_+$ tels que

$$
C_n = \int_a^b \mu(x) x^n dx \quad \text{pour tout } n \ge 0. \qquad (P)
$$

Une série algébrique. Soit $C(z)$ la série génératrice $C(z) = \sum_{n \ge 0} C_n z^n$.

1. Expliciter une récurrence linéaire satisfaite par la suite $(C_n)$.

2. Montrer que tout approximant de Padé-Hermite de type (1, 1, 1) du vecteur de
séries $^t(1, C, C^2)$ est proportionnel à $(1, -1, z)$. En déduire un polynôme $P(z, w) \in \mathbb{Q}[z, w]$ tel que $P(z, C(z)) = 0 \bmod z^5$.

Pour cela, exprimer le problème d'approximation en termes d'algèbre linéaire. Expliciter la matrice du système linéaire associé. Est-elle structurée? Quel est son rang de déplacement?

3. Montrer qu'il existe une unique série $S(z) \in \mathbb{Q}[[z]]$ telle que $P(z, S(z)) = 0$. Com- bien vaut $S(z) \bmod z^5$?

4. Écrire un algorithme à base d'itérations de Newton, prenant en entrée un entier positif $\kappa$, et renvoyant en sortie les $N = 2^\kappa$ premiers coefficients de S.

5. Montrer que S vérifie une équation différentielle linéaire, que l'on explicitera. On exhibera d'abord une relation de Bézout dans $\mathbb{Q}(z)[w]$ entre P et $\frac{\partial P}{\partial w}$.

6. En déduire que les coefficients de $S(z) = \sum_{n \ge 0} s_n z^n$ vérifient la récurrence

$$ (n+2)s_{n+1} - (4n+2)s_n = 0, \quad \text{pour tout } n \ge 0. $$

7. Conclure que la série C(z) est algébrique, et est racine du polynôme P(z, w). *Moments et résultats.* Soit $G(z)$ la série $G(z) = C(1/z)/z$ dans $\mathbb{Q}[[1/z]]$.

Nous admettons que G définit une fonction sur $C \setminus [0, 4]$, et que la solution du problème (P) est donnée par la formule d'inversion de Stieltjes :

$$ \mu(x) = - \frac{\psi(x)}{\pi}, \quad \text{où} \quad \psi(x) = \lim_{y \to 0^+} \left( \operatorname{Im} G(x + iy) \right). $$

8. Montrer que $G(z)$ est une fonction algébrique, en exhibant un polynôme annula- teur $K(z, w) \in \mathbb{Q}[z, w]$.

9. Écrivons $G(x + iy)$ sous la forme $A(x, y) + iB(x, y)$, avec A et B des fonctions réelles, et notons $\varphi(x)$ et $\psi(x)$ les limites en $y = 0^+$ de A et de B. Justifier l'égalité $K(x, \varphi(x) + i\psi(x)) = 0$. En déduire l'algébricité de $\varphi(x)$ et de $\psi(x)$.

10. Déterminer, à l'aide d'un résultant, un polynôme annulateur de $\psi(x)$. En déduire une forme explicite de $\mu(x)$.

*Preuve par télescopage créatif.* Nous allons prouver l'identité

$$ C_n = \frac{1}{2\pi} \int_0^4 x^n \sqrt{\frac{4-x}{x}} dx. \qquad (M) $$

11. On veut montrer que la fonction $U(n,x) = x^n \sqrt{\frac{4-x}{x}}$ est solution d'une équation fonctionnelle linéaire de la forme

$$ (a(n)S_n + b(n)) \cdot U = D_x \cdot (r(n, x)U), \qquad (C) $$

où $S_n$ est l'opérateur de décalage, $D_x$ est l'opérateur de dérivation, et où $r \in \mathbb{Q}(n, x)$ et $a, b \in \mathbb{Q}(n)$ sont des fractions rationnelles inconnues. (Ici, la notation « · » désigne l'application d'un opérateur à une fonction.)

Afin de déterminer $a, b$ et $r$, on parcourra les étapes suivantes :
a. Expliciter deux opérateurs qui annulent U, de la forme $S_n - \alpha(n,x)$ et $D_x - \beta(n,x)$, avec $\alpha, \beta \in \mathbb{Q}(n,x)$.

b. Utiliser ces deux opérateurs pour montrer que l'équation (C) est équivalente à l'équation différentielle linéaire inhomogène paramétrée d'ordre 1

$$ \frac{\partial r}{\partial x}(n,x) + \frac{nx - 4n + 2}{x(x - 4)} r(n,x) = a(n)x + b(n). $$

c. Montrer que $r$ n'a pas de pôle en $x = 0$ et $x = 4$. En déduire que $r$ est un polynôme en $x$, à coefficients dans $\mathbb{Q}(n)$.

d. Borner le degré (en $x$) de $r$, et montrer que $g$ est divisible par $x(x - 4)$ dans $\mathbb{Q}(n)[x]$.

e. Expliciter $g$, puis $a$ et $b$, et conclure.

12. En déduire une récurrence linéaire vérifiée par la suite $f_n = \int_0^4 U(n,x) dx$.

13. En admettant que $\int_0^4 \sqrt{\frac{4-x}{x}} = 2\pi$, conclure la preuve de l'égalité (M).

Compléments.

14. Quelle est la complexité arithmétique et binaire du calcul des N premiers termes de la série $S(z)$ en utilisant l'itération de Newton donnée en (4)?

15. Quelle est la taille binaire de $C_n$, et quel est le coût binaire de son calcul, en utilisant la récurrence obtenue en (1) et un algorithme : (i) naïf ; (ii) par scindage binaire ; (iii) par « pas de bébés, pas de géants » ?

■

**Exercice 33.20 — Relation de contiguïté entre fonctions de Bessel.** Les fonctions de Bessel de première espèce, $J_n(x)$, sont solutions de l'équation différentielle et de l'équation mixte différentielle et de récurrence

$$ x^2 y_n''(x) + xy_n'(x) + (x^2 - n^2)y_n(x) = 0 \quad \text{et} \quad xy_n'(x) + xy_{n+1}(x) - ny_n(x) = 0. $$

1. Écrire dans l'algèbre de Ore $\mathbb{Q}(n,x)(\partial_n, \partial_x; S_n, I, 0, d/dx)$ les polynômes tordus associés à ces équations, et montrer qu'ils constituent une base de Gröbner pour l'ordre lexicographique induit par $\partial_n > \partial_x$.

2. Soit $I$ l'idéal engendré par les polynômes tordus de la question précédente. Justifier, avec le moins de calculs possible, l'existence d'un polynôme de $I$ non nul et indépendant de $\partial_x$. Quel est le degré minimal en $\partial_n$ d'un tel polynôme ?

3. Indiquer une méthode de calcul de ce polynôme.

■

**Exercice 33.21 — Équations différentielles pour les fonctions algébriques.** On s'intéresse aux fonctions $\alpha$ solutions d'une équation polynomiale $P(x, \alpha(x)) = 0$ pour un polynôme $P(X, Y) \in \mathbb{Q}[X, Y]$ de degrés partiels $D_X$ en $X$ et $D_Y$ en $Y$, avec $D_X \ge 1, D_Y > 1$. Nous voulons trouver des équations différentielles linéaires vérifiées par ces fonctions algébriques $\alpha$.
On note $P_X$ et $P_Y$ les dérivées de P relativement à X et Y, respectivement. Pour éviter que P n'ait des facteurs multiples, on fait l'hypothèse que P et $P_Y$ sont premiers entre eux.

**Résolvante de Cockle.** Un premier algorithme, attribué à Cockle (1861), représente les dérivées $\alpha^{(k)}$ comme des polynômes de degrés au plus $D_Y - 1$ en $\alpha$ et se ramène à de l'algèbre linéaire sur $\mathbb{Q}(X)$. Il passe par une première famille de polynômes $W_k$, introduits ci-dessous.

1. Montrer la relation $\alpha' = -P_X(x, \alpha)/P_Y(x, \alpha)$.

2. Montrer l'existence de polynômes $W_k(X, Y)$ tels que

$$ \alpha^{(k)} = W_k(x, \alpha)/P_Y(x, \alpha)^{2k-1} $$

en établissant une récurrence sur les polynômes $W_k$.

3. Que vaut $W_1$ ?

4. Montrer les inégalités $\deg_X W_k \le (2D_X - 1)k - D_X$ et $\deg_Y W_k \le 2(D_Y - 1)k - D_Y + 2$.

Cockle définit une deuxième suite $(V_k)_{k \ge 0}$ de polynômes de $\mathbb{Q}(X)[Y]$ de degrés au plus $D_Y - 1$ en Y, de sorte que, pour $k \ge 1$, $\alpha^{(k)} = W_k(x, \alpha)/P_Y(x, \alpha)^{2k-1} = V_k(x, \alpha)$, et par ailleurs, $V_0 = 1$.

5. Justifier que $P_Y$ est inversible modulo P et indiquer comment se calcule $V_1$.

6. Donner un procédé de calcul itératif des $V_k$.

7. En déduire un algorithme par algèbre linéaire sur $\mathbb{Q}(X)$ pour calculer une équation différentielle linéaire d'ordre minimal annulant toute solution $\alpha(x)$ de $P(x, \alpha(x)) = 0$.

8. Soit $r$ l'ordre de la sortie de cet algorithme. Donner une borne simple sur cet ordre, valable pour tout P.

On s'intéresse à la complexité de cette approche en nombre d'opérations dans $\mathbb{Q}$ et on commence par donner des bornes sur les degrés des résultats intermédiaires. Tout polynôme $Q$ de $\mathbb{Q}(X)[Y]$ peut s'écrire sous la forme $q(X)^{-1} \tilde{Q}(X, Y)$ pour $\tilde{Q}$ dans $\mathbb{Q}[X, Y]$. On appellera degré de $Q$ en $X$ le maximum des degrés en $X$ de $q$ et $\tilde{Q}$. On note $p(X)$ le coefficient dominant de P.

On admettra l'existence de polynômes $A$ et $B$ de $\mathbb{Q}[X, Y]$ tels que

$$ \mathrm{Res}_Y(P, P_Y) = AP + BP_Y, $$

et tels que les degrés en $Y$ de $A$ et $B$ sont dans $O(D_Y)$ et les degrés en $X$ sont dans $O(D_X D_Y)$.

9. Pour un polynôme $Q(X, Y)$ de $\mathbb{Q}[X, Y]$, de degrés respectifs $\delta_X$ et $\delta_Y$ en $X$ et $Y$, on considère sa division euclidienne par $P$ sous la forme $p^{\delta_Y - D_Y} Q = UP + V$, pour $U$ et $V$ dans $\mathbb{Q}(X)[Y]$, avec $V$ de degré en $Y$ inférieur à $\delta_Y$. Expliquer que $U$ et $V$ sont en réalité des polynômes de $\mathbb{Q}[X, Y]$. Montrer que le reste $V$ vérifie

$$ \deg_X V \le \delta_X + (\delta_Y - D_Y)D_X. $$

10. Pour un polynôme $Q(X, Y)$ de $\mathbb{Q}(X)[Y]$, de degrés respectifs $\delta_X$ et $\delta_Y$ en $X$ et $Y$, expliciter une borne sur le degré en $X$ du reste de $Q$ modulo $P$.
11. Déduire du calcul des $V_k$ que le degré en X de $V_k$ est dans $O(kD_XD_Y)$ pour tout $k \ge 1$.

On passe maintenant à l'étude de complexité proprement dite. On pourra se contenter de donner des bornes sous la forme de $\tilde{O}()$ de quantités polynomiales en $D_X, D_Y$ et $k$.

12. Donner en la justifiant la complexité du calcul de $V_{k+1}$ à partir de $V_k$.

13. Décrire les systèmes linéaires considérés à la question 7 : quelles sont leurs tailles et les degrés de leurs coefficients ? Donner et justifier la complexité de leur résolution.

14. Conclure en donnant une borne de complexité pour l'algorithme de Cockle.
Quelle est la taille arithmétique totale de sa sortie ?

Par conception, l'algorithme de Cockle recherche une équation d'ordre minimal. En relâchant cette contrainte sur l'ordre, on peut grandement abaisser la taille arithmétique de la sortie.

*Approche par télescopage créatif.* On note $F = YP_Y/P$ et on admet la formule suivante, qui voit $\alpha$ comme un résidu :

$$ \alpha(x) = \frac{1}{2i\pi} \oint F(x, y) dy $$

pour un contour d'intégration qui tourne autour d'$\alpha(x)$ sans contenir aucun autre zéro de $P(x, Y)$.

On rappelle que le résidu d'une fraction rationnelle $S(Y)$ en un de ses pôles $y$ d'ordre $\rho$ est le coefficient $c_{-1}$ de $1/(Y - y)$ dans le développement

$$ S(Y) = \frac{c_{-\rho}}{(Y-y)^{\rho}} + \cdots + \frac{c_{-1}}{Y-y} + \sum_{n \ge 0} c_n (Y-y)^n. $$

On considère l'algèbre de Ore $\mathbb{Q}(X, Y)(\partial_X, \partial_Y; \text{id}, \text{id}, d/dX, d/dY)$ que l'on fait agir sur les fractions rationnelles. Soit

$$ \Lambda(X, Y, \partial_X, \partial_Y) = A(X, \partial_X) + \partial_Y B(X, Y, \partial_X, \partial_Y) $$

un polynôme tordu.

1. Que vaut le résidu de $\partial_Y(S)$ en l'un quelconque de pôles $y$ de $S$ ?

2. Si $\Lambda$ annule une fraction rationnelle $S$, montrer que $\Lambda$ annule tout résidu de $S$ en l'un quelconque de ses pôles $y$.

On veut maintenant construire un polynôme tordu $\Lambda$ annulant $F$ par recombinaison linéaire.

3. Montrer que les fractions rationnelles

$$ F_{i,j,k} = X^i \partial_X^j \partial_Y^k (F), \quad 0 \le i \le N, 0 \le j+k \le M $$
s'écrivent comme combinaisons linéaires sur $\mathbb{Q}$ des éléments

$$E_{i,j} = \frac{X^i Y^j}{p^{M+1}}, \quad 0 \le i \le N + D_X (M+1), \ 0 \le j \le D_Y (M+1).$$

4. Pour des entiers N et M fixés, combien y a-t-il de $F_{i,j,k}$ et combien y a-t-il de $E_{i,j}$ ?

5. Fixer $N = 3D_X D_Y - 1$ et $M = 6D_Y - 1$ et montrer l'existence de $\Lambda$ non nul qui annule F.

On s'intéresse maintenant à la complexité du calcul de $\Lambda$.

6. Décrire un calcul de l'ensemble des $F_{i,j,k}$ exprimés en termes des $E_{i,j}$ et en donner la complexité.

7. Indiquer comment en déduire $\Lambda$ et donner la complexité de cette étape.

8. Quelle est la complexité globale du calcul de $\Lambda$ ? Quelle est sa taille arithmétique totale ?

Dans les bons cas, on trouve $\Lambda \neq 0$ qui annule $\alpha$ ; quand $\Lambda$ est nul, on peut montrer l'existence d'un autre annulateur de $\alpha$ dont les degrés ne sont pas plus que le double de ceux de $\Lambda$. ■

**Exercice 33.22 — Transporteur de deux idéaux.** Soit $\mathbb{K}$ un corps. Soient $I$ et $J$ deux idéaux de $R := \mathbb{K}[x_1, \dots, x_n]$. On définit le *transporteur* de $J$ dans $I$, noté $(I:J)$, comme $(I:J) := \{f \in R \mid fJ \subseteq I\}$.

1. Montrer que $(I:J)$ est un idéal.

2. Montrer que pour tout idéal $K$ de $R$ l'inclusion $KJ \subseteq I$ est équivalente à $K \subseteq (I:J)$.

3. Montrer que si $J \subseteq I$ alors $(I:J) = R$.

4. Montrer que $(I:R) = I$.

5. Soient $J_1$ et $J_2$ deux idéaux de $R$. Montrer que $(I: (J_1 + J_2)) = (I:J_1) \cap (I:J_2)$.

6. Montrer que $(I:(r)) = \frac{1}{r}(I \cap (r))$, où $\frac{1}{r}(I \cap (r))$ représente $\{\frac{f}{r} \mid f \in I \cap (r)\}$.

7. Proposer un algorithme, utilisant un calcul de base standard, pour calculer $I \cap J$ lorsque $I$ et $J$ sont donnés par un ensemble de polynômes générateurs $I = (f_1, \dots, f_s)$ et $J = (g_1, \dots, g_r)$. On pourra, par exemple, considérer l'idéal $K := (tf_1, \dots, tf_s, (1-t)g_1, \dots, (1-t)g_r)$ de $\mathbb{K}[x_1, \dots, x_s, t]$, où $t$ est une nouvelle variable.

8. Lorsque $I$ est donné par un ensemble de polynômes générateurs $I = (f_1, \dots, f_s)$, en déduire un algorithme pour calculer un ensemble de polynômes générateurs de $(I:(r))$.

9. Supposons que $I$ et $J$ sont explicitement donnés par des polynômes générateurs $I = (f_1, \dots, f_s)$ et $J = (g_1, \dots, g_r)$. À partir des résultats précédents, proposer un algorithme pour calculer $(I:J)$.

10. Si $\mathbb{K}$ est algébriquement clos, et si $V$ et $W$ sont deux variétés affines de $A_{\mathbb{K}}^n$, alors montrer que $(I(V) : I(W)) = I(V \setminus W)$ (on rappelle que $I(V)$ représente l'ensemble des polynômes de $R$ qui s'annulent sur $V$). ■
**Exercice 33.23** On s'intéresse à la somme $F_n := \sum_{k=0}^{n} k \binom{n}{k}$, pour laquelle on veut trouver une forme explicite. On pose $f_{n,k} := k \binom{n}{k}$.

1. Calculer $f_{n+1,k}$, $f_{n,k+1}$ et $f_{n+1,k+1}$.

2. Montrer que la combinaison linéaire

$$Af_{n,k} + Bf_{n+1,k} + C f_{n,k+1} + Df_{n+1,k+1}$$

s'annule si et seulement si un certain polynôme s'annule.

3. Déterminer des constantes A, B, C et D qui annulent ce polynôme.

4. En déduire, par télescopage créatif qu'il conviendra de justifier, que la somme vérifie la récurrence

$$nF_{n+1} = 2(n + 1)F_n.$$

5. En déduire une forme explicite pour $F_n$.

6. Proposer une méthode de sommation pour des suites hypergéométriques qui généralise cet exemple. On tâchera de fournir une formule explicite pour le télescopage créatif.

■

**Exercice 33.24** On s'intéresse à la somme $F_n := \sum_{k=0}^{n} \binom{n}{2k} \binom{2k}{k} \frac{1}{4^k}$, pour laquelle on souhaite vérifier par l'algorithme de Zeilberger qu'elle vaut $\frac{1}{2^{n-1}} \binom{2n-1}{n-1}$. On pourra suivre les indications données.

1. Représenter $f_{n,k} := \binom{n}{2k} \binom{2k}{k} \frac{1}{4^k}$ à l'aide de factorielles et calculer $f_{n+1,k}$ et $f_{n,k+1}$.

2. Passer directement à l'étape de l'algorithme de Zeilberger qui recherche une récurrence en $n$ d'ordre 1. Écrire explicitement la récurrence qui relie une combinaison linéaire des décalées en $n$ de $f$ et une différence finie en $k$ du terme $R(n,k)f_{n,k}$. Quelles sont les inconnues de ce problème? Dans quels ensembles cherche-t-on les solutions?

Dans ce qui suit, on ne notera plus la dépendance de $R$ en $n$ et on écrira simplement $R(k)$, $R(k+1)$, etc.

3. Justifier que le seul dénominateur possible de $R$ est $n - 2k + 1$. Écrire $R$ sous la forme $S(k)/(n - 2k + 1)$ pour un polynôme $S$ en $k$ (à coefficient des fractions rationnelles en $n$) et remplacer dans l'équation.

4. On se restreint momentanément à l'équation homogène associée, c'est-à-dire au membre qui fait apparaître $S$. Remplacer $S$ par un polynôme unitaire de degré $\alpha$ en $k$ et développer juste suffisamment pour justifier que l'équation homogène ne peut avoir de solution polynomiale.

5. En déduire que le degré des solutions polynomiales de l'équation complète est 2.

6. Poser $S(k) = Ak^2 + Bk + C$. Relier d'abord $\eta$ et $A$.
7. Spécialiser en $k = -1$ pour obtenir une expression très simple pour C.

8. Spécialiser en $k = 0$ pour relier A et B.

9. Spécialiser en $k = (n+1)/2$ pour obtenir une autre relation entre A et B.

10. Conclure sur les valeurs de A, B, C et $\eta$.

11. En déduire que la somme $F_n$ vérifie $(n+1)F_{n+1} = (2n+1)F_n$.

12. Vérifier que la forme explicite annoncée est solution et prouver qu'elle est bien formée explicite de la somme des $f_{n,k}$.

■

**Exercice 33.25 — Composition itérée de séries formelles.** Soit F une série de la forme $F(X) = f_1X + f_2X^2 + \dots$ à coefficients dans un corps $\mathbb{K}$. En notant $F^{[0]}(X) = X$, on définit la $q$-ième itérée de F par

$$F^{[q]}(X) = F^{[q-1]}(F(X)). \qquad (E)$$

L'objectif de cet exercice est d'étudier la complexité $C_q(N)$ du calcul des N premiers termes de cette série pour N grand en nombre d'opérations dans $\mathbb{K}$. On note $M(N)$ une borne sur le nombre d'opérations dans $\mathbb{K}$ nécessaires pour calculer le produit de deux polynômes de degré N dans $\mathbb{K}[X]$. On fait sur M les hypothèses habituelles de régularité. On note également $C(N)$ une borne sur le nombre d'opérations dans $\mathbb{K}$ nécessaires pour calculer la composition $f(g(X))$ de deux séries tronquées à l'ordre N telles que $g(0) = 0$. On rappelle qu'aucun algorithme quasi-optimal n'est connu pour la composition et que la meilleure complexité connue est $C(N) = O(\sqrt{N \log NM(N)})$.

La notation $g(q, N) = O(f(q, N))$ pour des fonctions de $q$ et N voudra dire dans cet exercice qu'il existe un entier $N_0$ tel que pour tout $N > N_0$,

$$|g(q, N)| \le K|f(q, N)|,$$

la constante K ne dépendant ni de N, ni de $q$.

1. En n'utilisant que de l'algorithmique naïve, montrer que le calcul des N premiers termes de $F^{[q]}$ peut être effectué en $C_q(N) = O(qN^3)$ opérations dans $\mathbb{K}$.

2. En exploitant la composition rapide de séries, montrer que cette complexité peut être abaissée à $C_q(N) = O(q\sqrt{N \log NM(N)})$.

3. Décrire une idée simple permettant de réduire la dépendance en $q$ pour aboutir à $C_q(N) = O(\log q\sqrt{N \log NM(N)})$.

Le reste de l'exercice étudie un algorithme permettant d'abaisser encore cette complexité pour finir à la même complexité que la composition avec F, indépendamment de $q$. L'idée de départ est que dans le cas de la puissance, le calcul de $F(X)^q$ peut être réalisé efficacement sous la forme $\exp(q \log F(X))$. L'objectif est d'adapter cette technique à la composition.

On suppose maintenant que $f_1 \neq 0$ et que $f_1$ n'est pas une racine de l'unité.

On définit la série de Schroeder $S(X) = s_1X + s_2X^2 + \dots$ par

$$S(F(X)) = f_1 S(X), \quad s_1 = 1. \qquad (S)$$
4. Montrer que cette équation définit bien une série S(X), et que celle-ci est unique.

5. Montrer que pour tout entier $q$,

$$F^{[q]}(X) = S^{[-1]}(f_1^q S(X)),$$

où $S^{[-1]}$ est l'inverse de S pour la composition. En déduire une borne sur la complexité du calcul de $F^{[q]}$ une fois la série S connue à précision N.

6. Pour calculer S solution de (S), on va s'intéresser à la résolution d'une équation plus générale :

$$A(X)Y(F(X)) - B(X)Y(X) - C(X) = 0 \quad \mod X^k, \quad (E)$$

où A, B, C, F sont des séries données et Y est l'inconnue. L'approche est une technique de « diviser pour régner ». En posant

$$Y(X) = U(X) + X^n V(X),$$

où U est un polynôme de degré inférieur à $n$, montrer que U et V sont solutions d'équations du même type que (E). Expliciter les coefficients de ces équations.

7. Décrire un algorithme de calcul des N premiers coefficients de Y en nombre d'opérations $O(\sqrt{N} \log NM(N))$. En notant $a_0, b_0, c_0$ les termes constants des séries A, B, C, on supposera que $a_0 f_1^m \neq b_0$, pour $m = 1, 2, 3, \dots$, et que si $a_0 = b_0$, alors $c_0 = 0$.

8. Décrire enfin l'algorithme de calcul de $F^{[q]}$ dans la complexité annoncée.

9. À l'inverse, décrire un algorithme calculant une série G telle que $F = G^{[q]}$, dans la même complexité.

■

**Exercice 33.26 — Calcul du radical.** On rappelle que le radical d'un idéal I, noté $\sqrt{I}$, est défini par $\{f \mid \exists r \in \mathbb{N}, f^r \in I\}$. On rappelle aussi qu'un polynôme est dit sans carré si les multiplicités de ses facteurs irréductibles sont égales à un. Dans cet exercice K représente un corps de caractéristique zéro, et R est l'anneau des polynômes $K[X_1, \dots, X_n]$.

1. Si $n = 1$, et si I est un idéal de R engendré par $f_1, \dots, f_s$, décrire un algorithme pour calculer un ensemble de générateurs du radical de I.

2. Dans cette question nous supposons que, pour chaque $i \in \{1, \dots, n\}$, il existe $g_i \in I \cap K[X_i]$ sans carré, et souhaitons montrer que I est radical, en suivant les étapes suivantes :

a. Si $n = 1$ montrer que I est radical.

b. Si $h_1, \dots, h_m$ sont les facteurs irréductibles de $g_1$ alors montrer l'égalité $I = \bigcap_{j=1}^m (I + (h_j))$, en utilisant le fait qu'il existe des polynômes $v_1, \dots, v_m$ de $K[X_1]$ tels que $v_1 \frac{g_1}{h_1} + \dots + v_m \frac{g_m}{h_m} = 1$.

c. Montrer que si $I + (h_j)$ est radical pour tout $j \in \{1, \dots, m\}$, alors I est radical.

d. Soit $\mathcal{L}$ l'extension du corps $K$ définie par $K[X_1]/(h_1(X_1))$ et soit $\phi$ la projection $K[X_1, \dots, X_n] \to \mathcal{L}[X_2, \dots, X_n]$. Montrer que si $J := \phi(I + (h_1))$ est radical
alors $I + (h_1)$ est radical.

e. Finalement, en utilisant les questions précédentes, montrer par récurrence sur $n$ que $I$ est radical.

3. On rappelle que $I$ est dit de dimension affine zéro si la dimension de la $\mathbb{K}$-algèbre $R/I$ est finie. Nous supposons dans cette question que $I$ est un idéal de dimension affine zéro engendré par les polynômes $f_1, \dots, f_s$, et nous nous intéressons au calcul d'un ensemble de générateurs de son radical.

a. Montrer que pour tout $i \in \{1, \dots, n\}$, il existe un polynôme sans carré $g_i$ dans $\sqrt{I} \cap \mathbb{K}[X_i]$ et décrire un algorithme pour calculer de tels polynômes $g_i$.

b. Montrer que $\sqrt{I}$ est engendré par $f_1, \dots, f_s, g_1, \dots, g_n$.

■

**Exercice 33.27 — Terminaison de l'algorithm de Zeilbergersur la classe des termes proprement hypergéométriques.** Cet exercice montre la terminaison de l'algorithm de Zeilberger sur la classe des *termes proprement hypergéométriques*, qui sont des termes hypergéométriques de la forme

$$h_{n,k} = P(n,k) \zeta^n X_i^k \prod_{\ell=1}^{L} \Gamma(a_\ell n + b_\ell k + c_\ell)^{\epsilon_\ell}, \quad (33.4)$$

où, pour un corps $\mathbb{K}$ inclus dans $\mathbb{C}$, les $a_\ell$ et les $b_\ell$ sont dans $\mathbb{Z}$, les $\epsilon_\ell$ valent $\pm 1$, les $c_\ell$, $\zeta$ et $X_i$ sont dans $\mathbb{K}$, et $P$ est un polynôme dans $\mathbb{K}[n,k]$. On rappelle que la fonction gamma vérifie pour $s \in \mathbb{C} \setminus \mathbb{Z}^{-}$, $\Gamma(s+1) = s\Gamma(s)$, et pour tout $n \in \mathbb{N}$, $\Gamma(n+1) = n!$.

1. Rappeler comment l'existence d'une relation

$$\sum_{i=0}^{r} \sum_{j=0}^{s} f_{i,j}(n) h_{n+i,k+j} = 0 \quad (33.5)$$

pour $r, s \ge 0$ et des fractions rationnelles $f_{i,j} \in \mathbb{K}(n)$ non toutes nulles entraîne l'existence de fractions rationnelles $\theta_0, \dots, \theta_r \in \mathbb{K}(n)$ et $q \in \mathbb{K}(n,k)$, non toutes nulles, vérifiant la relation

$$\theta_r(n) h_{n+r,k} + \dots + \theta_0(n) h_{n,k} = q(n,k+1) h_{n,k+1} - q(n,k) h_{n,k}. \quad (33.6)$$

2. Donner un exemple de terme hypergéométrique qui ne peut pas s'exprimer comme terme proprement hypergéométrique.

3. Pour chaque $\ell$, borner en fonction de $r$ et $s$ la valeur absolue de l'entier $u$ intervenant dans les termes $\Gamma(a_\ell n + b_\ell k + c_\ell + u)$ apparaissant dans l'égalité (33.5) après prise en compte de la définition (33.4) et des décalages sur $n$ et $k$.

4. Montrer que, pour les entiers $u$ définis comme à la question précédente, les deux quotients

$$\frac{\Gamma(a_\ell n + b_\ell k + c_\ell + u)}{\Gamma(a_\ell n + b_\ell k + c_\ell - \sigma_\ell)} \quad \text{et} \quad \frac{\Gamma(a_\ell n + b_\ell k + c_\ell + \sigma_\ell)}{\Gamma(a_\ell n + b_\ell k + c_\ell + u)}$$
sont des polynômes dont on majorera le degré en fonction de la borne $σ_ℓ$ obtenue à la question précédente.

5. Construire un terme $H_{n,k}$ tel que chaque produit $H_{n,k}h_{n+i,k+j}$ pour $0 \le i \le r$ et $0 \le j \le s$ soit un polynôme de degré en $k$ au plus linéaire en $r$ et $s$.

6. En déduire que pour $i$ et $j$ comme à la question précédente

$$ \deg_k(H_{n,k}h_{n+i,k+j}) \le \deg_k(P) + Ar + Bs $$

pour des entiers $A$ et $B$ que l'on précisera.

7. En déduire une contrainte polynomiale sur $r$ et $s$ pour que l'équation (33.5) ait une solution non triviale $\{f_{i,j}\}_{0 \le i \le r, 0 \le j \le s}$ pour des $f_{i,j}$ dans $K(n)$.

8. En déduire que le choix

$$ r = B \text{ et } s = (A - 1)B + \deg_k(P) + 1 $$

fournit toujours une solution à l'équation (33.5).

9. Décrire à partir de l'analyse précédente un algorithme prenant en entrée un terme proprement hypergéométrique de la forme (33.4) et renvoyant une relation de la forme (33.6).

10. Expliciter (33.4) sur l'exemple $h_{n,k} = \binom{n+k}{k}^2 \binom{n}{k}^2$, puis calculer les grandeurs principales intervenant dans l'algorithmes : A, B, $r$, $s$, $H_{n,k}$. Décrire le système linéaire à résoudre : taille, degré des coefficients.

11. De nouveau sur le cas général, par quel algorithme spécialisé du cours suggérez-vous d'effectuer l'algèbre linéaire ? En admettant que cette étape est l'étape dominante du calcul, estimer la complexité de l'algorithmes, en fonction de A et B.

12. Ce qui précède ne justifie pas totalement la terminaison de l'algorithmes de Zeilberger, à cause de la possible annulation du membre gauche de (33.6). Pour achever la justification, on introduit l'algèbre de Ore

$$ S = K(n,k)\langle \partial_n, \partial_k; S_n, S_k, 0, 0 \rangle, $$

et on remplace (33.5) par le polynôme tordu

$$ Z = \sum_{i=0}^{r} \sum_{j=0}^{s} f_{i,j}(n) \partial_{n}^{i} \partial_{k}^{j}. $$

Montrer qu'il existe un entier $v$, un polynôme tordu $P$ non nul indépendant de $k$ et $\partial_k$, et un polynôme tordu général $Q$ tels que

$$ Z = (\partial_k - 1)^v (P(n, \partial_n) - (\partial_k - 1)Q(n, \partial_n, \partial_k)). $$
13. On introduit la factorielle descendante $k^s = k(k-1)...(k-s+1)$, où $s \in \mathbb{N}$. Montrer la commutation, pour $a \in \mathbb{K}$,

$$(k-a)^s (\partial_k - 1) = (\partial_k - 1)(k-a-1)^s - s(k-s-1)^{s-1}.$$

14. Calculer $k^s (\partial_k - 1)^s$ modulo $\partial_k - 1$ à gauche.

15. En déduire que l'existence d'une relation (33.6) non triviale implique l'existence d'un $P = \eta_r(n) \partial_n^r + \cdots + \eta_0(n)$ non nul de $S$ et d'une fraction rationnelle $Q \in \mathbb{K}(n, k)$ vérifiant

$$(P - (\partial_k - 1)Q) \cdot h = 0.$$

16. Conclure sur l'algorithm de Zeilberger : donner une classe de termes hypergéo-métriques sur laquelle il termine et indiquer des bornes sur l'ordre et le degré du télescopeur obtenu.

17. L'exemple $(\binom{n+k}{k})^2 (\binom{n}{k})^2$ a suggéré que l'algorithm sous-jacent à ce problème n'est (tel quel) pas efficace en pratique. Suggérez ce qui permet à l'algorithm de Zeilberger d'être plus efficace.

■

## Notes

L'Exercice 33.9 provient d'un article de van der Hoeven [Hoe02b] : il montre que le produit d'opérateurs différentiels de bidegrés $(n, n)$ en $(X, \theta)$ se ramène à un nombre constant de multiplications de matrices carrées de taille $n$. L'article plus récent de Bostan, Chyzak et Le Roux [BCL08] montre que ces deux problèmes sont équivalents du point de vue de la complexité. L'Exercice 33.1 est inspiré par un article de Alt [Alt79], qui montre que le coût $R(n)$ du calcul de la racine carrée d'une série tronquée à précision $n$ vérifie aussi $O(R(n)) = O(M(n))$. L'Exercice 33.10 est tiré d'un article de Bostan et Salvy [BS08]. L'Exercice 33.4 provient de résultats de Kung et Tong [KT77]. L'Exercice 33.25 est une adaptation d'un article de Brent et Traub [BT80]. L'Exercice 33.14 est extrait de travaux de Bostan, Chyzak, Li et Salvy [Bos12], l'Exercice 33.7 d'un article de Bostan, Flajolet, Salvy et Schost [Bos+06b]. La première question de l'Exercice 33.2 est tirée d'un article de Aho, Steiglitz et J. D. Ullman [ASU75], la seconde est implicite dans un papier de Bostan et Schost [BS05]. L'Exercice 33.11 est inspiré par une l'article de Keller-Gehrig [Kel85], l'Exercice 33.3 est provient d'un article de Bostan, Gaudry et Schost [BGS07].

## Bibliographie

Alt79 ALT, H. (1978/79). « Square rooting is as difficult as multiplication ». In : *Computing*, vol. 21, n°3, p. 221-232.

ASU75 AHO, A. V., K. STEIGLITZ et J. D. ULLMAN (1975). « Evaluating polynomials at fixed sets of points ». In : *SIAM Journal on Computing*, vol. 4, n°4, p. 533-539.
BCL08 BOSTAN, Alin, Frédéric CHYZAK et Nicolas LE ROUX (2008). « Products of ordinary differential operators by evaluation and interpolation ». In : *ISSAC'08 : International Symposium on Symbolic and Algebraic Computation*. Éd. par David J. JEFFREY. ACM Press, p. 23–30.

BGS07 BOSTAN, Alin, Pierrick GAUDRY et Éric SCHOST (2007). « Linear recurrences with polynomial coefficients and application to integer factorization and Cartier–Manin operator ». In : *SIAM Journal on Computing*, vol. 36, n°6, p. 1777–1806.

Bos+06b BOSTAN, Alin, Philippe FLAJOLET, Bruno SALVY et Éric SCHOST (2006). « Fast computation of special resultants ». In : *Journal of Symbolic Computation*, vol. 41, n°1, p. 1–29.

Bos+12 BOSTAN, Alin, Frédéric CHYZAK, Ziming LI et Bruno SALVY (2012). « Fast computation of common left multiples of linear ordinary differential operators ». In : *ISSAC 2012 : Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 99–106.

BS05 BOSTAN, Alin et Éric SCHOST (2005). « Polynomial evaluation and interpolation on special sets of points ». In : *Journal of Complexity*, vol. 21, n°4, p. 420–446.

BS08 BORWEIN, Jonathan M. et Bruno SALVY (2008). « A proof of a recurrence for Bessel moments ». In : *Experimental Mathematics*, vol. 17, n°2, p. 223–230.

BT80 BRENT, R. P. et J. F. TRAUB (1980). « On the complexity of composition and generalized composition of power series ». In : *SIAM Journal on Computing*, vol. 9, n°1, p. 54–66.

Hoe02b HOEVEN, Joris van der (2002). « FFT-like multiplication of linear differential operators ». In : *Journal of Symbolic Computation*, vol. 33, n°1, p. 123–127.

Kel85 KELLER-GEHRIG, Walter (1985). « Fast algorithms for the characteristic polynomial ». In : *Theoretical Computer Science*, vol. 36, n°2-3, p. 309–317.

KT77 KUNG, H. T. et D. M. TONG (1977). « Fast algorithms for partial fraction decomposition ». In : *SIAM Journal on Computing*, vol. 6, n°3, p. 582–593.
Bibliographie générale

Abe92 **ABEL**, Niels Henrik (1992). *Œuvres complètes. Tome II. Réimpression de la seconde édition (1881)*. Éditions Jacques Gabay. url : http://www.gallica.fr (cité page 266).

ABP95a **ABRAMOV**, Sergei A., **MANUEL BRONSTEIN** et **Marko PETKOVŠEK** (1995). « On Polynomial Solutions of Linear Operator Equations ». In : *Symbolic and Algebraic Computation*. Éd. par A. H. M. LEVELT. Proceedings of ISSAC'95, July 1995, Montreal, Canada. New York : ACM Press, p. 290–296 (cité page 310).

ABP95b — (1995). « On polynomial solutions of linear operator equations ». In : *ISSAC'95 : International Symposium on Symbolic and Algebraic Computation*. Éd. par A. H. M. LEVELT. New York : ACM Press, p. 290–296 (cité page 321).

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

Abr89 — (1989). « Rational solutions of linear differential and difference equations with polynomial coefficients ». In : *USSR Computational Mathematics and Mathematical Physics*, vol. 29, n°11, p. 1611–1620 (cité page 310).

Abr95 — (1995). « Rational solutions of linear difference and *q*-difference equations with polynomial coefficients ». In : *ISSAC'95 : International Symposium on Symbolic and Algebraic Computation*. Éd. par A. H. M. LEVELT. New York : ACM Press, p. 285–289 (cité page 310).

AHU74 **AHO**, Alfred V., **John E. HOPCROFT** et **Jeffrey D. ULLMAN** (1974). *The design and analysis of computer algorithms*. Addison-Wesley Publishing Co. (cité pages 12, 30).

Ajt98 **AJTAI**, Miklós (1998). « The shortest vector problem in $L^2$ is NP-hard for randomized reductions ». In : *Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing*. STOC '98. Extended abstract. New York, NY, USA : ACM, p. 10–19 (cité page 370).

AKS04 **AGRAWAL**, Manindra, **Neeraj KAYAL** et **Nitin SAXENA** (2004). « PRIMES is in P ». In : *Annals of Mathematics. Second Series*, vol. 160, n°2, p. 781–793 (cité page 92).
AL04 ABDELJAOUED, J. et H. LOMBARDI (2004). *Méthodes matricielles : introduction à la complexité algébrique*. Vol. 42. Mathématiques & Applications. Springer-Verlag ( cité pages 13, 180).

AL81 ALT, H. et J. van LEEUWEN (1981). « The complexity of basic complex operations ». In : *Computing. Archiv für Informatik und Numerik*, vol. 27, n°3, p. 205–215 ( cité page 180).

Alt79 ALT, H. (1978/79). « Square rooting is as difficult as multiplication ». In : *Computing*, vol. 21, n°3, p. 221–232 ( cité page 619).

Ant79 ANTONIOU, A. (1979). *Digital filters : analysis and design*. McGraw-Hill Book Co. ( cité page 231).

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 ( cité page 541).

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 ( cité page 541).

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 ( cité page 541).

Arr06 ARRONDO, Enrique (2006). « Another elementary proof of the Nullstellensatz ». In : *The American Mathematical Monthly*, vol. 113, n°2, p. 169–171 ( cité page 464).

AS92 ABRAMOWITZ, Milton et Irene A. STEGUN, éds. (1992). *Handbook of mathematical functions with formulas, graphs, and mathematical tables*. Réimpression de l’édition de 1972. Dover Publications Inc. ( cité page 266).

ASU75 AHO, A. V., K. STEIGLITZ et J. D. ULLMAN (1975). « Evaluating polynomials at fixed sets of points ». In : *SIAM Journal on Computing*, vol. 4, n°4, p. 533–539 ( cité pages 108, 619).

ASZ00 ABBOTT, John, Victor SHOUP et Paul ZIMMERMANN (2000). « Factorization in $\mathbb{Z}[x]$ : the searching phase ». In : *ISSAC’00 : International Symposium on Symbolic and Algebraic Computation*. St. Andrews, Scotland : ACM Press, p. 1–7 ( cité page 396).

BA80 BITMEAD, Robert R. et Brian D. O. ANDERSON (1980). « Asymptotically fast solution of Toeplitz and related systems of linear equations ». In : *Linear Algebra and its Applications*, vol. 34, p. 103–116 ( cité page 206).

Baj+93 BAJAJ, Chanderjit, John CANNY, Thomas GARRITY et Joe WARREN (1993). « Factoring rational polynomials over the complex numbers ». In : *SIAM Journal on Computing*, vol. 22, n°2, p. 318–331 ( cité page 413).

Bar99 BARKATOU, Moulay A. (1999). « On rational solutions of systems of linear differential equations ». In : *Journal of Symbolic Computation*, vol. 28, n°4-5. Differential algebra and differential equations, p. 547–567 ( cité page 588).

BCD16 BOSTAN, Alin, Gilles CHRISTOL et Philippe DUMAS (2016). « Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field ». In : *Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation*. ISSAC’16. ACM, p. 119–126 ( cité page 287).

BCL08 BOSTAN, Alin, Frédéric CHYZAK et Nicolas LE ROUX (2008). « Products of ordinary differential operators by evaluation and interpolation ». In : *ISSAC’08 : International Symposium on Symbolic and Algebraic Computation*. Éd. par David J. JEFFREY. ACM Press, p. 23–30 ( cité page 619).

BCP13 BOSTAN, Alin, Frédéric CHYZAK et Élie de PANAFIEU (2013). « Complexity estimates for two uncoupling algorithms ». In : *ISSAC 2013, Proceedings of the 38th Internatio-
nal Symposium on Symbolic and Algebraic Computation. ACM, New York, p. 85-92 (cité page 588).

BCS05 BOSTAN, Alin, Thomas CLUZEAU et Bruno SALVY (2005). « Fast algorithms for polynomial solutions of linear differential equations ». In : ISSAC'05 : International Symposium on Symbolic and Algebraic Computation. ACM Press, p. 45-52 (cité page 310).

BCS97 BÜRGISSE, Peter, Michael CLAUSEN et M. Amin SHOKROLLAHI (1997). Algebraic complexity theory. Vol. 315. Grundlehren der Mathematischen Wissenschaften. Springer-Verlag (cité pages 13, 180).

Bec+05 BECK, Matthias, Bruce C. BERNDT, O-Yeat CHAN et Alexandru ZAHARESCU (2005). « Determinations of analogues of Gauss sums and other trigonometric sums ». In : International Journal of Number Theory, vol. 1, n°3, p. 333-356 (cité page 30).

Bec92 BECKERMANN, Bernhard (1992). « A reliable method for computing M-Padé approximants on arbitrary staircases ». In : Journal of Computational and Applied Mathematics, vol. 40, n°1, p. 19-42 (cité page 154).

Bel+09 BELABAS, Karim, Mark van HOEIJ, Jürgen KLÜNERS et Allan STEEL (2009). « Factoring polynomials over global fields ». In : Journal de Théorie des Nombres de Bordeaux, vol. 21, n°1, p. 15-39 (cité pages 396, 413).

Bera BERNSTEIN, Daniel J. (2001). Multidigit multiplication for mathematicians. URL : http://cr.yp.to/papers.html (visible en 2001) (cité page 52).

Berb — (2001). Removing redundancy in high-precision Newton iteration. URL : http://cr.yp.to/fastnewton.html (visible en 2001) (cité page 78).

Berc — (2006). The transposition principle. URL : http://cr.yp.to/transposition.html (visible en 2006) (cité page 231).

Ber08 — (2008). « Fast multiplication and its applications ». In : Algorithmic number theory : lattices, number fields, curves and cryptography. Vol. 44. Publications of the Research Institute for Mathematical Sciences. Cambridge University Press, p. 325-384 (cité pages 78, 321).

Ber67 BERLEKAMP, E. R. (1967). « Factoring polynomials over finite fields ». In : Bell System Technical Journal, vol. 46, p. 1853-1859 (cité page 356).

Ber70 — (1970). « Factoring polynomials over large finite fields ». In : Mathematics of Computation, vol. 24, p. 713-735 (cité page 356).

Ber84 BERKOWITZ, Stuart J. (1984). « On computing the determinant in small parallel time using a small number of processors ». In : Information Processing Letters, vol. 18, p. 147-150 (cité page 181).

Ber98 BERNSTEIN, Daniel J. (1998). « Composing power series over a finite ring in essentially linear time ». In : Journal of Symbolic Computation, vol. 26, n°3, p. 339-341 (cité page 77).

Béz64 BÉZOUT, É. (1764). « Recherches sur le degré des équations résultantes de l'événouissement des inconnues ». In : Histoire de l'académie royale des sciences, p. 288-338 (cité page 135).

BFS15 BARDET, Magali, Jean-Charles FAUGÈRE et Bruno SALVY (2015). « On the complexity of the F₅ Gröbner basis algorithm ». In : Journal of Symbolic Computation, vol. 70, p. 49-70 (cité page 481).

BG96 BAKER Jr., George A. et Peter GRAVES-MORRIS (1996). Padé approximants. 2ᵉ éd. Vol. 59. Encyclopedia of Mathematics and its Applications. Cambridge University Press (cité page 153).

BGS07 BOSTAN, Alin, Pierrick GAUDRY et Éric SCHOST (2007). « Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin
operator ». In : *SIAM Journal on Computing*, vol. 36, n°6, p. 1777-1806 ( cité pages 286, 619).

BGS72 BEELER, Michael, R. William GOSPER et Richard SCHROEPPEL (1972). *HAKMEM*. Artificial Intelligence Memo No. 239. Massachusetts Institute of Technology ( cité page 321).

BGY80 BRENT, Richard P., Fred G. GUSTAVSON et David Y. Y. YUN (1980). « Fast solution of Toeplitz systems of equations and computation of Padé approximants ». In : *Journal of Algorithms*, vol. 1, n°3, p. 259-295 ( cité pages 135, 153, 206).

BH74 BUNCH, James R. et John E. HOPCROFT (1974). « Triangular factorization and inversion by fast matrix multiplication ». In : *Mathematics of Computation*, vol. 28, p. 231-236 ( cité page 180).

BHL11 BERTHOMIEU, Jérémy, Joris van der HOEVEN et Grégoire LECERF (2011). « Relaxed algorithms for p-adic numbers ». In : *Journal de Théorie des Nombres de Bordeaux*, vol. 23, n°3, p. 541-577 ( cité page 78).

BHS80 BENTLEY, Jon Louis, Dorothea HAKEN et James B. SAXE (1980). « A general method for solving divide-and-conquer recurrences ». In : *SIGACT News*, vol. 12, n°3, p. 36-44 ( cité page 30).

Bin+79 BINI, D., M. CAPOVANI, F. ROMANI et G. LOTTI (1979). « O(n².779⁹) complexity for n×n approximate matrix multiplication ». In : *Information Processing Letters*, vol. 8, n°5, p. 234-235 ( cité page 183).

Bin80 BINI, D. (1980). « Relations between exact and approximate bilinear algorithms. Applications ». In : *Calcolo*, vol. 17, n°1, p. 87-97 ( cité page 183).

BJS08 BOSTAN, Alin, Claude-Pierre JEANNEROD et Éric SCHOST (2008). « Solving structured linear systems with large displacement rank ». In : *Theoretical Computer Science*, vol. 407, n°1-3, p. 155-181 ( cité page 206).

BK78 BRENT, R. P. et H. T. KUNG (1978). « Fast algorithms for manipulating formal power series ». In : *Journal of the ACM*, vol. 25, n°4, p. 581-595 ( cité pages 77, 181, 247).

BKL91 BÜRGISSE, P., M. KARPINSKI et T. LICKTEIG (1991). « Some computational problems in linear algebra as hard as matrix multiplication ». In : *Computational Complexity*, vol. 1, n°2, p. 131-155 ( cité page 181).

BL00 BECKERMANN, Bernhard et George LABAHN (2000). « Fraction-free computation of matrix rational interpolants and matrix GCDs ». In : *SIAM Journal on Matrix Analysis and Applications*, vol. 22, n°1, p. 114-144 ( cité page 154).

BL04 BÜRGISSE, Peter et Martin LOTZ (2004). « Lower bounds on the bounded coefficient complexity of bilinear maps ». In : *Journal of the Association for Computing Machinery*, vol. 51, n°3, p. 464-482 ( cité page 53).

BL94 BECKERMANN, B. et G. LABAHN (1994). « A uniform approach for the fast computation of matrix-type Padé approximants ». In : *SIAM Journal on Matrix Analysis and Applications*, vol. 15, n°3, p. 804-823 ( cité page 154).

Blä01 BLÄSER, Markus (2001). « A 5/2n²-lower bound for the multiplicative complexity of n×n-matrix multiplication ». In : *STACS 2001 (Dresden)*. Vol. 2010. Lecture Notes in Computer Science. Springer-Verlag, p. 99-109 ( cité page 182).

Blä03 — (2003). « On the complexity of the multiplication of matrices of small formats ». In : *Journal of Complexity*, vol. 19, n°1, p. 43-60 ( cité page 182).

BLS03 BOSTAN, Alin, Grégoire LECERF et Éric SCHOST (2003). « Tellegen's principle into practice ». In : *ISSAC'03 : International Symposium on Symbolic and Algebraic Computation*. Éd. par J. R. SENDRA. ACM Press, p. 37-44 ( cité pages 107, 230, 231).

Blu68 BLUESTEIN, Leo I. (1968). « A linear filtering approach to the computation of the discrete Fourier transform ». In : *IEEE Northeast Electronics Research and Engineering Meeting*, vol. 10, p. 218-219 ( cité page 231).
Blu70 BLUESTEIN, L. I. (1970). « A linear filtering approach to the computation of the discrete Fourier transform ». In : *IEEE Trans. Electroacoustics*, vol. AU-18, p. 451-455 (cité page 107).

BM71 BORODIN, A. et I. MUNRO (1971). « Evaluating polynomials at many points ». In : *Information Processing Letters*, vol. 1, n°2, p. 66-68 (cité pages 107, 181).

BM74 BORODIN, A. et R. T. MOENCK (1974). « Fast modular transforms ». In : *Journal of Computer and System Sciences*, vol. 8, n°3, p. 366-386 (cité page 107).

BM97 BERNARDIN, Laurent et Michael B. MONAGAN (1997). « Efficient multivariate factorization over finite fields ». In : *Applied algebra, algebraic algorithms and error-correcting codes* (Toulouse, 1997). Vol. 1255. Lecture Notes in Computer Science. Springer-Verlag, p. 15-28 (cité page 412).

Boo72 BOOLE, George (1872). *A treatise on the calculus of finite differences*. 2nd. Macmillan (cité page 310).

Bor56 BORDEWIJK, J. L. (1956). « Inter-reciprocity applied to electrical networks ». In : *Applied Scientific Research, Section B*, vol. 6, p. 1-74 (cité page 231).

Bor85 BORWEIN, Peter B. (1985). « On the complexity of calculating factorials ». In : *Journal of Algorithms*, vol. 6, n°3, p. 376-380 (cité page 286).

Bos+04a BOSTAN, A., G. LECERF, B. SALVY, É. SCHOST et B. WIEBELT (2004). « Complexity issues in bivariate polynomial factorization ». In : *ISSAC'04 : International Symposium on Symbolic and Algebraic Computation*. New York : ACM Press, p. 42-49 (cité page 230).

Bos+04b BOSTAN, Alin, Grégoire LECERF, Bruno SALVY, Éric SCHOST et Bernd WIEBELT (2004). « Complexity issues in bivariate polynomial factorization ». In : *ISSAC'04 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 42-49 (cité page 413).

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 (cité pages 310, 558).

Bos+06b BOSTAN, Alin, Philippe FLAJOLET, Bruno SALVY et Éric SCHOST (2006). « Fast computation of special resultants ». In : *Journal of Symbolic Computation*, vol. 41, n°1, p. 1-29 (cité pages 77, 619).

Bos+07a BOSTAN, A., F. CHYZAK, F. OLLIVIER, B. SALVY, É. SCHOST et A. SEDOGLAVIC (2007). « Fast computation of power series solutions of systems of differential equations ». In : *SODA'07 : ACM-SIAM Symposium on Discrete Algorithms*. SIAM, p. 1012-1021 (cité page 247).

Bos+07b BOSTAN, Alin, Frédéric CHYZAK, Grégoire LECERF, Bruno SALVY et Éric SCHOST (2007). « Differential equations for algebraic functions ». In : *ISSAC'07 : International Symposium on Symbolic and Algebraic Computation*. Éd. par Dongming WANG. ACM Press, p. 25-32 (cité page 266).

Bos+12 BOSTAN, Alin, Frédéric CHYZAK, Ziming LI et Bruno SALVY (2012). « Fast computation of common left multiples of linear ordinary differential operators ». In : *ISSAC 2012 : Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 99-106 (cité page 619).

Bos03 BOSTAN, Alin (2003). « Algorithmique efficace pour des opérations de base en calcul formel ». Thèse de Doctorat. École polytechnique (cité page 267).

BP02 BLONDEL, Vincent D. et Natacha PORTIER (2002). « The presence of a zero in an integer linear recurrent sequence is NP-hard to decide ». In : *Linear Algebra and its Applications*, vol. 351/352. Fourth special issue on linear systems and control, p. 91-98 (cité page 91).
BP94a BINI, Dario et Victor Y. PAN (1994). *Polynomial and matrix computations. Vol. 1.* Progress in Theoretical Computer Science. Fundamental algorithms. Birkhäuser Boston, Inc., Boston, MA, (cité page 13).

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 (cité page 558).

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

Bre76 BRENT, Richard P. (1976). « Multiple-precision zero-finding methods and the complexity of elementary function evaluation ». In : *Analytic computational complexity*. Proceedings of a Symposium held at Carnegie-Mellon University, Pittsburgh, PA, 1975. Academic Press, p. 151–176 (cité pages 77, 322).

Bri74 BRIGHAM, E. Oran (1974). *The fast Fourier transform*. Prentice-Hall (cité page 52).

Bro71 BROWN, W. S. (1971). « On Euclid’s algorithm and the computation of polynomial greatest common divisors ». In : *SYMSAC’71 : ACM Symposium on Symbolic and Algebraic Manipulation*. Los Angeles, California, United States : ACM, p. 195–211 (cité page 135).

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 (cité page 558).

BS04 BOSTAN, A. et Éric SCHOST (2004). « On the complexities of multipoint evaluation and interpolation ». In : *Theoretical Computer Science*, vol. 329, n°1–3, p. 223–235 (cité page 231).

BS05 BOSTAN, Alin et Éric SCHOST (2005). « Polynomial evaluation and interpolation on special sets of points ». In : *Journal of Complexity*, vol. 21, n°4, p. 420–446 (cité pages 107, 108, 619).

BS08 BORWEIN, Jonathan M. et Bruno SALVY (2008). « A proof of a recurrence for Bessel moments ». In : *Experimental Mathematics*, vol. 17, n°2, p. 223–230 (cité page 619).

BS83 BAUR, W. et V. STRASSEN (1983). « The complexity of partial derivatives ». In : *Theoretical Computer Science*, vol. 22, p. 317–330 (cité pages 180, 232).

BSS03 BOSTAN, Alin, Bruno SALVY et Éric SCHOST (2003). « Fast algorithms for zero-dimensional polynomial systems using duality ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 14, n°4, p. 239–272 (cité page 464).

BSS08 — (2008). « Power series composition and change of basis ». In : *ISSAC’08 : International Symposium on Symbolic and Algebraic Computation*. Éd. par David J. JEFFREY. ACM Press, p. 269–276 (cité pages 77, 78, 231).

BT71 BROWN, W. S. et J. F. TRAUB (1971). « On Euclid’s algorithm and the theory of subresultants ». In : *Journal of the Association for Computing Machinery*, vol. 18, p. 505–514 (cité page 135).

BT80 BRENT, R. P. et J. F. TRAUB (1980). « On the complexity of composition and generalized composition of power series ». In : *SIAM Journal on Computing*, vol. 9, n°1, p. 54–66 (cité page 619).

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 (cité page 558).

BT88 BEN-OR, M. et P. TIWARI (1988). « A deterministic algorithm for sparse multivariate polynomial interpolation ». In : *STOC’88 : ACM Symposium on Theory of Computing*. ACM Press, p. 301–309 (cité pages 153, 231).
<table>
  <tr>
    <td>Buc65</td>
    <td>BUCHBERGER, Bruno (1965). « Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal ». Thèse de doctorat. Mathematical Institute, University of Innsbruck, Austria (cité page 444).</td>
  </tr>
  <tr>
    <td>BW93</td>
    <td>BECKER, Thomas et Volker WEISPFENNING (1993). Gröbner bases. A computational approach to commutative algebra. Vol. 141. Graduate Texts in Mathematics. Springer-Verlag New York (cité pages 13, 434, 444).</td>
  </tr>
  <tr>
    <td>BZ07</td>
    <td>BODRATO, Marco et Alberto ZANONI (2007). « Integer and polynomial multiplication : towards optimal Toom-Cook matrices ». In : ISSAC'07 : International Symposium on Symbolic and Algebraic Computation. Éd. par Dongming WANG. ACM Press, p. 17-24 (cité page 53).</td>
  </tr>
  <tr>
    <td>CA69</td>
    <td>COOK, S. A. et S. O. AANDERAA (1969). « On the minimum computation time of functions ». In : Transactions of the American Mathematical Society, vol. 142, p. 291-314 (cité page 53).</td>
  </tr>
  <tr>
    <td>Cam83</td>
    <td>CAMION, Paul (1983). « A deterministic algorithm for factorizing polynomials of Fq[X] ». In : Combinatorial mathematics (Marseille-Luminy, 1981). Vol. 75. North-Holland Math. Stud. North-Holland, Amsterdam, p. 149-157 (cité page 356).</td>
  </tr>
  <tr>
    <td>Car92</td>
    <td>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 (cité page 558).</td>
  </tr>
  <tr>
    <td>Car99</td>
    <td>CARDINAL, Jean-Paul (1999). « On a property of Cauchy-like matrices ». In : Comptes Rendus de l'Académie des Sciences. Série I. Mathématique, vol. 328, n°11, p. 1089-1093 (cité page 206).</td>
  </tr>
  <tr>
    <td>CC86</td>
    <td>CABAY, Stanley et Dong Koo CHOI (1986). « Algebraic computations of scaled Padé fractions ». In : SIAM Journal on Computing, vol. 15, n°1, p. 243-270 (cité page 153).</td>
  </tr>
  <tr>
    <td>CC88</td>
    <td>CHUDNOVSKY, D. V. et G. V. CHUDNOVSKY (1988). « Approximations and complex multiplication according to Ramanujan ». In : Proceedings of the Centenary Conference, University of Illinois at Urbana-Champaign, June 1-5, 1987. Éd. par G. E. ANDREWS, R. A. ASKEY, B. C. BERNDT, K. G. RAMANATHAN et R. A. RANKIN. Academic Press, p. 375-472 (cité pages 286, 322).</td>
  </tr>
  <tr>
    <td>CG00</td>
    <td>CHU, Eleanor et Alan GEORGE (2000). Inside the FFT black box. Serial and parallel fast Fourier transform algorithms. CRC Press (cité page 231).</td>
  </tr>
  <tr>
    <td>CH07</td>
    <td>CHUNG, Jaewook et M. Anwar HASAN (2007). « Asymmetric squaring formulae ». In : ARITH'07 : IEEE Symposium on Computer Arithmetic. IEEE, p. 113-122 (cité page 53).</td>
  </tr>
  <tr>
    <td>CH14</td>
    <td>COSTA, Edgar et David HARVEY (2014). « Faster deterministic integer factorization ». In : Mathematics of Computation, vol. 83, n°285, p. 339-345 (cité page 286).</td>
  </tr>
  <tr>
    <td>Cha91</td>
    <td>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 (cité page 558).</td>
  </tr>
  <tr>
    <td>Chè04</td>
    <td>CHÈZE, Guillaume (2004). « Des méthodes symboliques-numériques et exactes pour la factorisation absolue des polynômes en deux variables ». Thèse de doctorat. Université de Nice-Sophia Antipolis (France) (cité page 413).</td>
  </tr>
  <tr>
    <td>Che84</td>
    <td>CHENG, Unjeng (1984). « On the continued fraction and Berlekamp's algorithm ». In : IEEE Transactions on Information Theory, vol. 30, n°3, p. 541-544 (cité page 153).</td>
  </tr>
  <tr>
    <td>Chy00</td>
    <td>CHYZAK, Frédéric (2000). « An extension of Zeilberger's fast algorithm to general holonomic functions ». In : Discrete Mathematics, vol. 217, n°1-3, p. 115-134 (cité page 588).</td>
  </tr>
  <tr>
    <td>CK91</td>
    <td>CANTOR, D. G. et E. KALTOFEN (1991). « On fast multiplication of polynomials over arbitrary algebras ». In : Acta Informatica, vol. 28, n°7, p. 693-701 (cité page 53).</td>
  </tr>
</table>
CKM97 COLLART, S., M. KALKBRENER et D. MALL (1997). « Converting bases with the Gröbner walk ». In : *Journal of Symbolic Computation*, vol. 24, n°3-4, p. 465-469 (cité page 444).

CKO09 CENK, M., C. K. KOC et F. OZBUDAK (2009). « Polynomial multiplication over finite fields using field extensions and interpolation ». In : *ARITH'09 : IEEE Symposium on Computer Arithmetic*. IEEE Computer Society, p. 84-91 (cité page 54).

CKY89 CANNY, John F., Erich KALTOFEN et Lakshman YAGATI (1989). « Solving systems of non-linear polynomial equations faster ». In : *ISSAC'89 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 121-128 (cité pages 231, 232).

CL89 CABAY, S. et G. LABAHN (1989). « A fast, reliable algorithm for calculating Padé-Hermite forms ». In : *ISSAC'89 : International Symposium on Symbolic and Algebraic Computation*. Portland, Oregon, United States : ACM Press, p. 95-100 (cité page 154).

CLB92 CABAY, S., G. LABAHN et B. BECKERMANN (1992). « On the theory and computation of nonperfect Padé-Hermite approximants ». In : *Journal of Computational and Applied Mathematics*, vol. 39, n°3, p. 295-313 (cité page 154).

CLO96 COX, David, John LITTLE et Donal O'SHEA (1996). *Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra*. 2e éd. Undergraduate Texts in Mathematics. Springer-Verlag (cité pages 13, 434, 444, 480).

CMP87 CERLIENCO, L., M. MIGNOTTE et F. PIRAS (1987). « Suites récurrentes linéaires. Propriétés algébriques et arithmétiques ». In : *L'Enseignement Mathématique*. II, vol. 33, p. 67-108 (cité pages 91, 230).

Coh+05 COHN, H., R. KLEINBERG, B. SZEGEDY et C. UMANS (2005). « Group-theoretic algorithms for matrix multiplication ». In : *FOCS'05 : IEEE Conference on Foundations of Computer Science*. IEEE Computer Society, p. 379-388 (cité page 184).

Col66 COLLINS, G. E. (1966). « Polynomial remainder sequences and determinants ». In : *The American Mathematical Monthly*, vol. 73, p. 708-712 (cité page 135).

Col67 COLLINS, George E. (1967). « Subresultants and reduced polynomial remainder sequences ». In : *Journal of the Association for Computing Machinery*, vol. 14, p. 128-142 (cité page 135).

Col71 — (1971). « The calculation of multivariate polynomial resultants ». In : *Journal of the Association for Computing Machinery*, vol. 18, p. 515-532 (cité page 135).

Com70 COMTET, L. (1970). *Analyse combinatoire*. 2 volumes. Presses Universitaires de France (cité page 266).

Coo66 COOK, S. (1966). « On the minimum computation time of functions ». Thèse de doctorat. Harvard University (cité page 52).

Coo90 COOLEY, James W. (1990). « How the FFT gained acceptance ». In : *A history of scientific computing*. ACM Press Hist. Ser. P : ACM, p. 133-140 (cité page 52).

Cop94 COPPERSMITH, Don (1994). « Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm ». In : *Mathematics of Computation*, vol. 62, n°205, p. 333-350 (cité page 193).

Cor+09 CORMEN, Thomas H., Charles E. LEISERSON, Ronald L. RIVEST et Clifford STEIN (2009). *Introduction to algorithms*. Third. MIT Press, Cambridge, MA (cité pages 12, 30).

CPS08 CHEN, William Y. C., Peter PAULE et Husam L. SAAD (2008). « Converging to Gosper's algorithm ». In : *Advances in Applied Mathematics*, vol. 41, n°3, p. 351-364 (cité page 310).
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 (cité pages 558, 576).

CT65 COOLEY, James W. et John W. TUKEY (1965). « An algorithm for the machine calculation of complex Fourier series ». In : *Mathematics of Computation*, vol. 19, p. 297-301 (cité page 52).

CT93 — (1993). « On the origin and publication of the FFT paper ». In : *Current Contents*, vol. 33, n°51-52, p. 8-9 (cité page 52).

CU03 COHN, Henry et Christopher UMAN S (2003). « A group-theoretic approach to fast matrix multiplication ». In : *FOCS'03 : IEEE Conference on Foundations of Computer Science*. Washington, DC, USA : IEEE Computer Society, p. 438 (cité page 184).

CW90 COPPERSMITH, Don et Shmuel WINOGRAD (1990). « Matrix multiplication via arithmetic progressions ». In : *Journal of Symbolic Computation*, vol. 9, n°3, p. 251-280 (cité page 183).

CZ81 CANTOR, David G. et Hans ZASSENHAUS (1981). « A new algorithm for factoring polynomials over finite fields ». In : *Mathematics of Computation*, vol. 36, n°154, p. 587-592 (cité page 356).

Dan37 DANILEVSKII, A. M (1937). « The numerical solution of the secular equation ». In : *Matematicheski Sbornik*, vol. 44, n°2. (in Russian), p. 169-171 (cité page 181).

DD84a DELLA DORA, J. et C. DICRESCENZO (1984). « Approximants de Padé-Hermite. I. Théorie ». In : *Numerische Mathematik*, vol. 43, n°1, p. 23-39 (cité page 154).

DD84b — (1984). « Approximants de Padé-Hermite. II. Programmation ». In : *Numerische Mathematik*, vol. 43, n°1, p. 41-57 (cité page 154).

De+08 DE, A., P. P. KURUR, C. SAHA et R. SAPTHARISHI (2008). « Fast integer multiplication using modular arithmetic ». In : *STOC'08 : ACM Symposium on Theory of Computing*. Victoria, British Columbia, Canada : ACM, p. 499-506 (cité page 53).

Dem87 DEMAZURE, M. (1987). « Le théorème de complexité de Mayr et Meyer ». In : *Géométrie algébrique et applications, I (La Rábida, 1984)*. Vol. 22. Travaux en Cours. Paris : Hermann, p. 35-58 (cité page 481).

Dem97 DEMAZURE, Michel (1997). *Cours d'algèbre*. Nouvelle Bibliothèque Mathématique n°1. Cassini, Paris (cité page 53).

Der94 DERKSEN, Harm (1994). *An algorithm to compute generalized Padé-Hermite forms*. Report n°9403. Dept. of Math., Catholic University Nijmegen (cité page 153).

Dix82 DIXON, John D. (1982). « Exact solution of linear equations using p-adic expansions ». In : *Numerische Mathematik*, vol. 40, n°1, p. 137-141 (cité pages 153, 214).

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 (cité pages 500, 522, 523).

DL78 DEMILLO, Richard A. et Richard J. LIPTON (1978). « A probabilistic remark on algebraic program testing ». In : *Information Processing Letters*, vol. 7, n°4, p. 193-195 (cité page 193).

Dor87 DORNSTETTER, Jean-Louis (1987). « On the equivalence between Berlekamp's and Euclid's algorithms ». In : *IEEE Transactions on Information Theory*, vol. 33, n°3, p. 428-431 (cité page 153).

DPR61 DAVIS, Martin, Hilary PUTNAM et Julia ROBINSON (1961). « The decision problem for exponential diophantine equations ». In : *Annals of Mathematics. Second Series*, vol. 74, p. 425-436 (cité page 30).

DS00 DONGARRA, J. et F. SULLIVAN (2000). « Top ten algorithms ». In : *Computing in Science & Engineering*, vol. 2, n°1, p. 22-23 (cité page 52).
DS11 DRMOTA, Michael et Wojciech SZPANKOWSKI (2011). « A master theorem for discrete divide and conquer recurrences ». In : *SODA'11 : ACM-SIAM Symposium on Discrete Algorithms*. San Francisco, CA : SIAM, p. 342–361 (cité page 30).

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 (cité page 522).

DV90 DUHAMEL, P. et M. VETTERLI (1990). « Fast Fourier transforms : a tutorial review and a state of the art ». In : *Signal Processing. An Interdisciplinary Journal*, vol. 19, n°4, p. 259–299 (cité page 52).

Eis95 EISENBUD, David (1995). *Commutative algebra. With a view toward algebraic geometry*. Vol. 150. Graduate Texts in Mathematics. Springer-Verlag New York (cité pages 13, 434).

EKM96 ERLINGSSON, Úlfar, Erich KALTOFEN et David MUSSER (1996). « Generic Gram-Schmidt orthogonalization by exact division ». In : *Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation*. ISSAC'96. New York, NY, USA : ACM, p. 275–282 (cité page 370).

El 03 EL KAHOUI, M'hammed (2003). « An elementary approach to subresultants theory ». In : *Journal of Symbolic Computation*, vol. 35, n°3, p. 281–292 (cité page 135).

Erd32 ERDŐS, Paul (1932). « Beweis eines Satzes von Tschebyschef ». In : *Acta Litterarum ac Scientiarum, Szeged*, n°5, p. 194–198 (cité page 396).

Evd94 EVDOKIMOV, Sergei (1994). « Factorization of polynomials over finite fields in subexponential time under GRH ». In : *Algorithmic number theory (Ithaca, NY, 1994)*. Vol. 877. Lecture Notes in Computer Science. Springer-Verlag, p. 209–219 (cité page 356).

Eve+03 EVEREST, Graham, Alf van der POORTEN, Igor SHPARLINSKI et Thomas WARD (2003). *Recurrence sequences*. Vol. 104. Mathematical Surveys and Monographs. American Mathematical Society (cité page 91).

Fau+93 FAUGÈRE, J. C., P. GIANNI, D. LAZARD et T. MORA (1993). « Efficient computation of zero-dimensional Gröbner bases by change of ordering ». In : *Journal of Symbolic Computation*, vol. 16, n°4, p. 329–344 (cité pages 444, 576).

Fau02 FAUGÈRE, Jean-Charles (2002). « A new efficient algorithm for computing Gröbner bases without reduction to zero (F5) ». In : *Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation*. ISSAC'02. New York, NY, USA : ACM, p. 75–83 (cité pages 445, 481).

Fau99 — (1999). « A new efficient algorithm for computing Gröbner bases (F4) ». In : *Journal of Pure and Applied Algebra*, vol. 139, n°1–3, p. 61–88 (cité page 445).

Fet71 FETTWEIS, A. (1971). « A general theorem for signal-flow networks, with applications ». In : *Archiv für Elektronik und Übertragungstechnik*, vol. 25, n°12, p. 557–561 (cité page 231).

FGP01 FLAJOLET, P., X. GOURDON et D. PANARIO (2001). « The complete analysis of a polynomial factorization algorithm over finite fields ». In : *Journal of Algorithms*, vol. 40, n°1, p. 37–81 (cité page 356).

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 (cité page 522).

Fid72a FIDUCCIA, C. M. (1972). « On obtaining upper bounds on the complexity of matrix multiplication ». In : *Complexity of computer computations*. IBM Thomas J. Watson Research Center, Yorktown Heights, New York : Plenum, p. 31–40 (cité page 231).
Fid72b — (1972). « Polynomial evaluation via the division algorithm : the fast Fourier transform revisited. » In : STOC'72 : ACM Symposium on Theory of Computing, p. 88–93 (cité page 107).

Fid72c FIDUCCIA, Charles M. (1972). « On obtaining upper bounds on the complexity of matrix multiplication ». In : Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972). New York : Plenum, p. 31–40 (cité page 180).

Fid73 FIDUCCIA, C. M. (1973). « On the algebraic complexity of matrix multiplication ». Thèse de doctorat. Brown Univ., Providence, RI, Center Comput. Inform. Sci., Div. Engin. (cité page 231).

Fid85 — (1985). « An efficient formula for linear recurrences ». In : SIAM Journal on Computing, vol. 14, n°1, p. 106–112 (cité page 92).

Fis74 FISCHER, Patrick C. (1974). « Further schemes for combining matrix algorithms ». In : Automata, languages and programming. Vol. 14. Lecture Notes in Computer Science. Springer-Verlag, p. 428–436 (cité page 182).

Fj05 FRIGO, M. et S. G. JOHNSON (2005). « The design and implementation of FFTW3 ». In : Proceedings of the IEEE, vol. 93, n°2, p. 216–231 (cité pages 52, 53).

FP74 FISCHER, P. C. et R. L. PROBERT (1974). « Efficient procedures for using matrix algorithms ». In : Automata, languages and programming. Vol. 14. Lecture Notes in Computer Science. Springer-Verlag, p. 413–427 (cité page 182).

FS56 FRÖHLICH, A. et J. C. SHEPHERDSON (1956). « Effective procedures in field theory ». In : Philosophical Transactions of the Royal Society A, vol. 248, p. 407–432 (cité page 342).

FS82 FLAJOLET, Philippe et Jean-Marc STEYAERT (1982). « A branching process arising in dynamic hashing, trie searching and polynomial factorization ». In : Automata, Languages and Programming. Éd. par M. NIELSEN et E. SCHMIDT. Vol. 140. Lecture Notes in Computer Science. Springer-Verlag, p. 239–251 (cité page 356).

FS97 FLAJOLET, Philippe et Bruno SALVY (1997). « The SIGSAM challenges : symbolic asymptotics in practice ». In : ACM SIGSAM Bulletin, vol. 31, n°4, p. 36–47 (cité page 286).

Für07 FÜRER, Martin (2007). « Faster integer multiplication ». In : STOC'07 : ACM Symposium on Theory of Computing. New York : ACM, p. 57–66 (cité page 53).

Für09 — (2009). « Faster integer multiplication ». In : SIAM Journal on Computing, vol. 39, n°3, p. 979–1005 (cité page 53).

Gao03 GAO, Shuhong (2003). « Factoring multivariate polynomials via partial differential equations ». In : Mathematics of Computation, vol. 72, n°242, p. 801–822 (cité pages 412, 413).

Gar59 GARNER, Harvey L. (1959). « The residue number system ». In : IRE-AIEE-ACM'59 Western joint computer conference. San Francisco, California : ACM, p. 146–153 (cité page 107).

Gat06 GATHEN, Joachim von zur (2006). « Who was who in polynomial factorization ». In : ISSAC'06 : International Symposium on Symbolic and Algebraic Computation. ACM Press, p. 1–2 (cité pages 342, 412).

Gat84 — (1984). « Hensel and Newton methods in valuation rings ». In : Mathematics of Computation, vol. 42, n°166, p. 637–661 (cité pages 342, 412).

Gat85 GATHEN, J. von zur (1985). « Irreducibility of multivariate polynomials ». In : Journal of Computer and System Sciences, vol. 31, n°2. Special issue : Twenty-fourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983), p. 225–264 (cité page 413).
Gat87 GATHEN, Joachim von zur (1987). « Factoring polynomials and primitive elements for special primes ». In: *Theoretical Computer Science*, vol. 52, n°1-2, p. 77-89 (cité page 356).

Gau66 GAUSS, Carl Friedrich (1966). *Disquisitiones arithmeticae*. Translated into English by Arthur A. Clarke, S. J. Yale University Press (cité page 107).

GCL92 GEDDES, Keith O., Stephen R. CZAPOR et George LABAHN (1992). *Algorithms for computer algebra*. Kluwer Academic Publishers (cité pages 13, 135).

Ger01 GERHARD, Jürgen (2001). « Fast Modular Algorithms for Squarefree Factorization and Hermite Integration ». In: *Applicable Algebra in Engineering, Communication and Computing*, vol. 11, n°3, p. 203-226 (cité page 396).

GG03 GATHEN, Joachim von zur et Jürgen GERHARD (2003). *Modern computer algebra*. 2ᵉ éd. Cambridge University Press (cité pages 13, 53, 135, 342, 356, 370, 413, 481).

GG13 — (2013). *Modern computer algebra*. 3ᵉ éd. Cambridge University Press (cité page 136).

GG99 — (1999). *Modern computer algebra*. Cambridge University Press (cité page 231).

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 (cité pages 500, 522).

GHL15a GRENET, Bruno, Joris van der HOEVEN et Grégoire LECERF (2015). « Deterministic root finding over finite fields using Graeffe transforms ». In: *Applicable Algebra in Engineering, Communication and Computing*, vol. 27, n°3, p. 237-257 (cité page 356).

GHL15b — (2015). « Randomized root finding over finite FFT-fields using tangent Graeffe transforms ». In: *ISSAC'15 : International Symposium on Symbolic and Algebraic Computation*. Éd. par D. ROBERTZ. ACM Press, p. 197-204 (cité page 356).

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 (cité page 522).

Gie01 GIESBRECHT, Mark (2001). « Fast computation of the Smith form of a sparse integer matrix ». In: *Computational Complexity*, vol. 10, n°1, p. 41-69 (cité page 193).

Gie95 — (1995). « Nearly optimal algorithms for canonical matrix forms ». In: *SIAM Journal on Computing*, vol. 24, n°5, p. 948-969 (cité page 181).

Gio+91 GIOVINI, Alessandro, Teo MORA, Gianfranco NIESI, Lorenzo ROBBIANO et Carlo TRAVERSO (1991). « "One sugar cube, please" or selection strategies in the Buchberger algorithm ». In: *Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation*. ISSAC'91. New York, NY, USA : ACM, p. 49-54 (cité page 444).

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 (cité page 500).

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 (cité page 522).

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 (cité page 522).
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 (cité page 522).

Giu84
GIUSTI, M. (1984). « Some effectivity problems in polynomial ideal theory ». In : *EUROSAM 84 : International Symposium on Symbolic and Algebraic Computation* Cambridge, England, July 9-11, 1984. Éd. par John Fitch. Berlin, Heidelberg : Springer Berlin Heidelberg, p. 159-171 (cité page 481).

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 (cité page 500).

GJV03
GIORGI, Pascal, Claude-Pierre Jeannerod et Gilles Villard (2003). « On the complexity of polynomial matrix computations ». In : *ISSAC'03 : International Symposium on Symbolic and Algebraic Computation*. Éd. par J. R. Sendra. New York : ACM Press, p. 135-142 (cité pages 154, 214).

GK85a
GATHEN, J. von zur et E. KALTOFEN (1985). « Factorization of multivariate polynomials over finite fields ». In : *Mathematics of Computation*, vol. 45, n°171, p. 251-261 (cité page 412).

GK85b
GATHEN, Joachim von zur et Erich KALTOFEN (1985). « Factoring sparse multivariate polynomials ». In : *Journal of Computer and System Sciences*, vol. 31, n°2. Special issue : Twenty-fourth annual symposium on the foundations of computer science (Tucson, Ariz., 1983), p. 265-287 (cité page 413).

GL02
GAO, Shuhong et Alan G. B. LAUDER (2002). « Hensel lifting and bivariate polynomial factorisation over finite fields ». In : *Mathematics of Computation*, vol. 71, n°240, p. 1663-1676 (cité page 412).

GL03
GATHEN, Joachim von zur et Thomas LÜCKING (2003). « Subresultants revisited ». In : *Theoretical Computer Science*, vol. 297, n°1-3, p. 199-239 (cité page 135).

GLM91
GILBERT, J.-C., G. LE VET et J. MASSE (1991). *La différentiation automatique de fonctions représentées par des programmes*. Rapp. tech. RR INRIA 1557 (cité page 231).

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 (cité page 522).

GLS98
GIESBRECHT, M., A. LOBO et B. D. SAUNDERS (1998). « Certifying inconsistency of sparse linear systems ». In : *ISSAC'98 : International Symposium on Symbolic and Algebraic Computation*. New York : ACM Press, p. 113-119 (cité page 193).

GM89
GIANNI, Patrizia et Teo MORA (1989). « Algebraic solution of systems of polynomial equations using Groebner bases ». In : *Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. 5th International Conference, AAECC-5, Menorca, Spain, June 15-19, 1987. Proceedings*. Éd. par Llorenç HUGUET et Alain POLI. Vol. 356. Lecture Notes in Computer Science. Springer-Verlag Berlin Heidelberg, p. 247-257 (cité page 464).

GO94
GOHBERG, I. et V. OLSHEVSKY (1994). « Complexity of multiplication with vectors for structured matrices ». In : *Linear Algebra and its Applications*, vol. 202, p. 163-192 (cité page 206).

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 (cité page 541).

Gra+82
GRAGG, William B., Fred G. GUSTAVSON, Daniel D. WARNER et David Y. Y. YUN (1982). « On fast computation of superdiagonal Padé fractions ». In : *Mathematical Programming Study*, n°18. Algorithms and theory in filtering and control (Lexington, Ky., 1980), p. 39-42 (cité page 153).
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 (cité page 558).

GS66 GENTLEMAN, W. M. et G. SANDE (1966). « Fast Fourier transforms : for fun and profit ». In : *AFIPS'66*. San Francisco, California : ACM, p. 563-578 (cité page 52).

GS72 GOHBERG, I. C. et A. A. SEMENCUL (1972). « On the inversion of finite Toeplitz matrices and their continuous analogues (in Russian) ». In : *Matematicheskie Issue-dovaniya*, vol. 7, n°2, p. 201-223 (cité page 206).

GT96 GIANNI, P. et B. TRAGER (1996). « Square-free algorithms in positive characteristic ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 7, n°1, p. 1-14 (cité page 342).

Gup+12 GUPTA, Somit, Soumojit SARKAR, Arne STORJOHANN et Johnny VALERIOTE (2012). « Triangular x-basis decompositions and derandomization of linear algebra algorithms over K[x] ». In : *Journal of Symbolic Computation*, vol. 47, n°4, p. 422-453 (cité page 214).

GV13 GOLUB, Gene H. et Charles F. VAN LOAN (2013). *Matrix computations*. Fourth. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD (cité page 206).

GY79 GUSTAVSON, Fred G. et David Y. Y. YUN (1979). « Fast algorithms for rational Hermite approximation and solution of Toeplitz systems ». In : *IEEE Transactions on Circuits and Systems*, vol. 26, n°9, p. 750-755 (cité pages 135, 153, 206).

Har10 HARVEY, David (2010). « Faster exponentials of power series ». URL : https://arxiv.org/abs/0911.3110 (cité page 78).

Har11 — (2011). « Faster algorithms for the square root and reciprocal of power series ». In : *Mathematics of Computation*, vol. 80, p. 387-394 (cité page 78).

Har62 HARLEY, Rev. Robert (1862). « On the theory of the transcendental solution of algebraic equations ». In : *Quarterly Journal of Pure and Applied Mathematics*, vol. 5, p. 337-360 (cité page 266).

Har72 HARTER, Richard (1972). « The optimality of Winograd's formula ». In : *Communications of the ACM*, vol. 15, n°5, p. 352 (cité page 181).

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 (cité page 522).

Her73a HERMITE, C. (1873). « Extrait d'une lettre de Monsieur Ch. Hermite à Monsieur Paul Gordan ». In : *Journal für die Reine und Angewandte Mathematik*, vol. 78, p. 303-311 (cité page 154).

Her73b — (1873). « Sur la fonction exponentielle ». In : *Comptes-rendus de l'Académie des sciences de Paris*, vol. 77, p. 18-24 (cité page 154).

Her93 — (1893). « Sur la généralisation des fractions continues algébriques ». In : *Annali di Matematica pura ed applicata*, vol. 21, n°2, p. 289-308 (cité page 154).

HH71 HEINDEL, L. E. et E. HOROWITZ (1971). « On decreasing the computing time for modular arithmetic ». In : *12th symposium on switching and automata theory*. IEEE, p. 126-128 (cité page 108).

HHL14 HARVEY, David, Joris van der HOEVEN et Grégoire LECERF (2014). « Faster polynomial multiplication over finite fields ». http://arxiv.org/abs/1407.3361 (cité page 53).

HHL16 — (2016). « Even faster integer multiplication ». In : *Journal of Complexity*, vol. 36, p. 1-30 (cité page 53).
HHN11 HART, William, Mark van HOEIJ et Andrew NOVOCIN (2011). « Practical polynomial factoring in polynomial time ». In : *ISSAC'11 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 163–170 (cité page 397).

Hil92 HILBERT, David (1892). « Über die Irreducibilität ganzer rationaler Functionen mit ganzzahligen Coefficienten ». In : *Journal für die reine und angewandte Mathematik*, vol. 110 (cité page 413).

Hir64 HIRONAKA, Heisuke (1964). « Resolution of singularities of an algebraic variety over a field of characteristic zero. I, II ». In : *Annals of Mathematics. Second Series*, vol. 79, p. 205–326 (cité page 434).

HJB85 HEIDEMAN, Michael T., Don H. JOHNSON et C. Sidney BURRUS (1985). « Gauss and the history of the fast Fourier transform ». In : *Archive for History of Exact Sciences*, vol. 34, n°3, p. 265–277 (cité page 52).

HK71 HOPCROFT, J. E. et L. R. KERR (1971). « On minimizing the number of multiplications necessary for matrix multiplication ». In : *SIAM Journal on Applied Mathematics*, vol. 20, p. 30–36 (cité page 182).

HM73 HOPCROFT, J. et J. MUSINSKI (1973). « Duality applied to the complexity of matrix multiplication and other bilinear forms ». In : *SIAM Journal on Computing*, vol. 2, p. 159–173 (cité pages 183, 231, 232).

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 (cité page 522).

Hoe02a HOEIJ, Mark van (2002). « Factoring polynomials and the knapsack problem ». In : *Journal of Number Theory*, vol. 95, n°2, p. 167–189 (cité page 396).

Hoe02b HOEVEN, Joris van der (2002). « FFT-like multiplication of linear differential operators ». In : *Journal of Symbolic Computation*, vol. 33, n°1, p. 123–127 (cité page 619).

Hoe02c — (2002). « Relax, but don't be too lazy ». In : *Journal of Symbolic Computation*, vol. 34, n°6, p. 479–542 (cité pages 77, 78, 247).

Hoe03 — (2003). « Relaxed multiplication using the middle product ». In : *ISSAC'03 : International Symposium on Symbolic and Algebraic Computation*. Éd. par Manuel BRONSTEIN. Philadelphia, USA : ACM Press, p. 143–147 (cité page 78).

Hoe04 — (2004). « The truncated Fourier transform and applications ». In : *ISSAC'04 : International Symposium on Symbolic and Algebraic Computation*. New York : ACM Press, p. 290–296 (cité page 54).

Hoe07 — (2007). « New algorithms for relaxed multiplication ». In : *Journal of Symbolic Computation*, vol. 42, n°8, p. 792–802 (cité page 78).

Hoe10 — (2010). « Newton's method and FFT trading ». In : *Journal of Symbolic Computation*, vol. 45, n°8, p. 857–878 (cité pages 78, 247).

Hoe98 HOEIJ, Mark van (1998). « Rational solutions of linear difference equations ». In : *ISSAC'98 : International Symposium on Symbolic and Algebraic Computation*. New York : ACM Press, p. 120–123 (cité page 310).

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 (cité page 558).

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

Hor72 HOROWITZ, E. (1972). « A fast method for interpolation using preconditioning ». In : *Information Processing Letters*, vol. 1, n°4, p. 157–163 (cité page 107).
HQZ04 HANROT, Guillaume, Michel QUERCIA et Paul ZIMMERMANN (2004). « The middle product algorithm I ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 14, n°6, p. 415-438 (cité pages 54, 231, 232, 247).

HS81 HEINTZ, Joos et Malte SIEVEKING (1981). « Absolute primality of polynomials is decidable in random polynomial time in the number of variables ». In : *Automata, languages and programming (Akko, 1981)*. Vol. 115. Lecture Notes in Computer Science. Springer-Verlag, p. 16-28 (cité page 413).

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 (cité page 523).

HS85 HARRIS, William A. et Yasutaka SIBUYA (1985). « The reciprocals of solutions of linear ordinary differential equations ». In : *Advances in Mathematics*, vol. 58, n°2, p. 119-132 (cité page 267).

Hua91 HUANG, Ming-Deh A. (1991). « Generalized Riemann hypothesis and factoring polynomials over finite fields ». In : *Journal of Algorithms*, vol. 12, n°3, p. 464-481 (cité page 356).

Hus+96 HUSS-LEDERMAN, S., E. M. JACOBSON, A. TSAO, T. TURNBULL et J. R. JOHNSON (1996). « Implementation of Strassen's algorithm for matrix multiplication ». In : *Supercomputing'96*. 32 pp. Pittsburgh, PA : IEEE Computer Society (cité page 182).

Huỳ86 HUÝNH, Dùng T. (1986). « A superexponential lower bound for Gröbner bases and Church-Rosser commutative Thue systems ». In : *Information and Control*, vol. 68, n°1-3, p. 196-206 (cité page 481).

HW08 HARDY, G. H. et E. M. WRIGHT (2008). *An introduction to the theory of numbers*. 6e éd. Oxford University Press (cité page 396).

HZ HANROT, Guillaume et Paul ZIMMERMANN (2004). *Newton iteration revisited*. url : http://www.loria.fr/~zimmerma/papers (visible en 2004) (cité page 78).

Inc56 INCE, E. L. (1956). *Ordinary differential equations*. Reprint of the 1926 edition. Dover Publications (cité page 321).

JaJ79 Ja'Ja', Joseph (1979). « On the complexity of bilinear forms with commutativity ». In : *STOC'79 : ACM Symposium on Theory of Computing*. Atlanta, Georgia, United States : ACM, p. 197-208 (cité page 181).

Jan20 JANET, Maurice (1920). « Sur les systèmes d'équations aux dérivées partielles ». In : *Journal de Mathématiques Pures et Appliquées*, vol. 3, p. 65-151 (cité page 444).

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 (cité page 523).

Joh15 JOHANSSON, Fredrik (2015). « A fast algorithm for reversion of power series ». In : *Mathematics of Computation*, vol. 84, n°291, p. 475-484 (cité page 77).

Jou09 Joux, Antoine (2009). *Algorithmic cryptanalysis*. Chapman & Hall/CRC Cryptography and Network Security Series. Chapman et Hall/CRC (cité pages 13, 434).

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 (cité page 523).

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 (cité page 523).

JS02 — (2002). « Effective equidimensional decomposition of affine varieties ». In : *Journal of Pure and Applied Algebra*, vol. 169, n°2-3, p. 229-248 (cité page 523).
JV05 JEANNEROD, Claude-Pierre et Gilles VILLARD (2005). « Essentially optimal computation of the inverse of generic polynomial matrices ». In: *Journal of Complexity*, vol. 21, n°1, p. 72-86 (cité page 214).

Kal03 KALTOFEN, Erich (2003). « Polynomial factorization : a success story ». In: *ISSAC'03 : International Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 3-4 (cité page 412).

Kal59 KALMAN, R. E. (1959). « On the general theory of control systems ». In: *IRE Transactions on Automatic Control*, vol. 4, n°3, p. 481-491 (cité page 231).

Kal82a KALTOFEN, E. (1982). « A polynomial-time reduction from bivariate to univariate integral polynomial factorization ». In: *23rd Annual Symposium on Foundations of Computer Science (SFCS '08)*. IEEE, p. 57-64 (cité page 412).

Kal82b — (1982). « Polynomial factorization ». In: *Computer algebra. Symbolic and Algebraic Computation*. Éd. par B. BUCHBERGER, G. E. COLLINS et R. LOOS. Springer-Verlag, p. 95-113 (cité page 412).

Kal82c KALTOFEN, Erich (1982). « A polynomial reduction from multivariate to bivariate integral polynomial factorization ». In: *STOC'82 : ACM Symposium on Theory of Computing*. ACM Press, p. 261-266 (cité pages 412, 413).

Kal83 — (1983). « On the complexity of finding short vectors in integer lattices ». In: *Computer Algebra : EUROCAL'83, European Computer Algebra Conference London, England, March 28-30, 1983 Proceedings*. Éd. par J. A. HULZEN. Berlin, Heidelberg : Springer Berlin Heidelberg, p. 236-244 (cité page 370).

Kal85a KALTOFEN, E. (1985). « Sparse Hensel lifting ». In: *Proceedings of EUROCAL '85, Vol. 2 (Linz, 1985)*. Vol. 204. Lecture Notes in Computer Science. Springer-Verlag, p. 4-17 (cité pages 412, 413).

Kal85b KALTOFEN, Erich (1985). « Effective Hilbert irreducibility ». In: *Information and Control*, vol. 66, n°3, p. 123-137 (cité pages 412, 413).

Kal85c — (1985). « Fast parallel absolute irreducibility testing ». In: *Journal of Symbolic Computation*, vol. 1, n°1, p. 57-67 (cité pages 412, 413).

Kal85d — (1985). « Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization ». In: *SIAM Journal on Computing*, vol. 14, n°2, p. 469-489 (cité pages 412, 413).

Kal90 — (1990). « Polynomial factorization 1982-1986 ». In: *Computers in mathematics (Stanford, CA, 1986)*. Vol. 125. Lecture Notes in Pure and Applied Mathematics. Dekker, p. 285-309 (cité page 412).

Kal92 — (1992). « Polynomial factorization 1987-1991 ». In: *LATIN '92 (São Paulo, 1992)*. Vol. 583. Lecture Notes in Computer Science. Springer-Verlag, p. 294-313 (cité page 412).

Kal93a — (1993). « Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems ». In: *Applied algebra, algebraic algorithms and error-correcting codes*. Vol. 673. Lecture Notes in Computer Science. Springer-Verlag, p. 195-212 (cité page 232).

Kal93b — (1993). « Computational differentiation and algebraic complexity theory ». In: *Workshop Report on First Theory Institute on Computational Differentiation*, p. 28-30 (cité page 231).

Kal94 — (1994). « Asymptotically fast solution of Toeplitz-like singular linear systems ». In: *ISSAC'94 : International Symposium on Symbolic and Algebraic Computation*. Oxford, United Kingdom : ACM Press, p. 297-304 (cité page 206).

Kal95a KALTOFEN, E. (1995). « Effective Noether irreducibility forms and applications ». In: *Journal of Computer and System Sciences*, vol. 50, n°2, p. 274-295 (cité page 413).
Kal95b KALTOFEN, Erich (1995). « Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems ». In : Mathematics of Computation, vol. 64, n°210, p. 777-806 (cité page 206).

Kam85 KAMINSKI, Michael (1985). « A lower bound for polynomial multiplication ». In : Theoretical Computer Science, vol. 40, n°2-3, p. 319-322 (cité page 54).

Kap04 KAPORIN, I. (2004). « The aggregation and cancellation techniques as a practical tool for faster matrix multiplication ». In : Theoretical Computer Science, vol. 315, n°2-3, p. 469-510 (cité page 183).

Kap99 KAPORIN, Igor (1999). « A practical algorithm for faster matrix multiplication ». In : Numerical Linear Algebra with Applications, vol. 6, n°8, p. 687-700 (cité page 183).

KB70 KNUTH, Donald E. et Peter B. BENDIX (1970). « Computational problems in abstract algebra ». In : éd. par John LEECH. Pergamon Press. Chap. Simple word problems in universal algebras, p. 263-297 (cité page 435).

KCJ00 KALTOFEN, E., R. M. CORLESS et D. J. JEFFREY (2000). « Challenges of symbolic computation : my favorite open problems ». In : Journal of Symbolic Computation, vol. 29, n°6, p. 891-919 (cité page 231).

Kel85 KELLER-GEHRIG, Walter (1985). « Fast algorithms for the characteristic polynomial ». In : Theoretical Computer Science, vol. 36, n°2-3, p. 309-317 (cité pages 180, 181, 619).

Kha02 KHAN, M. A. H. (2002). « High-order differential approximants ». In : Journal of Computational and Applied Mathematics, vol. 149, n°2, p. 457-468 (cité page 154).

KK65 KLYUYEV, V. V. et N. I. KOKOVKIN-SHCHERBAK (1965). « On the minimization of the number of arithmetic operations for the solution of linear algebraic systems of equations ». In : USSR Computational Mathematics and Mathematical Physics, vol. 5, p. 25-43 (cité page 180).

KKB88 KAMINSKI, M., D. G. KIRKPATRICK et N. H. BSHOUTY (1988). « Addition requirements for matrix and transposed matrix products ». In : Journal of Algorithms, vol. 9, n°3, p. 354-364 (cité pages 230, 231).

KKM79a KAILATH, T., S. Y. KUNG et M. MORF (1979). « Displacement ranks of a matrix ». In : American Mathematical Society. Bulletin. New Series, vol. 1, n°5, p. 769-773 (cité page 206).

KKM79b KAILATH, Thomas, Sun Yuan KUNG et Martin MORF (1979). « Displacement ranks of matrices and linear equations ». In : Journal of Mathematical Analysis and Applications, vol. 68, n°2, p. 395-407 (cité page 206).

KM97 KARP, A. H. et P. MARKSTEIN (1997). « High-precision division and square root ». In : ACM Transactions on Mathematical Software, vol. 23, n°4, p. 561-589 (cité page 77).

Knu71 KNUTH, Donald E. (1971). « The analysis of algorithms ». In : Actes du Congrès International des Mathématiciens 1970. Vol. 3. Nice : Gauthier-Villars, p. 269-274 (cité page 135).

Knu97 — (1997). The art of computer programming. 3e éd. Vol. 2 : Seminumerical Algorithms. Computer Science and Information Processing. Addison-Wesley Publishing Co. (cité pages 12, 135, 342).

KO63 KARATSUBA, A. et Y. OFMAN (1963). « Multiplication of multidigit numbers on automata ». In : Soviet Physics Doklady, vol. 7, p. 595-596 (cité page 52).

Kou10 KOUTSCHAN, Christoph (2010). « A fast approach to creative telescoping ». In : Mathematics in Computer Science, vol. 4, n°2-3, p. 259-266 (cité page 588).

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 (cité page 541).
KP81 Knuth, Donald E. et Christos H. Papadimitriou (1981). « Duality in addition chains ». In: Bulletin of the European Association for Theoretical Computer Science, vol. 13, p. 2-4 (cité pages 231, 232).

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 (cité page 522).

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 (cité pages 464, 522).

Kry31 Krylov, A. N. (1931). « On the numerical solution of the equation by which in technical questions frequencies of small oscillations of material systems are determined ». In: Izvestiya Akademii Nauk SSSR, vol. 7, n°4. (in Russian), p. 491-539 (cité page 181).

KS01 Koy, Henrik et Claus Peter Schnorr (2001). « Segment LLL-Reduction of Lattice Bases ». In: Cryptography and Lattices: International Conference, CaLC 2001 Proceedings, RI, USA, March 29-30, 2001 Revised Papers. Éd. par Joseph H. Silverman. Berlin, Heidelberg: Springer Berlin Heidelberg, p. 67-80 (cité page 370).

KS73 Kogge, P. et H. STONE (1973). « A parallel algorithm for the efficient solution of a general class of recurrence equations ». In: IEEE Transactions on Computers, vol. C-22, p. 786-793 (cité page 322).

KS91 Kaltofen, Erich et B. David Saunders (1991). « On Wiedemann's method of solving sparse linear systems ». In: Applied algebra, algebraic algorithms and error-correcting codes (New Orleans, LA, 1991). Vol. 539. Lecture Notes in Computer Science. Springer-Verlag, p. 29-38 (cité page 193).

KS98 Kaltofen, Erich et Victor Shoup (1998). « Subquadratic-time factoring of polynomials over finite fields ». In: Mathematics of Computation, vol. 67, n°223, p. 1179-1197 (cité page 356).

KT77 Kung, H. T. et D. M. TONG (1977). « Fast algorithms for partial fraction decomposition ». In: SIAM Journal on Computing, vol. 6, n°3, p. 582-593 (cité page 619).

KU08 Kedlaya, Kiran S. et Christopher Umans (2008). « Fast modular composition in any characteristic ». In: FOCS'08: IEEE Conference on Foundations of Computer Science. Washington, DC, USA: IEEE Computer Society, p. 146-155 (cité pages 77, 356).

Kun74 Kung, H. T. (1974). « On computing reciprocals of power series ». In: Numerische Mathematik, vol. 22, p. 341-348 (cité page 77).

KV04 Kaltofen, Erich et Gilles Villard (2004). « On the complexity of computing determinants ». In: Computational Complexity, vol. 13, n°3-4, p. 91-130 (cité page 214).

Lad76 Laderman, Julian D. (1976). « A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications ». In: Bulletin of the American Mathematical Society, vol. 82, n°1, p. 126-128 (cité page 182).

Lag68 Lagrange, Joseph Louis, comte de (1768). « Nouvelle méthode pour résoudre les équations littérales par le moyen des séries ». In: Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin, vol. 24, p. 251-326 (cité page 77).

Lag73 — (1773). « Recherches d'arithmétique ». In: Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin, p. 265-312 (cité page 370).

Lag75 — (1775). « Recherches d'arithmétique ». In: Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin, p. 323-356 (cité page 370).

Lak90 Lakshman, Y. N. (1990). « On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal ». In: Proceedings of the Twenty-second Annual
ACM Symposium on Theory of Computing. STOC '90. New York, NY, USA : ACM, p. 555-563 (cité page 481).

Lak91 LAKSHMAN, Y. N. (1991). « A single exponential bound on the complexity of computing Gröbner bases of zero dimensional ideals ». In : *Effective Methods in Algebraic Geometry*. Éd. par Teo MORA et Carlo TRAVERSO. Boston, MA : Birkhäuser Boston, p. 227-234 (cité page 481).

Lan02 LANG, Serge (2002). *Algebra*. 3e éd. Vol. 211. Graduate Texts in Mathematics. Springer-Verlag (cité pages 12, 135).

Lan05 LANDAU, E. (1905). « Sur quelques théorèmes de M. Petrovitch relatifs aux zéros des fonctions analytiques ». In : *Bulletin de la S. M. F*. vol. 33, p. 251-261 (cité page 396).

Lan06 LANDSBERG, J. M. (2006). « The border rank of the multiplication of 2 × 2 matrices is seven ». In : *Journal of the American Mathematical Society*, vol. 19, n°2, p. 447-459 (cité page 182).

Lan08 — (2008). « Geometry and the complexity of matrix multiplication ». In : *Bulletin of the American Mathematical Society*, vol. 45, n°2, p. 247-284 (cité page 184).

Lan14 — (2014). « New lower bounds for the rank of matrix multiplication ». In : *SIAM Journal on Computing*, vol. 43, n°1, p. 144-149 (cité page 182).

Las03 LASCOUX, Alain (2003). *Symmetric functions and combinatorial operators on polynomials*. Vol. 99. CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC (cité page 135).

Laz83 LAZARD, D. (1983). « Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations ». In : *Computer Algebra : EUROCAL'83, European Computer Algebra Conference London, England, March 28-30, 1983 Proceedings*. Éd. par J. A. HULZEN. Springer Berlin Heidelberg, p. 146-156 (cité pages 444, 481).

Le 14 LE GALL, François (2014). « Powers of tensors and fast matrix multiplication ». In : *ISSAC'14 : International Symposium on Symbolic and Algebraic Computation*. Éd. par Katsusuke NABESHIMA. New York, NY, USA : ACM, p. 296-303 (cité page 183).

Le 40 LE VERRIER, Urbain (1840). « Sur les variations séculaires des éléments elliptiques des sept planètes principales : Mercure, Vénus, la Terre, Mars, Jupiter, Saturne et Uranus ». In : *Journal de Mathématiques Pures et Appliquées*, vol. 1 (5), p. 220-254 (cité page 181).

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 (cité page 523).

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

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 (cité page 523).

Lec06 — (2006). « Sharp precision in Hensel lifting for bivariate polynomial factorization ». In : *Mathematics of Computation*, vol. 75, p. 921-933 (cité page 413).

Lec07 — (2007). « Improved dense multivariate polynomial factorization algorithms ». In : *Journal of Symbolic Computation*, vol. 42, n°4, p. 477-494 (cité page 413).
Lec08 — (2008). « Fast separable factorization and applications ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 19, n°2, p. 135-160 (cité pages 342, 396, 412).

Lec10 — (2010). « New recombination algorithms for bivariate polynomial factorization based on Hensel lifting ». In : *Applicable Algebra in Engineering, Communication and Computing*, vol. 21, n°2, p. 151-176 (cité page 413).

Lec13 — (2013). « Factorisation des polynômes à plusieurs variables (Cours no. II) ». In : *Journées nationales de calcul formel*. Éd. par G. CHÈZE, P. BOITO, C. PERNET et M. Safey el DIN. Vol. 3. Les cours du CIRM n°1. Cedram, p. 1-85. url : http://ccirm.cedram.org/ccirm-bin/fitem?id=CCIRM_2013_3_1_A2_0 (cité pages 342, 413).

Leh38 LEHMER, D. H. (1938). « Euclid's Algorithm for large numbers ». In : *The American Mathematical Monthly*, vol. 45, n°4, p. 227-233 (cité page 135).

Lej84 LEJEUNE-JALABERT, Monique (1984). *Effectivité de calculs polynomiaux*. Vol. 19. Cours de l'Institut Fourier. Cours de DEA 84-85. Université de Grenoble I. url : http://www.numdam.org/numdam-bin/feuilleter?id=CIF_1984-1985_19_ (cité page 481).

Lev47 LEVINSON, Norman (1947). « The Wiener RMS (root mean square) error criterion in filter design and prediction ». In : *Journal of Mathematics and Physics*, vol. 25, p. 261-278 (cité page 206).

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

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 (cité page 558).

Lic87 LICKTEIG, Thomas (1987). « The computational complexity of division in quadratic extension fields ». In : *SIAM Journal on Computing*, vol. 16, n°2, p. 278-311 (cité page 180).

Lio33 LIOUVILLE, Joseph (1833). « Second mémoire sur la détermination des intégrales dont la valeur est algébrique ». In : *Journal de l'École polytechnique*, vol. 14, p. 149-193 (cité page 321).

Lip76 LIPSON, J. D. (1976). « Newton's method : a great algebraic algorithm ». In : *SYM-SAC'76 : ACM Symposium on Symbolic and Algebraic Computation*. ACM Press, p. 260-270 (cité page 77).

Lip89 LIPSHITZ, L. (1989). « D-finite power series ». In : *Journal of Algebra*, vol. 122, n°2, p. 353-373 (cité page 266).

LL91 LAKSHMAN, Y. N. et Daniel LAZARD (1991). « On the complexity of zero-dimensional algebraic systems ». In : *Effective Methods in Algebraic Geometry*. Éd. par Teo MORA et Carlo TRAVERSO. Boston, MA : Birkhäuser Boston, p. 217-225 (cité page 481).

LLL82 LENSTRA, A. K., H. W. LENSTRA Jr. et L. Lovász (1982). « Factoring polynomials with rational coefficients ». In : *Mathematische Annalen*, vol. 261, n°4, p. 515-534 (cité pages 370, 396).

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 (cité page 558).

LPS92 LADERMAN, Julian, Victor PAN et Xuan He SHA (1992). « On practical algorithms for accelerated matrix multiplication ». In : *Linear Algebra and its Applications*, vol. 162/164, p. 557-588 (cité page 183).