Algèbres de polynômes

On construit l’algèbre des polynômes sur un anneau commutatif $A$, et on étudie ses propriétés en fonction de celles de $A$.

Intuition

On fixe un anneau commutatif $A$. On note ses opérations $+$ et $\times$, et leurs unités $0$ et $1$, comme d’habitude (on pourra aussi utiliser $A$ comme indice pour éviter les ambigüités, par exemple $0_A$ pour éviter la confusion avec le polynôme nul).

Intuitivement, un polynôme à une indéterminée $X$ sur $A$ est une expression de la forme \[ P(X)=a_0+a_1 X+a_2 X^2+\cdots+a_nX^n\,, \] vue comme une somme finie de monômes $X^i$ avec des coefficients dans $A$: on peut sommer ces expressions et les multiplier entre elles ou par des éléments de $A$, pour former de nouveaux polynômes, ces opérations étant soumises aux identités usuelles. L’indéterminée $X$ est là pour suggérer qu’on voudra plus tard évaluer la fonction polynomiale associée, en remplaçant $X$ par un élément de $A$ par exemple: si $x\in A$, on écrira $P(x)=a_0+a_1 x+a_2 x^2+\cdots+a_nx^n$, où les sommes, les produits et les puissances sont les opérations dans $A$ et non plus des constructions formelles.

Tout ça est un peu flou, et on va le préciser tout de suite. En particulier, un polynôme est uniquement caractérisé par la suite de ses coefficients en tout degré, et les opérations peuvent être définies directement sur ces suites de coefficients.

L’algèbre des suites

On considère l’espace des suites $S(A)=A^{\mathbf{N}}$. La structure d’anneau commutatif de $A$ induit une structure d’anneau commutatif sur $S(A)$ de la manière suivante.

La somme des suites est définie composante par composante: si $P=(a_i)_{i\in \mathbf{N}}$ et $Q=(b_i)_{i\in \mathbf{N}}$ alors $P+Q=(a_i+b_i)_{i\in \mathbf{N}}$. Le neutre de cette somme est la suite partout nulle $0=(0_A)_{i\in\mathbf{N}}$. Il est évident qu’on obtient une structure de groupe commutatif (c’est le groupe produit), l’opposé étant encore défini composante par composante: $-P=(-a_i)_{i\in \mathbf{N}}$.

Ce groupe peut être équipé d’une multiplication externe, en considérant les éléments de $A$ comme des scalaires: on pose $a P = (a a_i)_{i\in \mathbf{N}}$. Cette opération vérifie les équations suivantes: \[ a(P+Q)=aP+aQ\qquad a0=0\] \[(a+b)P=aP+bP\qquad 0_A P=0\] \[(ab)P=a(bP)\qquad 1_A P=P\,.\] Ce sont les équations usuelles d’espace vectoriel, avec des scalaires pris dans l’anneau $A$ (on dit que $S(A)$ est un module sur $A$, ou $A$-module).

On peut par ailleurs munir les suites d’une multiplication interne, en posant: $P\times Q=(c_i)_{i\in\mathbf{N}}$ avec \[ c_n = \sum_{i=0}^{n} a_i b_{n-i}. \]

Exercices

Si $i,j\in\mathbf{N}$, on note $δ_{i,j}=\begin{cases}1_A&\text{si $i=j$}\\0_A&\text{sinon}\end{cases}$.

• Vérifiez que la multiplication des suites est associative et commutative, et admet $1=(δ_{i,0})_{i\in\mathbf{N}}$ comme élément neutre: c’est une loi de monoïde commutatif.
• Véfifiez que la multiplication est bilinéaire: \[ (aP)\times Q = a(P\times Q) \text{ et } P\times(Q+R)=P\times Q+P\times R \] (en particulier $S(A)$ a une structure d’anneau commutatif, et c’est une algèbre sur $A$).
• Vérifiez que la fonction $a\in A\mapsto a1=(δ_{i,0}a)_{i\in\mathbf{N}}\in S(A)$ est injective et préserve toute la structure: la somme et le produit, vu comme produit interne ou externe ($A$ se plonge dans $S(A)$ en tant qu’anneau et en tant que $A$-module).

