Opened 8 years ago
Last modified 4 months 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 (21)
comment:1 followup: ↓ 2 Changed 8 years ago by
 Description modified (diff)
comment:2 in reply to: ↑ 1 Changed 8 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 8 years ago by
 Summary changed from padic xgcd incorrect to xgcd incorrect for padic polynomials
comment:4 Changed 8 years ago by
 Dependencies set to #13630
comment:5 Changed 8 years ago by
 Dependencies changed from #13630 to #13630, #13619
comment:6 Changed 8 years ago by
 Dependencies changed from #13630, #13619 to #13630, #13619, #13620
Changed 8 years ago by
comment:7 Changed 8 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 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:9 Changed 7 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 7 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 7 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 7 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 7 years ago by
 Commit changed from a857a1c5aa59bd00a7d4c0041f47a681cd562d8b to 65c0b433c34d7473e5d6fe9f85707856246fd866
comment:14 Changed 7 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 7 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 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:18 Changed 5 years ago by
 Branch changed from u/niles/ticket/13439 to u/saraedum/ticket/13439
comment:19 Changed 5 years ago by
 Commit changed from 65c0b433c34d7473e5d6fe9f85707856246fd866 to fb269f615a445ebf831a85ad781684173cd65228
comment:20 Changed 4 months ago by
As of today, the main examples in this ticket all work. However, xgcd itself is still broken. Examples can be found by search:
sage: R = PolynomialRing(Qp(5), 'x') sage: while True: sage: f,g = R.random_element(degree=3), R.random_element(degree=3) sage: d,a,b = xgcd(f,g) sage: if a*f + b*g != d: sage: print("d =", d) sage: print("a =", a) sage: print('f = ', f) sage: print('b = ', b) sage: print('g = ', g) sage: break d = 1 + O(5^2) a = (3*5^41 + O(5^43))*x^2 + (3*5^14 + O(5^16))*x + 2*5^11 + 3*5^12 + O(5^13) f = (4*5^1 + 2 + 2*5 + 5^2 + 4*5^3 + 2*5^4 + 3*5^5 + 4*5^7 + 2*5^8 + 2*5^9 + 4*5^10 + 3*5^11 + 2*5^12 + 4*5^15 + 5^16 + 5^17 + 3*5^18 + O(5^19))*x^3 + (4*5^12 + 2*5^11 + 5^9 + 2*5^8 + 4*5^5 + 3*5^4 + 4*5^3 + 2*5^2 + 5^1 + 1 + 5 + 3*5^2 + 3*5^3 + 2*5^4 + 2*5^5 + 3*5^6 + O(5^7))*x^2 + (5 + 5^2 + 2*5^3 + 5^4 + 2*5^5 + 5^6 + 4*5^7 + 2*5^8 + 4*5^9 + 5^10 + 2*5^11 + 5^12 + 3*5^13 + 5^14 + 3*5^15 + 2*5^17 + 2*5^18 + 5^19 + 4*5^20 + O(5^21))*x + 3*5^5 + 5^2 + 5^1 + 4*5 + 4*5^2 + 4*5^4 + 2*5^5 + 5^6 + 5^8 + 2*5^9 + 2*5^10 + 3*5^11 + 2*5^12 + 5^13 + 3*5^14 + O(5^15) b = (4*5^14 + O(5^16))*x^2 + O(5^11)*x + O(5^38) g = (2*5^26 + 4*5^28 + 5^29 + 2*5^31 + 2*5^32 + 5^35 + 4*5^36 + 5^37 + 3*5^38 + 5^39 + 3*5^40 + 5^41 + 3*5^42 + 3*5^43 + 5^44 + O(5^45))*x^3 + (2*5^1 + 5 + 5^4 + 4*5^6 + 2*5^7 + 4*5^8 + 2*5^9 + 5^10 + 5^11 + 5^13 + 4*5^14 + 5^17 + 2*5^18 + O(5^19))*x^2 + (5^3 + 2*5^4 + 2*5^5 + 3*5^6 + 4*5^7 + 4*5^8 + 4*5^9 + 3*5^10 + 2*5^11 + 2*5^15 + 2*5^16 + 4*5^17 + 3*5^18 + 4*5^19 + O(5^21))*x + 1 + 4*5 + 4*5^3 + 3*5^4 + 3*5^5 + 4*5^7 + 3*5^8 + 5^9 + 5^11 + 2*5^12 + 5^13 + 2*5^14 + 4*5^15 + 4*5^17 + 5^18 + 3*5^19 + O(5^20)
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.