diff options
author | Fabrice Orgogozo <Fabrice.Orgogozo+git@gmail.com> | 2012-04-05 16:34:59 +0200 |
---|---|---|
committer | Fabrice Orgogozo <Fabrice.Orgogozo+git@gmail.com> | 2012-04-05 16:34:59 +0200 |
commit | 1ef091887b68298fb08b3f29a911c15d0ea7957b (patch) | |
tree | db7c206f0480db9f335446184067cd022b3830ba /chapitres/calculs-galois.tex | |
parent | a6d0efd6318e127ede519861721e05cae0b45f1c (diff) | |
download | galois-1ef091887b68298fb08b3f29a911c15d0ea7957b.tar.gz galois-1ef091887b68298fb08b3f29a911c15d0ea7957b.tar.bz2 galois-1ef091887b68298fb08b3f29a911c15d0ea7957b.zip |
[calculs] amélioration borne sur les coefficients des diviseurs + ajout remarque historique
Diffstat (limited to 'chapitres/calculs-galois.tex')
-rw-r--r-- | chapitres/calculs-galois.tex | 54 |
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$. |