L’algèbre des polynômes

Un polynôme $P$ à une indéterminée sur $A$ est une suite $(a_i)_{i\in \mathbf{N}}$ d’éléments de $A$ (les coefficients de $P$), presque tous nuls: $a_n=0$ pour $n$ suffisamment grand. Le degré de $P$, noté $d(P)$ est le plus grand entier $n\in\mathbf{N}$ tel que $a_n\not=0$, si un tel $n$ existe, et $-\infty$ sinon (les coefficients sont tous nuls). Si $d(P)=n\ge 0$, le coefficient $a_n$ est appelé coefficient dominant.

Lorsqu’on fixe une notation pour l’indéterminée, disons $X$, on note $A[X]$ l’ensemble des polynômes à coefficients dans $A$, et la suite $(δ_{i,n})_{i\in\mathbf{N}}$, qui est un polynôme, est notée $X^n$ (et ce n’est rien d’autre qu’une notation): c’est le monôme de degré $n$. On notera aussi $X=X^1$.

Vu l’exercice précédent, $A$ se plonge dans $A[X]$ via la fonction $a\mapsto a1=aX^0$. On confond donc $a$ avec $aX^0$, et en particulier $0_A$ avec le polynôme nul $0$.

Exercices

• Vérifiez que les polynômes sont stables par toutes les opérations définies sur les suites : $A[X]$ est un sous-anneau et un sous-$A$-module de $S(A)$, c’est l’algèbre des polynômes sur $A$. De plus, $d(P+Q)\le \max(d(P),d(Q))$, $d(aP)\le d(P)$ et $d(PQ)\le d(P)+d(Q)$.

• Vérifiez que \[ A[X]=\{ a_0+a_1 X+a_2 X^2+\cdots+a_{n-1}X^{n-1} \mid n\in\mathbf{N}\text{ et }(a_0,\ldots,a_{n-1})\in A^n \} \] ce qui formalise l’intuition dont on est parti.

• Définissez une classe P pour les polynômes à coefficients dans n’importe quel type numérique de Python. Munissez-la d’une méthode degre qui retourne le degré, et __eq__ pour avoir le bon test d’égalité. Munissez-la aussi des méthodes __add__, __neg__, __sub__, __mul__ pour l’équiper de sa structure d’anneau (somme, opposé, soustraction, produit interne).

• Modifiez la méthode __mul__ de la classe P : si l’autre argument est un nombre, on fait le produit externe (on peut importer le module numbers et utiliser isinstance(x,numbers.Number) pour tester si un objet est un nombre entier, rationnel, flottant ou complexe flottant). Ajoutez aussi une méthode __rmul__ pour le cas où on multiplie un nombre par un polynôme.

• Modifiez aussi les méthodes __add__ et __sub__ pour pouvoir ajouter ou soustraire un nombre à un polynôme, et ajoutez des méthodes __radd__ et __rsub__ pour traiter le cas symétrique.

• Modifiez aussi la méthode __eq__ pour identifier les nombres avec des polynômes de degré $<1$ (c’est automatiquement symétrique).

Divisibilité

Les notions liées à la divisibilité des nombres se traduisent directement pour les polynômes:

• Un polynôme $P$ divise un polynôme $Q$ s’il existe un polynôme $R$ tel que $Q=PR$: on note $P\mid Q$ comme pour les nombres.
• Un polynôme $P$ est inversible s’il existe un polynôme $R$ tel que $PR=1$, c’est-à-dire si $P\mid 1$.
• Un polynôme $Q$ est irréductible si $Q$ n’est pas inversible et, de plus, $Q=PR$ implique que $P$ ou $R$ est inversible.
• Deux polynômes $P$ et $Q$ sont premiers entre eux si leurs seuls diviseurs communs sont les inversibles.

