Bornes de Landau-Mignotte

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}}$

Summarize Timeline Top Qs Fact Check

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).}$

Summarize Timeline Top Qs Fact Check

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.

Summarize Timeline Top Qs Fact Check

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.