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: |
Description (last modified by )
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
- Description modified (diff)
comment:2 Changed 10 years ago by
comment:3 follow-up: ↓ 4 Changed 10 years ago by
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 I^{n = (a}n,b^{n) [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
Note that in a Dedekind domain if I = (a,b) then I^{n = (a}n,b^{n) [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
- 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
- Status changed from needs_review to positive_review
comment:7 follow-up: ↓ 8 Changed 8 years ago by
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: ↓ 9 Changed 8 years ago by
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: ↓ 10 Changed 8 years ago by
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: ↓ 11 Changed 8 years ago by
comment:11 in reply to: ↑ 10 Changed 8 years ago by
comment:12 Changed 8 years ago by
- Description modified (diff)
- Resolution set to duplicate
- Status changed from positive_review to closed
This is the heart of the problem
The conductor is computed as
P^14*Q^9
, which is defined by 2^{23} (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.^{}