[calculs] amélioration borne sur les coefficients des diviseurs + ajout remarque historique

1 files changed, 40 insertions, 14 deletions

diff --git a/chapitres/calculs-galois.tex b/chapitres/calculs-galois.tex
index 3fdc9ac..487da7f 100644
--- a/chapitres/calculs-galois.tex
+++ b/chapitres/calculs-galois.tex
@@ -254,6 +254,9 @@ algorithme.
 
 Pour une discussion historique du premier algorithme,
 cf. \cite{Mignotte-Stefanescu}.
+Le morphisme $S_e$, appelé « substitution de Kronecker »,
+a été introduit par Kronecker en 1882.
+% cf. Schinzel
 
 \XXX --- Faut-il mentionner ici le fait qu'une extension algébrique
 finie séparable (par un polynôme explicite) d'un corps dans lequel on
@@ -281,8 +284,8 @@ méthode est loin d'être optimale.
 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|)$,
+\subsubsection{}Pour tout polynôme $f= a_n X^n + \cdots + a₀=a_n(X-α₁)(X-α₂)\cdots (X-α_n)$ dans $𝐂[X]$
+posons : $M(f)=|a_n| ∏_{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‖₂$.
@@ -296,16 +299,14 @@ On a $M(gh)=M(g)M(h)$.
 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)$.
+(i) Soit $r ∈ [0,n]$. On a $a_{n-r} = ±a_n∑_{I: \# I=r} α_J$,
+où $α_I=∏_{i ∈ I} α_i$. Par définition, on a $|a_n||α_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
@@ -314,10 +315,11 @@ $(X-α)g =∑_i (b_{i-1}-α b_i)X^i$ et $(\sur{α}X-1)g = ∑_i
 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 ‖₂$.
+Dans ce cas, $M(f)=|a_n| ≤ (∑_i |a_i|²)^{½}=‖f ‖₂$.
 \end{démo}
 
 \begin{proposition2}
+\label{majoration-coefficients-diviseurs}
 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 ‖₂$.
@@ -330,11 +332,40 @@ M(f)$. D'autre part, on a $‖ g ‖_∞ ≤ ‖ g ‖₁$ et $‖ g ‖₁ ≤
 2^d M(g)$.
 \end{démo}
 
+\begin{remarque2}
+Il n'est pas difficile d'améliorer un peu la borne
+ci-dessus : si $g=b_dX^d+\cdots+b₀$ et $f=a_nX^n+\cdots+a₀$ sont comme dans l'énoncé, on a :
+\[
+|b_k| ≤ {d-1 \choose k} M(f) + {d-1 \choose k-1} |a_n|.
+\]
+Pour la vérifier, on peut supposer $g=f$.
+Dans ce cas, la majoration est valable sans hypothèse
+d'intégralité des coefficients ; on peut donc supposer
+de plus $a_n=1$.
+La valeur absolue de $b_{d-k}$ est alors majorée par la $k$-ième fonction symétrique élémentaire
+$σ_k=∑ x_{i₁}\cdots x_{i_k}$ en les $x_i=\max(1,|α_i|)$.
+Quitte à changer la numérotation, on peut également
+supposer que l'on a $x_1 ≤ … ≤ x_d$ ; par hypothèse
+on a également $M=x₁…x_d$.
+Or, on constate immédiatement que $σ_k$ augmente lorsque l'on 
+remplace $x_{d-1}$ par $1$ et $x_d$ par $x_d x_{d-1}$ :
+l'accroissement est égal à $(x_d-1)(x_{d-1}-1)$
+multiplié par la $k-1$-ième fonction symétrique
+élémentaire en les $x₁,…,x_{d-2}$.
+Il en résulte que $σ_k$ prend sa valeur maximale
+lorsque $x₁=…=x_{d-1}$ et $x_d=M$, auquel
+cas elle vaut ${d-1 \choose k-1} M + {d-1 \choose k}$.
+On fait alors le changement d'indice : $k ↔ d-k$.
+\end{remarque2}
+
 \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$,
+Il résulte de \ref{majoration-coefficients-diviseurs} que
+si $g$ est un diviseur de $f$ de degré au plus $4$,
 ses coefficients sont majorés par $2^4×11=176$.
+(En utilisant la borne de la remarque précédente, on trouve $34$
+de sorte que $p=71$ convient déjà.)
 Modulo $p=353>2×176$, le polynôme $f$ se décompose
 en produit de facteurs irréductibles sous la forme :
 \[
@@ -349,11 +380,6 @@ 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}
 
 \XXX Signaler également la méthode via Hensel, c'est-à-dire réduction
 modulo $p^e$ grand, $f$ séparable modulo $p$.