Mignotte's factor bound

Definition 6   Let $f = {\Sigma}_{0 \leq i \leq n} \ f_i x^i$ be a univariate polynomial over ${\mbox{${\mathbb{C}}$}}$ . The 2-norm of $f$ is defined by

$${\Vert f \Vert}_2 \ = \ \left( {\Sigma}_{0 \leq i \leq n} \ \vert f_i \vert^2 \right)^{1/2}$$ (72)

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

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

$$h \ \mid \ f \ \ \ \ \Rightarrow \ \ \ \ {\Vert h \Vert}_2 \ \leq \ B$$ (73)

One could hope that $B = {\Vert f \Vert}_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 $x^n - 1$ and satisfying ${\Vert h \Vert}_2 > B$ . See [GG99] for more details.

Lemma 3   For $f \in {\mbox{${\mathbb{C}}$}}[x]$ and $z \in {\mbox{${\mathbb{C}}$}}$ we have

$${\Vert (x -z) f \Vert}_2 \ = \ { \Vert (\overline{z} \, x -1) f \Vert}_2$$ (74)

Proof. Let $f = {\Sigma}_{0 \leq i \leq n} \ f_i x^i$ and define $f_{-1} = f_{n+1} = 0$ . We calculate

$$\begin{array}{rcl} {\Vert (x -z) f \Vert}_2^2 & = & {\Sigma}_... ... & = & { \Vert (\overline{z} \, x -1) f \Vert}_2 \\ \end{array}$$ (75)

$\qedsymbol$

Definition 7   Let $z_1, \ldots, z_n$ be the complex roots of the polynomial

$$f \ = \ {\Sigma}_{0 \leq i \leq n} \ f_i x^i \ = \ f_n \ {\Pi}_{1 \leq i \leq n} \ (x - z_i)$$ (76)

We define the measure of the polynomial $f$ by

$$M(f) \ = \ \mid f_n \mid \ {\Pi}_{1 \leq i \leq n} \ {\max}(1,\mid z_i \mid)$$ (77)

Remark 10   For $f,g \in {\mbox{${\mathbb{C}}$}}[x]$ the following statements are easy to prove:

1. $M(f) \ \geq \ {\rm lc}(f)$ .
2. $M(f g) \ = \ M(f) \, M(g)$ .

The following theorem of Landau (1905) relates $M(f)$ and ${\Vert f \Vert}_2$ .

Theorem 4 (Landau)   For any $f \in {\mbox{${\mathbb{C}}$}}[x]$ we have

$$M(f) \ \leq \ {\Vert f \Vert}_2$$ (78)

Proof. We arrange the roots $z_1, \ldots, z_n$ of $f$ such that

$$\mid z_1 \mid, \ldots, \mid z_k \mid \ > \ 1 \ \ \ \ {\rm and} \ \ \ \ \mid z_{k+1} \mid, \ldots, \mid z_n \mid \ \leq \ 1$$ (79)

Therefore

$$M(f) \ = \ \mid f_n \cdot z_1 \cdots z_k \mid$$ (80)

Let

$$\begin{array}{rcl} g & = & f_n \ {\Pi}_{1 \leq j \leq k} (\ov... ...j \leq n} (x - z_j) \\ & = & g_n x^n + \cdots + g_0 \end{array}$$ (81)

We calculate

$$\begin{array}{rcl} {M(f)}^2 & = & { \mid f_n \cdot z_1 \cdots... ... - z_k) \Vert }_2^2 \\ & = & {\Vert f \Vert}_2^2 \\ \end{array}$$ (82)

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

Remark 11   Given $f = {\Sigma}_{0 \leq i \leq n} \ f_i x^i$ it is convenient to use the $1$ -norm

$${\Vert f \Vert}_1 \ = \ {\Sigma}_{0 \leq i \leq n} \ \mid f_i \mid$$ (83)

and the $\infty$ -norm

