Opened 12 years ago

Closed 12 years ago

Last modified 12 years ago

#6044 closed enhancement (fixed)

[with patch, positive review] Enhanced reduction modulo ideals of number fields

Reported by: mtaranes Owned by: somebody
Priority: major Milestone: sage-4.0.2
Component: number theory Keywords: number fields, ideals
Cc: cremona Merged in: 4.0.2.alpha0
Authors: Maite Aranes Reviewers: John Cremona, David Loeffler
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

  1. Modify "residues" function so that it returns a canonical set of coset representatives.
  2. New "reduce" function for number field ideals that returns the canonical reduced representative of a given integral element: I.reduce(f) is an element of the set of representatives returned by I.residues().
  3. Have "inverse_mod" working for integral elements of a number field without having to coerce to the ring of integers (using existing functionality for order elements)

Patch based on 3.4.2 to follow soon.

Attachments (3)

trac_6044.patch (8.8 KB) - added by mtaranes 12 years ago.
trac_6044_review.patch (4.6 KB) - added by cremona 12 years ago.
trac_6044_rebased_and_folded.patch (9.1 KB) - added by davidloeffler 12 years ago.
Rebased to 4.0.1 and folded into one patch

Download all attachments as: .zip

Change History (11)

comment:1 follow-up: Changed 12 years ago by mabshoff

  • Milestone changed from sage-4.0 to sage-4.0.1

This is unlikely to make it into Sage 4.0, so bumping it to 4.0.1.

Cheers,

Michael

comment:2 in reply to: ↑ 1 Changed 12 years ago by cremona

Replying to mabshoff:

This is unlikely to make it into Sage 4.0, so bumping it to 4.0.1.

Cheers,

Michael

No problem, though it is likely to have been reviewed within a day or two!

Changed 12 years ago by mtaranes

comment:3 Changed 12 years ago by mtaranes

  • Summary changed from Enhanced reduction modulo ideals of number fields to [with patch, needs review] Enhanced reduction modulo ideals of number fields

Here is the patch, with the new functions, etc, and corrections for the docstrings that were affected by the change in the 'residues' function.

Changed 12 years ago by cremona

comment:4 Changed 12 years ago by cremona

  • Summary changed from [with patch, needs review] Enhanced reduction modulo ideals of number fields to [with patch, with review, needs second opinion] Enhanced reduction modulo ideals of number fields

The patch applies fine to 4.0.alpha0, and all tests in sage/rings/number_field pass.

There are some small glitches in the docstrings: in inverse_mod() in the first line, N should be I. In reduce(), there is a formatting problem which I think would go away if a space is inserted after the second in I`=self, and later on the single backquotes aroung small_residue should be double. Ans some small indentation issues (which aer oly seen as problematical when docbuild is used).

I fixed these things in the review patch (which also fixes a few minor documentation issues I noticed that are nothing to do with this ticket as such), but someone else should look at this too.

Changed 12 years ago by davidloeffler

Rebased to 4.0.1 and folded into one patch

comment:5 Changed 12 years ago by davidloeffler

  • Summary changed from [with patch, with review, needs second opinion] Enhanced reduction modulo ideals of number fields to [with patch, positive review] Enhanced reduction modulo ideals of number fields

Good stuff; it will be much more efficient to use hermite form rather than smith form in residues, besides being more canonical.

I have rebased the patch to 4.0.1, and checked that it commutes with #5842 and #6188. All tests in sage/rings/number_field pass still (on a 32-bit machine), as do those in sage/doc/en/bordeaux_2008 (which have a habit of catching out unwary number theory patch authors).

This one has been in limbo for three weeks because the trac reports of patches with review / needing review / etc are done using text searches of the summary field, and thus "with review, needs second opinion" doesn't get picked up. I guess it would be safer to set it to "needs review", but this strikes me as conclusive proof that we need to change the way we use trac -- this is the *fifth* ticket I've spotted today which has been in limbo because of a slightly unusual summary string.

comment:6 Changed 12 years ago by cremona

Many thanks for spotting this and delivering it out of limbo, especially as you had to rebase it. I have a habit of forgetting all about my own patches once I have put them up for review (and wish trac had an option to filter out those tickets which I had added a patch to which were still open).

As for SNF v. HNF it was just my stupidity in the first place which caused us to use SNF. HNF is particularly efficient since that's the form pari stores ideals in anyway.

comment:7 Changed 12 years ago by ncalexan

  • Authors set to Maite Aranes
  • Merged in set to alpha0
  • Resolution set to fixed
  • Reviewers set to John Cremona, David Loeffler
  • Status changed from new to closed

comment:8 Changed 12 years ago by mvngu

  • Merged in changed from alpha0 to 4.0.2.alpha0
Note: See TracTickets for help on using tickets.