Opened 7 years ago
Closed 7 months ago
#12567 closed enhancement (fixed)
Implement padic nth roots
Reported by:  dequan  Owned by:  roed 

Priority:  major  Milestone:  sage6.4 
Component:  padics  Keywords:  padics, nth roots, sd87, padicIMA 
Cc:  roed, saraedum, dequan, serickson, reinier  Merged in:  
Authors:  Xavier Caruso  Reviewers:  David Roe 
Report Upstream:  N/A  Work issues:  
Branch:  6216be0 (Commits)  Commit:  6216be01a3885f6c10eea14afe16ebde6859683d 
Dependencies:  #23218, #25990  Stopgaps: 
Description
We are implementing padic nth roots as a padic Sage Days project
Attachments (1)
Change History (44)
comment:1 Changed 6 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:2 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:3 Changed 5 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:4 Changed 5 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:5 Changed 21 months ago by
 Keywords sd87 added
comment:6 Changed 9 months ago by
 Keywords padicIMA added
 Priority changed from minor to major
comment:7 Changed 9 months ago by
 Branch set to u/caruso/padic_nthroot
comment:8 Changed 9 months ago by
 Commit set to e639faebca801514e900f5e913b79003c5b02124
comment:9 Changed 9 months ago by
 Cc roed saraedum dequan serickson reinier added
 Dependencies set to #23218
I just wrote a generic implementation of padic nth root, working over any padic extension (unramified, totally ramified or mixed).
Doctests are coming soon...
comment:10 Changed 9 months ago by
 Commit changed from e639faebca801514e900f5e913b79003c5b02124 to 5a4bf734f4c6ff9481709424c29f54ed4b515b20
Branch pushed to git repo; I updated commit sha1. New commits:
5a4bf73  Implementation of padic nth root

comment:11 Changed 9 months ago by
 Commit changed from 5a4bf734f4c6ff9481709424c29f54ed4b515b20 to be503569b13f449375f6ab1daae94055b14e015c
Branch pushed to git repo; I updated commit sha1. New commits:
be50356  Added doctests

comment:12 Changed 9 months ago by
 Status changed from new to needs_review
comment:13 Changed 9 months ago by
 Commit changed from be503569b13f449375f6ab1daae94055b14e015c to d7c39b0d16419f75a1caf3b10c337e0d6c5b3d42
comment:14 Changed 9 months ago by
For ease of review, I attach the diff between this ticket and #23218
comment:15 Changed 9 months ago by
 Branch changed from u/caruso/padic_nthroot to u/roed/padic_nthroot
comment:16 Changed 9 months ago by
 Commit changed from d7c39b0d16419f75a1caf3b10c337e0d6c5b3d42 to 0324b667a00a264131f512111a7dbb6837fa1c98
 Reviewers set to David Roe
 Status changed from needs_review to positive_review
comment:17 Changed 9 months ago by
 Branch changed from u/roed/padic_nthroot to u/caruso/padic_nthroot
