Opened 13 years ago

Closed 12 years ago

non-commutative liftstd seems to be wrong

Reported by: Owned by: Oleksandr seelisch major 3-1-2 and higher singular-kernel 3-0-4 nc, lift, liftstd, std

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
```

comment:1 Changed 13 years ago by Oleksandr

Owner: changed from hannes to Oleksandr

comment:2 Changed 13 years ago by Oleksandr

Status: new → assigned

comment:3 Changed 13 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 assigned → new

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
```
Version 0, edited 12 years ago by Oleksandr (next)

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 new → closed

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.