power series comparison should use padded_list

[niles]

Comparison of power series uses list instead of padded_list; this means that power series equality can fail:

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, False, True, False, True, False, True]
sage: g.add_bigoh(3).list()
[0, 1]
sage: g.add_bigoh(3).padded_list()
[0, 1, 0]

Apply

• trac_9457_power_series_eq_rebase.patch

[niles]

change list to padded_list in _richcmp_c_impl

[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'

[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]

[niles]

apply after previous patch; includes doctests

[SimonKing]

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

[SimonKing]

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.

[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.

[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.

[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).

[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

[niles]

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.

[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)

[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.

[niles]

rebased to 5.0.rc0

[niles]

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

[niles]

Patchbot: apply trac_9457_power_series_eq_rebase.patch

[niles]

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 . . .