Mignotte's coefficient bound
ProvedFamousTheorems.mignotte_coefficient_boundMignotte's coefficient bound. Let be complex polynomials with Mahler measure . Then every coefficient of satisfies
In the typical application divides an integer polynomial , and is a nonzero integer polynomial, so . The bound then limits the coefficients of any factor of in terms of alone, using (Landau's inequality). This is the basis of the Berlekamp–Zassenhaus and LLL algorithms for factoring integer polynomials.
Formalization note. Mathlib's Polynomial.norm_coeff_le_choose_mul_mahlerMeasure_of_one_le_mahlerMeasure. g.natDegree.choose n is the binomial coefficient , cast to , and mahlerMeasure is the Mahler measure.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem mignotte_coefficient_bound (n : ℕ) (g h : Polynomial ℂ) (hh : 1 ≤ h.mahlerMeasure) :
‖g.coeff n‖ ≤ (g.natDegree.choose n : ℝ) * (g * h).mahlerMeasure := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Polynomial.norm_coeff_le_choose_mul_mahlerMeasure_of_one_le_mahlerMeasure`. Proof here reduces to that Mathlib result.