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: sage-6.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 saraedum)

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)

trac_13439.patch (16.2 KB) - added by saraedum 7 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 follow-up: Changed 7 years ago by saraedum

  • Description modified (diff)

The only place where the doctests called that xgcd was in the padic L-series. I disabled the calls there until we have a working xgcd for padics.

comment:2 in reply to: ↑ 1 Changed 7 years ago by saraedum

  • Stopgaps set to #13537

Replying to saraedum:

The only place where the doctests called that xgcd was in the padic L-series. 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 saraedum

  • Summary changed from padic xgcd incorrect to xgcd incorrect for padic polynomials

comment:4 Changed 7 years ago by saraedum

  • Dependencies set to #13630

comment:5 Changed 7 years ago by saraedum

  • Dependencies changed from #13630 to #13630, #13619

comment:6 Changed 7 years ago by saraedum

  • Dependencies changed from #13630, #13619 to #13630, #13619, #13620

Changed 7 years ago by saraedum

comment:7 Changed 7 years ago by roed

  • 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 p-adic polynomials first. I'll review it once the prerequisites are finished.

comment:8 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:9 Changed 6 years ago by niles

  • 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 niles

  • Commit set to 0426249cc2c8162bb32dc965eecb0c3050cc689f

rebased and converted to git branch; no other changes


New commits:

0426249Trac #13439: implemented (x)gcd for polynomials over padic rings and fields

comment:11 Changed 6 years ago by git

  • Commit changed from 0426249cc2c8162bb32dc965eecb0c3050cc689f to a857a1c5aa59bd00a7d4c0041f47a681cd562d8b

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

e3315d8Trac #13626: implemented gcd for padics
c3df981Trac #13441: refactored gcd to not use _gcd calls anymore
aab8e2eMerge branch 'ticket/13441' into ticket/13626
5b6e9c6Trac #13628: refactored xgcd to not use _xgcd calls anymore.
f66e7a2Merge branch 'ticket/13628' into ticket/13627
da9b384Trac #13627: implemented xgcd for padics
861d698Trac #13629: rings can provide _xgcd_univariate_polynomial for xgcd computations
b7fcb0bMerge branch 'ticket/13629' into ticket/13630
b3eee8aTrac #13442: rings can provide _gcd_univariate_polynomial for polynomial factorization
abc6b02Merge branch 'ticket/13442' into ticket/13630

comment:12 Changed 6 years ago by niles

I am working on this in an attempt to resolve #9457. Bug-hunting 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 git

  • Commit changed from a857a1c5aa59bd00a7d4c0041f47a681cd562d8b to 65c0b433c34d7473e5d6fe9f85707856246fd866

Branch pushed to git repo; I updated commit sha1. New commits:

0570335fix arguments for sage.categories.fields._xgcd_univariate_polynomial
65c0b43Merge branch 'ticket/13629' into ticket/13439

comment:14 Changed 6 years ago by niles

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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:16 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:17 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:18 Changed 4 years ago by saraedum

  • Branch changed from u/niles/ticket/13439 to u/saraedum/ticket/13439

comment:19 Changed 4 years ago by wuthrich

  • Commit changed from 65c0b433c34d7473e5d6fe9f85707856246fd866 to fb269f615a445ebf831a85ad781684173cd65228

I work on #20254. The solution there will avoid the use of xgcd for p-adic L-functions.


New commits:

fb269f6Merge branch 'develop' into t/13439/ticket/13439
Note: See TracTickets for help on using tickets.