%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 

\documentclass{article}
\usepackage[francais]{babel}
%\usepackage[OT1]{fontenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{xspace}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\newcommand{\Q}{{\mathbb{Q}}}
\newtheorem{thm}{Théorème}

\begin{document}
\title{Intégration (l'algorithme de Risch)}

\author{B. Parisse\\Institut Fourier\\UMR 5582 du CNRS
\\Université de Grenoble I}
\maketitle

\section{Introduction}
Que peut-on espérer d'un système de calcul formel lorsqu'il s'agit
de calculer une primitive? Tout d'abord, on peut espérer qu'il
sache résoudre ce que l'on donne en exercice à nos étudiants!
Ceci suppose donc de connaitre quelques méthodes classiques, par
exemple: intégration de polynômes (!), polynômes multipliés par exponentielle
ou/et fonctions trigonométriques, de polynômes trigonométriques par
linéarisation, de fractions rationnelles,
de fractions trigonométriques, de fractions de racines carrées de 
polynômes du second ordre, de fonctions s'y ramenant par une ou plusieurs
intégrations par parties ou par
changement de fonction (par exemple reconnaissance de formes $F(u)u'\ $)
ou par changement de variables, etc.

Mais au-delà de ces méthodes (qui ont l'avantage de la rapidité mais
tiennent parfois plus de la
recette de cuisine que de l'algorithme...), on peut se demander 
si la primitive d'une fonction donnée peut ou non s'exprimer en terme 
des fonctions ``élémentaires''. Par exemple, tout le monde ``sait''
que la fonction $e^{x^2}$ n'admet pas de primitive ``simple'', encore
faut-il donner un sens mathématique précis à cette affirmation.
Ceci nécessite de donner une définition rigoureuse du terme fonction
élémentaire. On peut alors appliquer un algorithme développé
par Risch (pour les extensions dites transcendantes, obtenue par ajout
des fonctions exponentielle et logarithme)  
qui permet de répondre à la question~:
il s'agit vu de très loin d'une extension de l'algorithme d'intégration
des fractions rationnelles.

Cet article se décompose en deux parties principales~:
\begin{itemize}
\item la section \ref{sec:elem} présente les définitions de fonctions
élémentaires, de tour de variables, et donne deux théorèmes,
le théorème de structure de Risch qui permet d'écrire une fonction 
contenant des exponentielles et des logarithmes comme une fonction 
élémentaire par rapport à une tour de variable, et 
le théorème de Liouville qui donne la forme que peut prendre
une primitive d'une fonction élémentaire lorsqu'elle est aussi élémentaire.
\item la section \ref{sec:risch} décrit l'algorithme d'intégration de Risch
permettant de décider si une fonction élémentaire donnée possède
ou non une primitive élémentaire et de la calculer dans le premier
cas. Nous ne présentons ici l'algorithme de Risch que pour les extensions
transcendantes pures (ln et exp).
\end{itemize}
Le lecteur intéressé par le cas des extensions algébriques 
pourra consulter la thèse de Trager. Pour les extensions
plus g\'en\'erales (incluant en particulier les fonctions
tangente, arctangente), la r\'ef\'erence est le livre de Bronstein 
donnée en section \ref{sec:rischref}.

\section{Fonctions élémentaires} \label{sec:elem}

\subsection{Extensions transcendantes, tour de variables}
On se donne une expression $f(x)$ dépendant de la variable $x$ que l'on 
souhaite intégrer par rapport à $x$. L'algorithme de Risch s'applique à
cette expression si on peut l'écrire comme une fraction rationnelle à
plusieurs variables algébriquement indépendantes
\[ x, f_1(x), f_2(x,f_1(x)), ..., 
f_n(x,f_1(x),f_2(x,f_1(x)),...,f_{n-1}(x,f_1(x),...,f_{n-2}(x))) \]
où les $f_i$ sont soit l'exponentielle soit le logarithme d'une fraction
rationnelle (le corps de base appelé aussi corps de
constantes ici est soit $\C$, soit une extension algébrique de $\Q$ ou une
extension algébrique d'un corps de fractions rationnelles s'il
y a des paramètres). 
On appelle tour de variables
la suite des $x,f_1,...,f_n$ (chaque étage est donc une exponentielle
d'une fraction rationnelle ou le logarithme d'une fraction rationnelle
dépendant des étages précédents) 
et on dira que $f$ est une fonction élémentaire
par rapport à cette tour de variables.

L'intérêt de l'écriture d'une expression sous forme de tour est 
qu'elle est stable par dérivation~: 
si on dérive par rapport à $x$
une fonction élémentaire dépendant d'une tour de variables, on obtient encore 
une fonction élémentaire dépendant de la même tour de variables.
Autrement dit, l'ensemble des fonctions \'el\'ementaires pour une tour 
fix\'ee est un corps diff\'erentiel.

{\bf Exemples: }
\begin{itemize}
\item $e^{x^2}$ est bien dans ce cas, pour $n=1$, $f_1$
est l'exponentielle de $x^2$ qui est algébriquement indépendant
de $x$. Les fonctions $(2x^2-1)e^{x^2}$
ou $x/(e^{x^2}-1)$ sont aussi élémentaires par rapport à
la tour de variables $\{x,e^{x^2} \}$.  
\item $x \ln(x) \exp(x)$ est élémentaire par rapport à la tour
$\{ x, \ln(x), \exp(x)\}$, mais aussi par rapport à la tour
$\{ x, \exp(x), \ln(x)\}$.
\item $xe^{x \ln(x)}$ est élémentaire, en prenant $n=2$, $f_1=\ln(x)$
et $f_2=e^{x f_1}$.
\item $x^n=e^{n\ln(x)}$, o\`u $n$ est un param\`etre, convient avec
comme tour $\{x, \ln(x), e^{n \ln(x) }$
\item $e^{\ln(x)}$ ne convient pas car il n'est pas algébriquement
indépendant de $x,\ln(x)$ mais on peut le réécrire sous une forme
acceptable puisque $e^{\ln(x)}=x$.
\item $e^{\ln(x)/2}$ ne convient pas non plus car son carré est égal à $x$.
Une réécriture ne suffit pas, cet exemple est bien sûr une extension
algébrique et non transcendante.
\end{itemize}

Dans la suite, on va s'intéresser aux tours de variables dans lesquelles 
on a effectué des simplifications évidentes.
On élimine les $\ln \circ \exp$ de la manière suivante~:
si $f_k=\ln(g_k)$, on regarde si $g_k$ vu comme fraction 
en $f_1,...,f_{k-1}$ possède un facteur $f_j^m$ (avec $m \in \Z$)
lorsque $f_j=\exp(g_j)$ est une exponentielle.
Si c'est le cas, on a $f_k= m g_j + \ln(g_k/g_j^m)$. On change
alors de tour en remplaçant $f_k$ par $\tilde{f}_k=\ln(g_k/g_j^m)=f_k-mg_j$.
On élimine aussi les $\exp \circ \ln$, si
$f_k=\exp(g_k)$, pour $j<k$ si $f_j$ est un logarithme,
on regarde si $c_j=\partial_{f_j}g_k|_{f_j=0}$ est un entier, si
c'est le cas on remplace $f_k$ par $\tilde{f}_k=f_k/g_k^{c_j}$.

{\bf Exemples: }
\begin{eqnarray*}
 \ln(\frac{e^{x^2}+1}{e^{x^2}}) &\rightarrow &-x^2 + \ln(e^{x^2}+1) \\
e^{3 \ln(x)+\ln(x)^2+5} & \rightarrow & x^3 e^{\ln(x)^2+5} 
\end{eqnarray*}


\subsection{Théorème de structure de Risch}
On voit donc qu'il est nécessaire de disposer d'un algorithme
pour décider si des exponentielles et logarithmes sont
algébriquement indépendants. Cet algorithme est basé sur
un théorème de structure dû à Risch~:
\begin{thm}
Soit $f=\ln(g(x))$ le logarithme d'une fonction élémentaire
$g$ par rapport à une tour de variables $T$, alors soit $f$
est algébriquement indépendant des variables de $T$, soit $f$ est
élémentaire et plus précisément combinaison linéaire rationnelle
des logarithmes et des arguments des exponentielles de la tour $T$.

Soit $f=\exp(g)$ l'exponentielle d'une fonction élémentaire $g$
par rapport à une tour de variables $T$, alors soit $f$
est algébriquement indépendante des variables de $T$, soit
il existe $n$ tel que $f^n$ soit élémentaire par rapport à $T$ 
(on peut alors appliquer le cas précédent à $ng=\ln(f^n)$)
\end{thm}

{\bf Démonstration}~:\\
Commençons par le cas de l'exponentielle. On considère le polynôme minimal
de $f=\exp(g)$~:
\[ a_n f^n+...+a_0=0, \quad a_n \neq 0 , a_0 \neq 0\]
où les $a_i$ sont des fractions rationnelles en $T$. On dérive
et on applique $f'=g'f$~:
\[ (a_n'+n a_n g') f^n +   ... + ( a_{k}' + ka_k g')f^{k} +... =0\]
c'est un multiple du polynôme minimal donc il existe une fraction rationnelle
$C$ (par rapport à la tour de variables) telle que~:
\[ \forall k, \quad (a_k'+k a_k g') = C a_k\]
Comme $a_n\neq 0$, cela entraine $a_n'/a_n+ng'=C$. Le coefficient
constant $a_0$ est aussi non nul, donc $a_0'/a_0=C$ et 
\[ n g' = a_0'/a_0 - a_n'/a_n \Rightarrow ng=\ln(\frac{a_0}{a_n}) + k\]
où $k$ est constant, donc $f^n=\exp(ng)=e^k a_0/a_n$ est élémentaire.

Passons au cas du logarithme, supposons que $f=\ln(g)$ dépende
algébriquement de la tour $T$, on va commencer par montrer que
$f$ est élémentaire. On écrit~:
\[ a_n f^n+...+a_0=0\]
où les $a_i$ sont des fractions rationnelles en $T$. On dérive en
appliquant $f'=g'/g$~:
\[ a_n' f^n + (n a_n f' + a_{n-1}')f^{n-1}  ... + a_1 f'+a_0 '\]
Comme $f'$ est une fraction rationnelle en $T$, le polynôme
$a_n' X^n + (n a_n f'+a_{n-1}') X^{n-1}+...+ a_1 f'+a_0'$ qui annule $f$
doit être un multiple du polynôme minimal de $f$, il existe donc
une fraction rationnelle $C$ par rapport à $T$ telle que~:
\[ a_n' = C a_n \quad (n a_n f'+a_{n-1}') = C a_{n-1} \quad ... \]
On en déduit $f'$~:
\[ f'=\frac{\frac{a_n'}{a_n} a_{n-1}-a_{n-1}'}{n a_n} = 
\left(\frac{-a_{n-1}}{n a_n}\right)'\]
donc il existe une constante $c$ telle que~:
\[ f=\frac{-a_{n-1}}{n a_n}+c\]
donc $f$ est élémentaire par rapport à la même tour $T$ que $g$.

Montrons maintenant qu'un logarithme $f=\ln(g)$ qui est élémentaire
par rapport à une tour de variable $T$ est combinaison linéaire à
coefficients rationnelles des logarithmes et des arguments
des exponentielles de $T$\footnote{cette preuve peut être sautée en première
lecture}.
Soit $X$ la dernière variable de la tour $T$.
On factorise maintenant le numérateur et le dénominateur de $g$ en
$\prod_j P_j^j$ où les $P_j$ sont sans facteurs multiples et 
premiers entre eux 2 à 2 (par rapport à $X$), il existe
$C$ indépendant de $X$ tel que~:
\begin{equation} \label{eq:g}
 g=C\prod_{j \in \Z} P_j ^{j} \Rightarrow 
\ln(g)=\ln(C)+\sum_{j \in \Z} j \ln(P_j)
\end{equation}
Alors $f'=\ln(C)'+\sum_j j P_j'/P_j$ donc $\prod P_j f'$ est un 
polynôme en $X$. 
Soit $N/D$ la fraction irréductible représentant $f$, on a~:
\[ f'=\frac{N' D -N D'}{D^2}\]
on vient donc de montrer que~:
\begin{equation} \label{eq:prodpj}
\left(\prod_j P_j \right) \frac{N' D - N D'}{D^2} 
\mbox{ est un polynôme en $X$}
\end{equation}
Soit $P$ un facteur irréductible de $D$ de multiplicité
$k$ tel que $D=P^k Q$ (donc $P$ premier avec $Q$, mais $P$ est aussi
premier avec $N$ car $f=N/D$ est irréductible). Alors en simplifiant
numérateur et dénominateur par $P^{k-1}$, on a~:
\begin{equation} \label{eq:estpolynome}
 \left( \prod_j P_j \right) \frac{N' P Q - N (kP'Q+PQ')}{ P^{k+1} Q^2} 
\mbox{ est un polynôme en $X$.} 
\end{equation}
On en déduit, après simplification d'au plus un facteur $P$ au dénominateur 
avec l'un des $P_j$, que $P^{k}$ divise 
$N' P Q - N (kP'Q+PQ')$ donc $P$ divise $P'$. Ceci n'est possible
que si $P=1$ (et donc le dénominateur de $f$ est égal à 1) 
ou si la variable $X$ est une exponentielle et $P=X$.

Montrons que ce deuxième cas est en fait exclus:
en effet si $P=X=\exp(Y)$ est une exponentielle, on a alors 
$D=X^k$ et $Q=1$.
Comme $P'=Y'X$, (\ref{eq:estpolynome}) devient~:
\[ \left( \prod_j P_j \right) \frac{X (N' - k N Y' )}{X^{k+1}}
\mbox{ est un polynôme en $X$} \]
Comme $X$ ne divise pas $N$, $N$ possède donc un coefficient constant 
$a_0$ non nul. Le coefficient constant de $N'-kNY'$ est $a_0'-ka_0 Y'$. 
Si ce terme était nul alors $a_0'=ka_0 Y'$ donc $a_0=c \exp(kY)=cX^k$ 
or $a_0$ ne dépend pas de $X$ donc $c=0$ donc $a_0=0$, absurde. 
Donc $X$ ne divise pas $N'-kNY'$.
Comme $X^{k+1}$ divise $ \prod P_j X (N' - k N Y' )$, on en déduit que
$X^k$ divise un des $P_j$. Donc $k=1$ et $P_j=XQ_j$. 
Revenons maintenant à (\ref{eq:g}), on a~:
\[  f=\ln(g) = \ln(C)+j \ln(XQ_j)+ \sum_{l \neq j} l \ln(P_l) \]
on dérive~:
\[ f'=\ln(C)'+jY'+j\frac{Q_j'}{Q_j}+\sum_{l \neq j} l \frac{P_l'}{P_l}\]
on voit qu'il n'est plus nécessaire de multiplier $f'$ par $P_j$
pour avoir un polynôme, multiplier par $Q_j$ suffit, plus précisément
\[ 
\left( \prod_{l \neq j} P_l \right) Q_j \frac{N' D - N D'}{D^2} 
\mbox{ est un polynôme en $X$.} 
\]
donc $X^{k+1}$ divise  
$ \left(\prod_{l \neq j}P_l \right) Q_j X (N' - k N Y' )$ 
ce qui est impossible.

Donc $D=1$ dans tous les cas et on a $f=N$. Donc 
\[ f'=N'=\ln(C)'+\sum_j j P_j'/P_j 
\mbox{ est un polynôme par rapport à $X$} \]
On en déduit que les $P_j$ ne dépendent pas de $X$ sauf si
$X$ est une exponentielle et $P_j=X$. 
Dans les deux cas $N'$ ne
dépend pas de $X$ donc le polynôme $N$ est de degré 0 ou 1 en $X$
(si $X$ est une exponentielle, $N$ est forcément de degré 0)
\begin{itemize}
\item Si $X=\exp(Y)$ est une exponentielle (avec $Y$ élémentaire
ne dépendant pas de $X$), alors $f=N$ est indépendant de $X$.
On retire $jY$ à $f$ et on divise $g$ par $X^j$ 
(en posant $j=0$ si aucun des $P_j$ n'est égal à $X$), 
qui devient indépendant de $X$, on conserve ainsi l'égalité $f=\ln(g)$
mais avec une variable de moins dans la tour de variables par
rapport à laquelle $f$ et $g$ sont élémentaires.
\item Si $X$ n'est pas une exponentielle, $N=cX+d$ avec $c$
dans le corps de constantes, et $d$ indépendant de $X$.
Si $X=x$, on a $g=\exp(cx+d)$ qui n'est rationnel que si
$c=0$. On a alors $d$ donc $f$ et $g$ constants.
Si $X=\ln(Y)$ est un logarithme (avec $Y$ élémentaire
ne dépendant pas de $X$), alors $\forall j, P_j=1$ donc $g$ est élémentaire
indépendante de $X$. 
On a alors~:
\[ f=N=c\ln(Y)+d = \ln(g) \]
avec $c$ dans le corps des constantes, $d$ et $g$ élémentaires
indépendants de $X$. On cherche maintenant la fonction
élémentaire $d$. Cette fonction n'est pas le logarithme d'une
fonction élémentaire en général car $c$ n'est pas forcément entier,
mais $d'$ a les mêmes propriétés que la dérivée du logarithme
d'une fonction élémentaire.
On peut donc reprendre le même raisonnement mais avec une variable de moins
dans la tour de variables. Si la tour qu'on a choisie est normalisée,
alors $Y$ ne contient au numérateur et au dénominateur aucune puissance
d'une exponentielle d'une variable de la tour donc le polynôme $P_j$
du cas précédent ne peut provenir de $Y$ ce qui entraine que $j$
est bien entier dans le cas précédent (bien que $c$ ne le soit
pas forcément).
\end{itemize}

Après avoir fait une récurrence sur le nombre de variables de la tour,
on a donc $f$ qui s'exprime comme combinaison linéaire à coefficients
entiers des arguments $g_k$ des variables exponentielles $f_k=\exp(g_k)$
de la tour et à coefficients a priori quelconque des variables logarithmes
$f_l=\ln(g_l)$ de la tour~:
\[ f = \sum_k j_k g_k + \sum_l x_l \ln (g_l) = \ln (g) \]
Comme $g$ est élémentaire, $h=g/\prod_k \exp(g_k)^{j_k}$
est élémentaire de logarithme $\sum_l x_l \ln (g_l) $.
Montrons que si les arguments des $\ln$ sont des polynômes
sans facteurs multiples, alors
les $x_l$ sont entiers. Rappelons
que les $\ln (g_l)$ sont algébriquement indépendants, on peut donc
construire des polynômes irréductibles $I_l$ par rapport aux variables
de la tour tels que $I_l$ divise une fois $g_l$ mais ne divise pas les $g_k$
précédents. Soit $h=\prod_{j \in \Z} P_j^j$ la factorisation
sans facteurs multiples de $h$. On dérive alors $\ln(h)$ ce qui donne~:
\[ \sum_l x_l g_l'/g_l = \sum_j j P_j'/P_j \]
où $\prod_j P_j^j$ est la décomposition sans facteurs multiples
de $h$. Comme $I_l$ divise un et un seul des $P_j$ on en déduit
que $x_l$ est égal au $j$ correspondant et est donc entier.
(Remarque: si on n'impose pas aux arguments des logarithmes
d'être des polynômes sans facteurs carrés, 
on obtiendrait ici des coefficients rationnels).

{\bf En pratique}:\\
On peut effecter l'algorithme de la manière suivante~: 
\begin{itemize}
\item on cherche les variables généralisées de l'expression
qui dépendent de $x$.
\item On ajoute les variables généralisées en commençant par
la moins longue
\item Si c'est un logarithme, on extrait les puissances des
exponentielles précédentes dont il dépend.
On cherche des relations entre fonctions $\ln$ en les réécrivant
comme combinaison linéaire de $\ln$ indépendants. Pour avoir
des $\ln$ indépendants, on se ramène d'abord à des polynômes
sans facteurs multiples en utilisant la relation $\ln(a/b)=\ln(a)-\ln(b)$ 
et en écrivant la factorisation sans facteurs multiples 
de chaque polynôme argument, puis
on extrait le PGCD 2 à 2 des arguments de logarithmes jusqu'à
obtenir des arguments de $\ln$ premiers entre eux.
\item Si c'est une exponentielle, on teste
si son argument est combinaison linéaire à coefficients rationnels~:
\begin{itemize}
\item des arguments des exponentielles précédentes, 
\item des $\ln$ des logarithmes précédents,
\item de $\ln(x)$ et de $i*\pi$.
\end{itemize}
Pour cela on substitue les $\ln$ par des indéterminées,
et on dérive une fois par rapport à cette indéterminée, le
résultat doit être un rationnel, pour les variables exponentielles,
il faut réduire au même dénominateur et résoudre le système
linéaire obtenu en identifiant les coefficients du numérateur.
Si l'exponentielle est indépendante des précédentes, 
on extrait de l'exponentielle à rajouter la partie linéaire de la 
dépendance en les $\ln$ précédents si le coefficient correspondant est
entier. Par exemple, on réécrit~:
\[ xe^{2 \ln(x)+\ln(x)^2} = x^3 e^{\ln(x)^2} \]
\end{itemize}

{\bf Remarque}\\
On n'est pas obligé de se limiter aux seules fonctions logarithmes
et exponentielles, l'essentiel est de pouvoir tester l'indépendance
algébrique des expressions créées. Pour éviter d'avoir à introduire
des exponentielles et logarithmes complexes dans une expression
réelle, on peut autoriser
par exemple des extensions en tangente ou en arctangente.

\subsection{Théorème de Liouville}
On a vu que la d\'eriv\'ee d'une fonction élémentaire dépendant 
d'une tour de variables est une fonction élémentaire dépendant 
de la même tour de variables.
Réciproquement, supposons qu'une fonction élémentaire admette
une primitive qui soit élémentaire, c'est-à-dire qu'elle doit
être une fraction rationelle par rapport à une tour de variables
mais pas forcément identique à celle de départ. Alors, si une telle
écriture existe, à des termes logarithmiques près, elle
ne peut dépendre que de la même tour de variables, plus précisément
on a le théorème de Liouville~:
\begin{thm}
Soit $f$ une fonction élémentaire par rapport à une tour de variables $T$
et un corps de constantes $K$ admettant une primitive élémentaire $F$. Alors 
il existe un nombre fini de constantes $c_1,...,c_n$ et de fonctions
élémentaires $v_1,...,v_n$ par rapport à $T$ avec comme corps de constantes
une extension algébrique $K'$ de $K$ tel que $F - \sum_k c_k \ln(v_k) $
soit élémentaire par rapport à $T$ et $K$.
\end{thm}

{\bf Preuve:}\footnote{Peut être omise en première lecture}\\
Soit $f$ élémentaire de tour $T_1$ (corps $K$) et 
$F$ sa primitive supposée élémentaire de tour $T_2$ et de corps $K'$
une extension algébrique de $K$. 
On commence par rajouter après les élements de $T_1$ les 
élements nécessaires de $T_2$ pour obtenir une tour $T$ par rapport
à laquelle $f$ et $F$ sont élémentaires (plus précisément $F$ sera
élémentaire quitte à autoriser des puissances fractionnaires
des variables exponentielles de $T_1$). Le théorème de structure
de Risch permet de faire cela, en effet on regarde pour chaque
élément de $T_2$ s'il est algébriquement indépendant des éléments
de $T_1$ ou non. S'il l'est, on le rajoute à la tour $T$, s'il
ne l'est pas alors dans le cas d'un logarithme il est élémentaire
et dans le cas d'une exponentielle, une de ses puissances est
élémentaire. Donc $F$ est bien une fraction rationnelle par rapport
aux éléments logarithmiques de $T_1$, aux racines $n$-ième
des éléments exponentiels de $T_1$ et à des éléments de $T_2$
dans cet ordre (le corps des constantes étant $K'$).

{\bf Première étape:}\\
Commençons par les éléments restant de $T_2$. Soit $X_k$ l'élément
au sommet de la tour $T$. La dérivée $f$ de $F$ par rapport à $X_k$
ne dépend pas de $X_k$. Donc soit $F$ ne dépend pas de $X_k$ et
on passe à la variable suivante, soit $X_k=\ln(v_k)$ est un logarithme
et $F=c_k \ln(v_k)+d_k$ avec $c_k \in K'$ et $v_k$ et $d_k$ 
indépendants de $X_k$. S'il
n'y a pas d'autres éléments restants de $T_2$, on passe à la 2ème étape.
Sinon soit $X_{k-1}$ la variable suivante 
(juste en-dessous de $X_k$ dans la tour).
En dérivant, on a~:
\[ F'= c_k \frac{v_k'}{v_k} + d_k' = f\]
Supposons que $v_k$ dépende de $X_{k-1}$, on fait alors un raisonnement 
analogue à celui de la preuve du théorème de structure de Risch, en décomposant
$v_k$ en produit/quotient de facteurs sans multiplicités $v_k=\prod P_j^j$
et en écrivant $d_k=N/D$ on a~:
\[\left(\prod_j P_j \right) \frac{N' D - N D'}{D^2} \]
est un polynôme en $X_{k-1}$. On en déduit comme précédemment que
$D=1$, $N'=d_k'$ est indépendant de $X_{k-1}$. Comme on a supposé que
$v_k$ dépend de $X_{k-1}$, $X_{k-1}=\exp(Y_{k-1})$ est alors une 
exponentielle, $N=d_k$ ne dépend pas de $X_{k-1}$ et l'un des $P_j=X_{k-1}$
(sinon tous les $P_j$ seraient constants en $X_{k-1}$ donc $v_k$ aussi).
On élimine alors la variable $X_{k-1}$ en écrivant 
$\ln(v_k)=jY_{k-1}+\ln(w_k)$, avec $Y_{k-1}$ et $w_k$ élémentaires et
indépendants de $X_{k-1}$.

Si $v_k$ est indépendant de $X_{k-1}$, alors $d_k'$ aussi donc
soit $d_k$ est indépendant de $X_{k-1}$ et on passe à la variable
suivante, soit $X_{k-1}$ est un logarithme et 
$d_k=c_{k-1}\ln(v_{k-1})+d_{k-1}$.
En continuant pour toutes les variables restantes de $T_2$, on obtient
\[ F=\sum_k c_k \ln v_k +d \]
avec $d$ et $v_k$ élémentaires pour $T_1$ (avec exponentielles
modifiées en en prenant une racine $n$-ième) et $K'$.

{\bf Deuxième étape}
Il s'agit de montrer que pour les exponentielles, il n'est en fait pas
nécessaire de prendre de racines $n$-ième. La compréhension
de cette étape demande
un peu de familiarité avec l'algorithme de Risch (cf. infra).
On va faire la preuve pour la variable au sommet de la tour $T_1$ si
c'est une exponentielle. On verra dans le déroulement
de l'algorithme de Risch que pour les autres variables, il y a
appel récursif de l'algorithme d'intégration, donc traiter
la variable au sommet suffira.
Soit donc $\exp(Y)$ la variable au sommet de la tour $T_1$, on note
$X=\exp(Y/n)$ la racine $n$-ième de cette variable qui est utilisée
pour exprimer $F=\sum c_k \ln v_k + N/D$ comme une fraction
rationnelle en $X$ alors que $f=F'$ est une fraction rationnelle en $X^n$.
On a donc~:
\[ \sum c_k \frac{v_k'}{v_k} + \frac{N}{D}' 
=f=\mbox{fraction rationnelle en }(X^n) \]
Notons que le fait que $X$ soit une exponentielle est essentiel, 
car par exemple l'intégrale d'une fraction rationnelle dépendant de $x^n$ 
comme $x^3$ ou $1/(x^3-1)$ ne s'exprime pas en fonction de $x^3$.
On traite d'abord la partie polynomiale généralisée de $f$ en $X^n$:
\[ \sum_{j\in \Z} a_j (X^n)^j\]
Son intégrale est un polynôme généralisé, éventuellement dépendant
de $X$, soit $\sum_{j\in \Z} A_j X^j$. On dérive, et on obtient
pour $k$ non multiple de $n$, $A_k Y/n+A_k'=0$ dont $A_k=0$ est
solution. La partie polynôme généralisé ne dépend donc que de $X^n$.
On effectue aussi les intégrations par parties pour réduire le 
dénominateur de $f$ à un polynôme sans facteurs multiples (réduction
de Hermite), ce qui se fait en introduisant des fractions rationnelles 
en $X^n$ uniquement. Reste la partie logarithmique. On utilise le critère
du résultant, les coefficients des logarithmes sont les racines 
$c_k$ du polynôme en $t$
\[ \mbox{Res}_X (D,N-tD') \]
où ces racines doivent être indépendantes de $x$ (puisque $F$ existe)
et les $v_k$ correspondants sont égaux à
\[ \mbox{gcd}(D,N-c_k D') \]
Or comme $X$ est une exponentielle, $D'$ est un polynôme en
$X^n$, de même que $D$ et $N$, donc $v_k$ est un polynôme
en $X^n$.

{\bf Troisième étape}
Il reste enfin à montrer que seuls les $c_k$ et $v_k$ nécessitent
une extension algébrique de $K$. Ceci est encore une cons\'equence
de l'algorithme de Risch, la construction
de la partie polynomiale (éventuellement généralisée) et de la 
partie fractionnaire ne font en effet intervenir que des coefficients
dans le corps $K$.

\section{L'algorithme de Risch} \label{sec:risch}
On suppose dans la suite qu'on s'est ramené à une fraction rationnelle
par rapport à une tour de variables (où on a effectué les simplifications
évidentes $\ln \circ \exp$, ainsi que $\exp \circ \ln$, dans le
premier cas en extrayant les facteurs évidents en les variables
précédentes exponentielles, dans le deuxième cas en extrayant la
partie linéaire à coefficient entier en les variables logarithmes
précédentes).
On note $X$ la variable au sommet de la tour et $N_0/D_0$ l'écriture
de la fonction élémentaire comme fraction irréductible avec
$N_0$ et $D_0$ polynômes en $X$.

{\bf Exemples}\\
\begin{eqnarray*}
\int (2x^2+1) e^{x^2} & X=e^{x^2} & N_0=(2x^2+1) X, D_0=1 \\
\int \frac{x \ln(x)}{x+\ln(x)} & X=\ln(x) & N_0=xX, D_0=x+X
\end{eqnarray*}

La première étape va consister à se ramener à un dénominateur sans facteurs
multiples. Elle est analogue au cas des fractions
rationnelles de $x$ et est basée sur l'identité de Bézout entre
$P$ et $P'$ vu comme polynômes en la variable du haut de la tour. 
Il apparait toutefois une difficulté pour les
extensions exponentielles, à savoir que $X=e^f$ et $X'=f' X$
ne sont pas premiers entre eux comme polynômes en $X$, on devra
traiter le pôle 0 d'une fraction rationnelle en une exponentielle $X$ comme
on traite l'intégration d'un polynôme en $x$.
Si $P$ est sans facteurs multiples et premier avec $X$, alors
$P(X)$ et $P(X)'=f' X P'(X)$ vu comme
polynômes en $X$ n'ont pas de facteurs en commun.

On commence donc, si $X$ est une exponentielle et $D_0$ un
multiple de $X$, par appliquer Bézout pour décomposer la fraction $N_0/D_0$
en~:
\[ \frac{N_0}{D_0}
=\frac{N_1}{D_1} + \frac{P}{X^{k} } , \quad \mbox{gcd}(X,D_1)=1, D_0=X^k D_1\]
On isole aussi la partie polynômiale en effectuant
la division euclidienne de $N_0$ par $D_0$ (ou de $N_1$ par $D_1$ si $X$
est une exponentielle),
on obtient alors une écriture sous la forme~:
\[ \frac{N}{D} + \sum_j a_j X^j\]
où la somme sur $j$ est finie et porte sur des entiers positifs ou nul 
si $X$ n'est pas une exponentielle, ou sur des entiers relatifs si $X$
est une exponentielle.

On effectue la même écriture sur la partie fractionnaire de $F$,
et en identifiant les parties polynomiales et éventuellement la partie
polaire en 0 si $X$ est une exponentielle, on peut séparer l'intégration
en 2 parties: intégration de la partie polynomiale (généralisée)
et intégration de la partie fractionnaire propre.

{\bf Exemples}
\begin{itemize}
\item $ (2x^2+1) e^{x^2} = 0+(2x^2+1)X$ est un polynôme,
\item 
\[ \frac{x \ln(x)}{x+\ln(x)} = \frac{xX}{x+X}=-\frac{x^2}{x+X}+x\]
la partie polynomiale est $x$ (de degré 0 en $X$), la partie fractionnaire
est $-x^2/(x+X)$
\item 
\[ \frac{x(e^{2x}+1)}{e^x(e^x+1)^2}=\frac{x(X^2+1)}{X(X+1)^2}
= -\frac{2x}{(X+1)^2} + xX^{-1}\]
la partie polynôme généralisé est $xX^{-1}$
\end{itemize}

\subsection{Intégration d'une fraction propre}
\subsubsection{Réduction sans facteurs multiples}
On factorise $D$ en $\prod_i P_i^i$ avec $P_i$ sans facteurs multiples 
(et les $P_i$ premiers entre eux 2 \`a 2) et on décompose
en éléments simples relativement à cette factorisation (en appliquant
Bézout)~:
\[ \frac{N}{D} = \sum_{i>0} \frac{N_i}{P_i^i} \]
Pour chaque polynome $P_i$, on applique Bézout à $P_i$ et $P'_i$~:
\[ N_i = A_iP_i+B_iP'_i \Rightarrow \frac{N_i}{P_i^i}=\frac{A_i}{P_i^{i-1}}
+ \frac{B_iP_i'}{P_i^i}\]
on intègre par parties le second terme
\[ \int \frac{N_i}{P_i^i} = \int \frac{A_i}{P_i^{i-1}}
- \frac{B_i}{(i-1)P_i^{i-1}} + \int \frac{B_i'}{(i-1)P_i^{i-1}}  \]
on rassemble les deux int\'egrales ayant $P_i^{i-1}$ au dénominateur
et on recommence jusqu'à avoir une puissance 1 au dénominateur. Il reste
alors \`a int\'egrer une somme de fractions du type $N/D$ avec
$D$ et $D'$ premiers entre eux.

{\bf Exemple}\\
On reprend le dernier exemple de la section précédente pour
éliminer la puissance 2 au dénominateur:
$N_2=2x$ et $P_2=(X+1)$ avec $X=e^x$. On a $P_2'=X$, donc $A_2=2x$ et
$B_2=-2x$~:
\[ \int \frac{2x}{(X+1)^2} =\int \frac{2x}{P_2} + 
\int \frac{-2x P_2'}{P_2^2} = \int \frac{2x}{P_2} + \frac{2x}{P_2}
- \frac{2}{P_2}\]
il reste donc à intégrer $(2x-2)/(e^x+1)$.

\subsubsection{La partie logarithmique}
Comme on l'a vu lors de la preuve du théorème de structure de Risch,
si on dérive une fraction en $X$, le dénominateur de la dérivée ne
peut se décomposer qu'en produit de facteurs de multiplicité supérieure
ou égale à 2. Il en résulte que la fraction à intégrer résiduelle (encore
notée $f=N/D$) après l'étape de réduction ci-dessus ne peut provenir que de la
dérivation de $F=\sum_k c_k \ln (v_k)$~:
\[ f=\frac{N}{D}=F'= (\sum_k c_k \ln (v_k))'= \sum_k c_k \frac{v_k'}{v_k}\]
En identifiant les décompositions
en éléments simples de $F'$ et $f$, on montre également que 
les $v_k$ divisent $D$, plus précisément on peut imposer aux $v_k$
d'être premiers entre eux 2 à 2 et dans ce cas $D=\prod v_k$. 
Donc~:
\[ \sum_k c_k \frac{v_k'}{v_k} = \frac{N}{\prod_k v_k}=\frac{N}{D}\]
et~:
\[ N = \sum_k c_k v_k' \prod_{j\neq k} v_j \]
Soit $t$ un paramètre, formons le polynôme $N-tD'$~:
\[ N-tD' = \sum_k \left( (c_k -t) v_k' \prod_{j\neq k} v_j \right) \]
donc le pgcd en $X$ des polynômes $N-tD'$ et $D$ est~:
\begin{itemize}
\item si $t$ n'est égal à aucun des $c_k$, $N-tD'$ est premier
avec $v_k$ pour tout $k$ car $v_k$ divise
$\sum_{l \neq k} (c_l -t) v_l' \prod_{j\neq l} v_j$
et $v_k'\prod_{j\neq k} v_j $ est premier avec $v_k$. Donc
le pgcd est 1.
\item si $t$ est égal à l'un des $c_k$, alors le pgcd est le produit
des $v_k$ tels que $c_k=t$ (notons que dans ce cas on peut
rassembler ces $v_k$ à l'intérieur d'un même logarithme)
\end{itemize}
Considérons le polynôme $R$ de la variable $t$ égal au résultant par rapport
à $X$ des polynômes $D$ et $N-tD'$ (rappelons qu'il s'agit du
d\'eterminant du syst\`eme lin\'eaire $AD+B(N-tD')=1$
o\`u les inconnues sont les coefficients des polyn\^omes $A$ et $B$, 
ce d\'eterminant est nul si et seulement si le syst\`eme n'a pas
de solution donc si et seulement si $D$ et $N-tD'$ ne sont pas
premiers entre eux), alors ce polynôme en $t$
s'annule si et seulement si $t=c_k$. 
On cherche les racines $c_k$ en $t$ de ce polynôme,
elles doivent être indépendantes de $x$ si $F$ est élémentaire,
et dans ce cas la primitive $F$ de $f=N/D$ vaut
\[ F=\sum_{c_k \mbox{ racine de } R} c_k \ln(\mbox{gcd}(N-c_k D',D)) \]

{\bf Exemples}
\begin{itemize}
\item
\[ \frac{2x-2}{e^x+1}, \quad D=X+1, D'=e^x=X, \quad N-tD'=2x-2-tX \]
On calcule $R=-2*x-t+2$, l'unique racine est $t=2-2x$ qui n'est
pas constante donc cette fonction n'admet pas de primitive élémentaire.
\item 
\[ \frac{(2x^2-x-2)X-1}{X^2+(x+1)X+x}, \quad X=\exp(x^2+x)\]
On a $D'=2(2x+1)X^2+(1+(2x+1)(x+1))X+1$
\[ R=-(2\*x-1)\*(x+1)\*(2\*x+1)\*(x-1)^2\*(t+1)\*(t-1) \]
les racines en $t$ sont constantes et égales à 1 et -1, donc $c_1=1$
et $v_1=$gcd$(N-D',D)=X+1$ et $c_2=-1$, $v_2=$gcd$(N+D',D)=x+X$
donc~:
\[ \int \frac{(2x^2-x-2)X-1}{X^2+(x+1)X+x} = \ln(X+1)-\ln(x+X)\]
\end{itemize}

{\bf Remarque importante}\\
Pour les extensions exponentielles ou logarithmiques, 
la d\'eriv\'ee de la partie logarithmique
calcul\'ee comme ci-dessus contiendra en g\'en\'eral 
une partie enti\`ere constante par rapport \`a $X$, il faut
donc retirer cette partie enti\`ere \`a la partie polynomiale.

\subsection{La partie polynomiale (généralisée)}
On doit résoudre~:
\[ (\sum_j A_j X^j)'=\sum_j a_j X^j \]
avec une somme sur $j \in\Z$ si $X$ est une exponentielle et
$j\in \N$ sinon.

Si $X=x$, $j\geq 0$ et la résolution est immédiate: on prend $A_0=0$ et 
$A_{j+1}=a_{j}/(j+1)$.

\subsubsection{Extension logarithmique}
Si $X=\ln(Y)$ est un logarithme, $j \geq 0$ et on doit résoudre~:
\[ \sum_{j\geq 0} (A_j'+(j+1)A_{j+1} \frac{Y'}{Y}) X^j = \sum_j a_j X^j \]
Soit $k$ la plus grande puissance non nulle de $f$ ($a_j=0$ 
si $j>k$ et $a_k\neq 0$). Pour $j>k$, on a~:
\[ A_j'+(j+1)A_{j+1} \frac{Y'}{Y}  =0 \]
On résout pour des valeurs de $j$ décroissante, pour $j$ suffisamment
grand, on a $A_{j+1}=0$ car la somme sur $j$ est finie, donc $A_j$
est constant. Si $A_j \neq 0$, alors au rang $j-1$, on a 
$A_{j-1} ' = -j A_j Y'/Y $ qui n'admet pas de solutions car 
$A_{j-1}$ ne peut pas dépendre de $X=\ln(Y)$. On en déduit que pour
$j>k+1$, on a $A_j=0$ et $A_{k+1}$ est constant. En fait la
valeur constante de $A_{k+1}$ sera déterminée par une condition
de compatibilité en résolvant l'équation au rang du dessous.
On continue la résolution de 
\[ A_j'+(j+1)A_{j+1} \ln(Y)'  = a_j \]
par valeur décroissante de $j$, à chaque
rang on va déterminer $A_j$ à une constante près en résolvant
un problème d'intégration (par appel récursif de l'algorithme
de Risch, mais si $j \neq 0$ sans autoriser l'ajout de nouveaux 
logarithmes sauf $\ln(Y)$)
et la valeur de la constante de $A_{j+1}$ (on fait varier $A_{j+1}$
de la constante nécessaire pour absorber le terme en $\ln(Y)$
qui apparait lors de l'appel récursif de Risch).
Au rang 0, on est ramené à un problème d'intégration avec
une variable de moins (la constante
indéterminée dans $A_1$ peut par exemple être choisie comme
le coefficient constant de $\ln(Y)$ s'il en apparait un en intégrant).

{\bf Exemple}\\
$X=\ln(x^2+1)$ et on cherche l'intégrale de $X^2$. On a donc $A_3$
est constant,
\[ A_2' + 3 A_3 \ln(x^2+1)' = 1\]
La primitive de 1 est élémentaire et ne fait pas intervenir de $\ln$
donc $A_3=0$ et $A_2=x+C_2$. Au rang 1, on a~:
\[A_1' + 3 x \frac{2x}{x^2+1} + C_2 \ln(x^2+1)' = 0\]
On calcule la primitive de $6x^2/(x^2+1)$ qui doit être une fraction
rationnelle à un $C\ln(x^2+1)$ près, on voit que ce n'est pas le cas
donc $X^2$ n'admet pas de primitive élémentaire.
Remarque: si on avait voulu intégrer $X$ au lieu de $X^2$, la même
méthode montre que la primitive existe, car au rang 0 il n'y
a plus de contraintes sur les $\ln$ qu'on peut rajouter.

\subsubsection{Extension exponentielle}
Si $X=\exp(Y)$ est une exponentielle, on doit résoudre~:
\[ \sum_{j} (A_j'+j Y'A_{j}) X^j = \sum_j a_j X^j \]
Ceci va se faire degré par degré~:
\begin{equation} \label{eq:rischdiffeq}
 A_j'+j Y' A_{j} = a_j
\end{equation}
{\bf Exemple}\\
Pour calculer $\int a(x) \exp(x^2)$, on a $j=1$, et on doit résoudre
l'équation différentielle~:
\[ A_1'+2xA_1= a(x)\]

Pour $j=0$, il suffit de faire un appel récursif à l'algorithme de Risch,
mais pour $j\neq 0$, la situation se complique!
Notons $Z$ la variable situ\'ee juste en-dessous de $X$ dans la tour
de variables (dans l'exemple ci-dessus $Z=x$), il s'agit de r\'esoudre~: 
\begin{equation} \label{eq:rischdiffeq2}
y'+f y=g
\end{equation}
avec $f$, $g$ \'el\'ementaires par rapport \`a une tour dont le
variable au sommet est $Z$, on cherche $y$ \'el\'ementaire par rapport
\`a cette tour (ici $f=jY'$ est une d\'eriv\'ee mais dans certains
cas nous devrons r\'esoudre par appel r\'ecursif des \'equations
du type ci-dessus o\`u $f$ ne sera pas une d\'eriv\'ee).

{\bf \'Elimination des d\'enominateurs}\\
Soit $P$ un facteur irréductible du d\'enominateur de $y$, notons 
$\alpha<0$ la valuation de $y$ par rapport \`a $P$, 
$\beta$ celle de $f$, $\gamma$ celle de $g$. 
Si $P$ n'est pas une exponentielle,
la valuation de $y'$ est $\alpha-1$, celle de $ f y $ est $\alpha +\beta $. 
Si $\beta \neq -1$, 
il n'y a pas de simplification possible dans le membre de gauche
donc $\alpha + \min(\beta,-1) =\gamma$. Autrement dit, si 
$\beta \geq 0$ alors $\alpha=\gamma+1$ et si $\beta<-1$ 
alors $\alpha=\gamma-\beta$.
On observe que $\gamma<0$ donc
$P$ est un facteur du d\'enominateur $g_d$ de $g$. De plus, on va montrer
que la valuation $\alpha$ de $P$ dans $y$ est l'oppos\'e de celle
de $P$ dans~:
\begin{equation} \label{eq:defD}
D=\frac{\mbox{gcd}(g_d,\partial_Z g_d)}{\mbox{gcd}(c,\partial_Z c)}, 
\quad c=\mbox{gcd}(f_d,g_d)
\end{equation}
En effet, si $\beta \geq 0$, $P$ ne divise pas $f_d$ donc ne divise
pas $c$, donc la valuation de $P$ dans $D$ est $-\gamma-1$. Si $\beta < -1$,
alors $\alpha=\gamma - \beta <0$ entraine $-\gamma > -\beta$ donc la
valuation de $P$ dans $c$ est $-\beta$ et la valuation de $P$ dans $D$
est $-\gamma-1 - (-\beta-1)$.

Si $\beta=-1$, s'il n'y a pas de simplifications dans le membre
de gauche pour les termes de plus petite puissance en $P$, alors 
$\alpha=\gamma+1$. S'il y a simplification,
on d\'ecompose en \'el\'ements
simples (avec B\'ezout) puis on ordonne par puissances croissantes
de $P$~:
\[y= N_1 P^\alpha +..., f= N_2 P^{-1}+...,\]
avec $N_1,N_2$ de degré plus petit que $P$, puis on remplace dans 
(\ref{eq:rischdiffeq2}). On cherche les termes de valuation $\alpha-1$
en $P$ qui doivent se simplifier~:
\[ \alpha N_1 P' P^{\alpha-1} + N_2 P^{-1} N_1 P^\alpha =0 \]
donc~:
\[ N_2 = -\alpha P' \]
ce qui d\'etermine $\alpha$.

{\bf Récapitulons}\\
Si $f$ est une dérivée, alors $\beta=-1$ est exclus et on peut
appliquer (\ref{eq:defD}) pour déterminer $D$. Si $f$ n'est
pas une dérivée, on calcule les facteurs de degré 1 de $f_d$~:
\[ f_1=\frac{f_d}{\mbox{gcd}(f_d,\partial_Z f_d)} \]
on décompose $f$ par Bézout en isolant la partie $N/f_1$
les $\alpha$ possibles sont alors les racines entières (en $t$)
du résultant en $Z$ de $N-tf_1'$ et $f_1$, ils correspondent aux
facteurs gcd$(N-\alpha f_1',f_1)$ que l'on retire de $f_d$ pour
appliquer (\ref{eq:defD}).

{\bf Exemple}\\
Reprenons $y'+2xy=a(x)$. Si $a(x)=1$ (résolution de $\int \exp(x^2)$),
ou plus généralement si $a(x)$ est un polynôme,
alors $D=1$. Si $a(x)=1/x^2$, on trouve $D=x$ et on pose $y=xz$,
donc $x^2(xz'+z)+2x^4z=1$ soit $x^3z'+(2x^4+1)z=1$.

Reste le cas o\`u $Z$ est une exponentielle et $P=\exp(z)$. On reprend
le m\^eme raisonnement, $y'$ a pour valuation $-\alpha<0$, $fy$ a pour
valuation $-\beta-\alpha$, donc si $\beta > 0$,
$\alpha=\gamma$ et si $\beta<0$, $\alpha=\gamma-\beta$.
Si $\beta=0$, s'il n'y a pas de simplifications du terme de plus bas
degr\'e, on est ramen\'e au cas pr\'ec\'edent. 
Si $\beta=0$ et s'il y a simplification des termes de plus
bas degr\'e en $Z$, notons $f_0$ le coefficient constant de $f$ 
par rapport \`a $Z$ et $y_{\alpha}$ le coefficient de $Z^{\alpha}$
dans $y$, on a 
\[ y_\alpha ' + (\alpha z' + f_0) y_\alpha =0 \]
donc~:
\[ y_\alpha= \exp(-\alpha z-\int f_0)\]
Comme $y_\alpha$ est \'el\'ementaire et ind\'ependant de $Z$
on en d\'eduit par le th\'eor\`eme de structure de Risch
que $-\alpha z -\int f_0$ est combinaison lin\'eaire \`a coefficients
rationnels des logarithmes et des arguments des exponentielles de la tour,
de plus le coefficient de $z$ doit \^etre nul pour que $y_\alpha$ soit
ind\'ependant de $Z$, ce qui impose la valeur de $\alpha$ (apr\`es avoir
r\'esolu r\'ecursivement le probl\`eme d'int\'egration pour $f_0$)

{\bf Majoration du degr\'e du num\'erateur de $y$}\\
En multipliant $y$ par $D Z^{-\alpha}$, puis en réduisant au
même dénominateur,
on se ram\`ene alors à une équation différentielle à coefficients
polynomiaux par rapport \`a la variable $Z$ dont l'inconnue est un polynôme 
$N$~:
\begin{equation} \label{eq:rischdepol}
 R N' + S N = T
\end{equation}
On va chercher une majoration sur le degr\'e possible de $N$ puis
utiliser l'identit\'e de B\'ezout pour simplifier
cette \'equation. 

On \'ecrit maintenant $N=\sum_{k=0}^n N_k Z^k$ et on remplace, 
il y a \`a nouveau trois cas selon le type de $Z$.

{\bf Si $Z=x$: cas exponentielle rationnelle}\\
Donc $Z'=1$, le degré de $RN'$ est $r+n-1$ (si $N$ est non constant
c'est-à-dire si $T$ n'est pas un multiple de $S$), le degré de
$SN$ est $s+n$. Si $r-1\neq s$, on en déduit que~:
\[ n=t-\max(r-1,s)\]
Si $r-1=s$, on peut avoir
une simplification du terme de plus haut degré $s+n$ (sinon
on est dans le cas précédent) si $n R_r =S_s $
d'où on déduit le degré $n$ de $N$.

Par exemple, pour $y'+2xy=T$ ou pour $x^3z'+(2x^4+1)z=1$ on a $r=s-1$ donc
$n+s=t$, donc pas de solution dans le deuxième cas, dans le premier cas
il ne peut y avoir de solutions que si $t \geq s$, en particulier
il n'y a pas de solution pour $t=1$, on a donc démontré que $\int \exp(x^2)$
n'admet pas de primitive élémentaire.

{\bf Si $Z=\exp(z)$: cas exponentielle d'exponentielle}\\
Ici les $N_k$ peuvent ne pas être constants, on a~:
\[ N'=\sum_{k=0}^n (N_k'+kN_k z') Z^k\]
Comme on l'a déjà observé, $N_n'+n N_n z'\neq 0$, donc le
degré de $N'$ est égal au degré de $N$. On a donc trois cas~:
\begin{itemize} 
\item si $r\neq s$, alors $n=t-\max(r,s)$
\item si $r=s$ et les termes de plus haut degré du membre de gauche ne
se simplifient pas, alors, $n=t-r=t-s$.
\item si $r=s$ et s'il y a simplification, alors~:
\[ R_r(N_n'+nN_nz')+S_sN_n=0 \]
donc~:
\[ N_n' + (\frac{S_s}{R_r}+nz')N_n = 0\]
et~:
\[ N_n = C \exp(-nz-\int \frac{S_s}{R_r}) \]
On appelle alors l'algorithme de Risch avec une variable de moins ($S_s$
et $R_r$ ne dépendent plus de $Z$) pour calculer $I=\int S_s/R_r$. 
Il s'agit alors de trouver $n$ tel que l'exponentielle précédente
soit élémentaire et indépendante de la variable $Z$. Le théorème
de structure de Risch implique que $-nz-\int S_s/R_r$ est combinaison 
linéaire à coefficients rationnels des logarithmes et des arguments 
des exponentielles de autres variables de la tour (jusqu'à $z$ non compris).
Ceci permet de déterminer $n$ de manière unique (c'est le coefficient
rationnel de $\int S_s/R_r$ en $z$).
\end{itemize}

{\bf Si $Z=\ln(z)$: exponentielle de logarithme}\\
Ici aussi, les $N_k$ peuvent ne pas être constants, on a~:
\[ N'=\sum_{k=0}^n (N_k'Z^k+kN_k \frac{z'}{z} Z^{k-1})\]
Si $N_n$ n'est pas constant, le terme de plus haut degré de 
$RN'$ est $N_n' R_r Z^{n+r}$, si $N_n$ est constant, 
le terme de plus haut degré de $RN'$ est $R_r(nN_nz'/z+N_{n-1}') Z^{r-1}$ 
qui est non nul (sinon $z'/z=CN_{n-1}'$ et $z=\exp(CN_{n-1})$ serait 
une exponentielle).
Le terme de plus haut degré de $SN$ est $N_n S_s Z^{n+s}$.
\begin{itemize}
\item Si $r<s$ ou si $r=s$ sans simplifications,
alors $n=t-s$.
\item Si $r>s+1$ ou si $r=s+1$ sans simplifications,
alors deg$(N')=t-r$ donc $n=t-r$ ou $n=t-r+1$.
\item Si $r=s+1$, et s'il y a simplifications, alors $N_n$ est constant et~:
\[ R_r(nN_nz'/z+N_{n-1}')+ S_s N_n = 0 \]
alors $N_{n-1}=C (-\int N_n S_s/R_r -n N_n \ln(z))$
doit être élémentaire et indépendante de $Z$ donc $\int S_s/R_r$
est élémentaire, on détermine $n$ en éliminant le coefficient de 
$Z=\ln(z)$ provenant de $\int S_s/R_r$.
\item Si $r=s$, et s'il y a simplification des termes 
de plus haut degré du membre de gauche, 
alors $N_n' R_r+N_n S_s=0$ donc $N_n=\exp(-\int S_s/R_r)$
est élémentaire et indépendante de $Z$. On peut donc changer
d'inconnue $N=N_n M$ sans changer le fait que $M$ est un polynôme de
même degré que $N$. On se ramène alors à une équation du même type
\[ RM'+(S-R \frac{S_s}{R_r})M= \frac{T}{N_n}\]
mais avec $s$ diminué de 1 au moins.
\end{itemize}

{\bf R\'eduction (algorithme SPDE de Rothstein)}\\
On observe d'abord que si $R$ et $S$ ont un facteur
en commun, alors ce facteur divise $T$ car $N'$ et $N$ sont des polyn\^omes
en $Z$. On peut donc quitte \`a simplifier par gcd$(R,S)$ se ramener
au cas o\`u $R$ et $S$ sont premiers entre eux, il existe donc deux
polyn\^omes $U$ et $V$ tels que~:
\begin{equation} \label{eq:rischdebezout}
RU+SV=T, \quad \mbox{deg}(V)< \mbox{deg}(R)
\end{equation}
En soustrayant (\ref{eq:rischdebezout}) de (\ref{eq:rischdepol}), 
on montre que $R$ divise $N-V$. Soit $H=(N-V)/R$. Alors $N=RH+V$ donc
\[ R (RH'+R'H+V')+SRH+SV= T=RU+SV\]
donc apr\`es simplification par $SV$ et division par $R$, 
$H$ v\'erifie l'\'equation~:
\[ R H' + (S+R') H = U - V'\]
C'est une \'equation du m\^eme type mais avec deg$(H)$=deg$(N)$-deg$(R)$
ou $H=0$ (si $N=V$).
Donc si deg$(R)>0$, au bout d'un nombre fini d'\'etapes on doit 
tomber sur un second membre nul ou des simplifications de $R$ avec $S+R'$
telles que $R$ simplifié soit constant en $Z$.

{\bf R\'esolution}\\
Si $R$ est constant par rapport \`a $Z$, 
on simplifie par $R$ et on doit r\'esoudre 
\[ N'+SN=T \]
Si $S=0$, c'est un probl\`eme d'int\'egration. Supposons donc que
$S\neq 0$. Si $S$ est non constant par rapport \`a $Z$ ou si
$Z=x$, le degr\'e de $N'$ est strictement inf\'erieur 
au degr\'e de $SN$, on peut donc facilement r\'esoudre.
Reste le cas o\`u $S=b$ est constant non nul par rapport \`a $Z$ et $Z$ est
une exponentielle ou un logarithme.

{\bf Si $Z=\exp(z)$}\\
On a alors doit alors r\'esoudre 
\[ N_k'+ k N_k z' + b N_k=T_k \]
c'est une \'equation diff\'erentielle de Risch mais avec une variable de 
moins.

{\bf Si $Z=\ln(z)$}\\
On doit alors r\'esoudre 
\[ N_k'+ (k+1) N_{k+1} \frac{z'}{z} + b N_k =T_k \]
c'est aussi une \'equation diff\'erentielle de Risch avec une
variable de moins.

{\bf Exemple}\\
Voyons comment on intègre $x^n$ avec $n$ un paramètre par l'algorithme
de Risch (cela illustre les possibilités couvertes par l'algorithme
mais aussi l'efficacité des méthodes traditionnelles d'intégration
lorsqu'elles s'appliquent).
On écrit d'abord $x^n=e^{n \ln(x)}$, donc la tour de variables
est $\{ x, Z=\ln(x), X=e^{n \ln(x)}\}$, il s'agit donc d'intégrer
$X$ qui est un polynôme généralisé. On cherche donc $A_1$ solution
de l'équation différentielle de Risch 
\[ A_1'+ n /x A_1=1 \]
Par rapport à $Z=\ln(x)$ la fonction $f=n/x$ est un polynôme, donc on
applique le dernier cas ci-dessus, $A_1$ est aussi indépendant de $\ln(x)$
et on se ramène à résoudre la même équation mais avec comme variable
principale $x$ et non $Z$. Cette fois, il y a un dénominateur $x$ en $f$.
Si $A_1$ possède un dénominateur, il faut qu'il y ait annulation
du terme de plus bas degré en $x$ car le second membre n'a pas de
dénominateur, on obtient $n+\alpha=0$ qui n'a pas de solution, donc
$A_1$ est un polynôme en $x$ et l'équation se réécrit en~:
\[ xA_1'+nA_1=x\]
On majore alors le degré en $x$ de $A_1$ par 1, car il ne peut pas y avoir
d'annulation de terme de plus grand degré. Ensuite, on peut appliquer
l'algorithme SPDE de Rothstein pour réduire le degré, ou ici conclure
à la main, $x$ divise $nA_1$ donc $A_1=Cx$ qu'on remplace et $C=1/(n+1)$.
Finalement, $A_1=x/(n+1)$ et $\int x^n=x/(n+1) \* x^n$.

%\section{Cas des extensions plus générales}

\section{Quelques références} \label{sec:rischref}
\begin{itemize}
\item M. Bronstein:\\
Symbolic Integration I, Transcendental functions, Springer

\item M. Bronstein:\\
Integration tutorial, \\
\verb|http://www-sop.inria.fr/cafe/Manuel.Bronstein/publications/mb_papers.html|

\item J.H. Davenport, Y. Siret, E. Tournier:\\
Calcul formel: Syst\`emes et algorithmes 
de manipulations  alg\'ebriques

\item R. Risch: \\
les références des articles originaux de Risch sont dans
le ``Integration tutorial'' de Bronstein.

\item B. Trager:\\
PHD thesis MIT, 1984

\item On peut lire en clair le code source de l'implémentation en MuPAD
(sous Unix, désarchiver le fichier {\tt lib.tar} du répertoire
{\tt /usr/local/MuPAD/share/lib} et regarder dans le sous-répertoire
{\tt lib/INTLIB})

\end{itemize}

{\bf Remerciements}\\
Je remercie Renée De Graeve, Roland Bacher et Gérard Vinel pour leur patiente
relecture et corrections de ce manuscrit.

\end{document}


\end{itemize}