Remontée de Newton en algèbre

@moduloP
J'ai un peu peur d'une descente de police sur le forum (qui me prendrait la main dans le sac en train de faire du Newton pour obtenir le développement de $1 \over 1-t$). Je fais un peu moins trivial avec
$$
F(X) = X^2 - (1+t), \qquad \hbox {au point $x=1$, avec le modulus $t$}
$$
I.e. on va développer $\sqrt {1 + t}$ au voisinage de $t=0$ en prenant $\sqrt 1 = 1$ (et pas $-1$). On a $F'(X) = 2X$, $F(1) = 1 - (1+t) = 0 \bmod t$, et $F'(1) = 2$ est inversible car je travaille au dessus de $\Q$. L'itérateur de Newton est donc :
$$
x \longmapsto x - {1\over2} F(x) = x - {1 \over 2} \big( x^2 - (1+t) \big)
$$

 > Qt<t> := PolynomialRing(RationalField()) ;
> x := 1 ;
> for k := 2 to 20 do x := x - 1/2*(x^2 - (1+t)) ;  x := x mod t^k ;  end for ;
> x ;
119409675/34359738368*t^19 - 64822395/17179869184*t^18 + 17678835/4294967296*t^17 - 9694845/2147483648*t^16 + 334305/67108864*t^15 
    - 185725/33554432*t^14 + 52003/8388608*t^13 - 29393/4194304*t^12 + 4199/524288*t^11 - 2431/262144*t^10 + 715/65536*t^9 - 
    429/32768*t^8 + 33/2048*t^7 - 21/1024*t^6 + 7/256*t^5 - 5/128*t^4 + 1/16*t^3 - 1/8*t^2 + 1/2*t + 1

Le résultat $x$ est un polynôme en $t$, affiché coefficient dominant d'abord. On va passer dans $\Qt$ pour d'une part le faire afficher comme une série (coefficient constant d'abord) et d'autre part faire la comparaison avec $\sqrt {1+t}$ de magma :

> Qt<t> := PowerSeriesRing(RationalField()) ;                                    
> Qt ! x;                                                                        
1 + 1/2*t - 1/8*t^2 + 1/16*t^3 - 5/128*t^4 + 7/256*t^5 - 21/1024*t^6 + 33/2048*t^7 - 429/32768*t^8 + 715/65536*t^9 - 
    2431/262144*t^10 + 4199/524288*t^11 - 29393/4194304*t^12 + 52003/8388608*t^13 - 185725/33554432*t^14 + 334305/67108864*t^15 - 
    9694845/2147483648*t^16 + 17678835/4294967296*t^17 - 64822395/17179869184*t^18 + 119409675/34359738368*t^19
> Sqrt(1+t) ;  
1 + 1/2*t - 1/8*t^2 + 1/16*t^3 - 5/128*t^4 + 7/256*t^5 - 21/1024*t^6 + 33/2048*t^7 - 429/32768*t^8 + 715/65536*t^9 - 
    2431/262144*t^10 + 4199/524288*t^11 - 29393/4194304*t^12 + 52003/8388608*t^13 - 185725/33554432*t^14 + 334305/67108864*t^15 - 
    9694845/2147483648*t^16 + 17678835/4294967296*t^17 - 64822395/17179869184*t^18 + 119409675/34359738368*t^19 + O(t^20)
> Qt!x - Sqrt(1+t) ;
O(t^20)

Ca marche comme dit l'autre.

@moduloP
Contexte : $A \in M_n(K)$, $K$ corps commutatif. Obtenir, via la méthode de Newton, la décomposition $A = D+N$, $D,N \in M_n(K)$, avec $DN = ND$, $N$ nilpotente, $D$ diagonalisable dans un surcorps de $K$.
Mieux obtenir $D$ (ou $N$) sous la forme d'un polynôme en $A$. I.e. produire $P \in K[X]$ tel que $D = P(A)$. Sans sortir du corps de base $K$. I.e. toute cette histoire est $K$-rationnelle. Il faut juste une petite hypothèse technique sur le polynôme caractéristique de $A$, toujours vérifiée si $K$ est un corps parfait.

Tu as déjà vu cela ?

@Poirot
Merci pour le pointeur. C'était aussi le sujet de l'épreuve de Lyon en 1994. A l'époque, on ne disposait pas de toutes les documents que je vois dans les références bibliographiques du pdf pointé. J'avais dû tirer cela d'un écrit de Chevalley ou d'un papier qui rapportait cet écrit de Chevalley, je ne me souviens plus.

@moduloP
Avais tu vu les deux pdf attachés dans http://www.les-mathematiques.net/phorum/read.php?5,1585752,1586770#msg-1586770, en particulier la partie V ?

@moduloP
Pas étonnant (galère) parce qu'en même temps, tu apprends Sage.
J'ai également réalisé l'implémentation mais je me suis contenté de produire $(D,N)$ à partir de $A$, je n'ai pas fait suivre les polynômes (c'est pas bien). Le plus important dans cette histoire est de générer des données pour la matrice $A$. J'ai bien vu comment tu procédais (moi, pareil).

