Opened 6 years ago

Closed 21 months ago

Last modified 9 months ago

#14825 closed enhancement (fixed)

Iterators for p-adic expansions, polynomial representations of padic elements

Reported by: caruso Owned by: roed
Priority: major Milestone: sage-6.4
Component: padics Keywords: sd87, days88, polynomial representation
Cc: saraedum Merged in:
Authors: Xavier Caruso, David Roe, Julian Rüth Reviewers: Julian Rüth, David Roe
Report Upstream: N/A Work issues: plugin error
Branch: 04a1579 (Commits) Commit:
Dependencies: #20310 Stopgaps:

Description (last modified by saraedum)

This method makes a few additions/changes to p-adics.

  • If K is an extension of Z_p whose generator is a, we add a method polynomial which takes as input an element x in K and outputs a polynomial P with coefficients in Z_p such that P(a) = x.
sage: K.<a> = Qq(5^3)
sage: a.polynomial()
(1 + O(5^20))*x + (O(5^20))
  • Rename the list() method to expansion() and have it return a custom iterable instead of a list
  • Rename the teichmuller_list() method to teichmuller_expansion() and have it return a custom iterable instead of a list
  • Add an optional argument n to expansion() and teichmuller_expansion(), providing a single digit in the p-adic expansion.
  • Fix inconsistencies in teichmuller_expansion() for different precision types
  • Deprecate padded_list since this functionality is available either from expansion or from Integer.digits using the padto keyword.
  • Copy sections of inclusions ZZ->Zp when they’re used within the coercion system

There are followup tickets at #23827, #26406.

Attachments (2)

trac_14825_polynomial_representation_padics.patch (4.7 KB) - added by caruso 6 years ago.
14825_over_20310.diff (95.4 KB) - added by roed 23 months ago.
Diff against 20310

Download all attachments as: .zip

Change History (67)

comment:1 Changed 6 years ago by caruso

  • Status changed from new to needs_review

comment:2 Changed 5 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 rws

  • Status changed from needs_review to needs_work

Patch does not merge. Please rebase.

comment:5 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:6 Changed 2 years ago by roed

  • Branch set to u/roed/polynomial_representation_of_a_padic_number

comment:7 Changed 2 years ago by git

  • Commit set to 4088f9b3fa1033e77b3edf935c3608ebc806d5e3

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

4088f9bFixing doctest errors, changes to ZZ_pX p-adic types

comment:8 Changed 2 years ago by roed

  • Cc saraedum added

I got a little carried away with some other changes. In particular, I renamed and deprecated list and teichmuller list. There are still two failing doctests, but I'm going to be offline for a week or so and wanted to push my changes.

comment:9 Changed 2 years ago by git

  • Commit changed from 4088f9b3fa1033e77b3edf935c3608ebc806d5e3 to 24ee4fff0f114df6cc104a95b81673477c1294b0

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

24ee4ffFixing doctest errors due to switching from list to expansion

comment:10 Changed 2 years ago by git

  • Commit changed from 24ee4fff0f114df6cc104a95b81673477c1294b0 to cbfeb3429c52b82163b7abc747abba80d9b2f138

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

cbfeb34Making behavior of teichmuller_expansion uniform across precision types, adding doctests

comment:11 Changed 2 years ago by git

  • Commit changed from cbfeb3429c52b82163b7abc747abba80d9b2f138 to f5e24404b970f6b4e674643a10f442c9257e0a63

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

f5e2440Fix 'x'->'var' typo in some docstrings, add polynomial method to ntl p-adic types

comment:12 Changed 2 years ago by git

  • Commit changed from f5e24404b970f6b4e674643a10f442c9257e0a63 to 779ddb8fa159e88e3a53ba7d3fe786fed815afc5

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

779ddb8Remove added NOTES: in CR_template

comment:13 Changed 2 years ago by roed

  • Authors changed from Xavier Caruso to Xavier Caruso, David Roe
  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Summary changed from Polynomial representation of a padic number to Polynomial representations of padic elements, renaming list and teichmuller_list

