Normal form and remainder - Groebner Basis

Question

I'm quite confused about the concept of normal form of a polynomial $f$ relative to the ideal $I$. It should be the remainder of the division of $f$ with a Groebner Basis of $I$. But does that mean that no matter which division I compute and no matter which Groebner Basis I choose, I'll have the same remainder? If so, why?

Answer 1

Let $I \subset K[x_1,\ldots,x_n]$ be an ideal, and fix a monomial ordering; let $LM(h)$ denote the leading monomial of $h$.

Theorem: For every $f \in K[x_1,\ldots,x_n]$ there exist unique $g$ and $r$ such that $f = g + r$, where $g \in I$ and either $r=0$ or none of the monomials of $r$ are in $LM(I) = \{LM(h) \mid h \in I\}$.

Here $r = NF(f,I)$ is the normal form of $f$ relative to the ideal $I$. As you can see in the condition on $r$ above, it does depend on the monomial ordering. Existence and uniqueness can be proved without reference to Groebner bases.

Proof. Start with $p=f, g=0, r=0$. While $p \neq 0$, eliminate its leading term by either subtracting suitable $h \in I$ such that $LT(h) = LT(p)$ and adding this $h$ to $g$, or else subtracting $LT(p)$ and adding this to $r$. This process terminates by Dickson's lemma, and at the end $f=g+r$. Uniqueness is easy: if $f=g_1+r_1=g_2+r_2$ then $r_1-r_2=(f-g_1)-(f-g_2) \in I$ and none of its monomials are in $LM(I)$, hence $r_1-r_2=0$.

---

The theorem in this form is not very practical however, because for $I = \langle f_1,\ldots,f_t \rangle$ the set $LM(I)$ can be different from (larger than) $\langle LM(f_1),\ldots,LM(f_t) \rangle$, so the condition on $r$ (or finding $h$) is hard to deal with. A Groebner basis of $I$ is a set of generators $g_1,\ldots,g_s$ of $I$ such that $LM(I) = \langle LM(g_1),\ldots,LM(g_s) \rangle$. Such a Groebner basis provides a very concrete description of $LM(I)$; it makes it easy to find $h$. Multivariate polynomial division of $f$ by any Groebner basis $(g_1,\ldots,g_s)$ then yields a remainder $r$ with the same properties as in the theorem, hence $r = NF(f,I)$ is the normal form (and hence the remainder after multivariate polynomial division by a Groebner basis is unique).

The condition on $r$ then becomes: either $r=0$ or none of the monomials of $r$ are divisible by $LM(g_1),\ldots,LM(g_s)$.