Opened 10 years ago
Closed 6 years ago
#9457 closed defect (fixed)
power series equality fails when trailing coefficients are zero
Reported by:  niles  Owned by:  malb 

Priority:  major  Milestone:  sage6.2 
Component:  commutative algebra  Keywords:  
Cc:  SimonKing, wuthrich  Merged in:  
Authors:  Niles Johnson  Reviewers:  Peter Bruin 
Report Upstream:  N/A  Work issues:  
Branch:  9c0b17f (Commits)  Commit:  9c0b17f8ca77ce881b7b96a7a2b06ef8b856a0d1 
Dependencies:  #8198  Stopgaps:  #15748 
Description (last modified by )
Comparison of power series uses list
instead of padded_list
. This drops trailing zeros, and means that power series equality is buggy:
sage: A.<t> = PowerSeriesRing(ZZ) sage: g = t + t^3 + t^5 + O(t^6); g t + t^3 + t^5 + O(t^6) sage: g == t + O(t^3) # should be True False sage: [g == g.add_bigoh(i) for i in range(7)] # these should all be True [True, False, True, False, True, False, True] sage: g.add_bigoh(3).list() # drops trailing zero [0, 1] sage: g.add_bigoh(3).padded_list() [0, 1, 0]
Attachments (3)
Change History (46)
comment:1 Changed 10 years ago by
 Status changed from new to needs_review
comment:2 Changed 10 years ago by
 Description modified (diff)
Changed 10 years ago by
comment:3 Changed 10 years ago by
Replaced padded_list() with padded_list(prec) because of
sage: A.<t> = PowerSeriesRing(ZZ) sage: f = t + t^2 + O(t^10) sage: f == f.truncate() False sage: f.truncate().padded_list() [0, 1, 1]
This brought up a problem with padded_list(infinity), which is also now patched
sage: A.<t> = PowerSeriesRing(ZZ) sage: f = t + t^2 + O(t**10) sage: f.padded_list() [0, 1, 1, 0, 0, 0, 0, 0, 0, 0] sage: f.padded_list(infinity) Traceback (most recent call last): ... TypeError: unsupported operand parent(s) for '*': '<type 'list'>' and 'The Infinity Ring'
comment:4 followup: ↓ 5 Changed 10 years ago by
 Description modified (diff)
comment:5 in reply to: ↑ 4 Changed 10 years ago by
Replying to niles: Code in the previous description made no sense; my apologies. Here's what we have after applying the patch:
sage: A.<t> = PowerSeriesRing(ZZ) sage: g = t + t^3 + t^5 + O(t^6); g t + t^3 + t^5 + O(t^6) sage: [g == g.add_bigoh(i) for i in range(7)] [True, True, True, True, True, True, True] sage: f = t + t^2 + O(t^10) sage: f == f.truncate() True sage: f.padded_list() [0, 1, 1, 0, 0, 0, 0, 0, 0, 0] sage: f.padded_list(infinity) [0, 1, 1]
comment:6 Changed 10 years ago by
 Status changed from needs_review to needs_work
 Work issues set to Mention ticket number in commit messages
Hi!
The patches cleanly apply, and sage b
works.
The original problem is fixed:
sage: A.<t> = PowerSeriesRing(ZZ) sage: g = t + t^3 + t^5 + O(t^6); g t + t^3 + t^5 + O(t^6) sage: sage: [g == g.add_bigoh(i) for i in range(7)] [True, True, True, True, True, True, True]
The code looks good to me. I am now running doctests.
One minor problem: Please mention the ticket number in the commit messages. So, please add something like "#9457: " to the commit messages of both patches
comment:7 Changed 10 years ago by
 Work issues changed from Mention ticket number in commit messages to Fix bug in sage.schemes.elliptic_curves.sha_tate.Sha.an_padic; mention ticket number in commit messages.
