Opened 8 years ago
Closed 8 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 )
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)
Change History (38)
comment:1 Changed 8 years ago by
- 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
- Description modified (diff)
comment:3 Changed 8 years ago by
- Status changed from new to needs_review
comment:4 Changed 8 years ago by
- Dependencies set to #11130
comment:5 Changed 8 years ago by
- Component changed from commutative algebra to number fields
- Owner changed from malb to jdemeyer
comment:6 Changed 8 years ago by
- Summary changed from PARI bug in gens_reduced() to gens_reduced() does not handle "large" ideals
comment:7 Changed 8 years ago by
- Description modified (diff)
comment:8 Changed 8 years ago by
- Cc mstreng added
comment:9 Changed 8 years ago by
- Cc cremona added
comment:10 Changed 8 years ago by
Oops, clicked the wrong link :$ that was HTML, sorry.
comment:11 Changed 8 years ago by
- 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: ↓ 13 ↓ 15 Changed 8 years ago by
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
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: ↓ 18 Changed 8 years ago by
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: ↓ 17 Changed 8 years ago by
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
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: ↓ 19 Changed 8 years ago by
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: ↓ 23 Changed 8 years ago by
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: ↓ 21 Changed 8 years ago by
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
- Milestone changed from sage-4.7.2 to sage-4.7.3
comment:21 in reply to: ↑ 19 Changed 8 years ago by
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
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
comment:23 in reply to: ↑ 18 Changed 8 years ago by
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: ↓ 25 Changed 8 years ago by
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
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:
- removing some underscores.
- the implementation of the
_cache_bnfisprincipal()
function, lines 1060--1076. - added doctests for
ideal_class_log()
, lines 1123--1148.
comment:26 follow-up: ↓ 27 Changed 8 years ago by
#11130 needs a review first
comment:27 in reply to: ↑ 26 Changed 8 years ago by
comment:28 follow-up: ↓ 29 Changed 8 years ago by
ok, so you're saying that only that one patch of #11130 still needs a review?
comment:29 in reply to: ↑ 28 ; follow-up: ↓ 30 Changed 8 years ago by
comment:30 in reply to: ↑ 29 Changed 8 years ago by
comment:31 Changed 8 years ago by
Fixes all issues that I raised. Looks very good. Doctesting now...
comment:32 follow-up: ↓ 33 Changed 8 years ago by
- 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
comment:34 Changed 8 years ago by
- Milestone changed from sage-4.7.3 to sage-pending
comment:35 Changed 8 years ago by
- Milestone changed from sage-pending to sage-4.7.3
comment:37 Changed 8 years ago by
- 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
I get:
on a copy of John's 4.7.2.alpha2 with #11130 included. And the file integer.pyx was not patched. What happened?