Opened 13 years ago

Closed 12 years ago

#251 closed bug (fixed)

non-commutative liftstd seems to be wrong

Reported by: Oleksandr Owned by: seelisch
Priority: major Milestone: 3-1-2 and higher
Component: singular-kernel Version: 3-0-4
Keywords: nc, lift, liftstd, std Cc:

Description

Hello,

I am in trouble interpreting the results produced by "std(Plural)" and "liftstd(Plural)".

As far as I understand, they both return a left Groebner basis of an ideal or a module.

In the following example, their results do not agree with each other; the variable T appears in one Groebner basis, but not in the other.

I would appreciate your help. Thank you.

akishi

> LIB "nctools.lib";
> option(redSB);
> option(redTail);
> ring r=(0,q),(U,V,S,T),lp;
> matrix C[4][4];
C[1,2]=1/q;
C[1,3]=1;
C[1,4]=1;
C[2,3]=1;
C[2,4]=1;
C[3,4]=1/q;
> def R=nc_algebra(C,0);
> setring R;
> R;
// characteristic : 0
// 1 parameter : q
// minpoly : 0
// number of vars : 4
// block 1 : ordering lp
// : names U V S T
// block 2 : ordering C
// noncommutative relations:
// VU=1/(q)*UV
// TS=1/(q)*ST
> ideal I=U*V+S-V-1,U-V-V*T,U+V-V*S;
> I;
I[1]=UV-V+S-1
I[2]=U-VT-V
I[3]=U-VS+V
> ideal G=std(I);
> matrix M;
> ideal H=liftstd(I,M);
> G;
G[1]=T
G[2]=S-1
G[3]=V
G[4]=U
> std(G);
_[1]=T
_[2]=S-1
_[3]=V
_[4]=U
> H;
H[1]=(q7-q6-3q5+5q4-2q3)*S+(-q7+q6+3q5-5q4+2q3)
H[2]=(-q11+2q10+2q9-8q8+7q7-2q6)*V
H[3]=(q6-3q4+2q3)*U
> std(H);
_[1]=S-1
_[2]=V
_[3]=U

Change History (9)

comment:1 Changed 13 years ago by Oleksandr

Owner: changed from hannes to Oleksandr

comment:2 Changed 13 years ago by Oleksandr

Status: newassigned

comment:3 Changed 12 years ago by levandov

I've found the way to tackle this problem. Consider the replacement 1/q with Q.

ring r=(0,Q),(U,V,S,T),lp;
matrix C[4][4];
C[1,2]=Q;
C[1,3]=1;
C[1,4]=1;
C[2,3]=1;
C[2,4]=1;
C[3,4]=Q;
print(C);
def R=nc_algebra(C,0);
setring R;
R;
ideal I=U*V+S-V-1,U-V-V*T,U+V-V*S;
option(redSB);
option(redTail);
slimgb(I);// correct
std(I); // is correct as well!!!

In both cases the answer is

U, V, S-1

However, executing

matrix Z; 
liftstd(I,Z);

takes a long time, but still delivers an answer

_[1]=(2Q11-5Q10+3Q9+Q8-Q7)*S+(-2Q11+5Q10-3Q9-Q8+Q7)
_[2]=(-2Q16+7Q15-8Q14+2Q13+2Q12-Q11)*V
_[3]=(2Q7-3Q6+Q4)*U

which is - after normalizing - the same as above.

Hence, there's something wrong with the multiplication routines AND possibly with criteria. Alex, please check that this q-commutative algebra is handled correctly with respect to multiplication and criteria. Regards, Viktor

comment:4 Changed 12 years ago by Oleksandr

Owner: changed from Oleksandr to seelisch
Status: assignednew

while computing ideal G=std(I);

I have got a lot of assume violations at longtrans.cc:1387 like follows:

// ***dError: assume violation at longtrans.cc:1387 condition: a->n==__null && b->n==__null occured at: 
  #0 at longtrans.cc:1388    in ntIntDiv            
  #1 at polys1.cc:568        in p_Content           
  #2 at gring.cc:1510        in gnc_ReduceSpolyNew  
  #3 at gring.h:205          in nc_ReduceSpoly      
  #4 at gr_kstd2.cc:87       in redGrFirst          
  #5 at gr_kstd2.cc:1181     in gnc_gr_bba          
  #6 at gring.h:255          in nc_GB               
  #7 at kstd1.cc:1798        in kStd                

can there be something wrong with that p_Content?

TODO for Frank, please fix that assume-error, e,g, using the following code:

option(redSB); option(redTail);
ring r=(0,q),(U,V,S,T),lp;
matrix C[4][4];
C[1,2]=1/q; C[1,3]=1; C[1,4]=1;
            C[2,3]=1; C[2,4]=1;
                      C[3,4]=1/q;
def R=nc_algebra(C,0); setring R;
ideal I = U*V+S-V-1, U-V-V*T, U+V-V*S; 
std(I);

comment:5 Changed 12 years ago by Oleksandr

Besides, judging from the replacement example (1/q with Q) it seems that "T" should not appear in std(T)... no?

comment:6 Changed 12 years ago by Oleksandr

Owner: changed from seelisch to Oleksandr

Just some more test results:

