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.