next up previous
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 = $ \Sigma_{{{0 \leq i \leq n}}}^{{}}$ fixi be a univariate polynomial over $ \mbox{${\mathbb C}$}$. The 2-norm of f is defined by

| f|2  =  $\displaystyle \left(\vphantom{ {\Sigma}_{0 \leq i \leq n} \ \vert f_i \vert^2 }\right.$$\displaystyle \Sigma_{{{0 \leq i \leq n}}}^{{}}$ | fi|2$\displaystyle \left.\vphantom{ {\Sigma}_{0 \leq i \leq n} \ \vert f_i \vert^2 }\right)^{{1/2}}_{}$ (72)

where | z| denotes the square root of the product of z by its conjugate $ \overline{{z}}$.

Remark 9   Given f = $ \Sigma_{{{0 \leq i \leq n}}}^{{}}$ fixi we shall compute a bound B such that for any h $ \in$ $ \mbox{${\mathbb C}$}$[x] we have

h  |  f    $\displaystyle \Rightarrow$     | h|2  $\displaystyle \leq$  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 $ \in$ $ \mbox{${\mathbb C}$}$[x] and z $ \in$ $ \mbox{${\mathbb C}$}$ we have

|(x-z)f|2  =  |($\displaystyle \overline{{z}}$ x-1)f|2 (74)

Proof. Let f = $ \Sigma_{{{0 \leq i \leq n}}}^{{}}$ fixi and define f-1 = fn+1 = 0. We calculate

|(x-z)f|22 = $\displaystyle \Sigma_{{{0 \leq i \leq n+1}}}^{{}}$ | fi-1 - zfi|2
  = $\displaystyle \Sigma_{{{0 \leq i \leq n+1}}}^{{}}$ (fi-1 - zfi)$\displaystyle \left(\vphantom{ \overline{f_{i-1} - z f_i} }\right.$$\displaystyle \overline{{f_{i-1} - z f_i}}$$\displaystyle \left.\vphantom{ \overline{f_{i-1} - z f_i} }\right)$
  = | f|22(1 + | z$\displaystyle \mid^{{2}}_{{}}$) + $\displaystyle \Sigma_{{{0 \leq i \leq n+1}}}^{{}}$ $\displaystyle \left(\vphantom{ - f_{i-1} \, \overline{z f_i} - z f_i \overline{f_{i-1}} }\right.$ - fi-1 $\displaystyle \overline{{z f_i}}$ - zfi$\displaystyle \overline{{f_{i-1}}}$$\displaystyle \left.\vphantom{ - f_{i-1} \, \overline{z f_i} - z f_i \overline{f_{i-1}} }\right)$
  = | f|22( | z$\displaystyle \mid^{{2}}_{{}}$ + 1) + $\displaystyle \Sigma_{{{0 \leq i \leq n+1}}}^{{}}$ $\displaystyle \left(\vphantom{ - z \, \overline{f_{i-1}} \, f_i - \overline{z} \, f_{i-1}\, \overline{f_i} }\right.$ - z $\displaystyle \overline{{f_{i-1}}}$ fi - $\displaystyle \overline{{z}}$ fi-1 $\displaystyle \overline{{f_i}}$$\displaystyle \left.\vphantom{ - z \, \overline{f_{i-1}} \, f_i - \overline{z} \, f_{i-1}\, \overline{f_i} }\right)$
  = $\displaystyle \Sigma_{{{0 \leq i \leq n+1}}}^{{}}$ ($\displaystyle \overline{{z}}$fi-1 - fi)(z$\displaystyle \overline{{f_{i-1}}}$ - $\displaystyle \overline{{f_i}}$)
  = $\displaystyle \Sigma_{{{0 \leq i \leq n+1}}}^{{}}$ |$\displaystyle \overline{{z}}$fi-1 - fi|2
  = |($\displaystyle \overline{{z}}$ x-1)f|2
(75)

$ \qedsymbol$

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

f  =  $\displaystyle \Sigma_{{{0 \leq i \leq n}}}^{{}}$ fixi  =  fn $\displaystyle \Pi_{{{1 \leq i \leq n}}}^{{}}$ (x - zi) (76)

We define the measure of the polynomial f by

M(f )  =   | fn |  $\displaystyle \Pi_{{{1 \leq i \leq n}}}^{{}}$ max(1, | zi | ) (77)