Plusieurs choses à te dire en faisant un peu de maths (pour éviter que le fil ne soit déplacé en informatique).

1) Je n'ai pas pris le temps de regarder les documents pointés par Poirot mais je crois me souvenir de l'épreuve de Lyon. Depuis un certain temps, je n'utilise plus le schéma de Newton qui y est décrit, j'en prends une variante. Quand j'étais petit, j'ai enseigné un peu d'Analyse Numérique (si, si) et on pouvait remplacer le schéma de gauche par celui de droite :
$$
x_{k+1} = x_k - {F(x_k) \over F'(x_k)} \qquad\qquad
x_{k+1} = x_k - {F(x_k) \over \hbox {approximation de $F'(x_1)$}}
$$
En algèbre, cela prend la forme suivante : $F \in A[X]$, $I$ un idéal donné, $x \in A$ vérifiant $F(x) = 0 \bmod I$ et $u\in A$ tel que $uF'(x) \equiv 1 \bmod I$ ($u$ est un inverse de $F'(x)$ modulo $I$). Supposons avoir déterminé à une étape $k \ge 1$ un $y$ tel que :
$$
y \equiv x \bmod I, \qquad F(y) \equiv 0 \bmod I^k
$$
On veut améliorer $y$ en une racine modulo $I^{k+1}$. De manière absolument pas pédagogique, je pose $\fbox {$z = y - uF(y)$}$. C'est clair que $z \equiv y \bmod I^{k}$. En posant $h = -uF(y) \equiv 0 \bmod I^k$, on a :
$$
F(z) = F(y+h) \equiv F(y) + hF'(y) = F(y)\big(1 - uF'(y)\big) \bmod h^2 \quad \hbox { a fortiori modulo $I^{2k}$} \quad \hbox { a fortiori modulo $I^{k+1}$}
$$
Et comme $F(y) \equiv 0 \bmod I^k$ et $1 - uF'(y) \equiv 0 \bmod I$, on a bien $F(z) \equiv 0 \bmod I^{k+1}$.

Cela m'évite, pour passer de l'étape $k$ à l'étape $k+1$, de calculer un inverse de $F'(x)$ modulo $I^k$. Je ne sais pas si je suis bien clair.


2) Toujours histoire de faire un peu de maths. C'est à propos du polynôme caractéristique $\chi_A$. La première étape dans le binz $A \mapsto (D,N)$ est de produire un polynôme séparable $P$ tel que $\chi_A \mid P^ e$ pour un certain exposant $e$.

