Landau-Mignotte bound

Short description: Bound on the coefficients of a factor polynomial

In algebra, a Landau-Mignotte bound (sometimes only referred to as Mignotte's bound) is one of a family of inequalities concerning a univariate integer polynomial f(x) and one of its factors h(x). A basic version states that the coefficients of h(x) are bounded independently of h(x) by an exponential expression involving only the degree and coefficients of f(x), i.e. only depending on f(x).

It has applications in computer algebra where these bounds can give a priori estimates on the run time and complexity of algorithms.

Basic version

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

[math]\displaystyle{ \|h\|_{1}\leq 2^{n}\|f\|_{1} }[/math]

Notation

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

[math]\displaystyle{ f=\sum\limits_{i=0}^nf_ix^i,\ \ \ g=\sum\limits_{i=0}^mg_ix^i,\ \ \ h=\sum\limits_{i=0}^kh_ix^i. }[/math]

[math]\displaystyle{ n,m,k }[/math] are the degrees, the leading coefficients are [math]\displaystyle{ f_n,g_m,h_k }[/math].

Define norms by considering the coefficients as vectors, explicitly

[math]\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|. }[/math]

By the fundamental theorem of algebra [math]\displaystyle{ f }[/math] has [math]\displaystyle{ n }[/math] roots [math]\displaystyle{ z_1,z_2,\ldots,z_n }[/math] (with multiplicity). Set the Mahler measure of [math]\displaystyle{ f }[/math] to be

[math]\displaystyle{ M(f)=|f_n|\prod\limits_{i=1}^n\max\{1,|z_i|\}. }[/math]

Similarly define [math]\displaystyle{ \|g\|_{2} }[/math], [math]\displaystyle{ M(h) }[/math], etc.

Landau's inequality and other basic properties

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

[math]\displaystyle{ M(f)\leq\|f\|_{2} }[/math]

In general norms obey the following inequalities

[math]\displaystyle{ \|f\|_{\infty}\leq\|f\|_{2}\leq\|f\|_{1}\leq\sqrt{n+1}\|f\|_{2}\leq(n+1)\|f\|_{\infty}. }[/math]

The Mahler measure satisfies [math]\displaystyle{ M(f)\geq|f_n| }[/math] which for non-trivial integer polynomials implies [math]\displaystyle{ M(f)\geq 1 }[/math]. See also Lehmer's conjecture.

The Mahler measure is multiplicative, i.e. if [math]\displaystyle{ f=gh }[/math] then

[math]\displaystyle{ M(f)=M(g)M(h). }[/math]

Mignotte's bound

Mignotte used Landau's inequality in 1974 to prove a basic version of the following bounds in the notation introduced above.

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

[math]\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 }[/math]

and individual coefficients obey the inequalities

[math]\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 }[/math]

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

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

[math]\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}, }[/math]

[math]\displaystyle{ \|h\|_{\infty} \leq \|h\|_{2} \leq \|h\|_{1} \leq 2^{k}\|f\|_2 \leq 2^n\|f\|_2 \leq 2^n\|f\|_1, }[/math]

[math]\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}, }[/math]

[math]\displaystyle{ |h_i| \leq \binom{k}{i}M(h) \leq \binom{k}{i}\|f\|_2 \leq \binom{n}{i}\|f\|_2, }[/math]

[math]\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. }[/math]

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

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

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

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

[math]\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. }[/math]

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

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

Sharpness of bounds

Cyclotomic polynomials

For [math]\displaystyle{ f=x^n-1 }[/math] the cyclotomic polynomials [math]\displaystyle{ h=\Phi_n(x) }[/math] is an irreducible divisor of degree [math]\displaystyle{ k=\varphi(n) }[/math], Euler's totient function. In this case [math]\displaystyle{ \|f\|_{2}=\sqrt{2} }[/math] and it is custom to denote [math]\displaystyle{ \|h\|_{\infty}=A(n) }[/math]. A result of Vaugn states for infinitely many positive integers [math]\displaystyle{ n }[/math]

[math]\displaystyle{ \|h\|_{\infty} =A(n) \gt e^{\left(n^{(\log 2)/(\log\log n)}\right)}, }[/math]

a superpolynomial bound in the degree [math]\displaystyle{ n }[/math].

Comparing with Mignotte's bound and using Stirling's formula as well as bounds for Euler's totient function we get for infinitely many [math]\displaystyle{ n }[/math]