comment:18 Changed 9 months ago by
Perfect!
I've just changed a bit the doctests you added in order to have a test for the case where p1
divides e
(for which the algorithm I've implemented has an extra step).
comment:19 Changed 9 months ago by
 Commit changed from 0324b667a00a264131f512111a7dbb6837fa1c98 to 1bf897fc0c685be9f415f3b5608352b1a067e11e
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
1bf897f  Test for the case for p1 divides e

comment:20 Changed 9 months ago by
 Status changed from needs_review to positive_review
comment:21 Changed 9 months ago by
Great! I'll run the tests again.
comment:22 Changed 9 months ago by
 Status changed from positive_review to needs_work
Oops... there's a bug:
sage: K.<a> = Qq(2^3) sage: S.<x> = K[] sage: L.<pi> = K.extension(x^2 + 2*x + 2) sage: elt = L.random_element()^8 sage: elt.nth_root(8) # sometimes fails Traceback (most recent call last): ... ValueError: This element is not a nth power
comment:23 Changed 9 months ago by
Here's some more info. It looks like some chains of repeated square roots work while others fail.
sage: K.<a> = Qq(2^3) sage: S.<x> = K[] sage: L.<pi> = K.extension(x^2 + 2*x + 2) sage: ran = L.random_element(); elt = ran^8; r = elt.nth_root(8) ValueError: This element is not a nth power sage: ran a*pi^2 + a*pi^1 + a + a^2*pi^5 + a^2*pi^6 + (a^2 + 1)*pi^7 + (a^2 + 1)*pi^8 + a^2*pi^9 + a^2*pi^10 + (a + 1)*pi^11 + (a^2 + a + 1)*pi^12 + pi^13 + (a^2 + a)*pi^14 + (a^2 + a + 1)*pi^15 + (a^2 + 1)*pi^16 + a^2*pi^17 + (a^2 + 1)*pi^20 + (a + 1)*pi^21 + (a + 1)*pi^22 + (a^2 + a + 1)*pi^23 + (a^2 + a + 1)*pi^24 + (a^2 + a + 1)*pi^25 + pi^26 + (a + 1)*pi^27 + (a^2 + a)*pi^28 + pi^30 + (a^2 + 1)*pi^31 + a*pi^32 + a^2*pi^33 + pi^34 + a^2*pi^35 + O(pi^36) sage: r1 = elt.square_root() sage: r2 = r1.square_root() sage: r3 = r2.square_root() NotImplementedError: extending using the sqrt function not yet implemented sage: r1^2==elt True sage: r2^2==r1 True sage: s1 = L(1).square_root() sage: ran^2 == s1*r2 True sage: r1=r1 sage: r2 = r1.square_root() sage: r3 = r2.square_root() sage: ran == r3 True
comment:24 Changed 9 months ago by
This makes sense actually, since this field has no 8th root of unity.
comment:25 Changed 9 months ago by
Yes, that's it. We need to check all (or at least more) branches. I'm working on this now and will submit a revised version soon.
comment:26 Changed 9 months ago by
 Commit changed from 1bf897fc0c685be9f415f3b5608352b1a067e11e to 2cef5e09732e863322ae457e06d96c0a614b3a3a
Branch pushed to git repo; I updated commit sha1. New commits:
2cef5e0  Consider conjugates when computing successive pth roots

comment:27 Changed 9 months ago by
OK. The bug should be fixed now.
I'm not completely happy with the algorithm I've implemented since its complexity is possibly linear in p (i.e. exponential in log(p)). Something better should be feasible but I'll do it in another ticket (except if someone else does it now).
I attach a new diff with #23218
comment:28 Changed 9 months ago by
 Commit changed from 2cef5e09732e863322ae457e06d96c0a614b3a3a to c76a0a0e98e973fe0aac237132155bba1a4f0c7d
Branch pushed to git repo; I updated commit sha1. New commits:
c76a0a0  Better precision tracking in method is_square

comment:29 Changed 9 months ago by
 Status changed from needs_work to needs_review
comment:30 Changed 9 months ago by
 Commit changed from c76a0a0e98e973fe0aac237132155bba1a4f0c7d to dbd6aada155e7a3fb122d2a3284ce17d354935af
comment:31 Changed 9 months ago by
 Status changed from needs_review to needs_work
I found other bugs. I'm still working on this ticket...
comment:32 Changed 9 months ago by
 Commit changed from dbd6aada155e7a3fb122d2a3284ce17d354935af to fd786ba03c9cdd8dded7652867e6d2763169d0ba
Branch pushed to git repo; I updated commit sha1. New commits:
fd786ba  Fix bugs, clarify code and implement a better algorithm

Changed 9 months ago by
comment:33 Changed 9 months ago by
 Dependencies changed from #23218 to #23218, #25990
Finally, I've implemented a faster algorithm with better complexity with respect to p
.
I've also added doctests demonstrating that the computation of the n
th root works over various fields (including those having, or having almost, p
th or p^2
th roots of unity).
There are still failing doctests but they are due to the bug reported in #25990.
comment:34 Changed 8 months ago by
 Commit changed from fd786ba03c9cdd8dded7652867e6d2763169d0ba to 49d5c3e9758ca161a278da0818748fab5b8d3578
Branch pushed to git repo; I updated commit sha1. New commits:
efde687  Handle precision correctly in DefPolyConversion

9931917  Merge branch 'padic_extension_conversion' into t/12567/padic_nthroot

ff1ced3  Fix doctest

b4ed236  Handle precision even better

49d5c3e  Merge branch 'padic_extension_conversion' into t/12567/padic_nthroot

comment:35 Changed 8 months ago by
 Status changed from needs_work to needs_review
Now, all tests pass: the ticket is ready for review.
comment:36 Changed 8 months ago by
 Commit changed from 49d5c3e9758ca161a278da0818748fab5b8d3578 to 265720df550bab2910432bacbe9811e3078e123d
Branch pushed to git repo; I updated commit sha1. New commits:
265720d  Check that log(root of unity) is zero

comment:37 Changed 8 months ago by
Doc doesn't build (see patchbot).
Additionally EXAMPLES blocks in doc should end in :: not : I believe if the first thing after is code, (see primitive_root_of_unity and elsewhere).
comment:38 Changed 8 months ago by
 Commit changed from 265720df550bab2910432bacbe9811e3078e123d to e1cfa9daf47153f2322808e195bede6f42814fb7
Branch pushed to git repo; I updated commit sha1. New commits:
e1cfa9d  Fix doctest

comment:39 Changed 7 months ago by
 Commit changed from e1cfa9daf47153f2322808e195bede6f42814fb7 to 5790a670cc5d6814cab9d2a141b943323161a5bb
comment:40 Changed 7 months ago by
 Commit changed from 5790a670cc5d6814cab9d2a141b943323161a5bb to a53bf90d0ad12281a089deb7d669a8b9374fc970
Branch pushed to git repo; I updated commit sha1. New commits:
a53bf90  Merge branch 'develop' into t/12567/padic_nthroot

comment:41 Changed 7 months ago by
 Branch changed from u/caruso/padic_nthroot to u/roed/padic_nthroot
comment:42 Changed 7 months ago by
 Commit changed from a53bf90d0ad12281a089deb7d669a8b9374fc970 to 6216be01a3885f6c10eea14afe16ebde6859683d
 Status changed from needs_review to positive_review
comment:43 Changed 7 months ago by
 Branch changed from u/roed/padic_nthroot to 6216be01a3885f6c10eea14afe16ebde6859683d
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
allow extension() method to accept implementation and prec arguments
Fix integer_mod_ring extension method
Fix yet another bug in conversion from QpFP to QpCR
Fix yet another bug in conversion from QpFP to QpCR (try again)
Change ccmp to not shortcircuit
Merge branch 'u/roed/ramified_extensions_of_general_p_adic_rings_and_fields' of trac.sagemath.org:sage into t/23218/ramified_extensions_of_general_p_adic_rings_and_fields
Fix overflow issues
Merge branch 'u/caruso/ramified_extensions_of_general_p_adic_rings_and_fields' of git://trac.sagemath.org/sage into t/23218/general_extensions
Reduce further after remove
Add keyword reduce_relative in cremove