Opened 10 years ago

Closed 8 years ago

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

Reported by: Owned by: was cremona major sage-duplicate/invalid/wontfix elliptic curves Jeroen Demeyer N/A

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

### 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: ↓ 4 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: ↓ 8 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: ↓ 9 Changed 8 years ago by jdemeyer

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

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

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