Issue with letterplace rings with weighted orderings

mwageringel · 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

Re: Issue with letterplace rings with weighted orderings

levandov · Fri Jan 17, 2020 5:57 pm

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

Re: Issue with letterplace rings with weighted orderings

mwageringel · 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