syz over rings is buggy

[levandov]

Hi, there are problems with syzygies over Z modulo integers (with zero divisors)

ring r = (integer, 4), (x,y), lp;
poly f1 = 2*x*y;
poly f2 = 3*y^3+3;
poly f3 = x^2-3*x;
ideal I = f1,f2,f3;
ideal J = std(I); // is correct

but from now on it starts being buggy:

ideal F = f1,f2,f3;
module SF = syz(F);
print(SF);
>1,3,3y3+y2+1,
>0,0,x,       
>0,1,2y4+2y

where the first generator must be the transposed of (2,0,0) . The rest is incorrect as well, as we can see from the usual test (which should produce zero vector)

print(transpose(matrix(SF))*transpose(matrix(F)));
>2xy,             
>x2+2xy+x,        
>2x2y4+2x2y+xy3+3x

so, syzygy generators are all wrong.

It seems that the correct syzygy module is this one:

module S = [2*y^2,0,0],[y^5-y^2,-2*x*y^3,0],[x*y^2-y^2,-2*x^2+2*x,-2],[0,x^2-3*x, y^3+1], [1-y^3,2*x*y,0];
S = std(S);
print(S);
>2,x+2y3+1,3y3+1,0,   
>0,0,      2xy,  x2+x,
>0,2y,     0,    y3+1
print(transpose(matrix(S))*transpose(matrix(F)));
> 0....0

It sound like in the syzygy algorithm it will be normalized. MOREOVER, by simulating syzygy computations via std for modules, there are incorrect issues as well:

ring r = (integer, 4), (x,y), (c,lp); // elim.mod.comp ordering
poly f1 = 2*x*y;
poly f2 = 3*y^3+3;
poly f3 = x^2-3*x;
ideal I = f1,f2,f3;
ideal J = std(I); // correct
ideal F = f1,f2,f3;
module FF = f1*gen(1) + gen(2), f2*gen(1) + gen(3), f3*gen(1)+gen(4);
print(std(FF));
>0,0,     0,y3+1,x,    
>0,0,     1,0,   3y2+3,
>0,x,     0,3,   2x,   
>1,2y4+2y,0,0,   2y

what is wrong, since the Groebner basis is NOT {y3+1, x} but {y3+1,2x,x2+x}

funny enough, it works well for the 2 generators:

ideal G = f1,f2;
module GG = f1*gen(1) + gen(2), f2*gen(1) + gen(3);
print(std(GG));
>0,0,   y3+1,2x, 
>2,y3+1,0,   3y2,
>0,2xy, 3,   2x

what is by no doubt correct. Thanks in advance, Viktor

[wienand]

patch to fix component check in gcd poly creation and tidied up division checks for ring coefficients

[wienand@…]

The error was due to a variable switch in the check for equal components in the gcd poly creation routine.

Patch for the error and some tidying up for divisibility tests in coefficients rings are attached. I am not sure how comitting is regulated at the moment, can I go ahead and commit or is there some kind for CI/testing going on?

[wienand]

patch to fix component check in gcd poly creation and tidied up division checks for ring coefficients

[wienand]

That happens if replying without a final test and too much Python programming ... brackets ...

See the second attachement for the correct patch.

Output of given example:

                     SINGULAR                                 /  Development
 A Computer Algebra System for Polynomial Computations       /   version 3-1-2
                                                           0<
 by: W. Decker, G.-M. Greuel, G. Pfister, H. Schoenemann     \   Oct 2010
FB Mathematik der Universitaet, D-67653 Kaiserslautern        \
// ** executing /home/oliver.wienand/sandbox/Singular/LIB/.singularrc
> ring r = (integer, 4), (x,y), lp;
ng R = (integer, 4), (x,y), (c,lp); // elim.mod.comp ordering
poly f1 = 2*x*y;
poly f2 = 3*y^3+3;
poly f3 = x^2-3*x;
ideal I = f1,f2,f3;
ideal J = std(I); // correct
ideal F = f1,f2,f3;
module FF = f1*gen(1) + gen(2), f2*gen(1) + gen(3), f3*gen(1)+gen(4);
print(std(FF));
// ** You are using coefficient rings which are not fields.
// ** Please note that only limited functionality is available
// ** for these coefficients.
// ** 
// ** The following commands are meant to work:
// ** - basic polynomial arithmetic
// ** - std
// ** - syz
// ** - lift
// ** - reduce
> poly f1 = 2*x*y;
> poly f2 = 3*y^3+3;
> poly f3 = x^2-3*x;
> ideal I = f1,f2,f3;
> ideal J = std(I); // is correct
> print(J);
y3+1,
2x,
x2+x
> ideal F = f1,f2,f3;
> module SF = syz(F);
> print(SF);
2,x+1,3y3+3,0,   
0,0,  2xy,  x2+x,
0,2y, 0,    y3+1 
> print(transpose(matrix(SF))*transpose(matrix(F)));
0,
0,
0,
0 
> 
. ring R = (integer, 4), (x,y), (c,lp); // elim.mod.comp ordering
> poly f1 = 2*x*y;
> poly f2 = 3*y^3+3;
> poly f3 = x^2-3*x;
> ideal I = f1,f2,f3;
> ideal J = std(I); // correct
> ideal F = f1,f2,f3;
> module FF = f1*gen(1) + gen(2), f2*gen(1) + gen(3), f3*gen(1)+gen(4);
> print(std(FF));
0,   0,0,   0,  y3+1,2x, x2+x,
0,   2,y3+1,x+1,0,   3y2,0,   
x2+x,0,2xy, 0,  3,   2x, 0,   
y3+1,0,0,   2y, 0,   0,  1    

[wienand]

Fixed. See [13717].