Strategy for dividing multivariable polynomials leaving no remainder. Decide whether polynomial $f$ lies in ideal $I=\langle f_1, …, f_n\rangle$.

I'm looking for some general strategy to divide polynomials leaving no remainder after division using the canonical multivariable polynomial division algorithm where we divide some polynomial $f$ by a set of polynomials $(f_1,...,f_n)$ using some term ordering.

I've already done some exercises using brute force method and it can really take ages to compute a polynomial division leaving no remainder when the term ordering is free of choose.

In the following exercise I've already verified that I have a remainder when term ordering is $\le: X>Y$ - so clearly $(X^2+Y, X^2Y+1)$ is not a Gröbner basis for $I$.

Decide whether $f = X^3Y + X^3 + X^2Y^3-X^2Y+XY+X$ lies in the ideal $I=\langle X^2 + Y, X^2Y+1\rangle$. If so find $a_1, a_2 \in k[X,Y]$ such that $f = a_1f_1+a_2f_2$.

How could I do this exercise fast instead of wasting time doing division attempts with the canonical multivariable polynomial division algorithm that I've already studied and mastered several times.

• Do you want to compute a Gröbner basis without computing a Gröbner basis, or what? – Marc van Leeuwen Dec 10 '13 at 14:33
• See example 5.7.1 to see what a Grobner basis for that ideal is. – Tobias Kildetoft Dec 12 '13 at 11:33

Since the generators in your ideal are just binomials, you can do some quick'n'dirty replace operations. Start with the second because of its higher degree and replace all $X^2Y$ by $-1$

$-X+X^3-Y^2+1+XY+X$

Then replace using the first binomial $X^2$ by $-Y$

$-X-XY-Y^2+1+XY+X$

and simplify

$-Y^2+1$

This one now is tricky because it requires a degree increasing replacement, use one $Y$ to give $-X^2$,

$X^2Y+1$

which is just the first generator of the ideal. With a little book-keeping during the replace operations you can also obtain the coefficients.

Added: Since there was doubt, lets make the replacements exact. Name the generators $g_1=X^2+Y$ and $g_2=X^2Y+1$, so $g_2-g_1Y=1-Y^2$

\begin{aligned} f&=X^3Y+X^3+X^2Y^3−X^2Y+XY+X\\ &=X^2Y(X+Y^2-1)+X^2\cdot X+XY+X\\ &=(g_2-1)(X+Y^2-1)+(g_1-Y)X+XY+X\\ &=g_2(X+Y^2-1)-Y^2+1+g_1X\\ &=g_2(X+Y^2-1)+g_1X+g_2-g_1Y\\ &=g_1(X-Y)+g_2(X+Y^2) \end{aligned}

Remark: As I said above, this works only well because the generators are binomials telling us that $Y=-X^2$ and $X^4=1$. So one could also simplify $f(X,-X^2)$ by reducing all powers of $X$ by multiples of 4 in the exponent.

With more terms in the generators, the replacement strategy leads to a rapid increase in the number of terms in the expression. There you really need Gröbner bases or related tools.

• There is an error somewhere in these calculations, as the given polynomial is not in fact in the ideal. – Tobias Kildetoft Dec 12 '13 at 11:45
• Nope, everything checks out. The steps are simple enough. – LutzL Dec 12 '13 at 12:40
• Thank you. I had made an error in my division algorithm, working with the Grobner basis (and one of the other TAs had done the same, so we agreed that the polynomial should not be in the ideal). Glad I got this sorted. – Tobias Kildetoft Dec 13 '13 at 8:10

Use a computer algebra system such as Maple (commercial) or Singular (free).

• There is no smart way of doing it by hand, I guess then ? – Shuzheng Dec 10 '13 at 14:23
• I don't think so. Also using a CAS makes it fun. You can play choosing different monomia orderings, or choose different algorithms, etc... As far as I know fast algorithms to compute Groebner basis are not suitable to be done by hand, for example F4 algorithm uses linear algebra, sparse matrix results. – Sergio Parreiras Dec 10 '13 at 14:34
• You may want to read the section of Cox et al. book on using algebraic geometry that talks about using eigenvalues to solve polynomial eq but again you really don't want to compute eigenvalues by hand... – Sergio Parreiras Dec 10 '13 at 14:37
• Finally, since you system is small you could use the other algorithms in Cox et al by hand even if it is not faster you learn new stuff. Also I forgot that you may try to use resultants instead (also in Cox et al. book and any CAS) – Sergio Parreiras Dec 10 '13 at 14:43

I don't understand the problem with doing it by hand. Similar to the way one performs long division, write down the dividend with the terms in order, leave space between the terms for new terms which may be introduced. Cancel terms left to right, writing down new products, e.g. $q_j \cdot f_i$, on a new line.

If that seems faster than collecting like terms for $f - q_j \cdot f_i$ in each step, well, it is. And it's faster to do it this way on a computer too, using a heap to keep track of the next term of $f$ and each $q_j \cdot f_i$.