diff options
author | Fabrice Orgogozo <Fabrice.Orgogozo+git@gmail.com> | 2012-04-01 15:53:03 +0200 |
---|---|---|
committer | Fabrice Orgogozo <Fabrice.Orgogozo+git@gmail.com> | 2012-04-01 15:53:03 +0200 |
commit | a45a9b0466208720d70120e6501a8c8d145f7fb5 (patch) | |
tree | 3e748c35461cad6f70f855f392663aecc98b74bf /chapitres/calculs-galois.tex | |
parent | f22920853c9b4905be118393a2345379682b5b53 (diff) | |
download | galois-a45a9b0466208720d70120e6501a8c8d145f7fb5.tar.gz galois-a45a9b0466208720d70120e6501a8c8d145f7fb5.tar.bz2 galois-a45a9b0466208720d70120e6501a8c8d145f7fb5.zip |
[calculs] borne Landau-Mignotte (début)
Diffstat (limited to 'chapitres/calculs-galois.tex')
-rw-r--r-- | chapitres/calculs-galois.tex | 92 |
1 files changed, 92 insertions, 0 deletions
diff --git a/chapitres/calculs-galois.tex b/chapitres/calculs-galois.tex index f432bf7..16c2c47 100644 --- a/chapitres/calculs-galois.tex +++ b/chapitres/calculs-galois.tex @@ -8,6 +8,7 @@ \input{../configuration/numerotation} \input{../configuration/formules} \input{../configuration/encoredesmacros} +\input{../configuration/ucs_manquants} \usepackage{stmaryrd} \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} @@ -262,6 +263,97 @@ cf. Fröhlich \& Shepherdson, « Effective Procedures in Field Theory », \textit{Phil. Trans. R. Soc. A} \textbf{248} (1956) 407--432, théorème 7.27. +\subsection{Bornes explicites sur les coefficients des diviseurs d'un polynôme à coefficients entiers} + +\subsubsection{} +Soit $f ∈ 𝐙[X]$. Il existe un nombre premier $p$ +tel que les diviseurs de $f$ dans $𝐙[X]$ soient déterminés +par leur réduction modulo $p$ : cela résulte de la finitude +de l'ensemble de ces diviseurs, ayant pour conséquence +l'existence d'une borne $C$ (ne dépendant que de $f$) +sur la taille des coefficients de $g$. Tout $p>2C$ convient. +Il est \emph{a priori} possible de déduire +de la démonstration de la proposition \ref{factorisation-des-polynomes-est-algorithmique} +une méthode de calcul d'un tel nombre $C$. Cette +méthode est loin d'être optimale. +[Traiter un exemple ? cf. infra \XXX] +Nous nous proposons ici d'obtenir une meilleure borne. +% due à Landau et Mignotte ? \XXX + +\subsubsection{}Pour tout polynôme $f= a₀ X^n + \cdots + a_n=a₀(X-α₁)(X-α₂)\cdots (X-α_n)$ dans $𝐂[X]$ +posons : $M(f)=|a₀| ∏_{i=1}^n \max(1,|α_i|)$, +$‖f‖₂ = (∑_i |a_i|²)^{½}$, $‖f ‖₁=∑_i |a_i|$ et enfin $‖f ‖_∞ = \max_i |a_i|$. +Cette dernière quantité — qui nous intéresse le plus — est +majorée par $‖f‖₁$ et $‖f‖₂$. +La proposition suivante est évidente. + +\begin{proposition2} +On a $M(gh)=M(g)M(h)$. +\end{proposition2} + +\begin{proposition2} +Soit $f ∈ 𝐂[X]$ un polynôme de degré $n$. Les inégalités suivantes sont satisfaites : +\begin{enumerate} +\item $‖f ‖₁ ≤ 2^n M(f)$ ; +%\item Montrer que pour tout $α ∈ 𝐂$, $‖(X-α)f‖₂ = ‖(\sur{α}X-1)f‖₂$. +\item $M(f) ≤ ‖f ‖₂$. +\end{enumerate} +\end{proposition2} + +\begin{démo} +(i) Soit $r ∈ [0,n]$. On a $a_r = ±a₀∑_{I: \# I=r} α_J$, +où $α_I=∏_{i ∈ I} α_i$. Par définition, on a $|a₀||α_I| ≤ M(f)$. +Il en résulte que $|a_r|$ est majoré par ${n \choose r} +M(f)$ puis $‖ f ‖₁ = ∑_r |a_r| ≤ 2^n M(f)$. +(ii) Commençons par observer que pour tout polynôme $g$ et +tout $α ∈ 𝐂$, on a l'égalité $‖(X-α)g‖₂ = ‖(\sur{α}X-1)g‖₂$. +En effet, si l'on écrit $g = ∑_{i ∈ 𝐙} b_i X^i$, on a +$(X-α)g =∑_i (b_{i-1}-α b_i)X^i$ et $(\sur{α}X-1)g = ∑_i +(\sur{α}b_{i-1} - b_i) X^i$. On vérifie alors +en développant que $∑_i |b_{i-1}-α b_i|² = ∑_i |\sur{α}b_{i-1} - b_i|²$. +Il en résulte que l'on peut supposer que les racines de $f$ +sont de module inférieur ou égal à $1$ sans changer $‖f‖₂$. +Dans ce cas, $M(f)=|a₀| ≤ (∑_i |a_i|²)^{½}=‖f ‖₂$. +\end{démo} + +\begin{proposition2} +Soit $f ∈ 𝐙[X]$ un polynôme et soit $g$ un diviseur +de degré $d$ de $f$ dans l'anneau $𝐙[X]$. +Alors, $‖ g ‖_∞ ≤ 2^d ‖ f ‖₂$. +\end{proposition2} + +\begin{démo} +Si $f=gh$, on a $M(f)=M(g)M(h)$ et $M(h) ≥ 1$ car le +coefficient dominant de $h$ est un entier. Ainsi, $M(g) ≤ +M(f)$. D'autre part, on a $‖ g ‖_∞ ≤ ‖ g ‖₁$ et $‖ g ‖₁ ≤ +2^d M(g)$. +\end{démo} + +\begin{exemple2} +% Knuth, TACP II, 4.6.2 p. 450 +Soit $f=X⁸+X⁶-3X⁴-3X³+8X²+2X-5$. On a $‖f‖₂ =10,6…$. +Ainsi, si $g$ est un diviseur de $f$ de degré au plus $4$, +ses coefficients sont majorés par $2^4×11=176$. +Modulo $p=353>2×176$, le polynôme $f$ se décompose +en produit de facteurs irréductibles sous la forme : +\[ +f ≡ (X + 111) (X - 107) (X⁶-4X⁵-108X⁴ -127X³ -115X²+94X -113). +\] +D'autre part, +$(X + 111) (X - 107) ≡ X²-4X+125$. +Le polynôme $g$ étant uniquement déterminé par sa réduction +modulo $p$, on en déduit que $g$ est l'un des polynômes +$X+111$, $X-107$ ou $X²-4X+125$. +Visiblement, aucun de ces polynômes n'est un diviseur +de $f$, qui est donc irréductible. +\end{exemple2} + +\begin{remarque2} +Amélioration \XXX: $|g_{d-i}| ≤ {d-1 \choose i} M(f) + {d-1 +\choose j-1} |a₀|$ [ou variante] ... +On obtient $34$ au lieu de $176$. +\end{remarque2} + \subsection{Factorisations successives} \XXX À écrire : on peut calculer le groupe de Galois d'un polynôme en |