Chapter 5 Gröbner Basis
If we wish to divide the single-variable polynomial \(f(x) \in \mathbb R[x]\) by another polynomial of smaller order \(g(x)\in\mathbb R[x]\text{,}\) we are looking for two new polynomials, \(q, r\) such that:
\begin{align*}
f(x)\amp = q\cdot g(x) + r,
\end{align*}
where \(q\) is termed the quotient and \(r\) the remainder. To find such a \(q\text{ and } r\text{,}\) we follow a methodology called the division algorithm.
Section 5.1 The Division Algorithm
The division algorithm is comprised of four steps for the above specific \(f(x)\text{ and }g(x)\text{:}\)
-
Divide the leading term of \(f(x),\;\textbf{LT}(f(x))\) by the leading term of \(g(x),\;\textbf{LT}(g(x))\text{.}\) Add this to the quotient \(q\text{.}\)Here, we denote the leading term as the part of the polynomial with highest degree. For example, \(\textbf{LT}(x^2+3x+2)=x^2\text{.}\)
- Multiply the divisor, \(g(x)\text{,}\) by the result from Step 1.
-
Now, repeat the entire process with \(f(x):=f(x) - \frac{\textbf{LT}(f(x))}{\textbf{LT}(g(x))}\cdot g(x)\) until the degree of \(f(x)\) is less than the degree of \(g(x)\text{.}\)The final \(f(x)\) is our remainder, \(r\text{.}\)
This process can be repeated for any polynomial, not only in \(\mathbb R[x]\text{,}\) but for any field \(\mathbb K[x]\text{.}\) However, given two polynomials, \(g(x), k(x)\text{,}\) can we ensure that the order of division does not matter? Is is associative?
We know that this is the case in \(\mathbb R\text{.}\) Consider \(a,b,c\in \mathbb R\text{.}\) We know that:
\begin{align*}
\frac{\frac{a}{b}}{c} \amp = \frac{\frac{a}c}b.
\end{align*}
This same property also holds also in \(\mathbb K[x]\text{.}\) However, this property only holds in the single-variable case. For \(\mathbb K[x,y]\text{.}\) Consider \(f(x)=xy + 1,\) \(g(x)=xy,\) and \(k(x)=y+1\text{.}\) Via the division algorithm, we get that:
\begin{align*}
\frac{\frac{f(x)}{g(x)}}{k(x)} \amp = 1 \cdot g(x) + 1 \\
\frac{\frac{f(x)}{k(x)}}{g(x)}\amp = x\cdot k(x) - (x+1)
\end{align*}
With the same algorithm, we got two different remainders that are not divisible by the remaining polynomial. This may lead one to believe that consistent division of multivariable polynomails is simply impossible, but that is far from the case. Mathematicians far more intelligent than the authors of this textbook have devised methods to resolve this mathematical snail crevice.
