summaryrefslogtreecommitdiffstats
path: root/chapitres/bases-groebner.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david@procyon>2012-09-20 17:35:28 +0200
committerDavid A. Madore <david@procyon>2012-09-20 17:35:28 +0200
commitd234e5e67015aeffdd265597025bfdf2ba7aa038 (patch)
tree6084eb8bd39232a539611ec44ef51884bfc7ed33 /chapitres/bases-groebner.tex
parent454ae64e8339e30daeb03093b166093b69bc24dc (diff)
downloadgalois-d234e5e67015aeffdd265597025bfdf2ba7aa038.zip
galois-d234e5e67015aeffdd265597025bfdf2ba7aa038.tar.gz
galois-d234e5e67015aeffdd265597025bfdf2ba7aa038.tar.bz2
[Gröbner] Test de primalité en dimension 0.
Diffstat (limited to 'chapitres/bases-groebner.tex')
-rw-r--r--chapitres/bases-groebner.tex71
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