source: sage/rings/number_field/number_field.py @ 6140:2fb4b1da68ab

Revision 6140:2fb4b1da68ab, 61.3 KB checked in by William Stein <wstein@…>, 6 years ago (diff)

Working on improving basic structure of number fields.
Line 
1"""
2Number Fields
3
4AUTHORS:
5   -- William Stein (2004, 2005): initial version
6   -- Steven Sivek (2006-05-12): added support for relative extensions
7"""
8
9
10#*****************************************************************************
11#       Copyright (C) 2004, 2005, 2006 William Stein <wstein@gmail.com>
12#
13#  Distributed under the terms of the GNU General Public License (GPL)
14#
15#    This code is distributed in the hope that it will be useful,
16#    but WITHOUT ANY WARRANTY; without even the implied warranty of
17#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18#    General Public License for more details.
19#
20#  The full text of the GPL is available at:
21#
22#                  http://www.gnu.org/licenses/
23#*****************************************************************************
24
25# There will be one running instance of GP for all
26# number field calculations that use the interpreter.
27from sage.interfaces.gp import Gp
28
29import sage.libs.ntl.all as ntl
30import sage.interfaces.gap
31import sage.misc.preparser
32import sage.rings.arith
33import sage.rings.complex_field
34import sage.rings.ring
35
36from sage.structure.element import is_Element
37
38import sage.structure.parent_gens
39
40_gp = None
41def gp():
42    """
43    Return the unique copy of the gp (PARI) interpreter
44    used for number field computations.
45
46    EXAMPLES:
47        sage: from sage.rings.number_field.number_field import gp
48        sage: gp()
49        GP/PARI interpreter
50    """
51    global _gp
52    if not _gp is None:
53        return _gp
54    else:
55        _gp = Gp()
56        return _gp
57
58import operator
59
60import weakref
61
62from sage.misc.latex import latex
63
64import sage.rings.arith as arith
65import sage.rings.rational_field as rational_field
66import sage.rings.integer_ring as integer_ring
67import sage.rings.infinity as infinity
68import sage.rings.rational as rational
69import sage.rings.integer as integer
70import sage.rings.polynomial.polynomial_ring as polynomial_ring
71import sage.rings.polynomial.polynomial_element as polynomial_element
72import sage.rings.ideal as ideal
73import sage.rings.complex_field
74import sage.groups.abelian_gps.abelian_group
75
76from sage.structure.parent_gens import ParentWithGens
77import number_field_element
78from number_field_ideal import convert_from_zk_basis
79
80from sage.libs.all import pari, pari_gen
81
82QQ = rational_field.RationalField()
83ZZ = integer_ring.IntegerRing()
84
85_nf_cache = {}
86def NumberField(polynomial, name=None, check=True, names=None):
87    r"""
88    Return {\em the} number field defined by the given irreducible
89    polynomial and with variable with the given name.  If check is
90    True (the default), also verify that the defining polynomial is
91    irreducible and over Q.
92
93    INPUT:
94        polynomial -- a polynomial over Q  (for now)
95        name -- a string (default: 'a'), the name of the generator
96        check -- bool (default: True); do type checking and
97                 irreducibility checking.
98
99    EXAMPLES:
100        sage: z = QQ['z'].0
101        sage: K = NumberField(z^2 - 2,'s'); K
102        Number Field in s with defining polynomial z^2 - 2
103        sage: s = K.0; s
104        s
105        sage: s*s   
106        2
107        sage: s^2
108        2
109
110    EXAMPLES: Constructing a relative number field
111        sage: K.<a> = NumberField(x^2 - 2)
112        sage: R.<t> = K[]
113        sage: L = K.extension(t^3+t+a, 'b'); L
114        Extension by t^3 + t + a of the Number Field in a with defining polynomial x^2 - 2
115        sage: L.absolute_field()
116        Number Field in b with defining polynomial x^6 + 2*x^4 + x^2 - 2
117        sage: b = L.gen()
118        sage: a*b
119        -b^4 - b^2
120        sage: L.lift_to_base(-3*b^3 - 3*b + 1)
121        3*a + 1
122
123    Number fields are globally unique.
124        sage: K.<a>= NumberField(x^3-5)     
125        sage: a^3
126        5
127        sage: L.<a>= NumberField(x^3-5)
128        sage: K is L
129        True       
130    """
131    if name is None and names is None:
132        raise TypeError, "You must specify the name of the generator."
133    if not names is None:
134        name = names
135
136    name = sage.structure.parent_gens.normalize_names(1, name)
137    if not isinstance(polynomial, polynomial_element.Polynomial):
138        try:
139            polynomial = polynomial.polynomial(QQ)
140        except (AttributeError, TypeError):
141            raise TypeError, "polynomial (=%s) must be a polynomial."%repr(polynomial)
142
143   
144    key = (polynomial, name)
145    if _nf_cache.has_key(key):
146        K = _nf_cache[key]()
147        if not K is None: return K
148
149    R = polynomial.base_ring()
150    if R == ZZ:
151        polynomial = QQ['x'](polynomial)
152    elif isinstance(R, NumberField_generic):
153        S = R.extension(polynomial, name)
154        _nf_cache[key] = weakref.ref(S)
155        return S
156       
157    if polynomial.degree() == 2:
158        K = NumberField_quadratic(polynomial, name, check)
159    else:
160        K = NumberField_generic(polynomial, name, None, check)
161
162    _nf_cache[key] = weakref.ref(K)
163    return K
164
165def QuadraticField(D, names, check=True):
166    """
167    Return a quadratic field obtained by adjoining a square root of
168    $D$ to the rational numbers, where $D$ is not a perfect square.
169
170    INPUT:
171        D -- a rational number
172        name -- variable name
173        check -- bool (default: True)
174
175    OUTPUT:
176        A number field defined by a quadratic polynomial.
177
178    EXAMPLES:
179        sage: QuadraticField(3, 'a')
180        Number Field in a with defining polynomial x^2 - 3
181        sage: K.<theta> = QuadraticField(3); K
182        Number Field in theta with defining polynomial x^2 - 3
183        sage: QuadraticField(9, 'a')
184        Traceback (most recent call last):
185        ...
186        ValueError: D must not be a perfect square.
187        sage: QuadraticField(9, 'a', check=False)
188        Number Field in a with defining polynomial x^2 - 9
189
190    Quadratic number fields derive from general number fields.
191        sage: type(K)
192        <class 'sage.rings.number_field.number_field.NumberField_quadratic'>
193        sage: is_NumberField(K)
194        True
195    """
196    D = QQ(D)
197    if check:
198        if D.is_square():
199            raise ValueError, "D must not be a perfect square."
200    R = polynomial_ring.PolynomialRing(QQ, 'x')
201    f = R([-D, 0, 1])
202    return NumberField(f, names, check=False)
203
204def is_QuadraticField(x):
205    r"""
206    Return True if x is of the quadratic {\em number} field type.
207
208    EXAMPLES:
209        sage: is_QuadraticField(QuadraticField(5,'a'))
210        True
211        sage: is_QuadraticField(NumberField(x^2 - 5, 'b'))
212        True
213        sage: is_QuadraticField(NumberField(x^3 - 5, 'b'))
214        False
215
216    A quadratic field specially refers to a number field, not a finite
217    field:
218        sage: is_QuadraticField(GF(9,'a'))
219        False
220    """
221    return isinstance(x, NumberField_quadratic)
222
223def is_NumberFieldExtension(x):
224    return isinstance(x, NumberField_extension)
225
226_cyclo_cache = {}
227def CyclotomicField(n, names=None):
228    if names is None:
229        names = "zeta%s"%n
230    names = sage.structure.parent_gens.normalize_names(1, names)
231    key = (n, names)
232    if _cyclo_cache.has_key(key):
233        K = _cyclo_cache[key]()
234        if not K is None: return K
235    K = NumberField_cyclotomic(n, names)
236    _cyclo_cache[key] = weakref.ref(K)
237    return K
238
239def is_CyclotomicField(x):
240    return isinstance(x, NumberField_cyclotomic)
241
242import number_field_base
243
244is_NumberField = number_field_base.is_NumberField
245
246class NumberField_generic(number_field_base.NumberField):
247    """
248    EXAMPLES:
249        sage: K.<a> = NumberField(x^3 - 2); K
250        Number Field in a with defining polynomial x^3 - 2
251        sage: loads(K.dumps()) == K
252        True
253    """
254    def __init__(self, polynomial, name,
255                 latex_name=None, check=True):
256        ParentWithGens.__init__(self, QQ, name)
257        if not isinstance(polynomial, polynomial_element.Polynomial):
258            raise TypeError, "polynomial (=%s) must be a polynomial"%repr(polynomial)
259       
260        if check:
261            if not polynomial.is_irreducible():
262                raise ValueError, "defining polynomial (%s) must be irreducible"%polynomial
263            if not polynomial.parent().base_ring() == QQ:
264                raise TypeError, "polynomial must be defined over rational field"
265        if not polynomial.is_monic():
266            raise NotImplementedError, "number fields for non-monic polynomials not yet implemented."
267
268        self._assign_names(name)
269        if latex_name is None:
270            self.__latex_variable_name = self.variable_name()
271        else:
272            self.__latex_variable_name = latex_name
273        self.__polynomial = polynomial
274        self.__pari_bnf_certified = False
275        self.__absolute_field = self
276
277    def __reduce__(self):
278        """
279        TESTS:
280            sage: Z = var('Z')
281            sage: K.<w> = NumberField(Z^3 + Z + 1)
282            sage: L = loads(dumps(K))
283            sage: print L
284            Number Field in w with defining polynomial Z^3 + Z + 1
285            sage: print L == K
286            True
287        """
288        return NumberField_generic_v1, (self.__polynomial, self.variable_name(), self.__latex_variable_name)
289
290    def complex_embeddings(self, prec=53):
291        r"""
292        Return all homomorphisms of this ring into the approximate
293        complex field with precision prec.
294
295        EXAMPLES:
296            sage: x = polygen(QQ)
297            sage: f = x^5 + x + 17
298            sage: k.<a> = NumberField(f)
299            sage: v = k.complex_embeddings()
300            sage: [phi(k.0^2) for phi in v]
301            [0.921039066973047 - 3.07553311884578*I, 0.921039066973047 + 3.07553311884578*I, 2.97572074037668, -2.40889943716139 - 1.90254105303505*I, -2.40889943716139 + 1.90254105303505*I]
302        """
303        try:
304            return self.__complex_embeddings[prec]
305        except AttributeError:
306            self.__complex_embeddings = {}
307        except KeyError:
308            pass
309        CC = sage.rings.complex_field.ComplexField(prec)
310        f = self.defining_polynomial().base_extend(CC)
311        v = f.roots()
312        e = [self.hom([a], check=False) for a in v]
313        self.__complex_embeddings[prec] = e
314        return e
315
316    def latex_variable_name(self, name=None):
317        if name is None:
318            return self.__latex_variable_name
319        else:
320            self.__latex_variable_name = name
321
322    def _repr_(self):
323        return "Number Field in %s with defining polynomial %s"%(
324                   self.variable_name(), self.polynomial())
325
326    def _latex_(self):
327        return "%s[%s]/(%s)"%(latex(QQ), self.variable_name(),
328                              self.polynomial()._latex_(self.variable_name()))
329
330    def __call__(self, x):
331        """
332        Coerce x into this number field.
333
334        EXAMPLES:
335            sage: K.<a> = NumberField(x^3 + 17)
336            sage: K(a) is a
337            True
338            sage: K('a^2 + 2/3*a + 5')
339            a^2 + 2/3*a + 5
340            sage: K('1').parent()
341            Number Field in a with defining polynomial x^3 + 17
342            sage: K(3/5).parent()
343            Number Field in a with defining polynomial x^3 + 17       
344        """
345        if isinstance(x, number_field_element.NumberFieldElement):
346            if x.parent() is self:
347                return x
348            elif x.parent() == self:
349                return number_field_element.NumberFieldElement(self, x.polynomial())
350            return self._coerce_from_other_number_field(x)
351        elif isinstance(x,str):
352            return self._coerce_from_str(x)
353        return self._coerce_non_number_field_element_in(x)
354
355    def _coerce_from_str(self, x):
356        # provide string coercion, as
357        # for finite fields
358        w = sage.misc.all.sage_eval(x,locals=\
359                                  {self.variable_name():self.gen()})
360        if not (is_Element(w) and w.parent() is self):
361            return self(w)
362        else:
363            return w       
364
365    def _coerce_from_other_number_field(self, x):
366        f = x.polynomial()
367        if f.degree() <= 0:
368            return number_field_element.NumberFieldElement(self, f[0])
369        # todo: more general coercion if embedding have been asserted
370        raise TypeError, "Cannot coerce %s into %s"%(x,self)       
371   
372    def _coerce_non_number_field_element_in(self, x):
373        if isinstance(x, (int, long, rational.Rational,
374                              integer.Integer, pari_gen,
375                              polynomial_element.Polynomial,
376                              list)):
377            return number_field_element.NumberFieldElement(self, x)
378        try:
379            return number_field_element.NumberFieldElement(self, x._rational_())
380        except (TypeError, AttributeError):
381            pass
382        raise TypeError, "Cannot coerce %s into %s"%(x,self)
383
384    def _coerce_impl(self, x):
385        if isinstance(x, (rational.Rational, integer.Integer, int, long)):
386            return number_field_element.NumberFieldElement(self, x)
387        elif isinstance(x, number_field_element.NumberFieldElement) and x.parent() == self:
388            return number_field_element.NumberFieldElement(self, x.list())
389        raise TypeError
390
391    def category(self):
392        from sage.categories.all import NumberFields
393        return NumberFields()
394
395    def __cmp__(self, other):
396        if not isinstance(other, NumberField_generic):
397            return -1
398        if self.variable_name() != other.variable_name():
399            return -1
400        return self.__polynomial.__cmp__(other.__polynomial)
401
402    def _ideal_class_(self):
403        return sage.rings.number_field.number_field_ideal.NumberFieldIdeal
404
405    def ideal(self, gens):
406        r"""
407        Return the ideal in $\mathcal{O}_K$ generated by gens.  This
408        overrides the \code{sage.rings.ring.Field} method to use the
409        \code{sage.rings.ring.Ring} one instead, since we're not really
410        concerned with ideals in a field but in its ring of integers.
411
412        EXAMPLES:
413            sage: K.<a> = NumberField(x^3-2)
414            sage: K.ideal([a])
415            Fractional ideal (a) of Number Field in a with defining polynomial x^3 - 2
416        """
417        return sage.rings.ring.Ring.ideal(self, gens)
418
419    def _is_valid_homomorphism_(self, codomain, im_gens):
420        try:
421            # We need that elements of the base ring of the polynomial
422            # ring map canonically into codomain.
423            codomain._coerce_(rational.Rational(1))
424            f = self.defining_polynomial()
425            return codomain(f(im_gens[0])) == 0
426        except TypeError, ValueError:
427            return False
428
429    def pari_polynomial(self):
430        """
431        PARI polynomial corresponding to polynomial that defines
432        this field.
433        """
434        try:
435            return self.__pari_polynomial
436        except AttributeError:
437            self.__pari_polynomial = self.polynomial()._pari_()
438            return self.__pari_polynomial
439
440    def pari_nf(self):
441        """
442        PARI number field corresponding to this field.
443        """
444        try:
445            return self.__pari_nf
446        except AttributeError:
447            f = self.pari_polynomial()
448            self.__pari_nf = f.nfinit()
449            return self.__pari_nf
450
451    def _pari_init_(self):
452        """
453        Needed for conversion of number field to PARI.
454       
455        EXAMPLES:
456            sage: k = NumberField(x^2 + x + 1, 'a')
457            sage: k._pari_init_()
458            'nfinit(x^2 + x + 1)'
459            sage: k._pari_()
460            [x^2 + x + 1, [0, 1], -3, 1, [Mat([1, -0.50000000000000000000000000000000000000 + 0.86602540378443864676372317075293618347*I]), [1, 0.36602540378443864676372317075293618347; 1, -1.3660254037844386467637231707529361835], 0, [2, -1; -1, -1], [3, 2; 0, 1], [1, -1; -1, -2], [3, [2, -1; 1, 1]]], [-0.50000000000000000000000000000000000000 + 0.86602540378443864676372317075293618347*I], [1, x], [1, 0; 0, 1], [1, 0, 0, -1; 0, 1, 1, -1]]
461            sage: pari(k)
462            [x^2 + x + 1, [0, 1], -3, 1, [Mat([1, -0.50000000000000000000000000000000000000 + 0.86602540378443864676372317075293618347*I]), [1, 0.36602540378443864676372317075293618347; 1, -1.3660254037844386467637231707529361835], 0, [2, -1; -1, -1], [3, 2; 0, 1], [1, -1; -1, -2], [3, [2, -1; 1, 1]]], [-0.50000000000000000000000000000000000000 + 0.86602540378443864676372317075293618347*I], [1, x], [1, 0; 0, 1], [1, 0, 0, -1; 0, 1, 1, -1]]
463        """
464       
465        return 'nfinit(%s)'%self.pari_polynomial()
466
467    def pari_bnf(self, certify=False):
468        """
469        PARI big number field corresponding to this field.
470        """
471        try:
472            if certify:
473                self.pari_bnf_certify()
474            return self.__pari_bnf
475        except AttributeError:
476            f = self.pari_polynomial()
477            self.__pari_bnf = f.bnfinit()
478            if certify:
479                self.pari_bnf_certify()
480            return self.__pari_bnf
481
482    def pari_bnf_certify(self):
483        """
484        Run the PARI bnfcertify function to ensure the correctness of answers.
485        """
486        if not self.__pari_bnf_certified:
487            if self.pari_bnf(certify=False).bnfcertify() != 1:
488                raise ValueError, "The result is not correct according to bnfcertify"
489            self.__pari_bnf_certified = True
490
491    def characteristic(self):
492        return 0
493
494    def class_group(self, certify=True):
495        r"""
496        Return the class group of this field.
497        """
498        try:
499            return self.__class_group
500        except AttributeError:
501            k = self.pari_bnf(certify)
502            s = str(k.getattr('clgp'))
503            s = s.replace(";",",")
504            s = eval(s)
505            self.__class_group = \
506               sage.groups.abelian_gps.abelian_group.AbelianGroup(s[1])
507        return self.__class_group
508
509    def class_number(self, certify=True):
510        return self.class_group(certify).order()
511
512    def composite_fields(self, other, names):
513        """
514        List of all possible composite fields formed from self and other.
515        """
516        if not isinstance(other, NumberField_generic):
517            raise TypeError, "other must be a number field."
518        f = self.pari_polynomial()
519        g = other.pari_polynomial()
520        C = f.polcompositum(g)
521        R = self.polynomial().parent()
522        C = [R(h) for h in C]
523        return [NumberField(h, names) for h in C]
524           
525    def degree(self):
526        return self.polynomial().degree()
527
528    def different(self):
529        """
530        Compute the different ideal of this number field.
531        """
532        try:
533            return self.__different
534        except AttributeError:
535            diff = self.pari_nf().getattr('diff')
536            zk_basis = self.pari_nf().getattr('zk')
537            basis_elts = zk_basis * diff
538            R = self.polynomial().parent()
539            self.__different = self.ideal([ self(R(x)) for x in basis_elts ])
540            return self.__different
541
542    def discriminant(self, v=None):
543        """
544        Returns the discriminant of the ring of integers of the number field,
545        or if v is specified, the determinant of the trace pairing
546        on the elements of the list v.
547
548        INPUT:
549            v (optional) -- list of element of this number field
550        OUTPUT:
551            Integer if v is omitted, and Rational otherwise.
552
553        EXAMPLES:
554            sage: K.<t> = NumberField(x^3 + x^2 - 2*x + 8)
555            sage: K.disc()
556            -503
557            sage: K.disc([1, t, t^2])
558            -2012
559            sage: K.disc([1/7, (1/5)*t, (1/3)*t^2])
560            -2012/11025
561            sage: (5*7*3)^2
562            11025
563        """
564        if v == None:
565            try:
566                return self.__disc
567            except AttributeError:
568                self.__disc = QQ(str(self.pari_nf()[2]))
569                return self.__disc
570        else:
571            return QQ(self.trace_pairing(v).det())
572
573    disc = discriminant
574
575    def elements_of_norm(self, n, certify=True):
576        r"""
577        Return a list of solutions modulo units of positive norm to
578        $Norm(a) = n$, where a can be any integer in this number field.
579
580        EXAMPLES:
581            sage: K.<a> = NumberField(x^2+1)
582            sage: K.elements_of_norm(3)
583            []
584            sage: K.elements_of_norm(50)
585            [7*a - 1, -5*a + 5, a - 7]           # 32-bit
586            [7*a - 1, -5*a + 5, -7*a - 1]        # 64-bit
587        """
588        B = self.pari_bnf(certify).bnfisintnorm(n)
589        R = self.polynomial().parent()
590        return [self(QQ['x'](R(g))) for g in B]
591
592    def extension(self, poly, name=None, names=None):
593        """
594        Return the relative extension of this field by a given polynomial.
595
596        EXAMPLES:
597            sage: K.<a> = NumberField(x^3 - 2)
598            sage: R.<t> = K[]
599            sage: L.<b> = K.extension(t^2 + a); L
600            Extension by t^2 + a of the Number Field in a with defining polynomial x^3 - 2
601
602        We create another extension.
603            sage: k.<a> = NumberField(x^2 + 1); k
604            Number Field in a with defining polynomial x^2 + 1
605            sage: y = var('y')
606            sage: m.<b> = k.extension(y^2 + 1); m
607            Extension by y^2 + 1 of the Number Field in a with defining polynomial x^2 + 1
608            sage: b.minpoly()
609            x^4 + 10*x^2 + 9
610           
611        """
612        if not isinstance(poly, polynomial_element.Polynomial):
613            try:
614                poly = poly.polynomial(self)
615            except (AttributeError, TypeError):
616                raise TypeError, "polynomial (=%s) must be a polynomial."%repr(poly)
617        if not names is None:
618            name = names
619        if isinstance(name, tuple):
620            name = name[0]
621        if name is None:
622            raise TypeError, "the variable name must be specified."
623        return NumberField_extension(self, poly, str(name))
624
625    def factor_integer(self, n):
626        r"""
627        Ideal factorization of the principal ideal of the ring
628        of integers generated by $n$.
629
630        EXAMPLE:
631        Here we show how to factor gaussian integers.
632        First we form a number field defined by $x^2 + 1$:
633 
634            sage: K.<I> = NumberField(x^2 + 1); K
635            Number Field in I with defining polynomial x^2 + 1
636           
637        Here are the factors:
638           
639            sage: fi, fj = K.factor_integer(13); fi,fj
640            ((Fractional ideal (3*I - 2) of Number Field in I with defining polynomial x^2 + 1, 1),
641            (Fractional ideal (-3*I - 2) of Number Field in I with defining polynomial x^2 + 1, 1))
642           
643        Now we extract the reduced form of the generators:
644
645            sage: zi = fi[0].gens_reduced()[0]; zi
646            3*I - 2
647            sage: zj = fj[0].gens_reduced()[0]; zj
648            -3*I - 2
649           
650        We recover the integer that was factor in $\Z[i]$
651           
652            sage: zi*zj
653            13
654           
655            AUTHOR:
656                -- Alex Clemesha (2006-05-20): examples
657
658        """
659        return self.ideal(n).factor()
660
661    def gen(self, n=0):
662        if n != 0:
663            raise IndexError, "Only one generator."
664        try:
665            return self.__gen
666        except AttributeError:
667            if self.__polynomial != None:
668                X = self.__polynomial.parent().gen()
669            else:
670                X = PolynomialRing(rational_field.RationalField()).gen()
671            self.__gen = number_field_element.NumberFieldElement(self, X)
672            return self.__gen
673
674    def is_field(self):
675        return True
676
677    def galois_group(self, pari_group = False, use_kash=False):
678        r"""
679        Return the Galois group of the Galois closure of this number
680        field as an abstract group.
681
682        For more (important!) documentation, so the documentation
683        for Galois groups of polynomials over $\Q$, e.g., by
684        typing \code{K.polynomial().galois_group?}, where $K$
685        is a number field.
686
687        EXAMPLES:
688            sage: NumberField(x^3-2, 'a').galois_group(pari_group=True)
689            PARI group [6, -1, 2, "S3"] of degree 3
690           
691            sage: NumberField(x-1, 'a').galois_group()    # optional database_gap package
692            Transitive group number 1 of degree 1
693            sage: NumberField(x^2+2, 'a').galois_group()  # optional database_gap package
694            Transitive group number 1 of degree 2
695            sage: NumberField(x^3-2, 'a').galois_group()  # optional database_gap package
696            Transitive group number 2 of degree 3
697        """
698        return self.polynomial().galois_group(pari_group = pari_group, use_kash = use_kash)
699
700
701    def integral_basis(self):
702        """
703        Return a list of elements of this number field that are a basis
704        for the full ring of integers.
705
706        EXAMPLES:
707            sage: K.<a> = NumberField(x^5 + 10*x + 1)
708            sage: K.integral_basis()
709            [1, a, a^2, a^3, a^4]
710
711        Next we compute the ring of integers of a cubic field in which 2
712        is an "essential discriminant divisor", so the ring of integers
713        is not generated by a single element.
714            sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
715            sage: K.integral_basis()
716            [1, a, 1/2*a^2 + 1/2*a]
717        """
718        try:
719            return self.__integral_basis
720        except AttributeError:
721            f = self.pari_polynomial()
722            B = f.nfbasis()
723            R = self.polynomial().parent()
724            self.__integral_basis = [self(R(g).list()) for g in B]
725        return self.__integral_basis
726
727    def narrow_class_group(self, certify = True):
728        r"""
729        Return the narrow class group of this field.
730       
731        EXAMPLES:
732            sage: NumberField(x^3+x+9, 'a').narrow_class_group()
733            Multiplicative Abelian Group isomorphic to C2
734        """
735        try:
736            return self.__narrow_class_group
737        except AttributeError:
738            k = self.pari_bnf(certify)
739            s = str(k.bnfnarrow())
740            s = s.replace(";",",")
741            s = eval(s)
742            self.__narrow_class_group = sage.groups.abelian_gps.abelian_group.AbelianGroup(s[1])
743        return self.__narrow_class_group
744
745    def ngens(self):
746        return 1
747
748    def order(self):
749        return infinity.infinity
750       
751    def order_table(self):
752        return []
753
754    def polynomial_ntl(self):
755        try:
756            return (self.__polynomial_ntl, self.__denominator_ntl)
757        except AttributeError:
758            self.__denominator_ntl = ntl.ZZ()
759            den = self.polynomial().denominator()
760            self.__denominator_ntl.set_from_sage_int(ZZ(den))
761            self.__polynomial_ntl = ntl.ZZX((self.polynomial()*den).list())
762        return (self.__polynomial_ntl, self.__denominator_ntl)
763
764    def polynomial(self):
765        return self.__polynomial
766
767    def defining_polynomial(self):
768        return self.__polynomial
769
770    def polynomial_ring(self):
771        return self.polynomial().parent()
772
773    def polynomial_quotient_ring(self):
774        """
775        Return the polynomial quotient ring isomorphic to this number field.
776
777        EXAMPLES:
778            sage: K = NumberField(x^3 + 2*x - 5, 'alpha')
779            sage: K.polynomial_quotient_ring()
780            Univariate Quotient Polynomial Ring in alpha over Rational Field with modulus x^3 + 2*x - 5
781        """
782        return self.polynomial_ring().quotient(self.polynomial(), self.variable_name())
783       
784    def regulator(self, certify=True):
785        """
786        Return the regulator of this number field.
787
788        Note that PARI computes the regulator to higher precision than
789        the SAGE default.
790
791        EXAMPLES:
792            sage: NumberField(x^2-2, 'a').regulator()
793            0.88137358701954305
794            sage: NumberField(x^4+x^3+x^2+x+1, 'a').regulator()
795            0.96242365011920694
796        """
797        try:
798            return self.__regulator
799        except AttributeError:
800            k = self.pari_bnf(certify)
801            s = str(k.getattr('reg'))
802            self.__regulator = eval(s)
803        return self.__regulator
804
805    def signature(self):
806        """
807        Return (r1, r2), where r1 and r2 are the number of real embeddings
808        and pairs of complex embeddings of this field, respectively.
809
810        EXAMPLES:
811            sage: NumberField(x^2+1, 'a').signature()
812            (0, 1)
813            sage: NumberField(x^3-2, 'a').signature()
814            (1, 1)
815            sage: CyclotomicField(7).signature()
816            (0, 3)
817        """
818        r1, r2 = self.pari_nf().getattr('sign')
819        return (ZZ(r1), ZZ(r2))
820
821    def trace_pairing(self, v):
822        """
823        Return the matrix of the trace pairing on the elements of the
824        list $v$.
825
826        EXAMPLES:
827            sage: K.<zeta3> = NumberField(x^2 + 3)
828            sage: K.trace_pairing([1,zeta3])
829            [ 2  0]
830            [ 0 -6]
831        """
832        import sage.matrix.matrix_space
833        A = sage.matrix.matrix_space.MatrixSpace(self.base_ring(), len(v))(0)
834        for i in range(len(v)):
835            for j in range(i,len(v)):
836                t = (self(v[i]*v[j])).trace()
837                A[i,j] = t
838                A[j,i] = t
839        return A
840
841    def units(self, certify = True):
842        """
843        Return generators for the unit group modulo torsion.
844
845        ALGORITHM: Uses PARI's bnfunit command.
846       
847        EXAMPLES:
848            sage: x = QQ['x'].0
849            sage: A = x^4 - 10*x^3 + 20*5*x^2 - 15*5^2*x + 11*5^3
850            sage: K = NumberField(A, 'a')
851            sage: K.units()
852            [8/275*a^3 - 12/55*a^2 + 15/11*a - 2]
853        """
854        try:
855            return self.__units
856        except AttributeError:
857            B = self.pari_bnf(certify).bnfunit()
858            R = self.polynomial().parent()
859            self.__units = [self(R(g)) for g in B]
860            return self.__units
861
862       
863    def zeta(self, n=2, all=False):
864        """
865        Return an n-th root of unity in this field.  If all is True,
866        return all of them.
867
868        INPUT:
869            n -- positive integer
870            all -- bool, default: False.  If True, return a list
871                   of all n-th roots of 1)
872
873        If there are no n-th roots of unity in self (and all is
874        False), this function raises an ArithmeticError exception.
875
876        EXAMPLES:
877            sage: x = QQ['x'].0
878            sage: K = NumberField(x^2 + 3, 'zeta3')
879            sage: K.zeta(1)
880            1
881            sage: K.zeta(2)
882            -1
883            sage: K.zeta(2, all=True)
884            [-1]
885            sage: K.zeta(3)
886            1/2*zeta3 - 1/2           
887            sage: K.zeta(3, all=True)
888            [1/2*zeta3 - 1/2, -1/2*zeta3 - 1/2]
889            sage: K.zeta(4)
890            Traceback (most recent call last):
891            ...
892            ArithmeticError: There are no 4-th roots of unity self.
893
894            sage: r.<x> = QQ[]
895            sage: K.<a> = NumberField(x^2+1)
896            sage: K.zeta(4)
897            a
898            sage: K.zeta(4,all=True)
899            [a, -a]
900            sage: K.zeta(3)
901            Traceback (most recent call last):
902            ...
903            ArithmeticError: There are no 3-th roots of unity self.
904            sage: K.zeta(3,all=True)
905            []           
906        """
907        n = ZZ(n)
908        if n <= 0:
909            raise ValueError, "n (=%s) must be positive"%n
910        if n == 1:
911            if all:
912                return [self(1)]
913            else:
914                return self(1)
915        elif n == 2:
916            if all:
917                return [self(-1)]
918            else:
919                return self(-1)
920        else:
921            field = self.__absolute_field
922            f = field.polynomial_ring().cyclotomic_polynomial(n)
923            F = polynomial_ring.PolynomialRing(field, 'x')(f)
924            R = F.roots()
925            if len(R) == 0:
926                if all:
927                    return []
928                else:
929                    raise ArithmeticError, "There are no %s-th roots of unity self."%n
930            if all:
931                return [r[0] for r in R]
932            else:
933                return R[0][0]
934   
935    def zeta_coefficients(self, n):
936        """
937        Compute the first n coefficients of the Dedekind zeta function
938        of this field as a Dirichlet series.
939
940        EXAMPLE:
941            sage: x = QQ['x'].0
942            sage: NumberField(x^2+1, 'a').zeta_coefficients(10)
943            [1, 1, 0, 1, 2, 0, 0, 1, 1, 2]
944        """
945        return self.pari_nf().dirzetak(n)
946
947
948
949class NumberField_extension(NumberField_generic):
950    """
951    EXAMPLES:
952        sage: K.<a> = NumberField(x^3 - 2)
953        sage: t = K['x'].gen()
954        sage: L.<b> = K.extension(t^2+t+a); L
955        Extension by x^2 + x + a of the Number Field in a with defining polynomial x^3 - 2
956    """
957    def __init__(self, base, polynomial, name, latex_name=None, names=None):
958        """
959        Note: polynomial must be defined in the ring \code{K['x']}, where
960        K is the base field. 
961        """
962        if not names is None: name = names
963        if not is_NumberField(base):
964            raise TypeError, "base (=%s) must be a number field"%base
965        if not isinstance(polynomial, polynomial_element.Polynomial):
966            try:
967                polynomial = polynomial.polynomial(base)
968            except (AttributeError, TypeError), msg:
969                raise TypeError, "polynomial (=%s) must be a polynomial."%repr(polynomial)
970        if name == base.variable_name():
971            raise ValueError, "Base field and extension cannot have the same name"
972        if polynomial.parent().base_ring() != base:
973            raise ValueError, "The polynomial must be defined over the base field"
974
975        # Generate the nf and bnf corresponding to the base field
976        # defined as polynomials in y, e.g. for rnfisfree
977
978        # Convert the polynomial defining the base field into a
979        # polynomial in y to satisfy PARI's ordering requirements.
980        # NOTE: This might not work properly if the base field is not
981        #       defined by a polynomial in one variable.  But currently
982        #       they are all defined in one variable, so no problem!
983       
984        Qx = base.polynomial().parent()
985        Qy = (base.polynomial().base_ring())['y']
986        phi = Qx.hom([Qy.gen()])
987        base_polynomial_y = phi(base.polynomial())
988       
989        self.__base_nf = pari(base_polynomial_y).nfinit()
990        self.__base_bnf = pari(base_polynomial_y).bnfinit()
991
992        # Use similar methods to convert the polynomial defining the
993        # relative extension into a polynomial in x, with y denoting
994        # the generator of the base field.
995        # NOTE: This should be rewritten if there is a way to extend
996        #       homomorphisms K -> K' to homomorphisms K[x] -> K'[x].
997        base_field_y = NumberField(base.polynomial(), 'y')
998        Kx = base_field_y['x']
999        i = base.hom([base_field_y.gen()]) # inclusion K -> K' with a -> y
1000        rel_coeffs = [i(c) for c in polynomial.coeffs()]
1001        polynomial_y = Kx(rel_coeffs)
1002
1003        self.__pari_relative_polynomial = pari(str(polynomial_y))
1004        self.__rnf = self.__base_nf.rnfinit(self.__pari_relative_polynomial)
1005
1006        self.__base_field = base
1007        NumberField_generic.__init__(self, self.absolute_polynomial(), name=name, latex_name=latex_name, check=False)
1008       
1009        self._assign_names(name)
1010        self.__relative_polynomial = polynomial
1011        self.__pari_bnf_certified = False
1012
1013    def __reduce__(self):
1014        """
1015        TESTS:
1016            sage: Z = var('Z')
1017            sage: K.<w> = NumberField(Z^3 + Z + 1)
1018            sage: L.<z> = K.extension(Z^3 + 2)
1019            sage: L = loads(dumps(K))
1020            sage: print L
1021            Number Field in w with defining polynomial Z^3 + Z + 1
1022            sage: print L == K
1023            True       
1024        """
1025        return NumberField_extension_v1, (self.__base_field, self.polynomial(), self.variable_name(),
1026                                          self.latex_variable_name())
1027
1028    def _repr_(self):
1029        return "Extension by %s of the Number Field in %s with defining polynomial %s"%(
1030            self.polynomial(), self.base_field().variable_name(),
1031            self.base_field().polynomial())
1032
1033    def _latex_(self):
1034        r"""
1035        Return a \LaTeX representation of the extension.
1036
1037        EXAMPLE:
1038            sage: x = QQ['x'].0
1039            sage: K.<a> = NumberField(x^3 - 2)
1040            sage: t = K['x'].gen()
1041            sage: K.extension(t^2+t+a, 'b')._latex_()
1042            '\\mathbf{Q}[b,a]/(b^{2} + b + a, a^{3} - 2)'
1043        """
1044        return "%s[%s,%s]/(%s, %s)"%(latex(QQ), self.variable_name(), self.base_field().variable_name(), self.polynomial()._latex_(self.variable_name()), self.base_field().polynomial()._latex_(self.base_field().variable_name()))
1045
1046    def __call__(self, x):
1047        """
1048        Coerce x into this number field.
1049        """
1050        if isinstance(x, number_field_element.NumberFieldElement):
1051            P = x.parent()
1052            if P is self:
1053                return x
1054            elif P == self:
1055                return number_field_element.NumberFieldElement(self, x.polynomial())
1056            if x.parent() == self.base_field():
1057                return self.__base_inclusion(x)
1058
1059        if not isinstance(x, (int, long, rational.Rational,
1060                              integer.Integer, pari_gen,
1061                              polynomial_element.Polynomial,
1062                              list)):
1063            raise TypeError, "Cannot coerce %s into %s"%(x,self)
1064       
1065        return number_field_element.NumberFieldElement(self, x)
1066
1067    def _coerce_impl(self, x):
1068        if isinstance(x, number_field_element.NumberFieldElement):
1069            if x.parent() == self:
1070                return x
1071            if x.parent() == self.base_field():
1072                return self.__base_inclusion(x)
1073        elif isinstance(x, (rational.Rational, integer.Integer, int, long)):
1074            return number_field_element.NumberFieldElement(self, x)
1075        raise TypeError
1076
1077    def __base_inclusion(self, element):
1078        """
1079        Given an element of the base field, give its inclusion into this
1080        extension (according to PARI's rnfeltreltoabs) in terms of the
1081        generator of this field.
1082        """
1083        if not number_field_element.is_NumberFieldElement(element):
1084            raise TypeError, "element must be a NumberFieldElement"
1085        if element.parent() != self.base_field():
1086            raise TypeError, "element must belong to the base field"
1087        base_field_y = NumberField(self.base_field().polynomial(), 'y')
1088        phi = self.base_field().hom([base_field_y.gen()])
1089        expr_x = self.pari_rnf().rnfeltreltoabs(str(phi(element)))
1090       
1091        # Convert to a polynomial in x, then to one in gen(), and return it
1092        return self(QQ['x'](str(expr_x).replace('^','**')))
1093
1094    def _ideal_class_(self):
1095        return sage.rings.number_field.number_field_ideal.NumberFieldIdeal_rel
1096
1097    def _pari_base_bnf(self, certify=False):
1098        # No need to certify the same field twice, so we'll just check
1099        # that the base field is certified.
1100        if certify:
1101            self.base_field().pari_bnf_certify()
1102        return self.__base_bnf
1103
1104    def _pari_base_nf(self):
1105        return self.__base_nf
1106
1107    def gen(self, n=0):
1108        if n != 0:
1109            raise IndexError, "Only one generator."
1110        try:
1111            return self.__gen
1112        except AttributeError:
1113            X = rational_field.RationalField()['x'].gen()
1114            self.__gen = number_field_element.NumberFieldElement(self, X)
1115            return self.__gen
1116
1117    def gen_relative(self):
1118        """
1119        Return root of defining polynomial, which is a generator of
1120        the relative number field over the base.
1121
1122        EXAMPLES:
1123            sage: k.<a> = NumberField(x^2+1); k
1124            Number Field in a with defining polynomial x^2 + 1
1125            sage: y = polygen(k)
1126            sage: m.<b> = k.extension(y^2+3); m
1127            Extension by x^2 + 3 of the Number Field in a with defining polynomial x^2 + 1
1128            sage: c = m.gen_relative(); c
1129            1/4*b^3 + 5/2*b
1130            sage: c^2 + 3
1131            0
1132            sage: m.gen()
1133            b       
1134        """
1135        try:
1136            return self.__gen_relative
1137        except AttributeError:
1138            rnf = self.pari_rnf()
1139            f = (pari('x') - rnf[10][2]*rnf[10][1]).lift()
1140            self.__gen_relative = number_field_element.NumberFieldElement(self, f)
1141            return self.__gen_relative
1142       
1143    def pari_polynomial(self):
1144        """
1145        PARI polynomial corresponding to polynomial that defines
1146        this field.
1147        """
1148        try:
1149            return self.__pari_polynomial
1150        except AttributeError:
1151            self.__pari_polynomial = self.absolute_polynomial()._pari_()
1152            return self.__pari_polynomial
1153
1154    def pari_rnf(self):
1155        return self.__rnf
1156
1157    def pari_relative_polynomial(self):
1158        return self.__pari_relative_polynomial
1159
1160    def absolute_field(self, name=None):
1161        r"""
1162        Return this field as an extension of $\Q$ rather than an
1163        extension of the base field.
1164        """
1165        try:
1166            return self.__absolute_field
1167        except AttributeError:
1168            if name is None:
1169                name = self.variable_name()
1170            self.__absolute_field = NumberField(self.absolute_polynomial(), name)
1171            return self.__absolute_field
1172
1173    def absolute_polynomial(self):
1174        r"""
1175        Return the polynomial over $\Q$ which defines this field as an
1176        extension of the rational numbers.
1177        """
1178        try:
1179            return self.__absolute_polynomial
1180        except AttributeError:
1181            pbn = self._pari_base_nf()
1182            prp = self.pari_relative_polynomial()
1183            pari_poly = pbn.rnfequation(prp)
1184            R = self.base_field().polynomial().parent()
1185            self.__absolute_polynomial = R(pari_poly)
1186            return self.__absolute_polynomial
1187
1188    def base_field(self):
1189        return self.__base_field
1190
1191    def base_ring(self):
1192        return self.base_field()
1193
1194    def discriminant(self, certify=True):
1195        """
1196        Return the relative discriminant of this extension $L/K$ as
1197        an ideal of $K$.  If you want the (rational) discriminant of
1198        $L/Q$, use e.g. \code{L.absolute_field().discriminant()}.
1199
1200        Note that this uses PARI's \code{rnfdisc} function, which
1201        according to the documentation takes an \code{nf} parameter in
1202        GP but a \code{bnf} parameter in the C library.  If the C
1203        library actually accepts an \code{nf}, then this function
1204        should be fixed and the \code{certify} parameter removed.
1205
1206        EXAMPLE:
1207            sage: x = QQ['x'].0
1208            sage: K.<i> = NumberField(x^2+1)
1209            sage: t = K['x'].gen()
1210            sage: L.<b> = K.extension(t^4-i)
1211            sage: L.discriminant()
1212            Fractional ideal (256) of Number Field in i with defining polynomial x^2 + 1
1213        """
1214        bnf = self._pari_base_bnf(certify)
1215        K = self.base_field()
1216        R = K.polynomial().parent()
1217        D, d = bnf.rnfdisc(self.pari_relative_polynomial())
1218        return K.ideal([ K(R(x)) for x in convert_from_zk_basis(K, D) ])
1219
1220    disc = discriminant
1221
1222    def extension(self, poly, name='b'):
1223        """
1224        Raise a NotImplemented error, since relative extensions of relative
1225        extensions are not yet supported.
1226        """
1227        raise NotImplementedError, "relative extensions of relative extensions are not supported"
1228
1229    def galois_group(self, pari_group = False, use_kash=False):
1230        r"""
1231        Return the Galois group of the Galois closure of this number
1232        field as an abstract group.  Note that even though this is an
1233        extension $L/K$, the group will be computed as if it were $L/\Q$.
1234
1235        For more (important!) documentation, so the documentation
1236        for Galois groups of polynomials over $\Q$, e.g., by
1237        typing \code{K.polynomial().galois_group?}, where $K$
1238        is a number field.
1239
1240        EXAMPLE:
1241            sage: x = QQ['x'].0
1242            sage: K.<a> = NumberField(x^2 + 1)
1243            sage: R.<t> = PolynomialRing(K)
1244            sage: L = K.extension(t^5-t+a, 'b')
1245            sage: L.galois_group()                     # optional
1246            Transitive group number 22 of degree 10
1247        """
1248        return self.absolute_polynomial().galois_group(pari_group = pari_group, use_kash = use_kash)
1249
1250    def is_free(self, certify=True):
1251        r"""
1252        Determine whether or not $L/K$ is free (i.e. if $\mathcal{O}_L$ is
1253        a free $\mathcal{O}_K$-module).
1254
1255        EXAMPLES:
1256            sage: x = QQ['x'].0
1257            sage: K.<a> = NumberField(x^2+6)
1258            sage: L.<b> = K.extension(K['x'].gen()^2 + 3)    ## extend by x^2+3
1259            sage: L.is_free()
1260            False
1261        """
1262        base_bnf = self._pari_base_bnf(certify)
1263        if base_bnf.rnfisfree(self.pari_relative_polynomial()) == 1:
1264            return True
1265        return False
1266
1267    def lift_to_base(self, element):
1268        """
1269        Lift an element of this extension into the base field if possible,
1270        or raise a ValueError if it is not possible.
1271
1272        EXAMPLES:
1273            sage: x = QQ['x'].0
1274            sage: K = NumberField(x^3 - 2, 'a')
1275            sage: R = K['x']
1276            sage: L = K.extension(R.gen()^2 - K.gen(), 'b')
1277            sage: b = L.gen()
1278            sage: L.lift_to_base(b^4)
1279            a^2
1280            sage: L.lift_to_base(b)
1281            Traceback (most recent call last):
1282            ...
1283            ValueError: The element b is not in the base field
1284        """
1285        poly_xy = self.pari_rnf().rnfeltabstorel( self(element)._pari_() )
1286        if str(poly_xy).find('x') >= 0:
1287            raise ValueError, "The element %s is not in the base field"%element
1288        return self.base_field()( QQ['y'](poly_xy) )
1289
1290    def polynomial(self):
1291        return self.__relative_polynomial
1292
1293
1294
1295class NumberField_cyclotomic(NumberField_generic):
1296    """
1297    Create a cyclotomic extension of the rational field.
1298   
1299    The command CyclotomicField(n) creates the n-th cyclotomic
1300    field, got by adjoing an n-th root of unity to the rational
1301    field.
1302   
1303    EXAMPLES:
1304        sage: CyclotomicField(3)
1305        Cyclotomic Field of order 3 and degree 2
1306        sage: CyclotomicField(18)
1307        Cyclotomic Field of order 18 and degree 6
1308        sage: z = CyclotomicField(6).gen(); z
1309        zeta6
1310        sage: z^3
1311        -1
1312        sage: (1+z)^3
1313        6*zeta6 - 3
1314
1315        sage: K = CyclotomicField(197)
1316        sage: loads(K.dumps()) == K
1317        True
1318        sage: loads((z^2).dumps()) == z^2
1319        True
1320
1321        sage: cf12 = CyclotomicField( 12 )
1322        sage: z12 = cf12.0
1323        sage: cf6 = CyclotomicField( 6 )
1324        sage: z6 = cf6.0
1325        sage: FF = Frac( cf12['x'] )
1326        sage: x = FF.0
1327        sage: print z6*x^3/(z6 + x)
1328        zeta12^2*x^3/(x + zeta12^2)       
1329    """
1330    def __init__(self, n, names):
1331        f = QQ['x'].cyclotomic_polynomial(n)
1332        if names[0][:4] == 'zeta':
1333            latex_name = "\\zeta_{%s}"%n
1334        else:
1335            latex_name = None
1336        NumberField_generic.__init__(self, f,
1337                                     name= names,
1338                                     latex_name=latex_name,
1339                                     check=False)
1340        n = integer.Integer(n)
1341        zeta = self.gen()
1342        zeta._set_multiplicative_order(n)
1343        self.__zeta_order = n
1344
1345    def __reduce__(self):
1346        """
1347        TESTS:
1348            sage: K.<zeta7> = CyclotomicField(7)
1349            sage: L = loads(dumps(K))
1350            sage: print L
1351            Cyclotomic Field of order 7 and degree 6
1352            sage: print L == K
1353            True
1354        """
1355        return NumberField_cyclotomic_v1, (self.__zeta_order, self.variable_name())
1356
1357    def _repr_(self):
1358        return "Cyclotomic Field of order %s and degree %s"%(
1359                self.zeta_order(), self.degree())
1360
1361    def _latex_(self):
1362        return "%s(\\zeta_{%s})"%(latex(QQ), self.__zeta_order)
1363               
1364    def __call__(self, x):
1365        """
1366        Create an element of this cyclotomic field from $x$.
1367       
1368        EXAMPLES:
1369        The following example illustrates coercion from the cyclotomic
1370        field Q(zeta_42) to the cyclotomic field Q(zeta_6), in a case
1371        where such coercion is defined:
1372       
1373            sage: k42 = CyclotomicField(42)
1374            sage: k6 = CyclotomicField(6)
1375            sage: a = k42.gen(0)
1376            sage: b = a^7
1377            sage: b
1378            zeta42^7
1379            sage: k6(b)
1380            zeta6
1381            sage: b^2
1382            zeta42^7 - 1
1383            sage: k6(b^2)
1384            zeta6 - 1
1385
1386        Coercion of GAP cyclotomic elements is also fully supported.
1387
1388       
1389        """
1390        if isinstance(x, number_field_element.NumberFieldElement):
1391            if isinstance(x.parent(), NumberField_cyclotomic):
1392                return self._coerce_from_other_cyclotomic_field(x)
1393            else:
1394                return self._coerce_from_other_number_field(x)
1395        elif sage.interfaces.gap.is_GapElement(x):
1396            return self._coerce_from_gap(x)
1397        elif isinstance(x,str):
1398            return self._coerce_from_str(x)
1399        else:
1400            return self._coerce_non_number_field_element_in(x)
1401
1402    def _coerce_from_other_cyclotomic_field(self, x, only_canonical=False):
1403        """
1404        Coerce an element x of a cyclotomic field into self, if at all possible.
1405
1406        INPUT:
1407            x -- number field element
1408            only_canonical -- bool (default: False); Attempt to work, even in some
1409                   cases when x is not in a subfield of the cyclotomics (as long as x is
1410                   a root of unity).
1411        """
1412        K = x.parent()
1413        if K is self:   
1414            return x
1415        elif K == self:
1416            return number_field_element.NumberFieldElement(self, x.polynomial())
1417        n = K.zeta_order()
1418        m = self.zeta_order()
1419        if m % n == 0:   # easy case
1420            # pass this off to a method in the element class
1421            # it can be done very quickly and easily by the pyrex<->NTL interface there
1422            return x._lift_cyclotomic_element(self)
1423        else:
1424            if only_canonical:
1425                raise TypeError
1426            n = x.multiplicative_order()
1427            if m % n == 0:
1428                # Harder case.  E.g., x = (zeta_42)^7 and
1429                # self.__zeta = zeta_6, so it is possible to
1430                # coerce x in, but not zeta_42 in.
1431                # Algorithm:
1432                #    1. Compute self.__zeta as an element
1433                #       of K = parent of x.  Call this y.
1434                #    2. Write x as a power r of y.
1435                #       TODO: we do step two STUPIDLY.
1436                #    3. Return self.__zeta to the power r.
1437                y = K(self.zeta())
1438                z = y
1439                for r in xrange(y.multiplicative_order()):
1440                    if z == x:
1441                        return self.zeta()**(r+1)
1442                    z *= y
1443            raise TypeError, "Cannot coerce %s into %s"%(x,self)
1444        return number_field_element.NumberFieldElement(self, g)
1445
1446    def _coerce_from_gap(self, x):
1447        """
1448        Attempt to coerce a GAP number field element into this cyclotomic field.
1449        """
1450        s = str(x)
1451        i = s.find('E(')
1452        if i == -1:
1453            return self(rational.Rational(s))
1454        j = i + s[i:].find(')')
1455        n = int(s[i+2:j])
1456        if n == self.zeta_order():
1457            K = self
1458        else:
1459            K = CyclotomicField(n)
1460        zeta = K.gen()
1461        s = s.replace('E(%s)'%n,'zeta')
1462        s = sage.misc.all.sage_eval(s, locals={'zeta':K.gen()})
1463        if K is self:
1464            return s
1465        else:
1466            return self(s)
1467
1468    def _coerce_impl(self, x):
1469        """
1470        Canonical coercion of x into self.
1471
1472        Elements of other compatible cyclotomic fields coerce in, as do elements
1473        of the rings that coerce to all number fields (e.g., integers, rationals).
1474        """
1475        if isinstance(x, number_field_element.NumberFieldElement) and \
1476                isinstance(x.parent(), NumberField_cyclotomic):
1477            return self._coerce_from_other_cyclotomic_field(x, only_canonical=True)
1478        return NumberField_generic._coerce_impl(self, x)       
1479
1480    def complex_embedding(self, prec=53):
1481        r"""
1482        Return the embedding of this cyclotomic field into the
1483        approximate complex field with precision prec obtained by
1484        sending the generator $\zeta$ of self to exp(2*pi*i/n), where
1485        $n$ is the multiplicative order of $\zeta$.
1486
1487        EXAMPLES:
1488            sage: C = CyclotomicField(4)
1489            sage: C.complex_embedding()
1490            Ring morphism:
1491              From: Cyclotomic Field of order 4 and degree 2
1492              To:   Complex Field with 53 bits of precision
1493              Defn: zeta4 |--> 6.12323399573677e-17 + 1.00000000000000*I
1494             
1495        Note in the example above that the way zeta is computed (using
1496        sin and cosine in MPFR) means that only the prec bits of the
1497        number after the decimal point are valid.
1498             
1499            sage: K = CyclotomicField(3)
1500            sage: phi = K.complex_embedding (10)
1501            sage: phi(K.0)
1502            -0.50 + 0.87*I
1503            sage: phi(K.0^3)
1504            1.0
1505            sage: phi(K.0^3 - 1)
1506            0
1507            sage: phi(K.0^3 + 7)
1508            8.0
1509        """
1510        CC = sage.rings.complex_field.ComplexField(prec)
1511        return self.hom([CC.zeta(self.zeta_order())], check=False)
1512
1513    def complex_embeddings(self, prec=53):
1514        r"""
1515        Return all embeddings of this cyclotomic field into the
1516        approximate complex field with precision prec.
1517
1518        EXAMPLES:
1519            sage: C = CyclotomicField(4)
1520            sage: C.complex_embeddings()
1521            [Ring morphism:
1522              From: Cyclotomic Field of order 4 and degree 2
1523              To:   Complex Field with 53 bits of precision
1524              Defn: zeta4 |--> 6.12323399573677e-17 + 1.00000000000000*I, Ring morphism:
1525              From: Cyclotomic Field of order 4 and degree 2
1526              To:   Complex Field with 53 bits of precision
1527              Defn: zeta4 |--> -0.000000000000000183697019872103 - 1.00000000000000*I]
1528        """
1529        CC = sage.rings.complex_field.ComplexField(prec)
1530        n = self.zeta_order()
1531        z = CC.zeta(self.zeta_order())
1532        X = [m for m in range(n) if sage.rings.arith.gcd(m,n) == 1]
1533        return [self.hom([z**n], check=False) for n in X]
1534
1535    def next_split_prime(self, p=2):
1536        """
1537        Return the next prime integer $p$ that splits completely in
1538        this cyclotomic field (and does not ramify).
1539
1540        EXAMPLES:
1541            sage: K.<z> = CyclotomicField(3)
1542            sage: K.next_split_prime(7)
1543            13           
1544        """
1545        n = self.zeta_order()
1546        while True:
1547            p = sage.rings.arith.next_prime(p)
1548            if p % n == 1:
1549                return p
1550
1551    def integral_basis(self):
1552        """
1553        Return a list of elements of this number field that are a basis
1554        for the full ring of integers.
1555        """
1556        try:
1557            return self.__integral_basis
1558        except AttributeError:
1559            z = self.gen()
1560            a = self(1)
1561            B = []
1562            for n in xrange(self.degree()):
1563                B.append(a)
1564                a *= z
1565            self.__integral_basis = B
1566        return self.__integral_basis
1567       
1568               
1569    def zeta_order(self):
1570        return self.__zeta_order
1571       
1572    def multiplicative_order_table(self):
1573        try:
1574            return self.__multiplicative_order_table
1575        except AttributeError:
1576            t = {}
1577            x = self(1)
1578            n = self.zeta_order()
1579            m = 0
1580            zeta = self.zeta()
1581            # todo: this desperately needs to be optimized!!!
1582            for i in range(n):
1583                t[x.polynomial()] = n//arith.GCD(m,n)   # multiplicative_order of (zeta_n)**m
1584                x *= zeta
1585                m += 1
1586            self.__multiplicative_order_table = t
1587            return t
1588
1589    def zeta(self, n=None, all=False):
1590        """
1591        Returns an element of multiplicative order $n$ in this this
1592        number field, if there is one.  Raises a ValueError if there
1593        is not.
1594
1595        INPUT:
1596            n -- integer (default: None, returns element of maximal order)
1597            all -- bool (default: False) -- whether to return a list of
1598                        all n-th roots.
1599
1600        OUTPUT:
1601            root of unity or list
1602
1603        EXAMPLES:
1604            sage: k = CyclotomicField(7)
1605            sage: k.zeta()
1606            zeta7
1607            sage: k.zeta().multiplicative_order()
1608            7
1609            sage: k = CyclotomicField(49)
1610            sage: k.zeta().multiplicative_order()
1611            49
1612            sage: k.zeta(7).multiplicative_order()
1613            7
1614            sage: k.zeta()
1615            zeta49
1616            sage: k.zeta(7)
1617            zeta49^7
1618
1619            sage: K.<a> = CyclotomicField(5)
1620            sage: K.zeta(4)
1621            Traceback (most recent call last):
1622            ...
1623            ValueError: n (=4) does not divide order of generator
1624            sage: v = K.zeta(5, all=True); v
1625            [a, a^2, a^3, -a^3 - a^2 - a - 1]
1626            sage: [b^5 for b in v]
1627            [1, 1, 1, 1]           
1628        """
1629        if n is None:
1630            return self.gen()
1631        else:
1632            n = integer.Integer(n)
1633            z = self.gen()
1634            m = z.multiplicative_order()
1635            if m % n != 0:
1636                raise ValueError, "n (=%s) does not divide order of generator"%n
1637                # use generic method (factor cyclotomic polynomial)
1638                #  -- this is potentially really slow, so don't do it.
1639                #return field.Field.zeta(self, n, all=all)
1640            a = z**(m//n)
1641            if all:
1642                v = [a]
1643                b = a*a
1644                for i in range(2,n):
1645                    if sage.rings.arith.gcd(i, n) == 1:
1646                        v.append(b)
1647                    b = b * a
1648                return v
1649            else:
1650                return a
1651   
1652class NumberField_quadratic(NumberField_generic):
1653    """
1654    Create a quadratic extension of the rational field.
1655   
1656    The command QuadraticExtension(a) creates the field Q(sqrt(a)).
1657   
1658    EXAMPLES:
1659        sage: QuadraticField(3, 'a')
1660        Number Field in a with defining polynomial x^2 - 3
1661        sage: QuadraticField(-4, 'b')
1662        Number Field in b with defining polynomial x^2 + 4
1663    """
1664    def __init__(self, polynomial, name=None, check=True):
1665        NumberField_generic.__init__(self, polynomial, name=name, check=check)
1666       
1667    def __reduce__(self):
1668        """
1669        TESTS:
1670            sage: K.<z7> = QuadraticField(7)
1671            sage: L = loads(dumps(K))
1672            sage: print L
1673            Number Field in z7 with defining polynomial x^2 - 7
1674            sage: print L == K
1675            True
1676        """
1677        return NumberField_quadratic_v1, (self.polynomial(), self.variable_name())
1678
1679    def class_number(self, proof = True):
1680        """
1681        Return the size of the class group of self.
1682
1683        If proof = False (not the default) and the discriminant of the
1684        field is negative, then the following warning from the PARI
1685        manual applies: IMPORTANT WARNING: For D<0, this function may
1686        give incorrect results when the class group has a low exponent
1687        (has many cyclic factors), because implementing Shank's method
1688        in full generality slows it down immensely.
1689        """
1690        try:
1691            return self.__class_number
1692        except AttributeError:
1693            D = self.discriminant()
1694            if D < 0 and proof:
1695                self.__class_number = pari("qfbclassno(%s,1)"%D).python()
1696            else:
1697                self.__class_number = pari("qfbclassno(%s)"%D).python()
1698            return self.__class_number
1699
1700    def hilbert_class_polynomial(self):
1701        r"""
1702        Returns a polynomial over $\Q$ whose roots generate the
1703        Hilbert class field of this quadratic field.
1704
1705        \note{Computed using PARI via Schertz's method.  This
1706        implementation is quite fast.}
1707
1708        EXAMPLES:
1709            sage: x = QQ['x'].0
1710            sage: K = NumberField(x^2 + 23, 'a')
1711            sage: K.hilbert_class_polynomial()
1712            x^3 + x^2 - 1
1713
1714            sage: K = NumberField(x^2 + 431, 'a')
1715            sage: K.hilbert_class_polynomial()
1716            x^21 + x^20 - 13*x^19 - 50*x^18 + 592*x^17 - 2403*x^16 + 5969*x^15 - 10327*x^14 + 13253*x^13 - 12977*x^12 + 9066*x^11 - 2248*x^10 - 5523*x^9 + 11541*x^8 - 13570*x^7 + 11315*x^6 - 6750*x^5 + 2688*x^4 - 577*x^3 + 9*x^2 + 15*x + 1
1717        """
1718        f = pari('quadhilbert(%s))'%self.discriminant())
1719        g = QQ['x'](f)
1720        return g
1721
1722    def hilbert_class_field(self, names):
1723        r"""
1724        Returns the Hilbert class field of this quadratic
1725        field as an absolute extension of $\Q$.  For a polynomial
1726        that defines a relative extension see the
1727        \code{hilbert_class_polynomial} command.
1728
1729        \note{Computed using PARI via Schertz's method.  This implementation
1730        is amazingly fast.}       
1731
1732        EXAMPLES:
1733            sage: x = QQ['x'].0
1734            sage: K = NumberField(x^2 + 23, 'a')
1735            sage: K.hilbert_class_polynomial()
1736            x^3 + x^2 - 1
1737            sage: K.hilbert_class_field('h')
1738            Number Field in h with defining polynomial x^6 + 2*x^5 + 70*x^4 + 90*x^3 + 1631*x^2 + 1196*x + 12743
1739        """
1740        f = self.hilbert_class_polynomial()
1741        C = self.composite_fields(NumberField(f,'x'),names)
1742        assert len(C) == 1
1743        return C[0]
1744
1745def is_fundamental_discriminant(D):
1746    d = D % 4
1747    if not (d in [0,1]):
1748        return False
1749    return D != 1 and  D != 0 and \
1750           (arith.is_squarefree(D) or \
1751            (d == 0 and (D//4)%4 in [2,3] and arith.is_squarefree(D//4)))
1752
1753
1754###################
1755# For pickling
1756###################
1757
1758def NumberField_generic_v1(poly, name, latex_name):
1759    return NumberField_generic(poly, name, latex_name, check=False)
1760
1761def NumberField_extension_v1(base_field, poly, name, latex_name):
1762    return NumberField_extension(base_field, poly, name, latex_name, check=False)
1763
1764def NumberField_cyclotomic_v1(zeta_order, name):
1765    return NumberField_cyclotomic(zeta_order, name)
1766
1767def NumberField_quadratic_v1(poly, name):
1768    return NumberField_quadratic(poly, name, check=False)
Note: See TracBrowser for help on using the repository browser.