Opened 14 years ago

Closed 14 years ago

Last modified 13 years ago

#5306 closed enhancement (fixed)

[with new patch, with positive review] More number field ideal utilities

Reported by: John Cremona Owned by: William Stein
Priority: major Milestone: sage-3.4.1
Component: number theory Keywords:
Cc: David Loeffler, Maite Aranés Merged in: 3.4.1.rc2
Authors: Maite Aranes Reviewers: David Loeffler, John Cremona
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Following #4688 which wrapped the pari functions ideallog and idealstar, we need to provide functions which access these cleanly from Sage's NumberField? and NumberFieldFractionalIdeal? classes.

Maite Aranes and John Cremona are working on this and will post a patch based on 3.3 + #4688.

Attachments (3)

nf_utilities.patch (13.7 KB) - added by John Cremona 14 years ago.
trac_5306.patch (14.7 KB) - added by John Cremona 14 years ago.
replaces previous
trac_5306-reviewer-fixes.patch (11.1 KB) - added by David Loeffler 14 years ago.
apply on top of trac_5306.patch

Download all attachments as: .zip

Change History (18)

Changed 14 years ago by John Cremona

Attachment: nf_utilities.patch added

comment:1 Changed 14 years ago by John Cremona

Cc: David Loeffler added
Priority: minormajor
Summary: More number field ideal utilities[with patch, needs review] More number field ideal utilities

The attached patch (by Maite Aranes) is based on 3.4. It provides a number of Sage functions for ideals in number fields: idealstar (multiplicative group modulo I), ideallog, idealcoprime, reduce (to reduce an element modulo an ideal) and invertible_residues_mod_units (an iterator through representatives of (R/I)^* modulo the image of a subgroup of the group of units -- something which will be needed for enumerating cusps over number fields!).

comment:2 Changed 14 years ago by David Loeffler

Summary: [with patch, needs review] More number field ideal utilities[with patch, needs work] More number field ideal utilities

The patch applies cleanly to 3.4.1.rc1, and all tests in sage/rings/number_field pass. However, there is a trivial little problem: the documentation won't build -- Sphinx crashes on trying to read number_field_ideal.py. The obvious suspect is the accented character in Maite Aranes' name in the docstring for invertible_residues_mod_units. It processes fine with the accent removed.

Also: a pedantic docstring issue -- for invertible_residues_mod_units, the docstring says: "Returns an iterator through a list of invertible residues modulo the integral ideal self and the list of units u." Firstly, I don't think that's very clear -- there's a confusion between residue classes and representatives for them. Secondly, does the list of units need to be a subgroup? I suggest: "Returns an iterator through a set of representatives for the units modulo the integral ideal self and the subgroup generated by the list of units u".

Similarly I'm not very happy with the docstring for "reduce": from what it says, one might expect to get back an element of some quotient ring structure. It should probably say something closer to what the Pari documentation says, i.e. something like "Given an element f of the ambient number field, find an element g such that f - g belongs to the (integral) ideal self, and g is small." I think that's a better explanation of what it's actually doing, particularly since it isn't generally the case that I.reduce(x) is one of the representatives returned by I.residues() (if x is non-integral but coprime to I). It might even be worth adding the remark that reduced representatives aren't necessarily unique into the docstring.

These are only very small glitches, though; with these fixed I'd be happy to give a positive review.

comment:3 Changed 14 years ago by John Cremona

Cc: Maite Aranés added

Thanks for the review -- I will see to those things soon. Funnily enough I was just talking to Maite about the accents issue, without realising that I had allowed her accent through!

For reduce, I think that "reduced_representative" might be a better name?

comment:4 Changed 14 years ago by David Loeffler

As for the name of this function: the trouble is that anything with "reduce" in the title tends to suggest that the representative returned is in some way canonical, as with the reduce_cusp command for subgroups of SL2Z; one would be led to suspect that x - y is in I if and only if I.reduce(x) = I.reduce(y). Ideally this would be true and then there is no issue. However, I'm worried by the fact that Pari provides a separate function nfeltreducemodpr where the ideal I is assumed to be prime, for which the documentation does make that uniqueness claim; this tends to suggest that it isn't true for nfeltreduce. If this doesn't hold then perhaps "small_representative" might be less dangerous.

comment:5 Changed 14 years ago by John Cremona