J'oublie un peu le contexte matriciel et je prends le contexte suivant : $G \in K[X]$ un polynôme de degré $\ge 1$ sur un corps commutatif $K$ et $L/K$ le corps de décomposition de $G$ sur $K$. Alors :
$$
\hbox {$L/K$ est une extension séparable} \iff
\hbox {il existe $P \in K[X]$ séparable tel que $G$ divise une puissance de $P$}
$$
Pour me rassurer, j'ai fait la vérification (je ne me souvenais plus de l'avoir faite un jour).

@moduloP
Plusieurs petites choses

1) En procédant comme dans mon dernier post, on perd l'avantage de disposer d'une convergence quadratique i.e. on passe de $I^k$ à $I^{k+1}$. Alors que l'on pourrait passer de $I^k$ à $I^{2k}$ (en travaillant bien). Mais je ne crois pas que l'on veuille fonder une boite de logiciels autour de Newton. Donc l'aspect quadratique, on peut s'asseoir dessus.

2) Tu parles pgcd dans ton dernier post. Mais peut-être que tu voulais dire ppcm ? En tout cas, le ppcm de deux polynômes séparables est séparable et cela intervient dans le binz.

Le minimum syndical dans les histoires d'extensions (algébriques) séparables, c'est de savoir qu'une extension engendrée par des éléments (algébriques) séparables est séparable. Et cela peut se voir en faisant intervenir l'algèbre linéaire et la diagonalisation simultanée. Il faut travailler un peu car si $x,y$ sont séparables sur $K$ i.e. $P(x) = Q(y) = 0$ avec $P, Q \in K[X]$ séparables, il va falloir faire un petit effort pour montrer que $x+y$ et $xy$ le sont.

3) Mais surtout. J'ai encore fait joujou avec ma calculette Newton. Autour de la réversion des séries. Et j'ai enfin réglé un truc qui trainait depuis plus d'une dizaine d'années : la formule de réversion de Lagrange-Bürmann. C'est dingue : de nos jours, on trouve de bons cours (ici de Combinatoire) sur le net (on trouve aussi n'importe quoi, mais c'est une autre histoire).

$\def\fa{\mathfrak a}$@gai-requin
Non, justement. Car le coup du résultant pour le produit $xy$, à partir d'un polynôme unitaire $P$ de racines $x_1=x, x_2, \cdots$ et d'un polynôme unitaire $Q$ de racines $y_1=y, y_2, \cdots$ produit un polynôme ayant pour racines les $x_iy_j$ qui n'ont aucune raison d'être deux à deux distincts même si $P, Q$ sont séparables. Pense par exemple à $P(X) = X$ de racine $0$ ; il va y avoir un méchant écrasement en ce qui concerne les $x_iy_j$.

Même mésaventure pour la somme.

Mais l'algèbre linéaire va nous sauver. Je note $L$ une extension de $K(x,y)$ dans laquelle $P,Q$ sont complètement scindés. Par exemple, le corps de décomposition de $PQ$ au dessus de $K(x,y)$ si c'est moi qui paie, sinon $\overline {K(x,y)}$. On fixe une base $e_1, \cdots, e_n$ de $K(x,y)$ sur $K$ et on considère :
$$
K(x,y) \ni z \longmapsto M_z \in M_n(K), \qquad \hbox {$M_z$ matrice de la multiplication par $z$ dans la base choisie de $K(x,y)/K$}
$$
Alors $M_x, M_y$ sont diagonalisables au dessus de $L$ car d'une part $P,Q$ sont séparables et d'autre part $L$ est algébriquement clos (pour les pauvres). Mais $M_x$ et $M_y$ commutent donc sont simultanément diagonalisables dans $M_n(L)$. Donc tous les $z \in K(x,y)$ sont simultanément diagonalisables dans $M_n(L)$.

