Remontée de Hensel et borne de Mignotte

Blanc

Bonjour,
J'ai essayé de m'atteler à ce sujet et ne comprends pas bien l'utilité de la borne de Mignotte dans la remontée de Hensel. Je précise que je comprends pafaitement la démonstration du lemme.
C'est plutôt la mise en place de l'algorithme avec arrêt grâce à la borne de Mignotte que je ne comprends pas.
Voici quelques documents qui pourront servir en vous priant de bien me détailler votre aide.
Merci beaucoup

 Dans le lemme lc(F) désigne le coefficient dominant de F.





Voici un exemple:
Il semblerait qu'il faille utiliser l'unicité des polynômes fournis par le lemme de Hensel et qu'au plus il faille effectuer 5 itérations avec cet algorithme pour trouver la décomposition de F, la borne de Mignotte est ici égale à 6.

Blanc

Bonjour,

J'ai cru bon de rajouter un exemple pour faire comprendre de quoi il s'agit.

LOU16

Bonjour,

Voilà ce que j'ai compris. On recherche une décomposition d'un polynôme $F\in \Z[X],\:$ de degré $5$.

 Si $A$ est un polynôme de degré $2$ divisant $F$ dans $\Z[X],\:\: $alors: $\:\|A\|_{\infty}\leqslant  b=2^2 \|F\|_2.\:$(borne de Mignotte)

Le lemme de Hensel nous indique que: $A\equiv A_3\equiv X^2+5X+2 \mod 125$

Tout élément $A\in\Z[X]$ distinct de $A_3$ et congru à $A_3 \mod 125$,  est tel que $\|A\|_{\infty}\geqslant 120.\:\:$ Ainsi:

$$\text{Si } 120>b \text { et si } A\text { divise }F \text { dans } \Z[X], \:\text { alors } A =A_3.$$

Or ici $b=385.91...,\:$ et il n'a y aucune raison pour affirmer,a priori, que $A=A_3.$

 En revanche,$\:\dfrac {5^4}2<b<\dfrac{5^5}2. \:\:$ Donc: $\quad \text{ Si } A \text { divise }F ,\: \text{ alors } A=A_5,\quad$ où $A_5$ est l'élément de $\Z[X]$ obtenu à la cinquième itération de la remontée de Hensel, et tel que $\|A_5\|_{\infty}<\dfrac {5^5}2.$

Dans cet exemple, on s'est arrêté à $A=A_3$, parce qu'il s'est trouvé  que $A_3$ était le diviseur de $F$ recherché.

Blanc

Bonjour Lou 16
Il y a plusieurs choses que je ne comprends pas:

1)  Si A est distinct de A3  et congru à A3 alors sa norme infinie est supérieure à 120. (d'ou vient ce 120 ?)

2) Pourquoi est on sûr à la cinquième itération que A =A5 et que de plus la norme infinie de A5 est strictement inférieure à (5^5)/2  ?

3) Quel est le lien entre entre la borne Mignotte et le nombre d'itérations maximales? 
Pourquoi la borne de Mignotte est ellle calculée comme dans le corrigé?

Peux tu me détailler chacune de ces étapes car je suis un peu perdu? Merci beaucoup

LOU16

Bonjour @Blanc

$1)\quad 120=125-\|A_3\|_{\infty.}.$

$2)\quad $ Ce que j'ai dit, c'est que $A_5$  était défini par: $A_5B_5\equiv F \mod 5^5\Z[X], \:\:\text{ deg }A_5 =2, \:\:\|A_5\|_ {\infty}<\dfrac {5^5}2.$

Ainsi , si $A\text{ divise }F,\: $ alors $A\equiv A_5\mod 5^5, \:\:\|A\|_{\infty}<b<\dfrac {5^5}2,\:\:\|A-A_5\|_{\infty}<5^5,\quad A=A_5.$

