Next: Modular Gcd Algorithms in [x] Up: Advanced Computer Algebra: The resultant Previous: Lucky and unlucky modular reductions

# Mignotte's factor bound

Definition 6   Let f =  fixi be a univariate polynomial over . The 2-norm of f is defined by

 | f|2  =   | fi|2 (72)

where | z| denotes the square root of the product of z by its conjugate .

Remark 9   Given f =  fixi we shall compute a bound B such that for any h [x] we have

 h  |  f        | h|2   B (73)

One could hope that B = | f|2 would work. Unfortunately there are some counter-examples. Though they are very rare, there are infinitely many of them.
(2) -> factor(x^105 - 1)

(2)
2           4    3    2
(x - 1)(x  + x + 1)(x  + x  + x  + x + 1)

*
6    5    4    3    2
(x  + x  + x  + x  + x  + x + 1)

*
8    7    5    4    3
(x  - x  + x  - x  + x  - x + 1)
*
12    11    9    8    6    4    3
(x   - x   + x  - x  + x  - x  + x  - x + 1)
*
24    23    19    18    17    16    14    13
x   - x   + x   - x   + x   - x   + x   - x

12    11    10    8    7   6    5
+ x   - x   + x   - x  + x - x  + x  - x + 1

*
48    47    46    43    42     41    40
x   + x   + x   - x   - x   - 2x   - x

39    36    35    34    33
- x   + x   + x   + x   + x

32    31    28    26    24    22    20
+ x   + x   - x   - x   - x   - x   - x

17    16    15    14    13
+ x   + x   + x   + x   + x

12    9    8     7    6    5    2
+ x   - x  - x  - 2x  - x  - x  + x  + x + 1
Type: Factored Polynomial Integer
Worse than that: for every B > 0 there exist infinitely many n such that there exists a polynomial h dividing xn - 1 and satisfying | h|2 > B. See [vzGG99] for more details.

Lemma 3   For f [x] and z we have

 |(x-z)f|2  =  |( x-1)f|2 (74)

Proof. Let f =  fixi and define f-1 = fn+1 = 0. We calculate

 |(x-z)f|22 = | fi-1 - zfi|2 = (fi-1 - zfi) = | f|22(1 + | z) +   - fi-1  - zfi = | f|22( | z + 1) +   - z  fi -  fi-1 = (fi-1 - fi)(z - ) = |fi-1 - fi|2 = |( x-1)f|2
(75)

Definition 7   Let z1,..., zn be the complex roots of the polynomial

 f  =   fixi  =  fn  (x - zi) (76)

We define the measure of the polynomial f by

 M(f )  =   | fn |   max(1, | zi | ) (77)

Remark 10   For f, g [x] the following statements are easy to prove:
1. M(f  lc(f ).
2. M(fg)  =  M(fM(g).
The following theorem of Landau (1905) relates M(f ) and | f|2.

Theorem 4 (Landau)   For any f [x] we have

 M(f )   | f|2 (78)

Proof. We arrange the roots z1,..., zn of f such that

 | z1 | ,..., | zk |   >  1    and    | zk+1 | ,..., | zn |    1 (79)

Therefore

 M(f )  =   | fn . z1 ... zk | (80)

Let

 g = fn (z - 1)(x - zj) = gnxn + ... + g0
(81)

We calculate

 M(f )2 = | fn . z1 ... zk = | fn . ... = | gn | g|22 = |(x-z1)|22 = ... = |(x-z1) ... (x-zk)|22 = | f|22
(82)

where we made repeated use of Lemma 3.

Remark 11   Given f =  fixi it is convenient to use the 1-norm

 | f|1  =    | fi | (83)

and the -norm

 | f|  =  ( | fi | ) (84)

The following inequalities are classical.

 | f|   | f|2   | f|1   (n + 1) | f|    and    | f|2   (n + 1)1/2 | f| (85)

Theorem 5   Let f =  fixi and h =  hixi be two polynomials such that h divides f. Then we have

 | h|2   | h|1   2m M(h)    2m | f|2 (86)

Proof. Let us write

 h  =  hn  (x - ui) (87)

where u1,..., um are the roots of h and thus among the roots of f. Observe that the coefficient hi of h (in the term of degree i)
• is a sum of products, where each product consists of m - i factors, each of these factors being a root of h.
• Hence each of these factors is bounded by M(h).
• Moreover there are of these factors. Indeed, in order to build one of these factors, one needs to choose i roots among the m of h.
So for i = 0 ... m we have

 | hi |    M(h) (88)

This implies

 | h|1 = | hi | M(h) = M(h) (1 + 1)m = M(h) 2m
(89)

Now observe that the measures of h and f satisfy

 M(h)   M(f ) (90)

Relations (89) and (90) together we Theorem 4 leads to

 | h|2   | h|1   M(h) 2m   M(f ) 2m   | f|2 2m (91)

The theorem is proved.

Corollary 4 (Mignotte's bound)   Let f, g, h [x] be univariate polynomials with degrees n, m, k respectively. If the product g h divides f in [x] then we have

 | g| | h|   | g|2 | h|2   | g|1 | h|1   2m+k | f|2   (n + 1)1/2 2m+k | f| (92)

Proof. The first, the second and the fourth above inequalities follow directly from the classical relations between the norms .  |1, .  |2 and .  | given in Remark 11. So the only inequality to prove is

 | g|1 | h|1   2m+k | f|2. (93)

From Theorem 5 (that essentially relates the 1-norm of a polynomial with its measure) we have

 | g|1   2m M(g)    and    | h|1   2k M(h). (94)

From the elementary properties of the measure of a polynomial given in Remark 10 we have

 M(g) M(h)   M(f ). (95)

By virtue of Landau's inequality (Theorem 4) we have

 M(f )   | f|2. (96)

Putting all these relations together leads to

 | g|1 | h|1   2m+k M(g) M(h)   2m+k M(f )   2m+k | f|2. (97)

The corollary is proved.

Remark 12   Applying Corollary 4 to g = 1 and keeping f, g as before leads to the following bound for every coefficient of every factor h of f.

 | h|   (n + 1)1/2 2n | f| (98)

Next: Modular Gcd Algorithms in [x] Up: Advanced Computer Algebra: The resultant Previous: Lucky and unlucky modular reductions
Marc Moreno Maza
2003-06-06