\documentclass[a4paper,12pt]{amsart}
\usepackage{kbexo}


%%%%%%%%%%%%%%%%%%%%%
%% Alice's packages
%%%%%%%%%%%%%%%%%%%%%
\usepackage{xcolor}

%%%%%%%%%%%%%%%%%%%
%% Alice's macros
%%%%%%%%%%%%%%%%%%%
\newcommand{\comment}[1]{{\color{gray}#1}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}

\def\pow{\^{}\hskip0pt}

\course{Algèbre et calcul formel -- Agrégation}
\num{2}

\begin{document}
\exotitle[Équations, polynômes]

\section{Équations, dérivation, intégration}

Pour résoudre une équation, ou un système d'équations, on peut utiliser la
commande {\tt solve}. Attention ! Pour cette fonction, comme pour la plupart
des fonctions de Sage, il faut d'abord définir les variables.

\bigskip

\Q Essayer la commande

{\tt solve([x-1==0],x)}

Ok, ça marche. Maintenant essayer

{\tt solve([t-1==0],t)}

La variable {\tt x} est une exception. Toute autre variable doit
absolument être déclarée au préalable.
{\tt t=var('t')}

{\tt solve([t-1==0],t)}

{\tt parent(t)}

La variable ainsi définie appartient donc à l'ensemble
{\tt Symbolic Ring}, qu'on peut noter {\tt SR}.

Si on fait {\tt parent(x)}, on voit que la variable {\tt x} est par
défaut dans {\tt Symbolic Ring}.

Taper

{\tt reset('t')}

puis

{\tt parent(t)}

On a effacé la variable {\tt t}.
\bigskip

\Q 
Dans {\tt Aide}, {\tt Sage Tutorial}, {\tt Basic algebra and
calculus}, faire les exercices des paragraphes {\sl Solving equations
exactly}, {\sl Solving equations numerically} puis {\sl Differentiation,
integration etc}.

\misctitle{Remarque} La commande {\tt solve} résout les équations dans $\CC$. Testez par exemple \begin{verbatim} solve(x^2 == -1,x). \end{verbatim} 
Pour résoudre des équations dans un corps fini, il faut procéder différemment (on verra ci-dessous comment trouver les racines d'un polynôme dans un corps fini).

\section{Anneaux et corps}
Sage connaît par défaut de nombreux anneaux et corps. Regardez par exemple les anneaux et corps suivants (en tapant leur nom et en validant)

{\tt CC}

{\tt RR}

{\tt QQ}

{\tt ZZ}

{\tt Integers(7)}

{\tt Integers(10)}

{\tt GF(5)}

{\tt GF(25)}

La commande {\tt GF} permet de définir un corps fini. Elle prend en argument une puissance d'un nombre premier. La syntaxe pour définir un corps fini est {\tt K.<a> = GF(25)}. Quand vous écrivez ça, sage définit $K$ comme étant le corps fini à 25 élément, et $a$ est un générateur de $K$. En particulier, sage représente tous les éléments de $K$ sous la forme {\tt x + a*y} où {\tt x} et {\tt y} vivent modulo $5$. Si on avait pris un corps fini à $5\hat{\ }k$ éléments, les éléments seraient des polynômes de degré $k-1$ en {\tt a}.

\Q
Par défaut, sage ne choisit par d'anneaux/corps précis pour un élément, tant qu'il n'a pas besoin de le faire. Testez par exemple

\noindent{\tt 1 in CC}

\noindent{\tt 1 in ZZ}

\noindent{\tt 1 in Integers(10)}

\noindent{\tt 1 in GF(25)}

\vspace{2mm}
\noindent Par contre

\vspace{2mm}

\noindent{\tt 1.5 in RR}

\noindent{\tt 1.5 in QQ}

\noindent{\tt 1.5 in Integers(5)}

\begin{verbatim}
K.<a> = GF(25)
a in K
a in CC
\end{verbatim}

\Q
On peut forcer une variable {\tt x} à appartenir à un anneau {\tt R} en faisant {\tt R(x)}. C'est une façon de préciser à sage qu'on ne s'intéresse qu'à cet anneau. La variable n'appartient alors plus forcément à tous les autres anneaux/corps comme avant. Testez

{\tt ZZ(1) in CC} \comment{(la réponse est {\tt True} car $\ZZ$ est inclus dans $\CC$)}

{\tt CC(1) in ZZ} \comment{(la réponse est {\tt False} car $\CC$ n'est pas inclus dans $\ZZ$)}


\noindent Bon, ça peut sembler logique, mais la logique s'arrête assez vite... Testez les 3 égalités entre {\tt GF(3)(1)}, {\tt CC(1)} et {\tt ZZ(1)}. La conclusion, c'est qu'il faut faire attention quand vous commencez à mélanger des variables de différents anneaux.

L’intérêt de forcer une variable à être dans un anneau précis devient plus clair quand on commence à faire des calculs

\vspace{2mm}

{\tt ZZ(2)\pow3}

{\tt (Integers(3)(2))\pow3}

\misctitle{Remarque} Les anneaux {\tt ZZ} et {\tt QQ} contiennent des éléments exacts. Si vous faites des calculs sur ces éléments, sage va augmenter la taille des éléments pour toujours les représenter de façon exacte (il n'y a pas de limite sur la taille des entiers). C'est pratique, mais ça peut devenir très lent si vous commencez à manipuler de gros entiers, ou des rationnels avec un gros numérateur et/ou dénominateur. Si vous n'avez pas besoin de précision exacte, vous pouvez utiliser {\tt RR}, qui ne fera les calculs qu'avec 53 bits de précision, mais plus rapidement.

\Q Écrivez une fonction {\tt puissance(x,k,n)} qui renvoie la valeur de $x^k \bmod n$. Mesurez le temps de votre fonction sur $(x,k,n) = (7,2\cdot 10^8,13)$ en faisant 
\begin{verbatim}
time puissance(7,2*10^8,13).
\end{verbatim}
Si votre fonction prend plus que quelques ms, essayez de comprendre pourquoi et améliorez-la.



\section{Polynômes}

Dans sage, toutes les valeurs sont définies en temps qu'éléments d'un
ensemble bien précis, que l'on retrouve grâce à la commande {\tt parent}, ou
bien {\tt type}.\footnote{Ce qui est un peu contradictoire avec le fait que $1$ soit à la fois dans {\tt CC}, {\tt ZZ} et {\tt GF(3)}, mais bon, c'est quand même bien pratique de ne pas avoir des notations différente pour $1$ dans chaque anneau...} 
Nous avons vu l'exemple des entiers, des listes, des nombres
rationnels, des réels, des corps finis, de $\ZZ/n\ZZ$.

Dans cet exercise, on va voir une nouvelle structure: les anneaux de polynômes.

\Q Tester

{\tt p=t\pow2-2; p}

Ça ne marche pas : il faut définir {\tt t}. Comme ci-dessus, si l'on
met {\tt x} plutôt que  {\tt t}, cela va fonctionner, mais $p$ ne
sera pas vraiment considéré comme un polynôme en {\tt x} et les
fonctions adaptées aux polynômes ne fonctionneront pas de la
même manière. En effet, {\tt x} est par défaut un élément de
{\tt Symbolic Rings}.

\bigskip

\Q
On va définir l'anneau de polynômes $\QM[x]$, et
explorer quelques fonctions définie sur cet anneau.

Expérimentez les commandes suivantes.

{\tt QQ} (C'est le corps $\QM$ des nombres rationnels)

{\tt Qx.<x>=PolynomialRing(QQ)}

Cette commande définit {\tt Qx} comme étant l'anneau de polynômes
$\QM[x]$ et la variable {\tt x} devient la variable $x$ de cet
anneau.

{\tt Qx}

{\tt parent(x)}

{\tt p=x\pow2-2; p}

{\tt p=Qx([-2,0,1]); p} \comment{(c'est une autre façon de définir le même polynôme)}

{\tt p.degree()}

{\tt p.is\_irreducible()}

{\tt factor(p)}

{\tt p.roots()}

{\tt p.roots?} \comment{(pour demander le mode d'emploi de la fonction)}

{\tt p.roots(ring=RealField())}

{\tt p(2); p[2]}

{\tt p.coefficients()}

{\tt p.coefficients(sparse=false)}

{\tt list(p)} \comment{(comme au dessus mais en plus court)}

On peut aussi définir $\RM[x]$ :

{\tt Rx.<x>=PolynomialRing(RR)}

Si on veut considérer $p$ comme un polynôme de $\RM[x]$,
on fait~:

{\tt p=Rx(p)}

Alors, la commande 
{\tt p.roots()}
donnera les racines de {\tt p} dans son corps de base, c'est-à-dire $\RM$.
%Nous verrons plus tard d'autres corps ou anneaux que $\QM$ et $\RM$.

\misctitle{Remarque}
Plus généralement, si l'on a défini un objet $A$, qui est un certain
ensemble ou structure, et si $a$ est un objet susceptible de définir
un élément de $A$, alors on définit cet élément par la commande
$A(a)$.

Par exemple, si $A=\ZM/n\ZM$ et si $a$ est un entier, alors $A(a)$ est l'élément de $\ZM/n\ZM$
défini par $a$.
Nous avions déjà utilisé cette construction, par exemple quand on a posé
ci-dessus
{\tt p=Qx([-2,0,1])}, nous avons défini un élément de {\tt Qx}
(c'est-à-dire $\QM[x]$) à partir d'une liste. De même, {\tt list(p)}
permet de définir une liste à partir du polynôme {\tt p}.
Nous retrouverons ce principe à maintes reprises. 

\Q
Il y a d'autres façons de définir les anneaux de polynômes. Dans {\tt Aide},
{\tt Sage tutorials}, faire les exercices de {\tt Polynomials}.

\Q
Expérimenter les commandes suivantes

{\tt PR=PolynomialRing(QQ,3,'a');PR}

{\tt p=a0+2*a1}

Problème ! Il faut donner un nom aux variables.

{\tt v=PR.gens();v}

{\tt p=v[0]+2*v[1];p}

\Q
Nous allons ici calculer toutes les solutions polynomiales
de degré inférieur ou égal à $2$ de l'équation différentielle
\begin{equation}\label{equa}
(3t-2)y''+2t^2y'-2(2t-1)y=0
\end{equation}
en utilisant un polynôme à coefficients indéterminés.

Nous allons ici utiliser la commande {\tt solve}. Lorsque nous aurons vu (ou
revu) le calcul matriciel sur Sage, nous pourrons refaire le même exercice en
utilisant les matrices.

Il y a différentes manières de faire. Par exemple :

{\tt SRt.<t>=PolynomialRing(SR)} (c'est l'anneau des polynômes
de variable {\tt t} sur l'anneau {\tt Symbolic Ring})

\begin{verbatim}
  a0,a1,a2 = var('a0 a1 a2')
  p = a0+a1*t+a2*t^2
  p1 = diff(p,t)
  p2 = diff(p1,t)
  q = (3*t-2)*p2+2*t^2*p1-2*(2*t-1)*p
  l = q.coefficients()
  solve(l,[a0,a1,a2])}
\end{verbatim}

C'est une possibilité, mais comment faire si l'on veut automatiser ce calcul
en une fonction qui prendrait le degré maximal du polynôme recherché en
paramètre~? Cela ne semble pas évident\dots

Voici une autre manière de faire, qui semble plus facile à automatiser.
Commençons par définir les indéterminées. Pour cela, on définit un anneau de
polynômes à plusieurs variables (ces variables seront les variables de notre
polynôme en $t$).

{\tt PR=PolynomialRing(QQ,3,'b');PR}

{\tt PR} est l'anneau des polynômes à coefficients dans
$\QM$ et à trois indéterminées {\tt b0, b1, b2}.
Si on tape
{\tt b0},
on voit qu'il y a un problème, comme on l'a déjà vu dans
la question {\bf 4}. Il faut renommer les variables.

{\tt v=PR.gens();v;v[1]}

C'est mieux, mais les listes sont plus maniables
que les $n$-uplets, c'est pourquoi je préfère écrire

{\tt v=list(PR.gens());v}

La commande {\tt list('***')} transforme {\tt '***'} en liste,
conformément à la remarque générale de la fin du {\bf 2.}

Reste à définir l'anneau des polynômes en $t$.

{\tt PRt.<t>=PolynomialRing(PR);PRt}

{\tt PRt} est donc l'anneau $\QM[b_0,b_1,b_2][t]$, 
et chaque indéterminée $b_i$ correspond ici à {\tt v[i]}.
On cherche les polynômes de la forme 
$$P=b_2t^2+b_1t+b_0$$
qui sont solutions de (\ref{equa}). On pose

{\tt p=v[2]*t**2+v[1]*t+v[0]}

Puis on fait comme ci-dessus

\begin{verbatim}
  p1 = diff(p,t);
  p2 = diff(p1,t)
  q = (3*t-2)*p2+2*t^2*p1-2*(2*t-1)*p
  l = q.coefficients()
  solve(l,v)
\end{verbatim}

Ah ! Cela ne marche pas ! C'est que dans {\tt solve}, il faut que les {\tt
v[i]} soient des éléments de {\tt Symbolic Ring}.

Pour cela, on peut faire :

\begin{verbatim}
  for i in range(3):
    v[i]=SR(v[i])
\end{verbatim}

\begin{verbatim}
  for i in range(3):
    l[i]=SR(l[i])
\end{verbatim}

et ensuite seulement :

{\tt solve(l,v)}

(c'est sur la boucle {\tt for} ci-dessus que le fait que {\tt v} soit une
liste plutôt qu'un triplet est utile~: si {\tt v} est un triplet, on ne peut
pas modifier ses composantes).

Cette dernière commande affiche alors les coefficients des solutions de
l'équation. Cela peut nous suffire, mais on peut aussi affiner en affichant
les polynômes solutions eux-mêmes. Pour cela, on peut utiliser la commande

{\tt S=solve(l,v,solution\_dict=True)}

Alors, {\tt S} est la liste des solutions. Ici, il n'y en a qu'une~: {\tt
S[0]}, qui est un dictionnaire dont les entrées sont numérotées par les {\tt
v[i]}. Ainsi, les solutions sont données par

{\tt sum([S[0][v[i]]*t**i for i in range(3)])}

\Q
Écrire une fonction qui, étant donnés $a$, $b$ et $c$ dans $\QM[t]$ et un
entier $d$, donne les polynômes de degré inférieur ou égal à $d$ solutions de
l'équation
$$ay''+by'+cy=0.$$

\section{Évaluation et interpolation}

\Q 
Écrire une fonction qui prend en entrée un polynôme $P \in K[X]$ et un élément $x \in K$ et renvoie $P(x)$ en effectuant au plus $\mathrm{deg}(P)$ multiplications et $\mathrm{deg}(P)$ additions dans $K$.\\
\comment{[Indice: si vous n'avez pas d'idées, aller voir "Horner's method" sur wikipedia.]}

\Q 
Écrire une fonction {\tt multi\_eval(P,liste)} qui prend en entrée un polynôme {\tt P} et une liste de valeurs {\tt liste = [x1,$\dots$,xk]} et renvoie la liste des évaluations {\tt [P(x1), $\dots$, P(xk)]}.

\Q
En utilisant les polynômes interpolateurs de Lagrange $L_i = \prod_{j \neq i} \frac{X-x_j}{x_i-x_j}$, écrire une fonction {\tt interpolation(liste\_points, liste\_valeurs)} qui prend en entrée une liste {\tt liste\_points = [x1, $\dots$, xk]} de points distincts ($x_i \neq x_j$ pour tout $i \neq j$), et une liste de valeurs {\tt liste\_valeurs = [y1, $\dots$, yk]} et renvoie un polynôme $P$ de degré $k-1$ tel que $P(x_i) = y_i$ pour tout $i$.\\
\comment{[Note: pour récupérer la taille d'une liste, vous pouvez utiliser la commande {\tt len(liste)}]}

\Q
Vérifiez que vos fonctions {\tt multi\_eval} et {\tt interpolation} sont correctes en les utilisant l'une après l'autre et en vérifiant que vous retombez bien sur le polynôme de départ. Faites des tests sur $\mathbb{R}$ et d'autres sur $\mathbb{F}_p$. Que se passe-t-il si $\mathrm{deg}(P) \geq p$?
\end{document}
