1.1 A brief introduction to computational algebraic geometry  (Page 10/20)

The division algorithm

We would like to generalize the division algorithm to polynomials in several variables. In the single variable case, it suffices to be able to divide by a single polynomial

with $degr\left(x\right)<degf\left(x\right)$ , in the sense that even if we want to determine, given $g\left(x\right),f_1\left(x\right),f_2\left(x\right)$ , whether it's possible to write

we can use Euclid's algorithm to find the gcd $f\left(x\right)$ of $f_1\left(x\right)$ and $f_2\left(x\right)$ and write it as $f\left(x\right)=a_1\left(x\right)f_1\left(x\right)+a_2\left(x\right)f_2\left(x\right)$ , and then simply divide $g\left(x\right)$ by $f\left(x\right)$ .

Another way of saying this is that every ideal $⟨f_1\left(x\right),...,f_k\left(x\right)⟩\subseteq \mathbf{R}\left[x\right]$ is in fact generated by a single element $⟨f_1\left(x\right),...,f_k\left(x\right)⟩=⟨f\left(x\right)⟩$ , and both computing this element (using Euclid's algorithm) and testing whether $g\left(x\right)$ is divisible by it can be carried out by dividing by single polynomials.

The situation is much more complicated when dealing with polynomials in several variables. For example, the ideal $⟨x,y⟩\subset \mathbf{R}[x,y]$ can not be generated by a single element, and while $x$ and $y$ have no common factors, it is not possible to write $1=q_1(x,y)x+q_2(x,y)y$ . As such, we won't be able to limit ourselves to dividing by a single polynomial.

Another condition that we'll have to change in the multivariable case is our requirement that $degr\left(x\right)<degf\left(x\right)$ . For example, if we tried to write

it seems like whatever choices of $q_1$ and $q_2$ we make we'll always be stuck with a $z^3$ term in the remainder, which has a larger degree than the polynomials $x$ and $y$ that we're dividing by.

The division algorithm in several variables

We now describe what we can do over $\mathbf{R}[x_1,...,x_n]$ by essentially just following the usual division algorithm for single variable polynomials. Since the single variable division algorithm involves the leading terms of various polynomials, we fix a monomial order on $\mathbf{R}[x_1,...,x_n]$ and use it to define $LT\left(f\right)$ to be the leading term of a polynomial $f$ according to that monomial order.

Now suppose we are given a polynomial $g$ that we are trying to divide by polynomials $f_1,...,f_k\in \mathbf{R}[x_1,...,x_n]$ to write

If $LT\left(g\right)$ is divisible by $LT\left(f_i\right)$ , then we can add $\frac{LT\left(g\right)}{LT\left(f_i\right)}$ to $q_i$ and subtract $\frac{LT\left(g\right)}{LT\left(f_i\right)}{f}_i$ from $g$ to cancel out the leading term of $g$ , leaving it with aa smaller leading term. In this way, we eventually arrive at a polynomial whose leading term is not divisible by any of the $LT\left(f_i\right)$ , and so we must move that leading term to the remainder. We continue in this way: we either cancel out $LT\left(g\right)$ if it is divisible by some $LT\left(f_i\right)$ or we just move it to the remainder if it isn't. Since the leading term decreases at each step, this process must terminate eventually with no terms left of $g$ , and at that point every term of the remainder we're left with will not be divisible by any of the $LT\left(f_i\right)$ .

Theorem (Division algorithm in $\mathbf{R}[x_1,...,x_n]$ ) Fix a monomial order. Let $f_1,...,f_k\in \mathbf{R}[x_1,...,x_n]$ be given. Then every $g\in \mathbf{R}[x_1,...,x_n]$ can be expressed as

with $q_1,...,q_k,r\in \mathbf{R}[x_1,...,x_n]$ and either $r=0$ or every term of $r$ is not divisible by the leading term of any of the $f_i$ . Also, the leading monomial of each $q_i{f}_i$ is no greater than that of $f$ .