Opened 9 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: sage-6.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 niles)

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)

trac_9457_power_series_eq.patch (1.1 KB) - added by niles 9 years ago.
change list to padded_list in _richcmp_c_impl
trac_9457_power_series_eq_doctests.patch (1.7 KB) - added by niles 9 years ago.
apply after previous patch; includes doctests
trac_9457_power_series_eq_rebase.patch (2.5 KB) - added by niles 8 years ago.
rebased to 5.0.rc0

Download all attachments as: .zip

Change History (46)

comment:1 Changed 9 years ago by niles

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by niles

  • Description modified (diff)

Changed 9 years ago by niles

change list to padded_list in _richcmp_c_impl

comment:3 Changed 9 years ago by niles

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 follow-up: Changed 9 years ago by niles

  • Description modified (diff)

comment:5 in reply to: ↑ 4 Changed 9 years ago by niles

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]

Changed 9 years ago by niles

apply after previous patch; includes doctests

comment:6 Changed 9 years ago by SimonKing

  • Authors set to niles
  • 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 9 years ago by SimonKing

  • 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/sage-4.4.2/devel/sage-main/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/sage-4.4.2/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/king/SAGE/sage-4.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/sage-4.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/sage-4.4.2/local/lib/python/site-packages/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 p-adic BSD."
    RuntimeError: There must be a bug in the supersingular routines for the p-adic BSD.

So, there will be some bug hunt needed.

comment:8 Changed 9 years ago by SimonKing

Here's the problem.

Without the patch:

sage: R.<T> = QQ.completion(5,5)[[]]
sage: R
Power Series Ring in T over 5-adic 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 5-adic 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 follow-up: Changed 9 years ago by niles

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 p-adic L-series
# (namely the coefficients of zero-relative 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 p-adic 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 p-adic 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 ; follow-ups: Changed 9 years ago by SimonKing

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 on shan0 and shan1 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 9 years ago by niles

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 e-mail to sage-devel and see if someone can help

comment:12 in reply to: ↑ 10 ; follow-up: Changed 9 years ago by niles

  • 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 p-adics. 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 = (1-phi)**(-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 with-patch 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 upper-right entry).

Here is a more direct test that passing to the power series ring over 5-adic 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 p-adics, 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 p-adic problem. This is sort of dodging the issue, but helps keep the individual bugs separated.

comment:13 in reply to: ↑ 12 ; follow-up: Changed 9 years ago by niles

Replying to niles:

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 upper-right 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 p-adic L-series
verbose 1 (316: sha_tate.py, an_padic) r = 1
verbose 1 (881: padic_lseries.py, series) using p-adic 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 9 years ago by niles

A bug in p-adic vectors related to the problems here was noticed and filed at #8198. Problems with power series having zero p-adic 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 p-adic polynomials). When these are resolved, perhaps progress can be made here.

comment:15 Changed 9 years ago by jdemeyer

  • 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

Changed 8 years ago by niles

rebased to 5.0.rc0

comment:16 Changed 8 years ago by niles

  • Description modified (diff)
  • Milestone changed from sage-5.0 to sage-5.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 p-adics 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 niles

  • Priority changed from minor to major

comment:18 Changed 8 years ago by niles

Patchbot: apply trac_9457_power_series_eq_rebase.patch

comment:19 Changed 8 years ago by niles

  • 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 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:21 Changed 6 years ago by niles

  • Branch set to u/niles/ticket/9457
  • Commit set to 83d1220d288e46df6e3e933a79faa4fc064ccefa
  • Description modified (diff)

Last 10 new commits:

83d1220rebase to 6.0 and #12555
aa65f59Removed removed file from doc.
f338b7fFix wrong NOTE block.
fcf6ad2Fix for comparison of padics.
5f00813Fixes for "sage not defined".
89ef12dMerge remote-tracking branch 'origin/develop' into ticket/12555
0e7c964Fixed failing doctest (likely due to #15422).
7d7ff1fMerge branch 'master' into public/padics/templates-12555
4b633abFixes for some missing/duplicated chunks.
66e5746From Trac patches: trac_12555-pdf_fix-ts.patch.

comment:22 Changed 6 years ago by git

  • Commit changed from 83d1220d288e46df6e3e933a79faa4fc064ccefa to e2219602a9d360f465ad79b098e4f923765ab791

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

e221960rebase to 6.0

comment:23 Changed 6 years ago by niles

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

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

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 follow-up: Changed 6 years ago by wuthrich

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

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 5-adics 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 p-adics does not keep track of negative precision when there are no non-zero 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 non-zero 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 vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:29 follow-up: Changed 6 years ago by wuthrich

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 still O(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 p-adics 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 doc-string in sha-tate 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 ; follow-up: Changed 6 years ago by niles

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 still O(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 p-adics 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 doc-string in sha-tate 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 rws

Last edited 6 years ago by rws (previous) (diff)

comment:32 Changed 6 years ago by darij

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 rws

The first commit in comment:21 shows Bad object id: 83d1220.

comment:34 Changed 6 years ago by niles

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 niles

  • Branch changed from u/niles/ticket/9457 to u/niles/ticket/9457.2
  • Commit changed from e2219602a9d360f465ad79b098e4f923765ab791 to 4329b79d433f2bc1658df01bba9d53f2e467bf86

rebased to 6.2.beta2 and put changes on a completely new branch: u/niles/ticket/9457.2


New commits:

e221960rebase to 6.0
4329b79Merge branch 'ticket/9457' into ticket/9457.2

comment:36 Changed 6 years ago by pbruin

  • 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 follow-up: Changed 6 years ago by 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. 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 pbruin

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 wuthrich

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 pbruin

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 pbruin

  • Authors changed from niles to Niles Johnson
  • Branch changed from u/niles/ticket/9457.2 to u/pbruin/9457-power_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 niles

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 p-adic L-series
verbose 1 (1059: padic_lseries.py, series) using p-adic 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 p-adic 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 vbraun

  • Branch changed from u/pbruin/9457-power_series_comparison to 9c0b17f8ca77ce881b7b96a7a2b06ef8b856a0d1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.