Landau–Mignotte bound

The Landau–Mignotte bound is an upper bound on the size of the coefficients of any factor of a polynomial with integer coefficients, computed from the polynomial alone^[1]. It is needed because divisibility does not make coefficients smaller: a factor can have larger coefficients than the product. The polynomial $x^{105}-1$ has coefficients 0 and $\pm 1$, yet its factor, the cyclotomic polynomial ${\Phi }_{105}$, has a coefficient $-2$. Algorithms that recover a factor or a gcd from its image modulo some large number $M$, such as Hensel lifting and the modular gcd, need to know in advance how large $M$ must be for the image to determine the integer coefficients uniquely, and the bound tells them. Maurice Mignotte proved it in 1974^[1] from an inequality of Edmund Landau of 1905^[2].

For $f={\sum }_i{a}_i{x}^i\in \mathbb{Z}[x]$, write $\Vert f{\Vert }_2=({\sum }_i{a}_i^2{)}^{1/2}$. If $g={\sum }_{j=0}^k{b}_j{x}^j$ divides $f$ in $\mathbb{Z}[x]$, then^[1][4]:

and so $\Vert g{\Vert }_{\infty }\le \left(\genfrac{}{}{0ex}{}{k}{\lfloor k/2\rfloor }\right)\Vert f{\Vert }_2$ and $\Vert g{\Vert }_1\le 2^k\Vert f{\Vert }_2$. Since $\left(\genfrac{}{}{0ex}{}{k}{\lfloor k/2\rfloor }\right)<2^k$, a factor of degree $k$ has coefficients of at most about $k+{\log }_2\Vert f{\Vert }_2$ bits.

The Mahler measure of $f=a_n{\prod }_i(x-{\alpha }_i)$ is

It is multiplicative, $M(gh)=M(g)M(h)$, and $M(h)\ge |\mathrm{lc}(h)|$ for every $h$, so a factor $g$ of $f$ satisfies $M(g)\le M(f)|\mathrm{lc}(g)/\mathrm{lc}(f)|$. Landau's inequality states that $M(f)\le \Vert f{\Vert }_2$^[2]; Mahler later derived it from Jensen's formula^[3]. Finally, each coefficient $b_j$ of $g$ is $\mathrm{lc}(g)$ times an elementary symmetric function of its roots, a sum of $\left(\genfrac{}{}{0ex}{}{k}{j}\right)$ products of roots, each at most $M(g)/|\mathrm{lc}(g)|$ in absolute value. So $|b_j|\le \left(\genfrac{}{}{0ex}{}{k}{j}\right)M(g)$, and combining the inequalities gives the bound^[1][4].

open Zpoly
 
(* Cyclotomic polynomials by division: x^n - 1 is the product of Phi_d
   over the divisors d of n. Their coefficients are small, but not all 1. *)
let cyclotomic = Hashtbl.create 64
let rec phi n =
  match Hashtbl.find_opt cyclotomic n with
  | Some p -> p
  | None ->
    let xn1 = sub (shift one n) one in
    let p = List.fold_left (fun acc d ->
        if n mod d = 0 && d < n then fst (divmod_exact acc (phi d)) else acc) xn1 (List.init n (fun i -> i + 1)) in
    Hashtbl.replace cyclotomic n p; p

Phi_105: degree 48, largest coefficient 2; factor of x^105 - 1, whose coefficients are 1
Phi_385: degree 240, largest coefficient 3; factor of x^385 - 1, whose coefficients are 1
Phi_1365: degree 576, largest coefficient 4; factor of x^1365 - 1, whose coefficients are 1
Phi_1785: degree 768, largest coefficient 5; factor of x^1785 - 1, whose coefficients are 1
Phi_2805: degree 1280, largest coefficient 6; factor of x^2805 - 1, whose coefficients are 1
bound on the coefficients of a degree-48 factor of x^105 - 1: binom(48, 24) * 2 = 64495207366200

All the factors have larger coefficients than $x^n-1$. Migotti showed in 1883 that ${\Phi }_n$ has only the coefficients 0 and $\pm 1$ when $n$ has at most two distinct odd prime factors^[9], which makes $105=3\cdot 5\cdot 7$ the smallest candidate. The coefficients of cyclotomic polynomials are unbounded, but they grow slowly, and the bound, some fourteen digits for a factor of degree 48, is extremely pessimistic here. Mignotte also showed that the exponential dependence on the degree cannot be avoided in general: there are polynomials with small coefficients whose factors have coefficients exponentially large in the degree^[1].

To recover an integer polynomial $g$ from its image modulo $M$, one takes each coefficient in the symmetric range $(-M/2,M/2]$; this is correct if every coefficient of $g$ is smaller than $M/2$ in absolute value. With $B$ the Landau–Mignotte bound, $M>2B$ suffices. Factorization over the integers lifts a factorization modulo $p$ to one modulo $p^e$ with $p^e>2B$^[7][8], and the modular gcd collects primes until their product exceeds $2B$^[4].

open Zpoly
 
(* f = g h for random g and h with one-digit coefficients: the actual size
   of the factor g against the bound computed from f alone. *)
let random n = normalize (Array.init (n + 1) (fun i ->
    if i = n then Z.of_int (1 + Random.int 9) else Z.of_int (Random.int 19 - 9)))

