Opened 10 years ago

Closed 8 years ago

#11639 closed defect (duplicate)

conductor of simple curve over Q(cube root 3) takes forever

Reported by: was Owned by: cremona
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: elliptic curves Keywords:
Cc: Merged in:
Authors: Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by jdemeyer)

sage: x=var('x'); K.<a> = NumberField(x^3 - 2); EllipticCurve([0,a]).conductor()
[[ wait forever! ]]

The correct answer has norm 322486272, and should be instant:

sage: magma(E).Conductor()
Ideal
Basis:
[864   0   0]
[  0 864   0]
[  0   0 432]
sage: magma(E).Conductor().Norm()
322486272

Trying with proof.all(False) doesn't help, by the way, so I don't think it is just some complexity issue... and yet, I just tried control-c after letting "E.conductor()" sit there for a while, then typed "%debug", then "u", then saw that two ideals of the integers of the cubic field were being multiplied. I printed the gens of one ideal and got

ipdb> u
> /Users/wstein/sage/install/current/local/lib/python2.6/site-packages/sage/rings/ideal.py(857)__mul__()
    856             other = self.ring().ideal(other)
--> 857         return self.ring().ideal([x*y for x in self.gens() for y in other.gens()])
    858 

ipdb> print self.gens()
(16384, 8192*a, 8192*a, 4096*a^2, 8192*a, 4096*a^2,  ... goes on redundantly for many pages!)

Fixed by #13958.

Change History (12)

comment:1 Changed 10 years ago by was

  • Description modified (diff)

comment:2 Changed 10 years ago by fwclarke

This is the heart of the problem

sage: K.<a> = NumberField(x^3 - 2); E = EllipticCurve([0, a])
sage: P, Q = K.prime_factors(E.discriminant())
sage: P, P.gens()
(Fractional ideal (a), (2, a))
sage: P2 = P*P; P2, P2.gens()
(Fractional ideal (a^2), (4, 2*a, 2*a, a^2))

The conductor is computed as P^14*Q^9, which is defined by 223 (highly redundant) generators. Multiplication of ideals avoids reducing the generators, which can be time-consuming (though not in this case), but it could at least eliminate repeats.

comment:3 follow-up: Changed 10 years ago by cremona

How hard would it be to eliminate repeated gens after any ideal multiplication? And would that make this particular example run in reasonable time?

Note that in a Dedekind domain if I = (a,b) then In = (an,bn) [exercise!] which is surely a special case worth catching!

Otherwise I suppose we could have an option to return the conductor in factored form. When I compute conductors over number fields I almost always factor it right away (which is a bit silly when that poor ideal has only just been multiplied together), and take its norm and factor that; rarely would I want to see the conductor as an ideal unless it were principal.

comment:4 in reply to: ↑ 3 Changed 10 years ago by cremona

Note that in a Dedekind domain if I = (a,b) then In = (an,bn) [exercise!] which is surely a special case worth catching!

That should read: if I = (a,b) then I^n = (a^n,b^n)

comment:5 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.10 to sage-duplicate/invalid/wontfix
  • Reviewers set to Jeroen Demeyer
  • Status changed from new to needs_review

This works now:

sage: K.<a> = NumberField(x^3 - 2)
sage: %time EllipticCurve([0,a]).conductor().norm()
CPU times: user 0.14 s, sys: 0.01 s, total: 0.15 s
Wall time: 0.14 s
322486272

comment:6 Changed 8 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:7 follow-up: Changed 8 years ago by cremona

As there is no patch here, do we know what changed to make this work ok now?

comment:8 in reply to: ↑ 7 ; follow-up: Changed 8 years ago by jdemeyer

Replying to cremona:

As there is no patch here, do we know what changed to make this work ok now?

I know the multiplication of number field ideals got improved, which was essentially the problem this ticket is about.

comment:9 in reply to: ↑ 8 ; follow-up: Changed 8 years ago by cremona

Replying to jdemeyer:

Replying to cremona:

As there is no patch here, do we know what changed to make this work ok now?

I know the multiplication of number field ideals got improved, which was essentially the problem this ticket is about.

OK, fine. We could add a doctest referencing this ticket. Is that worth while?

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

Replying to cremona:

We could add a doctest referencing this ticket. Is that worth while?

Not really, since the actual issue is fixed and doctested in #13958.

comment:11 in reply to: ↑ 10 Changed 8 years ago by cremona

Replying to jdemeyer:

Replying to cremona:

We could add a doctest referencing this ticket. Is that worth while?

Not really, since the actual issue is fixed and doctested in #13958.

Then I am happy, especially since this cross-reference is now on this ticket!

comment:12 Changed 8 years ago by jdemeyer

  • Description modified (diff)
  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.