$3)\quad $ Je ne comprends pas le calcul de ton document. En ce qui me concerne, j'ai pris le nombre d'itérations $\mathcal l=\Big\lceil  \log_5(2b)\Big\rceil=5, \: $équivalent à $\dfrac{5^{\mathcal l-1}}2<b<\dfrac{5^{\mathcal l}}2.$

Blanc

Tu me dis au 2) que : 

 deg A5 =2 et que norme infinie de A5  strictemet inférieure à (5^2)/2.  Je ne vois pas pourquoi ces 2 affirmations .
Ce n'est pas dit dans la remontée de Hensel.

Au 3) deux points à éclaircir;

Si A divise F alors A congru à A5 modulo 5^5

 puis:
 pourquoi si norme infinie de A-A5 stictement inférieure à 5^5 alors A= A5 ?
En te remerciant

LOU16

Re,

$\bullet\:$Le degré $2$ dont je parle est bien donné par la "remontée de Hensel", qui part de la décomposition en produit d'irréductibles $\overline F=\overline{A_1}\:\overline {B_1}=\overline{(X^2+2)}\:\:\overline{(X^3+2X+1)}$ dans $\mathbb F_5[X].$ (note qu'il y a à ce sujet plusieurs erreurs dans ton document).

$\bullet\:$D'autre part, $A_5$ est choisi dans $ \Z[X],\:$ comme l'unique polynôme dont la valeur absolue des coefficients est inférieure à $\dfrac{5^5}2$, et qui appartient à la classe $\overline{A_5}$ définie par le lemme de Hensel: $\:\overline F =\overline{A_5}\overline{B_5}\text{ dans }(\Z/5^5\Z)[X].\:\:$ (tout élément de $ \Z/3125\Z$ possède un unique représentant dans $[\![-1562;\:1562]\!].)$ Dans le cas présent, nous avons en fait $A_5=A_4=A_3=A.$.

$\bullet\:$$\|A-A_5\|_{\infty}<5^5,\quad A-A_5=5^5 P, \:\:P\in \Z[X] \implies P=0, \:\:A=A_5.$

Je viens de voir que ton document est en fait incompréhensible, car outre les incohérences que j'ai signalées, il ne fait pas mention du choix des $A_k, B_k,\:(\|A_k\|_{\infty}<\dfrac{5^k}2)\:$ que j'ai indiqué. Il est en effet indispensable de contrôler la taille des coefficients  de ces polynômes pour pouvoir utiliser $\|A\|_{\infty}\leqslant 2^2\|F\|_2.$

Blanc

Lou 16,

Je dois dire que je ne comprends rien à ce que je fais. J'aurais besoin si tu en as la patience que tu m'exposes de manière progressive le cheminement qui permet de trouver la décomposition d'un polynôme de Z[X] en admettant bien sûr le lemme de Hensel.

C'est sûrement du travail pour l'intervenant qui m'aidera dans cette tâche mais c'est à ce prix que les choses deviendront claires pour moi.
Si tu t'en sens le courage, je t'en serai extrêmement reconnaissant.

Blanc

LOU16

Bonsoir,

Je vais être hélas amené à répéter des explications que je pensais avoir convenablement détaillées.

On veut donc décomposer $F =X^5+5X^4+19X^3+86X^2+4X+2$ en facteurs irréductibles de $\Z[X].$

La décomposition en irréductibles (distincts) de $\mathbb F_5[X]$ est: $\: \overline F=\overline{(X^2+2)}\:\:\overline{(X^3+2X+1)}$

Cela entraîne que si $F$ n'est pas irréductible dans $\Z[X],\:$ alors sa décomposition s'écrit $F=AB, \:\:\text{ deg }A=2,\:\text{ deg }B=3,\:\: A\equiv A_1=X^2+2, \:\:B\equiv B_1=X^3+2X+1 \mod 5\Z[X].$

De plus $\boxed{\|A\|_{\infty}\leqslant 2^2\|F\|_2 =b.}$

