Opened 14 years ago

Closed 14 years ago

#300 closed bug (fixed)

syz over rings is buggy

Reported by: levandov Owned by: seelisch
Priority: minor Milestone: 3-1-3 and higher
Component: dontKnow Version: 3-1-2
Keywords: syzygy, coefficients from ring Cc: wienand@…

Description

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

Attachments (2)

fix component check in gcd poly creation and tidied up division checks for ring coefficients.patch (2.8 KB) - added by wienand 14 years ago.
patch to fix component check in gcd poly creation and tidied up division checks for ring coefficients
fix component check in gcd poly creation and tidied up division checks for ring coefficients.2.patch (2.8 KB) - added by wienand 14 years ago.
patch to fix component check in gcd poly creation and tidied up division checks for ring coefficients

Download all attachments as: .zip

Change History (5)

Changed 14 years ago by wienand

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

comment:1 Changed 14 years ago by 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?

Changed 14 years ago by wienand

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

comment:2 Changed 14 years ago by 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    

comment:3 Changed 14 years ago by wienand

Resolution: fixed
Status: newclosed

Fixed. See [13717].

Note: See TracTickets for help on using tickets.