Lucky and unlucky modular reductions

gcd(f, g) $\displaystyle \in$ R $\displaystyle \iff$ res(f, g) $\displaystyle \neq$ 0

(36)

Example 1 Consider R = $\mbox{${\mathbb Z}$}$ , p = 2, f = x + 2 and g = x. Then we have

res(f, g) = - 2 $\displaystyle \equiv$ 0 mod2 and res( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ ) = 0

(37)

as expected. But when f = 4x³ - x and g = 2x + 1 we have

res(f, g) = 0 and res( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ ) = res(x, 1) = 1

(38)

The reason for this unexpected behavior in the last example is that the Sylvester matrix of $\overline{{f}}$ = x and $\overline{{g}}$ = 1 is

$\displaystyle \left(\vphantom{ \begin{array}{c} 1 \end{array} }\right.$ $\displaystyle \begin{array}{c} 1 \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}{c} 1 \end{array} }\right)$

(39)

and thus is not the reduction modulo 2 of the Sylvester matrix of f and g which is

$\displaystyle \left(\vphantom{ \begin{array}{cccc} 4 & 2 & 0 & 0 \\ 0 & 1 & 2 & 0 \\ -1 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 \end{array} }\right.$ $\displaystyle \begin{array}{cccc} 4 & 2 & 0 & 0 \\ 0 & 1 & 2 & 0 \\ -1 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}{cccc} 4 & 2 & 0 & 0 \\ 0 & 1 & 2 & 0 \\ -1 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 \end{array} }\right)$

(40)

In other words the res operation for $\overline{{f}}$ and $\overline{{g}}$ is not the reduction modulo 2 of the res operation for f and g. This is because the res operation depends on the degrees of its input polynomials. Fortunately this nuisance disappears when p does not divide at least one of the leading coefficients.

Lemma 2 Let R be a commutative ring with identity element. Let f, g $\in$ R[x] be nonzero polynomials. Let r be their resultant. Let I be an ideal if R and let denote by a $\longmapsto$ $\overline{{a}}$ the reduction modulo I. Assume that

$\displaystyle \overline{{{\rm lc}(f)}}$ $\displaystyle \neq$ 0

(41)

Then we have

$\displaystyle \overline{{r}}$ = 0 $\displaystyle \iff$ res( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ ) = 0

(42)

Moreover, if R/I is a UFD, then we have

$\displaystyle \overline{{r}}$ = 0 $\displaystyle \iff$ deg(gcd( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ )) > 0

(43)

Proof. Let us write:

f = f_nxⁿ + ^... + f₀ and g = g_mx^m + ^... + g₀

(44)

with f_n $\neq$ 0 and g_m $\neq$ 0. If n = 0 then Sylv(f, g) and Sylv( $\overline{{f}}$ , $\overline{{g}}$ ) are both diagonal with f on the diagonal. Then in that case

$\displaystyle \overline{{r}}$ = $\displaystyle \overline{{f^m}}$ = $\displaystyle \overline{{f}}^{m}_{}$ = res( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ )^m

(45)

If n > 0 we distinguish two cases. If $\overline{{g}}$ = 0 then res( $\overline{{f}}$ , $\overline{{g}}$ ) = 0 (by Definition 4). Moreover each g-column of Sylv(f, g) is zero modulo I such that $\overline{{r}}$ = 0 too. From now on assume $\overline{{g}}$ $\neq$ 0 and let i be the smallest index such that $\overline{{g_{m-i}}}$ $\neq$ 0 holds.

Sylv(f, g) = $\displaystyle \left(\vphantom{ \begin{array}{ccccccccc} f_0 & & & & & g_0 & & &... ...ts & \vdots & & & & \vdots \\ & & & & f_n & & & & g_m \\ \end{array} }\right.$ $\displaystyle \begin{array}{ccccccccc} f_0 & & & & & g_0 & & & \\ \vdots & \dd... ... & & \ddots & \vdots & & & & \vdots \\ & & & & f_n & & & & g_m \\ \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}{ccccccccc} f_0 & & & & & g_0 & & &... ...ts & \vdots & & & & \vdots \\ & & & & f_n & & & & g_m \\ \end{array} }\right)$

(46)

By exchanging the f-zone with the g-zone we have also

