Opened 4 years ago
Closed 4 years ago
#23259 closed defect (fixed)
polredabs does not does not always return the correct transformation map
Reported by:  mderickx  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  number fields  Keywords:  
Cc:  mderickx  Merged in:  
Authors:  Maarten Derickx  Reviewers:  Vincent Delecroix 
Report Upstream:  Fixed upstream, but not in a stable release.  Work issues:  
Branch:  d097929 (Commits, GitHub, GitLab)  Commit:  d0979299e4e2b40af7723a03876b147e6c200724 
Dependencies:  Stopgaps: 
Description
In this example I ask pari to polredabs a polynomial f
and also return a transformation map h
such that h(x)
is a root of f
in QQ[x]/g
.
sage: R.<x> = QQ[] ....: f = x^12 + x^7  1/5*x^6  3*x^5 + 13/5*x^4 + 11/5*x^3 + 2/5*x^2 + 2/5*x + 1/5 ....: gh = pari(f).polredabs(1) ....: print "gh", gh ....: g,h = gh[0].sage(locals={'x':x}),gh[1].lift().sage(locals={'x':x}) ....: print "g",g ....: print "h",h ....: print "f(h)mod g", f(h)%g ....: gh [x^12  2*x^11 + 2*x^10  11*x^9 + 13*x^8 + 15*x^7  x^6  5*x^5 + 5, Mod(x^11  2*x^10 + 2*x^9  11*x^8 + 13*x^7 + 15*x^6  x^5  5*x^4, x^12  2*x^11 + 2*x^10  11*x^9 + 13*x^8 + 15*x^7  x^6  5*x^5 + 5)] g x^12  2*x^11 + 2*x^10  11*x^9 + 13*x^8 + 15*x^7  x^6  5*x^5 + 5 h x^11  2*x^10 + 2*x^9  11*x^8 + 13*x^7 + 15*x^6  x^5  5*x^4 f(h)mod g 195293748/5*x^11 + 244181236/5*x^10  634884076/5*x^9 + 3564400908/5*x^8  2539683564/5*x^7 + 166278100*x^6  14647209952/5*x^5  1269578400*x^4 + 4072182580*x^3 + 3017386300*x^2  1562284000*x  7518315624/5
The above shows that f,g and h don't satisfy the promised relation. Changing the leading term of f from 12 to 11 does give something correct.
sage: f = x^11 + x^7  1/5*x^6  3*x^5 + 13/5*x^4 + 11/5*x^3 + 2/5*x^2 + 2/5*x + 1/5 ....: gh = pari(f).polredabs(1) ....: print "gh", gh ....: g,h = gh[0].sage(locals={'x':x}),gh[1].lift().sage(locals={'x':x}) ....: print "g",g ....: print "h",h ....: print "f(h)mod g", f(h)%g ....: gh [x^11  2*x^10 + 2*x^9  11*x^8 + 13*x^7 + 15*x^6  x^5  5*x^4  5, Mod(1/5*x^10 + 2/5*x^9  2/5*x^8 + 11/5*x^7  13/5*x^6  3*x^5 + 1/5*x^4 + x^3, x^11  2*x^10 + 2*x^9  11*x^8 + 13*x^7 + 15*x^6  x^5  5*x^4  5)] g x^11  2*x^10 + 2*x^9  11*x^8 + 13*x^7 + 15*x^6  x^5  5*x^4  5 h 1/5*x^10 + 2/5*x^9  2/5*x^8 + 11/5*x^7  13/5*x^6  3*x^5 + 1/5*x^4 + x^3 f(h)mod g 0
This error was produced on SageMath version 7.6 on OS X 10.12.
Change History (13)
comment:1 Changed 4 years ago by
comment:2 Changed 4 years ago by
 Report Upstream changed from Not yet reported upstream; Will do shortly. to Reported upstream. No feedback yet.
comment:3 Changed 4 years ago by
comment:4 Changed 4 years ago by
 Report Upstream changed from Reported upstream. No feedback yet. to Fixed upstream, but not in a stable release.
This has been fixed upstream in commit 1420fa40a which can be found at: https://pari.math.ubordeaux.fr/cgibin/gitweb.cgi?p=pari.git;a=commit;h=1420fa40a7d7b43cf2d21c530a0a1d394bac245d
comment:5 Changed 4 years ago by
 Branch set to u/mderickx/23259
 Commit set to 4ac02825b1c290c2ae77137a6d3783b5eba622ba
 Status changed from new to needs_review
comment:6 Changed 4 years ago by
 Status changed from needs_review to needs_work
Merge conflict (the patch needs to be based on 8.0.beta11
).
comment:7 Changed 4 years ago by
 Commit changed from 4ac02825b1c290c2ae77137a6d3783b5eba622ba to 72412ac25c54b3147df00c5ca3888ca4d97be801
Branch pushed to git repo; I updated commit sha1. New commits:
72412ac  Merge branch 'u/mderickx/23259' of git://trac.sagemath.org/sage into develop

comment:8 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:9 followup: ↓ 11 Changed 4 years ago by
This line is horrible
g,h = gh[0].sage(locals={'x':x}),gh[1].lift().sage(locals={'x':x})
comment:10 Changed 4 years ago by
 Commit changed from 72412ac25c54b3147df00c5ca3888ca4d97be801 to d0979299e4e2b40af7723a03876b147e6c200724
Branch pushed to git repo; I updated commit sha1. New commits:
d097929  improved polredabs doctest for trac 23259

comment:11 in reply to: ↑ 9 Changed 4 years ago by
Replying to vdelecroix:
This line is horrible
g,h = gh[0].sage(locals={'x':x}),gh[1].lift().sage(locals={'x':x})
I changed the doctest to something more elegant. Is it better now?
comment:12 Changed 4 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
Indeed. Thanks for this fix!
comment:13 Changed 4 years ago by
 Branch changed from u/mderickx/23259 to d0979299e4e2b40af7723a03876b147e6c200724
 Resolution set to fixed
 Status changed from positive_review to closed
The following shows that the error already occurs in pari.