Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.
share|improve this question
1  
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. –  Matthew Towers May 28 '13 at 14:57

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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$.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.