gens_reduced() does not handle "large" ideals

[sagetrac-mirela]

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)

Depends on #11130

CC: @jdemeyer @mstreng @JohnCremona

Component: number fields

Author: Jeroen Demeyer

Reviewer: Marco Streng

Merged: sage-4.8.alpha1

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

[jdemeyer]

Author: Jeroen Demeyer

[jdemeyer]

Dependencies: #11130

[mstreng]

comment:9

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?

[mstreng]

comment:10

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

[mstreng]

Reviewer: Marco Streng

[mstreng]

comment:11

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

[jdemeyer]

comment:12

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.

[mstreng]

comment:13

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.

[mstreng]

comment:14

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

[mstreng]

comment:15

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.

[mstreng]

comment:16

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!

[mstreng]

comment:17

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

[mstreng]

comment:18

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?

[jdemeyer]

comment:19

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.

[mstreng]

comment:21

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

[jdemeyer]

comment:22

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.

[jdemeyer]

comment:23

Attachment: 11836.patch.gz

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.

[mstreng]

comment:24

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.

[jdemeyer]

comment:25

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.

[mstreng]

comment:26

#11130 needs a review first

[jdemeyer]

comment:27

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.

[mstreng]

comment:28

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

[jdemeyer]

comment:29

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.

[mstreng]

comment:30

Replying to @jdemeyer:

Yes, and also the dependency #11321.

Ok, so no rush for #11836 then.

[mstreng]

comment:31

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

[mstreng]

comment:32

Tests pass, thanks for all the work!

[jdemeyer]

comment:33

Replying to @mstreng:

Tests pass, thanks for all the work!

And thanks for the reviewing!

[jdemeyer]

Milestone sage-4.7.3 deleted

[jdemeyer]

Merged: sage-4.8.alpha1