Opened 8 years ago

Closed 12 months ago

#12567 closed enhancement (fixed)

Implement p-adic n-th roots

Reported by: dequan Owned by: roed
Priority: major Milestone: sage-6.4
Component: padics Keywords: padics, n-th 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 p-adic n-th roots as a p-adic Sage Days project

Attachments (1)

12567-vs-23218.diff (31.8 KB) - added by caruso 14 months ago.

Download all attachments as: .zip

Change History (44)

comment:1 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:3 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:4 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:5 Changed 2 years ago by roed

  • Keywords sd87 added

comment:6 Changed 14 months ago by roed

  • Keywords padicIMA added
  • Priority changed from minor to major

comment:7 Changed 14 months ago by caruso

  • Branch set to u/caruso/padic_nthroot

comment:8 Changed 14 months ago by caruso

  • Authors changed from dequan, serickson, reinier to Xavier Caruso
  • Commit set to e639faebca801514e900f5e913b79003c5b02124

Last 10 new commits:

2d1a5c7allow extension() method to accept implementation and prec arguments
f34a01eFix integer_mod_ring extension method
98565aeFix yet another bug in conversion from QpFP to QpCR
344df3dFix yet another bug in conversion from QpFP to QpCR (try again)
dd5d0cdChange ccmp to not short-circuit
f87dad8Merge 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
8296e2cFix overflow issues
3de944aMerge branch 'u/caruso/ramified_extensions_of_general_p_adic_rings_and_fields' of git://trac.sagemath.org/sage into t/23218/general_extensions
e7a5b08Reduce further after remove
e639faeAdd keyword reduce_relative in cremove

comment:9 Changed 14 months ago by caruso

  • Cc roed saraedum dequan serickson reinier added
  • Dependencies set to #23218

I just wrote a generic implementation of p-adic nth root, working over any p-adic extension (unramified, totally ramified or mixed).

Doctests are coming soon...

comment:10 Changed 14 months ago by git

  • Commit changed from e639faebca801514e900f5e913b79003c5b02124 to 5a4bf734f4c6ff9481709424c29f54ed4b515b20

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

5a4bf73Implementation of p-adic nth root

comment:11 Changed 14 months ago by git

  • Commit changed from 5a4bf734f4c6ff9481709424c29f54ed4b515b20 to be503569b13f449375f6ab1daae94055b14e015c

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

be50356Added doctests

comment:12 Changed 14 months ago by caruso

  • Status changed from new to needs_review

comment:13 Changed 14 months ago by git

  • Commit changed from be503569b13f449375f6ab1daae94055b14e015c to d7c39b0d16419f75a1caf3b10c337e0d6c5b3d42

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

319f6d4Remove the debugging method _unit
d7c39b0Merge branch 't/23218/ramified_extensions_of_general_p_adic_rings_and_fields' into t/12567/padic_nthroot

comment:14 Changed 14 months ago by caruso

For ease of review, I attach the diff between this ticket and #23218

comment:15 Changed 14 months ago by roed

  • Branch changed from u/caruso/padic_nthroot to u/roed/padic_nthroot

comment:16 Changed 14 months ago by roed

  • Commit changed from d7c39b0d16419f75a1caf3b10c337e0d6c5b3d42 to 0324b667a00a264131f512111a7dbb6837fa1c98
  • Reviewers set to David Roe
  • Status changed from needs_review to positive_review

I made some minor changes and tests still pass. Positive review!


New commits:

477e000Fixing some typos and moving the expansion out of an inner loop
0324b66Fix a small bug in _pth_root and add some tests

comment:17 Changed 14 months ago by caruso

  • Branch changed from u/roed/padic_nthroot to u/caruso/padic_nthroot

comment:18 Changed 14 months ago by caruso

Perfect! I've just changed a bit the doctests you added in order to have a test for the case where p-1 divides e (for which the algorithm I've implemented has an extra step).

comment:19 Changed 14 months ago by git

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

1bf897fTest for the case for p-1 divides e

comment:20 Changed 14 months ago by caruso

  • Status changed from needs_review to positive_review

comment:21 Changed 14 months ago by roed

Great! I'll run the tests again.

comment:22 Changed 14 months ago by caruso

  • 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 14 months ago by roed

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 14 months ago by roed

This makes sense actually, since this field has no 8th root of unity.

