12
$\begingroup$

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.
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – M T
    May 28, 2013 at 14:57

2 Answers 2

7
$\begingroup$

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 syzygies. (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". https://www.singular.uni-kl.de/Manual/4-0-3/sing_513.htm

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ May 28, 2013 at 22:05
2
$\begingroup$

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$.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ May 28, 2013 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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