Opened 8 years ago

Closed 7 years ago

#11836 closed defect (fixed)

gens_reduced() does not handle "large" ideals

Reported by: mirela Owned by: jdemeyer
Priority: major Milestone: sage-4.8
Component: number fields Keywords:
Cc: jdemeyer, mstreng, cremona Merged in: sage-4.8.alpha1
Authors: Jeroen Demeyer Reviewers: Marco Streng
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11130 Stopgaps:

Description (last modified by jdemeyer)

PARI does not compute the reduced generators of the ideal below (even though the class number of L is 1, so the ideal is certainly principal):

sage: R.<x> = QQ['x']
sage: L.<b3> = NumberField(x^10 - 10*x^8 - 20*x^7 + 165*x^6 - 12*x^5 - 760*x^3 + 2220*x^2 + 5280*x + 7744)
sage: z_x = -96698852571685/2145672615243325696*b3^9 + 2472249905907/195061146840302336*b3^8 + 916693155514421/2145672615243325696*b3^7 + 1348520950997779/2145672615243325696*b3^6 - 82344497086595/12191321677518896*b3^5 + 2627122040194919/536418153810831424*b3^4 - 452199105143745/48765286710075584*b3^3 + 4317002771457621/536418153810831424*b3^2 + 2050725777454935/67052269226353928*b3 + 3711967683469209/3047830419379724
sage: P = EllipticCurve(L, '57a1').lift_x(z_x) * 3
sage: ideal = L.OK().fractional_ideal(P[0], P[1])
sage: ideal.gens_reduced(proof=False)
  ***   Warning: precision too low for generators, not given.
---------------------------------------------------------------------------
Traceback 
...

PariError:  (25)

Attachments (1)

11836.patch (23.9 KB) - added by jdemeyer 8 years ago.

Download all attachments as: .zip

Change History (38)

comment:1 Changed 8 years ago by leif

  • Cc jdemeyer added
  • Description modified (diff)
  • Summary changed from pari bug in gens_reduced to PARI bug in gens_reduced()

comment:2 Changed 8 years ago by jdemeyer

  • Description modified (diff)

comment:3 Changed 8 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Status changed from new to needs_review

comment:4 Changed 8 years ago by jdemeyer

  • Dependencies set to #11130

comment:5 Changed 8 years ago by jdemeyer

  • Component changed from commutative algebra to number fields
  • Owner changed from malb to jdemeyer

comment:6 Changed 8 years ago by jdemeyer

  • Summary changed from PARI bug in gens_reduced() to gens_reduced() does not handle "large" ideals

comment:7 Changed 8 years ago by jdemeyer

  • Description modified (diff)

comment:8 Changed 8 years ago by mstreng

  • Cc mstreng added

comment:9 Changed 8 years ago by mstreng

  • Cc cremona added

I get:

marco@fermat:~/sage-4.7.2.alpha2/devel/sage$ hg qpush
applying 11836.patch
sage/rings/integer.pyx</pre>: No such file or directory
now at: 11836.patch

on a copy of John's 4.7.2.alpha2 with #11130 included. And the file integer.pyx was not patched. What happened?

comment:10 Changed 8 years ago by mstreng

Oops, clicked the wrong link :$ that was HTML, sorry.

comment:11 Changed 8 years ago by mstreng

  • Reviewers set to Marco Streng

