[Sage Bug Report] Invalid polynomials generated in formal group law calculation

[Hamish]

Dear sage-devel,

I have recently come across a bug which is perhaps best summarised in
the following code (I've removed a big chunk of the backtrace to make
it easier to read; the full backtrace is available at the end of this
message):

--- BEGIN ---

sage: k.<a> = GF(5^2, 'a')
sage: EllipticCurve(k, [1,1]).formal_group().group_law(prec = 7)
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)

/Users/hlaw/src/<ipython console> in <module>()

/Users/hlaw/sage/local/lib/python2.5/site-packages/sage/schemes/
elliptic_curves/formal_group.py in group_law(self, prec)
440 lam3 = lam2*lam
441 t3 = -t1 - t2 - \
--> 442 (a1*lam + a3*lam2 + a2*nu + 2*a4*lam*nu +
3*a6*lam2*nu)/ \
443 (1 + a2*lam + a4*lam2 + a6*lam3)
444 inv = self.inverse(prec)

[snip]

/Users/hlaw/src/polynomial_element.pyx in
sage.rings.polynomial.polynomial_element.Polynomial.valuation (sage/
rings/polynomial/polynomial_element.c:22641)()

TypeError: The polynomial, p, must have the same parent as self.

--- END ---

(Note that the polynomial referred to in the TypeError is a red
herring: it's an optional parameter to the valuation() method that
is not being used in this case.) So the bug is being triggered in the
Polynomial.valuation() method, but from what I've determined so far,
it occurs because the polynomial whose valuation is being calculated
is "corrupted" in the following sense. If p is the polynomial
triggering the error, then:

p.coeffs() is [0, 0, 0, 0, 0, 0, 0]
p.degree() is 6
p.is_zero() is False

Moreover, the error only occurs at certain precisions. For example:

sage: def run_test(field, prec_bound=20):
E = EllipticCurve(field, [1,1])
FG = E.formal_group()
error_precisions = []
for precision in range(2, prec_bound):
try:
gl = FG.group_law(precision)
except TypeError:
error_precisions.append(precision)
return error_precisions

sage: run_test(GF(5^2, 'a'), 30)
[5, 6, 7, 9, 11, 13, 14, 15, 17, 19, 21, 23, 25, 26, 27, 29]

I have tried randomly changing the elliptic curve and the field
degree, but run_test() returned exactly the same list each time.
Changing the base field modifies the list a bit:

sage: run_test(GF(7^2, 'a'), 30)
[5, 6, 7, 9, 11, 13, 15, 17, 18, 19, 20, 21, 23, 25, 27, 29]

So 14 and 26 are now gone, but 18 and 20 have been introduced.

And finally, no errors occur at all if we use a prime finite field
instead of a non-prime one:

sage: run_test(GF(5), 30); run_test(GF(7), 30)
[]
[]


The same basic bug occurs on the following machines:
Sage 3.0.3 (upgraded from 2.11), Ubuntu Linux 8.04, x86
Sage 2.11, Ubuntu Linux 8.04, x86
Sage 3.04, Mac OS X 10.5.3, x86

The examples in this message were all calculated on the MacOSX
machine.


Also, I'd like to be put on the CC list of the ticket, if/when a
ticket is created for this bug.

Thanks in advance,
Hamish.


Full backtrace:

sage: k.<a> = GF(5^2, 'a')
sage: EllipticCurve(k, [1,1]).formal_group().group_law(prec = 7)
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)

/Users/hlaw/src/<ipython console> in <module>()

/Users/hlaw/sage/local/lib/python2.5/site-packages/sage/schemes/
elliptic_curves/formal_group.py in group_law(self, prec)
440 lam3 = lam2*lam
441 t3 = -t1 - t2 - \
--> 442 (a1*lam + a3*lam2 + a2*nu + 2*a4*lam*nu +
3*a6*lam2*nu)/ \
443 (1 + a2*lam + a4*lam2 + a6*lam3)
444 inv = self.inverse(prec)