La suite $(A_n, B_n) _n$ produite par le lemme de  Hensel est telle que: $\:\forall n \in \N^*, F\equiv A_nB_n \mod 5^n\Z[X],$

$\text{ deg } A_n =2, \:\text{deg }B_n =3,\quad \boxed{A\equiv A_n, \: B\equiv B_n \mod 5^n\Z[X].}\:$

On a choisi les coefficients de $A_n$ et $B_n$ compris entre $-\dfrac{5^n}2$ et $\dfrac{  5^n}2.$

Soit $n \in \N^*$ tel que $\dfrac{5 ^{n-1}}2<b<\dfrac{5^n}2.\:$ Alors $\|A\|_{\infty}<\dfrac {5^n}2, \quad\|A-A_n\|_{\infty}<5^n.\:\:$ 

D'autre part, $\exists P \in \Z[X],\:$ tel que $A-A_n=5^n P.\:\:$ Il s'ensuit que $P=0 $ et donc que $\boxed{A=A_n.}$

Si $A_n$ ne divise pas $F$, cela signifie que $F$ est irréductible dans $\Z[X]$

Blanc

Bonsoir,
J'arrive à mieux suivre à présent.
Dans la partie que tu as encadrée, le lemme de Hensel nous dit que A=A1 congru  à An modulo n et non modulo 5^n.
Par ailleurs je ne sais rien sur les degrés de la suite (An, Bn). Or tu affirmes que degAn =2 et deg Bn= 3.
Une fois ces deux points éclaircis, je pense que la présentation que tu as eu la gentillesse de faire fait bien comprendre le cheminement.

LOU16

Bonjour,

J'ai réexaminé les rouages du lemme de Hensel, pour aboutir à quelque chose de conforme à mes souvenirs, et de plus précis que ce qu'indique ton document.

Soit $p$ un nombre premier.

Pour $n\in \N^*,\:$ je note $\pi_n$ et $\psi_n$ les projections canoniques: $\:\:\pi_n: \Z[X]\to \Z/p^n\Z[X], \:\: \psi_n: \Z/p^{n+1}\Z [X]\to\Z/p^n\Z[X].$

$$\pi_n =\psi_n \circ \pi_{n+1}.$$

Soit $F\in\Z[X]\:\text{ unitaire tel que } \pi_1(F) =\overline A_1 \overline B_1,\:\:\overline A_1\wedge \overline B_1 =1.$

Alors, il existe une unique suite $\left(\overline A_n,\overline B_n\right)_n $ avec $\:\overline A_n,\overline B_n\in\Z/p^n\Z[X]\: $ telle que:

$$\boxed{\forall n \in \N^*, \:\: \pi_n(F)=\overline A_n\overline B_n, \quad \psi_n(\overline A_{n+1}) =\overline A_n, \: \psi_n(\overline B_{n+1} )=\overline B_n.\quad \text{ deg }\overline A_n =\text{ deg } \overline A_1,\:\:\text{ deg }\overline B_n =\text{ deg }\overline B_1}$$

Ainsi si $F =AB, \:\:A,B\in \Z[X],\:\:\pi_1(A) =\overline A_1,\:\:\pi_1(B) =\overline B_1,\:\:$ alors la suite $\left( \pi_n(A), \pi_n(B) \right)_n\:$ a exactement les propriétés de la suite $\left( \overline A_n, \overline B_n\right) _n.$

Il s'ensuit que: $\:\forall n\in \N^*, \:\:\pi_n(A) =\overline A_n,\:\: A\equiv A_n \mod \Z/p^n\Z[X].$

Blanc

Bonjour Lou 16

C'est interéssant de constater la différence entre ce que tu proposes et ce qui ressort de la littérature consacrée à Hensel. Sans compter les erreurs que tu as relevées.
Avec cette version, tout devient plus clair et te remercie d'avoir pris à coeur de m'aider. 

Bonne soirée,
Blanc