# Ticket #9457(needs_work defect)

Opened 3 years ago

## power series comparison should use padded_list

Reported by: Owned by: niles malb major sage-5.10 commutative algebra SimonKing resolve problems with sha_tate.py N/A 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]
[0, 1]
[0, 1, 0]
```

## Change History

### comment:1 Changed 3 years ago by niles

• Status changed from new to needs_review

### comment:2 Changed 3 years ago by niles

• Description modified (diff)

### Changed 3 years ago by niles

change list to padded_list in _richcmp_c_impl

### comment:3 Changed 3 years ago by niles

```sage: A.<t> = PowerSeriesRing(ZZ)
sage: f = t + t^2 + O(t^10)
sage: f == f.truncate()
False
[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)
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for '*': '<type 'list'>' and 'The Infinity Ring'
```

### comment:4 follow-up: ↓ 5 Changed 3 years ago by niles

• Description modified (diff)

### comment:5 in reply to: ↑ 4 Changed 3 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
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1]
```

### Changed 3 years ago by niles

apply after previous patch; includes doctests

### comment:6 Changed 3 years ago by SimonKing

• Status changed from needs_review to needs_work
• Work issues set to Mention ticket number in commit messages
• Authors set to niles

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 3 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 3 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
```

### comment:9 follow-up: ↓ 10 Changed 3 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)
...
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)
...
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: 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: 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: ↓ 11 ↓ 12 Changed 3 years ago by SimonKing

Hi 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 3 years ago by niles

Hi Simon, thanks for the quick reply :)

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: ↓ 13 Changed 3 years ago by niles

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: 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)
0
-1
+Infinity
5^-2 + O(5^-1)
-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: ↓ 14 Changed 3 years ago by 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)
...
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) r = 1
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 3 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 2 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 13 months ago by niles

rebased to 5.0.rc0

### comment:16 Changed 13 months ago by niles

• Status changed from needs_work to needs_review
• Work issues Fix bug in sage.schemes.elliptic_curves.sha_tate.Sha.an_padic deleted
• Description modified (diff)
• Milestone changed from sage-5.0 to sage-5.1

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

• Priority changed from minor to major

### comment:18 Changed 13 months ago by niles

Patchbot: apply trac_9457_power_series_eq_rebase.patch

### comment:19 Changed 13 months 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 . . .

Note: See TracTickets for help on using tickets.