[Gröbner] Un éclaircissement sur ce qu'on peut et ne peut pas faire (test de primalité indécidable en général).

1 files changed, 38 insertions, 0 deletions

diff --git a/chapitres/bases-groebner.tex b/chapitres/bases-groebner.tex
index 9906c0c..c32f1dd 100644
--- a/chapitres/bases-groebner.tex
+++ b/chapitres/bases-groebner.tex
@@ -1901,8 +1901,21 @@ Donné un idéal $I$ (défini par ses générateurs) de dimension $0$ et
 géométriquement radical de $k[Z_1,\ldots,Z_d]$, avec $k$ un corps
 infini, si on sait tester l'irréductibilité des polynômes à une
 variable à coefficients dans $k$, on peut tester si $I$ est premier.
+
+(En particulier, si $k$ est un corps infini parfait, et si on sait
+tester l'irréductibilité des polynômes à une variable à coefficients
+dans $k$, alors donné un idéal $I$ de dimension $0$, on peut tester si
+$I$ est premier.)
 \end{algorithme2}
 \begin{proof}[Description de l'algorithme]
+S'agissant du deuxième paragraphe, sur un corps parfait un idéal est
+radical si et seulement si il est géométriquement radical, on sait
+tester ce fait
+d'après \ref{algorithme-test-ideal-radical-dimension-0}, et si l'idéal
+n'est pas radical en particulier il n'est pas premier.  Décrivons
+maintenant l'algorithme pour tester la primalité d'un idéal
+géométriquement radical sur un corps infini quelconque.
+
 On trouve $c_1,\ldots,c_d$ tels que l'idéal $I$ soit en position nette
 par rapport à $c_1 Z_1 + \ldots + c_d Z_d$ (avec l'abus de langage
 évident, c'est-à-dire, au sens de la proposition précédente) : d'après
@@ -2026,6 +2039,31 @@ possibilités parmi les six : on va expliquer pourquoi ce qu'on a fait
 revient exactement à calculer le groupe de Galois de $f$.
 \end{exemple2}
 
+\begin{remarque2}
+On observera que si $k$ est un corps sur lequel on sait factoriser les
+polynômes en une variable, sans l'hypothèse que $k$ est parfait, nous
+n'avons pas donné d'algorithme permettant de décider si un idéal de
+dimension $0$ de $k[Z_1,\ldots,Z_d]$ est radical, ou bien premier
+(seulement pour savoir s'il est géométriquement radical, et pour
+savoir s'il est premier en supposant qu'il est géométriquement
+radical).  Ce n'est pas un oubli : un tel algorithme n'existe pas, car
+le problème est \emph{indécidable} au sens de Church-Turing.
+
+En effet, il existe (\XXX --- référencer Fröhlich \& Shepherdson
+lemme 7.21 et th. 7.27) un corps $k$ de caractéristique $p>0$ tel
+qu'on sache algorithmiquement factoriser les polynômes dans $k[X]$
+mais que si $k' = k[Y]/(h)$ est une certaine extension algébrique
+finie purement inséparable de $k$ alors il est indécidable de savoir
+si un élément $\xi$ de $k'$ a une racine $p$-ième dans $k'$.  Or si
+$I_\xi$ désigne l'idéal de $k[X,Y]$ engendré par $h \in k[Y]$ et par
+$X^p - \tilde\xi$ (où $\tilde\xi \in k[Y]$ est un relevé quelconque
+de $\xi$, dont le choix n'a pas d'importance), alors $k[X,Y]/I_\xi =
+k'[X]/(X^p-\xi)$ est un corps, ou est réduit, si et seulement si $\xi$
+a une racine $p$-ième.  Donc arriver à décider si $I_\xi$ est premier,
+ou radical, revient à décider si $\xi$ a une racine $p$-ième, ce qui
+n'est pas possible en général.
+\end{remarque2}
+
 
 \section{Quelques applications}