Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: Issue with letterplace rings with weighted orderings
PostPosted: Thu Jan 16, 2020 12:04 am 
Hi everyone,

when trying to compute Gröbner bases of ideals in letterplace rings with weighted orderings, the computation always fails with an error:

Code:
LIB "freegb.lib";
ring r = 0,(x,y,z),wp(1,2,3);
def R = freeAlgebra(r, 22);
setring R;
ideal I = x*y+z-y*x, x*y*z-x^6+y^3;
ideal J = twostd(I);
//   ? degree bound of Letterplace ring is 22, but at least 23 is needed for this multiplication


As far as I understand, the computation should not go beyond the degree bound here, but return the result up to the degree bound instead. Any help in resolving this problem would be appreciated.

This came up in Sage trac #25993. Sage wraps an older version of Singular's letterplace functionality which does not exist anymore in the current version of Singular, and I have difficulties making the above example work with the current version of Singular.

Thank you,
Markus


Report this post
Top
  
Reply with quote  
 Post subject: Re: Issue with letterplace rings with weighted orderings
PostPosted: Fri Jan 17, 2020 5:57 pm 

Joined: Thu Aug 11, 2005 8:03 pm
Posts: 40
Location: RWTH Aachen, Germany
Hello Markus,

we have massively rewritten and refactor the new Letterplace in recent years. I doubt, that the ordering you use was properly supported in older versions. The behavior as above, i.e. saying "degree bound is ..., but at least ... is needed" appears only with monomal orderings, which are not compatible with the length of the words (like usual degree left/right lex).
My recommendations:
1) Have a close look at https://www.singular.uni-kl.de/Manual/l ... ng_801.htm for the exact description of the supported orderings.
We use Singular classical lp, dp etc names only as placeholders,
they encode the specific orderings as described in the manual.
No other system except us can do non-length-compatible orderings properly, so the message (and the behavior) as above is a part of the price to pay.
2) keep activated
Code:
option(redTail);

3) have a look at how the polynomials in your input are ordered (Singular automatically orders them according to the monomial ordering) - with your ordering the polynomials look as
Code:
I[1]=z-y*x+x*y
I[2]=y*y*y+x*y*z-x*x*x*x*x*x

so any operation on y's in the second will increase the degree of the trailing x's and nothing can be done here.
4) Instead, try other ordering and also other order of variables in addition:
Code:
...
ring r = 0,(x,y,z),(a(1,2,3),dp);
...
I;
>I[1]=-y*x+x*y+z
>I[2]=-x*x*x*x*x*x+y*y*y+x*y*z
twostd(I); //gives 40 elements

Also,
Code:
...
r = 0,(z,y,x),(a(3,2,1),dp);
...

resulted in the finite answer.

All the best,
Viktor Levandovskyy

mwageringel wrote:
Hi everyone,

when trying to compute Gröbner bases of ideals in letterplace rings with weighted orderings, the computation always fails with an error:

Code:
LIB "freegb.lib";
ring r = 0,(x,y,z),wp(1,2,3);
def R = freeAlgebra(r, 22);
setring R;
ideal I = x*y+z-y*x, x*y*z-x^6+y^3;
ideal J = twostd(I);
//   ? degree bound of Letterplace ring is 22, but at least 23 is needed for this multiplication


As far as I understand, the computation should not go beyond the degree bound here, but return the result up to the degree bound instead. Any help in resolving this problem would be appreciated.

This came up in Sage trac #25993. Sage wraps an older version of Singular's letterplace functionality which does not exist anymore in the current version of Singular, and I have difficulties making the above example work with the current version of Singular.

Thank you,
Markus


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Issue with letterplace rings with weighted orderings
PostPosted: Sun Jan 19, 2020 6:52 pm 
Dear Viktor,

thanks a lot for the detailed response. This is very helpful.

Regarding the ordering wp(1,2,3), Sage did not call the Letterplace library with this ordering directly, but instead used the concept of a slack variable s to encode y and z as y*s and z*s*s. It then called the library with the ordering (dp(3),lp(1)) on the variables (x,y,z,s). With the current version of Singular, such a block ordering is not allowed anymore and I wrongly assumed the wp(1,2,3) ordering was a suitable replacement, as I had missed the documentation page you linked. Quite possibly, the ordering (dp(3),lp(1)) did not actually get respected with previous versions of the Letterplace API.

Using the current version of Singular, I have now tried several different supported orderings for the example above. Apparently, one obtains the best results using the slack variable approach and a Dp ordering.
Code:
LIB "freegb.lib";
ring r = 0,(x,y,z,s),Dp;
def R = freeAlgebra(r, 22);
setring R;
ideal I = x*y*s - y*s*x + z*s*s, -x*x*x*x*x*x + x*y*s*z*s*s + y*s*y*s*y*s;
ideal J = twostd(I);

The result J is generated by only 5 elements of degree up to 11. Since the degree bound of 22 is twice as large, Sage concludes that this is the Gröbner basis for any degree bound ≥ 11. (Please correct me if this is wrong.)

This result is close to what previous versions would compute, so this will allow Sage to upgrade to the new version of Singular and the Letterplace library. Thanks again for the kind help.

Best,
Markus Wageringel


Report this post
Top
  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

It is currently Fri May 13, 2022 10:55 am
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group