Opened 9 years ago

Closed 9 years ago

# gens_reduced() does not handle "large" ideals

Reported by: Owned by: mirela jdemeyer major sage-4.8 number fields jdemeyer, mstreng, cremona sage-4.8.alpha1 Jeroen Demeyer Marco Streng N/A #11130

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)

```

### comment:1 Changed 9 years ago by leif

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

### comment:2 Changed 9 years ago by jdemeyer

• Description modified (diff)

### comment:3 Changed 9 years ago by jdemeyer

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

### comment:4 Changed 9 years ago by jdemeyer

• Dependencies set to #11130

### comment:5 Changed 9 years ago by jdemeyer

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

### comment:6 Changed 9 years ago by jdemeyer

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

### comment:7 Changed 9 years ago by jdemeyer

• Description modified (diff)

### comment:9 Changed 9 years ago by mstreng

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 9 years ago by mstreng

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

### comment:11 Changed 9 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: ↓ 13 ↓ 15 Changed 9 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 9 years ago by mstreng

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 9 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: ↓ 17 Changed 9 years ago by mstreng

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 9 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: ↓ 19 Changed 9 years ago by 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 9 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: ↓ 21 Changed 9 years ago by jdemeyer

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 9 years ago by jdemeyer

• Milestone changed from sage-4.7.2 to sage-4.7.3

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

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

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

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 9 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 9 years ago by jdemeyer

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: ↓ 27 Changed 9 years ago by mstreng

#11130 needs a review first

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

#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: ↓ 29 Changed 9 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: ↓ 30 Changed 9 years ago by jdemeyer

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 9 years ago by mstreng

Yes, and also the dependency #11321.

Ok, so no rush for #11836 then.

### comment:31 Changed 9 years ago by mstreng

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

### comment:32 follow-up: ↓ 33 Changed 9 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 9 years ago by jdemeyer

Tests pass, thanks for all the work!

And thanks for the reviewing!

### comment:34 Changed 9 years ago by jdemeyer

• Milestone changed from sage-4.7.3 to sage-pending

### comment:35 Changed 9 years ago by jdemeyer

• Milestone changed from sage-pending to sage-4.7.3

### comment:36 Changed 9 years ago by jdemeyer

• Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

### comment:37 Changed 9 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.