Landau-Mignotte bound

also: mignotte bound, coefficient bound

A bound on the coefficients of any factor of an integer polynomial, in terms of the degree and norm of the polynomial itself. It is what tells a Hensel lift when to stop: once the modulus exceeds twice the bound, a symmetric representative is the integer factor rather than merely congruent to it.

A bound on the coefficients of any factor of an integer polynomial, in terms of the polynomial itself. If $g ∣ f$ in $Z [x]$ with $de g g = m$ and $de g f = n$ , then

∥ g ∥_{\infty} \leq ∥ g ∥_{1} \leq 2^{m} \frac{∣ lc ( g ) ∣}{∣ lc ( f ) ∣} ∥ f ∥_{2}

The point is not the constant, which is generous, but that the bound exists and is computable before any factor is known. That is what makes Hensel lifting terminate: lift until the modulus exceeds twice the bound, and a symmetric representative modulo $p^{k}$ can only be the integer itself.

A safe, cheap version: the 2-norm is at most (n+1) times the max norm.

let coefficient_bound f =
  let n = Upoly.degree f in
  Bigint.mul (Bigint.pow (Bigint.of_int 2) n)
    (Bigint.mul (Bigint.of_int (n + 1)) (Upoly.max_norm f))
 
let lift_exponent p bound =
  let target = Bigint.mul (Bigint.of_int 2) bound in
  let k = ref 1 and m = ref (Bigint.of_int p) in
  while Bigint.compare !m target <= 0 do
    m := Bigint.mul !m (Bigint.of_int p); incr k
  done;
  !k

Being generous costs real time, since $k$ sets how many lifting steps run, and being wrong costs correctness. Tighter bounds exist and are worth using; what is not negotiable is that the bound be a bound.