Problem displaying a number field (fractional) ideal

[JohnCremona]

With 8.3.rc1:

sage: K.<a> = NumberField(x^6 - x^5 - 5*x^4 + 4*x^3 + 6*x^2 - 3*x - 1)
sage: K.ideal(1,1)

takes a long time to return -- why? Using %time it immediately shows 1ms for the second line but the prompt does not appear until minutes later. So it is the display of the ideal which is triggering something long. In a new session:

sage: K.<a> = NumberField(x^6 - x^5 - 5*x^4 + 4*x^3 + 6*x^2 - 3*x - 1)
sage: %time I=K.ideal([1,1])
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 1.08 ms
sage: %time I
CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 10 µs
<long wait>

CC: @jdemeyer @slel

Component: number fields

Keywords: NumberField, ideal

Author: John Cremona

Branch/Commit: 1e45e42

Reviewer: Frédéric Chapoton, Samuel Lelièvre

Issue created by migration from https://trac.sagemath.org/ticket/25934

[JohnCremona]

comment:2

Since the field discriminant is less than 10^6 the string function calls gens_reduced, and that is taking the time. Specifially the call to self_cache_bnfisprincipal() is. This suggests that something needs fixing; but also it might be a good idea to include special case code for the unit ideal -- this ideal has norm 1 which is trivial to compute so returning the string '(1)' could be done as a short cut.

[jdemeyer]

comment:3

Replying to @JohnCremona:

but also it might be a good idea to include special case code for the unit ideal -- this ideal has norm 1 which is trivial to compute so returning the string '(1)' could be done as a short cut.

That's such a special case, I'm not convinced that it's worth it.

[jdemeyer]

comment:4

Replying to @JohnCremona:

Since the field discriminant is less than 10^6 the string function calls gens_reduced, and that is taking the time.

Indeed. So I would say that this heuristic bound of the discriminant is not sufficient to predict that the class group is easy to compute.

[jdemeyer]

comment:5

I asked pari-dev.

• http://pari.math.u-bordeaux.fr/archives/pari-dev-1807/msg00001.html

[slel]

comment:6

From Karim Belabas's answer on pari-dev:

In any case, you should never compute a bnfinit
when it's not absolutely necessary. [ I.e. you
should do it on the fly when the extra structure
is a prerequisite for a specific function call. ]

[JohnCremona]

comment:9

There is something strange here. Nothing to do with the representation if ideals really. For this field, if you construct its pari_bnf, it takes ages to return even with no output:

sage: K.<a> = NumberField(x^6 - x^5 - 5*x^4 + 4*x^3 + 6*x^2 - 3*x - 1)                                                                                 
sage: %time pK = K.pari_bnf(proof=False, units=False)                    
CPU times: user 1min 11s, sys: 128 ms, total: 1min 11s
Wall time: 1min 11s

but in a fresh Sage session, if I interrupt the second line immediately and then rerun it:

sage: K.<a> = NumberField(x^6 - x^5 - 5*x^4 + 4*x^3 + 6*x^2 - 3*x - 1)                                                                                 
sage: %time pK = K.pari_bnf(proof=False, units=False)                
<interrupt after <1s>
sage: %time pK = K.pari_bnf(proof=False, units=False)                                                                                                  
CPU times: user 36 ms, sys: 0 ns, total: 36 ms
Wall time: 37.2 ms

Also, after this, displaying K.ideal(1,1) is instantaneous. So I think that there is a bug in here, though I cannot tell what is happening.

Simplifying further:

sage: y = polygen(QQ, 'y')                                                                                                                             
sage: f = pari(y^6 - y^5 - 5*y^4 + 4*y^3 + 6*y^2 - 3*y - 1)                                                                                            
sage: %time f.bnfinit() 
CPU times: user 1min 9s, sys: 144 ms, total: 1min 9s
Wall time: 1min 9s

while again, interrupting immediately and reissuing the last line gives the output immediately.

Lastly,

sage: %gp                                                                                                                                              

  --> Switching to PARI/GP interpreter <--

pari: K = bnfinit(y^6 - y^5 - 5*y^4 + 4*y^3 + 6*y^2 - 3*y - 1);                                                                                        

pari: ##                                                                                                                                               
  ***   last result computed in 24 ms.

[videlec]

comment:10

What about 9.3.beta6? Sage 8.3.rc1 is not very relevant unless you precisely bisect where the problem is.

[videlec]

comment:11

(implicit note: I can not reproduce on 9.3.beta6)

[JohnCremona]

comment:12

The original posting was for an old version, but everything I wrote in the last 24 hours has been for 9.2, running on ubuntu, built from source.

[JohnCremona]

comment:13

Ah, and when I try on 9.3.beta6 is is fine. That's good! I'll mark this as invalid / won't-fix as something has fixed it between 9.2 and now.

[videlec]

comment:14

Maybe cypari2 upgrade #31029?

[slel]

comment:16

Any way to add a doctest for this?

[JohnCremona]

comment:17

Replying to @slel:

Any way to add a doctetcst for this?

Sure: the 2 lines of the original post should do.

[JohnCremona]

Branch: u/cremona/25934

[JohnCremona]

Commit: 1e45e42

[JohnCremona]

comment:19

I added a doctest as suggested. No code changes.

---

New commits:

1e45e42

#25934: add doctest to show the problem has gone away

[JohnCremona]

Author: John Cremona

[JohnCremona]

comment:20

Review please? The patch just adds one tiny doctest.

[slel]

Changed keywords from none to NumberField, ideal

[fchapoton]

Reviewer: Frédéric Chapoton, Samuel Lelièvre

[vbraun]

Changed branch from u/cremona/25934 to 1e45e42