comment:25 Changed 14 months ago by caruso

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 14 months ago by git

  • Commit changed from 1bf897fc0c685be9f415f3b5608352b1a067e11e to 2cef5e09732e863322ae457e06d96c0a614b3a3a

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

2cef5e0Consider conjugates when computing successive p-th roots

comment:27 Changed 14 months ago by caruso

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 14 months ago by git

  • Commit changed from 2cef5e09732e863322ae457e06d96c0a614b3a3a to c76a0a0e98e973fe0aac237132155bba1a4f0c7d

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

c76a0a0Better precision tracking in method is_square

comment:29 Changed 14 months ago by caruso

  • Status changed from needs_work to needs_review

comment:30 Changed 14 months ago by git

  • Commit changed from c76a0a0e98e973fe0aac237132155bba1a4f0c7d to dbd6aada155e7a3fb122d2a3284ce17d354935af

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

8099775Cache the result of _maximal_qth_root_of_unity
dbd6aadAdd the option "all=True" and several functionalities for roots of unity

comment:31 Changed 14 months ago by caruso

  • Status changed from needs_review to needs_work

I found other bugs. I'm still working on this ticket...

comment:32 Changed 14 months ago by git

  • Commit changed from dbd6aada155e7a3fb122d2a3284ce17d354935af to fd786ba03c9cdd8dded7652867e6d2763169d0ba

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

fd786baFix bugs, clarify code and implement a better algorithm

Changed 14 months ago by caruso

comment:33 Changed 14 months ago by caruso

  • 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 nth root works over various fields (including those having, or having almost, pth or p^2th roots of unity).

There are still failing doctests but they are due to the bug reported in #25990.

comment:34 Changed 13 months ago by git

  • Commit changed from fd786ba03c9cdd8dded7652867e6d2763169d0ba to 49d5c3e9758ca161a278da0818748fab5b8d3578

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

efde687Handle precision correctly in DefPolyConversion
9931917Merge branch 'padic_extension_conversion' into t/12567/padic_nthroot
ff1ced3Fix doctest
b4ed236Handle precision even better
49d5c3eMerge branch 'padic_extension_conversion' into t/12567/padic_nthroot

comment:35 Changed 13 months ago by caruso

  • Status changed from needs_work to needs_review

Now, all tests pass: the ticket is ready for review.

Last edited 13 months ago by caruso (previous) (diff)

comment:36 Changed 13 months ago by git

  • Commit changed from 49d5c3e9758ca161a278da0818748fab5b8d3578 to 265720df550bab2910432bacbe9811e3078e123d

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

265720dCheck that log(root of unity) is zero

comment:37 Changed 13 months ago by alexjbest

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 13 months ago by git

  • Commit changed from 265720df550bab2910432bacbe9811e3078e123d to e1cfa9daf47153f2322808e195bede6f42814fb7

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

e1cfa9dFix doctest

comment:39 Changed 12 months ago by git

  • Commit changed from e1cfa9daf47153f2322808e195bede6f42814fb7 to 5790a670cc5d6814cab9d2a141b943323161a5bb

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

c3f9824Merge branch 'develop' into t/12567/padic_nthroot
5790a67Move cache of _inverse_pth_root to the parent

comment:40 Changed 12 months ago by git

  • Commit changed from 5790a670cc5d6814cab9d2a141b943323161a5bb to a53bf90d0ad12281a089deb7d669a8b9374fc970

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

a53bf90Merge branch 'develop' into t/12567/padic_nthroot

comment:41 Changed 12 months ago by roed

  • Branch changed from u/caruso/padic_nthroot to u/roed/padic_nthroot

comment:42 Changed 12 months ago by roed

  • Commit changed from a53bf90d0ad12281a089deb7d669a8b9374fc970 to 6216be01a3885f6c10eea14afe16ebde6859683d
  • Status changed from needs_review to positive_review

Looks good; just ran make ptestlong.


New commits:

3c1b194Merge branch 'develop' into t/12567/padic_nthroot
0fe1ed4A few fixes
16ab40dMerge branch 'u/caruso/padic_nthroot' of git://trac.sagemath.org/sage into t/12567/padic_nthroot
6216be0Small improvement to nth root

comment:43 Changed 12 months ago by vbraun

  • Branch changed from u/roed/padic_nthroot to 6216be01a3885f6c10eea14afe16ebde6859683d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.