En algèbre, les bornes de Landau-Mignotte (parfois appelée bornes de Mignotte), 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.

Version de base Soit tel que divise . Si on note (respectivement ) la somme des valeurs absolues des coefficients de (respectivement ) et le degré de , alors

Notations On se fixe des polynômes complexes univariés. On se restreindra plus tard à des polynômes entiers, c'est-à-dire dans . On les note

où sont les degrés respectifs et les coefficients dominants (supposés non nuls) sont .

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

Par le théorème fondamental de l'algèbre, le polynôme a racines (comptées avec multiplicité). On introduit alors la mesure de Mahler de comme

On définit de la même manière , , etc.

L'inégalité de Landau et quelques propriétés fondamentales Landau a prouvé en 1905 une inégalité clef reliant la mesure de Mahler d'un polynôme à sa norme euclidienne.

ce qui est détaillé dans l'article Mesure de Mahler.

On remarque de plus que les normes précédemment définies obéissent aux inégalités suivantes :

Finalement, la mesure de Mahler est multiplicative, c'est-à-dire si alors et satisfait par les relations coefficients racines. On peut aussi remarquer que, pour un polynôme non constant, on a . Voir aussi la conjecture de Lehmer pour une minoration plus précise.

Borne de Mignotte En 1974, Mignotte a utilisé l'inégalité de Landau pour prouver une version de base des bornes suivantes.

Pour les polynômes complexes dans , si divise alors :

.

et les coefficients individuels obéissent aux inégalités suivantes pour tout :

.

Le passage de à s'obtient par les relations coefficients racines tandis que la deuxième inégalité s'obtient par les considérations de la section précédente. En effet :. On en déduit le lien entre en sommant (on a l'égalité par le binôme de Newton).

Pour des polynômes entiers (c'est-à-dire ) alors et si de plus est unitaire alors .

On peut alors obtenir des inégalités plus fines. Si on a tel que divise alors

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 :

En retournant aux bornes sur les coefficients, on en déduit que si est réductible alors il a un facteur non trivial de degré tel que

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 présentent un grand intérêt théorique, on dispose souvent en pratique d'informations sur le degré de . C'est pourquoi les bornes plus fines qui dépendent de sont souvent plus pertinentes.

Précision des bornes

Polynômes cyclotomiques Pour le polynômes cyclotomiques est un diviseur irréductible de degré , où désigne fonction indicatrice d'Euler. Dans ce cas et il est d'usage de noter .

Or, par un théorème de Bateman, on obtient que pour tout et tout entier positif suffisamment grands on a . On trouve alors un écart superpolynomial en le degré entre le coefficient maximum et la borne de Landau-Mignotte ce qui montre qu'elle est loin d'être parfaite. En effet, en utilisant la formule de Stirling ainsi que des bornes de la fonction indicatrice d'Euler, on obtient

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.

Généralisations 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 . En particulier lorsque l'on considère uniquement les polynômes unitaires pour lesquels . 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.

Applications 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 (ce qui est équivalent à factoriser dans en multipliant le polynôme par le ppcm des dénominateurs de ses coefficients), on peut chercher un nombre premier suffisamment grand pour que les coefficients ne soient pas réduis modulo . Les bornes de Mignotte donnent une majoration de la taille d'un tel nombre premier.

En pratique, on factorise pour un nombre premier fixé et on propage la factorisation à pour un 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).

Références

Catégorie:Inégalité Catégorie:Pages avec des traductions non relues