non-commutative liftstd seems to be wrong

[Oleksandr]

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

[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

[Oleksandr]

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);

[Oleksandr]

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

[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

[Oleksandr]

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        

[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?

[seelisch]

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.