$${\Vert f \Vert}_{\infty} \ = \ {\max}_{\ 0 \leq i \leq n}(\mid f_i \mid)$$ (84)

The following inequalities are classical.

$${\Vert f \Vert}_{\infty} \ \leq \ {\Vert f \Vert}_2 \ \leq \ {\Ve... ...and} \ \ \ \ {\Vert f \Vert}_2 \ \leq \ (n+1)^{1/2} \, {\Vert f \Vert}_{\infty}$$ (85)

Theorem 5   Let $f = {\Sigma}_{0 \leq i \leq n} \ f_i x^i$ and $h = {\Sigma}_{0 \leq i \leq m} \ h_i x^i$ be two polynomials such that $h$ divides $f$ . Then we have

$${\Vert h \Vert}_2 \ \leq \ {\Vert h \Vert}_1 \ \leq \ 2^m \, M(h) \ \leq \ \left\vert \frac{h_m}{f_n} \right\vert \, 2^m \, {\Vert f \Vert}_2$$ (86)

Proof. Let us write

$$h \ = \ h_n \ {\Pi}_{1 \leq i \leq m} \ (x - u_i)$$ (87)

where $u_1, \ldots, u_m \in {\mbox{${\mathbb{C}}$}}$ are the roots of $h$ and thus among the roots of $f$ . Observe that the coefficient $h_i$ 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 $\left( \begin{array}{c} m \\ i \end{array} \right)$ 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 \cdots m$ we have

$$\mid h_i \mid \ \leq \ \left( \begin{array}{c} m \\ i \end{array} \right) M(h)$$ (88)

This implies

$$\begin{array}{rcl} {\Vert h \Vert}_1 & = & {\Sigma}_{0 \leq i... ...t) \\ & = & M(h) \ (1 + 1)^m \\ & = & M(h) \ 2^m \\ \end{array}$$ (89)

Now observe that the measures of $h$ and $f$ satisfy

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

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

$${\Vert h \Vert}_2 \ \leq \ {\Vert h \Vert}_1 \ \leq \ M(h) \ 2^m ... ...) \ 2^m \ \leq \ \left\vert \frac{h_m}{f_n} \right\vert {\Vert f \Vert}_2 \ 2^m$$ (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

$${\Vert g \Vert}_{\infty} \, {\Vert h \Vert}_{\infty} \ \leq \ {\V... ...{\Vert f \Vert}_2 \ \leq \ (n + 1)^{1/2} \, 2^{m+k} \, {\Vert f \Vert}_{\infty}$$ (92)

Proof. The first, the second and the fourth above inequalities follow directly from the classical relations between the norms ${ \Vert \ \cdot \ \Vert }_1$ , ${ \Vert \ \cdot \ \Vert }_2$ and ${ \Vert \ \cdot \ \Vert }_{\infty}$ given in Remark 11. So the only inequality to prove is

$${\Vert g \Vert}_1 \, {\Vert h \Vert}_1 \ \leq \ 2^{m+k} \, {\Vert f \Vert}_2 .$$ (93)

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

$${\Vert g \Vert}_1 \ \leq \ 2^m \, M(g) \ \ \ \ {\rm and} \ \ \ \ {\Vert h \Vert}_1 \ \leq \ 2^k \, M(h).$$ (94)

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

$$M(g) \, M(h) \ \leq \ M(f).$$ (95)

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

$$M(f) \ \leq \ {\Vert f \Vert}_2.$$ (96)

Putting all these relations together leads to

$${\Vert g \Vert}_1 \, {\Vert h \Vert}_1 \ \leq \ 2^{m+k} \, M(g) \, M(h) \ \leq \ 2^{m+k} \, M(f) \ \leq \ 2^{m+k} \, {\Vert f \Vert}_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$ .

$${\Vert h \Vert}_{\infty} \ \leq \ (n + 1)^{1/2} \, 2^n \, {\Vert f \Vert}_{\infty}$$ (98)