First, I applied the patches from #9443 and found that all doctests pass. Then, I applied the tickets from here, and got one doctest failure:
sage t long devel/sage/sage/schemes/elliptic_curves/sha_tate.py Saturation index bound = 265 WARNING: saturation at primes p > 100 will not be done; points may be unsaturated at primes between 100 and index bound Failed to saturate MW basis at primes [ ] *** saturation possibly incomplete at primes [ ] ********************************************************************** File "/home/king/SAGE/sage4.4.2/devel/sagemain/sage/schemes/elliptic_curves/sha_tate.py", line 393: sage: EllipticCurve('53a1').sha().an_padic(5) # rank 1 (long time) Exception raised: Traceback (most recent call last): File "/home/king/SAGE/sage4.4.2/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/home/king/SAGE/sage4.4.2/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/home/king/SAGE/sage4.4.2/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_4[13]>", line 1, in <module> EllipticCurve('53a1').sha().an_padic(Integer(5)) # rank 1 (long time)###line 393: sage: EllipticCurve('53a1').sha().an_padic(5) # rank 1 (long time) File "/home/king/SAGE/sage4.4.2/local/lib/python/sitepackages/sage/schemes/elliptic_curves/sha_tate.py", line 567, in an_padic raise RuntimeError, "There must be a bug in the supersingular routines for the padic BSD." RuntimeError: There must be a bug in the supersingular routines for the padic BSD.
So, there will be some bug hunt needed.
comment:8 Changed 10 years ago by
Here's the problem.
Without the patch:
sage: R.<T> = QQ.completion(5,5)[[]] sage: R Power Series Ring in T over 5adic Field with capped relative precision 5 sage: O(T^2) == 0 False
With the patch:
sage: R.<T> = QQ.completion(5,5)[[]] sage: R Power Series Ring in T over 5adic Field with capped relative precision 5 sage: O(T^2) == 0 True
I guess that the second answer is correct. Unfortunately, Sha.an_padic relies on the wrong answer.
comment:9 followup: ↓ 10 Changed 10 years ago by
Thanks, but I'm not sure I can tell how to fix this . . . I see in the code for Sha.an_padic
the following lines:
# check consistency (the first two are only here to avoid a bug in the padic Lseries # (namely the coefficients of zerorelative precision are treated as zero) if shan0 != 0 and shan1 != 0 and shan0  shan1 != 0: raise RuntimeError, "There must be a bug in the supersingular routines for the padic BSD."
I suppose this is part of the problem but I don't see how to fix it . . . the two variables shan0
and shan1
are printed in the verbose output as "the two values for Sha"; the value of shan1
is different depending on whether or not the patch is applied, but I have no idea which value is correct:
Without the patch:
sage: set_verbose(1) sage: EllipticCurve('53a1').sha().an_padic(5) ... verbose 1 (316: sha_tate.py, an_padic) ...putting things together verbose 1 (316: sha_tate.py, an_padic) the two values for Sha : [1 + O(5), 0] 1 + O(5)
With the patch:
sage: set_verbose(1) sage: EllipticCurve('53a1').sha().an_padic(5) ... verbose 1 (316: sha_tate.py, an_padic) ...putting things together verbose 1 (316: sha_tate.py, an_padic) the two values for Sha : [1 + O(5), 4 + O(5)]  Traceback (most recent call last) ... RuntimeError: There must be a bug in the supersingular routines for the padic BSD.
Note that simply removing the conditions shan0 != 0 and shan1 != 0
(as implied by the inline comment) does not resolve the problem, since shan0 != shan1
is True
with the patch. The values of shan0
and shan1
are computed by the function pAdicLseriesSupersingular.Dp_valued_series
, which gives different output with and without the patch; again I have no idea which is correct.
Without the patch:
sage: E = EllipticCurve('53a1') sage: Et, D = E.minimal_quadratic_twist() sage: lp = Et.padic_lseries(5) sage: lps = lp.Dp_valued_series(4,quadratic_twist=D, prec=4) sage: lps (O(5^4) + (3 + O(5))*T + O(5)*T^2 + (4 + O(5))*T^3 + O(T^4), O(T^4))
With the patch:
sage: E = EllipticCurve('53a1') sage: Et, D = E.minimal_quadratic_twist() sage: lp = Et.padic_lseries(5) sage: lps = lp.Dp_valued_series(4,quadratic_twist=D, prec=4) sage: lps (O(5^4) + (3 + O(5))*T + O(5)*T^2 + (4 + O(5))*T^3 + O(T^4), O(5^5) + (4*5 + O(5^2))*T + O(5^2)*T^2 + (2*5 + O(5^2))*T^3 + O(T^4))
Note that every line of pAdicLseriesSupersingular.Dp_valued_series
gives the same output with or without the patch, except for the very last one, which computes lpv*eps.transpose()
where (with or without the patch)
lpv = (O(5^3) + (2*5^1 + O(5^0))*T + O(5^0)*T^2 + (5^1 + O(5^0))*T^3 + O(T^4), O(T^4))
and
eps.transpose() = [ 5/9 25/18] [5/18 5/9]
Before I try to chase this further, I think we should try to determine whether the patch is causing Dp_valued_series
to give the wrong answer, or whether the conditions on shan0
and shan1
should be changed. Ideas? If I've missed the point of your previous comment, could you explain how you determined that was the problem?
p.s. I haven't forgotten about fixing the commit messages; I'll do it after this is sorted out.
comment:10 in reply to: ↑ 9 ; followups: ↓ 11 ↓ 12 Changed 10 years ago by
Hi niles!
Replying to niles:
Thanks, but I'm not sure I can tell how to fix this . . .
At least your bug hunting was much deeper than mine.
Before I try to chase this further, I think we should try to determine whether the patch is causing
Dp_valued_series
to give the wrong answer, or whether the conditions onshan0
andshan1
should be changed.
Probably Dp_valued_series
, since the patch changes it, as you found out. But I am no expert for elliptic curves.
Ideas? If I've missed the point of your previous comment, could you explain how you determined that was the problem?
I inserted some print statements into an_padic, I don't recall exactly where. And it told me that just before the error occured, O(T^2)
occured and was tested for being zero. As this is something that the patch changed, I conluded that there is a problem (but perhaps not the only problem).
comment:11 in reply to: ↑ 10 Changed 10 years ago by
Hi Simon, thanks for the quick reply :)
Replying to SimonKing:
Probably
Dp_valued_series
, since the patch changes it, as you found out. But I am no expert for elliptic curves.
That's my guess too; I'll write an email to sagedevel and see if someone can help
comment:12 in reply to: ↑ 10 ; followup: ↓ 13 Changed 10 years ago by
 Cc SimonKing added
