Jump to content

Landau-Mignotte bound

From Wikipedia, the free encyclopedia

In algebra, a Landau-Mignotte bound (sometimes only referred to as Mignotte's bound[1]) 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.[2]

Basic version

[edit]

For such that divides denote by resp. the sum of the absolute values of the coefficients of resp. and let be the degree of , then

Notation

[edit]

will be univariate complex polynomials which later will be restricted to be integer polynomials, i.e. in . Explicitly

are the degrees, the leading coefficients are .

Define norms by considering the coefficients as vectors, explicitly

By the fundamental theorem of algebra has roots (with multiplicity). Set the Mahler measure of to be

Similarly define , , etc.

Landau's inequality and other basic properties

[edit]

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

In general norms obey the following inequalities

The Mahler measure satisfies which for non-trivial integer polynomials implies . See also Lehmer's conjecture.

The Mahler measure is multiplicative, i.e. if then

Mignotte's bound

[edit]

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 , if divides then

and individual coefficients obey the inequalities

If additionally and are integer polynomials in then and if is additionally monic then even . In these cases one can simplify by omitting the fraction. Including products in the analysis we have the following theorem.

Let such that divides then

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

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

If is reducible then it has a non-trivial factor of degree such that

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

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

Sharpness of bounds

[edit]

Cyclotomic polynomials

[edit]

For the cyclotomic polynomials is an irreducible divisor of degree , Euler's totient function. In this case and it is custom to denote . A result of Vaugn states[5] for infinitely many positive integers

a superpolynomial bound in the degree .

Comparing with Mignotte's bound and using Stirling's formula as well as bounds for Euler's totient function we get for infinitely many

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[6] for every for all sufficiently large positive integers we have

Also note that despite the superpolynomial growth of Vaugn's lower bound in practice looking at examples of cyclotomic polynomials the coefficients of are far smaller than Mignotte's bound.

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

[edit]

Abbot gives the following example[7] related to cyclotomic polynomials. Set

and consider for positive integers

Note that the degrees are resp. . Abbot shows that asymptotically for large we have

Using Mignotte's bound in the version we compare

Ignoring the root terms leads to

Abbot claims that[7]: 24 

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[7]: 7ff .

Also note that, while the cyclotomic polynomials from the previous section are irreducible factors, the factors have many factors themselves. Abbot speculates[7]: 32 

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 . This suggests that such an ideal single factor bound could be very much smaller than the currently known ones.

Generalizations

[edit]

Usually the Mignotte bounds are only stated for complex or integer polynomials. They are equally valid for any subring , in particular when considering only monic polynomials for which .

Any abstract number field and its ring of integers can be considered a subring of , 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 .

Applications

[edit]

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

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 from a solution for .

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.

See also

[edit]

References

[edit]
  1. ^ a b Bhatt, Bhuvanesh. "Landau-Mignotte Bound". MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. Wolfram Research Inc. Retrieved 2023-05-06.
  2. ^ a b c von zur Gathen, Joachim; Gerhard, Jürgen (2013). Modern Computer Algebra. Cambridge UK: Cambridge University Press. ISBN 9781139856065.
  3. ^ Landau, Edmund (1905). "Sur quelques théorèmes de M. Petrovitch relatifs aux zéros des fonctions analytiques". Bulletin de la Société Mathématique de France. 33: 251–261. doi:10.24033/BSMF.760.
  4. ^ Mignotte, Maurice (1974). "An Inequality About Factors of Polynomials". Mathematics of Computation. 28 (128): 1153–1157. doi:10.2307/2005373. JSTOR 2005373.
  5. ^ Vaughan, R. C. (1975). "Bounds for the coefficients of cyclotomic polynomials". Michigan Math. J. 21 (4): 289–295. doi:10.1307/mmj/1029001352.
  6. ^ Bateman, Paul T. (1981). "On the Size of the Coefficients of the Cyclotomic Polynomial". Séminaire de Théorie des Nombres de Bordeaux: 1–17. JSTOR 44165422.
  7. ^ a b c d e Abbott, John (2013). "Bounds on factors in Z[x]". Journal of Symbolic Computation. 50: 532–563. arXiv:0904.3057. doi:10.1016/j.jsc.2012.09.004. S2CID 15176498.