Bornes de Landau-Mignotte

En algèbre, les bornes de Landau-Mignotte (parfois appelée bornes de Mignotte ^[1]), du nom du mathématicien allemand Edmund Landau et du mathématicien français Maurice Mignotte, font partie d'une famille d'inégalités reliant un polynôme entier univarié P(X) à l'un de ses facteurs Q(X). Une version de base stipule que les coefficients de Q(X) sont bornés indépendamment de Q(X) par une expression exponentielle impliquant uniquement le degré et les coefficients de P(X), c'est-à-dire dépendant uniquement de P(X).

Cette borne a des applications en calcul formel où ces limites peuvent donner des estimations a priori sur le temps d'exécution et la complexité des algorithmes^[2].

Pour ${\displaystyle P,Q\in \mathbb {Z} [x]}$ tel que ${\displaystyle Q(x)}$ divise ${\displaystyle P(x)}$. Si on note ${\displaystyle \|Q\|_{1}}$ (respectivement ${\displaystyle \|P\|_{1}}$) la somme des valeurs absolues des coefficients de ${\displaystyle Q(x)}$ (respectivement ${\displaystyle P(x)}$) et ${\displaystyle n}$ le degré de ${\displaystyle P(x)}$, alors

${\displaystyle \|Q\|_{1}\leq 2^{n}\|P\|_{1}}$

On se fixe ${\displaystyle P,Q,R\in \mathbb {C} [X]}$ des polynômes complexes univariés. On se restreindra plus tard à des polynômes entiers, c'est-à-dire dans ${\displaystyle \mathbb {Z} [x]}$ . On les notes

${\displaystyle P=\sum \limits _{i=0}^{n}p_{i}X^{i},\ \ \ Q=\sum \limits _{i=0}^{m}q_{i}X^{i},\ \ \ R=\sum \limits _{i=0}^{k}r_{i}X^{i}.}$

où ${\displaystyle n,m,k}$ sont les degrés respectifs et les coefficients dominants sont ${\displaystyle p_{n},q_{m}{\text{ et }}r_{k}}$.

On défini les normes suivantes en considérant les coefficients des polynômes comme des vecteurs, explicitement

${\displaystyle \|P\|_{\infty }=\max _{0\leq i\leq n}|p_{i}|,\ \ \ \|P\|_{2}=\left(\sum \limits _{i=0}^{n}|p_{i}|^{2}\right)^{1/2},\ \ \ \|P\|_{1}=\sum \limits _{i=0}^{n}|p_{i}|.}$

Par le théorème fondamental de l'algèbre, le polynôme ${\displaystyle P}$ a ${\displaystyle n}$ racines ${\displaystyle z_{1},z_{2},\ldots ,z_{n}}$ (comptées avec multiplicité). On introduit aussi la mesure de Mahler de ${\displaystyle P}$ comme

${\displaystyle M(P)=|p_{n}|\prod \limits _{i=1}^{n}\max\{1,|z_{i}|\}.}$

On définit de la même manière ${\displaystyle \|Q\|_{2}}$, ${\displaystyle M(R)}$, etc.

Landau a prouvé ^[3] en 1905 une inégalité clef reliant la mesure de Mahler d'un polynôme à sa norme euclidienne.

${\displaystyle M(P)\leq \|P\|_{2}}$ ce qui est détaillé dans l'article Mesure de Mahler.

En général, les normes ainsi définies obéissent aux inégalités suivantes

${\displaystyle \|P\|_{\infty }\leq \|P\|_{2}\leq \|P\|_{1}\leq {\sqrt {n+1}}\|P\|_{2}\leq (n+1)\|P\|_{\infty }.}$

Tandis que la mesure de Mahler satisfait ${\displaystyle M(P)\geq |p_{n}|}$ par les relations coefficients racines. De plus, pour un polynôme non constant, on a ${\displaystyle M(P)\geq 1}$. Voir aussi la conjecture de Lehmer.

La mesure de Mahler est multiplicative, c'est-à-dire si ${\displaystyle P=QR}$ alors

${\displaystyle M(P)=M(Q)M(R).}$

En 1974, Mignotte a utilisé l'inégalité de Landau pour prouver une version de base^[4] des bornes suivantes^[2] dans la notation introduite ci-dessus.

Pour les polynômes complexes dans ${\displaystyle \mathbb {C} [X]}$, si ${\displaystyle Q}$ divise ${\displaystyle P}$ alors

${\displaystyle \|Q\|_{1}\leq 2^{m}M(Q)\leq 2^{m}{\frac {|q_{m}|}{|p_{n}|}}\|P\|_{2}\leq 2^{m}{\frac {|q_{m}|}{|p_{n}|}}\|P\|_{2}}$

et les coefficients individuels obéissent aux inégalités suivantes pour tout ${\displaystyle i\in [\![0,m]\!]}$

${\displaystyle |q_{i}|\leq {\binom {m}{i}}M(Q)\leq {\binom {m}{i}}{\frac {|q_{m}|}{|p_{n}|}}\|P\|_{2}\leq {\binom {n}{i}}{\frac {|q_{m}|}{|p_{n}|}}\|P\|_{2}}$