On considèrera aussi les propriétés de l’anneau commutatif $A$: on dit que $A$ est intègre si $1\not=0$ et si $ab=0$ implique $a=0$ ou $b=0$ (c’est le cas pour tous les anneaux de nombres usuels). En particulier, $A$ est intègre dès que c’est un corps, c’est-à-dire quand $A^\times = A^\bullet$.

Exercices

• Vérifiez que $\mathbf{Z}/6\mathbf{Z}$ n’est pas intègre.
• Montrez que si $A$ est intègre, alors $d(PQ)=d(P)+d(Q)$.
• Déduisez-en que les seuls polynômes inversibles dans un anneau intègre sont les scalaires inversibles.
• Montrez que si $A$ est un corps alors pour tout polynôme $P\not=0$ il existe un unique polynôme unitaire (c’est-à-dire un polynôme non nul dont le coefficient dominant est $1$) $U$ tel que $U \mid P$ et $P \mid U$.
• Équipez la classe P d’une méthode unitaire(self) qui retourne le polynôme unitaire associé au polynôme courant.

Valuation

À chaque polynôme $P=\sum_{i=0}^n a_i X^i$, on peut associer la fonction polynomiale $\hat P:A\to A$: \[ \hat P(a)=\sum_{i=0}^n a_i a^i\,. \] Autrement dit, $\hat P(a)$ c’est $P$ où on remplace $X$ par $a$ et les opérations formelles par les opérations dans $A$: on dit que $\hat P$ est la valuation de $P$ dans $A$, et $\hat P(a)$ est la valeur de $P$ en $a$.

Exercice

• Équipez la classe P d’une méthode val(self,a) qui calcule la valeur du polynôme en a.

Division de polynômes

La division euclidienne des polynômes est définie dès que le coefficient dominant du diviseur est inversible dans $A$, en utilisant le degré comme mesure décroissante plutôt que la valeur absolue: pour tous polynômes $U$ et $V$ avec $V=\sum_{i=0}^n a_i X^i$ et $a_n$ inversible, il existe des polynômes $Q$ et $R$ (définis de manière unique) tels que $U=QV+R$ avec $d(R)<d(V)$.

Exercices

• Démontrez le résultat précédent.
• Équipez la classe P d’une méthode __divmod__(self,autre) pour la division euclidienne.

Racines

Une racine de $P$ dans $A$, c’est un élément $a\in A$ tel que $\hat P(a)=0_A$. Il est évident que si $X-a\mid P$ alors $a$ est une racine de $P$.

Exercice

• Montrez que cette dernière implication est une équivalence. En particulier, un polynôme admet une racine ssi il est divisible par un polynôme de degré 1; et un polynôme irréductible admet une racine ssi il est de degré 1.

PGCD et décomposition de polynômes sur un corps

Lorsque $A$ est un corps, tout coefficient non nul est inversible, donc la division par un polynôme non nul est toujours définie.

Exercices

On suppose que $A$ est un corps.

• Déduisez-en que tous deux polynômes $U$ et $V$ admettent un unique PGCD unitaire ou nul $U\wedge V$, vérifiant le lemme de Bézout:

Lemme. Pour tous $U,V\in A[X]$, il existe $K,L\in A[X]$ tels que $UK+VL=U\wedge V$.

De plus, si $P$ est irréductible, alors il est premier: $P\not=0$, et si $P\mid QR$ alors $P\mid Q$ ou $P\mid R$.

• Ajoutez une méthode pgcd_couple_bezout(self,autre) à la classe P, qui renvoie un triplet (C,K,L) avec C le PGCD unitaire ou nul de self et autre, et K et L vérifiant l’égalité du lemme de Bézout.
• Déduisez-en une méthode pgcd(self,autre) qui renvoie uniquement le PGCD.
• (Optionnel) Montrez que tout polynôme admet une unique décomposition comme produit d’un scalaire et d’une famille de polynômes irréductibles unitaires.