Ok, now I get (with #11130 and 11836.patch):

***   Warning: precision too low for generators, not given.

even though I do get correct output.

Example:

sage: K.<a> = NumberField(x^2+x-58)
sage: p = 613224584287432205092056925860654065041482770538957925076607095244391171340391841
sage: P = K.ideal(p).factor()[0][0]
sage: P
  ***   Warning: precision too low for generators, not given.
Fractional ideal (49582667258207098257547477827105364096774*a + 402403512193607551973543413116828658131543)
sage: P.gens_reduced()
  ***   Warning: precision too low for generators, not given.
(49582667258207098257547477827105364096774*a + 402403512193607551973543413116828658131543,)
sage: _[0].norm().abs() == p
True

comment:12 follow-ups: Changed 8 years ago by jdemeyer

I don't think I can easily disable that warning (without disabling all warnings from PARI), so I think we just have to live with it.

comment:13 in reply to: ↑ 12 Changed 8 years ago by mstreng

Replying to jdemeyer:

I don't think I can easily disable that warning (without disabling all warnings from PARI), so I think we just have to live with it.

Ok. In that case, could you explain the warning in the documentation and add it to the examples? I was very confused by it.

Of course it also appears when gens_reduced isn't called directly, so there are a lot of functions where you can choose add it or not.

comment:14 follow-up: Changed 8 years ago by mstreng

Looking at the patch right now. Passed all tests, building documentation.

Question now that I'm making comments anyway: between lines 1060 and 1061, should/could you add self.__is_principal = ...? Just in case some method comes into existence later that sets __ideal_class_log without setting __is_principal.

sage: K.<a> = QuadraticField(-5)
sage: P = K.ideal(3).factor()[0][0]
sage: P.is_principal()
False
sage: P = K.ideal(3).factor()[0][0]
sage: P.__ideal_class_log = [1]
sage: P.is_principal()
AttributeError: 'NumberFieldFractionalIdeal' object has no attribute '_NumberFieldIdeal__is_principal'

Also, the use of v[1] in 1073 requires some complicated logic to see that it is really defined. I think it could lead to bugs when other people edit your code later without realising this.

(p.s. I'm not setting anything to "needs work" for any of this.)

comment:15 in reply to: ↑ 12 ; follow-up: Changed 8 years ago by mstreng

Replying to jdemeyer:

I don't think I can easily disable that warning (without disabling all warnings from PARI), so I think we just have to live with it.

Actually, you could try to avoid bnf.bnfisprincipal(self.pari_hnf(), 1) whenever gens_needed=True. That may even save time, as it saves a call to bnfisprincipal in some cases. I'm afraid it would mean throwing a lot of stuff around in __cache_... though.

comment:16 Changed 8 years ago by mstreng

Ok, so here's something that really puzzles me:

sage: P
  ***   Warning: precision too low for generators, not given.
Fractional ideal (49582667258207098257547477827105364096774*a + 402403512193607551973543413116828658131543)
sage: P
  ***   Warning: precision too low for generators, not given.
Fractional ideal (49582667258207098257547477827105364096774*a + 402403512193607551973543413116828658131543)

I get the warning twice, indicating that something isn't cached!

In fact, if I do

sage: trace('P.is_principal()')

twice, then I get the following each time:

-> 1068             self.__ideal_class_log = list(v[0])

So you're setting self.__ideal_class_log, but the next time, if not hasattr(self, "__ideal_class_log") is False again!

comment:17 in reply to: ↑ 15 ; follow-up: Changed 8 years ago by mstreng

Replying to mstreng

Wait, why use flag=1 at all in bnfisprincipal? flag=1 is the (only) one that gives the warning. So if you replace flag=1 by flag=0 or flag=2 on line 1067, then that removes the warning.

More importantly: flag=2 (as opposed to 0 or 1) makes sure that __ideal_class_log is really correct by doubling the precision if necessary. That would fix a bug that we haven't even found yet! It doesn't slow correct answers down, as it only doubles the precision until we know __ideal_class_log; it does not continue on until we know a generator.

sage: K.<a> = NumberField(x^2+x-58)
sage: p = 613224584287432205092056925860654065041482770538957925076607095244391171340391841
sage: P = K.ideal(p).factor()[0][0]
sage: bnf = P.number_field().pari_bnf()
sage: bnf.bnfisprincipal(P.pari_hnf(), 0)
[]~
sage: bnf.bnfisprincipal(P.pari_hnf(), 1)
  ***   Warning: precision too low for generators, not given.
[[]~, []~]
sage: bnf.bnfisprincipal(P.pari_hnf(), 2)
[]~
sage: bnf.bnfisprincipal(P.pari_hnf(), 3)
[[]~, [402403512193607551973543413116828658131543, 49582667258207098257547477827105364096774]~]

comment:18 in reply to: ↑ 14 ; follow-up: Changed 8 years ago by mstreng

Ok, sorry for the amount of posts. I'm done reading the patch, and it looks good. So let me sum things up:

Could you...

  • replace flag 1 by flag 2 in bnfisprincipal to fix one more bug, and remove the confusing pari warnings all at the same time!
  • find out why caching doesn't seem to work. Is the problem a difference between hasattr and catching AttributeError? see mstreng
  • while you're doing the above, think about the minor things of mstreng?

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

Replying to mstreng:

Replying to mstreng

Wait, why use flag=1 at all in bnfisprincipal? flag=1 is the (only) one that gives the warning. So if you replace flag=1 by flag=0 or flag=2 on line 1067, then that removes the warning.

More importantly: flag=2 (as opposed to 0 or 1) makes sure that __ideal_class_log is really correct by doubling the precision if necessary. That would fix a bug that we haven't even found yet! It doesn't slow correct answers down, as it only doubles the precision until we know __ideal_class_log; it does not continue on until we know a generator.

What bnfisprincipal() tries to do is to write an ideal as C_1 e_1 * ... * C_n e_n * (a), where (a) is a principal ideal and C_1, ..., C_n are fixed generators of the class group (these are determined by bnfinit() or pari_bnf() in Sage). The exponents e_1, ..., e_n are always computed but (a) is not and that is what is warning is about. The warning is never about potentially incorrect results, it essentially means "we could not easily compute (a), so we didn't bother". __ideal_class_log should always be correct, regardless of the flag.

My code uses flag=1 first because sometimes we might not care about (a). For example, if the ideal is non-principal or the user wants to know I.is_principal() without actually needing the generator.

One thing could be improved: if we know that the class group is trivial, some shortcuts can be made.

comment:20 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-4.7.2 to sage-4.7.3

comment:21 in reply to: ↑ 19 Changed 8 years ago by mstreng

Replying to jdemeyer

Hi Jeroen,

Thanks for the explanation. I understood all of that, except for __ideal_class_log always being output and always being correct. If it is, then what is the difference between flag=0 and flag=2? Are you saying that there is no difference? The documentation of bnfisprincipal from pari 2.5.0 seems to confirm what you are saying. I just realised that I was reading the documentation from 2.3.5, which suggested otherwise.

I guess that leaves only my other reason for removing flag=1:

The warning disappears if you replace flag=1 by 0, 2 or 3. This is because you only get the warning when you ask for a generator, but don't get it and don't demand it (i.e., if you choose flag=1 and the ideal is too big). The warning is confusing and worried me as a user. So I would like to either have it extensively documented in this patch, or removed. And it can be removed simply by never using flag=1, but always 0, 2, or 3.

If you simply replace flag=1 by 0, 2 or 3, then that slows your patch down in some cases. However, you could do flag=3 if gens_needed=True, and flag=0 otherwise. In other words, call bnfisprincipal only 1 time during __cache_... with the flag directly depending on gens_needed. That would not slow things down. In fact, it would speed things up in case of gens_needed=True and a big ideal.

Marco

comment:22 Changed 8 years ago by jdemeyer

New patch, hopefully fixing all issues mentioned above. The caching problem was apparently caused by double underscores, so I'm using single underscores now. I am still using flag=1 if gens_needed simply because it seems silly not to store the generator if PARI computes it anyway.

Changed 8 years ago by jdemeyer

comment:23 in reply to: ↑ 18 Changed 8 years ago by jdemeyer

Replying to mstreng:

Is the problem a difference between hasattr and catching AttributeError?

Could be but I don't feel like delving too much in the details here.

comment:24 follow-up: Changed 8 years ago by mstreng

Looks good, but no time to look at it in detail today. Could you send me a diff between the two versions (or simply tell me which parts didn't change)? That may save time.

comment:25 in reply to: ↑ 24 Changed 8 years ago by jdemeyer

Replying to mstreng:

Looks good, but no time to look at it in detail today. Could you send me a diff between the two versions (or simply tell me which parts didn't change)? That may save time.

I'm afraid I don't have a copy of the old patch.

The only parts which changed w.r.t. the old patch are:

  1. removing some underscores.
  2. the implementation of the _cache_bnfisprincipal() function, lines 1060--1076.
  3. added doctests for ideal_class_log(), lines 1123--1148.

comment:26 follow-up: Changed 8 years ago by mstreng

#11130 needs a review first

comment:27 in reply to: ↑ 26 Changed 8 years ago by jdemeyer

Replying to mstreng:

#11130 needs a review first

Why? It's not because a dependency needs review that this cannot be reviewed. Anyway, #11130 was positively reviewed against sage-4.7.2.alpha2 and I simply added a small patch to #11130 for sage-4.7.2.alpha3.

comment:28 follow-up: Changed 8 years ago by mstreng

ok, so you're saying that only that one patch of #11130 still needs a review?

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

Replying to mstreng:

ok, so you're saying that only that one patch of #11130 still needs a review?

Yes, and also the dependency #11321.

comment:30 in reply to: ↑ 29 Changed 8 years ago by mstreng

Replying to jdemeyer:

Yes, and also the dependency #11321.

Ok, so no rush for #11836 then.

comment:31 Changed 8 years ago by mstreng

Fixes all issues that I raised. Looks very good. Doctesting now...

comment:32 follow-up: Changed 8 years ago by mstreng

  • Status changed from needs_review to positive_review

Tests pass, thanks for all the work!

comment:33 in reply to: ↑ 32 Changed 8 years ago by jdemeyer

Replying to mstreng:

Tests pass, thanks for all the work!

And thanks for the reviewing!

comment:34 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-4.7.3 to sage-pending

comment:35 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-pending to sage-4.7.3

comment:36 Changed 7 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:37 Changed 7 years ago by jdemeyer

  • Merged in set to sage-4.8.alpha1
  • Milestone set to sage-4.8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.