Replying to SimonKing:
Hi Simon,
I believe I have identified the problem; I think it is a problem with negative valuation for padics. First, here is what Dp_valued_series
does:
With or without the patch, we have
sage: import sage.matrix.all as matrix sage: p = 5 sage: prec = 2 sage: E = EllipticCurve('53a1') sage: L = E.padic_lseries(5) sage: lps = L.series(4) sage: R = lps.base_ring().base_ring() sage: QpT, T = PowerSeriesRing(R,'T',2).objgen() sage: G = QpT([lps[n][0] for n in range(0,lps.prec())], prec) sage: H = QpT([lps[n][1] for n in range(0,lps.prec())], prec) sage: phi = matrix.matrix([[0,1/p],[1,E.ap(p)/p]]) sage: lpv = vector([G + (E.ap(p))*H ,  R(p) * H ]) sage: eps = (1phi)**(2) sage: lpv (O(5^3) + (2*5^1 + O(5^0))*T + O(T^2), O(T^2)) sage: eps.transpose() [ 5/9 25/18] [5/18 5/9]
Now Dp_valued_series
ends by returning lpv*eps.transpose()
.
Without the patch:
sage: lpv*eps.transpose() (O(5^4) + (3 + O(5))*T + O(T^2), O(T^2))
And with the patch:
sage: lpv*eps.transpose() (O(5^4) + (3 + O(5))*T + O(T^2), O(5^5) + (4*5 + O(5^2))*T + O(T^2))
I had thought the withpatch answer was clearly right, until I tried the following (without the patch):
sage: a = vector([O(5^3) + (R(2/5).add_bigoh(0))*T + O(T^2), O(T^2)]) sage: M = matrix.matrix([[ 0, 1],[0, 1]]); M [0 1] [0 1] sage: a (O(5^3) + (2*5^1 + O(5^0))*T + O(T^2), O(T^2)) sage: lpv (O(5^3) + (2*5^1 + O(5^0))*T + O(T^2), O(T^2)) sage: a*M (0, O(5^3) + (2*5^1 + O(5^0))*T + O(T^2)) sage: lpv*M (0, O(5^3) + (2*5^1 + O(5^0))*T + O(T^2)) sage: M = matrix.matrix([[ 0, 5],[0, 1]]) sage: a*M (0, O(5^4) + (2 + O(5))*T + O(T^2)) sage: lpv*M (0, O(T^2))
Now note the way lpv[1]
is constructed: pull certain coefficients from lps
and make a power series (of precision 2) in QpT
with them. Here is the list of coefficients for H
:
sage: [lps[n][1] for n in range(0,lps.prec())] [O(5^2), O(5^1), O(5^1), O(5^1), O(5^1)] sage: H O(T^2)
So the O(T^2)
in lpv[1]
should really be O(5^2) + O(5^1)*T + O(T^2)
, and this explains why lpv*M
really should be (0, O(T^2))
(when M has a 5 in the upperright entry).
Here is a more direct test that passing to the power series ring over 5adic field does not remember negative precision of 0 (this is without the patch):
sage: R(0).add_bigoh(1) O(5^1) sage: QpT(R(0).add_bigoh(1)) 0 sage: R(0).add_bigoh(1).precision_absolute() 1 sage: QpT(R(0).add_bigoh(1))[0].precision_absolute() +Infinity sage: QpT(R(1/25).add_bigoh(1)) 5^2 + O(5^1) sage: QpT(R(1/25).add_bigoh(1))[0].precision_absolute() 1
I believe the correct arithmetic should be as follows:
(O(5^3) + (2*5^1 + O(5^0))*T + O(T^2), O(5^2) + O(5^1)*T + O(T^2))* [ 5/9 25/18] [5/18 5/9]
should be
(O(5^3) + O(5^0)*T + O(T^2), O(5^3) + O(5^0)*T + O(T^2))
Does this seem right? If this were the output of Dp_valued_series
, then EllipticCurve('53a1').sha().an_padic(5)
would increase the precision of Dp_valued_series
from 2 to 3 and run it again; I tested this, and with this precision EllipticCurve('53a1').sha().an_padic(5)
succeeds (with the patch applied!) and gives the expected answer.
So I believe the problem is a bug with power series over padics, rather than with this patch or with the elliptic curves code. Does this seem right to you? If so, one possible route at this stage is to modify the an_padic
code so that rather than throwing the error it first runs another loop with additional precision, and then submit a separate trac ticket for the padic problem. This is sort of dodging the issue, but helps keep the individual bugs separated.
comment:13 in reply to: ↑ 12 ; followup: ↓ 14 Changed 10 years ago by
Replying to niles:
So the
O(T^2)
inlpv[1]
should really beO(5^2) + O(5^1)*T + O(T^2)
, and this explains whylpv*M
really should be(0, O(T^2))
(when M has a 5 in the upperright entry).
oops, lpv[1]
is (R(p)) * H
, so I guess it should be O(5^3) + O(5^0)*T + O(T^2)
and the arithmetic is:
(O(5^3) + (2*5^1 + O(5^0))*T + O(T^2), O(5^3) + O(5^0)*T + O(T^2))* [ 5/9 25/18] [5/18 5/9]
should be
(O(5^4) + (3 + O(5))*T + O(T^2), O(5^4) + O(5)*T + O(T^2))
which will cause an_padic
to still throw the error :(
In any case, computing with a higher precision does give the right answer with or without the patch. I noticed there is an optional argument for this:
sage: set_verbose(1) sage: EllipticCurve('53a1').sha().an_padic(5, prec=5) ... verbose 1 (316: sha_tate.py, an_padic) the algebraic leading terms : (3 + 5 + 2*5^3 + 3*5^4 + 3*5^6 + 4*5^7 + 2*5^8 + 5^10 + 4*5^11 + 4*5^12 + 5^13 + 3*5^15 + 4*5^16 + 4*5^17 + 3*5^18 + 4*5^19 + O(5^20), 5 + 5^2 + 3*5^3 + 4*5^4 + 5^5 + 2*5^6 + 3*5^7 + 2*5^8 + 4*5^9 + 2*5^10 + 4*5^12 + 3*5^13 + 3*5^14 + 4*5^15 + 3*5^16 + 2*5^17 + 3*5^18 + 5^19 + O(5^20)) verbose 1 (316: sha_tate.py, an_padic) ...computing the padic Lseries verbose 1 (316: sha_tate.py, an_padic) r = 1 verbose 1 (881: padic_lseries.py, series) using padic precision of 5 verbose 1 (881: padic_lseries.py, series) Now iterating over 2500 summands verbose 1 (316: sha_tate.py, an_padic) the leading terms : [3 + O(5), 5 + O(5^2)] verbose 1 (316: sha_tate.py, an_padic) ...putting things together verbose 1 (316: sha_tate.py, an_padic) the two values for Sha : [1 + O(5), 1 + O(5)] 1 + O(5)
comment:14 in reply to: ↑ 13 Changed 10 years ago by
A bug in padic vectors related to the problems here was noticed and filed at #8198. Problems with power series having zero padic coefficients were noticed and filed at #4656. These seem related to #5075 (polynomials over inexact rings should not truncate inexact leading zeroes) and #6084 (Improved padic polynomials). When these are resolved, perhaps progress can be made here.
comment:15 Changed 9 years ago by
 Work issues changed from Fix bug in sage.schemes.elliptic_curves.sha_tate.Sha.an_padic; mention ticket number in commit messages. to Fix bug in sage.schemes.elliptic_curves.sha_tate.Sha.an_padic
comment:16 Changed 8 years ago by
 Description modified (diff)
 Milestone changed from sage5.0 to sage5.1
 Status changed from needs_work to needs_review
 Work issues Fix bug in sage.schemes.elliptic_curves.sha_tate.Sha.an_padic deleted
Bugs in padics seem to have been fixed as of Sage 5.0.rc0, so this patch passes all long tests in sage/schemes/elliptic_curves. Since padded_list
is quite a bit slower than list
, I've reworked the patch to keep using list
, but to append zeroes to the end of those lists which are too short.
Patchbot: apply trac_9457_power_series_eq_rebase.patch
comment:17 Changed 8 years ago by
 Priority changed from minor to major
comment:18 Changed 8 years ago by
Patchbot: apply trac_9457_power_series_eq_rebase.patch
comment:19 Changed 8 years ago by
 Status changed from needs_review to needs_work
 Work issues set to resolve problems with sha_tate.py
Oh bother! When switching from padded_list
to
x += [0]*(prec  len(x)) # x.list() does not include trailing zeroes x = x[:prec] # truncate x to common prec
I seem to be triggering the problem in sha_tate.py
again . . .
comment:20 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:21 Changed 6 years ago by
 Branch set to u/niles/ticket/9457
 Commit set to 83d1220d288e46df6e3e933a79faa4fc064ccefa
 Description modified (diff)
Last 10 new commits:
83d1220  rebase to 6.0 and #12555

aa65f59  Removed removed file from doc.

f338b7f  Fix wrong NOTE block.

fcf6ad2  Fix for comparison of padics.

5f00813  Fixes for "sage not defined".

89ef12d  Merge remotetracking branch 'origin/develop' into ticket/12555

0e7c964  Fixed failing doctest (likely due to #15422).

7d7ff1f  Merge branch 'master' into public/padics/templates12555

4b633ab  Fixes for some missing/duplicated chunks.

66e5746  From Trac patches: trac_12555pdf_fixts.patch.

comment:22 Changed 6 years ago by
 Commit changed from 83d1220d288e46df6e3e933a79faa4fc064ccefa to e2219602a9d360f465ad79b098e4f923765ab791
Branch pushed to git repo; I updated commit sha1. New commits:
e221960  rebase to 6.0

comment:23 Changed 6 years ago by
 Description modified (diff)
I had hoped the changes at #12555 would magically resolve this, but they do not. The other related tickets, listed in comment 14 are also not fixed by #12555.
Note that the current version of the git branch for this ticket (commit e221960) does *not* include the changes of #12555, although the initial version mistakenly did.
comment:24 Changed 6 years ago by
 Description modified (diff)
 Stopgaps set to #15748
 Summary changed from power series comparison should use padded_list to power series equality fails when trailing coefficients are zero
comment:25 Changed 6 years ago by
The problem with Sha.an_padic may also be related to the bug in extended gcd at #13439 or one of its dependencies.
comment:26 followup: ↓ 27 Changed 6 years ago by
 Cc wuthrich added
Interesting. I just started to look at #4656 again this morning. And then I discovered this ticket. The problems there would get solved partially by this solution here and conversely, the problem there to fix it are with the supersingular case tested in this one case. Of course, I offer my help with this as I am at the origin of the code that causes troubles.
comment:27 in reply to: ↑ 26 Changed 6 years ago by
Replying to wuthrich:
Of course, I offer my help with this as I am at the origin of the code that causes troubles.
Thanks :) The last real progress I made in understanding this is up in comments 13 and 14, where I worked through the offending doctest by hand  see the block starting on line 632.
One helpful thing would be to verify the calculations below:
Using the objects constructed in comment 13, sage says
sage: G O(5^3) + (2*5^1 + O(5^0))*T + O(T^2) sage: H O(T^2) sage: lpv (O(5^3) + (2*5^1 + O(5^0))*T + O(T^2), O(T^2)) sage: eps.transpose() [ 5/9 25/18] [5/18 5/9]
I think that H
is not correct, as it it built from the following list of coefficients
sage: [lps[n][1] for n in range(0,lps.prec())] [O(5^2), O(5^1), O(5^1), O(5^1), O(5^1)]
So I think the correct value should be H = O(5^2) + O(5^1)*T + O(T^2)
and hence
R(p) * H = O(5^3) + O(5^0)*T + O(T^2)
. Converting eps.transpose()
to the 5adics R
, so that I can check lpv * eps.transpose()
by hand, I have
sage: Matrix(R,2,2,[R(_) for _ in eps.transpose().list()]) [ 4*5 + 2*5^2 + 5^4 + 2*5^5 + O(5^6) 2*5^2 + 5^3 + 3*5^5 + 3*5^6 + O(5^7)] [3*5 + 3*5^2 + 4*5^3 + 5^4 + 5^5 + O(5^6) 4*5 + 2*5^2 + 5^4 + 2*5^5 + O(5^6)]
Therefore lpv * eps.transpose()
should be
( O(5^3) + (3 + O(5))*T + O(T^2) , O(5^4) + O(5^1)*T + O(T^2) )
Can you verify these calculations, and verify that if this were the output of lpv*eps.transpose()
, then the rest of the code would work correctly and return 1
, as expected? (I think I was confused about this last point when I made my comment 14; but this value for lpv * eps.transpose()
should make shan0 = 1
and shan1 = 0
, and if I read the rest of that block correctly then this will lead to the expected output).
If the analysis above is right, then the only problem remaining to solve is why H
is not computed correctly. The problem seems to be that the power series ring over padics does not keep track of negative precision when there are no nonzero coefficients:
sage: R(0).add_bigoh(1) O(5^1) sage: QpT(R(0).add_bigoh(1)) 0 # should be same as line above sage: QpT(1/25 + R(0).add_bigoh(1)) 5^2 + O(5^1) # precision remembered when nonzero coefficients are present
I guess there is some problem with positive precision too:
sage: QpT(R(0).add_bigoh(1)) 0 sage: QpT(1 + R(0).add_bigoh(1)) 1 + O(5)
Is this issue already part of one of the other padic bug tickets?
comment:28 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:29 followup: ↓ 30 Changed 6 years ago by
I try to remember what happened 4 years ago. I think I discovered exactly the same problem as you. First some bug, then fixing that gave an error for sha_tate in the supersingular case. This was due to the Dp_valued series return the wrong result. Chasing that I came to #8198, where I got stuck becasue (at the time) I did not know how I could fix that.
So let's make a list  as there are several overlapping tickets and issues:
 (see #4656) is_zero is broken for power series. This causes your
QpT( O(5^1))
to print as zero. It remembers that it is not, if you have .list you see its first coefficient is stillO(5^1)
. We should change__nonzero__
in power_series_poly.pyx
 (see #4656, too) power series compare wrongly. Your suggestion to use padded_list above is better than what I tried to do in the other ticket. That is cmp in power_series_ring_element.pyx
 (see #4656) power series also print wrongly. You would expect the inexact coefficients of the form
O(p^2)
to print, too. I tried to change that in the other ticket. That is_repr_
in power_series_ring_element.pyx
 (see #8198) Matrix multiplication on padics looses precision. I believe that is the heart of the problem for getting the right answer for this Dp_series. If I understand correctly you have spotted the same thing above.
 There is also #5075 which I have never looked at myself.
We could take the out the docstring in shatate out for now, so that this and #4656 can be closed. Then reintroduce it if we can fix #8198.
comment:30 in reply to: ↑ 29 ; followup: ↓ 31 Changed 6 years ago by
Replying to wuthrich:
I try to remember what happened 4 years ago.
Thanks for putting this together :)
So let's make a list  as there are several overlapping tickets and issues:
 (see #4656) is_zero is broken for power series. This causes your
QpT( O(5^1))
to print as zero. It remembers that it is not, if you have .list you see its first coefficient is stillO(5^1)
. We should change__nonzero__
in power_series_poly.pyx
#5075 addresses this too  the patch there introduces 3 concepts of zero: exact zero (infinite precision), maximally zero (zero to maximal precision allowed by parent ring), and inexact zero (zero to precision less than maximal precision). These are used to define some functions that are equal to degree for polynomials over exact rings, but more subtle over inexact rings, and these functions, in turn, are used to fix other functions . . .
In short, that ticket seems to me like a good place to start.
 (see #4656, too) power series compare wrongly. Your suggestion to use padded_list above is better than what I tried to do in the other ticket. That is cmp in power_series_ring_element.pyx
padded_list
works, but is substantially slower. In the latest commit here, I have a more direct fix. The patch at #5075 also has a fix that looks similar to mine, but I didn't compare them closely.
 (see #4656) power series also print wrongly. You would expect the inexact coefficients of the form
O(p^2)
to print, too. I tried to change that in the other ticket. That is_repr_
in power_series_ring_element.pyx
#5075 may address this too, at least judging by how some of the new doctests appear.
 (see #8198) Matrix multiplication on padics looses precision. I believe that is the heart of the problem for getting the right answer for this Dp_series. If I understand correctly you have spotted the same thing above.
This might be right . . . in my calculation above, the input to the vector*matrix multiplication is wrong, so I can't tell whether the matrix multiplication would also go wrong or not.
 There is also #5075 which I have never looked at myself.
I think we should go there :)
We could take the out the docstring in shatate out for now, so that this and #4656 can be closed. Then reintroduce it if we can fix #8198.
Hmmm . . . that doctest is holding up some pretty reasonable fixes, but it's also the only reason that we noticed these padic problems in the first place so I'm extremely reluctant to take it out. I think it is especially bad to take it out before we fully understand where the problems are coming from.
comment:31 in reply to: ↑ 30 Changed 6 years ago by
comment:32 Changed 6 years ago by
The only thing I see when I click on the green " u/niles/ticket/9457 " link in the branch field is a deletion of a file. What the hell, trac?
comment:33 Changed 6 years ago by
The first commit in comment:21 shows Bad object id: 83d1220
.
comment:34 Changed 6 years ago by
Replying to rws:
The first commit in comment:21 shows
Bad object id: 83d1220
.
Weird; The commit linked by trac seems wrong, although the "Commit" field is correct. The branch should point to e2219602.... Here are some other links you can look at, which seem to have the branch pointing at the correct commit:
I think the changes listed in comment 21 came from trying to merge some other ticket branches with this one, which I think I should not have done. Or rather, I should not have deleted that branch and replaced it with a new one having the same name  that's probably causing confusion for trac.
Commit e2219602... makes just the changes necessary for fixing this ticket, so that's the correct starting point. Later today I'll make a new branch pointing to it and fix the trac branch field.
comment:35 Changed 6 years ago by
 Branch changed from u/niles/ticket/9457 to u/niles/ticket/9457.2
 Commit changed from e2219602a9d360f465ad79b098e4f923765ab791 to 4329b79d433f2bc1658df01bba9d53f2e467bf86
comment:36 Changed 6 years ago by
 Dependencies set to #8198
The doctest failure in sha_tate.py
disappears when testing this ticket together with #8198. Is this the only thing keeping this ticket from being ready to be reviewed?
comment:37 followup: ↓ 38 Changed 6 years ago by
Yes, that is mine now. That may take me soem time to fix. This is really a new bug, which was not apparent with the bug fixed here. So my suggestion would be to comment out the failing test, to open a new ticket and to fix the new bug in a separate ticket as they are unrelated topics. Though I am not sure that is the way we should do it.
In any case, I start looking into the issue.
comment:38 in reply to: ↑ 37 Changed 6 years ago by
Replying to wuthrich:
Yes, that is mine now. That may take me soem time to fix. This is really a new bug, which was not apparent with the bug fixed here.
I'm not sure you interpreted my comment correctly. I meant I merged #8198 and the branch for this, ran make ptestlong
, and got NO doctest failures; I hope I made no mistakes there. I.e. if that (former, after #8198) doctest failure in sha_tate.py
was the only problem with this ticket, then there should be nothing stopping us from positively reviewing this one.
comment:39 Changed 6 years ago by
Oh, I see. If so, we should change the branch on this one by merging #8198 into it, I think. Then a reviewer (e.g. me or you since you have done the work already) can give it a positive review.
comment:40 Changed 6 years ago by
OK, I'll do that and also add a reviewer patch to remove the stopgap that was made for this ticket.
I also thought of replacing the use of list()
by padded_list()
as the stopgap warning suggests, but judging from some small experiments that seems to be much slower.
comment:41 Changed 6 years ago by
 Branch changed from u/niles/ticket/9457.2 to u/pbruin/9457power_series_comparison
 Commit changed from 4329b79d433f2bc1658df01bba9d53f2e467bf86 to 9c0b17f8ca77ce881b7b96a7a2b06ef8b856a0d1
 Reviewers set to Peter Bruin
 Status changed from needs_work to positive_review
 Work issues resolve problems with sha_tate.py deleted
OK, all tests still pass. 8) Just a reviewer patch, as promised. I mostly edited the documentation a bit more to also mention the idea that comparing to the minimum of the two precisions is consistent with coercing the elements to a common parent.
comment:42 Changed 6 years ago by
This is fantastic!! Thanks for seeing it through :)
padded_list
is indeed slower  I just suggested it as a simple workaround for the stopgap warning.
The confounding doctest seems to be behaving correctly now  the intermediate steps are consistent with my calculations by hand above, and the verbose output is as expected (given that there are still other problems with padics):
sage: EllipticCurve('53a1').sha().an_padic(5) ... verbose 1 (431: sha_tate.py, an_padic) ...computing the padic Lseries verbose 1 (1059: padic_lseries.py, series) using padic precision of 4 verbose 1 (1059: padic_lseries.py, series) Now iterating over 100 summands verbose 1 (431: sha_tate.py, an_padic) the leading terms : [0, 0] verbose 1 (431: sha_tate.py, an_padic) increased precision to 4 verbose 1 (1059: padic_lseries.py, series) using padic precision of 5 verbose 1 (1059: padic_lseries.py, series) Now iterating over 500 summands verbose 1 (431: sha_tate.py, an_padic) the leading terms : [3 + O(5), 0] verbose 1 (431: sha_tate.py, an_padic) ...putting things together verbose 1 (431: sha_tate.py, an_padic) the two values for Sha : [1 + O(5), 0] 1 + O(5)
comment:43 Changed 6 years ago by
 Branch changed from u/pbruin/9457power_series_comparison to 9c0b17f8ca77ce881b7b96a7a2b06ef8b856a0d1
 Resolution set to fixed
 Status changed from positive_review to closed
change list to padded_list in _richcmp_c_impl