La relation entre ${\displaystyle |q_{i}|}$ et ${\displaystyle {\binom {m}{i}}M(Q)}$ s'obtient par relations coefficients racines tandis que la deuxième inégalité s'obtient par les considérations de la section précédente. On en déduit le lien entre ${\displaystyle \|Q\|_{1}{\text{ et }}\|P\|_{2}}$ en sommant (on a l'égalité ${\displaystyle \sum _{k=0}^{n}{\binom {n}{k}}=2^{n}}$ par le binôme de Newton).

Si de plus ${\displaystyle P{\text{ et }}Q}$ sont à coefficients entiers (c'est à dire ${\displaystyle P,Q\in \mathbb {Z} [X]}$) alors ${\displaystyle 0<{\frac {|q_{m}|}{|p_{n}|}}\leq 1}$ et si de plus ${\displaystyle P}$ est unitaire alors ${\displaystyle p_{n}=q_{m}=1}$.

Laisser ${\displaystyle P,Q,R\in \mathbb {Z} [X]}$ tel que ${\displaystyle QR}$ divise ${\displaystyle P}$ alors

${\displaystyle \|Q\|_{\infty }\|R\|_{\infty }\leq \|Q\|_{2}\|R\|_{2}\leq \|Q\|_{1}\|R\|_{1}\leq 2^{m+k}\|P\|_{2}\leq 2^{n}{\sqrt {n+1}}\|P\|_{\infty },}$

${\displaystyle \|R\|_{\infty }\leq \|R\|_{2}\leq \|R\|_{1}\leq 2^{k}\|P\|_{2}\leq 2^{n}\|P\|_{2}\leq 2^{n}\|P\|_{1},}$

${\displaystyle \|R\|_{\infty }\leq \|R\|_{2}\leq \|R\|_{1}\leq 2^{k}\|P\|_{2}\leq 2^{k}{\sqrt {n+1}}\|P\|_{\infty }\leq 2^{n}{\sqrt {n+1}}\|P\|_{\infty },}$

${\displaystyle |r_{i}|\leq {\binom {k}{i}}M(R)\leq {\binom {k}{i}}\|P\|_{2}\leq {\binom {n}{i}}\|P\|_{2},}$

${\displaystyle \|R\|_{\infty }\leq {\binom {k}{\lfloor k/2\rfloor }}\|P\|_{2}\leq {\binom {n}{\lfloor n/2\rfloor }}\|P\|_{2}\leq {\binom {n}{\lfloor n/2\rfloor }}\|P\|_{1}.}$

En utilisant la formule de Stirling appliquée aux coefficients binomiaux, nous obtenons asymptotiquement une légère amélioration lors de l'utilisation de coefficients binomiaux

${\displaystyle \|R\|_{\infty }\leq {\binom {n}{\lfloor n/2\rfloor }}\|P\|_{2}\approx 2^{n}{\sqrt {\frac {2}{\pi n}}}\|P\|_{2}.}$

À partir des bornes des coefficients individuels, on peut déduire la limite connexe suivante.

Si ${\displaystyle P\in \mathbb {Z} [X]}$ est réductible alors il a un facteur non trivial ${\displaystyle R}$ de degré ${\displaystyle k\leq \lfloor n/2\rfloor }$ tel que

${\displaystyle \|R\|_{\infty }\leq {\binom {\lfloor n/2\rfloor }{\lfloor n/4\rfloor }}\|P\|_{2}\leq {\binom {\lfloor n/2\rfloor }{\lfloor n/4\rfloor }}\|P\|_{1}.}$

En combinant cela avec la formule de Stirling pour remplacer les coefficients binomiaux, on obtient des versions plus explicites.

Bien que ces bornes indépendantes de ${\displaystyle R}$ et ne dépendant que de ${\displaystyle P}$ présentent un grand intérêt théorique, on dispose souvent en pratique d'informations sur le degré ${\displaystyle k}$ de ${\displaystyle R}$ . C'est pourquoi les limites plus nettes qui dépendent en outre de ${\displaystyle k}$ sont souvent plus pertinents.

Habituellement, les limites de Mignotte ne sont utilisées que pour les polynômes complexes ou entiers. Ils sont cependant tout autant valables pour n'importe quel sous-anneau ${\displaystyle R\subset \mathbb {C} }$. En particulier lorsque l'on considère uniquement les polynômes unitaires pour lesquels ${\displaystyle {\frac {|h_{k}|}{|f_{n}|}}=1}$ .

En calcul formel, il est commun de vouloir factoriser des polynômes. Cela est possible dans les corps finis, par exemple en utilisant l'algorithme de Berlekamp ou de Cantor-Zassenhaus. Afin d'étendre ces algorithmes pour factoriser des polynômes de ${\displaystyle \mathbb {Z} [X]}$ (ce qui est équivalent à ${\displaystyle \mathbb {Q} [X]}$ en multipliant le polynôme par le ppcm des dénominateurs de ses coefficients) on peut chercher un nombre premier ${\displaystyle p}$ tel que les coefficients ne soient pas réduis modulo ${\displaystyle p}$. Les bornes de Mignotte donnent une majoration de la taille d'un tel nombre premier.

En pratique, on utilise plutôt le lemme de relèvement de Hensel plutôt que de chercher un grand nombre premier.

• Portail de l’algèbre