Remark 10   For f, g $ \in$ $ \mbox{${\mathbb C}$}$[x] the following statements are easy to prove:
  1. M(f$ \geq$  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 $ \in$ $ \mbox{${\mathbb C}$}$[x] we have

M(f$\displaystyle \leq$  | f|2 (78)

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

| z1 | ,..., | zk |   >  1    and    | zk+1 | ,..., | zn |   $\displaystyle \leq$  1 (79)

Therefore

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

Let

g = fn $\displaystyle \Pi_{{{1 \leq j \leq k}}}^{{}}$($\displaystyle \overline{{z_j}}$z - 1)$\displaystyle \Pi_{{{k < j \leq n}}}^{{}}$(x - zj)
  = gnxn + ... + g0
(81)

We calculate

M(f )2 = | fn . z1 ... zk$\displaystyle \mid^{{2}}_{{}}$
  = | fn . $\displaystyle \overline{{z_1}}$ ... $\displaystyle \overline{{z_k}}$$\displaystyle \mid^{{2}}_{{}}$
  = | gn$\displaystyle \mid^{{2}}_{{}}$
  $\displaystyle \leq$ | g|22
  = |$\displaystyle {\frac{{g}}{{\overline{z_1} x - 1}}}$(x-z1)|22
  = ...
  = |$\displaystyle {\frac{{g}}{{ (\overline{z_1} x - 1) \cdots (\overline{z_k} x - 1)}}}$(x-z1) ... (x-zk)|22
  = | f|22
(82)

where we made repeated use of Lemma 3. $ \qedsymbol$

Remark 11   Given f = $ \Sigma_{{{0 \leq i \leq n}}}^{{}}$ fixi it is convenient to use the 1-norm

| f|1  =  $\displaystyle \Sigma_{{{0 \leq i \leq n}}}^{{}}$  | fi | (83)

and the $ \infty$-norm

| f|$\scriptstyle \infty$  =  $\displaystyle \max_{{{0 \leq i \leq n}}}^{{}}$( | fi | ) (84)

The following inequalities are classical.

| f|$\scriptstyle \infty$  $\displaystyle \leq$  | f|2  $\displaystyle \leq$  | f|1  $\displaystyle \leq$  (n + 1) | f|$\scriptstyle \infty$    and    | f|2  $\displaystyle \leq$  (n + 1)1/2 | f|$\scriptstyle \infty$ (85)

Theorem 5   Let f = $ \Sigma_{{{0 \leq i \leq n}}}^{{}}$ fixi and h = $ \Sigma_{{{0 \leq i \leq m}}}^{{}}$ hixi be two polynomials such that h divides f. Then we have

| h|2  $\displaystyle \leq$  | h|1  $\displaystyle \leq$  2m M(h$\displaystyle \leq$  $\displaystyle \left\vert\vphantom{ \frac{h_m}{f_n} }\right.$$\displaystyle {\frac{{h_m}}{{f_n}}}$$\displaystyle \left.\vphantom{ \frac{h_m}{f_n} }\right\vert$ 2m | f|2 (86)

Proof. Let us write

h  =  hn $\displaystyle \Pi_{{{1 \leq i \leq m}}}^{{}}$ (x - ui) (87)

where u1,..., um $ \in$ $ \mbox{${\mathbb C}$}$ 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) So for i = 0 ... m we have

| hi |   $\displaystyle \leq$  $\displaystyle \left(\vphantom{ \begin{array}{c} m \\  i \end{array} }\right.$$\displaystyle \begin{array}{c} m \\  i \end{array}$$\displaystyle \left.\vphantom{ \begin{array}{c} m \\  i \end{array} }\right)$M(h) (88)

This implies

| h|1 = $\displaystyle \Sigma_{{{0 \leq i \leq m}}}^{{}}$  | hi |
  $\displaystyle \leq$ M(h$\displaystyle \Sigma_{{{0 \leq i \leq m}}}^{{}}$ $\displaystyle \left(\vphantom{ \begin{array}{c} m \\  i \end{array} }\right.$$\displaystyle \begin{array}{c} m \\  i \end{array}$$\displaystyle \left.\vphantom{ \begin{array}{c} m \\  i \end{array} }\right)$
  = M(h) (1 + 1)m
  = M(h) 2m
(89)

Now observe that the measures of h and f satisfy

M(h$\displaystyle \leq$  $\displaystyle \left\vert\vphantom{ \frac{h_m}{f_n} }\right.$$\displaystyle {\frac{{h_m}}{{f_n}}}$$\displaystyle \left.\vphantom{ \frac{h_m}{f_n} }\right\vert$M(f ) (90)

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

| h|2  $\displaystyle \leq$  | h|1  $\displaystyle \leq$  M(h) 2m  $\displaystyle \leq$  $\displaystyle \left\vert\vphantom{ \frac{h_m}{f_n} }\right.$$\displaystyle {\frac{{h_m}}{{f_n}}}$$\displaystyle \left.\vphantom{ \frac{h_m}{f_n} }\right\vert$M(f ) 2m  $\displaystyle \leq$  $\displaystyle \left\vert\vphantom{ \frac{h_m}{f_n} }\right.$$\displaystyle {\frac{{h_m}}{{f_n}}}$$\displaystyle \left.\vphantom{ \frac{h_m}{f_n} }\right\vert$| f|2 2m (91)

The theorem is proved. $ \qedsymbol$

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

| g|$\scriptstyle \infty$ | h|$\scriptstyle \infty$  $\displaystyle \leq$  | g|2 | h|2  $\displaystyle \leq$  | g|1 | h|1  $\displaystyle \leq$  2m+k | f|2  $\displaystyle \leq$  (n + 1)1/2 2m+k | f|$\scriptstyle \infty$ (92)

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

| g|1 | h|1  $\displaystyle \leq$  2m+k | f|2. (93)

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

| g|1  $\displaystyle \leq$  2m M(g)    and    | h|1  $\displaystyle \leq$  2k M(h). (94)

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

M(gM(h$\displaystyle \leq$  M(f ). (95)

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

M(f$\displaystyle \leq$  | f|2. (96)

Putting all these relations together leads to

| g|1 | h|1  $\displaystyle \leq$  2m+k M(gM(h$\displaystyle \leq$  2m+k M(f$\displaystyle \leq$  2m+k | f|2. (97)

The corollary is proved. $ \qedsymbol$

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|$\scriptstyle \infty$  $\displaystyle \leq$  (n + 1)1/2 2n | f|$\scriptstyle \infty$ (98)


next up previous
Next: Modular Gcd Algorithms in [x] Up: Advanced Computer Algebra: The resultant Previous: Lucky and unlucky modular reductions
Marc Moreno Maza
2004-04-27