comment:14 Changed 2 years ago by roed

By the way, I ran all tests and they pass.

comment:15 Changed 2 years ago by saraedum

  • Branch changed from u/roed/polynomial_representation_of_a_padic_number to u/saraedum/polynomial_representation_of_a_padic_number

comment:16 Changed 2 years ago by saraedum

  • Commit changed from 779ddb8fa159e88e3a53ba7d3fe786fed815afc5 to 985a23a4332d6d8b6ccf7f104f87b634903e3b60

David, feel free to set this to positive review. My only question would be whether polynomial should be added to API.pxi?


New commits:

985a23aamend documentation of ccoefficients

comment:17 Changed 2 years ago by saraedum

  • Status changed from needs_review to positive_review

Misunderstood something about polynomial. Never mind.

comment:18 Changed 2 years ago by roed

  • Branch changed from u/saraedum/polynomial_representation_of_a_padic_number to u/roed/polynomial_representation_of_a_padic_number

comment:19 Changed 2 years ago by roed

  • Commit changed from 985a23a4332d6d8b6ccf7f104f87b634903e3b60 to 3cddbdd8e66606f5d4f8c225316a2b3285142181
  • Status changed from positive_review to needs_review

New commits:

3cddbddFix doctests

comment:20 Changed 2 years ago by saraedum

  • Reviewers set to Julian Rüth
  • Status changed from needs_review to positive_review

comment:21 Changed 2 years ago by caruso

  • Status changed from positive_review to needs_work
    sage: K.<a> = Qq(7^3,4)
    sage: b = (a+1)/7
    sage: b.polynomial()
    sig_error() without sig_on()
    <BOUM>
Last edited 2 years ago by caruso (previous) (diff)

comment:22 Changed 23 months ago by git

  • Commit changed from 3cddbdd8e66606f5d4f8c225316a2b3285142181 to 1ec63e7cf496c866fb7fd7ede7c7310844aac877

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

1ec63e7Merge branch 'u/roed/polynomial_representation_of_a_padic_number' of git://trac.sagemath.org/sage into t/14825/polynomial_representation_of_a_padic_number

comment:23 Changed 23 months ago by git

  • Commit changed from 1ec63e7cf496c866fb7fd7ede7c7310844aac877 to b9c2fe42e7e93e64a03dbe13bd792988f38fa735

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

7f87069Fix segfault
b9c2fe4Fix pickling of sections for p-adic coercions

comment:24 Changed 23 months ago by roed

  • Status changed from needs_work to needs_review

I fixed the segfault, and tests pass.

comment:25 Changed 23 months ago by git

  • Commit changed from b9c2fe42e7e93e64a03dbe13bd792988f38fa735 to 1eeb367a038d5752ff793ccb71094af497d75b37

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

85019ccFix errors due to moving digits code earlier in the change function
39043f1Merge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/20310/change_precision
6e2495fMerge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/20310/change_precision
7428353minor docstring fixes
99dccf6Merge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/20310/change_precision
ef4ed33Fix SEEALSO:
1754b44Fix exact=True errors in the right branch
3142701Merge branch 'u/roed/change_precision' of git://trac.sagemath.org/sage into t/20310/change_precision
138d939Fix string representation doctest from #22103
1eeb367Merge branch 't/20310/change_precision' into t/14825/polynomial_representation_of_a_padic_number

comment:26 Changed 23 months ago by roed

  • Dependencies set to #20310

Adding a dependency for merging purposes.

Changed 23 months ago by roed

Diff against 20310

comment:27 Changed 23 months ago by roed

For ease of reviewing, I've attached a diff against #20310.

comment:28 Changed 23 months ago by saraedum

  • Branch changed from u/roed/polynomial_representation_of_a_padic_number to u/saraedum/polynomial_representation_of_a_padic_number