deg g  deg f  bits of f  bits of g  bits of bound
    4     24          7          4             11
    8     28          8          4             15
   12     32          8          4             19
   16     36          9          4             23
   20     40          9          4             27
   24     44          8          4             31
   28     48          8          4             35
   32     52          9          4             39
   36     56          8          4             43
   40     60          9          4             47

Because the bound is usually far from tight, implementations use sharper variants, such as bounds based on the Bombieri norm^[5], or compare several bounds and take the smallest^[6], and they test candidates before the bound is reached.

Landau proved his inequality for the product of the absolute values of the roots outside the unit circle in 1905, in the context of complex analysis^[2]. Mahler introduced the measure that bears his name and related it to Jensen's formula in 1960^[3]. The need for coefficient bounds arose with Zassenhaus's algorithm for factoring integer polynomials by Hensel lifting in 1969^[7], and Mignotte's paper of 1974 gave the bound that is now standard^[1]. Refinements based on other norms followed from the 1990s^[5][6].

• Hensel liftingHensel lifting turns a factorization of a polynomial modulo a prime p into a factorization modulo p², p⁴ and so on, as long as the factors modulo p are coprime. Each step solves a linear equation using the Bézout relation between the factors, and in quadratic form it doubles the precision, the p-adic analogue of Newton's method. It is the core of Zassenhaus's algorithm for factoring integer polynomials: factor modulo a small prime, lift until the modulus exceeds twice the Landau–Mignotte bound, and recombine the lifted factors into true factors over the integers.
• Modular GCDThe modular GCD algorithm computes the greatest common divisor of two polynomials with integer coefficients by computing it modulo many machine-word primes, where coefficients never grow, and reconstructing the integer coefficients with the Chinese remainder theorem once the product of the primes exceeds twice a bound on them. Primes that divide the leading coefficients are skipped, unlucky primes that give an image of too high a degree are detected and discarded, and a final trial division certifies the result. The intermediate numbers are no larger than the answer, which makes it far faster than remainder-sequence methods; it was introduced by Brown in 1971.
• Swinnerton-Dyer polynomialThe Swinnerton-Dyer polynomials are the integer polynomials SD_k(x) = ∏(x ± √p₁ ± √p₂ ± … ± √p_k), taken over all 2^k sign choices, for the first k primes. They are irreducible over the integers but factor into polynomials of degree at most two modulo every prime, because their Galois group (ℤ/2)^k has no element of order greater than two. They are the worst case for the Berlekamp–Zassenhaus factoring algorithm: every prime yields at least 2^(k−1) modular factors, and before concluding that the polynomial is irreducible the algorithm must try exponentially many subsets of them. They motivated the lattice-based factoring algorithms of Lenstra, Lenstra and Lovász and of van Hoeij.
• Cantor–Zassenhaus algorithmThe Cantor–Zassenhaus algorithm is a randomized method for factoring polynomials over a finite field. After the input is made square-free, distinct-degree factorization separates the irreducible factors by degree, using the fact that x^(p^d) − x is the product of all monic irreducibles whose degree divides d. Each group, a product of factors of the same degree d, is then split by taking the gcd with a^((p^d − 1)/2) − 1 for a random polynomial a: by the Chinese remainder theorem, this power is +1 or −1 independently in each factor's field, so the gcd separates the factors with probability about one half. It runs in expected polynomial time and is the standard method in computer algebra systems.
• Subresultant PRSThe subresultant polynomial remainder sequence is a way of running Euclid's algorithm on polynomials over the integers, or any integral domain, without fractions and without the exponential coefficient growth of plain pseudo-division. After each pseudo-division, the remainder is divided by a factor computed from the previous leading coefficients and degree differences; the division is always exact, and the remainders obtained are the subresultants of the input, determinants of submatrices of the Sylvester matrix, whose size grows only linearly with the degree. The sequence yields the gcd, up to a constant, and the resultant. It was introduced by Collins in 1967 and developed by Brown and Traub.

1. [1]M. Mignotte, “An inequality about factors of polynomials”, Mathematics of Computation 28 (1974).
2. [2]E. Landau, “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 (1905).
3. [3]K. Mahler, “An application of Jensen’s formula to polynomials”, Mathematika 7 (1960).
4. [4]J. von zur Gathen, J. Gerhard, Modern Computer Algebra, §6.6, Cambridge University Press (3rd ed., 2013).
5. [5]B. Beauzamy, V. Trevisan, P. S. Wang, “Polynomial factorization: sharp bounds, efficient algorithms”, Journal of Symbolic Computation 15 (1993).
6. [6]J. Abbott, “Bounds on factors in Z[x]”, Journal of Symbolic Computation 50 (2013).
7. [7]H. Zassenhaus, “On Hensel factorization, I”, Journal of Number Theory 1 (1969).
8. [8]D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, §4.6.2, Addison-Wesley (3rd ed., 1997).
9. [9]A. Migotti, “Zur Theorie der Kreisteilungsgleichung”, Sitzungsberichte der Mathematisch-Naturwissenschaftlichen Classe der Kaiserlichen Akademie der Wissenschaften, Wien 87 (1883).

last updated 28 September 2026