[calculs] borne Landau-Mignotte (début)

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