Mignotte's factor bound

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

$$\left(\vphantom{ {\Sigma}_{0 \leq i \leq n} \ \vert f_i \vert^2 }\right. \Sigma_{{{0 \leq i \leq n}}}^{{}} \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}}}^{{}}$ f_ixⁱ we shall compute a bound B such that for any h $\in$ $\mbox{${\mathbb C}$}$[x] we have

$$\Rightarrow \leq$$ (73)

One could hope that B = | f|₂ 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ⁿ - 1 and satisfying | h|₂ > B. See [vzGG99] for more details.

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

$$\overline{{z}}$$ (74)

Proof. Let f = $\Sigma_{{{0 \leq i \leq n}}}^{{}}$ f_ixⁱ and define f_-1 = f_n+1 = 0. We calculate

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

(75)

$\qedsymbol$

Definition 7   Let z₁,..., z_n be the complex roots of the polynomial

$$\Sigma_{{{0 \leq i \leq n}}}^{{}} \Pi_{{{1 \leq i \leq n}}}^{{}}$$ (76)

We define the measure of the polynomial f by

$$\Pi_{{{1 \leq i \leq n}}}^{{}}$$ (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(f ) M(g).

The following theorem of Landau (1905) relates M(f ) and | f|₂.

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

$$\leq$$ (78)

Proof. We arrange the roots z₁,..., z_n of f such that

$$\leq$$ (79)

Therefore

M(f )  =   | f_n ^. z₁ ^... z_k | (80)

Let

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

(81)

We calculate

M(f )2	=	| fn . z1 ... zk$$\mid^{{2}}_{{}}$$
	=	| fn . $$\overline{{z_1}}$$ ... $$\overline{{z_k}}$$$$\mid^{{2}}_{{}}$$
	=	| gn$$\mid^{{2}}_{{}}$$
	$$\leq$$	| g|22
	=	|$${\frac{{g}}{{\overline{z_1} x - 1}}}$$(x-z1)|22
	=	...
	=	|$${\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}}}^{{}}$ f_ixⁱ it is convenient to use the 1-norm

$$\Sigma_{{{0 \leq i \leq n}}}^{{}}$$ (83)

and the $\infty$-norm

$$\infty \max_{{{0 \leq i \leq n}}}^{{}}$$ (84)

The following inequalities are classical.

$$\infty \leq \leq \leq \infty \leq \infty$$ (85)

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

$$\leq \leq \leq \left\vert\vphantom{ \frac{h_m}{f_n} }\right. {\frac{{h_m}}{{f_n}}} \left.\vphantom{ \frac{h_m}{f_n} }\right\vert$$ (86)

Proof. Let us write

$$\Pi_{{{1 \leq i \leq m}}}^{{}}$$ (87)

where u₁,..., 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(\vphantom{ \begin{array}{c} m \\ i \end{array} }\right.$$\begin{array}{c} m \\ i \end{array}$$\left.\vphantom{ \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 ^... m we have

$$\leq \left(\vphantom{ \begin{array}{c} m \\ i \end{array} }\right. \begin{array}{c} m \\ i \end{array} \left.\vphantom{ \begin{array}{c} m \\ i \end{array} }\right)$$ (88)

This implies

| h|1	=	$$\Sigma_{{{0 \leq i \leq m}}}^{{}}$$  | hi |
	$$\leq$$	M(h) $$\Sigma_{{{0 \leq i \leq m}}}^{{}}$$ $$\left(\vphantom{ \begin{array}{c} m \\ i \end{array} }\right.$$$$\begin{array}{c} m \\ i \end{array}$$$$\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

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

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

$$\leq \leq \leq \left\vert\vphantom{ \frac{h_m}{f_n} }\right. {\frac{{h_m}}{{f_n}}} \left.\vphantom{ \frac{h_m}{f_n} }\right\vert \leq \left\vert\vphantom{ \frac{h_m}{f_n} }\right. {\frac{{h_m}}{{f_n}}} \left.\vphantom{ \frac{h_m}{f_n} }\right\vert$$ (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

$$\infty \infty \leq \leq \leq \leq \infty$$ (92)

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

$$\leq$$ (93)

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

$$\leq \leq$$ (94)

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

$$\leq$$ (95)

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

$$\leq$$ (96)

Putting all these relations together leads to

$$\leq \leq \leq$$ (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.

$$\infty \leq \infty$$ (98)