comment:29 follow-up: Changed 23 months ago by saraedum

  • Branch changed from u/saraedum/polynomial_representation_of_a_padic_number to u/roed/polynomial_representation_of_a_padic_number
  • Status changed from needs_review to needs_info

Ok. Looks good. I fixed a few very minor documentation issues. I also wrote a unit test for expansion and it fails for some instances. This is likely only a error in the documentation:

sage: K=Qp(2)
sage: K(2).expansion()
[1]
sage: K(2).expansion(n=0)
0 # should return 1?
sage: K(2).expansion(n=1)
1 # sould return 0?

That's at least how I understand the expansion() docstring. Is the current behaviour intended?

comment:30 follow-up: Changed 23 months ago by saraedum

Here is something that the unit test found that seems to be a bug:

sage: ZpCA(2)(2).expansion(lift_mode='teichmuller')
[1 + O(2^19)]
sage: ZpFM(2)(2).expansion(lift_mode='teichmuller')
[1 + O(2^20)]

comment:31 Changed 23 months ago by saraedum

  • Work issues set to failing doctests

comment:32 Changed 23 months ago by saraedum

  • Authors changed from Xavier Caruso, David Roe to Xavier Caruso, David Roe, Julian Rüth

comment:33 Changed 23 months ago by saraedum

  • Branch changed from u/roed/polynomial_representation_of_a_padic_number to u/saraedum/polynomial_representation_of_a_padic_number

comment:34 in reply to: ↑ 30 ; follow-up: Changed 23 months ago by roed

  • Commit changed from 1eeb367a038d5752ff793ccb71094af497d75b37 to 6732d3814afa9650b29356ffa2b2d1f225e0b343

Replying to saraedum:

Here is something that the unit test found that seems to be a bug:

sage: ZpCA(2)(2).expansion(lift_mode='teichmuller')
[1 + O(2^19)]
sage: ZpFM(2)(2).expansion(lift_mode='teichmuller')
[1 + O(2^20)]

Why is this a bug?


New commits:

1e07709fix typo
ec9f8e6fix typo
dfa2a28fix typo
1bb288fprotect LaTeX commands
054e5d6clarify where _list_zero comes from
0b7fd02default docstring layout
def3897replace p with pi and clarify meaning of expansion
99c40d6add unit test for expansion
6732d38coefficients might be lists in the maximal unramified subextension

comment:35 in reply to: ↑ 29 ; follow-up: Changed 23 months ago by roed

Replying to saraedum:

Ok. Looks good. I fixed a few very minor documentation issues. I also wrote a unit test for expansion and it fails for some instances. This is likely only a error in the documentation:

sage: K=Qp(2)
sage: K(2).expansion()
[1]
sage: K(2).expansion(n=0)
0 # should return 1?
sage: K(2).expansion(n=1)
1 # should return 0?

That's at least how I understand the expansion() docstring. Is the current behaviour intended?

Yeah, this is intended. When you pass in a value for n it gives you the coefficient of pn, rather than the nth term in the list. I've updated the test (but haven't pushed yet).

comment:36 follow-up: Changed 23 months ago by roed

So, your test causes padic_expansion_generic.py to time out, since it's running with precision cap 10000. One way to improve the situation might be to change expansion to return an iterator (and then change _test_expansion to top out at testing at most 40 terms or something). This ticket might be a good time to do this, since we're already deprecating list; it's not hard to change the behavior of expansion at the same time (which we're in fact doing by adding the n keyword).

What do you think?

comment:37 Changed 23 months ago by roed

  • Branch changed from u/saraedum/polynomial_representation_of_a_padic_number to u/roed/polynomial_representation_of_a_padic_number

comment:38 in reply to: ↑ 35 Changed 23 months ago by saraedum

  • Commit changed from 6732d3814afa9650b29356ffa2b2d1f225e0b343 to 40737f6ae9eafcec67129892b5c5df591023ab85

Replying to roed:

Replying to saraedum:

