xgcd incorrect for padic polynomials

[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?

Depends on #13630
Depends on #13619
Depends on #13620

Component: padics

Keywords: gcd

Stopgaps: #13537

Branch/Commit: u/saraedum/ticket/13439 @ fb269f6

Reviewer: David Roe

Issue created by migration from https://trac.sagemath.org/ticket/13439

[saraedum]

comment:1

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.

[saraedum]

Stopgaps: #13537

[saraedum]

comment:2

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.

[saraedum]

Dependencies: #13630

[saraedum]

Changed dependencies from #13630 to #13630, #13619

[saraedum]

Changed dependencies from #13630, #13619 to #13630, #13619, #13620

[saraedum]

Attachment: trac_13439.patch.gz

[roed314]

comment:7

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.

[roed314]

Reviewer: David Roe

[nilesjohnson]

Branch: u/niles/ticket/13439

[nilesjohnson]

Commit: 0426249

[nilesjohnson]

comment:10

rebased and converted to git branch; no other changes

---

New commits:

0426249

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

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 0426249 to a857a1c

[nilesjohnson]

comment:12

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 . . .

[sagetrac-git]

Changed commit from a857a1c to 65c0b43

[sagetrac-git]

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

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

[nilesjohnson]

comment:14

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.

[saraedum]

Changed branch from u/niles/ticket/13439 to u/saraedum/ticket/13439

[chriswuthrich]

Changed commit from 65c0b43 to fb269f6

[chriswuthrich]

comment:19

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

---

New commits:

fb269f6

Merge branch 'develop' into t/13439/ticket/13439

[EnderWannabe]

comment:20

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)