/Users/hlaw/src/element.pyx in
sage.structure.element.RingElement.__mul__ (sage/structure/element.c:
8797)()

/Users/hlaw/src/coerce.pxi in sage.structure.element._mul_c (sage/
structure/element.c:16614)()

/Users/hlaw/src/power_series_poly.pyx in
sage.rings.power_series_poly.PowerSeries_poly._mul_c_impl (sage/rings/
power_series_poly.c:3161)()

/Users/hlaw/src/element.pyx in
sage.structure.element.RingElement.__mul__ (sage/structure/element.c:
8797)()

/Users/hlaw/src/coerce.pxi in sage.structure.element._mul_c (sage/
structure/element.c:16614)()

/Users/hlaw/src/polynomial_element.pyx in
sage.rings.polynomial.polynomial_element.Polynomial._mul_c_impl (sage/
rings/polynomial/polynomial_element.c:7260)()

/Users/hlaw/src/polynomial_element.pyx in
sage.rings.polynomial.polynomial_element.Polynomial._mul_karatsuba
(sage/rings/polynomial/polynomial_element.c:10735)()

/Users/hlaw/src/polynomial_element.pyx in
sage.rings.polynomial.polynomial_element.do_karatsuba (sage/rings/
polynomial/polynomial_element.c:25040)()

/Users/hlaw/src/polynomial_element.pyx in
sage.rings.polynomial.polynomial_element.do_karatsuba (sage/rings/
polynomial/polynomial_element.c:24742)()

/Users/hlaw/src/element.pyx in
sage.structure.element.RingElement.__mul__ (sage/structure/element.c:
8797)()

/Users/hlaw/src/coerce.pxi in sage.structure.element._mul_c (sage/
structure/element.c:16614)()

/Users/hlaw/src/power_series_poly.pyx in
sage.rings.power_series_poly.PowerSeries_poly._mul_c_impl (sage/rings/
power_series_poly.c:3145)()

/Users/hlaw/src/power_series_ring_element.pyx in
sage.rings.power_series_ring_element.PowerSeries._mul_prec (sage/rings/
power_series_ring_element.c:5554)()

/Users/hlaw/src/power_series_poly.pyx in
sage.rings.power_series_poly.PowerSeries_poly.valuation (sage/rings/
power_series_poly.c:2050)()

/Users/hlaw/src/polynomial_element.pyx in
sage.rings.polynomial.polynomial_element.Polynomial.valuation (sage/
rings/polynomial/polynomial_element.c:22641)()

TypeError: The polynomial, p, must have the same parent as self.


--
Hamish Ivey-Law
PhD student,
Institut de Mathématiques de Luminy, Université de la Méditerranée,
and
School of Mathematics and Statistics, University of Sydney.

[David Harvey]

Hi, I don't have time to debug this now, but I want to mention that it sounds suspiciously similar to this ticket:

http://sagetrac.org/sage_trac/ticket/2943

Maybe there are some clues there, but I never quite got to the bottom of it.

david

[Hamish]

On Jul 17, 2:58 pm, David Harvey <dmhar...@math.harvard.edu> wrote:
> I don't have time to debug this now, but I want to mention that  
> it sounds suspiciously similar to this ticket:
>
> http://sagetrac.org/sage_trac/ticket/2943

It certainly does. (I probably should have filtered the tickets with
"power series" instead of just "polynomial" when I was looking through
them.)

The main difference seems to be that in the the present case, the base
ring of the polynomial ring is exact, though the polynomial ring in
question is "derived" from the inexact power series ring used in the
calculation of the formal group law. Anyway, I get something that
works if I remove the bit in the patch in ticket 2943 that uses the
old way of determining "__nonzero__-ness" for exact base rings (i.e.
now the code says a polynomial is __nonzero__ if all its
coefficients are nonzero, instead of checking if the list of
coefficients is non-empty).

Cheers,
Hamish.

[David Harvey]

I have added a link back to this thread from the ticket. If you find
out any more, please add comments to that ticket.

david