Bug #1758
Graeffe "sign bug"
Description
I put in a (not-so) "clever trick" in graeffe and graeffe3 so that the LC is positive if the coeff rings is ZZ/QQ.
This does not work if the coeff ring is not an ordered domain, because it simply checked the sign of the LC of the putative result (and negated the whole poly if the LC was negative).
I think it would be nice if graeffe/graeffe3 commuted with "reduction mod p". I think this implies that no clever trick can be used.
Investigate, and decide/implement.
History
#1
Updated by John Abbott 9 months ago
Updated by - Status changed from New to In Progress
- % Done changed from 0 to 10
Currently, trying to compute graeffe(f) over a finite field produces:
--> ERROR: Ring is not an ordered domain --> [CoCoALib] sign(RingElem)
Possible test cases: x^2+x+1 and x^3+x^2+x+1
#2
Updated by John Abbott 9 months ago
- Assignee set to John Abbott
- % Done changed from 10 to 50
I have removed the "sign tricks". Also checked-in.
I wonder if the doc should be changed to point out that sometimes the result might be minus what one hoped for?
#3
Updated by John Abbott 9 months ago
- Status changed from In Progress to Feedback
- % Done changed from 50 to 90
#4
Updated by John Abbott 7 months ago
A reasonable solution could be to define GraeffeN(f,n) to be the same as resultant(f(y), y-x^n).
This would then fix the scalar factor which is not fixed by the ad hoc description "polynomial whose
roots are the n-th powers of the roots of the original".
I find on Wikipedia a formula relating the short-cut version of graeffe(f) with the resultant version;
I have changed the implementation to adhere to what Wikipedia says.
#5
Updated by John Abbott 4 months ago
- Status changed from Feedback to Closed
- % Done changed from 90 to 100
- Estimated time set to 1.33 h