diff options
author | David A. Madore <david@procyon> | 2012-09-20 17:35:28 +0200 |
---|---|---|
committer | David A. Madore <david@procyon> | 2012-09-20 17:35:28 +0200 |
commit | d234e5e67015aeffdd265597025bfdf2ba7aa038 (patch) | |
tree | 6084eb8bd39232a539611ec44ef51884bfc7ed33 /chapitres/bases-groebner.tex | |
parent | 454ae64e8339e30daeb03093b166093b69bc24dc (diff) | |
download | galois-d234e5e67015aeffdd265597025bfdf2ba7aa038.tar.gz galois-d234e5e67015aeffdd265597025bfdf2ba7aa038.tar.bz2 galois-d234e5e67015aeffdd265597025bfdf2ba7aa038.zip |
[Gröbner] Test de primalité en dimension 0.
Diffstat (limited to 'chapitres/bases-groebner.tex')
-rw-r--r-- | chapitres/bases-groebner.tex | 71 |
1 files changed, 70 insertions, 1 deletions
diff --git a/chapitres/bases-groebner.tex b/chapitres/bases-groebner.tex index b86cd0b..505746f 100644 --- a/chapitres/bases-groebner.tex +++ b/chapitres/bases-groebner.tex @@ -1545,7 +1545,7 @@ de $k[Z_1,\ldots,Z_d]$ est radical si et seulement si tous ses idéaux d'élimination à une seule variable le sont. Ceci nous permet de donner une conséquence algorithmique : -\begin{algorithme2} +\begin{algorithme2}\label{algorithme-test-ideal-radical-dimension-0} Donné un idéal $I$ (défini par ses générateurs) de dimension $0$ de $k[Z_1,\ldots,Z_d]$, avec $k$ parfait, on peut tester si $I$ est radical, ou, s'il ne l'est pas, calculer son radical. @@ -1795,6 +1795,75 @@ Z_d)) \pmod{I}$ en divisant par $q(c_1,\ldots,c_d)$. C'est bien ce qu'on voulait montrer. \end{proof} +\begin{algorithme2} +Donné un idéal $I$ (défini par ses générateurs) de dimension $0$ de +$k[Z_1,\ldots,Z_d]$, avec $k$ parfait et infini, si on sait tester +l'irréductibilité des polynômes à une variable à coefficients +dans $k$, on peut tester si $I$ est premier. +\end{algorithme2} +\begin{proof}[Description de l'algorithme] +En utilisant \ref{algorithme-test-ideal-radical-dimension-0}, on peut +commencer par tester si $I$ est radical (s'il ne l'est pas, il n'est +sûrement pas premier). + +On trouve ensuite $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 la proposition précédente, en prenant +$c_1,\ldots,c_d$ dans un ensemble suffisamment grand, ce sera toujours +possible (formellement, on peut commencer par tester tous les +$d$-uplets d'un ensemble fini, puis agrandir cet ensemble fini si +aucun ne convient, et répéter jusqu'à trouver un $d$-uplet qui +convient, ce qui se produira toujours si l'idéal était bien radical) : +à chaque fois, on teste si on est en position nette en utilisant +\ref{critere-nettete-dimension-0} ou la remarque qui précède. + +(Remarquons que si on trouve $c_1,\ldots,c_d$ tels que $I$ soit en +position nette, on peut passer à la suite même si on n'a pas testé que +$I$ est radical. Cependant, le fait que $I$ soit radical permet de +garantir que cette étape terminera bien.) + +Une fois trouvé $c_1,\ldots,c_d$ tels que $I$ soit en position nette +par rapport à $Y = c_1 Z_1 + \ldots + c_d Z_d$, on calcule le +générateur unitaire $h(Y)$ de l'idéal d'élimination de $I$ sur la +variable $Y$ (cf. \ref{base-de-groebner-elimination} et +\ref{critere-nettete-dimension-0}) : il ne reste plus qu'à tester +l'irréductibilité de $h$ dans $k[Y]$ puisque $k[Y]/(h) \cong +k[Z_1,\ldots,Z_d]/I$ est intègre si et seulement si $h$ est +irréductible. +\end{proof} + +La correction de cet algorithme est claire compte tenu de ce qui a +déjà été expliqué. Si $k$ est fini, on peut passer à +$k(C_1,\ldots,C_d)$, auquel cas l'idéal sera en position nette par +rapport à $Y = C_1 Z_1 + \ldots + C_d Z_d$ +d'après \ref{nettete-projection-generique-dimension-0}, mais les +calculs seront nettement plus complexes (il vaut mieux, au moins, +passer à $k[C_1,\ldots,C_d]$ et calculer l'idéal d'élimination par +rapport à $C_1,\ldots,C_d,Y$). Remarquons que dans ce cas, il faudra +savoir factoriser (ou au moins tester la primalité de) polynômes à +plusieurs variables. Par ailleurs, sous-jacent à cette variante de +l'algorithme est le résultat facile suivant : +\begin{proposition2} +Soit $I$ un idéal de $k[Z_1,\ldots,Z_d]$ et soient $U_1,\ldots,U_m$ de +nouvelles indéterminées. Alors l'idéal $\tilde I$ engendré par $I$ +dans $k(U_1,\ldots,U_m)[Z_1,\ldots,Z_d]$ ou bien $k[U_1,\ldots,U_m, + Z_1,\ldots,Z_d]$ est premier si et seulement si $I$ l'est. +\end{proposition2} +\begin{proof} +Dans le cas de $k[U_1,\ldots,U_m, Z_1,\ldots,Z_d]$, le quotient de +celui-ci par $\tilde I$ est l'anneau des polynômes en $m$ variables +$U_1,\ldots,U_m$, à coefficients dans le quotient +$k[Z_1,\ldots,Z_d]/I$. Or il est bien connu qu'un anneau de polynômes +est intègre si et seulement si son anneau de coefficients l'est. + +Dans le cas de $k(U_1,\ldots,U_m)[Z_1,\ldots,Z_d]$, on obtient +l'anneau qui inverse les éléments non nuls de $k[U_1,\ldots,U_m]$ dans +l'anneau ci-dessus : lui aussi est intègre si $I$ est premier, et a +des diviseurs de $0$ s'il y en a déjà dans $k[Z_1,\ldots,Z_d]/I$. +\end{proof} + + \ifx\danslelivre\undefined |