Landau-Mignotte bound

For ${\displaystyle f(x),h(x)\in \mathbb {Z} [x]}$ such that ${\displaystyle h(x)}$ divides ${\displaystyle f(x)}$ denote by ${\displaystyle \|h\|_{1}}$ resp. ${\displaystyle \|f\|_{1}}$ the sum of the absolute values of the coefficients of ${\displaystyle h(x)}$ resp. ${\displaystyle f(x)}$ and let ${\displaystyle n}$ be the degree of ${\displaystyle f(x)}$, then

${\displaystyle \|h\|_{1}\leq 2^{n}\|f\|_{1}}$

${\displaystyle f,g,h\in \mathbb {C} [x]}$ will be univariate complex polynomials which later will be restricted to be integer polynomials, i.e. in ${\displaystyle \mathbb {Z} [x]}$. Explicitly

${\displaystyle f=\sum \limits _{i=0}^{n}f_{i}x^{i},\ \ \ g=\sum \limits _{i=0}^{m}g_{i}x^{i},\ \ \ h=\sum \limits _{i=0}^{k}h_{i}x^{i}.}$

${\displaystyle n,m,k}$ are the degrees, the leading coefficients are ${\displaystyle f_{n},g_{m},h_{k}}$.

Define norms by considering the coefficients as vectors, explicitly

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

By the fundamental theorem of algebra ${\displaystyle f}$ has ${\displaystyle n}$ roots ${\displaystyle z_{1},z_{2},\ldots ,z_{n}}$ (with multiplicity). Set the Mahler measure of ${\displaystyle f}$ to be

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

Similarly define ${\displaystyle \|g\|_{2}}$, ${\displaystyle M(h)}$, etc.

Landau proved[3] in 1905 a key inequality linking the Mahler measure of a polynomial to its Euclidean norm.

${\displaystyle M(f)\leq \|f\|_{2}}$

In general norms obey the following inequalities

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

The Mahler measure satisfies ${\displaystyle M(f)\geq |f_{n}|}$ which for non-trivial integer polynomials implies ${\displaystyle M(f)\geq 1}$. See also Lehmer's conjecture.

The Mahler measure is multiplicative, i.e. if ${\displaystyle f=gh}$ then

${\displaystyle M(f)=M(g)M(h).}$

Mignotte used Landau's inequality in 1974 to prove a basic version[4] of the following bounds[2]^{: 164 ff} in the notation introduced above.

For complex polynomials in ${\displaystyle \mathbb {C} [x]}$, if ${\displaystyle h}$ divides ${\displaystyle f}$ then

${\displaystyle \|h\|_{1}\leq 2^{k}M(h)\leq 2^{k}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}\leq 2^{n}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}}$

and individual coefficients obey the inequalities

${\displaystyle |h_{i}|\leq {\binom {k}{i}}M(h)\leq {\binom {k}{i}}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}\leq {\binom {n}{i}}{\frac {|h_{k}|}{|f_{n}|}}\|f\|_{2}}$

If additionally ${\displaystyle f}$ and ${\displaystyle h}$ are integer polynomials in ${\displaystyle \mathbb {Z} [x]}$ then ${\displaystyle 0<{\frac {|h_{k}|}{|f_{n}|}}\leq 1}$ and if ${\displaystyle f}$ is additionally monic then even ${\displaystyle {\frac {|h_{k}|}{|f_{n}|}}=1}$. In these cases one can simplify by omitting the fraction. Including products in the analysis we have the following theorem.

Let ${\displaystyle f,g,h\in \mathbb {Z} [x]}$ such that ${\displaystyle gh}$ divides ${\displaystyle f}$ then

${\displaystyle \|g\|_{\infty }\|h\|_{\infty }\leq \|g\|_{2}\|h\|_{2}\leq \|g\|_{1}\|h\|_{1}\leq 2^{m+k}\|f\|_{2}\leq 2^{n}{\sqrt {n+1}}\|f\|_{\infty },}$

${\displaystyle \|h\|_{\infty }\leq \|h\|_{2}\leq \|h\|_{1}\leq 2^{k}\|f\|_{2}\leq 2^{n}\|f\|_{2}\leq 2^{n}\|f\|_{1},}$

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

${\displaystyle |h_{i}|\leq {\binom {k}{i}}M(h)\leq {\binom {k}{i}}\|f\|_{2}\leq {\binom {n}{i}}\|f\|_{2},}$

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

Using Stirling's formula applied to binomial coefficients we get asymptotically a slight improvement when using binomial coefficients

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

From the bounds on the individual coefficients one can deduce the following related bound.

If ${\displaystyle f\in \mathbb {Z} [x]}$ is reducible then it has a non-trivial factor ${\displaystyle h}$ of degree ${\displaystyle k\leq \lfloor n/2\rfloor }$ such that

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

Combining this with Stirling's formula to replace the binomial coefficients leads to more explicit versions.

While the upper bounds that are independent of ${\displaystyle h}$ and only depend on ${\displaystyle f}$ are of great theoretical interest and aesthetic appeal, in practical application one has usually information about the degree ${\displaystyle k}$ of ${\displaystyle h}$. This is why the sharper bounds that additionally depend on ${\displaystyle k}$ are often more relevant.

Usually the Mignotte bounds are only stated for complex or integer polynomials. They are equally valid for any subring ${\displaystyle R\subset \mathbb {C} }$, in particular when considering only monic polynomials for which ${\displaystyle {\frac {|h_{k}|}{|f_{n}|}}=1}$.

Any abstract number field and its ring of integers can be considered a subring of ${\displaystyle \mathbb {C} }$, however there can be multiple embeddings which are inequivalent with respect to absolute values. The Mignotte bounds are abstract and general enough that they hold independent of the chosen embedding. This may be taken as a hint that they are not as tight as possible in principle, as can indeed be seen from competing bounds that are sometimes better[7]^: 7ff.

In computer algebra when doing effective computations with integer polynomials often the following strategy is applied. One reduces a polynomial ${\displaystyle f}$ modulo a suitable prime number ${\displaystyle p}$ to get ${\displaystyle f_{p}}$, solves a related problem over ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ instead of ${\displaystyle \mathbb {Z} }$ which is often simpler, and finally uses Hensel lifting to transfer the result for ${\displaystyle f_{p}}$ back to ${\displaystyle f}$.

Hensel lifting is an iterative process and it is in general not clear when to stop it. The Landau-Mignotte bounds can supply additional a priori information that makes it possible to give explicit bounds on how often Hensel lifting has to be iterated to recover the solution for ${\displaystyle f}$ from a solution for ${\displaystyle f_{p}}$.

In particular this can be applied to factoring integer polynomials[1] or for computing the gcd of integer polynomials[2]^: 166. Although effective, this approach may not be the most efficient, as can be seen in the case of factoring.

• Mignotte's separation bound