res(f, g) = (- 1)^nm $\displaystyle \left\vert\vphantom{ \begin{array}{ccccccccc} g_0 & & & &f_0 & & ... ...ts & & & & \ddots & \vdots \\ & & & g_m & & & & & f_n \\ \end{array} }\right.$ $\displaystyle \begin{array}{ccccccccc} g_0 & & & &f_0 & & & & \\ \vdots & & & ... ... & & \vdots & & & & \ddots & \vdots \\ & & & g_m & & & & & f_n \\ \end{array}$ $\displaystyle \left.\vphantom{ \begin{array}{ccccccccc} g_0 & & & &f_0 & & & & ... ... & & & \ddots & \vdots \\ & & & g_m & & & & & f_n \\ \end{array} }\right\vert$

(47)

Let M be the submatrix obtained from Sylv(g, f ) by deleting the last i rows and the last i columns. Observe that we have

$\displaystyle \overline{{{\rm res}(f,g)}}$ = (- 1)^nm $\displaystyle \overline{{{\det}(M)}}$ $\displaystyle \overline{{{f_n}^i}}$

(48)

Since

$\displaystyle \overline{{{\det}(M)}}$ = det( $\displaystyle \overline{{M}}$ ) = res( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ )

(49)

we obtain

$\displaystyle \overline{{{\rm res}(f,g)}}$ = (- 1)^nm res( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ ) $\displaystyle \overline{{{\rm lc}(f)}}^{{i}}_{{}}$

(50)

This shows that we have

$\displaystyle \overline{{r}}$ = 0 $\displaystyle \iff$ res( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ ) = 0

(51)

and the first claim of the lemma is proved. The second claim follows from Proposition 6. $\qedsymbol$

Theorem 3 Let f, g $\in$ R[x] be nonzero polynomials for an Euclidean Domain R. Let p $\in$ R be a prime. Let

h = gcd(f, g), e = deg(h). and $\displaystyle \alpha$ = lc(h)

(52)

Assume that p does not divide

b = gcd(lc(f ), lc(g))

(53)

Finally let

e^* = deg(gcd( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ )) (54)

Then we have

$\alpha$ divides b
e^* $\geq$ e
e^* = e $\iff$ $\overline{{{\alpha}}}$ gcd( $\overline{{f}}$ , $\overline{{g}}$ ) = $\overline{{h}}$ $\iff$ p $\not\mid$ res(f /h, g/h)

Proof. Since in R[x]

h | f and h | g

(55)

we have in R

lc(h) | lc(f ) and lc(h) | lc(g).

(56)

Therefore

$\displaystyle \alpha$ = lc(h) | gcd(lc(f ), lc(g)) = b

(57)

and the first claim is proved. Consider now the cofactors of f and g in R[x]

u = f /h and v = g/h.

(58)

Then we have

$\displaystyle \overline{{u}}$ $\displaystyle \overline{{h}}$ = $\displaystyle \overline{{f}}$ and $\displaystyle \overline{{v}}$ $\displaystyle \overline{{h}}$ = $\displaystyle \overline{{g}}$

(59)

which shows that

$\displaystyle \overline{{h}}$ | gcd( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ )

(60)

and implies that

deg( $\displaystyle \overline{{h}}$ ) $\displaystyle \leq$ deg(gcd( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ ))

(61)

Since p does not divide b, it cannot not divide $\alpha$ neither. Hence the leading coefficient of $\overline{{h}}$ is $\overline{{{\alpha}}}$ and we have

deg( $\displaystyle \overline{{h}}$ ) = deg(h)

(62)

Therefore

e = deg(h) $\displaystyle \leq$ deg(gcd( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ )) = e^* (63)

and the second claim is proved.

Now consider the case where e = e^*. Since $\overline{{h}}$ divides gcd( $\overline{{f}}$ , $\overline{{g}}$ ) and since gcd( $\overline{{f}}$ , $\overline{{g}}$ ) is monic (as a gcd over the field R/p) there exists a unit $\beta$ such that

$\displaystyle \overline{{h}}$ = $\displaystyle \beta$ gcd( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ )

(64)

Since the leading coefficient of $\overline{{h}}$ is $\overline{{{\alpha}}}$ we have in fact

$\displaystyle \beta$ = $\displaystyle \overline{{{\alpha}}}$

(65)

Therefore we have the following equivalence

e = e^* $\displaystyle \iff$ $\displaystyle \overline{{h}}$ = $\displaystyle \overline{{{\alpha}}}$ gcd( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ ) (66)

