Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
""" Number Field Ideals
AUTHORS:
- Steven Sivek (2005-05-16)
- William Stein (2007-09-06): vastly improved the doctesting
- William Stein and John Cremona (2007-01-28): new class NumberFieldFractionalIdeal now used for all except the 0 ideal
- Radoslav Kirov and Alyson Deines (2010-06-22): prime_to_S_part, is_S_unit, is_S_integral
We test that pickling works::
sage: K.<a> = NumberField(x^2 - 5) sage: I = K.ideal(2/(5+a)) sage: I == loads(dumps(I)) True """
#***************************************************************************** # Copyright (C) 2004 William Stein <wstein@gmail.com> # # Distributed under the terms of the GNU General Public License (GPL) # # This code is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU # General Public License for more details. # # The full text of the GPL is available at: # # http://www.gnu.org/licenses/ #***************************************************************************** from __future__ import absolute_import from six.moves import range
SMALL_DISC = 1000000
import sage.libs.all
import sage.misc.latex as latex
import sage.rings.rational_field as rational_field import sage.rings.integer_ring as integer_ring import sage.arith.all as arith import sage.misc.misc as misc from sage.rings.finite_rings.finite_field_constructor import FiniteField
from sage.rings.ideal import (Ideal_generic, Ideal_fractional) from sage.misc.all import prod from sage.misc.mrange import xmrange_iter from sage.misc.cachefunc import cached_method from sage.structure.element import MultiplicativeGroupElement from sage.structure.factorization import Factorization from sage.structure.sequence import Sequence from sage.structure.proof.proof import get_flag from sage.structure.richcmp import richcmp
QQ = rational_field.RationalField() ZZ = integer_ring.IntegerRing()
class NumberFieldIdeal(Ideal_generic): """ An ideal of a number field. """ def __init__(self, field, gens, coerce=True): """ INPUT:
- ``field`` - a number field
- ``x`` - a list of NumberFieldElements belonging to the field
EXAMPLES::
sage: K.<i> = NumberField(x^2 + 1) sage: K.ideal(7) Fractional ideal (7)
Initialization from PARI::
sage: K.ideal(pari(7)) Fractional ideal (7) sage: K.ideal(pari(4), pari(4 + 2*i)) Fractional ideal (2) sage: K.ideal(pari("i + 2")) Fractional ideal (i + 2) sage: K.ideal(pari("[3,0;0,3]")) Fractional ideal (3) sage: F = pari(K).idealprimedec(5) sage: K.ideal(F[0]) Fractional ideal (2*i + 1)
TESTS:
Check that _pari_prime is set when initializing from a PARI prime ideal::
sage: K.ideal(pari(K).idealprimedec(5)[0])._pari_prime [5, [-2, 1]~, 1, 1, [2, -1; 1, 2]]
Number fields defined by non-monic and non-integral polynomials are supported (:trac:`252`)::
sage: K.<a> = NumberField(2*x^2 - 1/3) sage: I = K.ideal(a); I Fractional ideal (a) sage: I.norm() 1/6 """ raise TypeError("field (=%s) must be a number field."%field)
gens = gens[0] # Init from PARI # Assume columns are generators # Assume prime ideal form else: # Assume one element of the field raise ValueError("gens must have length at least 1 (zero ideal is not a fractional ideal)")
def __hash__(self): """ EXAMPLES::
sage: NumberField(x^2 + 1, 'a').ideal(7).__hash__() # random 7806919040325273549 """ # At some point in the future (e.g., for relative extensions), # we'll likely have to consider other hashes.
def _latex_(self): r""" EXAMPLES::
sage: K.<a> = NumberField(x^2 + 23) sage: K.ideal([2, 1/2*a - 1/2])._latex_() '\\left(2, \\frac{1}{2} a - \\frac{1}{2}\\right)' sage: latex(K.ideal([2, 1/2*a - 1/2])) \left(2, \frac{1}{2} a - \frac{1}{2}\right)
The gens are reduced only if the norm of the discriminant of the defining polynomial is at most sage.rings.number_field.number_field_ideal.SMALL_DISC::
sage: K.<a> = NumberField(x^2 + 902384092834); K Number Field in a with defining polynomial x^2 + 902384092834 sage: I = K.factor(19)[0][0]; I._latex_() '\\left(19\\right)'
We can make the generators reduced by increasing SMALL_DISC. We had better also set proof to False, or computing reduced gens could take too long::
sage: proof.number_field(False) sage: sage.rings.number_field.number_field_ideal.SMALL_DISC = 10^20 sage: K.<a> = NumberField(x^4 + 3*x^2 - 17) sage: K.ideal([17*a,17,17,17*a])._latex_() '\\left(17\\right)'
TESTS:
Reset SMALL_DISC for continued testing::
sage: sage.rings.number_field.number_field_ideal.SMALL_DISC = 1000000 """
def _richcmp_(self, other, op): """ Compare an ideal of a number field to something else.
REMARK:
By default, comparing ideals is the same as comparing their generator list. But of course, different generators can give rise to the same ideal. And this can easily be detected using Hermite normal form.
EXAMPLES::
sage: K.<a> = NumberField(x^2 + 3); K Number Field in a with defining polynomial x^2 + 3 sage: f = K.factor(15); f (Fractional ideal (-a))^2 * (Fractional ideal (5)) sage: (f[0][0] < f[1][0]) True sage: (f[0][0] == f[0][0]) True sage: (f[1][0] > f[0][0]) True sage: f[1][0] == 5 True sage: f[1][0] == GF(7)(5) False
TESTS::
sage: L.<b> = NumberField(x^8-x^4+1) sage: F_2 = L.fractional_ideal(b^2-1) sage: F_4 = L.fractional_ideal(b^4-1) sage: F_2 == F_4 True """ return NotImplemented
def _mul_(self, other): """ Returns the product of self and other.
This is implemented by just calling pari to do the multiplication.
EXAMPLES::
sage: K.<I>=QQ[i] sage: A = K.ideal([5, 2 + I]) sage: B = K.ideal([13, 5 + 12*I]) sage: A*B Fractional ideal (4*I - 7) sage: (K.ideal(3 + I) * K.ideal(7 + I)).gens() (10*I + 20,)
TESTS:
Make sure that :trac:`13958` is fixed::
sage: I = QuadraticField(-5).ideal(2).factor()[0][0] sage: I = I * I * I; I.ngens() == 2 True sage: I = I^301; I.ngens() == 2 True """
def coordinates(self, x): r""" Returns the coordinate vector of `x` with respect to this ideal.
INPUT: ``x`` -- an element of the number field (or ring of integers) of this ideal.
OUTPUT: List giving the coordinates of `x` with respect to the integral basis of the ideal. In general this will be a vector of rationals; it will consist of integers if and only if `x` is in the ideal.
AUTHOR: John Cremona 2008-10-31
ALGORITHM:
Uses linear algebra. Provides simpler implementations for ``_contains_()``, ``is_integral()`` and ``smallest_integer()``.
EXAMPLES::
sage: K.<i> = QuadraticField(-1) sage: I = K.ideal(7+3*i) sage: Ibasis = I.integral_basis(); Ibasis [58, i + 41] sage: a = 23-14*i sage: acoords = I.coordinates(a); acoords (597/58, -14) sage: sum([Ibasis[j]*acoords[j] for j in range(2)]) == a True sage: b = 123+456*i sage: bcoords = I.coordinates(b); bcoords (-18573/58, 456) sage: sum([Ibasis[j]*bcoords[j] for j in range(2)]) == b True sage: J = K.ideal(0) sage: J.coordinates(0) () sage: J.coordinates(1) Traceback (most recent call last): ... TypeError: vector is not in free module """
def _contains_(self, x): """ Return True if x is an element of this ideal.
This function is called (indirectly) when the ``in`` operator is used.
EXAMPLES::
sage: K.<a> = NumberField(x^2 + 23); K Number Field in a with defining polynomial x^2 + 23 sage: I = K.factor(13)[0][0]; I Fractional ideal (13, 1/2*a + 9/2) sage: I._contains_(a) False sage: a in I False sage: 13 in I True sage: 13/2 in I False sage: a + 9 in I True sage: J = K.ideal(0) sage: 0 in J True sage: 1 in J False
sage: K.<a> = NumberField(x^4 + 3); K Number Field in a with defining polynomial x^4 + 3 sage: I = K.factor(13)[0][0] sage: I # random sign in output Fractional ideal (-2*a^2 - 1) sage: 2/3 in I False sage: 1 in I False sage: 13 in I True sage: 1 in I*I^(-1) True sage: I # random sign in output Fractional ideal (-2*a^2 - 1)
sage: K.<y>=NumberField(x^2-3) sage: L.<z>=K.extension(x^2-5) sage: 0 in L.ideal(0) True sage: 1 in L.ideal(0) False """
def __elements_from_hnf(self, hnf): """ Convert a PARI Hermite normal form matrix to a list of NumberFieldElements.
EXAMPLES::
sage: K.<a> = NumberField(x^3 + 389); K Number Field in a with defining polynomial x^3 + 389 sage: I = K.factor(17)[0][0] sage: I # random sign in generator Fractional ideal (-100*a^2 + 730*a - 5329) sage: hnf = I.pari_hnf(); hnf [17, 0, 13; 0, 17, 8; 0, 0, 1] sage: I._NumberFieldIdeal__elements_from_hnf(hnf) [17, 17*a, a^2 + 8*a + 13] sage: I._NumberFieldIdeal__elements_from_hnf(hnf^(-1)) [1/17, 1/17*a, a^2 - 8/17*a - 13/17] """
def __repr__(self): """ Return the string representation of this number field ideal.
.. note::
Only the zero ideal actually has type NumberFieldIdeal; all others have type NumberFieldFractionalIdeal. So this function will only ever be called on the zero ideal.
EXAMPLES::
sage: K.<a> = NumberField(x^3-2) sage: I = K.ideal(0); I Ideal (0) of Number Field in a with defining polynomial x^3 - 2 sage: type(I) <class 'sage.rings.number_field.number_field_ideal.NumberFieldIdeal'> sage: I = K.ideal(1); I Fractional ideal (1) sage: type(I) <class 'sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal'> sage: I = K.ideal(a); I Fractional ideal (a) sage: type(I) <class 'sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal'> sage: I = K.ideal(1/a); I Fractional ideal (1/2*a^2) sage: type(I) <class 'sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal'> """
def _repr_short(self): """ Compact string representation of this ideal. When the norm of the discriminant of the defining polynomial of the number field is less than
sage.rings.number_field.number_field_ideal.SMALL_DISC
then display reduced generators. Otherwise display two generators.
EXAMPLES::
sage: K.<a> = NumberField(x^4 + 389); K Number Field in a with defining polynomial x^4 + 389 sage: I = K.factor(17)[0][0]; I Fractional ideal (17, a^2 + 6) sage: I._repr_short() '(17, a^2 + 6)'
We use reduced gens, because the discriminant is small::
sage: K.<a> = NumberField(x^2 + 17); K Number Field in a with defining polynomial x^2 + 17 sage: I = K.factor(17)[0][0]; I Fractional ideal (a)
Here the discriminant is 'large', so the gens aren't reduced::
sage: sage.rings.number_field.number_field_ideal.SMALL_DISC 1000000 sage: K.<a> = NumberField(x^2 + 902384094); K Number Field in a with defining polynomial x^2 + 902384094 sage: I = K.factor(19)[0][0]; I Fractional ideal (19, a + 5) sage: I.gens_reduced() (19, a + 5) """
def _gens_repr(self): """ Returns tuple of generators to be used for printing this number field ideal. The gens are reduced only if the absolute value of the norm of the discriminant of the defining polynomial is at most sage.rings.number_field.number_field_ideal.SMALL_DISC.
EXAMPLES::
sage: sage.rings.number_field.number_field_ideal.SMALL_DISC 1000000 sage: K.<a> = NumberField(x^4 + 3*x^2 - 17) sage: K.discriminant() # too big -1612688 sage: I = K.ideal([17*a*(2*a-2),17*a*(2*a-3)]); I._gens_repr() (289, 17*a) sage: I.gens_reduced() (17*a,) """ # If the discriminant is small, it is easy to find nice gens. # Otherwise it is potentially very hard. except TypeError: # In some cases with relative extensions, computing the # discriminant of the defining polynomial is not # supported. pass # Return two generators unless the second one is zero else:
def __pari__(self): """ Returns PARI Hermite Normal Form representations of this ideal.
EXAMPLES::
sage: K.<w> = NumberField(x^2 + 23) sage: I = K.class_group().0.ideal(); I Fractional ideal (2, 1/2*w - 1/2) sage: I.__pari__() [2, 0; 0, 1] """
def _pari_init_(self): """ Returns self in PARI Hermite Normal Form as a string
EXAMPLES::
sage: K.<w> = NumberField(x^2 + 23) sage: I = K.class_group().0.ideal() sage: I._pari_init_() '[2, 0; 0, 1]' """
def pari_hnf(self): """ Return PARI's representation of this ideal in Hermite normal form.
EXAMPLES::
sage: R.<x> = PolynomialRing(QQ) sage: K.<a> = NumberField(x^3 - 2) sage: I = K.ideal(2/(5+a)) sage: I.pari_hnf() [2, 0, 50/127; 0, 2, 244/127; 0, 0, 2/127] """
@cached_method def basis(self): r""" Return a basis for this ideal viewed as a `\ZZ` -module.
OUTPUT:
An immutable sequence of elements of this ideal (note: their parent is the number field) forming a basis for this ideal.
EXAMPLES::
sage: K.<z> = CyclotomicField(7) sage: I = K.factor(11)[0][0] sage: I.basis() # warning -- choice of basis can be somewhat random [11, 11*z, 11*z^2, z^3 + 5*z^2 + 4*z + 10, z^4 + z^2 + z + 5, z^5 + z^4 + z^3 + 2*z^2 + 6*z + 5]
An example of a non-integral ideal.::
sage: J = 1/I sage: J # warning -- choice of generators can be somewhat random Fractional ideal (2/11*z^5 + 2/11*z^4 + 3/11*z^3 + 2/11) sage: J.basis() # warning -- choice of basis can be somewhat random [1, z, z^2, 1/11*z^3 + 7/11*z^2 + 6/11*z + 10/11, 1/11*z^4 + 1/11*z^2 + 1/11*z + 7/11, 1/11*z^5 + 1/11*z^4 + 1/11*z^3 + 2/11*z^2 + 8/11*z + 7/11]
Number fields defined by non-monic and non-integral polynomials are supported (:trac:`252`)::
sage: K.<a> = NumberField(2*x^2 - 1/3) sage: K.ideal(a).basis() [1, a] """
@cached_method def free_module(self): r""" Return the free `\ZZ`-module contained in the vector space associated to the ambient number field, that corresponds to this ideal.
EXAMPLES::
sage: K.<z> = CyclotomicField(7) sage: I = K.factor(11)[0][0]; I Fractional ideal (-2*z^4 - 2*z^2 - 2*z + 1) sage: A = I.free_module() sage: A # warning -- choice of basis can be somewhat random Free module of degree 6 and rank 6 over Integer Ring User basis matrix: [11 0 0 0 0 0] [ 0 11 0 0 0 0] [ 0 0 11 0 0 0] [10 4 5 1 0 0] [ 5 1 1 0 1 0] [ 5 6 2 1 1 1]
However, the actual `\ZZ`-module is not at all random::
sage: A.basis_matrix().change_ring(ZZ).echelon_form() [ 1 0 0 5 1 1] [ 0 1 0 1 1 7] [ 0 0 1 7 6 10] [ 0 0 0 11 0 0] [ 0 0 0 0 11 0] [ 0 0 0 0 0 11]
The ideal doesn't have to be integral::
sage: J = I^(-1) sage: B = J.free_module() sage: B.echelonized_basis_matrix() [ 1/11 0 0 7/11 1/11 1/11] [ 0 1/11 0 1/11 1/11 5/11] [ 0 0 1/11 5/11 4/11 10/11] [ 0 0 0 1 0 0] [ 0 0 0 0 1 0] [ 0 0 0 0 0 1]
This also works for relative extensions::
sage: K.<a,b> = NumberField([x^2 + 1, x^2 + 2]) sage: I = K.fractional_ideal(4) sage: I.free_module() Free module of degree 4 and rank 4 over Integer Ring User basis matrix: [ 4 0 0 0] [ -3 7 -1 1] [ 3 7 1 1] [ 0 -10 0 -2] sage: J = I^(-1); J.free_module() Free module of degree 4 and rank 4 over Integer Ring User basis matrix: [ 1/4 0 0 0] [-3/16 7/16 -1/16 1/16] [ 3/16 7/16 1/16 1/16] [ 0 -5/8 0 -1/8]
An example of intersecting ideals by intersecting free modules.::
sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8) sage: I = K.factor(2) sage: p1 = I[0][0]; p2 = I[1][0] sage: N = p1.free_module().intersection(p2.free_module()); N Free module of degree 3 and rank 3 over Integer Ring Echelon basis matrix: [ 1 1/2 1/2] [ 0 1 1] [ 0 0 2] sage: N.index_in(p1.free_module()).abs() 2
TESTS:
Sage can find the free module associated to quite large ideals quickly (see :trac:`4627`)::
sage: y = polygen(ZZ) sage: M.<a> = NumberField(y^20 - 2*y^19 + 10*y^17 - 15*y^16 + 40*y^14 - 64*y^13 + 46*y^12 + 8*y^11 - 32*y^10 + 8*y^9 + 46*y^8 - 64*y^7 + 40*y^6 - 15*y^4 + 10*y^3 - 2*y + 1) sage: M.ideal(prod(prime_range(6000, 6200))).free_module() Free module of degree 20 and rank 20 over Integer Ring User basis matrix: 20 x 20 dense matrix over Rational Field """
def reduce_equiv(self): """ Return a small ideal that is equivalent to self in the group of fractional ideals modulo principal ideals. Very often (but not always) if self is principal then this function returns the unit ideal.
ALGORITHM: Calls pari's idealred function.
EXAMPLES::
sage: K.<w> = NumberField(x^2 + 23) sage: I = ideal(w*23^5); I Fractional ideal (6436343*w) sage: I.reduce_equiv() Fractional ideal (1) sage: I = K.class_group().0.ideal()^10; I Fractional ideal (1024, 1/2*w + 979/2) sage: I.reduce_equiv() Fractional ideal (2, 1/2*w - 1/2) """
def gens_reduced(self, proof=None): r""" Express this ideal in terms of at most two generators, and one if possible.
This function indirectly uses ``bnfisprincipal``, so set ``proof=True`` if you want to prove correctness (which *is* the default).
EXAMPLES::
sage: R.<x> = PolynomialRing(QQ) sage: K.<a> = NumberField(x^2 + 5) sage: K.ideal(0).gens_reduced() (0,) sage: J = K.ideal([a+2, 9]) sage: J.gens() (a + 2, 9) sage: J.gens_reduced() # random sign (a + 2,) sage: K.ideal([a+2, 3]).gens_reduced() (3, a + 2)
TESTS::
sage: len(J.gens_reduced()) == 1 True
sage: all(j.parent() is K for j in J.gens()) True sage: all(j.parent() is K for j in J.gens_reduced()) True
sage: K.<a> = NumberField(x^4 + 10*x^2 + 20) sage: J = K.prime_above(5) sage: J.is_principal() False sage: J.gens_reduced() (5, a) sage: all(j.parent() is K for j in J.gens()) True sage: all(j.parent() is K for j in J.gens_reduced()) True
Make sure this works with large ideals (:trac:`11836`)::
sage: R.<x> = QQ['x'] sage: L.<b> = 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*b^9 + 2472249905907/195061146840302336*b^8 + 916693155514421/2145672615243325696*b^7 + 1348520950997779/2145672615243325696*b^6 - 82344497086595/12191321677518896*b^5 + 2627122040194919/536418153810831424*b^4 - 452199105143745/48765286710075584*b^3 + 4317002771457621/536418153810831424*b^2 + 2050725777454935/67052269226353928*b + 3711967683469209/3047830419379724 sage: P = EllipticCurve(L, '57a1').lift_x(z_x) * 3 sage: ideal = L.fractional_ideal(P[0], P[1]) sage: ideal.is_principal(proof=False) *** Warning: precision too low for generators, not given. True sage: len(ideal.gens_reduced(proof=False)) 1 """
def gens_two(self): r""" Express this ideal using exactly two generators, the first of which is a generator for the intersection of the ideal with `Q`.
ALGORITHM: uses PARI's :pari:`idealtwoelt` function, which runs in randomized polynomial time and is very fast in practice.
EXAMPLES::
sage: R.<x> = PolynomialRing(QQ) sage: K.<a> = NumberField(x^2 + 5) sage: J = K.ideal([a+2, 9]) sage: J.gens() (a + 2, 9) sage: J.gens_two() (9, a + 2) sage: K.ideal([a+5, a+8]).gens_two() (3, a + 2) sage: K.ideal(0).gens_two() (0, 0)
The second generator is zero if and only if the ideal is generated by a rational, in contrast to the PARI function :pari:`idealtwoelt`::
sage: I = K.ideal(12) sage: pari(K).idealtwoelt(I) # Note that second element is not zero [12, [0, 12]~] sage: I.gens_two() (12, 0)
""" # Check whether the ideal is generated by an integer, i.e. # whether HNF is a multiple of the identity matrix else:
def integral_basis(self): r""" Return a list of generators for this ideal as a `\ZZ`-module.
EXAMPLES::
sage: R.<x> = PolynomialRing(QQ) sage: K.<i> = NumberField(x^2 + 1) sage: J = K.ideal(i+1) sage: J.integral_basis() [2, i + 1] """
def integral_split(self): r""" Return a tuple `(I, d)`, where `I` is an integral ideal, and `d` is the smallest positive integer such that this ideal is equal to `I/d`.
EXAMPLES::
sage: R.<x> = PolynomialRing(QQ) sage: K.<a> = NumberField(x^2-5) sage: I = K.ideal(2/(5+a)) sage: I.is_integral() False sage: J,d = I.integral_split() sage: J Fractional ideal (-1/2*a + 5/2) sage: J.is_integral() True sage: d 5 sage: I == J/d True """ self.__integral_split = (self, ZZ(1)) else: for (p,e) in denom_list ]) ## Get a list of the primes dividing the denominator
def intersection(self, other): r""" Return the intersection of self and other.
EXAMPLES::
sage: K.<a> = QuadraticField(-11) sage: p = K.ideal((a + 1)/2); q = K.ideal((a + 3)/2) sage: p.intersection(q) == q.intersection(p) == K.ideal(a-2) True
An example with non-principal ideals::
sage: L.<a> = NumberField(x^3 - 7) sage: p = L.ideal(a^2 + a + 1, 2) sage: q = L.ideal(a+1) sage: p.intersection(q) == L.ideal(8, 2*a + 2) True
A relative example::
sage: L.<a,b> = NumberField([x^2 + 11, x^2 - 5]) sage: A = L.ideal([15, (-3/2*b + 7/2)*a - 8]) sage: B = L.ideal([6, (-1/2*b + 1)*a - b - 5/2]) sage: A.intersection(B) == L.ideal(-1/2*a - 3/2*b - 1) True
TESTS:
Test that this works with non-integral ideals (:trac:`10767`)::
sage: K = QuadraticField(-2) sage: I = K.ideal(1/2) sage: I.intersection(I) Fractional ideal (1/2) """
def is_integral(self): """ Return True if this ideal is integral.
EXAMPLES::
sage: R.<x> = PolynomialRing(QQ) sage: K.<a> = NumberField(x^5-x+1) sage: K.ideal(a).is_integral() True sage: (K.ideal(1) / (3*a+1)).is_integral() False """
def is_maximal(self): """ Return True if this ideal is maximal. This is equivalent to self being prime and nonzero.
EXAMPLES::
sage: K.<a> = NumberField(x^3 + 3); K Number Field in a with defining polynomial x^3 + 3 sage: K.ideal(5).is_maximal() False sage: K.ideal(7).is_maximal() True """ return self.is_prime() and not self.is_zero()
def is_prime(self): """ Return True if this ideal is prime.
EXAMPLES::
sage: K.<a> = NumberField(x^2 - 17); K Number Field in a with defining polynomial x^2 - 17 sage: K.ideal(5).is_prime() # inert prime True sage: K.ideal(13).is_prime() # split False sage: K.ideal(17).is_prime() # ramified False """ else:
def pari_prime(self): r""" Returns a PARI prime ideal corresponding to the ideal ``self``.
INPUT:
- ``self`` - a prime ideal.
OUTPUT: a PARI "prime ideal", i.e. a five-component vector `[p,a,e,f,b]` representing the prime ideal `p O_K + a O_K`, `e`, `f` as usual, `a` as vector of components on the integral basis, `b` Lenstra's constant.
EXAMPLES::
sage: K.<i> = QuadraticField(-1) sage: K.ideal(3).pari_prime() [3, [3, 0]~, 1, 2, 1] sage: K.ideal(2+i).pari_prime() [5, [2, 1]~, 1, 1, [-2, -1; 1, -2]] sage: K.ideal(2).pari_prime() Traceback (most recent call last): ... ValueError: Fractional ideal (2) is not a prime ideal """
def _cache_bnfisprincipal(self, proof=None, gens_needed=False): r""" This function is essentially the implementation of :meth:`is_principal`, :meth:`gens_reduced` and :meth:`ideal_class_log`.
INPUT:
- ``self`` -- an ideal
- ``proof`` -- proof flag. If ``proof=False``, assume GRH.
- ``gens_needed`` -- (default: True) if True, insist on computing the reduced generators of the ideal. With ``gens=False``, they may or may not be computed (depending on how big the ideal is).
OUTPUT:
None. This function simply caches the results: it sets ``_ideal_class_log`` (see :meth:`ideal_class_log`), ``_is_principal`` (see :meth:`is_principal`) and ``_reduced_generators``. """ # Since pari_bnf() is cached, this call to pari_bnf() should not # influence the run-time much. Also, this simplifies the handling # of the proof flag: if we computed bnfisprincipal() in the past # with proof=False, then we do not need to recompute the result. # We just need to check correctness of pari_bnf().
# If we already have _reduced_generators, no need to compute them again
# Is there something to do?
# Call bnfisprincipal(). # If gens_needed, use flag=3 which will insist on computing # the generator. Otherwise, use flag=1, where the generator # may or may not be computed.
# Cache reduced generator if it was computed else: # Non-principal ideal, compute two generators if asked for
def is_principal(self, proof=None): r""" Return True if this ideal is principal.
Since it uses the PARI method :pari:`bnfisprincipal`, specify ``proof=True`` (this is the default setting) to prove the correctness of the output.
EXAMPLES:
sage: K = QuadraticField(-119,'a') sage: P = K.factor(2)[1][0] sage: P.is_principal() False sage: I = P^5 sage: I.is_principal() True sage: I # random Fractional ideal (-1/2*a + 3/2) sage: P = K.ideal([2]).factor()[1][0] sage: I = P^5 sage: I.is_principal() True """
def ideal_class_log(self, proof=None): r""" Return the output of PARI's :pari:`bnfisprincipal` for this ideal, i.e. a vector expressing the class of this ideal in terms of a set of generators for the class group.
Since it uses the PARI method :pari:`bnfisprincipal`, specify ``proof=True`` (this is the default setting) to prove the correctness of the output.
EXAMPLES:
When the class number is 1, the result is always the empty list::
sage: K.<a> = QuadraticField(-163) sage: J = K.primes_above(random_prime(10^6))[0] sage: J.ideal_class_log() []
An example with class group of order 2. The first ideal is not principal, the second one is::
sage: K.<a> = QuadraticField(-5) sage: J = K.ideal(23).factor()[0][0] sage: J.ideal_class_log() [1] sage: (J^10).ideal_class_log() [0]
An example with a more complicated class group::
sage: K.<a, b> = NumberField([x^3 - x + 1, x^2 + 26]) sage: K.class_group() Class group of order 18 with structure C6 x C3 of Number Field in a with defining polynomial x^3 - x + 1 over its base field sage: K.primes_above(7)[0].ideal_class_log() # random [1, 2] """
def S_ideal_class_log(self, S): r""" S-class group version of :meth:`ideal_class_log`.
EXAMPLES::
sage: K.<a> = QuadraticField(-14) sage: S = K.primes_above(2) sage: I = K.ideal(3, a + 1) sage: I.S_ideal_class_log(S) [1] sage: I.S_ideal_class_log([]) [3]
TESTS::
sage: K.<a> = QuadraticField(-974) sage: S = K.primes_above(2) sage: G = K.S_class_group(S) sage: I0 = G.0.ideal(); I1 = G.1.ideal() sage: for p in prime_range(100): ....: for P in K.primes_above(p): ....: v = P.S_ideal_class_log(S) ....: assert(G(P) == G(I0^v[0] * I1^v[1])) """ else:
def is_zero(self): """ Return True iff self is the zero ideal
Note that `(0)` is a ``NumberFieldIdeal``, not a ``NumberFieldFractionalIdeal``.
EXAMPLES::
sage: K.<a> = NumberField(x^2 + 2); K Number Field in a with defining polynomial x^2 + 2 sage: K.ideal(3).is_zero() False sage: I=K.ideal(0); I.is_zero() True sage: I Ideal (0) of Number Field in a with defining polynomial x^2 + 2 """
def norm(self): """ Return the norm of this fractional ideal as a rational number.
EXAMPLES::
sage: K.<a> = NumberField(x^4 + 23); K Number Field in a with defining polynomial x^4 + 23 sage: I = K.ideal(19); I Fractional ideal (19) sage: factor(I.norm()) 19^4 sage: F = I.factor() sage: F[0][0].norm().factor() 19^2 """
# synonyms (using terminology of relative number fields)
def absolute_norm(self): """ A synonym for norm.
EXAMPLES::
sage: K.<i> = NumberField(x^2 + 1) sage: K.ideal(1 + 2*i).absolute_norm() 5 """
def relative_norm(self): """ A synonym for norm.
EXAMPLES::
sage: K.<i> = NumberField(x^2 + 1) sage: K.ideal(1 + 2*i).relative_norm() 5 """
def absolute_ramification_index(self): """ A synonym for ramification_index.
EXAMPLES::
sage: K.<i> = NumberField(x^2 + 1) sage: K.ideal(1 + i).absolute_ramification_index() 2 """
def relative_ramification_index(self): """ A synonym for ramification_index.
EXAMPLES::
sage: K.<i> = NumberField(x^2 + 1) sage: K.ideal(1 + i).relative_ramification_index() 2 """
def number_field(self): """ Return the number field that this is a fractional ideal in.
EXAMPLES::
sage: K.<a> = NumberField(x^2 + 2); K Number Field in a with defining polynomial x^2 + 2 sage: K.ideal(3).number_field() Number Field in a with defining polynomial x^2 + 2 sage: K.ideal(0).number_field() # not tested (not implemented) Number Field in a with defining polynomial x^2 + 2 """
def smallest_integer(self): r""" Return the smallest non-negative integer in `I \cap \ZZ`, where `I` is this ideal. If `I = 0`, returns 0.
EXAMPLES::
sage: R.<x> = PolynomialRing(QQ) sage: K.<a> = NumberField(x^2+6) sage: I = K.ideal([4,a])/7; I Fractional ideal (2/7, 1/7*a) sage: I.smallest_integer() 2
TESTS::
sage: K.<i> = QuadraticField(-1) sage: P1, P2 = [P for P,e in K.factor(13)] sage: all([(P1^i*P2^j).smallest_integer() == 13^max(i,j,0) for i in range(-3,3) for j in range(-3,3)]) True sage: I = K.ideal(0) sage: I.smallest_integer() 0
See :trac:`4392`::
sage: K.<a>=QuadraticField(-5) sage: I=K.ideal(7) sage: I.smallest_integer() 7
sage: K.<z> = CyclotomicField(13) sage: a = K([-8, -4, -4, -6, 3, -4, 8, 0, 7, 4, 1, 2]) sage: I = K.ideal(a) sage: I.smallest_integer() 146196692151 sage: I.norm() 1315770229359 sage: I.norm() / I.smallest_integer() 9 """
# There is no need for caching since pari_hnf() is already cached.
#Old code by John Cremona, 2008-10-30, using the new coordinates() #function instead of factorization. # #Idea: We write 1 as a Q-linear combination of the Z-basis of self, #and return the denominator of this vector. # #self.__smallest_integer = self.coordinates(1).denominator() #return self.__smallest_integer
def valuation(self, p): r""" Return the valuation of self at ``p``.
INPUT:
- ``p`` -- a prime ideal `\mathfrak{p}` of this number field.
OUTPUT:
(integer) The valuation of this fractional ideal at the prime `\mathfrak{p}`. If `\mathfrak{p}` is not prime, raise a ValueError.
EXAMPLES::
sage: K.<a> = NumberField(x^5 + 2); K Number Field in a with defining polynomial x^5 + 2 sage: i = K.ideal(38); i Fractional ideal (38) sage: i.valuation(K.factor(19)[0][0]) 1 sage: i.valuation(K.factor(2)[0][0]) 5 sage: i.valuation(K.factor(3)[0][0]) 0 sage: i.valuation(0) Traceback (most recent call last): ... ValueError: p (= Ideal (0) of Number Field in a with defining polynomial x^5 + 2) must be nonzero sage: K.ideal(0).valuation(K.factor(2)[0][0]) +Infinity """ raise ValueError("p (= %s) must be a prime"%p) raise ValueError("p (= %s) must be an ideal in %s"%self.number_field())
def decomposition_group(self): r""" Return the decomposition group of self, as a subset of the automorphism group of the number field of self. Raises an error if the field isn't Galois. See the decomposition_group method of the ``GaloisGroup_v2`` class for further examples and doctests.
EXAMPLES::
sage: QuadraticField(-23, 'w').primes_above(7)[0].decomposition_group() Galois group of Number Field in w with defining polynomial x^2 + 23 """
def ramification_group(self, v): r""" Return the `v`'th ramification group of self, i.e. the set of elements `s` of the Galois group of the number field of self (which we assume is Galois) such that `s` acts trivially modulo the `(v+1)`'st power of self. See the ramification_group method of the ``GaloisGroup`` class for further examples and doctests.
EXAMPLES::
sage: QuadraticField(-23, 'w').primes_above(23)[0].ramification_group(0) Galois group of Number Field in w with defining polynomial x^2 + 23 sage: QuadraticField(-23, 'w').primes_above(23)[0].ramification_group(1) Subgroup [()] of Galois group of Number Field in w with defining polynomial x^2 + 23 """
def inertia_group(self): r""" Return the inertia group of self, i.e. the set of elements s of the Galois group of the number field of self (which we assume is Galois) such that s acts trivially modulo self. This is the same as the 0th ramification group of self. See the inertia_group method of the ``GaloisGroup_v2`` class for further examples and doctests.
EXAMPLES::
sage: QuadraticField(-23, 'w').primes_above(23)[0].inertia_group() Galois group of Number Field in w with defining polynomial x^2 + 23 """
def random_element(self, *args, **kwds): """ Return a random element of this order.
INPUT:
- ``*args``, ``*kwds`` - Parameters passed to the random integer function. See the documentation of ``ZZ.random_element()`` for details.
OUTPUT:
A random element of this fractional ideal, computed as a random `\ZZ`-linear combination of the basis.
EXAMPLES::
sage: K.<a> = NumberField(x^3 + 2) sage: I = K.ideal(1-a) sage: I.random_element() # random output -a^2 - a - 19 sage: I.random_element(distribution="uniform") # random output a^2 - 2*a - 8 sage: I.random_element(-30,30) # random output -7*a^2 - 17*a - 75 sage: I.random_element(-100, 200).is_integral() True sage: I.random_element(-30,30).parent() is K True
A relative example::
sage: K.<a, b> = NumberField([x^2 + 2, x^2 + 1000*x + 1]) sage: I = K.ideal(1-a) sage: I.random_element() # random output 17/500002*a^3 + 737253/250001*a^2 - 1494505893/500002*a + 752473260/250001 sage: I.random_element().is_integral() True sage: I.random_element(-100, 200).parent() is K True """ else:
def artin_symbol(self): r""" Return the Artin symbol `( K / \QQ, P)`, where `K` is the number field of `P` =self. This is the unique element `s` of the decomposition group of `P` such that `s(x) = x^p \pmod{P}` where `p` is the residue characteristic of `P`. (Here `P` (self) should be prime and unramified.)
See the ``artin_symbol`` method of the ``GaloisGroup_v2`` class for further documentation and examples.
EXAMPLES::
sage: QuadraticField(-23, 'w').primes_above(7)[0].artin_symbol() (1,2) """
def residue_symbol(self, e, m, check=True): r""" The m-th power residue symbol for an element e and the proper ideal.
.. MATH:: \left(\frac{\alpha}{\mathbf{P}}\right) \equiv \alpha^{\frac{N(\mathbf{P})-1}{m}} \operatorname{mod} \mathbf{P}
.. note:: accepts m=1, in which case returns 1
.. note:: can also be called for an element from sage.rings.number_field_element.residue_symbol
.. note:: e is coerced into the number field of self
.. note:: if m=2, e is an integer, and self.number_field() has absolute degree 1 (i.e. it is a copy of the rationals), then this calls kronecker_symbol, which is implemented using GMP.
INPUT:
- ``e`` - element of the number field
- ``m`` - positive integer
OUTPUT:
- an m-th root of unity in the number field
EXAMPLES:
Quadratic Residue (7 is not a square modulo 11)::
sage: K.<a> = NumberField(x - 1) sage: K.ideal(11).residue_symbol(7,2) -1
Cubic Residue::
sage: K.<w> = NumberField(x^2 - x + 1) sage: K.ideal(17).residue_symbol(w^2 + 3,3) -w
The field must contain the m-th roots of unity::
sage: K.<w> = NumberField(x^2 - x + 1) sage: K.ideal(17).residue_symbol(w^2 + 3,5) Traceback (most recent call last): ... ValueError: The residue symbol to that power is not defined for the number field
"""
except TypeError: pass else: raise ValueError("Ideal must be proper") raise ValueError("Power must be positive") raise ValueError("Element is not coprime to the ideal") raise ValueError("Ideal is not coprime to the power") return prod(Q.residue_symbol(e,m,check=False)**i for Q, i in self.factor()) except TypeError: raise ValueError("Element and ideal must be in a common number field")
def _quadratic_form(self): r""" If this is a quadratic extension over `\QQ`, return the binary quadratic form associated with this ideal.
EXAMPLES::
sage: K.<a> = QuadraticField(23) sage: K.ideal(a).quadratic_form() 23*x^2 - y^2
sage: K.<a> = QuadraticField(-5) sage: K.class_group().order() 2 sage: A = K.class_group().gen() sage: A.ideal().quadratic_form().reduced_form() 2*x^2 + 2*x*y + 3*y^2 sage: (A^2).ideal().quadratic_form().reduced_form() x^2 + 5*y^2
sage: K.<a> = QuadraticField(-40) sage: K.class_group().order() 2 sage: A = K.class_group().gen() sage: A.ideal().quadratic_form().reduced_form() 2*x^2 + 5*y^2 sage: (A^2).ideal().quadratic_form().reduced_form() x^2 + 10*y^2
One more check::
sage: K = QuadraticField(-79) sage: A = K.class_group().gen() sage: [(A**i).ideal().quadratic_form().discriminant() ....: for i in range(5)] [-79, -79, -79, -79, -79]
This is not defined for higher-degree extensions::
sage: x = var('x') sage: K.<a> = NumberField(x**3-x-1) sage: K.ideal(a)._quadratic_form() Traceback (most recent call last): ... ValueError: not defined for ideals in number fields of degree > 2 over Q.
REFERENCES:
.. [Cohen] Henri Cohen, A Course in Computational Algebraic Number Theory. Section 5.2. """ else: beta * alpha.galois_conjugate()) // N
def basis_to_module(B, K): r""" Given a basis `B` of elements for a `\ZZ`-submodule of a number field `K`, return the corresponding `\ZZ`-submodule.
EXAMPLES::
sage: K.<w> = NumberField(x^4 + 1) sage: from sage.rings.number_field.number_field_ideal import basis_to_module sage: basis_to_module([K.0, K.0^2 + 3], K) Free module of degree 4 and rank 2 over Integer Ring User basis matrix: [0 1 0 0] [3 0 1 0] """
def is_NumberFieldIdeal(x): """ Return True if x is an ideal of a number field.
EXAMPLES::
sage: from sage.rings.number_field.number_field_ideal import is_NumberFieldIdeal sage: is_NumberFieldIdeal(2/3) False sage: is_NumberFieldIdeal(ideal(5)) False sage: k.<a> = NumberField(x^2 + 2) sage: I = k.ideal([a + 1]); I Fractional ideal (a + 1) sage: is_NumberFieldIdeal(I) True sage: Z = k.ideal(0); Z Ideal (0) of Number Field in a with defining polynomial x^2 + 2 sage: is_NumberFieldIdeal(Z) True """
class NumberFieldFractionalIdeal(MultiplicativeGroupElement, NumberFieldIdeal): r""" A fractional ideal in a number field.
EXAMPLES::
sage: R.<x> = PolynomialRing(QQ) sage: K.<a> = NumberField(x^3 - 2) sage: I = K.ideal(2/(5+a)) sage: J = I^2 sage: Jinv = I^(-2) sage: J*Jinv Fractional ideal (1) """ def __init__(self, field, gens, coerce=True): """ INPUT: field -- a number field x -- a list of NumberFieldElements of the field, not all zero
EXAMPLES::
sage: NumberField(x^2 + 1, 'a').ideal(7) Fractional ideal (7) """ raise TypeError("field (=%s) must be a number field."%field)
raise ValueError("gens must have length at least 1 (zero ideal is not a fractional ideal)") gens = gens[0] else:
def __repr__(self): """ Return the string representation of this number field fractional ideal.
.. note::
Only the zero ideal actually has type NumberFieldIdeal; all others have type NumberFieldFractionalIdeal.
EXAMPLES::
sage: K.<a>=NumberField(x^2+5) sage: I = K.ideal([2,1+a]); I Fractional ideal (2, a + 1) sage: type(I) <class 'sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal'> """
def divides(self, other): """ Returns True if this ideal divides other and False otherwise.
EXAMPLES::
sage: K.<a> = CyclotomicField(11); K Cyclotomic Field of order 11 and degree 10 sage: I = K.factor(31)[0][0]; I Fractional ideal (31, a^5 + 10*a^4 - a^3 + a^2 + 9*a - 1) sage: I.divides(I) True sage: I.divides(31) True sage: I.divides(29) False """
def factor(self): """ Factorization of this ideal in terms of prime ideals.
EXAMPLES::
sage: K.<a> = NumberField(x^4 + 23); K Number Field in a with defining polynomial x^4 + 23 sage: I = K.ideal(19); I Fractional ideal (19) sage: F = I.factor(); F (Fractional ideal (19, 1/2*a^2 + a - 17/2)) * (Fractional ideal (19, 1/2*a^2 - a - 17/2)) sage: type(F) <class 'sage.structure.factorization.Factorization'> sage: list(F) [(Fractional ideal (19, 1/2*a^2 + a - 17/2), 1), (Fractional ideal (19, 1/2*a^2 - a - 17/2), 1)] sage: F.prod() Fractional ideal (19)
TESTS:
Number fields defined by non-monic and non-integral polynomials are supported (:trac:`252`)::
sage: F.<a> = NumberField(2*x^3 + x + 1) sage: fact = F.factor(2); fact (Fractional ideal (2*a^2 + 1))^2 * (Fractional ideal (-2*a^2)) sage: [p[0].norm() for p in fact] [2, 2] """
def prime_factors(self): """ Return a list of the prime ideal factors of self
OUTPUT: list -- list of prime ideals (a new list is returned each time this function is called)
EXAMPLES::
sage: K.<w> = NumberField(x^2 + 23) sage: I = ideal(w+1) sage: I.prime_factors() [Fractional ideal (2, 1/2*w - 1/2), Fractional ideal (2, 1/2*w + 1/2), Fractional ideal (3, 1/2*w + 1/2)] """
def _div_(self, other): """ Return the quotient self / other.
EXAMPLES::
sage: R.<x> = PolynomialRing(QQ) sage: K.<a> = NumberField(x^2 - 5) sage: I = K.ideal(2/(5+a)) sage: J = K.ideal(17+a) sage: I/J Fractional ideal (-11/1420*a + 9/284) sage: (I/J) * J == I True """
def __invert__(self): """ Return the multiplicative inverse of self. Call with ~self.
EXAMPLES::
sage: R.<x> = PolynomialRing(QQ) sage: K.<a> = NumberField(x^3 - 2) sage: I = K.ideal(2/(5+a)) sage: ~I Fractional ideal (1/2*a + 5/2) sage: 1/I Fractional ideal (1/2*a + 5/2) sage: (1/I) * I Fractional ideal (1) """ self.pari_hnf())
def is_maximal(self): """ Return True if this ideal is maximal. This is equivalent to self being prime, since it is nonzero.
EXAMPLES::
sage: K.<a> = NumberField(x^3 + 3); K Number Field in a with defining polynomial x^3 + 3 sage: K.ideal(5).is_maximal() False sage: K.ideal(7).is_maximal() True """
def is_trivial(self, proof=None): """ Returns True if this is a trivial ideal.
EXAMPLES::
sage: F.<a> = QuadraticField(-5) sage: I = F.ideal(3) sage: I.is_trivial() False sage: J = F.ideal(5) sage: J.is_trivial() False sage: (I+J).is_trivial() True """
def ramification_index(self): r""" Return the ramification index of this fractional ideal, assuming it is prime. Otherwise, raise a ValueError.
The ramification index is the power of this prime appearing in the factorization of the prime in `\ZZ` that this prime lies over.
EXAMPLES::
sage: K.<a> = NumberField(x^2 + 2); K Number Field in a with defining polynomial x^2 + 2 sage: f = K.factor(2); f (Fractional ideal (a))^2 sage: f[0][0].ramification_index() 2 sage: K.ideal(13).ramification_index() 1 sage: K.ideal(17).ramification_index() Traceback (most recent call last): ... ValueError: Fractional ideal (17) is not a prime ideal """
def reduce(self, f): """ Return the canonical reduction of the element of `f` modulo the ideal `I` (=self). This is an element of `R` (the ring of integers of the number field) that is equivalent modulo `I` to `f`.
An error is raised if this fractional ideal is not integral or the element `f` is not integral.
INPUT:
- ``f`` - an integral element of the number field
OUTPUT:
An integral element `g`, such that `f - g` belongs to the ideal self and such that `g` is a canonical reduced representative of the coset `f + I` (`I` =self) as described in the ``residues`` function, namely an integral element with coordinates `(r_0, \dots,r_{n-1})`, where:
- `r_i` is reduced modulo `d_i` - `d_i = b_i[i]`, with `{b_0, b_1, \dots, b_n}` HNF basis of the ideal self.
.. note::
The reduced element `g` is not necessarily small. To get a small `g` use the method ``small_residue``.
EXAMPLES::
sage: k.<a> = NumberField(x^3 + 11) sage: I = k.ideal(5, a^2 - a + 1) sage: c = 4*a + 9 sage: I.reduce(c) a^2 - 2*a sage: c - I.reduce(c) in I True
The reduced element is in the list of canonical representatives returned by the ``residues`` method:
::
sage: I.reduce(c) in list(I.residues()) True
The reduced element does not necessarily have smaller norm (use ``small_residue`` for that)
::
sage: c.norm() 25 sage: (I.reduce(c)).norm() 209 sage: (I.small_residue(c)).norm() 10
Sometimes the canonical reduced representative of `1` won't be `1` (it depends on the choice of basis for the ring of integers):
::
sage: k.<a> = NumberField(x^2 + 23) sage: I = k.ideal(3) sage: I.reduce(3*a + 1) -3/2*a - 1/2 sage: k.ring_of_integers().basis() [1/2*a + 1/2, a]
AUTHOR: Maite Aranes. """
raise ValueError("reduce only defined for integral ideals")
raise TypeError("reduce only defined for integral elements")
def residues(self): """ Returns a iterator through a complete list of residues modulo this integral ideal.
An error is raised if this fractional ideal is not integral.
OUTPUT:
An iterator through a complete list of residues modulo the integral ideal self. This list is the set of canonical reduced representatives given by all integral elements with coordinates `(r_0, \dots,r_{n-1})`, where:
- `r_i` is reduced modulo `d_i`
- `d_i = b_i[i]`, with `{b_0, b_1, \dots, b_n}` HNF basis of the ideal.
AUTHOR: John Cremona (modified by Maite Aranes)
EXAMPLES::
sage: K.<i>=NumberField(x^2+1) sage: res = K.ideal(2).residues(); res xmrange_iter([[0, 1], [0, 1]], <function <lambda> at 0x...>) sage: list(res) [0, i, 1, i + 1] sage: list(K.ideal(2+i).residues()) [-2*i, -i, 0, i, 2*i] sage: list(K.ideal(i).residues()) [0] sage: I = K.ideal(3+6*i) sage: reps=I.residues() sage: len(list(reps)) == I.norm() True sage: all([r==s or not (r-s) in I for r in reps for s in reps]) # long time (6s on sage.math, 2011) True
sage: K.<a> = NumberField(x^3-10) sage: I = K.ideal(a-1) sage: len(list(I.residues())) == I.norm() True
sage: K.<z> = CyclotomicField(11) sage: len(list(K.primes_above(3)[0].residues())) == 3**5 # long time (5s on sage.math, 2011) True """ raise ValueError("residues only defined for integral ideals")
def invertible_residues(self, reduce=True): r""" Returns a iterator through a list of invertible residues modulo this integral ideal.
An error is raised if this fractional ideal is not integral.
INPUT:
- ``reduce`` - bool. If True (default), use ``small_residue`` to get small representatives of the residues.
OUTPUT:
- An iterator through a list of invertible residues modulo this ideal `I`, i.e. a list of elements in the ring of integers `R` representing the elements of `(R/I)^*`.
ALGORITHM: Use pari's ``idealstar`` to find the group structure and generators of the multiplicative group modulo the ideal.
EXAMPLES::
sage: K.<i>=NumberField(x^2+1) sage: ires = K.ideal(2).invertible_residues(); ires xmrange_iter([[0, 1]], <function <lambda> at 0x...>) sage: list(ires) [1, -i] sage: list(K.ideal(2+i).invertible_residues()) [1, 2, 4, 3] sage: list(K.ideal(i).residues()) [0] sage: list(K.ideal(i).invertible_residues()) [1] sage: I = K.ideal(3+6*i) sage: units=I.invertible_residues() sage: len(list(units))==I.euler_phi() True
sage: K.<a> = NumberField(x^3-10) sage: I = K.ideal(a-1) sage: len(list(I.invertible_residues())) == I.euler_phi() True
sage: K.<z> = CyclotomicField(10) sage: len(list(K.primes_above(3)[0].invertible_residues())) 80
AUTHOR: John Cremona """
def invertible_residues_mod(self, subgp_gens=[], reduce=True): r""" Returns a iterator through a list of representatives for the invertible residues modulo this integral ideal, modulo the subgroup generated by the elements in the list ``subgp_gens``.
INPUT:
- ``subgp_gens`` - either None or a list of elements of the number field of self. These need not be integral, but should be coprime to the ideal self. If the list is empty or None, the function returns an iterator through a list of representatives for the invertible residues modulo the integral ideal self.
- ``reduce`` - bool. If True (default), use ``small_residues`` to get small representatives of the residues.
.. note::
See also invertible_residues() for a simpler version without the subgroup.
OUTPUT:
- An iterator through a list of representatives for the invertible residues modulo self and modulo the group generated by ``subgp_gens``, i.e. a list of elements in the ring of integers `R` representing the elements of `(R/I)^*/U`, where `I` is this ideal and `U` is the subgroup of `(R/I)^*` generated by ``subgp_gens``.
EXAMPLES:
::
sage: k.<a> = NumberField(x^2 +23) sage: I = k.ideal(a) sage: list(I.invertible_residues_mod([-1])) [1, 5, 2, 10, 4, 20, 8, 17, 16, 11, 9] sage: list(I.invertible_residues_mod([1/2])) [1, 5] sage: list(I.invertible_residues_mod([23])) Traceback (most recent call last): ... TypeError: the element must be invertible mod the ideal
::
sage: K.<a> = NumberField(x^3-10) sage: I = K.ideal(a-1) sage: len(list(I.invertible_residues_mod([]))) == I.euler_phi() True
sage: I = K.ideal(1) sage: list(I.invertible_residues_mod([])) [1]
::
sage: K.<z> = CyclotomicField(10) sage: len(list(K.primes_above(3)[0].invertible_residues_mod([]))) 80
AUTHOR: Maite Aranes. """
for i in range(n))) else: combo = lambda c: prod(new_basis[i] ** c[i] for i in range(n))
def denominator(self): r""" Return the denominator ideal of this fractional ideal. Each fractional ideal has a unique expression as `N/D` where `N`, `D` are coprime integral ideals; the denominator is `D`.
EXAMPLES::
sage: K.<i>=NumberField(x^2+1) sage: I = K.ideal((3+4*i)/5); I Fractional ideal (4/5*i + 3/5) sage: I.denominator() Fractional ideal (2*i + 1) sage: I.numerator() Fractional ideal (-i - 2) sage: I.numerator().is_integral() and I.denominator().is_integral() True sage: I.numerator() + I.denominator() == K.unit_ideal() True sage: I.numerator()/I.denominator() == I True """
def numerator(self): r""" Return the numerator ideal of this fractional ideal.
Each fractional ideal has a unique expression as `N/D` where `N`, `D` are coprime integral ideals. The numerator is `N`.
EXAMPLES::
sage: K.<i>=NumberField(x^2+1) sage: I = K.ideal((3+4*i)/5); I Fractional ideal (4/5*i + 3/5) sage: I.denominator() Fractional ideal (2*i + 1) sage: I.numerator() Fractional ideal (-i - 2) sage: I.numerator().is_integral() and I.denominator().is_integral() True sage: I.numerator() + I.denominator() == K.unit_ideal() True sage: I.numerator()/I.denominator() == I True """
def is_coprime(self, other): """ Returns True if this ideal is coprime to the other, else False.
INPUT:
- ``other`` -- another ideal of the same field, or generators of an ideal.
OUTPUT:
True if self and other are coprime, else False.
.. note::
This function works for fractional ideals as well as integral ideals.
AUTHOR: John Cremona
EXAMPLES::
sage: K.<i>=NumberField(x^2+1) sage: I = K.ideal(2+i) sage: J = K.ideal(2-i) sage: I.is_coprime(J) True sage: (I^-1).is_coprime(J^3) True sage: I.is_coprime(5) False sage: I.is_coprime(6+i) True
See :trac:`4536`::
sage: E.<a> = NumberField(x^5 + 7*x^4 + 18*x^2 + x - 3) sage: OE = E.ring_of_integers() sage: i,j,k = [u[0] for u in factor(3*OE)] sage: (i/j).is_coprime(j/k) False sage: (j/k).is_coprime(j/k) False
sage: F.<a, b> = NumberField([x^2 - 2, x^2 - 3]) sage: F.ideal(3 - a*b).is_coprime(F.ideal(3)) False """ # Catch invalid inputs by making sure that we can make an ideal out of other. else: # This special case is necessary since the zero ideal is not a # fractional ideal! return self == one
def idealcoprime(self, J): """ Returns l such that l*self is coprime to J.
INPUT:
- ``J`` - another integral ideal of the same field as self, which must also be integral.
OUTPUT:
- ``l`` - an element such that l*self is coprime to the ideal J
TODO: Extend the implementation to non-integral ideals.
EXAMPLES::
sage: k.<a> = NumberField(x^2 + 23) sage: A = k.ideal(a+1) sage: B = k.ideal(3) sage: A.is_coprime(B) False sage: lam = A.idealcoprime(B); lam -1/6*a + 1/6 sage: (lam*A).is_coprime(B) True
ALGORITHM: Uses Pari function :pari:`idealcoprime`. """ raise ValueError("Both ideals must be integral.")
# Catch invalid inputs by making sure that J is an ideal of the same field as self:
def small_residue(self, f): r""" Given an element `f` of the ambient number field, returns an element `g` such that `f - g` belongs to the ideal self (which must be integral), and `g` is small.
.. note::
The reduced representative returned is not uniquely determined.
ALGORITHM: Uses Pari function :pari:`nfeltreduce`.
EXAMPLES:
::
sage: k.<a> = NumberField(x^2 + 5) sage: I = k.ideal(a) sage: I.small_residue(14) 4
::
sage: K.<a> = NumberField(x^5 + 7*x^4 + 18*x^2 + x - 3) sage: I = K.ideal(5) sage: I.small_residue(a^2 -13) a^2 + 5*a - 3
""" raise ValueError("The ideal must be integral")
def _pari_bid_(self, flag=1): """ Returns the pari structure ``bid`` associated to the ideal self.
INPUT:
- ``flag`` - when flag=2 it computes the generators of the group `(O_K/I)^*`, which takes more time. By default flag=1 (no generators are computed).
OUTPUT:
- The pari special structure ``bid``.
EXAMPLES::
sage: k.<a> = NumberField(x^4 + 13) sage: I = k.ideal(2, a^2 + 1) sage: hasattr(I, '_bid') False sage: bid = I._pari_bid_() sage: hasattr(I, '_bid') True sage: bid.getattr('clgp') [2, [2]] """ # Try to access generators, we get PariError if this fails.
def idealstar(self, flag=1): r""" Returns the finite abelian group `(O_K/I)^*`, where I is the ideal self of the number field K, and `O_K` is the ring of integers of K.
INPUT:
- ``flag`` (int default 1) -- when ``flag`` =2, it also computes the generators of the group `(O_K/I)^*`, which takes more time. By default ``flag`` =1 (no generators are computed). In both cases the special pari structure ``bid`` is computed as well. If ``flag`` =0 (deprecated) it computes only the group structure of `(O_K/I)^*` (with generators) and not the special ``bid`` structure.
OUTPUT:
The finite abelian group `(O_K/I)^*`.
.. note::
Uses the pari function :pari:`idealstar`. The pari function outputs a special ``bid`` structure which is stored in the internal field ``_bid`` of the ideal (when flag=1,2). The special structure ``bid`` is used in the pari function :pari:`ideallog` to compute discrete logarithms.
EXAMPLES::
sage: k.<a> = NumberField(x^3 - 11) sage: A = k.ideal(5) sage: G = A.idealstar(); G Multiplicative Abelian group isomorphic to C24 x C4 sage: G.gens() (f0, f1)
sage: G = A.idealstar(2) sage: G.gens() (f0, f1) sage: G.gens_values() # random output (2*a^2 - 1, 2*a^2 + 2*a - 2) sage: all([G.gen(i).value() in k for i in range(G.ngens())]) True
TESTS::
sage: k.<a> = NumberField(x^2 + 1) sage: k.ideal(a+1).idealstar(2) Trivial Abelian group
ALGORITHM: Uses Pari function :pari:`idealstar` """ G = k.pari_nf().idealstar(self.pari_hnf(), 0) else:
else:
def ideallog(self, x, gens=None, check=True): r""" Returns the discrete logarithm of x with respect to the generators given in the ``bid`` structure of the ideal self, or with respect to the generators ``gens`` if these are given.
INPUT:
- ``x`` - a non-zero element of the number field of self, which must have valuation equal to 0 at all prime ideals in the support of the ideal self. - ``gens`` - a list of elements of the number field which generate `(R / I)^*`, where `R` is the ring of integers of the field and `I` is this ideal, or ``None``. If ``None``, use the generators calculated by :meth:`~idealstar`. - ``check`` - if True, do a consistency check on the results. Ignored if ``gens`` is None.
OUTPUT:
- ``l`` - a list of non-negative integers `(x_i)` such that `x = \prod_i g_i^{x_i}` in `(R/I)^*`, where `x_i` are the generators, and the list `(x_i)` is lexicographically minimal with respect to this requirement. If the `x_i` generate independent cyclic factors of order `d_i`, as is the case for the default generators calculated by :meth:`~idealstar`, this just means that `0 \le x_i < d_i`.
A ``ValueError`` will be raised if the elements specified in ``gens`` do not in fact generate the unit group (even if the element `x` is in the subgroup they generate).
EXAMPLES::
sage: k.<a> = NumberField(x^3 - 11) sage: A = k.ideal(5) sage: G = A.idealstar(2) sage: l = A.ideallog(a^2 +3) sage: r = G(l).value() sage: (a^2 + 3) - r in A True sage: A.small_residue(r) # random a^2 - 2
Examples with custom generators::
sage: K.<a> = NumberField(x^2 - 7) sage: I = K.ideal(17) sage: I.ideallog(a + 7, [1+a, 2]) [10, 3] sage: I.ideallog(a + 7, [2, 1+a]) [0, 118]
sage: L.<b> = NumberField(x^4 - x^3 - 7*x^2 + 3*x + 2) sage: J = L.ideal(-b^3 - b^2 - 2) sage: u = -14*b^3 + 21*b^2 + b - 1 sage: v = 4*b^2 + 2*b - 1 sage: J.ideallog(5+2*b, [u, v], check=True) [4, 13]
A non-example::
sage: I.ideallog(a + 7, [2]) Traceback (most recent call last): ... ValueError: Given elements do not generate unit group -- they generate a subgroup of index 36
ALGORITHM: Uses Pari function :pari:`ideallog`, and (if ``gens`` is not None) a Hermite normal form calculation to express the result in terms of the generators ``gens``. """ # sanitise input
# calculate ideal log w.r.t. standard gens
#Now it is important to call _pari_bid_() with flag=2 to make sure #we fix a basis, since the log would be different for a different #choice of basis.
# otherwise translate answer in terms of given gens
# We use Hermite normal form twice: once to express the standard # generators in terms of the new ones (independently of x) and once to # reduce the resulting logarithm of x so it is lexicographically # minimal.
#print "Matrix of relations:\n%s" % C
def element_1_mod(self, other): r""" Returns an element `r` in this ideal such that `1-r` is in other
An error is raised if either ideal is not integral of if they are not coprime.
INPUT:
- ``other`` -- another ideal of the same field, or generators of an ideal.
OUTPUT:
An element `r` of the ideal self such that `1-r` is in the ideal other
AUTHOR: Maite Aranes (modified to use PARI's :pari:`idealaddtoone` by Francis Clarke)
EXAMPLES::
sage: K.<a> = NumberField(x^3-2) sage: A = K.ideal(a+1); A; A.norm() Fractional ideal (a + 1) 3 sage: B = K.ideal(a^2-4*a+2); B; B.norm() Fractional ideal (a^2 - 4*a + 2) 68 sage: r = A.element_1_mod(B); r -33 sage: r in A True sage: 1-r in B True
TESTS::
sage: K.<a> = NumberField(x^3-2) sage: A = K.ideal(a+1) sage: B = K.ideal(a^2-4*a+1); B; B.norm() Fractional ideal (a^2 - 4*a + 1) 99 sage: A.element_1_mod(B) Traceback (most recent call last): ... TypeError: Fractional ideal (a + 1), Fractional ideal (a^2 - 4*a + 1) are not coprime ideals
sage: B = K.ideal(1/a); B Fractional ideal (1/2*a^2) sage: A.element_1_mod(B) Traceback (most recent call last): ... TypeError: Fractional ideal (1/2*a^2) is not an integral ideal """ raise TypeError("%s is not an integral ideal"%self)
# Catch invalid inputs by making sure that we can make an ideal out of other.
def euler_phi(self): r""" Returns the Euler `\varphi`-function of this integral ideal.
This is the order of the multiplicative group of the quotient modulo the ideal.
An error is raised if the ideal is not integral.
EXAMPLES::
sage: K.<i>=NumberField(x^2+1) sage: I = K.ideal(2+i) sage: [r for r in I.residues() if I.is_coprime(r)] [-2*i, -i, i, 2*i] sage: I.euler_phi() 4 sage: J = I^3 sage: J.euler_phi() 100 sage: len([r for r in J.residues() if J.is_coprime(r)]) 100 sage: J = K.ideal(3-2*i) sage: I.is_coprime(J) True sage: I.euler_phi()*J.euler_phi() == (I*J).euler_phi() True sage: L.<b> = K.extension(x^2 - 7) sage: L.ideal(3).euler_phi() 64 """ raise ValueError("euler_phi only defined for integral ideals") for np,e in [(p.absolute_norm(),e) \ for p,e in self.factor()]])
def prime_to_S_part(self,S): r""" Return the part of this fractional ideal which is coprime to the prime ideals in the list ``S``.
.. NOTE::
This function assumes that `S` is a list of prime ideals, but does not check this. This function will fail if `S` is not a list of prime ideals.
INPUT:
- `S` -- a list of prime ideals
OUTPUT:
A fractional ideal coprime to the primes in `S`, whose prime factorization is that of ``self`` with the primes in `S` removed.
EXAMPLES::
sage: K.<a> = NumberField(x^2-23) sage: I = K.ideal(24) sage: S = [K.ideal(-a+5),K.ideal(5)] sage: I.prime_to_S_part(S) Fractional ideal (3) sage: J = K.ideal(15) sage: J.prime_to_S_part(S) Fractional ideal (3)
sage: K.<a> = NumberField(x^5-23) sage: I = K.ideal(24) sage: S = [K.ideal(15161*a^4 + 28383*a^3 + 53135*a^2 + 99478*a + 186250),K.ideal(2*a^4 + 3*a^3 + 4*a^2 + 15*a + 11), K.ideal(101)] sage: I.prime_to_S_part(S) Fractional ideal (24) """
def is_S_unit(self,S): r""" Return True if this fractional ideal is a unit with respect to the list of primes ``S``.
INPUT:
- `S` - a list of prime ideals (not checked if they are indeed prime).
.. note::
This function assumes that `S` is a list of prime ideals, but does not check this. This function will fail if `S` is not a list of prime ideals.
OUTPUT:
True, if the ideal is an `S`-unit: that is, if the valuations of the ideal at all primes not in `S` are zero. False, otherwise.
EXAMPLES::
sage: K.<a> = NumberField(x^2+23) sage: I = K.ideal(2) sage: P = I.factor()[0][0] sage: I.is_S_unit([P]) False """
def is_S_integral(self,S): r""" Return True if this fractional ideal is integral with respect to the list of primes ``S``.
INPUT:
- `S` - a list of prime ideals (not checked if they are indeed prime).
.. note::
This function assumes that `S` is a list of prime ideals, but does not check this. This function will fail if `S` is not a list of prime ideals.
OUTPUT:
True, if the ideal is `S`-integral: that is, if the valuations of the ideal at all primes not in `S` are non-negative. False, otherwise.
EXAMPLES::
sage: K.<a> = NumberField(x^2+23) sage: I = K.ideal(1/2) sage: P = K.ideal(2,1/2*a - 1/2) sage: I.is_S_integral([P]) False
sage: J = K.ideal(1/5) sage: J.is_S_integral([K.ideal(5)]) True """ return True
def prime_to_idealM_part(self, M): r""" Version for integral ideals of the ``prime_to_m_part`` function over `\ZZ`. Returns the largest divisor of self that is coprime to the ideal ``M``.
INPUT:
- ``M`` -- an integral ideal of the same field, or generators of an ideal
OUTPUT:
An ideal which is the largest divisor of self that is coprime to `M`.
AUTHOR: Maite Aranes
EXAMPLES::
sage: k.<a> = NumberField(x^2 + 23) sage: I = k.ideal(a+1) sage: M = k.ideal(2, 1/2*a - 1/2) sage: J = I.prime_to_idealM_part(M); J Fractional ideal (12, 1/2*a + 13/2) sage: J.is_coprime(M) True
sage: J = I.prime_to_idealM_part(2); J Fractional ideal (3, 1/2*a + 1/2) sage: J.is_coprime(M) True """ # Catch invalid inputs by making sure that we can make an ideal out of M.
raise TypeError("prime_to_idealM_part defined only for integral ideals")
def _p_quotient(self, p): """ This is an internal technical function that is used for example for computing the quotient of the ring of integers by a prime ideal.
INPUT: p -- a prime number contained in self.
OUTPUT: V -- a vector space of characteristic p quo -- a partially defined quotient homomorphism from the ambient number field to V lift -- a section of quo.
EXAMPLES::
sage: K.<i> = NumberField(x^2 + 1); O = K.maximal_order() sage: I = K.factor(3)[0][0] sage: Q, quo, lift = I._p_quotient(3); Q Vector space quotient V/W of dimension 2 over Finite Field of size 3 where V: Vector space of dimension 2 over Finite Field of size 3 W: Vector space of degree 2 and dimension 0 over Finite Field of size 3 Basis matrix: []
We do an example with a split prime and show both the quo and lift maps: sage: K.<i> = NumberField(x^2 + 1); O = K.maximal_order() sage: I = K.factor(5)[0][0] sage: Q,quo,lift = I._p_quotient(5) sage: lift(quo(i)) 3 sage: lift(quo(i)) - i in I True sage: quo(lift(Q.0)) (1) sage: Q.0 (1) sage: Q Vector space quotient V/W of dimension 1 over Finite Field of size 5 where V: Vector space of dimension 2 over Finite Field of size 5 W: Vector space of degree 2 and dimension 1 over Finite Field of size 5 Basis matrix: [1 3] sage: quo Partially defined quotient map from Number Field in i with defining polynomial x^2 + 1 to an explicit vector space representation for the quotient of the ring of integers by (p,I) for the ideal I=Fractional ideal (-i - 2). sage: lift Lifting map to Gaussian Integers in Number Field in i with defining polynomial x^2 + 1 from quotient of integers by Fractional ideal (-i - 2) """
def residue_field(self, names=None): r""" Return the residue class field of this fractional ideal, which must be prime.
EXAMPLES::
sage: K.<a> = NumberField(x^3-7) sage: P = K.ideal(29).factor()[0][0] sage: P.residue_field() Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10) sage: P.residue_field('z') Residue field in z of Fractional ideal (2*a^2 + 3*a - 10)
Another example::
sage: K.<a> = NumberField(x^3-7) sage: P = K.ideal(389).factor()[0][0]; P Fractional ideal (389, a^2 - 44*a - 9) sage: P.residue_class_degree() 2 sage: P.residue_field() Residue field in abar of Fractional ideal (389, a^2 - 44*a - 9) sage: P.residue_field('z') Residue field in z of Fractional ideal (389, a^2 - 44*a - 9) sage: FF.<w> = P.residue_field() sage: FF Residue field in w of Fractional ideal (389, a^2 - 44*a - 9) sage: FF((a+1)^390) 36 sage: FF(a) w
An example of reduction maps to the residue field: these are defined on the whole valuation ring, i.e. the subring of the number field consisting of elements with non-negative valuation. This shows that the issue raised in :trac:`1951` has been fixed::
sage: K.<i> = NumberField(x^2 + 1) sage: P1, P2 = [g[0] for g in K.factor(5)]; (P1,P2) (Fractional ideal (-i - 2), Fractional ideal (2*i + 1)) sage: a = 1/(1+2*i) sage: F1, F2 = [g.residue_field() for g in [P1,P2]]; (F1,F2) (Residue field of Fractional ideal (-i - 2), Residue field of Fractional ideal (2*i + 1)) sage: a.valuation(P1) 0 sage: F1(i/7) 4 sage: F1(a) 3 sage: a.valuation(P2) -1 sage: F2(a) Traceback (most recent call last): ZeroDivisionError: Cannot reduce field element -2/5*i + 1/5 modulo Fractional ideal (2*i + 1): it has negative valuation
An example with a relative number field::
sage: L.<a,b> = NumberField([x^2 + 1, x^2 - 5]) sage: p = L.ideal((-1/2*b - 1/2)*a + 1/2*b - 1/2) sage: R = p.residue_field(); R Residue field in abar of Fractional ideal ((-1/2*b - 1/2)*a + 1/2*b - 1/2) sage: R.cardinality() 9 sage: R(17) 2 sage: R((a + b)/17) abar sage: R(1/b) 2*abar
We verify that :trac:`8721` is fixed::
sage: L.<a, b> = NumberField([x^2 - 3, x^2 - 5]) sage: L.ideal(a).residue_field() Residue field in abar of Fractional ideal (a) """ raise ValueError("The ideal must be prime")
def residue_class_degree(self): r""" Return the residue class degree of this fractional ideal, assuming it is prime. Otherwise, raise a ValueError.
The residue class degree of a prime ideal `I` is the degree of the extension `O_K/I` of its prime subfield.
EXAMPLES::
sage: K.<a> = NumberField(x^5 + 2); K Number Field in a with defining polynomial x^5 + 2 sage: f = K.factor(19); f (Fractional ideal (a^2 + a - 3)) * (Fractional ideal (-2*a^4 - a^2 + 2*a - 1)) * (Fractional ideal (a^2 + a - 1)) sage: [i.residue_class_degree() for i, _ in f] [2, 2, 1] """
def ray_class_number(self): r""" Return the order of the ray class group modulo this ideal. This is a wrapper around Pari's :pari:`bnrclassno` function.
EXAMPLES::
sage: K.<z> = QuadraticField(-23) sage: p = K.primes_above(3)[0] sage: p.ray_class_number() 3
sage: x = polygen(K) sage: L.<w> = K.extension(x^3 - z) sage: I = L.ideal(5) sage: I.ray_class_number() 5184 """
def is_NumberFieldFractionalIdeal(x): """ Return True if x is a fractional ideal of a number field.
EXAMPLES::
sage: from sage.rings.number_field.number_field_ideal import is_NumberFieldFractionalIdeal sage: is_NumberFieldFractionalIdeal(2/3) False sage: is_NumberFieldFractionalIdeal(ideal(5)) False sage: k.<a> = NumberField(x^2 + 2) sage: I = k.ideal([a + 1]); I Fractional ideal (a + 1) sage: is_NumberFieldFractionalIdeal(I) True sage: Z = k.ideal(0); Z Ideal (0) of Number Field in a with defining polynomial x^2 + 2 sage: is_NumberFieldFractionalIdeal(Z) False """
class QuotientMap: """ Class to hold data needed by quotient maps from number field orders to residue fields. These are only partial maps: the exact domain is the appropriate valuation ring. For examples, see :meth:`~sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal.residue_field`. """ def __init__(self, K, M_OK_change, Q, I): """ Initialize this QuotientMap.
EXAMPLES::
sage: K.<a> = NumberField(x^3 + 4) sage: f = K.ideal(1 + a^2/2).residue_field().reduction_map(); f # indirect doctest Partially defined reduction map: From: Number Field in a with defining polynomial x^3 + 4 To: Residue field of Fractional ideal (1/2*a^2 + 1) sage: f.__class__ <type 'sage.rings.finite_rings.residue_field.ReductionMap'> """
def __call__(self, x): """ Apply this QuotientMap to an element of the number field.
INPUT:
x -- an element of the field
EXAMPLES::
sage: K.<a> = NumberField(x^3 + 4) sage: f = K.ideal(1 + a^2/2).residue_field().reduction_map() sage: f(a) 2 """
def __repr__(self): """ Return a string representation of this QuotientMap.
EXAMPLES::
sage: K.<a> = NumberField(x^3 + 4) sage: f = K.ideal(1 + a^2/2).residue_field().reduction_map() sage: repr(f) 'Partially defined reduction map:\n From: Number Field in a with defining polynomial x^3 + 4\n To: Residue field of Fractional ideal (1/2*a^2 + 1)' """
class LiftMap: """ Class to hold data needed by lifting maps from residue fields to number field orders. """ def __init__(self, OK, M_OK_map, Q, I): """ Initialize this LiftMap.
EXAMPLES::
sage: K.<a> = NumberField(x^3 + 4) sage: I = K.ideal(1 + a^2/2) sage: f = I.residue_field().lift_map() sage: f.__class__ <type 'sage.rings.finite_rings.residue_field.LiftingMap'> """
def __call__(self, x): """ Apply this LiftMap to an element of the residue field.
EXAMPLES::
sage: K.<a> = NumberField(x^3 + 4) sage: R = K.ideal(1 + a^2/2).residue_field() sage: f = R.lift_map() sage: f(R(a/17)) 1
A relative example, which used to fail but is fixed by :trac:`8721`::
sage: L.<a, b> = NumberField([x^2 + 1, x^2 - 5]) sage: p = L.ideal(2*a + 3) sage: V, to_V, from_V = p._p_quotient(13) sage: from_V(V.0) (-1/2*b + 7/2)*a - 1/2*b + 3/2 """ # This lifts to OK tensor F_p # This lifts to ZZ^n (= OK) # Write back in terms of K
def __repr__(self): """ Return a string representation of this QuotientMap.
EXAMPLES::
sage: K.<a> = NumberField(x^3 + 4) sage: R = K.ideal(1 + a^2/2).residue_field() sage: repr(R.lift_map()) 'Lifting map:\n From: Residue field of Fractional ideal (1/2*a^2 + 1)\n To: Maximal Order in Number Field in a with defining polynomial x^3 + 4' """
def quotient_char_p(I, p): r""" Given an integral ideal `I` that contains a prime number `p`, compute a vector space `V = (O_K \mod p) / (I \mod p)`, along with a homomorphism `O_K \to V` and a section `V \to O_K`.
EXAMPLES::
sage: from sage.rings.number_field.number_field_ideal import quotient_char_p
sage: K.<i> = NumberField(x^2 + 1); O = K.maximal_order(); I = K.fractional_ideal(15) sage: quotient_char_p(I, 5)[0] Vector space quotient V/W of dimension 2 over Finite Field of size 5 where V: Vector space of dimension 2 over Finite Field of size 5 W: Vector space of degree 2 and dimension 0 over Finite Field of size 5 Basis matrix: [] sage: quotient_char_p(I, 3)[0] Vector space quotient V/W of dimension 2 over Finite Field of size 3 where V: Vector space of dimension 2 over Finite Field of size 3 W: Vector space of degree 2 and dimension 0 over Finite Field of size 3 Basis matrix: []
sage: I = K.factor(13)[0][0]; I Fractional ideal (-3*i - 2) sage: I.residue_class_degree() 1 sage: quotient_char_p(I, 13)[0] Vector space quotient V/W of dimension 1 over Finite Field of size 13 where V: Vector space of dimension 2 over Finite Field of size 13 W: Vector space of degree 2 and dimension 1 over Finite Field of size 13 Basis matrix: [1 8] """ raise ValueError("I must be an integral ideal.")
# Now we have to quite explicitly find a way to compute # with OK / I viewed as a quotient of two F_p vector spaces, # and itself viewed as an F_p vector space.
# Step 1. Write each basis vector for I (as a ZZ-module) # in terms of the basis for OK.
# Step 2. Define "M_OK mod p" to just be (F_p)^n and # "M_I mod p" to be the reduction mod p of the elements # compute in step 1.
# Step 3. Compute the quotient of these two F_p vector space.
# Step 4. Now we get the maps we need from the above data.
|