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 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 note

${\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 (supposés non nuls) sont ${\displaystyle p_{n},q_{m}{\text{ et }}r_{k}}$.

On définit 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 alors 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.

De plus, les normes précédemment 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 est multiplicative, c'est-à-dire si ${\displaystyle P=QR}$ alors ${\displaystyle M(P)=M(Q)M(R)}$ et 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 pour une minoration plus précise.

La mesure de Mahler est multiplicative

${\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].

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

${\displaystyle \|Q\|_{\infty }\leq \|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}}$ .

Le passage de ${\displaystyle |q_{i}|}$ à ${\displaystyle {\binom {m}{i}}M(Q)}$ s'obtient par les relations coefficients racines tandis que la deuxième inégalité s'obtient par les considérations précédente. En effet :$${\displaystyle \|P\|_{2}\geq M(P)=M\left(P{\frac {Q}{Q}}\right)=M\left({\frac {P}{Q}}\right)M(Q)\geq M(Q).}$$. 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).

Pour les polynômes 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}$.

On peut alors obtenir des inégalités plus fines. Si on a ${\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 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}{\text{ pour tout }}0\leq i\leq k{\text{ et}}}$

${\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 de la borne précédente :

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

En retournant aux bornes sur les coefficients, on en déduit que 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 une majoration encore plus fine.

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 bornes plus fines qui dépendent en outre de ${\displaystyle k}$ sont souvent plus pertinentes.

Pour ${\displaystyle P=X^{n}-1}$ les polynômes cyclotomiques ${\displaystyle R=\Phi _{n}(X)}$ est un diviseur irréductible de degré ${\displaystyle k=\varphi (n)}$, où ${\displaystyle \varphi (n)}$ désigne fonction indicatrice d'Euler. Dans ce cas ${\displaystyle \|P\|_{2}={\sqrt {2}}}$ et il est d'usage de noter ${\displaystyle \|R\|_{\infty }=A(n)}$.

Or par un théorème de Bateman qui stipule^[5] que pour tout ${\displaystyle \varepsilon >0}$ et tout entier positif suffisamment grands ${\displaystyle n}$ nous avons ${\displaystyle \|R\|_{\infty }=A(n)<e^{\left(n^{(\log 2+\varepsilon )/(\log \log n)}\right)}}$, on trouve un écart superpolynomial en le degré ${\displaystyle n}$ entre le coefficient maximum ${\displaystyle \|R\|_{\infty }}$ et la borne de Landau-Mignotte. En effet en utilisant la formule de Stirling ainsi que des bornes de la fonction indicatrice d'Euler, on obtient

${\displaystyle {\binom {k}{\lfloor k/2\rfloor }}\|P\|_{2}={\binom {\varphi (n)}{\lfloor \varphi (n)/2\rfloor }}{\sqrt {2}}\approx 2^{\varphi (n)}{\sqrt {\frac {2}{\pi \varphi (n)}}}{\sqrt {2}}\geq 2^{e^{-\gamma }n/(\log \log n)}{\frac {2}{\sqrt {\pi e^{-\gamma }n/(\log \log n)}}}.}$

Cela laisse donc un écart important entre les bornes de Landau-Mignotte et ce que l'on sait être atteint par les polynômes cyclotomiques.

Habituellement, les bornes de Landau-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}$. On ne peut cependant pas s'aventurer au delà des complexes à cause de l'utilisation de la formule de Jensen (pour les fonctions holomorphes) dans la preuve.

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 à factoriser dans ${\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 factorise pour un nombre premier ${\displaystyle p}$ fixé et on propage la factorisation à ${\displaystyle p^{k}}$ pour un ${\displaystyle k}$ assez grand en utilisant le lemme de relèvement de Hensel plutôt que de chercher un grand nombre premier (ce qui est très coûteux).

• Portail de l’algèbre