Coefficients growth in the Euclidean Algorithm over ${\mbox{${\mathbb{Q}}$}}[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

$${\lambda}(a) = \lfloor {\log}_2(a) / N \rfloor + 1 \ \ \ \ {\rm and} \ \ \ \ {\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}, \ldots, a_1, a_0$ have gcd 1 then we define the length of $a$ as

$${\lambda}(a) = {\max}({\lambda}(b), {\max}_{0 \leq i \leq n}({\lambda}(a_i)))$$ (2)

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

$${\lambda}(a) \left( 2 + {\deg}(a) \right)$$ (3)

words.

Proposition 1   Let $a, b$ be univariate polynomials over ${\mbox{${\mathbb{Z}}$}}$ in $x$ . Then we have

1. ${\lambda}(a + b) \ \leq \ {\max}({\lambda}(a), {\lambda}(b)) + 1$ .
2. ${\lambda}(a b) \ \leq \ {\lambda}(a) + {\lambda}(b) + {\lambda}({\min}({\deg}(a), {\deg}(b)) + 1)$ .

Proof. See [GG99]. $\qedsymbol$

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

$${\lambda}(r) \ \leq \ {\lambda}(a) + 2 {\lambda}(b) + 3$$ (4)

Proof. We define

$$a \ = \ x^n + a_{n-1} x^{n-1} + \cdots + a_0 \ \ \ \ {\rm and} \ \ \ \ b \ = \ x^{n-1} + b_{n-2} x^{n-2} + \cdots + b_0$$ (5)

It is not hard to see that

$$q \ = \ x + a_{n-1} - b_{n-2}$$ (6)

Then

$${\lambda}(q) \ \leq \ {\max}({\lambda}(a), {\lambda}(b)) + 1$$ (7)

Thus

$${\lambda}(b q) \ \leq \ {\max}({\lambda}(a), {\lambda}(b)) + 1 + {\lambda}(b) + {\lambda}({\deg}(q) + 1)$$ (8)

Recall that

$$r \ = \ a - b q$$ (9)

Since ${\lambda}(b q) \geq {\lambda}(a)$ we obtain

$$\begin{array}{rcl} {\lambda}(r) & \leq & {\max}({\lambda}(a),... ...) + 1 \\ & \leq & {\lambda}(a) + 2 {\lambda}(b) + 3 \end{array}$$ (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 [GG99]. 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.