diff options
author | David A. Madore <david+git@madore.org> | 2012-11-22 15:14:33 +0100 |
---|---|---|
committer | David A. Madore <david+git@madore.org> | 2012-11-22 15:14:33 +0100 |
commit | b49d70f75a643f337f6918d0acec3ae5db8f938f (patch) | |
tree | 2a0ab727b86e55849f732d0918fb0c22fdda641a /chapitres | |
parent | 2f17278dfe9f69e4a196717a591c0f8b50488286 (diff) | |
download | galois-b49d70f75a643f337f6918d0acec3ae5db8f938f.tar.gz galois-b49d70f75a643f337f6918d0acec3ae5db8f938f.tar.bz2 galois-b49d70f75a643f337f6918d0acec3ae5db8f938f.zip |
[Gröbner] Un éclaircissement sur ce qu'on peut et ne peut pas faire (test de primalité indécidable en général).
Diffstat (limited to 'chapitres')
-rw-r--r-- | chapitres/bases-groebner.tex | 38 |
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} |