It remains to prove that

$\displaystyle \overline{{{\alpha}}}$ gcd( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ ) = $\displaystyle \overline{{h}}$ $\displaystyle \iff$ p $\displaystyle \not\mid$ res(f /h, g/h)

(67)

Observe that p cannot divide both lc(u) and lc(v). If this was the case then from Relation (59) (and since p does not divide $\alpha$ = lc(h)) p would divide lc(f ) and lc(g), and thus b. A contradiction. Therefore we can assume that p does not divide lc(u). By applying Lemma 2 we obtain

$\displaystyle \overline{{{\rm res}(u,v)}}$ = 0 $\displaystyle \iff$ res( $\displaystyle \overline{{u}}$ , $\displaystyle \overline{{v}}$ ) = 0

(68)

By applying Proposition 5 this leads to

p | res(u, v) $\displaystyle \iff$ gcd( $\displaystyle \overline{{u}}$ , $\displaystyle \overline{{v}}$ ) $\displaystyle \neq$ 1

(69)

From Relation (59) we have

gcd( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ ) = gcd( $\displaystyle \overline{{u}}$ , $\displaystyle \overline{{v}}$ ) $\displaystyle \overline{{h}}$ / $\displaystyle \overline{{{\alpha}}}$

(70)

Therefore

p $\displaystyle \not\mid$ res(u, v) $\displaystyle \iff$ gcd( $\displaystyle \overline{{f}}$ , $\displaystyle \overline{{g}}$ ) = 1 × $\displaystyle \overline{{h}}$ / $\displaystyle \overline{{{\alpha}}}$

(71)

This concludes the proof of the theorem. $\qedsymbol$

Definition 5 Let f, g $\in$ R[x] be nonzero polynomials for an Euclidean domain R. Let h $\in$ R[x] be gcd(f, g). A prime element p $\in$ R is said lucky if p does not divide res(f /h, g/h) otherwise it is said unlucky.

Example 2 Consider f = 12x³ - 28x² + 20x - 4, g = - 12x² + 10x - 2 and p = 17. We have the following computation in AXIOM (where we do not display types)

N := NonNegativeInteger

   (1)  NonNegativeInteger

Z := Integer

   (2)  Integer

U := UnivariatePolynomial(x,Z)

   (3)  UnivariatePolynomial(x,Integer)

f: U := 12*x^3 -28*x^2 +20*x - 4

           3      2
   (4)  12x  - 28x  + 20x - 4

g: U := -12*x^2 +10*x -2

             2
   (5)  - 12x  + 10x - 2

resultant(f,g)

   (6)  0

h: U := gcd(f,g)

   (7)  6x - 2

r: Z := resultant(exquo(f,h),exquo(g,h))

   (8)  2

K17 := PrimeField(17)

   (9)  PrimeField 17

r :: K17
 

   (10)  2

U17 := UnivariatePolynomial(x,K17)

   (11)  UnivariatePolynomial(x,PrimeField 17)

f17: U17 := f :: U17

            3     2
   (12)  12x  + 6x  + 3x + 13

g17: U17 := g :: U17

           2
   (13)  5x  + 10x + 15

h17: U17 := h ::U17

   (14)  6x + 15

c17 := gcd(f17,g17)

   (15)  x + 11

h17 - (leadingCoefficient(h17)) * c17

   (16)  0

Example 3 Consider f = x⁴ - 3x² + 2x, g = x³ - 1 and p = 13. We have the following computation in AXIOM (where we do not display types) The variables N, Z, U are defined as above.

f: U := x^4 -3*x^3 + 2*x 

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

g: U := x^3  -1

         3
   (5)  x  - 1

resultant(f,g)

   (6)  0

h: U := gcd(f,g)

   (7)  x - 1

r: Z := resultant(exquo(f,h),exquo(g,h))

   (8)  9

K3 := PrimeField(3)

   (9)  PrimeField 3

r :: K3

   (10)  0

U3 := UnivariatePolynomial(x,K3)

   (11)  UnivariatePolynomial(x,PrimeField 3)

f3: U3 := f :: U3

          4
   (12)  x  + 2x

g3: U3 := g :: U3

          3
   (13)  x  + 2

h3: U3 := h ::U3

   (14)  x + 2

c3 := gcd(f3,g3)

          3
   (15)  x  + 2

exquo(c3, h3)

          2
   (16)  x  + x + 1