> slimgb(I);
_[1]=S-1
_[2]=V
_[3]=U
LIB "teachstd.lib";
> printlevel = 0;
> standard(I);   
_[1]=UV-V+S-1
_[2]=U-VT-V
_[3]=U-VS+V
_[4]=(q)*V2T+(q)*V2-V+S-1
_[5]=(q)*V2S+(-q)*V2-V+S-1
_[6]=VS-VT-2*V
_[7]=(q-1)/(q)*VT2+(2q-2)/(q)*VT+(q-1)/(q)*V+(q-1)/(q2)*S+(-q+1)/(q2)
_[8]=(-q+1)*V+(-q+1)/(q)*S+(q-1)/(q)
_[9]=S2+(-q2-2q+2)/(q2)*ST+(-q2-4q+2)/(q)*S+(q2+2q-2)/(q)*T+(q2+3q-2)/(q)
_[10]=(q2+q-2)/(q2)*ST+(q2+q-2)/(q)*S+(-q2-q+2)/(q)*T+(-q2-q+2)/(q)
_[11]=(q+1)/(q2)*S+(-q-1)/(q2)

> simplify(_, 1+2+4);
_[1]=UV-V+S-1
_[2]=U-VT-V
_[3]=U-VS+V
_[4]=V2T+V2-1/(q)*V+1/(q)*S-1/(q)
_[5]=V2S-V2-1/(q)*V+1/(q)*S-1/(q)
_[6]=VS-VT-2*V
_[7]=VT2+2*VT+V+1/(q)*S-1/(q)
_[8]=V+1/(q)*S-1/(q)
_[9]=S2+(-q2-2q+2)/(q2)*ST+(-q2-4q+2)/(q)*S+(q2+2q-2)/(q)*T+(q2+3q-2)/(q)
_[10]=ST+(q)*S+(-q)*T+(-q)
_[11]=S-1

> ideal II = _;
> slimgb(II);
_[1]=S-1
_[2]=V
_[3]=U


> std(II);                               
_[1]=T
_[2]=S-1
_[3]=V
_[4]=U

> std(ideal(II[1..6], II[8..11]));       
_[1]=S-1
_[2]=V
_[3]=U

> std(ideal(II[1..6], II[8..11]) + II[7]); 
_[1]=T
_[2]=S-1
_[3]=V
_[4]=U

> std(std(ideal(II[1..6], II[8..11])), II[7]);
_[1]=S-1
_[2]=V
_[3]=U

> II[7];                                  
VT2+2*VT+V+1/(q)*S-1/(q)

Moreover:

> interred(II);
_[1]=S-1
_[2]=V
_[3]=U

The following will run VERY slowly:

std(ideal(II[7], II[1]));
std((ideal(II[7], II[3], II[3], II[9])));
Last edited 12 years ago by Oleksandr (previous) (diff)

comment:7 Changed 12 years ago by Oleksandr

Owner: changed from Oleksandr to seelisch
ring r=(0,q),(U,V,S,T),lp;
poly o = (-q4-5q3-2q2+10q-4)/(q)*ST2+(-q4-6q3-5q2+12q-4)*ST+(q5+5q4+2q3-10q2+4q)*T2 + (q5+6q4+5q3-12q2+4q)*T;

now applying p_Content on this polynomial changes it into

poly O = (-q2-2q+2)*ST2+(-q2-3q+2)*ST+(q3+2q2-2q)*T2+(q3+3q2-2q)*T

which doesn't seem correct thing to do since the 1st quotient of coeffs is:

> leadcoef(o)/leadcoef(O);
(q2+3q-2)/(q)

whereas both other quotes are

(q2+3q-2)

The debug version produces the following:

// ***dError: assume violation at longtrans.cc:1393 condition: a->n==__null && b->n==__null occured at: 
  #0 at longtrans.cc:1394    in ntIntDiv            
  #1 at polys1.cc:568        in p_Content           
  #2 at iplib.cc:482         in iiMake_proc         
  #3 at iparith.cc:1462      in jjPROC              
  #4 at iparith.cc:7454      in iiExprArith2        
  #5 at iparith.cc:6807      in jjKLAMMER_PL        
  #6 at iparith.cc:7976      in iiExprArithM        

comment:8 Changed 12 years ago by seelisch

The assume conditions in longtrans.cc are correct. The corresponding method (ntIntDiv) expects two numbers, that is, two rational functions but WITH CLEARED DENOMINATORS! Otherwise results will in general not be correct! And this is what happens when running your sample code. I have checked that cleardenom(o) yields indeed the correct O = cleardenom(o) = (-q2-2q+2)*ST2+(-q3-3q2+2q)*ST+(q4+2q3-2q2)*T2+(q4+3q3-2q2)*T So maybe, the call of p_Content in polys1.cc:568 should be called only after clearing denominators?

Anyway, I have nothing changed in this place. So I do not know what's going on when running your sample code. Who should take a look?

comment:9 Changed 12 years ago by seelisch

Resolution: fixed
Status: newclosed

fixed by git commit 9ab0d92415ff1396d13b1c5a94330ac125116b68; Now sample code (at the beginning of this ticket) yields the same (and correct) result. Running gdb shows no more assume violations when running that code.

Note: See TracTickets for help on using tickets.