Opened 15 years ago

Closed 14 years ago

#1951 closed defect (fixed)

[with patch, positive review] reduction map modulo a number field prime ideal still not 100% done

Reported by: William Stein Owned by: William Stein
Priority: major Milestone: sage-3.1.3
Component: number theory Keywords: number field residue field reduction
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

This should work:

sage: K.<i> = NumberField(x^2 + 1)
sage: P = [g[0] for g in K.factor_integer(5)]; P
[Fractional ideal (-i - 2), Fractional ideal (2*i + 1)]
sage: a = 1/(1+2*i)
sage: K = [g.residue_field() for g in P]; K
[Residue field of Fractional ideal (-i - 2), Residue field of Fractional ideal (2*i + 1)]
sage: F = K[0]
sage: a.valuation(P[0])
0
sage: F(i/7)
4
sage: F(a)
Traceback (most recent call last):
...
ZeroDivisionError: Inverse does not exist.

The problem is that a in terms of a basis for the maximal order still has some 5's in the denominator, even though a is P[0]-integral. To fix this in general, one could:

  1. Find an element b of the ring of integers that is 1 modulo P[0] and is 0 modulo all the other P[i] (using the not-implemented-right now CRT),
  1. Multiply a through by some power of b.
  1. Reduce.
  1. Divide back through by the reduction of b.

Attachments (2)

1951-residues.patch (5.9 KB) - added by John Cremona 14 years ago.
1951-residues-1.patch (1.3 KB) - added by John Cremona 14 years ago.

Download all attachments as: .zip

Change History (6)

Changed 14 years ago by John Cremona

Attachment: 1951-residues.patch added

comment:1 Changed 14 years ago by John Cremona

Keywords: number field residue field reduction added
Summary: reducation map modulo a number field prime ideal still not 100% done[with patch, needs review] reducation map modulo a number field prime ideal still not 100% done

The patch fixes this, so that any element which is P-integral can be reduced modulo P (non-P-integral elements will raise a ZeroDivisionError? with an explanation).

It took a long time to find out where to put the new code, since the structure of the residue fields and reduction maps code is so byzantine! In the end the solution was not hard, though I used a different method from what was suggested (see comments in the patch).

The new code is in sage.rings.residue_field.pyx; I also put a doctest into number_field.number_field_ideal.py.

By the way, it is not really necessary to use recursion since when the function calls itself it always bottoms out right away. So it would be easy to rewrite it without any; I just found it easier to write self(nx) than self.__F(self.__to_vs(nx) * self.__PBinv) and similar.

Changed 14 years ago by John Cremona

Attachment: 1951-residues-1.patch added

comment:2 Changed 14 years ago by John Cremona

It's a small thing but I just noticed that the number field function residue_field() has this definition:

    def residue_field(self, prime, names = None, check = False):

where the "check" parameter claims to control whether "prime" really is prime, but this is ignored. It should be passed down through the call to sage.rings.residue_field.ResidueField(prime, names = names) which does honour the check parameter.

Example:

sage: K.<i> = NumberField(x^2 + 1)
sage: Q = K.ideal(5)
sage: Q.is_prime()
False
sage: K.residue_field(Q, check=False)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)

/home/john/sage-3.1.2.rc1/devel/<ipython console> in <module>()

/home/john/sage-3.1.2.rc1/local/lib/python2.5/site-packages/sage/rings/number_field/number_field.py in residue_field(self, prime, names, check)
   3000             raise ValueError, "prime must be a prime ideal of self"
   3001         import sage.rings.residue_field
-> 3002         return sage.rings.residue_field.ResidueField(prime, names = names)
   3003 
   3004     def signature(self):

/home/john/sage-3.1.2.rc1/devel/residue_field.pyx in sage.rings.residue_field.ResidueField (sage/rings/residue_field.c:2778)()

ValueError: p must be prime

The second patch fixes this. Note that the default was "check=False", while the called function ResidueField?() has its default as "check=True". I thought it safer to change the deafult to "check=True" since this makes the new default behaviour like the old behaviour. (If you use check=False and the ideal is not prime, the first error which arises is a bit obscure:

    AttributeError: 'NumberFieldFractionalIdeal' object has no attribute '_NumberFieldIdeal__smallest_integer'

since smallest_integer() is defined only for prime ideals. But something has to go wrong at some point in this situation, and at least now it will only happen when the user has deliberately turned off checking.

comment:3 Changed 14 years ago by Alex Ghitza

Summary: [with patch, needs review] reducation map modulo a number field prime ideal still not 100% done[with patch, positive review] reduction map modulo a number field prime ideal still not 100% done

Looks good, applies cleanly against 3.1.2, and passes relevant doctests (checked sage/rings, sage/schemes, and sage/modular).

comment:4 Changed 14 years ago by Michael Abshoff

Resolution: fixed
Status: newclosed

Merged in Sage 3.1.3.alpha1

Note: See TracTickets for help on using tickets.