Mignotte's factor bound

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

 (72)

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

Remark 9   Given we shall compute a bound such that for any we have

 (73)

One could hope that 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 there exist infinitely many such that there exists a polynomial dividing and satisfying . See [GG99] for more details.

Lemma 3   For and we have

 (74)

Proof. Let and define . We calculate

 (75)

Definition 7   Let be the complex roots of the polynomial

 (76)

We define the measure of the polynomial by

 (77)

Remark 10   For the following statements are easy to prove:
1. .
2. .
The following theorem of Landau (1905) relates and .

Theorem 4 (Landau)   For any we have

 (78)

Proof. We arrange the roots of such that

 (79)

Therefore

 (80)

Let

 (81)

We calculate

 (82)

where we made repeated use of Lemma 3.

Remark 11   Given it is convenient to use the -norm

 (83)

and the -norm

 (84)

The following inequalities are classical.

 (85)

Theorem 5   Let and be two polynomials such that divides . Then we have

 (86)

Proof. Let us write

 (87)

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

 (88)

This implies

 (89)

Now observe that the measures of and satisfy

 (90)

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

 (91)

The theorem is proved.

Corollary 4 (Mignotte's bound)   Let be univariate polynomials with degrees respectively. If the product divides in then we have

 (92)

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

 (93)

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

 (94)

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

 (95)

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

 (96)

Putting all these relations together leads to

 (97)

The corollary is proved.

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

 (98)

Marc Moreno Maza
2008-01-07