Coefficients growth in the Euclidean Algorithm over [x]

We saw in the first chapter that running the Euclidean Algorithm in $\mbox{${\mathbb Q}$}$ [x] can lead to a significant expression swell. Let us try to estimate how coefficients grow. That is, we want to estimate the maximal space needed to store one coefficient of an intermediate polynomial. Let N be the number of bits of a machine word.

Definition 1 For an integer a $\in$ $\mbox{${\mathbb Z}$}$ we define $\lambda$ (a) the length of a as the minimum number of words to encode a. Hence for a $\neq$ 0 we have

$\displaystyle \lambda$ (a) = $\displaystyle \lfloor$ log₂(a)/N $\displaystyle \rfloor$ + 1 and $\displaystyle \lambda$ (0) = 0

(1)

For a rational number a = b/c with b, c $\in$ $\mbox{${\mathbb Z}$}$ and gcd(c, d )= 1 we define $\lambda$ (a), the length of a, as the maximum among $\lambda$ (b) and $\lambda$ (c).

Definition 2 For a polynomial a $\in$ $\mbox{${\mathbb Q}$}$ [x] of degree n $\geq$ 0 such that all coefficients have denominator b and such that the numerators a_n, a_n-1,..., a₁, a₀ have gcd 1 then we define the length of a as

$\displaystyle \lambda$ (a) = max( $\displaystyle \lambda$ (b), $\displaystyle \max_{{{0 \leq i \leq n}}}^{{}}$ ( $\displaystyle \lambda$ (a_i)))

(2)

Remark 1 A polynomial a $\in$ $\mbox{${\mathbb Q}$}$ [x] of degree n $\geq$ 0 can be represented with

$\displaystyle \lambda$ (a) $\displaystyle \left(\vphantom{ 2 + {\deg}(a) }\right.$ 2 + deg(a) $\displaystyle \left.\vphantom{ 2 + {\deg}(a) }\right)$

(3)

words.

Proposition 2 Let a, b be univariate polynomials over $\mbox{${\mathbb Z}$}$ in x. We assume that a and b are monic and that deg(a) = deg(b) + 1 holds. Let q and r be the quotient and the remainder of a w.r.t. b. Then we have

$\displaystyle \lambda$ (r) $\displaystyle \leq$ $\displaystyle \lambda$ (a) + 2 $\displaystyle \lambda$ (b) + 3

(4)

Proof. We define

a = xⁿ + a_n-1x^n-1 + ^... + a₀ and b = x^n-1 + b_n-2x^n-2 + ^... + b₀

(5)

It is not hard to see that

q = x + a_n-1 - b_n-2

(6)

Then

$\displaystyle \lambda$ (q) $\displaystyle \leq$ max( $\displaystyle \lambda$ (a), $\displaystyle \lambda$ (b)) + 1

(7)

Thus

$\displaystyle \lambda$ (bq) $\displaystyle \leq$ max( $\displaystyle \lambda$ (a), $\displaystyle \lambda$ (b)) + 1 + $\displaystyle \lambda$ (b) + $\displaystyle \lambda$ (deg(q) + 1)

(8)

Recall that

r = a - bq

(9)

Since $\lambda$ (bq) $\geq$ $\lambda$ (a) we obtain

$\displaystyle \lambda$ (r)	$\displaystyle \leq$	max( $\displaystyle \lambda$ (a), $\displaystyle \lambda$ (b)) + 1 + $\displaystyle \lambda$ (b) + $\displaystyle \lambda$ (deg(q) + 1) + 1
	$\displaystyle \leq$	$\displaystyle \lambda$ (a) + 2 $\displaystyle \lambda$ (b) + 3

(10)

Indeed max( $\lambda$ (a), $\lambda$ (b)) $\leq$ $\lambda$ (a) + $\lambda$ (b) and $\lambda$ (deg(q) + 1) = $\lambda$ (2) $\leq$ 1. $\qedsymbol$

Remark 2 A similar result as Proposition 2 holds for monic polynomials a, b $\in$ $\mbox{${\mathbb Q}$}$ [x] such that deg(a) = deg(b) + 1. See [vzGG99]. These results provide us with an exponential upper bound for the coefficient of the gcd computed by the Euclidean Algorithm. But in fact a polynomial bound can be established. Moreover there is an efficient modular approach for computing gcds in $\mbox{${\mathbb Q}$}$ [x] and $\mbox{${\mathbb Z}$}$ [x] as we shall see in the next sections.