# Ideal Membership without Certificate?

I have a homogeneous ideal $I=\langle f_1,\ldots,f_r\rangle$ of the polynomial ring $\mathbb C[X_1,\ldots,X_n]=:R$ where each of the $f_i$ is actually over $\mathbb Z$. My computations are usually performed over $\mathbb Q$. As an additional note, the $f_i$ are all homogeneous of the same degree. I also have a monomial $\mu = X^\alpha$, where $\alpha\in\mathbb N^n$ is some multi-index. I don't know if it matters that $\mu$ is a monomial.

Several computer algebra systems (magma, sage, macaulay2) can tell me that $\mu\in I$, but only in SAGE I could find a method to compute $g_1,\ldots,g_r\in R$ with $\sum_{i=1}^r g_i f_i = \mu$. Unfortunately, this method seems to crash the SAGE kernel, because after a couple of minutes the execution simply stops with no result, and SAGE has forgotten everything from the session. I have two questions:

1. How do Computer Algebra systems check ideal membership without actually creating a certificate? In other words, how do they know $\mu\in I$ without having the $g_i$ that prove it?
2. I would really like to know those $g_i$. Given that SAGE just flat-out crashes on me, do you know any other options I could try? There might be routines in other computer algebra systems that I am simply unaware of and which I could try.
-
It seems that Sage calls Singular singular.uni-kl.de to do this computation. Have you tried it in Singular directly? Even if it still crashes it may produce a more helpful error message. – M T May 28 '13 at 14:57

This should really be a comment. But since I dont't have enough reputation I have to write it here.

If you only want to check ideal membership you "just" have to compute a gröbner basis and check if all S-polynomials reduce to $0$. (the above mentioned computer algebra systems check ideal member ship in this way)

If you want to compute the $g_i$ you need to compute the syzygys. (I think this is just bookkeeping during the gröbner basis computation)

Edit: I think the CAS Singular is able to compute the $g_i$ using the command "lift". http://www.singular.uni-kl.de/Manual/latest/sing_331.htm#SEC371

-
I disagree, this is a perfectly reasonable answer. Also @mt, trying the lift command in singular on my own machine rather than the SAGE online interface actually produced a result, so all my questions are answered and my problem is solved. – Jesko Hüttenhain May 28 '13 at 22:05

My recollection of the Gröbner engine of Macaulay 2 is that it's rather black-boxed. Surely others here know better than I how to access its parts directly.

The first step is to extend to a Gröbner basis $G$. But without reimplementing the Buchberger algorithm I don't know how to express the new generators in terms of the old.

Then, you can $\rm scan()$ through ${\rm flatten\ entries\ generators}\ G$, replacing p by p%G, and if they're different print out (G, (p-p%G)/G). Continue cycling through until $p=0$.

-
To express the new generators in terms of the old: when computing the Gröbner basis, use the ChangeMatrix => true option. Then, once you've computed a Gröbner basis b, call getChangeMatrix(b) to get the matrix of coefficients to express the new generators in terms of the old. – Charles Staats May 28 '13 at 17:22