On invertible_residues_mod_units() it is not easy to explain what this is: Let R be the ring of integers and I the ideal (self). When there are no units given we iterate through (R/I)^*. When there are units which generate some subgroup U of the unit group R^* (which in our applications will always be all of R^*) we want to iterate through elements of R representing the elements of (R/I)^*/U_I, where U_I is the image of U in (R/I)^*.

Believe me, we need this for enumeration of cusps over number fields for the subgroup Gamma_0(n) where n is an ideal in GL(2,R)!. Now I need to find a way of writing that succinctly in a docstring. [The special case where U is [] will be of most use to most people, so we could provide a clear indication of how to use that.]

On reduce: I'll need to check whether the element being reduced also needs to be integral (I suspect so) and adapt the docstring if so.

Changed 14 years ago by John Cremona

Attachment: trac_5306.patch added

replaces previous

comment:6 Changed 14 years ago by John Cremona

Summary: [with patch, needs work] More number field ideal utilities[with new patch, needs review again] More number field ideal utilities

The new patch trac_5306.patch addresses the issues raised in the review (removes the accent, gives better descriptions of the functions, and does a little more tidying up). It replaces the earlier patch. (This makes it easier to apply, but harder to see what changed I made!)

comment:7 Changed 14 years ago by David Loeffler

At risk of being really ridiculously pedantic: there's a typo in the new docstring for invertible_residues_mod_units (and invertible_residues): "represnting".

Also, as for our terminological confusion, I think that the whole thing can be explained more clearly by *not* distinguishing between "units" and "invertible residues". You're clearly thinking of taking the quotient of a local unit group by the image of a subgroup of the global units; but the function as coded here works perfectly well for finding any quotient of the form (O_K / I)* / U where U is an arbitrary subgroup of (O_K / I)*. E.g.

sage: K.<a> = NumberField(x - 1)
sage: I = K.ideal(5)
sage: list(I.invertible_residues_mod_units([4]))
[1, 2]

The fact that 4 isn't a unit in K is no problem. And this makes it easier to avoid getting tied up in terminological knots: we can now just drop all mention of "units", and call it "invertible_residues_mod", with the docstring

"Returns an iterator through a set of representatives for the group of invertible residues modulo this ideal, modulo the subgroup generated by the elements in the list u."

I think I've tortured you (and Maite) enough now: I'll write a patch myself for this change, and if you agree it's OK we'll call it a +ve review.

(I'll also fix a micro-bug: the invertible_residues function ignores its second argument -- it always calls invertible_residues_mod_units with reduce = True.)

comment:8 Changed 14 years ago by John Cremona

Thanks, David -- you are 100% right and I look forward to seeing your version. Another case of reviewing producing better, more usable code & functions (in case William is listening!). John

Changed 14 years ago by David Loeffler

apply on top of trac_5306.patch

comment:9 Changed 14 years ago by David Loeffler

OK, here's another patch, which renames the function to just "invertible_residues_mod" and tidies up the docstrings a bit. If you're happy with it, then let's call that a positive review.

comment:10 Changed 14 years ago by John Cremona

Summary: [with new patch, needs review again] More number field ideal utilities[with new patch, with positive review] More number field ideal utilities

I am entirely happy with David's extra patch which only improves the wording and typography of docstrings and makes a sensible change to the name of one function; so I have changed the status to "positive review", as agreed.

PS I suppose that we should really add a doctest to show that the things now called subgp_gens need not be units, e.g.

sage: list(QuadraticField(-1,'i').ideal(7).invertible_residues_mod([2,i]))
[1, -2*i + 1, 3*i - 3, 2*i + 3]

comment:11 Changed 14 years ago by David Loeffler

I already added a doctest showing that the elements involved need not be integral, let alone units, as long as they are coprime to the ideal -- see number_field_ideal_rel.py, line 1445.

comment:12 Changed 14 years ago by David Loeffler

PS: Sorry, I mean number_field_ideal.py of course.

comment:13 in reply to:  12 Changed 14 years ago by John Cremona

Replying to davidloeffler:

PS: Sorry, I mean number_field_ideal.py of course.

OK, found it -- sorry to doubt you!

comment:14 Changed 14 years ago by Michael Abshoff

Milestone: sage-3.4.2sage-3.4.1
Resolution: fixed
Status: newclosed

Merged trac_5306.patch and trac_5306-reviewer-fixes.patch in Sage 3.4.1.rc2.

Cheers,

Michael

comment:15 Changed 13 years ago by David Loeffler

Authors: Maite Aranes
Merged in: 3.4.1.rc2
Reviewers: David Loeffler, John Cremona
Note: See TracTickets for help on using tickets.