Opened 3 years ago

Closed 7 months ago

#25934 closed defect (fixed)

Problem displaying a number field (fractional) ideal

Reported by: cremona Owned by:
Priority: major Milestone: sage-9.3
Component: number fields Keywords: NumberField, ideal
Cc: jdemeyer, slelievre Merged in:
Authors: John Cremona Reviewers: Frédéric Chapoton, Samuel Lelièvre
Report Upstream: N/A Work issues:
Branch: 1e45e42 (Commits, GitHub, GitLab) Commit: 1e45e421fe879eb9e306fde3745ef3cbc36bf43c
Dependencies: Stopgaps:

Status badges

Description (last modified by cremona)

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>

Change History (23)

comment:1 Changed 3 years ago by cremona

  • Description modified (diff)
  • Summary changed from Problem creating a number field (fractional) ideal to Problem displaying a number field (fractional) ideal

comment:2 follow-ups: Changed 3 years ago by cremona

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.

comment:3 in reply to: ↑ 2 Changed 3 years ago by jdemeyer

Replying to cremona:

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.

comment:4 in reply to: ↑ 2 Changed 3 years ago by jdemeyer

Replying to cremona:

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.

comment:6 Changed 18 months ago by slelievre

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

comment:7 Changed 18 months ago by slelievre

  • Cc slelievre added
  • Component changed from PLEASE CHANGE to number fields
  • Milestone changed from sage-8.4 to sage-9.2

comment:8 Changed 13 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:9 Changed 8 months ago by cremona

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.

comment:10 Changed 8 months ago by vdelecroix

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

comment:11 Changed 8 months ago by vdelecroix

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

comment:12 Changed 8 months ago by cremona

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.

comment:13 Changed 8 months ago by cremona

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.

comment:14 Changed 8 months ago by vdelecroix

Maybe cypari2 upgrade #31029?

comment:15 Changed 8 months ago by cremona

  • Milestone changed from sage-9.3 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

comment:16 follow-up: Changed 8 months ago by slelievre

Any way to add a doctest for this?

comment:17 in reply to: ↑ 16 Changed 8 months ago by cremona

Replying to slelievre:

Any way to add a doctetcst for this?

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

comment:18 Changed 8 months ago by cremona

  • Status changed from needs_review to needs_work

comment:19 Changed 8 months ago by cremona

  • Authors set to John Cremona
  • Branch set to u/cremona/25934
  • Commit set to 1e45e421fe879eb9e306fde3745ef3cbc36bf43c
  • Status changed from needs_work to needs_review

I added a doctest as suggested. No code changes.


New commits:

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

comment:20 Changed 8 months ago by cremona

Review please? The patch just adds one tiny doctest.

comment:21 Changed 8 months ago by slelievre

  • Keywords NumberField ideal added
  • Milestone changed from sage-duplicate/invalid/wontfix to sage-9.3

comment:22 Changed 8 months ago by chapoton

  • Reviewers set to Frédéric Chapoton, Samuel Lelièvre
  • Status changed from needs_review to positive_review

comment:23 Changed 7 months ago by vbraun

  • Branch changed from u/cremona/25934 to 1e45e421fe879eb9e306fde3745ef3cbc36bf43c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.