Ok. Looks good. I fixed a few very minor documentation issues. I also wrote a unit test for expansion and it fails for some instances. This is likely only a error in the documentation:

sage: K=Qp(2)
sage: K(2).expansion()
[1]
sage: K(2).expansion(n=0)
0 # should return 1?
sage: K(2).expansion(n=1)
1 # should return 0?

That's at least how I understand the expansion() docstring. Is the current behaviour intended?

Yeah, this is intended. When you pass in a value for n it gives you the coefficient of pn, rather than the nth term in the list. I've updated the test (but haven't pushed yet).

Ok. Then the documentation should be more explicit. I thought it's just a shortcut to get the n-th element in the list.


New commits:

0d46568Merge branch 'develop' into t/14825/polynomial_representation_of_a_padic_number
acc606aMerge branch 'u/saraedum/polynomial_representation_of_a_padic_number' of git://trac.sagemath.org/sage into t/14825/polynomial_representation_of_a_padic_number
40737f6Fix some of the errors in _test_expansion
Last edited 23 months ago by saraedum (previous) (diff)

comment:39 in reply to: ↑ 36 Changed 23 months ago by saraedum

Replying to roed:

So, your test causes padic_expansion_generic.py to time out, since it's running with precision cap 10000. One way to improve the situation might be to change expansion to return an iterator (and then change _test_expansion to top out at testing at most 40 terms or something). This ticket might be a good time to do this, since we're already deprecating list; it's not hard to change the behavior of expansion at the same time (which we're in fact doing by adding the n keyword).

What do you think?

Sounds good.

comment:40 in reply to: ↑ 34 Changed 23 months ago by saraedum

Replying to roed:

Replying to saraedum:

Here is something that the unit test found that seems to be a bug:

sage: ZpCA(2)(2).expansion(lift_mode='teichmuller')
[1 + O(2^19)]
sage: ZpFM(2)(2).expansion(lift_mode='teichmuller')
[1 + O(2^20)]

Why is this a bug?

The docstring says that (since this is not a field) summing these with powers of pi should return the original element, i.e., (1 + O(2^19))*2^0 == 2.

comment:41 Changed 22 months ago by git

  • Commit changed from 40737f6ae9eafcec67129892b5c5df591023ab85 to 6efed0be21d740b73063e0c606a95b0cd73f3034

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

6efed0bMerge branch 'u/roed/polynomial_representation_of_a_padic_number' of git://trac.sagemath.org/sage into t/14825/polynomial_representation_of_a_padic_number

comment:42 Changed 22 months ago by roed

  • Keywords sd87 days88 added
  • Status changed from needs_info to needs_work

comment:43 Changed 22 months ago by git

  • Commit changed from 6efed0be21d740b73063e0c606a95b0cd73f3034 to f80ca7607e136ba5989ff30318f7c7a681317081

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

f80ca76Working on adding iterators

comment:44 Changed 22 months ago by git

  • Commit changed from f80ca7607e136ba5989ff30318f7c7a681317081 to 030251c4e8ce05066a7fcd6618078f6d8b537f14

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

030251cRestructing of p-adic expansions

comment:45 Changed 22 months ago by git

  • Commit changed from 030251c4e8ce05066a7fcd6618078f6d8b537f14 to 3c912f948e9282a780e34ddfc2ddf4ae72f69678

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

3c912f9Adding documentation and making small changes to names

comment:46 Changed 22 months ago by git

  • Commit changed from 3c912f948e9282a780e34ddfc2ddf4ae72f69678 to 7e037b337e3d5057fb0734e81030396fe814d0d4

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

7e037b3cleaning up a couple of hyperelliptic curve changes

comment:47 Changed 22 months ago by roed

  • Status changed from needs_work to needs_review

comment:48 Changed 22 months ago by git

  • Commit changed from 7e037b337e3d5057fb0734e81030396fe814d0d4 to acf6b666b144d0b98b16383fa47cfa9133019bd8

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

acf6b66Fix implementation in linear_code that used padded_list