Je te laisse terminer. Attention au patacaisse : base de $L^n$ sur $L$ (quand j'ai parlé de $M_n(L)$) et base de $K(x,y)/K$. Prendre un verre d'eau avant. Et ne pas oublier de redescendre sur $K$ : on veut un polynôme unitaire séparable $R \in K[X]$ tel que $R(z) = 0$. Reprendre un second verre d'eau. Mieux : pendre du papier et un stylo et le faire au calme.


@moduloP
Tu as fini par montrer que $\fa \subseteq I$ et $\fa \subseteq J$, cela entraine $\fa \subseteq IJ$. C'est cela ? Les catégories, c'est fortiche, non ?

Hello,
Je pense qu'une fois dans sa vie (encore !), il est bon de faire l'exercice suivant. Soit $E$ un $K$-espace vectoriel de dimension finie et $(u_i)_{i \in I}$ une famille QUELCONQUE d'endomorphismes de $E$ telle que chaque $u_i$ soit diagonalisable (sur $K$) et telle que les $u_i$ commutent deux à deux.

Alors les $u_i$ sont simultanément diagonalisables.

Note : famille quelconque signifie qu'elle n'est pas supposée finie, par exemple.

@moduloP
Vu (on est poussé à faire une récurrence sur la dimension .. et pas sur le nombre d'endomorphismes !).

@gai-requin
Rationalité pour les polynômes minimaux. J'ai vu ton post (flemme de pointer) : on peut se passer de ce que tu évoques mais on en reparlera à une autre occasion.

Je propose de le (= coup des polynômes minimaux) tirer comme conséquence des résultats suivants de rationalité linéaire où $K \subset L$ sont deux corps quelconques.

1) Si des vecteurs de $K^N$ sont $L$-liés dans le $L$-espace espace vectoriel $L^N$, ils sont $K$-liés. Ou encore, si des vecteurs de $K^N$ sont $K$-linéairement, ils sont $L$-linéairement indépendants.

2) Soit $A : K^m \to K^n$ et $b \in K^n$. Si le système $Ax = b$ a une solution $x$ dans $L^m$, alors il admet une solution dans $K^m$. Bonus : qui va nous donner sur un plateau une $K$-solution ?

Matrice de Cohn, de déterminant 1, que j'ai utilisée pour créer du garbage $(F_1, F_2) \mapsto (G_1, G_2)$ :
$$
C = \pmatrix { 1 + ab & -a^2 \cr b^2 & 1-ab}, \qquad \qquad \det(C) = 1
$$
Ce n'est pas une matrice banale.
En prime, dans le demi-plan de Poincaré, c'est le fixateur sous $\text{PSL}_2(\Z)$, du cusp $(a : b) = a/b$ :
$$
\pmatrix { 1 + ab & -a^2 \cr b^2 & 1-ab} \pmatrix {a \cr b} = \pmatrix {a \cr b}
$$


PS : aucun rapport avec la méthode de Newton. C'est n'importe quoi ce fil. On devrait prendre modèle sur les autres fils, qui sont tellement carrés.

@moduloP
Oui, c'est cela. Mais ce n'était absolument pas pédagogique de ma part d'en parler. J'aurais dû rester dans le cadre ``linéaire pur'' (encore que, avec la $K$-base des monômes, je me comprends). Bref, j'aurais dû considérer les sous-espaces vectoriels $E$ de $K^n$. Relativement à la fonction hauteur, ceux-ci admettent une et une seule base strictement échelonnée (j'espère ne pas raconter de bêtise). C'est elle qui tient la rationalité.

Comme je me suis fait ch.er à écrire un programme général (qui prend en données la suite des hauteurs), je redonne un exemple pour l'aspect strictement échelonné (en colonnes).

[  1   0   0   0]
[a21   0   0   0]
[  0   0   0   1]
[  0   0   1   0]
[a51   0 a53 a54]
[  0   1   0   0]
[a71 a72 a73 a74]
[a81 a82 a83 a84]
[a91 a92 a93 a94]

J'aurais pu faire du garbage sur les colonnes mais du point de vue affichage, horrible.

@moduloP, gai-requin
Je tiens à m'excuser. Vraiment. Car cette histoire de base de Gröbner, ce n'est pas du tout, mais pas du tout pédagogique. Alors que je vois d'autres fils qui le sont tant.