Opened 7 years ago
Last modified 4 years ago
#13439 new defect
xgcd incorrect for padic polynomials
Reported by:  saraedum  Owned by:  roed 

Priority:  minor  Milestone:  sage6.4 
Component:  padics  Keywords:  gcd 
Cc:  Merged in:  
Authors:  Reviewers:  David Roe  
Report Upstream:  N/A  Work issues:  
Branch:  u/saraedum/ticket/13439 (Commits)  Commit:  fb269f615a445ebf831a85ad781684173cd65228 
Dependencies:  #13630, #13619, #13620  Stopgaps:  #13537 
Description (last modified by )
xgcd
is broken for padics:
sage: R.<x> = Qp(3,3)[] sage: f = 3*x + 7 sage: g = 5*x + 9 sage: f.xgcd(f*g)[0].is_one() True sage: R.<x> = Qp(3)[] sage: f = 490473657*x + 257392844/729 sage: g = 225227399/59049*x  8669753175 sage: f.xgcd(f*g)[0].is_one() True
The algorithm used is the standard Euclidean algorithm which is afaik not correct for inexact fields. Or are my examples somehow incorrect?
Attachments (1)
Change History (20)
comment:1 followup: ↓ 2 Changed 7 years ago by
 Description modified (diff)
comment:2 in reply to: ↑ 1 Changed 7 years ago by
 Stopgaps set to #13537
Replying to saraedum:
The only place where the doctests called that xgcd was in the padic Lseries. I disabled the calls there until we have a working xgcd for padics.
Just found out about stopgaps. A stopgap makes of course much more sense than just removing functionality.
comment:3 Changed 7 years ago by
 Summary changed from padic xgcd incorrect to xgcd incorrect for padic polynomials
comment:4 Changed 7 years ago by
 Dependencies set to #13630
comment:5 Changed 7 years ago by
 Dependencies changed from #13630 to #13630, #13619
comment:6 Changed 7 years ago by
 Dependencies changed from #13630, #13619 to #13630, #13619, #13620
Changed 7 years ago by
comment:7 Changed 7 years ago by
 Reviewers set to David Roe
This is great. I could never get up the motivation to fix this since I always wanted to fix so many other things about padic polynomials first. I'll review it once the prerequisites are finished.
comment:8 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:9 Changed 6 years ago by
 Branch set to u/niles/ticket/13439
 Created changed from 09/07/12 18:55:38 to 09/07/12 18:55:38
 Modified changed from 08/13/13 15:35:53 to 08/13/13 15:35:53
comment:10 Changed 6 years ago by
 Commit set to 0426249cc2c8162bb32dc965eecb0c3050cc689f
rebased and converted to git branch; no other changes
New commits:
0426249  Trac #13439: implemented (x)gcd for polynomials over padic rings and fields

comment:11 Changed 6 years ago by
 Commit changed from 0426249cc2c8162bb32dc965eecb0c3050cc689f to a857a1c5aa59bd00a7d4c0041f47a681cd562d8b
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
e3315d8  Trac #13626: implemented gcd for padics

c3df981  Trac #13441: refactored gcd to not use _gcd calls anymore

aab8e2e  Merge branch 'ticket/13441' into ticket/13626

5b6e9c6  Trac #13628: refactored xgcd to not use _xgcd calls anymore.

f66e7a2  Merge branch 'ticket/13628' into ticket/13627

da9b384  Trac #13627: implemented xgcd for padics

861d698  Trac #13629: rings can provide _xgcd_univariate_polynomial for xgcd computations

b7fcb0b  Merge branch 'ticket/13629' into ticket/13630

b3eee8a  Trac #13442: rings can provide _gcd_univariate_polynomial for polynomial factorization

abc6b02  Merge branch 'ticket/13442' into ticket/13630

comment:12 Changed 6 years ago by
I am working on this in an attempt to resolve #9457. Bughunting there triggers the stopgap for this ticket (see comment 12 there). I have now created git branches for all of this ticket's dependencies and merged them here. Unfortunately the tests in this ticket description now trigger an error:
sage: R.<x> = Qp(3,3)[] sage: f = 3*x + 7 sage: g = 5*x + 9 sage: f.xgcd(f*g)[0].is_one() Traceback (most recent call last) ... TypeError: _xgcd_univariate_polynomial() takes exactly 2 arguments (3 given)
So there are some problems here, possibly caused by my rebasing . . .
comment:13 Changed 6 years ago by
 Commit changed from a857a1c5aa59bd00a7d4c0041f47a681cd562d8b to 65c0b433c34d7473e5d6fe9f85707856246fd866
comment:14 Changed 6 years ago by
After a change in #13629, this seems to be working correctly and giving the output written in the examples/tests. But the main examples on this ticket description are still broken.
comment:15 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:16 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:17 Changed 5 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:18 Changed 4 years ago by
 Branch changed from u/niles/ticket/13439 to u/saraedum/ticket/13439
comment:19 Changed 4 years ago by
 Commit changed from 65c0b433c34d7473e5d6fe9f85707856246fd866 to fb269f615a445ebf831a85ad781684173cd65228
The only place where the doctests called that xgcd was in the padic Lseries. I disabled the calls there until we have a working xgcd for padics.