Macaulay2: How to compute the remainder when dividing a polynomial by a set of polynomials (in some order)?

Question

I'm writing Buchberger's Criterion in a program in Macaulay2 to check whether or not the set of polynomials I have form a Grobner basis for the ideal it generates. However, I have not been able to find a method that gives me the remainder when a polynomial, say $f$, is divided by a set of polynomials $G=\{g_1, g_2, ..., g_t\}$ in some order. Would anyone know if such a method exists and, if yes, what is its name?

Although that's not all I have, here is the part of the program where I try to implement the Buchberger's Criterion:

n=0;
for i to #polynomials-2 do
    (
        for j from i+1 to #polynomials-1 do 
    (
Spoly := lcm(leadTerm(polynomials#i),leadTerm(polynomials#j))/leadTerm(polynomials#i)*polynomials#i-lcm(leadTerm(polynomials#i),leadTerm(polynomials#j))/leadTerm(polynomials#j)*polynomials#j;
remainder := Spoly%polynomials;
if remainder == 0 then n=n+1;
  );
    );
    if n == binomial(#polynomials, 2) then print "The polynomials form a Grobner basis for the ideal it generates." else print "The polynomials don't form a Grobner basis for the ideal it generates."

On the codes above, I use % as the method I'm looking for - but it doesn't work for a polynomial being divided by a list of polynomials.

Answer 1

If you are given f and g two polynomials the remainder is given by f % g. suppose now you are given with G ideal and G=(g1,g2,...,gn). then the remainder when f is divided by G should be f % G. Hope this helps.

Answer 2

It seems this is not built in (at least, not exposed to users), but it is easy enough to achieve:

Given a monomial ordering, dividing a polynomial $f$ by an ordered list of polynomials $f_1,\ldots,f_s$ means to express $$f = q_1f_1 + \ldots + q_sf_s + r,$$ where either $r=0$ or none of the monomials in $r$ are divisible by any of $LT(f_1), \ldots, LT(f_s)$.

Algorithm. To begin, set $q_1:= 0, \ldots, q_s :=0$ and $r := 0$, and introduce $p := f$.

While $p \neq 0$, we remove $LT(p)$ (and possibly more) from $p$ as follows:

• Try to find the smallest index $i$ such that $LT(f_i)$ divides $LT(p)$.

  • If $i$ is found (division step): set $q_i := q_i + LT(p)/LT(f_i)$ and $p := p - (LT(p)/LT(f_i))f_i$.
  • If no such $i$ exists (remainder step), then set $r := r + LT(p)$ and $p := p - LT(p)$.

Finally, return $(q_1,\ldots,q_s)$ and $r$.

See Ideals, Varieties, and Algorithms 4th ed. by Cox, Little and O'Shea, Chapter 2, $\S$3, Theorem 3, pp. 64 – 66. They give more imperative pseudo-code which should be easy to translate into Macaulay2. It is a nice programming exercise.