comment:49 Changed 22 months ago by roed

  • Description modified (diff)
  • Summary changed from Polynomial representations of padic elements, renaming list and teichmuller_list to Iterators for p-adic expansions, polynomial representations of padic elements

comment:50 Changed 22 months ago by saraedum

  • Work issues changed from failing doctests to plugin failures

comment:51 Changed 22 months ago by saraedum

  • Status changed from needs_review to needs_work

comment:52 follow-up: Changed 22 months ago by saraedum

  • Work issues changed from plugin failures to plugin failures, patchbot happy ⇒ positive_review

This looks very good. Is there a follow up ticket to implement the new __getitem__?

comment:53 Changed 22 months ago by git

  • Commit changed from acf6b666b144d0b98b16383fa47cfa9133019bd8 to d7d5fb612c45ed3e51724f3834d194415cc0a122

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

1f8aa2eFix NOTES
5cf279bFix izip
d7d5fb6Fixing documentation

comment:54 in reply to: ↑ 52 Changed 22 months ago by roed

Replying to saraedum:

This looks very good. Is there a follow up ticket to implement the new __getitem__?

Followup is now #23827

comment:55 Changed 22 months ago by roed

  • Status changed from needs_work to needs_review
  • Work issues plugin failures, patchbot happy ⇒ positive_review deleted

Patchbot complains about .. SEEALSO::, but I'm confused: this is the correct syntax described both in the developer guide and the patchbot source code! Am I missing something?

The doctest errors are the normal glpk issues, which aren't due to this ticket.

comment:56 Changed 21 months ago by saraedum

  • Work issues set to merge conflicts, plugin error

comment:57 Changed 21 months ago by saraedum

  • Branch changed from u/roed/polynomial_representation_of_a_padic_number to u/saraedum/polynomial_representation_of_a_padic_number

comment:58 Changed 21 months ago by saraedum

  • Commit changed from d7d5fb612c45ed3e51724f3834d194415cc0a122 to e51c0f50660a4fdb06071dba0551f5252984b171
  • Work issues changed from merge conflicts, plugin error to plugin error

New commits:

46f9caeMerge branch 'develop' into t/14825/polynomial_representation_of_a_padic_number
e51c0f5Merge branch 'u/roed/polynomial_representation_of_a_padic_number' of git://trac.sagemath.org/sage into t/14825/polynomial_representation_of_a_padic_number

comment:59 Changed 21 months ago by git

  • Commit changed from e51c0f50660a4fdb06071dba0551f5252984b171 to b6457b1d48311d45bee32228bf989391b9754d88

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

b6457b1Moving SEEALSO to the end of the docstring

comment:60 Changed 21 months ago by git

  • Commit changed from b6457b1d48311d45bee32228bf989391b9754d88 to b81b7223f120e4714163c79cab851f62eccf4e19

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

b81b722Remove use of depraceted list()

comment:61 Changed 21 months ago by roed

  • Branch changed from u/saraedum/polynomial_representation_of_a_padic_number to u/roed/polynomial_representation_of_a_padic_number

comment:62 Changed 21 months ago by roed

  • Commit changed from b81b7223f120e4714163c79cab851f62eccf4e19 to 04a1579131d64cdc63ecf1babcba2350dec6497c
  • Reviewers changed from Julian Rüth to Julian Rüth, David Roe
  • Status changed from needs_review to positive_review

I'm happy with Julian's changes, and the patchbot is green. Positive review!


New commits:

04a1579Fix NOTES blocks

comment:63 Changed 21 months ago by vbraun

  • Branch changed from u/roed/polynomial_representation_of_a_padic_number to 04a1579131d64cdc63ecf1babcba2350dec6497c
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:64 Changed 9 months ago by saraedum

  • Commit 04a1579131d64cdc63ecf1babcba2350dec6497c deleted
  • Description modified (diff)

comment:65 Changed 9 months ago by saraedum

  • Description modified (diff)
Note: See TracTickets for help on using tickets.