Bug #1740
MinGens gives non minimal gens *if some deg=0*
Description
In this example MinGens gives a result which is not minimal.
Can the algorithm MinGens work if the input is homogeneous but with some weight=0?
I don't think so, but think about it and block MinGens in this case (and fix whatever might not work if homogeneous with null weights)
letters := [ascii(96+i) | i in 1..26];
--======================================================
W := mat([[0, 2, 2, 2, 1, 1, 1, 1]]);
R := NewPolyRing(QQ, first(letters, NumCols(W)), MakeTermOrdMat(W), 1);
use R;
NumIndets(R);
indets(R);
F := a^4*e -a^4*g -a^3*f -a^3*g +a^2*e +2*a^2*g -2*a*f -a*h +g;
G := a^3*(a^2*e*f +a^2*e*g -a^2*f*g -a^2*g^2 -a^2*e*h +a^2*g*h -a*f^2 -2*a*f*g -a*g^2 +a*f*h +a*g*h -e*f);
LL := [ F,
F*(-a^2*f +a^2*h -a^2*g +2*f +g) +a*G,
G];
L := MinGens(ideal(LL)); indent(L);
L[2] IsIn ideal(L[1],L[3]);
GenRepr(L[2], ideal(L[1], L[3]));
Related issues
History
#1
Updated by Anna Maria Bigatti 12 months ago
Updated by This example was generated by simplifying the original big example found by L.Robbiano
#2
Updated by John Abbott 12 months ago
Updated by - Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850
I wonder if it could be made to work by assuming that all indets with weight 0 actually have epsilon (an infinitesimal).
Strictly the polynomial would no longer be homogeneous: e.g. some PPs would have degree 2 others 2+epsilon.
Anna reported (by phone) that Robbiano observed that the current impl often does give the right answer.
Anna also reported that it was not easy finding a smaller example which gave the wrong answer.
Not at all sure that my idea is a good one, but I did want to write it down.
#3
Updated by Anna Maria Bigatti 12 months ago
smaller
W := mat([[0, 1, 1]]);
R := NewPolyRing(QQ, first(lettere, NumCols(W)), MakeTermOrdMat(W), 1);
use R;
LL := [
a^4*b -a^4*c -2*a^3*c +a^2*b +2*a^2*c -3*a*c +c,
-4*a^4*c^2 -a^3*c^2 +2*a^2*b*c +3*a^2*c^2 -6*a*c^2 +2*c^2,
a^5*b*c -a^5*c^2 -2*a^4*c^2 -a^3*b*c
];
L := MinGens(ideal(LL)); indent(L);
L[2] IsIn ideal(L[1],L[3]);
GenRepr(L[2], ideal(L[1], L[3]));
#4
Updated by Anna Maria Bigatti 11 months ago
SetVerbosityLevel(120); --====================================================== W := mat([[0, 1, 1]]); R := NewPolyRing(QQ, first(lettere, NumCols(W)), MakeTermOrdMat(W), 1); use R; LL := [ a*b +c, a^2*c, a^2*b ]; L := MinGens(ideal(LL)); indent(L); ---> [a*b +c, a^2*c, -a*c] L[2] IsIn ideal(L[1],L[3]); ---> true
So, what happens here?
The generators are processed in this order:
- a*b +c
- a^2*c
- a^2*b ---> -a*c
When all weights are positive,
if deg(T1) = deg(T2) and T1 | T2 then T1 = T2
(thanks J.Abbott for pointing that out)
so T2+... could be reduced by T1+... as well as the opposite, making the order in which we deal with them irrelevant.
This is not the case here:
deg(a*c) = deg(a^2*c) and a*c | a^2*c
but a^2*c was the one found first and is not reduced by the new one.
Notice that we are following this ordering
[[0, 1, 1], [1, 0, 0], [0, 0, -1]])
we choose the generators in increasing order
a*b < a^2*c < a^2*b
and also choosing with decreasing order we would meet the same problem, worse, in fact.
This is the point I wanted to study (if there was a way to guarantee the result even with 0 weights) and why I looked so much for a small example.
Now I'm inclined to say there is no trivial way out.
The good point is that we could just interreduce the polynomials with the same degree, but that would require changing the "homogeneous" code ad-hoc and is not trivial.
#5
Updated by Anna Maria Bigatti 11 months ago
- Related to Feature #1742: MinGens could be faster added
#6
Updated by Anna Maria Bigatti 11 months ago
- Subject changed from MinGens gives non minimal gens (if some deg=0) to MinGens gives non minimal gens *if some deg=0*
#7
Updated by John Abbott 10 months ago
I have inserted a "quick hack" solution: just call HasPositiveGrading inside myMinGens.
It detects the examples here. Checking in so that we can make an interim release tomorrow,
#8
Updated by Anna Maria Bigatti about 1 month ago
For the time being: should we give error? (as if non-homogeneous?)
#9
Updated by John Abbott about 1 month ago
Perhaps ERR::NYI ?
#10
Updated by Anna Maria Bigatti about 1 month ago
- Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880