[math]\displaystyle{ e^{\left(n^{(\log 2)/(\log\log n)}\right)}\lt \|h\|_{\infty} \leq \binom{k}{\lfloor k/2\rfloor}\|f\|_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)}}. }[/math]

This leaves a gap between Mignotte's upper bound and what is known to be attained through cyclotomic polynomials. Cyclotomic polynomials cannot close this gap by a result of Bateman that states for every [math]\displaystyle{ \varepsilon\gt 0 }[/math] for all sufficiently large positive integers [math]\displaystyle{ n }[/math] we have

[math]\displaystyle{ \|h\|_{\infty} =A(n) \lt e^{\left(n^{(\log 2+\varepsilon)/(\log\log n)}\right)}. }[/math]

Also note that despite the superpolynomial growth of Vaugn's lower bound in practice looking at examples of cyclotomic polynomials the coefficients of [math]\displaystyle{ h=\Phi_n(x) }[/math] are far smaller than Mignotte's bound.

A family of polynomials with exponential growth in the coefficients of its factors

Abbot gives the following example related to cyclotomic polynomials. Set

[math]\displaystyle{ H(x)=(x+1)(x^2+x+1)=x^3+2x^2+2x+1, \ \ \ F(x)=H(x)\cdot H(-x)=-x^6+1 }[/math]

and consider for positive integers [math]\displaystyle{ j }[/math]

[math]\displaystyle{ h=h_j=H(x)^j, \ \ \ f=f_j=F(x)^j. }[/math]

Note that the degrees are [math]\displaystyle{ k=3j }[/math] resp. [math]\displaystyle{ n=6j }[/math]. Abbot shows that asymptotically for large [math]\displaystyle{ j }[/math] we have

[math]\displaystyle{ \|h_j\|_{\infty}\geq 6^j\frac{1}{3j+1}, \ \ \ \|f_j\|_{\infty}\approx 2^j\sqrt{\frac{2}{\pi j}}. }[/math]

Using Mignotte's bound in the version [math]\displaystyle{ \|h\|_{\infty} \leq 2^{k}\sqrt{n+1}\|f\|_{\infty} }[/math] we compare

[math]\displaystyle{ 3^{n/6}\sqrt{\frac{\pi}{3n}} \approx \frac{6^j\frac{1}{3j+1}}{2^j\sqrt{\frac{2}{\pi j}}} \lesssim \frac{\|h\|_{\infty}}{\|f\|_{\infty}} \leq 2^{k}\sqrt{n+1}= 2^{n/2}\sqrt{n+1} }[/math]

Ignoring the root terms leads to

[math]\displaystyle{ 1.2009^n \approx \sqrt[6]{3}^n \lesssim \frac{\|h\|_{\infty}}{\|f\|_{\infty}} \lesssim \sqrt{2}^n\approx 1.4142^n. }[/math]

Abbot claims that

An exhaustive search in low degrees suggests that this family of factorizations is close to extremal.

While there is still an exponential gap between the example and Mignotte's bound, the example shows that exponential growth is the right order for such a general bound.

Note that Abbot also compares Mignotte's bound with other types of bounds and gives examples where Mignotte's bound is best and examples where other bounds are better.

Also note that, while the cyclotomic polynomials [math]\displaystyle{ h=\Phi_n(x) }[/math] from the previous section are irreducible factors, the factors [math]\displaystyle{ h=h_j=H(x)^j=(x+1)^j(x^2+x+1)^j }[/math] have many factors themselves. Abbot speculates

The examples [...] compel any ideal “irreducible single factor bound” to grow with degree, though the rate of growth appears to be much slower than for single factor bounds valid for any (suitably scaled) factorization in [math]\displaystyle{ \mathbb{C}[x] }[/math]. This suggests that such an ideal single factor bound could be very much smaller than the currently known ones.

Generalizations

Usually the Mignotte bounds are only stated for complex or integer polynomials. They are equally valid for any subring [math]\displaystyle{ R\subset\mathbb{C} }[/math], in particular when considering only monic polynomials for which [math]\displaystyle{ \frac{|h_k|}{|f_n|}=1 }[/math].

Any abstract number field and its ring of integers can be considered a subring of [math]\displaystyle{ \mathbb{C} }[/math], 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.

Applications

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

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 [math]\displaystyle{ f }[/math] from a solution for [math]\displaystyle{ f_p }[/math].

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

See also

• Mignotte's separation bound