# source:sage/rings/number_field/number_field.py@6792:5a3078f992a0

Revision 6792:5a3078f992a0, 164.0 KB checked in by William Stein <wstein@…>, 6 years ago (diff)

Add fractional_ideal as alias for ideal for number fields.

However, *much* more work will be needed to make actual
fractional ideals, since all the base class infrastructure
doesn't work for this.

Line
1r"""
2Number Fields
3
4AUTHORS:
5   -- William Stein (2004, 2005): initial version
6   -- Steven Sivek (2006-05-12): added support for relative extensions
7   -- William Stein (2007-09-04): major rewrite and documentation
8
9NOTE:
10
11    Unlike in PARI/GP, class group computations *in SAGE* do *not* by
12    default assume the Generalized Riemann Hypothesis.  To do class
13    groups computations not provably correctly you must often pass the
14    flag proof=False to functions or call the function
15    \code{proof.number_field(False)}.  It can easily take 1000's of
16    times longer to do computations with \code{proof=True} (the
17    default).
18
19This example follows one in the Magma reference manual:
20    sage: K.<y> = NumberField(x^4 - 420*x^2 + 40000)
21    sage: z = y^5/11; z
22    420/11*y^3 - 40000/11*y
23    sage: R.<y> = PolynomialRing(K)
24    sage: f = y^2 + y + 1
25    sage: L.<a> = K.extension(f); L
26    Number Field in a with defining polynomial y^2 + y + 1 over its base field
27    sage: KL.<b> = NumberField([x^4 - 420*x^2 + 40000, x^2 + x + 1]); KL
28    Number Field in b0 with defining polynomial x^4 + (-420)*x^2 + 40000 over its base field
29
30We do some arithmetic in a tower of relative number fields:
31    sage: K.<cuberoot2> = NumberField(x^3 - 2)
32    sage: L.<cuberoot3> = K.extension(x^3 - 3)
33    sage: S.<sqrt2> = L.extension(x^2 - 2)
34    sage: S
35    Number Field in sqrt2 with defining polynomial x^2 + -2 over its base field
36    sage: sqrt2 * cuberoot3
37    cuberoot3*sqrt2
38    sage: (sqrt2 + cuberoot3)^5
39    (20*cuberoot3^2 + 15*cuberoot3 + 4)*sqrt2 + 3*cuberoot3^2 + 20*cuberoot3 + 60
40    sage: cuberoot2 + cuberoot3
41    cuberoot3 + cuberoot2
42    sage: cuberoot2 + cuberoot3 + sqrt2
43    sqrt2 + cuberoot3 + cuberoot2
44    sage: (cuberoot2 + cuberoot3 + sqrt2)^2
45    (2*cuberoot3 + 2*cuberoot2)*sqrt2 + cuberoot3^2 + 2*cuberoot2*cuberoot3 + cuberoot2^2 + 2
46    sage: cuberoot2 + sqrt2
47    sqrt2 + cuberoot2
48    sage: a = S(cuberoot2); a
49    cuberoot2
50    sage: a.parent()
51    Number Field in sqrt2 with defining polynomial x^2 + -2 over its base field
52
53WARNING: Doing arithmetic in towers of relative fields that depends on
54canonical coercions is currently VERY SLOW.  It is much better to
55explicitly coerce all elements into a common field, then do arithmetic
56with them there (which is quite fast).
57
58TESTS:
59    sage: y = polygen(QQ,'y'); K.<beta> = NumberField([y^3 - 3, y^2 - 2])
60    sage: K(y^10)
61    (-3024*beta1 + 1530)*beta0^2 + (-2320*beta1 + 5067)*beta0 + -3150*beta1 + 7592
62"""
63
64# TODO:
65#   * relative over relative
66
67#*****************************************************************************
68#       Copyright (C) 2004, 2005, 2006, 2007 William Stein <wstein@gmail.com>
69#
71#
72#    This code is distributed in the hope that it will be useful,
73#    but WITHOUT ANY WARRANTY; without even the implied warranty of
74#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
75#    General Public License for more details.
76#
77#  The full text of the GPL is available at:
78#
80#*****************************************************************************
81
82from __future__ import with_statement
83from sage.structure.parent_gens import localvars
84
85# There will be one running instance of GP for all
86# number field calculations that use the interpreter.
87from sage.interfaces.gp import Gp
88
89import sage.libs.ntl.all as ntl
90import sage.libs.pari.all as pari
91import sage.interfaces.gap
92import sage.misc.preparser
93import sage.rings.arith
94
95import sage.rings.complex_field
96import sage.rings.real_mpfr
97import sage.rings.complex_double
98import sage.rings.real_double
99
100import sage.rings.ring
101from sage.misc.latex import latex_variable_name, latex_varify
102
103from class_group import ClassGroup
104from galois_group import GaloisGroup
105#import order
106
107from sage.structure.element import is_Element
108from sage.structure.sequence import Sequence
109
110import sage.structure.parent_gens
111
112from sage.structure.proof.proof import get_flag
113import maps
114
115def proof_flag(t):
116    """
117    Used for easily determining the correct proof flag to use.
118    """
119    return get_flag(t, "number_field")
120
121_gp = None
122def gp():
123    """
124    Return the unique copy of the gp (PARI) interpreter
125    used for number field computations.
126
127    EXAMPLES:
128        sage: from sage.rings.number_field.number_field import gp
129        sage: gp()
130        GP/PARI interpreter
131    """
132    global _gp
133    if not _gp is None:
134        return _gp
135    else:
136        _gp = Gp()
137        return _gp
138
139import operator
140
141import weakref
142
143from sage.misc.latex import latex
144
145import sage.rings.arith as arith
146import sage.rings.rational_field as rational_field
147import sage.rings.integer_ring as integer_ring
148import sage.rings.infinity as infinity
149import sage.rings.rational as rational
150import sage.rings.integer as integer
151import sage.rings.polynomial.polynomial_ring as polynomial_ring
152import sage.rings.polynomial.polynomial_element as polynomial_element
153import sage.rings.ideal as ideal
154import sage.rings.complex_field
155import sage.groups.abelian_gps.abelian_group
156
157from sage.structure.parent_gens import ParentWithGens
158import number_field_element
160from number_field_ideal import convert_from_zk_basis, is_NumberFieldIdeal
161
162import sage.rings.number_field.number_field_ideal_rel
163
164from sage.libs.all import pari, pari_gen
165
166QQ = rational_field.RationalField()
167ZZ = integer_ring.IntegerRing()
168
169_nf_cache = {}
170def NumberField(polynomial, name=None, check=True, names=None, cache=True):
171    r"""
172    Return {\em the} number field defined by the given irreducible
173    polynomial and with variable with the given name.  If check is
174    True (the default), also verify that the defining polynomial is
175    irreducible and over Q.
176
177    INPUT:
178        polynomial -- a polynomial over QQ or a number field, or
179                      a list of polynomials.
180        name -- a string (default: 'a'), the name of the generator
181        check -- bool (default: True); do type checking and
182                 irreducibility checking.
183
184    EXAMPLES:
185        sage: z = QQ['z'].0
186        sage: K = NumberField(z^2 - 2,'s'); K
187        Number Field in s with defining polynomial z^2 - 2
188        sage: s = K.0; s
189        s
190        sage: s*s
191        2
192        sage: s^2
193        2
194
195    EXAMPLES: Constructing a relative number field
196        sage: K.<a> = NumberField(x^2 - 2)
197        sage: R.<t> = K[]
198        sage: L.<b> = K.extension(t^3+t+a); L
199        Number Field in b with defining polynomial t^3 + t + a over its base field
200        sage: L.absolute_field('c')
201        Number Field in c with defining polynomial x^6 + 2*x^4 + x^2 - 2
202        sage: a*b
203        a*b
204        sage: L(a)
205        a
206        sage: L.lift_to_base(b^3 + b)
207        -a
208
209    Constructing another number field:
210        sage: k.<i> = NumberField(x^2 + 1)
211        sage: R.<z> = k[]
212        sage: m.<j> = NumberField(z^3 + i*z + 3)
213        sage: m
214        Number Field in j with defining polynomial z^3 + i*z + 3 over its base field
215
216    Number fields are globally unique.
217        sage: K.<a>= NumberField(x^3-5)
218        sage: a^3
219        5
220        sage: L.<a>= NumberField(x^3-5)
221        sage: K is L
222        True
223
224    Having different defining polynomials makes them fields different:
225        sage: x = polygen(QQ, 'x'); y = polygen(QQ, 'y')
226        sage: k.<a> = NumberField(x^2 + 3)
227        sage: m.<a> = NumberField(y^2 + 3)
228        sage: k
229        Number Field in a with defining polynomial x^2 + 3
230        sage: m
231        Number Field in a with defining polynomial y^2 + 3
232
233    An example involving a variable name that defines a function in
234    PARI:
235        sage: theta = polygen(QQ, 'theta')
236        sage: M.<z> = NumberField([theta^3 + 4, theta^2 + 3]); M
237        Number Field in z0 with defining polynomial theta^3 + 4 over its base field
238    """
239    if name is None and names is None:
240        raise TypeError, "You must specify the name of the generator."
241    if not names is None:
242        name = names
243
244    if isinstance(polynomial, (list, tuple)):
245        return NumberFieldTower(polynomial, name)
246
247    name = sage.structure.parent_gens.normalize_names(1, name)
248
249    if not isinstance(polynomial, polynomial_element.Polynomial):
250        try:
251            polynomial = polynomial.polynomial(QQ)
252        except (AttributeError, TypeError):
253            raise TypeError, "polynomial (=%s) must be a polynomial."%repr(polynomial)
254
255    #if all:
256    #    return [NumberField(f, name=name, check=check, names=names) for f, _ in polynomial.factor()]
257
258    if cache:
259        key = (polynomial, name)
260        if _nf_cache.has_key(key):
261            K = _nf_cache[key]()
262            if not K is None: return K
263
264    R = polynomial.base_ring()
265    if R == ZZ:
266        polynomial = QQ['x'](polynomial)
267    elif isinstance(R, NumberField_generic):
268        S = R.extension(polynomial, name, check=check)
269        if cache:
270            _nf_cache[key] = weakref.ref(S)
271        return S
272
273    if polynomial.degree() == 2:
274        K = NumberField_quadratic(polynomial, name, check)
275    else:
276        K = NumberField_absolute(polynomial, name, None, check)
277
278    if cache:
279        _nf_cache[key] = weakref.ref(K)
280    return K
281
282
283def NumberFieldTower(v, names, check=True):
284    """
285    Return the tower of number fields defined by the polynomials or
286    number fields in the list v.
287
288    This is the field constructed first from v[0], then over that
289    field from v[1], etc.  If all is False, then each v[i] must be
290    irreducible over the previous fields.  Otherwise a list of all
291    possible fields defined by all those polynomials is output.
292
293    If names defines a variable name a, say, then the generators of
294    the intermediate number fields are a0, a1, a2, ...
295
296    INPUT:
297        v -- a list of polynomials or number fields
298        names -- variable names
299        check -- bool (default: True) only relevant if all is False.
300               Then check irreducibility of each input polynomial.
301
302    OUTPUT:
303        a single number field or a list of number fields
304
305    EXAMPLES:
306        sage: k.<a,b,c> = NumberField([x^2 + 1, x^2 + 3, x^2 + 5]); k
307        Number Field in a with defining polynomial x^2 + 1 over its base field
308        sage: a^2
309        -1
310        sage: b^2
311        -3
312        sage: c^2
313        -5
314        sage: (a+b+c)^2
315        (2*b + 2*c)*a + 2*c*b + -9
316
317    The Galois group is a product of 3 groups of order 2:
318        sage: k.galois_group()
319        Galois group PARI group [8, 1, 3, "E(8)=2[x]2[x]2"] of degree 8 of the number field Number Field in a with defining polynomial x^2 + 1 over its base field
320
321
322    Repeatedly calling base_field allows us to descend the internally
323    constructed tower of fields:
324        sage: k.base_field()
325        Number Field in b with defining polynomial x^2 + 3 over its base field
326        sage: k.base_field().base_field()
327        Number Field in c with defining polynomial x^2 + 5
328        sage: k.base_field().base_field().base_field()
329        Rational Field
330
331    In the following examle the second polynomial reducible over the first, so
332    we get an error:
333        sage: v = NumberField([x^3 - 2, x^3 - 2], names='a')
334        Traceback (most recent call last):
335        ...
336        ValueError: defining polynomial (x^3 + -2) must be irreducible
337
338    We mix polynomial parent rings:
339        sage: k.<y> = QQ[]
340        sage: m = NumberField([y^3 - 3, x^2 + x + 1, y^3 + 2], 'beta')
341        sage: m
342        Number Field in beta0 with defining polynomial y^3 + -3 over its base field
343        sage: m.base_field ()
344        Number Field in beta1 with defining polynomial x^2 + x + 1 over its base field
345
346    A tower of quadratic fields:
347        sage: K.<a> = NumberField([x^2 + 3, x^2 + 2, x^2 + 1])
348        sage: K
349        Number Field in a0 with defining polynomial x^2 + 3 over its base field
350        sage: K.base_field()
351        Number Field in a1 with defining polynomial x^2 + 2 over its base field
352        sage: K.base_field().base_field()
353        Number Field in a2 with defining polynomial x^2 + 1
354
355    A bigger tower of quadratic fields.
356        sage: K.<a2,a3,a5,a7> = NumberField([x^2 + p for p in [2,3,5,7]]); K
357        Number Field in a2 with defining polynomial x^2 + 2 over its base field
358        sage: a2^2
359        -2
360        sage: a3^2
361        -3
362        sage: (a2+a3+a5+a7)^3
363        ((6*a5 + 6*a7)*a3 + 6*a7*a5 + -47)*a2 + (6*a7*a5 + -45)*a3 + (-41)*a5 + -37*a7
364    """
365    # there is an "all" option below -- we do not use it, since
366    # I couldn't get it to work with PARI reliably, and it isn't
367    # very useful in practice.
368    try:
369        names = sage.structure.parent_gens.normalize_names(len(v), names)
370    except IndexError:
371        names = sage.structure.parent_gens.normalize_names(1, names)
372        if len(v) > 1:
373            names = ['%s%s'%(names[0], i) for i in range(len(v))]
374
375    if not isinstance(v, (list, tuple)):
376        raise TypeError, "v must be a list or tuple"
377    if len(v) == 0:
378        return QQ
379    if len(v) == 1:
380        #if all:
381        #    f = v[0]
382        #    if not isinstance(f, polynomial_element.Polynomial):
383        #        f = QQ['x'](v[0])
384        #    F = f.factor()
385        #    return [NumberField(F[i][0], names='%s%s'%(names[0],str(i))) for i in range(len(F))]
386        #else:
387        return NumberField(v[0], names=names)
388    f = v[0]
389    w = NumberFieldTower(v[1:], names=names[1:])
390    if isinstance(f, polynomial_element.Polynomial):
391        var = f.name()
392    else:
393        var = 'x'
394
395    name = names[0]
396    #if all:
397    #    R = w[0][var]  # polynomial ring
398    #else:
399    R = w[var]  # polynomial ring
400
401    f = R(f)
402    i = 0
403
404    sep = chr(ord(name[0]) + 1)
405    #if all:
406    #    z = []
407    #    for k in w:
408    #        for g, _ in f.factor():
409    #            z.append(k.extension(g, names='%s%s%s'%(name, sep, str(i)), check=False))
410    #            i += 1
411    #    return z
412    #else:
413    return w.extension(f, name, check=check)
414
415
417    """
418    Return a quadratic field obtained by adjoining a square root of
419    $D$ to the rational numbers, where $D$ is not a perfect square.
420
421    INPUT:
422        D -- a rational number
423        name -- variable name
424        check -- bool (default: True)
425
426    OUTPUT:
427        A number field defined by a quadratic polynomial.
428
429    EXAMPLES:
431        Number Field in a with defining polynomial x^2 - 3
432        sage: K.<theta> = QuadraticField(3); K
433        Number Field in theta with defining polynomial x^2 - 3
435        Traceback (most recent call last):
436        ...
437        ValueError: D must not be a perfect square.
439        Number Field in a with defining polynomial x^2 - 9
440
441    Quadratic number fields derive from general number fields.
442        sage: type(K)
444        sage: is_NumberField(K)
445        True
446    """
447    D = QQ(D)
448    if check:
449        if D.is_square():
450            raise ValueError, "D must not be a perfect square."
451    R = polynomial_ring.PolynomialRing(QQ, 'x')
452    f = R([-D, 0, 1])
453    return NumberField(f, names, check=False)
454
455def is_AbsoluteNumberField(x):
456    """
457    Return True if x is an absolute number field.
458
459    EXAMPLES:
460        sage: is_AbsoluteNumberField(NumberField(x^2+1,'a'))
461        True
462        sage: is_AbsoluteNumberField(NumberField([x^3 + 17, x^2+1],'a'))
463        False
464
465    The rationals are a number field, but they're not of the absolute number field class.
466        sage: is_AbsoluteNumberField(QQ)
467        False
468    """
469    return isinstance(x, NumberField_absolute)
470
472    r"""
473    Return True if x is of the quadratic {\em number} field type.
474
475    EXAMPLES:
477        True
478        sage: is_QuadraticField(NumberField(x^2 - 5, 'b'))
479        True
480        sage: is_QuadraticField(NumberField(x^3 - 5, 'b'))
481        False
482
483    A quadratic field specially refers to a number field, not a finite
484    field:
486        False
487    """
489
490def is_RelativeNumberField(x):
491    """
492    Return True if x is a relative number field.
493
494    EXAMPLES:
495        sage: is_RelativeNumberField(NumberField(x^2+1,'a'))
496        False
497        sage: k.<a> = NumberField(x^3 - 2)
498        sage: l.<b> = k.extension(x^3 - 3); l
499        Number Field in b with defining polynomial x^3 + -3 over its base field
500        sage: is_RelativeNumberField(l)
501        True
502        sage: is_RelativeNumberField(QQ)
503        False
504    """
505    return isinstance(x, NumberField_relative)
506
507_cyclo_cache = {}
508def CyclotomicField(n, names=None):
509    r"""
510    Return the n-th cyclotomic field, where n is a positive integer.
511
512    INPUT:
513        n -- a positive integer
514        names -- name of generator (optional -- defaults to zetan).
515
516    EXAMPLES:
517    We create the $7$th cyclotomic field $\QQ(\zeta_7)$ with the
518    default generator name.
519        sage: k = CyclotomicField(7); k
520        Cyclotomic Field of order 7 and degree 6
521        sage: k.gen()
522        zeta7
523
524    Cyclotomic fields are of a special type.
525        sage: type(k)
526        <class 'sage.rings.number_field.number_field.NumberField_cyclotomic'>
527
528    We can specify a different generator name as follows.
529        sage: k.<z7> = CyclotomicField(7); k
530        Cyclotomic Field of order 7 and degree 6
531        sage: k.gen()
532        z7
533
534    The $n$ must be an integer.
535        sage: CyclotomicField(3/2)
536        Traceback (most recent call last):
537        ...
538        TypeError: no coercion of this rational to integer
539
540    The degree must be positive.
541        sage: CyclotomicField(0)
542        Traceback (most recent call last):
543        ...
544        ValueError: n (=0) must be a positive integer
545
546    The special case $n=1$ does \emph{not} return the rational numbers:
547        sage: CyclotomicField(1)
548        Cyclotomic Field of order 1 and degree 1
549    """
550    n = ZZ(n)
551    if n <= 0:
552        raise ValueError, "n (=%s) must be a positive integer"%n
553
554    if names is None:
555        names = "zeta%s"%n
556    names = sage.structure.parent_gens.normalize_names(1, names)
557    key = (n, names)
558    if _cyclo_cache.has_key(key):
559        K = _cyclo_cache[key]()
560        if not K is None: return K
561    K = NumberField_cyclotomic(n, names)
562    _cyclo_cache[key] = weakref.ref(K)
563    return K
564
565def is_CyclotomicField(x):
566    """
567    Return True if x is a cyclotomic field, i.e., of the special
568    cyclotomic field class.  This function does not return True
569    for a number field that just happens to be isomorphic to a
570    cyclotomic field.
571
572    EXAMPLES:
573        sage: is_CyclotomicField(NumberField(x^2 + 1,'zeta4'))
574        False
575        sage: is_CyclotomicField(CyclotomicField(4))
576        True
577        sage: is_CyclotomicField(CyclotomicField(1))
578        True
579        sage: is_CyclotomicField(QQ)
580        False
581        sage: is_CyclotomicField(7)
582        False
583    """
584    return isinstance(x, NumberField_cyclotomic)
585
586
587
588import number_field_base
589
590is_NumberField = number_field_base.is_NumberField
591
592class NumberField_generic(number_field_base.NumberField):
593    """
594    EXAMPLES:
595        sage: K.<a> = NumberField(x^3 - 2); K
596        Number Field in a with defining polynomial x^3 - 2
598        True
599    """
600    def __init__(self, polynomial, name,
601                 latex_name=None, check=True):
602        """
603        Create a number field.
604
605        EXAMPLES:
606            sage: NumberField(x^97 - 19, 'a')
607            Number Field in a with defining polynomial x^97 - 19
608
609        If you use check=False, you avoid checking irreducibility of
610        the defining polynomial, which can save time.
611            sage: K.<a> = NumberField(x^2 - 1, check=False)
612
613        It can also be dangerous:
614            sage: (a-1)*(a+1)
615            0
616        """
617        ParentWithGens.__init__(self, QQ, name)
618        if not isinstance(polynomial, polynomial_element.Polynomial):
619            raise TypeError, "polynomial (=%s) must be a polynomial"%repr(polynomial)
620
621        if check:
622            if not polynomial.is_irreducible():
623                raise ValueError, "defining polynomial (%s) must be irreducible"%polynomial
624            if not polynomial.parent().base_ring() == QQ:
625                raise TypeError, "polynomial must be defined over rational field"
626            if not polynomial.is_monic():
627                raise NotImplementedError, "number fields for non-monic polynomials not yet implemented."
628
629        self._assign_names(name)
630        if latex_name is None:
631            self.__latex_variable_name = latex_variable_name(self.variable_name())
632        else:
633            self.__latex_variable_name = latex_name
634        self.__polynomial = polynomial
635        self.__pari_bnf_certified = False
636
637    def _Hom_(self, codomain, cat=None):
638        """
639        Return homset of homomorphisms from self to the number field codomain.
640
641        The cat option is currently ignored.
642
643        EXAMPLES:
644        This function is implicitly caled by the Hom method or function.
645            sage: K.<i> = NumberField(x^2 + 1); K
646            Number Field in i with defining polynomial x^2 + 1
647            sage: K.Hom(K)
648            Automorphism group of Number Field in i with defining polynomial x^2 + 1
650            Set of field embeddings from Number Field in i with defining polynomial x^2 + 1 to Number Field in b with defining polynomial x^2 + 1
651        """
652        import morphism
653        return morphism.NumberFieldHomset(self, codomain)
654
655    def _set_structure(self, from_self, to_self, unsafe_force_change=False):
656        # Note -- never call this on a cached number field, since
657        # that could eventually lead to problems.
658        if unsafe_force_change:
659            self.__from_self = from_self
660            self.__to_self = to_self
661            return
662        try:
663            self.__from_self
664        except AttributeError:
665            self.__from_self = from_self
666            self.__to_self = to_self
667        else:
668            raise ValueError, "number field structure is immutable."
669
670    def structure(self):
671        """
672        Return fixed isomorphism or embedding structure on self.
673
674        This is used to record various isomorphisms or embeddings
675        that arise naturally in other constructions.
676
677        EXAMPLES:
678            sage: K.<z> = NumberField(x^2 + 3)
679            sage: L.<a> = K.absolute_field(); L
680            Number Field in a with defining polynomial x^2 + 3
681            sage: L.structure()
682            (Number field isomorphism from Number Field in a with defining polynomial x^2 + 3 to Number Field in z with defining polynomial x^2 + 3 given by variable name change,
683             Number field isomorphism from Number Field in z with defining polynomial x^2 + 3 to Number Field in a with defining polynomial x^2 + 3 given by variable name change)
684        """
685        try:
686            if self.__to_self is not None:
687                return self.__from_self, self.__to_self
688            else:
689                return self.__from_self, self.__to_self
690        except AttributeError:
691            f = self.hom(self)
692            self._set_structure(f,f)
693            return f, f
694
695    def primitive_element(self):
696        r"""
697        Return a primitive element for this field, i.e., an element
698        that generates it over $\QQ$.
699
700        EXAMPLES:
701            sage: K.<a> = NumberField(x^3 + 2)
702            sage: K.primitive_element()
703            a
704            sage: K.<a,b,c> = NumberField([x^2-2,x^2-3,x^2-5])
705            sage: K.primitive_element()
706            a + (-1)*b + c
707            sage: alpha = K.primitive_element(); alpha
708            a + (-1)*b + c
709            sage: alpha.minpoly()
710            x^2 + (2*b + -2*c)*x + (-2*c)*b + 6
711            sage: alpha.absolute_minpoly()
712            x^8 - 40*x^6 + 352*x^4 - 960*x^2 + 576
713        """
714        try:
715            return self.__primitive_element
716        except AttributeError:
717            pass
718        K = self.absolute_field('a')
719        from_K, to_K = K.structure()
720        self.__primitive_element = from_K(K.gen())
721        return self.__primitive_element
722
723    def subfield(self, alpha, name=None):
724        r"""
725        Return an absolute number field K isomorphic to QQ(alpha) and
726        a map from K to self that sends the generator of K to alpha.
727
728        INPUT:
729            alpha -- an element of self, or something that coerces
730                     to an element of self.
731
732        OUTPUT:
733            K -- a number field
734            from_K -- a homomorphism from K to self that sends the
735                      generator of K to alpha.
736
737        EXAMPLES:
738            sage: K.<a> = NumberField(x^4 - 3); K
739            Number Field in a with defining polynomial x^4 - 3
740            sage: H, from_H = K.subfield(a^2, name='b')
741            sage: H
742            Number Field in b with defining polynomial x^2 - 3
743            sage: from_H(H.0)
744            a^2
745            sage: from_H
746            Ring morphism:
747              From: Number Field in b with defining polynomial x^2 - 3
748              To:   Number Field in a with defining polynomial x^4 - 3
749              Defn: b |--> a^2
750
751
752        You can also view a number field as having a different
753        generator by just chosing the input to generate the
754        whole filed; for that it is better to use
755        \code{self.change_generator}, which gives isomorphisms
756        in both directions.
757        """
758        if name is None:
759            name = self.variable_name() + '0'
760        beta = self(alpha)
761        f = beta.minpoly()
762        K = NumberField(f, names=name)
763        from_K = K.hom([beta])
764        return K, from_K
765
766    def change_generator(self, alpha, name=None):
767        r"""
768        Given the number field self, construct another isomorphic
769        number field $K$ generated by the element alpha of self, along
770        with isomorphisms from $K$ to self and from self to $K$.
771
772        EXAMPLES:
773            sage: K.<i> = NumberField(x^2 + 1); K
774            Number Field in i with defining polynomial x^2 + 1
775            sage: L.<i> = NumberField(x^2 + 1); L
776            Number Field in i with defining polynomial x^2 + 1
777            sage: K, from_K, to_K = L.change_generator(i/2 + 3)
778            sage: K
779            Number Field in i0 with defining polynomial x^2 - 6*x + 37/4
780            sage: from_K
781            Ring morphism:
782              From: Number Field in i0 with defining polynomial x^2 - 6*x + 37/4
783              To:   Number Field in i with defining polynomial x^2 + 1
784              Defn: i0 |--> 1/2*i + 3
785            sage: to_K
786            Ring morphism:
787              From: Number Field in i with defining polynomial x^2 + 1
788              To:   Number Field in i0 with defining polynomial x^2 - 6*x + 37/4
789              Defn: i |--> 2*i0 - 6
790
791        We compute the image of the generator $\sqrt{-1}$ of $L$.
792            sage: to_K(L.0)
793            2*i0 - 6
794
795        Note that he image is indeed a square root of -1.
796            sage: to_K(L.0)^2
797            -1
798            sage: from_K(to_K(L.0))
799            i
800            sage: to_K(from_K(K.0))
801            i0
802        """
803        alpha = self(alpha)
804        K, from_K = self.subfield(alpha, name=name)
805        if K.degree() != self.degree():
806            raise ValueError, "alpha must generate a field of degree %s, but alpha generates a subfield of degree %s"%(self.degree(), K.degree())
807        # Now compute to_K, which is an isomorphism
808        # from self to K such that from_K(to_K(x)) == x for all x,
809        # and to_K(from_K(y)) == y.
810        # To do this, we must compute the image of self.gen()
811        # under to_K.   This means writing self.gen() as a
812        # polynomial in alpha, which is possible by the degree
813        # check above.  This latter we do by linear algebra.
814        phi = alpha.coordinates_in_terms_of_powers()
815        c = phi(self.gen())
816        to_K = self.hom([K(c)])
817        return K, from_K, to_K
818
819    def is_absolute(self):
820        raise NotImplementedError
821
822    def is_relative(self):
823        """
824        EXAMPLES:
825            sage: K.<a> = NumberField(x^10 - 2)
826            sage: K.is_absolute()
827            True
828            sage: K.is_relative()
829            False
830        """
831        return not self.is_absolute()
832
833    def absolute_field(self, names):
834        """
835        Returns self as an absolute extension over QQ.
836
837        OUTPUT:
838            K -- this number field (since it is already absolute)
839
840        Also, \code{K.structure()} returns from_K and to_K, where
841        from_K is an isomorphism from K to self and to_K is an isomorphism
842        from self to K.
843
844        EXAMPLES:
845            sage: K = CyclotomicField(5)
846            sage: K.absolute_field('a')
847            Number Field in a with defining polynomial x^4 + x^3 + x^2 + x + 1
848        """
849        try:
850            return self.__absolute_field[names]
851        except KeyError:
852            pass
853        except AttributeError:
854            self.__absolute_field = {}
855        K = NumberField(self.defining_polynomial(), names, cache=False)
856        K._set_structure(maps.NameChangeMap(K, self), maps.NameChangeMap(self, K))
857        self.__absolute_field[names] = K
858        return K
859
860    def is_isomorphic(self, other):
861        """
862        Return True if self is isomorphic as a number field to other.
863
864        EXAMPLES:
865            sage: k.<a> = NumberField(x^2 + 1)
866            sage: m.<b> = NumberField(x^2 + 4)
867            sage: k.is_isomorphic(m)
868            True
869            sage: m.<b> = NumberField(x^2 + 5)
870            sage: k.is_isomorphic (m)
871            False
872
873            sage: k = NumberField(x^3 + 2, 'a')
874            sage: k.is_isomorphic(NumberField((x+1/3)^3 + 2, 'b'))
875            True
876            sage: k.is_isomorphic(NumberField(x^3 + 4, 'b'))
877            True
878            sage: k.is_isomorphic(NumberField(x^3 + 5, 'b'))
879            False
880        """
881        if not isinstance(other, NumberField_generic):
882            raise ValueError, "other must be a generic number field."
883        t = self.pari_polynomial().nfisisom(other.pari_polynomial())
884        return t != 0
885
886    def complex_embeddings(self, prec=53):
887        r"""
888        Return all homomorphisms of this number field into the
889        approximate complex field with precision prec.
890
891        If prec is 53 (the default), then the complex double field is
892        used; otherwise the arbitrary precision (but slow) complex
893        field is used.  If you want 53-bit arbitrary precision then
894        do \code{self.embeddings(ComplexField(53))}.
895
896        EXAMPLES:
897            sage: k.<a> = NumberField(x^5 + x + 17)
898            sage: v = k.complex_embeddings()
899            sage: [phi(k.0^2) for phi in v] # random low order bits
900            [2.97572074038 + 1.73496602657e-16*I, -2.40889943716 + 1.90254105304*I, -2.40889943716 - 1.90254105304*I, 0.921039066973 + 3.07553311885*I, 0.921039066973 - 3.07553311885*I]
901            sage: K.<a> = NumberField(x^3 + 2)
902            sage: K.complex_embeddings() # random low order bits
903            [Ring morphism:
904              From: Number Field in a with defining polynomial x^3 + 2
905              To:   Complex Double Field
906              Defn: a |--> -1.25992104989 - 3.88578058619e-16*I,
907            ...]
908            sage: K.complex_embeddings(100)
909            [Ring morphism:
910              From: Number Field in a with defining polynomial x^3 + 2
911              To:   Complex Field with 100 bits of precision
912              Defn: a |--> -1.2599210498948731647672106073,
913            ...]
914        """
915        if prec == 53:
916            CC = sage.rings.complex_double.CDF
917        else:
918            CC = sage.rings.complex_field.ComplexField(prec)
919        return self.embeddings(CC)
920
921    def real_embeddings(self, prec=53):
922        r"""
923        Return all homomorphisms of this number field into the
924        approximate real field with precision prec.
925
926        If prec is 53 (the default), then the real double field is
927        used; otherwise the arbitrary precision (but slow) real field
928        is used.
929
930        EXAMPLES:
931            sage: K.<a> = NumberField(x^3 + 2)
932            sage: K.real_embeddings()
933            [Ring morphism:
934              From: Number Field in a with defining polynomial x^3 + 2
935              To:   Real Double Field
936              Defn: a |--> -1.25992104989]
937            sage: K.real_embeddings(16)
938            [Ring morphism:
939              From: Number Field in a with defining polynomial x^3 + 2
940              To:   Real Field with 16 bits of precision
941              Defn: a |--> -1.260]
942            sage: K.real_embeddings(100)
943            [Ring morphism:
944              From: Number Field in a with defining polynomial x^3 + 2
945              To:   Real Field with 100 bits of precision
946              Defn: a |--> -1.2599210498948731647672106073]
947        """
948        if prec == 53:
949            K = sage.rings.real_double.RDF
950        else:
951            K = sage.rings.real_mpfr.RealField(prec)
952        return self.embeddings(K)
953
954    def latex_variable_name(self, name=None):
955        """
956        Return the latex representation of the variable name for
957        this number field.
958
959        EXAMPLES:
960            sage: NumberField(x^2 + 3, 'a').latex_variable_name()
961            'a'
962            sage: NumberField(x^3 + 3, 'theta3').latex_variable_name()
963            '\\theta_{3}'
964            sage: CyclotomicField(5).latex_variable_name()
965            '\\zeta_{5}'
966        """
967        if name is None:
968            return self.__latex_variable_name
969        else:
970            self.__latex_variable_name = name
971
972    def _repr_(self):
973        """
974        Return string representation of this number field.
975
976        EXAMPLES:
977            sage: k.<a> = NumberField(x^13 - (2/3)*x + 3)
978            sage: k._repr_()
979            'Number Field in a with defining polynomial x^13 - 2/3*x + 3'
980        """
981        return "Number Field in %s with defining polynomial %s"%(
982                   self.variable_name(), self.polynomial())
983
984    def _latex_(self):
985        r"""
986        Return latex representation of this number field.  This is viewed
987        as a polynomial quotient ring over a field.
988
989        EXAMPLES:
990            sage: k.<a> = NumberField(x^13 - (2/3)*x + 3)
991            sage: k._latex_()
992            '\\mathbf{Q}[a]/(a^{13} - \\frac{2}{3}a + 3)'
993            sage: latex(k)
994            \mathbf{Q}[a]/(a^{13} - \frac{2}{3}a + 3)
995
996        Numbered variables are often correctly typeset:
997            sage: k.<theta25> = NumberField(x^25+x+1)
998            sage: print k._latex_()
999            \mathbf{Q}[\theta_{25}]/(\theta_{25}^{25} + \theta_{25} + 1)
1000        """
1001        return "%s[%s]/(%s)"%(latex(QQ), self.latex_variable_name(),
1002                              self.polynomial()._latex_(self.latex_variable_name()))
1003
1004    def __call__(self, x):
1005        """
1006        Coerce x into this number field.
1007
1008        EXAMPLES:
1009            sage: K.<a> = NumberField(x^3 + 17)
1010            sage: K(a) is a
1011            True
1012            sage: K('a^2 + 2/3*a + 5')
1013            a^2 + 2/3*a + 5
1014            sage: K('1').parent()
1015            Number Field in a with defining polynomial x^3 + 17
1016            sage: K(3/5).parent()
1017            Number Field in a with defining polynomial x^3 + 17
1018        """
1019        if isinstance(x, number_field_element.NumberFieldElement):
1020            if x.parent() is self:
1021                return x
1022            elif x.parent() == self:
1023                return self._element_class(self, x.polynomial())
1024            elif isinstance(x, number_field_element.OrderElement_absolute) or isinstance(x, number_field_element.OrderElement_relative):
1025                if x.parent().number_field() is self:
1026                    return self._element_class(self, x)
1027                x = x.parent().number_field()(x)
1028            return self._coerce_from_other_number_field(x)
1029        elif isinstance(x,str):
1030            return self._coerce_from_str(x)
1031        return self._coerce_non_number_field_element_in(x)
1032
1033    def _coerce_from_str(self, x):
1034        """
1035        Coerce a string representation of an element of this
1036        number field into this number field.
1037
1038        INPUT:
1039            x -- string
1040
1041        EXAMPLES:
1042            sage: k.<theta25> = NumberField(x^3+(2/3)*x+1)
1043            sage: k._coerce_from_str('theta25^3 + (1/3)*theta25')
1044            -1/3*theta25 - 1
1045
1046        This function is called by the coerce method when it gets a string
1047        as input:
1048            sage: k('theta25^3 + (1/3)*theta25')
1049            -1/3*theta25 - 1
1050        """
1051        # provide string coercion, as
1052        # for finite fields
1053        w = sage.misc.all.sage_eval(x,locals=\
1054                                  {self.variable_name():self.gen()})
1055        if not (is_Element(w) and w.parent() is self):
1056            return self(w)
1057        else:
1058            return w
1059
1060    def _coerce_from_other_number_field(self, x):
1061        """
1062        Coerce a number field element x into this number field.
1063
1064        In most cases this currently doesn't work (since it is
1065        barely implemented) -- it only works for constants.
1066
1067        INPUT:
1068            x -- an element of some number field
1069
1070        EXAMPLES:
1071            sage: K.<a> = NumberField(x^3 + 2)
1072            sage: L.<b> = NumberField(x^2 + 1)
1073            sage: K._coerce_from_other_number_field(L(2/3))
1074            2/3
1075        """
1076        f = x.polynomial()
1077        if f.degree() <= 0:
1078            return self._element_class(self, f[0])
1079        # todo: more general coercion if embedding have been asserted
1080        raise TypeError, "Cannot coerce %s into %s"%(x,self)
1081
1082    def _coerce_non_number_field_element_in(self, x):
1083        """
1084        Coerce a non-number field element x into this number field.
1085
1086        INPUT:
1087            x -- a non number field element x, e.g., a list, integer,
1088            rational, or polynomial.
1089
1090        EXAMPLES:
1091            sage: K.<a> = NumberField(x^3 + 2/3)
1092            sage: K._coerce_non_number_field_element_in(-7/8)
1093            -7/8
1094            sage: K._coerce_non_number_field_element_in([1,2,3])
1095            3*a^2 + 2*a + 1
1096
1097        The list is just turned into a polynomial in the generator.
1098            sage: K._coerce_non_number_field_element_in([0,0,0,1,1])
1099            -2/3*a - 2/3
1100
1101        Not any polynomial coerces in, e.g., not this one in characteristic 7.
1102            sage: f = GF(7)['y']([1,2,3]); f
1103            3*y^2 + 2*y + 1
1104            sage: K._coerce_non_number_field_element_in(f)
1105            Traceback (most recent call last):
1106            ...
1107            TypeError
1108        """
1109        if isinstance(x, (int, long, rational.Rational,
1110                              integer.Integer, pari_gen,
1111                              list)):
1112            return self._element_class(self, x)
1113
1114        try:
1115            if isinstance(x, polynomial_element.Polynomial):
1116                return self._element_class(self, x)
1117
1118            return self._element_class(self, x._rational_())
1119        except (TypeError, AttributeError), msg:
1120            pass
1121        raise TypeError
1122
1123    def _coerce_impl(self, x):
1124        """
1125        Canonical coercion of x into self.
1126
1127        Currently integers, rationals, and this field itself coerce
1128        canonical into this field.
1129
1130        EXAMPLES:
1131            sage: S.<y> = NumberField(x^3 + x + 1)
1132            sage: S._coerce_impl(int(4))
1133            4
1134            sage: S._coerce_impl(long(7))
1135            7
1136            sage: S._coerce_impl(-Integer(2))
1137            -2
1138            sage: z = S._coerce_impl(-7/8); z, type(z)
1139            (-7/8, <type 'sage.rings.number_field.number_field_element.NumberFieldElement_absolute'>)
1140            sage: S._coerce_impl(y) is y
1141            True
1142
1143        There are situations for which one might imagine canonical
1144        coercion could make sense (at least after fixing choices), but
1145        which aren't yet implemented:
1147            sage: K._coerce_impl(sqrt(2))
1148            Traceback (most recent call last):
1149            ...
1150            TypeError
1151        """
1152        if isinstance(x, (rational.Rational, integer.Integer, int, long)):
1153            return self._element_class(self, x)
1154        elif isinstance(x, number_field_element.NumberFieldElement):
1155            from sage.rings.number_field.order import is_NumberFieldOrder
1156            if x.parent() is self:
1157                return x
1158            elif is_NumberFieldOrder(x.parent()) and x.parent().number_field() is self:
1159                return self._element_class(self, x.polynomial())
1160            elif x.parent() == self:
1161                return self._element_class(self, x.list())
1162        raise TypeError
1163
1164    def category(self):
1165        """
1166        Return the category of number fields.
1167
1168        EXAMPLES:
1169            sage: NumberField(x^2 + 3, 'a').category()
1170            Category of number fields
1171            sage: category(NumberField(x^2 + 3, 'a'))
1172            Category of number fields
1173
1174        The special types of number fields, e.g., quadratic fields,
1175        don't have their own category:
1177            Category of number fields
1178        """
1179        from sage.categories.all import NumberFields
1180        return NumberFields()
1181
1182    def __cmp__(self, other):
1183        """
1184        Compare a number field with something else.
1185
1186        INPUT:
1187            other -- arbitrary Python object.
1188
1189        If other is not a number field, then the types of self and
1190        other are compared.  If both are number fields, then the
1191        variable names are compared.  If those are the same, then the
1192        underlying defining polynomials are compared.  If the
1193        polynomials are the same, the number fields are considered
1194        equal'', but need not be identical.  Coercion between equal
1195        number fields is allowed.
1196
1197        EXAMPLES:
1198            sage: k.<a> = NumberField(x^3 + 2); m.<b> = NumberField(x^3 + 2)
1199            sage: cmp(k,m)
1200            -1
1201            sage: cmp(m,k)
1202            1
1203            sage: k == QQ
1204            False
1205            sage: k.<a> = NumberField(x^3 + 2); m.<a> = NumberField(x^3 + 2)
1206            sage: k is m
1207            True
1209            sage: k is m
1210            False
1211            sage: k == m
1212            True
1213        """
1214        if not isinstance(other, NumberField_generic):
1215            return cmp(type(self), type(other))
1216        c = cmp(self.variable_name(), other.variable_name())
1217        if c: return c
1218        return cmp(self.__polynomial, other.__polynomial)
1219
1220    def _ideal_class_(self):
1221        """
1222        Return the Python class used in defining ideals of the ring of
1223        integes of this number field.
1224
1225        This function is required by the general ring/ideal machinery.
1226
1227        EXAMPLES:
1228            sage: NumberField(x^2 + 2, 'c')._ideal_class_()
1229            <class 'sage.rings.number_field.number_field_ideal.NumberFieldIdeal'>
1230        """
1231        return sage.rings.number_field.number_field_ideal.NumberFieldIdeal
1232
1233    def ideal(self, *gens, **kwds):
1234        return self.fractional_ideal(*gens, **kwds)
1235
1236    def fractional_ideal(self, *gens, **kwds):
1237        r"""
1238        Return the ideal in $\mathcal{O}_K$ generated by gens.  This
1239        overrides the \code{sage.rings.ring.Field} method to use the
1240        \code{sage.rings.ring.Ring} one instead, since we're not really
1241        concerned with ideals in a field but in its ring of integers.
1242
1243        INPUT:
1244            gens -- a list of generators, or a number field ideal.
1245
1246        EXAMPLES:
1247            sage: K.<a> = NumberField(x^3-2)
1248            sage: K.ideal([a])
1249            Fractional ideal (a) of Number Field in a with defining polynomial x^3 - 2
1250
1251        One can also input in a number field ideal itself.
1252            sage: K.ideal(K.ideal(a))
1253            Fractional ideal (a) of Number Field in a with defining polynomial x^3 - 2
1254        """
1255        if len(gens) == 1 and isinstance(gens[0], (list, tuple)):
1256            gens = gens[0]
1257        if len(gens) == 1 and is_NumberFieldIdeal(gens[0]):
1258            I = gens[0]
1259            if I.number_field() == self:
1260                return I
1261            else:
1262                gens = I.gens()
1263        return sage.rings.ring.Ring.ideal(self, gens, **kwds)
1264
1265    def _is_valid_homomorphism_(self, codomain, im_gens):
1266        """
1267        Return whether or not there is a homomorphism defined by the
1268        given images of generators.
1269
1270        To do this we just check that the elements of the image of the
1271        given generator (im_gens always has length 1) satisfies the
1272        relation of the defining poly of this field.
1273
1274        EXAMPLES:
1275            sage: k.<a> = NumberField(x^2 - 3)
1276            sage: k._is_valid_homomorphism_(QQ, [0])
1277            False
1278            sage: k._is_valid_homomorphism_(k, [])
1279            False
1280            sage: k._is_valid_homomorphism_(k, [a])
1281            True
1282            sage: k._is_valid_homomorphism_(k, [-a])
1283            True
1284            sage: k._is_valid_homomorphism_(k, [a+1])
1285            False
1286        """
1287        try:
1288            if len(im_gens) != 1:
1289                return False
1290            # We need that elements of the base ring of the polynomial
1291            # ring map canonically into codomain.
1292            codomain._coerce_(rational.Rational(1))
1293            f = self.defining_polynomial()
1294            return codomain(f(im_gens[0])) == 0
1295        except (TypeError, ValueError):
1296            return False
1297
1298    def pari_polynomial(self):
1299        """
1300        PARI polynomial corresponding to polynomial that defines
1301        this field.   This is always a polynomial in the variable "x".
1302
1303        EXAMPLES:
1304            sage: y = polygen(QQ)
1305            sage: k.<a> = NumberField(y^2 - 3/2*y + 5/3)
1306            sage: k.pari_polynomial()
1307            x^2 - 3/2*x + 5/3
1308        """
1309        try:
1310            return self.__pari_polynomial
1311        except AttributeError:
1312            poly = self.polynomial()
1313            with localvars(poly.parent(), 'x'):
1314                self.__pari_polynomial = poly._pari_()
1315            return self.__pari_polynomial
1316
1317    def pari_nf(self):
1318        """
1319        PARI number field corresponding to this field.
1320
1321        This is the number field constructed using nfinit.
1322        This is the same as the number field got by doing
1323        pari(self) or gp(self).
1324
1325        EXAMPLES:
1326            sage: k.<a> = NumberField(x^4 - 3*x + 7); k
1327            Number Field in a with defining polynomial x^4 - 3*x + 7
1328            sage: k.pari_nf()[:4]
1329            [x^4 - 3*x + 7, [0, 2], 85621, 1]
1330            sage: pari(k)[:4]
1331            [x^4 - 3*x + 7, [0, 2], 85621, 1]
1332
1333            sage: k.<a> = NumberField(x^4 - 3/2*x + 5/3); k
1334            Number Field in a with defining polynomial x^4 - 3/2*x + 5/3
1335            sage: k.pari_nf()
1336            Traceback (most recent call last):
1337            ...
1338            TypeError: Unable to coerce number field defined by non-integral polynomial to PARI.
1339            sage: pari(k)
1340            Traceback (most recent call last):
1341            ...
1342            TypeError: Unable to coerce number field defined by non-integral polynomial to PARI.
1343            sage: gp(k)
1344            Traceback (most recent call last):
1345            ...
1346            TypeError: Unable to coerce number field defined by non-integral polynomial to PARI.
1347        """
1348        if self.defining_polynomial().denominator() != 1:
1349            raise TypeError, "Unable to coerce number field defined by non-integral polynomial to PARI."
1350        try:
1351            return self.__pari_nf
1352        except AttributeError:
1353            f = self.pari_polynomial()
1354            self.__pari_nf = f.nfinit()
1355            return self.__pari_nf
1356
1357    def _pari_init_(self):
1358        """
1359        Needed for conversion of number field to PARI.
1360
1361        This only works if the defining polynomial of this number
1362        field is integral and monic.
1363
1364        EXAMPLES:
1365            sage: k = NumberField(x^2 + x + 1, 'a')
1366            sage: k._pari_init_()
1367            'nfinit(x^2 + x + 1)'
1368            sage: k._pari_()
1369            [x^2 + x + 1, [0, 1], -3, 1, ... [1, x], [1, 0; 0, 1], [1, 0, 0, -1; 0, 1, 1, -1]]
1370            sage: pari(k)
1371            [x^2 + x + 1, [0, 1], -3, 1, ...[1, x], [1, 0; 0, 1], [1, 0, 0, -1; 0, 1, 1, -1]]
1372        """
1373        if self.defining_polynomial().denominator() != 1:
1374            raise TypeError, "Unable to coerce number field defined by non-integral polynomial to PARI."
1375        return 'nfinit(%s)'%self.pari_polynomial()
1376
1377    def pari_bnf(self, certify=False, units=True):
1378        """
1379        PARI big number field corresponding to this field.
1380
1381        EXAMPLES:
1382            sage: k.<a> = NumberField(x^2 + 1); k
1383            Number Field in a with defining polynomial x^2 + 1
1384            sage: len(k.pari_bnf())
1385            10
1386            sage: k.pari_bnf()[:4]
1387            [[;], matrix(0,7), [;], ...]
1388            sage: len(k.pari_nf())
1389            9
1390        """
1391        if self.defining_polynomial().denominator() != 1:
1392            raise TypeError, "Unable to coerce number field defined by non-integral polynomial to PARI."
1393        try:
1394            if certify:
1395                self.pari_bnf_certify()
1396            return self.__pari_bnf
1397        except AttributeError:
1398            f = self.pari_polynomial()
1399            if units:
1400                self.__pari_bnf = f.bnfinit(1)
1401            else:
1402                self.__pari_bnf = f.bnfinit()
1403            if certify:
1404                self.pari_bnf_certify()
1405            return self.__pari_bnf
1406
1407    def pari_bnf_certify(self):
1408        """
1409        Run the PARI bnfcertify function to ensure the correctness of answers.
1410
1411        If this function returns True (and doesn't raise a
1412        ValueError), then certification succeeded, and results that
1413        use the PARI bnf structure with this field are supposed to be
1414        correct.
1415
1416        WARNING: I wouldn't trust this to mean that everything
1417        computed involving this number field is actually correct.
1418
1419        EXAMPLES:
1420            sage: k.<a> = NumberField(x^7 + 7); k
1421            Number Field in a with defining polynomial x^7 + 7
1422            sage: k.pari_bnf_certify()
1423            True
1424        """
1425        if self.defining_polynomial().denominator() != 1:
1426            raise TypeError, "Unable to coerce number field defined by non-integral polynomial to PARI."
1427        if not self.__pari_bnf_certified:
1428            if self.pari_bnf(certify=False, units=True).bnfcertify() != 1:
1429                raise ValueError, "The result is not correct according to bnfcertify"
1430            self.__pari_bnf_certified = True
1431        return self.__pari_bnf_certified
1432
1433    def characteristic(self):
1434        """
1435        Return the characteristic of this number field, which is
1436        of course 0.
1437
1438        EXAMPLES:
1439            sage: k.<a> = NumberField(x^99 + 2); k
1440            Number Field in a with defining polynomial x^99 + 2
1441            sage: k.characteristic()
1442            0
1443        """
1444        return 0
1445
1446    def class_group(self, proof=None, names='c'):
1447        r"""
1448        Return the class group of the ring of integers of this number field.
1449
1450        INPUT:
1451            proof -- if True then compute the classgroup provably correctly.
1452                     Default is True.  Call number_field_proof to change
1453                     this default globally.
1454            names -- names of the generators of this class group.
1455
1456        OUTPUT:
1457            The class group of this number field.
1458
1459        EXAMPLES:
1460            sage: K.<a> = NumberField(x^2 + 23)
1461            sage: G = K.class_group(); G
1462            Class group of order 3 with structure C3 of Number Field in a with defining polynomial x^2 + 23
1463            sage: G.0
1464            Fractional ideal class (2, 1/2*a - 1/2) of Number Field in a with defining polynomial x^2 + 23
1465            sage: G.gens()
1466            [Fractional ideal class (2, 1/2*a - 1/2) of Number Field in a with defining polynomial x^2 + 23]
1467
1468            sage: G.number_field()
1469            Number Field in a with defining polynomial x^2 + 23
1470            sage: G is K.class_group()
1471            True
1472            sage: G is K.class_group(proof=False)
1473            False
1474            sage: G.gens()
1475            [Fractional ideal class (2, 1/2*a - 1/2) of Number Field in a with defining polynomial x^2 + 23]
1476
1477        There can be multiple generators:
1478            sage: k.<a> = NumberField(x^2 + 20072)
1479            sage: G = k.class_group(); G
1480            Class group of order 76 with structure C38 x C2 of Number Field in a with defining polynomial x^2 + 20072
1481            sage: G.gens()
1482            [Fractional ideal class (41, a + 10) of Number Field in a with defining polynomial x^2 + 20072, Fractional ideal class (2, -1/2*a) of Number Field in a with defining polynomial x^2 + 20072]
1483            sage: G.0
1484            Fractional ideal class (41, a + 10) of Number Field in a with defining polynomial x^2 + 20072
1485            sage: G.0^20
1486            Fractional ideal class (43, a + 3) of Number Field in a with defining polynomial x^2 + 20072
1487            sage: G.0^38
1488            Trivial principal fractional ideal class of Number Field in a with defining polynomial x^2 + 20072
1489            sage: G.1
1490            Fractional ideal class (2, -1/2*a) of Number Field in a with defining polynomial x^2 + 20072
1491            sage: G.1^2
1492            Trivial principal fractional ideal class of Number Field in a with defining polynomial x^2 + 20072
1493
1494        Class groups of Hecke polynomials tend to be very small:
1495            sage: f = ModularForms(97, 2).T(2).charpoly()
1496            sage: f.factor()
1497            (x - 3) * (x^3 + 4*x^2 + 3*x - 1) * (x^4 - 3*x^3 - x^2 + 6*x - 1)
1498            sage: for g,_ in f.factor(): print NumberField(g,'a').class_group().order()
1499            ...
1500            1
1501            1
1502            1
1503        """
1504        proof = proof_flag(proof)
1505        try:
1506            return self.__class_group[proof, names]
1507        except KeyError:
1508            pass
1509        except AttributeError:
1510            self.__class_group = {}
1511        k = self.pari_bnf(proof)
1512        cycle_structure = eval(str(k.getattr('clgp.cyc')))
1513
1514        # First gens is a pari list of pari gens
1515        gens = k.getattr('clgp.gen')
1516        R    = self.polynomial_ring()
1517
1518        # Next gens is a list of ideals.
1519        gens = [self.ideal([self(R(convert_from_zk_basis(self, y))) for y in x]) for x in gens]
1520
1521        G    = ClassGroup(cycle_structure, names, self, gens)
1522        self.__class_group[proof,names] = G
1523        return G
1524
1525    def class_number(self, proof=None):
1526        """
1527        Return the class number of this number field, as an integer.
1528
1529        INPUT:
1530            proof -- bool (default: True unless you called number_field_proof)
1531
1532        EXAMPLES:
1533            sage: NumberField(x^2 + 23, 'a').class_number()
1534            3
1535            sage: NumberField(x^2 + 163, 'a').class_number()
1536            1
1537            sage: NumberField(x^3 + x^2 + 997*x + 1, 'a').class_number(proof=False)
1538            1539
1539        """
1540        proof = proof_flag(proof)
1541        return self.class_group(proof).order()
1542
1543    def composite_fields(self, other, names=None):
1544        """
1545        List of all possible composite number fields formed from self
1546        and other.
1547
1548        INPUT:
1549            other -- a number field
1550            names -- generator name for composite fields
1551
1552        OUTPUT:
1553            list -- list of the composite fields.
1554
1555        EXAMPLES:
1556            sage: K.<a> = NumberField(x^4 - 2)
1557            sage: K.composite_fields(K)
1558            [Number Field in a0 with defining polynomial x^4 - 162,
1559             Number Field in a1 with defining polynomial x^4 - 2,
1560             Number Field in a2 with defining polynomial x^8 + 28*x^4 + 2500]
1561            sage: k.<a> = NumberField(x^3 + 2)
1562            sage: m.<b> = NumberField(x^3 + 2)
1563            sage: k.composite_fields(m, 'c')
1564            [Number Field in c0 with defining polynomial x^3 - 2,
1565             Number Field in c1 with defining polynomial x^6 - 40*x^3 + 1372]
1566        """
1567        if names is None:
1568            sv = self.variable_name(); ov = other.variable_name()
1569            names = sv + (ov if ov != sv else "")
1570        if not isinstance(other, NumberField_generic):
1571            raise TypeError, "other must be a number field."
1572        f = self.pari_polynomial()
1573        g = other.pari_polynomial()
1574        C = f.polcompositum(g)
1575        R = self.polynomial().parent()
1576        C = [R(h) for h in C]
1577        if len(C) == 1:
1578            return [NumberField(C[0], names)]
1579        else:
1580            name = sage.structure.parent_gens.normalize_names(1, names)[0]
1581            return [NumberField(C[i], name + str(i)) for i in range(len(C))]
1582
1583    def absolute_degree(self):
1584        return self.polynomial().degree()
1585
1586    def degree(self):
1587        """
1588        Return the degree of this number field.
1589
1590        EXAMPLES:
1591            sage: NumberField(x^3 + x^2 + 997*x + 1, 'a').degree()
1592            3
1593            sage: NumberField(x + 1, 'a').degree()
1594            1
1595            sage: NumberField(x^997 + 17*x + 3, 'a', check=False).degree()
1596            997
1597        """
1598        return self.polynomial().degree()
1599
1600    def different(self):
1601        r"""
1602        Compute the different fractional ideal of this number field.
1603
1604        The different is the set of all $x$ in $K$ such that the trace
1605        of $xy$ is an integer for all $y \in O_K$.
1606
1607        EXAMPLES:
1608            sage: k.<a> = NumberField(x^2 + 23)
1609            sage: d = k.different()
1611            Fractional ideal (-a) of Number Field in a with defining polynomial x^2 + 23
1612            sage: d.norm()
1613            23
1614            sage: k.disc()
1615            -23
1616
1617        The different is cached:
1618            sage: d is k.different()
1619            True
1620
1621        Another example:
1622            sage: k.<b> = NumberField(x^2 - 123)
1623            sage: d = k.different(); d
1624            Fractional ideal (2*b) of Number Field in b with defining polynomial x^2 - 123
1625            sage: d.norm()
1626            492
1627            sage: k.disc()
1628            492
1629        """
1630        try:
1631            return self.__different
1632
1633        except AttributeError:
1634
1635            diff = self.pari_nf().getattr('diff')
1636            zk_basis = self.pari_nf().getattr('zk')
1637            basis_elts = zk_basis * diff
1638            R = self.polynomial().parent()
1639            self.__different = self.ideal([ self(R(x)) for x in basis_elts ])
1640            return self.__different
1641
1642    def discriminant(self, v=None):
1643        """
1644        Returns the discriminant of the ring of integers of the number field,
1645        or if v is specified, the determinant of the trace pairing
1646        on the elements of the list v.
1647
1648        INPUT:
1649            v (optional) -- list of element of this number field
1650        OUTPUT:
1651            Integer if v is omitted, and Rational otherwise.
1652
1653        EXAMPLES:
1654            sage: K.<t> = NumberField(x^3 + x^2 - 2*x + 8)
1655            sage: K.disc()
1656            -503
1657            sage: K.disc([1, t, t^2])
1658            -2012
1659            sage: K.disc([1/7, (1/5)*t, (1/3)*t^2])
1660            -2012/11025
1661            sage: (5*7*3)^2
1662            11025
1663        """
1664        if v == None:
1665            try:
1666                return self.__disc
1667            except AttributeError:
1668                self.__disc = ZZ(str(self.pari_polynomial().nfdisc()))
1669                return self.__disc
1670        else:
1671            return QQ(self.trace_pairing(v).det())
1672
1673    def disc(self, v=None):
1674        """
1675        Shortcut for self.discriminant.
1676
1677        EXAMPLES:
1678            sage: k.<b> = NumberField(x^2 - 123)
1679            sage: k.disc()
1680            492
1681        """
1682        return self.discriminant(v=v)
1683
1684    def elements_of_norm(self, n, proof=None):
1685        r"""
1686        Return a list of solutions modulo units of positive norm to
1687        $Norm(a) = n$, where a can be any integer in this number field.
1688
1689        INPUT:
1690            proof -- default: True, unless you called number_field_proof and
1691            set it otherwise.
1692
1693        EXAMPLES:
1694            sage: K.<a> = NumberField(x^2+1)
1695            sage: K.elements_of_norm(3)
1696            []
1697            sage: K.elements_of_norm(50)
1698            [7*a - 1, -5*a + 5, a - 7]           # 32-bit
1699            [7*a - 1, -5*a + 5, -7*a - 1]        # 64-bit
1700        """
1701        proof = proof_flag(proof)
1702        B = self.pari_bnf(proof).bnfisintnorm(n)
1703        R = self.polynomial().parent()
1704        return [self(QQ['x'](R(g))) for g in B]
1705
1706    def extension(self, poly, name=None, names=None, check=True):
1707        """
1708        Return the relative extension of this field by a given polynomial.
1709
1710        EXAMPLES:
1711            sage: K.<a> = NumberField(x^3 - 2)
1712            sage: R.<t> = K[]
1713            sage: L.<b> = K.extension(t^2 + a); L
1714            Number Field in b with defining polynomial t^2 + a over its base field
1715
1716        We create another extension.
1717            sage: k.<a> = NumberField(x^2 + 1); k
1718            Number Field in a with defining polynomial x^2 + 1
1719            sage: y = var('y')
1720            sage: m.<b> = k.extension(y^2 + 2); m
1721            Number Field in b with defining polynomial y^2 + 2 over its base field
1722
1723        Note that b is a root of $y^2 + 2$:
1724            sage: b.minpoly()
1725            x^2 + 2
1726            sage: b.minpoly('z')
1727            z^2 + 2
1728
1729        A relative extension of a relative extension.
1730            sage: k.<a> = NumberField([x^2 + 1, x^3 + x + 1])
1731            sage: R.<z> = k[]
1732            sage: L.<b> = NumberField(z^3 + 3 + a); L
1733            Number Field in b with defining polynomial z^3 + a0 + 3 over its base field
1734        """
1735        if not isinstance(poly, polynomial_element.Polynomial):
1736            try:
1737                poly = poly.polynomial(self)
1738            except (AttributeError, TypeError):
1739                raise TypeError, "polynomial (=%s) must be a polynomial."%repr(poly)
1740        if not names is None:
1741            name = names
1742        if isinstance(name, tuple):
1743            name = name[0]
1744        if name is None:
1745            raise TypeError, "the variable name must be specified."
1746        return NumberField_relative(self, poly, str(name), check=check)
1747
1748    def factor_integer(self, n):
1749        r"""
1750        Ideal factorization of the principal ideal of the ring
1751        of integers generated by $n$.
1752
1753        EXAMPLE:
1754        Here we show how to factor gaussian integers.
1755        First we form a number field defined by $x^2 + 1$:
1756
1757            sage: K.<I> = NumberField(x^2 + 1); K
1758            Number Field in I with defining polynomial x^2 + 1
1759
1760        Here are the factors:
1761
1762            sage: fi, fj = K.factor_integer(13); fi,fj
1763            ((Fractional ideal (-3*I - 2) of Number Field in I with defining polynomial x^2 + 1, 1), (Fractional ideal (3*I - 2) of Number Field in I with defining polynomial x^2 + 1, 1))
1764
1765        Now we extract the reduced form of the generators:
1766
1767            sage: zi = fi[0].gens_reduced()[0]; zi
1768            -3*I - 2
1769            sage: zj = fj[0].gens_reduced()[0]; zj
1770            3*I - 2
1771
1772        We recover the integer that was factor in $\Z[i]$
1773
1774            sage: zi*zj
1775            13
1776
1777        AUTHOR:
1778            -- Alex Clemesha (2006-05-20): examples
1779        """
1780        return self.ideal(n).factor()
1781
1782    def gen(self, n=0):
1783        """
1784        Return the generator for this number field.
1785
1786        INPUT:
1787            n -- must be 0 (the default), or an exception is raised.
1788
1789        EXAMPLES:
1790            sage: k.<theta> = NumberField(x^14 + 2); k
1791            Number Field in theta with defining polynomial x^14 + 2
1792            sage: k.gen()
1793            theta
1794            sage: k.gen(1)
1795            Traceback (most recent call last):
1796            ...
1797            IndexError: Only one generator.
1798        """
1799        if n != 0:
1800            raise IndexError, "Only one generator."
1801        try:
1802            return self.__gen
1803        except AttributeError:
1804            if self.__polynomial != None:
1805                X = self.__polynomial.parent().gen()
1806            else:
1807                X = PolynomialRing(rational_field.RationalField()).gen()
1808            self.__gen = self._element_class(self, X)
1809            return self.__gen
1810
1811    def is_field(self):
1812        """
1813        Return True since a number field is a field.
1814
1815        EXAMPLES:
1816            sage: NumberField(x^5 + x + 3, 'c').is_field()
1817            True
1818        """
1819        return True
1820
1821    def is_galois(self):
1822        r"""
1823        Return True if this relative number field is a Galois extension of $\QQ$.
1824
1825        EXAMPLES:
1826            sage: NumberField(cyclotomic_polynomial(5),'a').is_galois()
1827            True
1828            sage: NumberField(x^2 + 1, 'i').is_galois()
1829            True
1830            sage: NumberField(x^3 + 2, 'a').is_galois()
1831            False
1832        """
1833        return self.galois_group(pari_group=True).group().order() == self.degree()
1834
1835    def galois_group(self, pari_group = True, use_kash=False):
1836        r"""
1837        Return the Galois group of the Galois closure of this number
1838        field as an abstract group.
1839
1840        For more (important!) documentation, so the documentation
1841        for Galois groups of polynomials over $\QQ$, e.g., by
1842        typing \code{K.polynomial().galois_group?}, where $K$
1843        is a number field.
1844
1845        To obtain actual field automorphisms that can be applied to
1846        elements, use \code{End(K).list()} and
1847        \code{K.galois_closure()} together (see example below).
1848
1849        EXAMPLES:
1850            sage: k.<b> = NumberField(x^2 - 14)
1851            sage: k.galois_group ()
1852            Galois group PARI group [2, -1, 1, "S2"] of degree 2 of the number field Number Field in b with defining polynomial x^2 - 14
1853
1854            sage: NumberField(x^3-2, 'a').galois_group(pari_group=True)
1855            Galois group PARI group [6, -1, 2, "S3"] of degree 3 of the number field Number Field in a with defining polynomial x^3 - 2
1856
1857            sage: NumberField(x-1, 'a').galois_group(pari_group=False)    # optional database_gap package
1858            Galois group Transitive group number 1 of degree 1 of the number field Number Field in a with defining polynomial x - 1
1859            sage: NumberField(x^2+2, 'a').galois_group(pari_group=False)  # optional database_gap package
1860            Galois group Transitive group number 1 of degree 2 of the number field Number Field in a with defining polynomial x^2 + 2
1861            sage: NumberField(x^3-2, 'a').galois_group(pari_group=False)  # optional database_gap package
1862            Galois group Transitive group number 2 of degree 3 of the number field Number Field in a with defining polynomial x^3 - 2
1863
1864        EXPLICIT GALOIS GROUP:
1865        We compute the Galois group as an explicit group of
1866        automorphisms of the Galois closure of a field.
1867
1868            sage: K.<a> = NumberField(x^3 - 2)
1869            sage: L.<b> = K.galois_closure(); L
1870            Number Field in b1 with defining polynomial x^6 + 40*x^3 + 1372
1871            sage: G = End(L); G
1872            Automorphism group of Number Field in b1 with defining polynomial x^6 + 40*x^3 + 1372
1873            sage: G.list()
1874            [
1875            Ring endomorphism of Number Field in b1 with defining polynomial x^6 + 40*x^3 + 1372
1876              Defn: b1 |--> b1,
1877            ...
1878            Ring endomorphism of Number Field in b1 with defining polynomial x^6 + 40*x^3 + 1372
1879              Defn: b1 |--> -2/63*b1^4 - 31/63*b1
1880            ]
1881            sage: G[1](b)
1882            1/36*b1^4 + 1/18*b1
1883        """
1884        try:
1885            return self.__galois_group[pari_group, use_kash]
1886        except KeyError:
1887            pass
1888        except AttributeError:
1889            self.__galois_group = {}
1890
1891        G = self.polynomial().galois_group(pari_group = pari_group, use_kash = use_kash)
1892        H = GaloisGroup(G, self)
1893        self.__galois_group[pari_group, use_kash] = H
1894        return H
1895
1896
1897    def integral_basis(self):
1898        """
1899        Return a list of elements of this number field that are a basis
1900        for the full ring of integers.
1901
1902        EXAMPLES:
1903            sage: K.<a> = NumberField(x^5 + 10*x + 1)
1904            sage: K.integral_basis()
1905            [1, a, a^2, a^3, a^4]
1906
1907        Next we compute the ring of integers of a cubic field in which 2
1908        is an "essential discriminant divisor", so the ring of integers
1909        is not generated by a single element.
1910            sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
1911            sage: K.integral_basis()
1912            [1, a, 1/2*a^2 + 1/2*a]
1913        """
1914        try:
1915            return self.__integral_basis
1916        except AttributeError:
1917            f = self.pari_polynomial()
1918            B = f.nfbasis()
1919            R = self.polynomial().parent()
1920            self.__integral_basis = [self(R(g).list()) for g in B]
1921        return self.__integral_basis
1922
1923    def narrow_class_group(self, proof=None):
1924        r"""
1925        Return the narrow class group of this field.
1926
1927        INPUT:
1928            proof -- default: None (use the global proof setting, which defaults to True).
1929
1930        EXAMPLES:
1931            sage: NumberField(x^3+x+9, 'a').narrow_class_group()
1932            Multiplicative Abelian Group isomorphic to C2
1933        """
1934        proof = proof_flag(proof)
1935        try:
1936            return self.__narrow_class_group
1937        except AttributeError:
1938            k = self.pari_bnf(proof)
1939            s = str(k.bnfnarrow())
1940            s = s.replace(";",",")
1941            s = eval(s)
1942            self.__narrow_class_group = sage.groups.abelian_gps.abelian_group.AbelianGroup(s[1])
1943        return self.__narrow_class_group
1944
1945    def ngens(self):
1946        """
1947        Return the number of generators of this number field (always 1).
1948
1949        OUTPUT:
1950            the python integer 1.
1951
1952        EXAMPLES:
1953            sage: NumberField(x^2 + 17,'a').ngens()
1954            1
1955            sage: NumberField(x + 3,'a').ngens()
1956            1
1957            sage: k.<a> = NumberField(x + 3)
1958            sage: k.ngens()
1959            1
1960            sage: k.0
1961            -3
1962        """
1963        return 1
1964
1965    def order(self):
1966        """
1967        Return the order of this number field (always +infinity).
1968
1969        OUTPUT:
1970            always positive infinity
1971
1972        EXAMPLES:
1973            sage: NumberField(x^2 + 19,'a').order()
1974            +Infinity
1975        """
1976        return infinity.infinity
1977
1978    def polynomial_ntl(self):
1979        """
1980        Return defining polynomial of this number field
1981        as a pair, an ntl polynomial and a denominator.
1982
1983        This is used mainly to implement some internal arithmetic.
1984
1985        EXAMPLES:
1986            sage: NumberField(x^2 + (2/3)*x - 9/17,'a').polynomial_ntl()
1987            ([-27 34 51], 51)
1988        """
1989        try:
1990            return (self.__polynomial_ntl, self.__denominator_ntl)
1991        except AttributeError:
1992            self.__denominator_ntl = ntl.ZZ()
1993            den = self.polynomial().denominator()
1994            self.__denominator_ntl.set_from_sage_int(ZZ(den))
1995            self.__polynomial_ntl = ntl.ZZX((self.polynomial()*den).list())
1996        return (self.__polynomial_ntl, self.__denominator_ntl)
1997
1998    def polynomial(self):
1999        """
2000        Return the defining polynomial of this number field.
2001
2002        This is exactly the same as \code{self.defining_polynomal()}.
2003
2004        EXAMPLES:
2005            sage: NumberField(x^2 + (2/3)*x - 9/17,'a').polynomial()
2006            x^2 + 2/3*x - 9/17
2007        """
2008        return self.__polynomial
2009
2011        """
2012        Return the defining polynomial of this number field.
2013
2014        This is exactly the same as \code{self.polynomal()}.
2015
2016        EXAMPLES:
2017            sage: k5.<z> = CyclotomicField(5)
2018            sage: k5.defining_polynomial()
2019            x^4 + x^3 + x^2 + x + 1
2020            sage: y = polygen(QQ,'y')
2021            sage: k.<a> = NumberField(y^9 - 3*y + 5); k
2022            Number Field in a with defining polynomial y^9 - 3*y + 5
2023            sage: k.defining_polynomial()
2024            y^9 - 3*y + 5
2025        """
2026        return self.polynomial()
2027
2028    def polynomial_ring(self):
2029        """
2030        Return the polynomial ring that we view this number field as being
2031        a quotient of (by a principal ideal).
2032
2033        EXAMPLES:
2034        An example with an absolute field:
2035            sage: k.<a> = NumberField(x^2 + 3)
2036            sage: y = polygen(QQ, 'y')
2037            sage: k.<a> = NumberField(y^2 + 3)
2038            sage: k.polynomial_ring()
2039            Univariate Polynomial Ring in y over Rational Field
2040
2041        An example with a relative field:
2042            sage: y = polygen(QQ, 'y')
2043            sage: M.<a> = NumberField([y^3 + 97, y^2 + 1]); M
2044            Number Field in a0 with defining polynomial y^3 + 97 over its base field
2045            sage: M.polynomial_ring()
2046            Univariate Polynomial Ring in y over Number Field in a1 with defining polynomial y^2 + 1
2047        """
2048        return self.polynomial().parent()
2049
2050    def polynomial_quotient_ring(self):
2051        """
2052        Return the polynomial quotient ring isomorphic to this number field.
2053
2054        EXAMPLES:
2055            sage: K = NumberField(x^3 + 2*x - 5, 'alpha')
2056            sage: K.polynomial_quotient_ring()
2057            Univariate Quotient Polynomial Ring in alpha over Rational Field with modulus x^3 + 2*x - 5
2058        """
2059        return self.polynomial_ring().quotient(self.polynomial(), self.variable_name())
2060
2061    def regulator(self, proof=None):
2062        """
2063        Return the regulator of this number field.
2064
2065        Note that PARI computes the regulator to higher precision than
2066        the SAGE default.
2067
2068        INPUT:
2069            proof -- default: True, unless you set it otherwise.
2070
2071        EXAMPLES:
2072            sage: NumberField(x^2-2, 'a').regulator()
2073            0.88137358701954305
2074            sage: NumberField(x^4+x^3+x^2+x+1, 'a').regulator()
2075            0.96242365011920694
2076        """
2077        proof = proof_flag(proof)
2078        try:
2079            return self.__regulator
2080        except AttributeError:
2081            k = self.pari_bnf(proof)
2082            s = str(k.getattr('reg'))
2083            self.__regulator = eval(s)
2084        return self.__regulator
2085
2086    def residue_field(self, prime, name = None, check = False):
2087        """
2088        Return the residue field of this number field at a given prime, ie $O_K / p O_K$.
2089
2090        INPUT:
2091            prime -- a prime ideal of the maximal order in this number field.
2092            name -- the name of the variable in the residue field
2093            check -- whether or not to check the primality of prime.
2094        OUTPUT:
2095            The residue field at this prime.
2096
2097        EXAMPLES:
2098        sage: R.<x> = QQ[]
2099        sage: K.<a> = NumberField(x^4+3*x^2-17)
2100        sage: P = K.ideal(61).factor()[0][0]
2101        sage: K.residue_field(P)
2102        Residue field of Fractional ideal (-2*a^2 + 1) of Number Field in a with defining polynomial x^4 + 3*x^2 - 17
2103        """
2104        import sage.rings.residue_field
2105        return sage.rings.residue_field.ResidueField(prime)
2106
2107    def signature(self):
2108        """
2109        Return (r1, r2), where r1 and r2 are the number of real embeddings
2110        and pairs of complex embeddings of this field, respectively.
2111
2112        EXAMPLES:
2113            sage: NumberField(x^2+1, 'a').signature()
2114            (0, 1)
2115            sage: NumberField(x^3-2, 'a').signature()
2116            (1, 1)
2117            sage: CyclotomicField(7).signature()
2118            (0, 3)
2119        """
2120        r1, r2 = self.pari_nf().getattr('sign')
2121        return (ZZ(r1), ZZ(r2))
2122
2123    def trace_pairing(self, v):
2124        """
2125        Return the matrix of the trace pairing on the elements of the
2126        list $v$.
2127
2128        EXAMPLES:
2129            sage: K.<zeta3> = NumberField(x^2 + 3)
2130            sage: K.trace_pairing([1,zeta3])
2131            [ 2  0]
2132            [ 0 -6]
2133        """
2134        import sage.matrix.matrix_space
2135        A = sage.matrix.matrix_space.MatrixSpace(self.base_ring(), len(v))(0)
2136        for i in range(len(v)):
2137            for j in range(i,len(v)):
2138                t = (self(v[i]*v[j])).trace()
2139                A[i,j] = t
2140                A[j,i] = t
2141        return A
2142
2143    def uniformizer(self, P, others = "positive"):
2144        """
2145        Returns an element of self with valuation 1 at P.
2146
2147        INPUT:
2148        self -- a number field
2149        P -- a prime ideal of self
2150        others -- either "positive" (default), in which case the element will have
2151                  non-negative valuation at all other primes of self,
2152                  or "negative", in which case the element will have non-positive
2153                  valuation at all other primes of self.
2154        """
2155        if not is_NumberFieldIdeal(P):
2156            P = self.ideal(P)
2157        if not P.is_prime():
2158            raise ValueError, "P must be prime"
2159        if others == "negative":
2160            P = ~P
2161        elif others != "positive":
2162            raise ValueError, "others must be 'positive' or 'negative'"
2163        nf = self.pari_nf()
2164        a = self(nf.idealappr(P.pari_hnf()))
2165        if others == "negative":
2166            a = ~a
2167        return a
2168
2169    def units(self, proof=None):
2170        """
2171        Return generators for the unit group modulo torsion.
2172
2173        ALGORITHM: Uses PARI's bnfunit command.
2174
2175        INPUTS:
2176            proof -- default: True
2177
2178        EXAMPLES:
2179            sage: x = QQ['x'].0
2180            sage: A = x^4 - 10*x^3 + 20*5*x^2 - 15*5^2*x + 11*5^3
2181            sage: K = NumberField(A, 'a')
2182            sage: K.units()
2183            [8/275*a^3 - 12/55*a^2 + 15/11*a - 2]
2184        """
2185        proof = proof_flag(proof)
2186        try:
2187            return self.__units
2188        except AttributeError:
2189            B = self.pari_bnf(proof).bnfunit()
2190            R = self.polynomial().parent()
2191            self.__units = [self(R(g)) for g in B]
2192            return self.__units
2193
2194    def zeta(self, n=2, all=False):
2195        """
2196        Return an n-th root of unity in this field.  If all is True,
2197        return all of them.
2198
2199        INPUT:
2200            n -- positive integer
2201            all -- bool, default: False.  If True, return a list
2202                   of all n-th roots of 1)
2203
2204        If there are no n-th roots of unity in self (and all is
2205        False), this function raises an ArithmeticError exception.
2206
2207        EXAMPLES:
2208            sage: K.<z> = NumberField(x^2 + 3)
2209            sage: K.zeta(1)
2210            1
2211            sage: K.zeta(2)
2212            -1
2213            sage: K.zeta(2, all=True)
2214            [-1]
2215            sage: K.zeta(3)
2216            1/2*z - 1/2
2217            sage: K.zeta(3, all=True)
2218            [1/2*z - 1/2, -1/2*z - 1/2]
2219            sage: K.zeta(4)
2220            Traceback (most recent call last):
2221            ...
2222            ArithmeticError: There are no 4-th roots of unity self.
2223
2224            sage: r.<x> = QQ[]
2225            sage: K.<b> = NumberField(x^2+1)
2226            sage: K.zeta(4)
2227            b
2228            sage: K.zeta(4,all=True)
2229            [b, -b]
2230            sage: K.zeta(3)
2231            Traceback (most recent call last):
2232            ...
2233            ArithmeticError: There are no 3-rd roots of unity self.
2234            sage: K.zeta(3,all=True)
2235            []
2236        """
2237        n = ZZ(n)
2238        if n <= 0:
2239            raise ValueError, "n (=%s) must be positive"%n
2240        if n == 1:
2241            if all:
2242                return [self(1)]
2243            else:
2244                return self(1)
2245        elif n == 2:
2246            if all:
2247                return [self(-1)]
2248            else:
2249                return self(-1)
2250        else:
2251            field = self.absolute_field('a')
2252            from_field = field.structure()[0]
2253            f = field.polynomial_ring().cyclotomic_polynomial(n)
2254            F = field['x'](f)
2255            R = F.roots()
2256            if len(R) == 0:
2257                if all:
2258                    return []
2259                else:
2260                    if n == 1:
2261                        th = 'st'
2262                    elif n == 2:
2263                        th = 'nd'
2264                    elif n == 3:
2265                        th = 'rd'
2266                    else:
2267                        th = 'th'
2268                    raise ArithmeticError, "There are no %s-%s roots of unity self."%(n,th)
2269            if all:
2270                return [from_field(r[0]) for r in R]
2271            else:
2272                return from_field(R[0][0])
2273
2274    def zeta_coefficients(self, n):
2275        """
2276        Compute the first n coefficients of the Dedekind zeta function
2277        of this field as a Dirichlet series.
2278
2279        EXAMPLE:
2280            sage: x = QQ['x'].0
2281            sage: NumberField(x^2+1, 'a').zeta_coefficients(10)
2282            [1, 1, 0, 1, 2, 0, 0, 1, 1, 2]
2283        """
2284        return self.pari_nf().dirzetak(n)
2285
2286
2287class NumberField_absolute(NumberField_generic):
2288
2289    def __init__(self, polynomial, name, latex_name=None, check=True):
2290        NumberField_generic.__init__(self, polynomial, name, latex_name, check)
2291        self._element_class = number_field_element.NumberFieldElement_absolute
2292
2293    def base_field(self):
2294        return QQ
2295
2296    def is_absolute(self):
2297        """
2298        EXAMPLES:
2299            sage: K = CyclotomicField(5)
2300            sage: K.is_absolute()
2301            True
2302        """
2303        return True
2304
2305    def absolute_polynomial(self):
2306        r"""
2307        Return absolute polynomial that defines this absolute field.
2308        This is the same as \code{self.polynomial()}.
2309
2310        EXAMPLES:
2311            sage: K.<a> = NumberField(x^2 + 1)
2312            sage: K.absolute_polynomial ()
2313            x^2 + 1
2314        """
2315        return self.polynomial()
2316
2317    def __reduce__(self):
2318        """
2319        TESTS:
2320            sage: Z = var('Z')
2321            sage: K.<w> = NumberField(Z^3 + Z + 1)
2323            sage: print L
2324            Number Field in w with defining polynomial Z^3 + Z + 1
2325            sage: print L == K
2326            True
2327        """
2328        return NumberField_absolute_v1, (self.polynomial(), self.variable_name(), self.latex_variable_name())
2329
2330    def optimized_representation(self, names=None, both_maps=True):
2331        """
2332        Return a field isomorphic to self with a better defining
2333        polynomial if possible, along with field isomorphisms from the
2334        new field to self and from self to the new field.
2335
2336        EXAMPLES:
2337        We construct a compositum of 3 quadratic fields, then find an optimized
2338        representation and transform elements back and forth.
2339            sage: K = NumberField([x^2 + p for p in [5, 3, 2]],'a').absolute_field('b'); K
2340            Number Field in b with defining polynomial x^8 + 40*x^6 + 352*x^4 + 960*x^2 + 576
2341            sage: L, from_L, to_L = K.optimized_representation()
2342            sage: L    # your answer may different, since algorithm is random
2343            Number Field in a14 with defining polynomial x^8 + 4*x^6 + 7*x^4 + 36*x^2 + 81
2344            sage: to_L(K.0)   # random
2345            4/189*a14^7 - 1/63*a14^6 + 1/27*a14^5 + 2/9*a14^4 - 5/27*a14^3 + 8/9*a14^2 + 3/7*a14 + 3/7
2346            sage: from_L(L.0)   # random
2347            1/1152*a1^7 + 1/192*a1^6 + 23/576*a1^5 + 17/96*a1^4 + 37/72*a1^3 + 5/6*a1^2 + 55/24*a1 + 3/4
2348
2349        The transformation maps are mutually inverse isomorphisms.
2350            sage: from_L(to_L(K.0))
2351            b
2352            sage: to_L(from_L(L.0))     # random
2353            a14
2354        """
2355        return self.optimized_subfields(degree=self.degree(), name=names, both_maps=both_maps)[0]
2356
2357    def optimized_subfields(self, degree=0, name=None, both_maps=True):
2358        """
2359        Return optimized representations of many (but *not* necessarily
2360        all!)  subfields of self of degree 0, or of all possible
2361        degrees if degree is 0.
2362
2363        EXAMPLES:
2364            sage: K = NumberField([x^2 + p for p in [5, 3, 2]],'a').absolute_field('b'); K
2365            Number Field in b with defining polynomial x^8 + 40*x^6 + 352*x^4 + 960*x^2 + 576
2366            sage: L = K.optimized_subfields(name='b')
2367            sage: L[0][0]
2368            Number Field in b0 with defining polynomial x - 1
2369            sage: L[1][0]
2370            Number Field in b1 with defining polynomial x^2 - x + 1
2371            sage: [z[0] for z in L]          # random -- since algorithm is random
2372            [Number Field in b0 with defining polynomial x - 1,
2373             Number Field in b1 with defining polynomial x^2 - x + 1,
2374             Number Field in b2 with defining polynomial x^4 - 5*x^2 + 25,
2375             Number Field in b3 with defining polynomial x^4 - 2*x^2 + 4,
2376             Number Field in b4 with defining polynomial x^8 + 4*x^6 + 7*x^4 + 36*x^2 + 81]
2377
2378        We examine one of the optimized subfields in more detail:
2379             sage: M, from_M, to_M = L[2]
2380             sage: M                             # random
2381             Number Field in b2 with defining polynomial x^4 - 5*x^2 + 25
2382             sage: from_M     # may be slightly random
2383             Ring morphism:
2384               From: Number Field in b2 with defining polynomial x^4 - 5*x^2 + 25
2385               To:   Number Field in a1 with defining polynomial x^8 + 40*x^6 + 352*x^4 + 960*x^2 + 576
2386               Defn: b2 |--> -5/1152*a1^7 + 1/96*a1^6 - 97/576*a1^5 + 17/48*a1^4 - 95/72*a1^3 + 17/12*a1^2 - 53/24*a1 - 1
2387
2388        The to_M map is None, since there is no map from K to M:
2389             sage: to_M
2390
2391        We apply the from_M map to the generator of M, which gives a rather
2392        large element of $K$:
2393             sage: from_M(M.0)          # random
2394             -5/1152*a1^7 + 1/96*a1^6 - 97/576*a1^5 + 17/48*a1^4 - 95/72*a1^3 + 17/12*a1^2 - 53/24*a1 - 1
2395
2396        Nevertheless, that large-ish element lies in a degree 4 subfield:
2397             sage: from_M(M.0).minpoly()   # random
2398             x^4 - 5*x^2 + 25
2399        """
2400        return self._subfields_helper(degree=degree,name=name,
2401                                      both_maps=both_maps,optimize=True)
2402
2403    def change_name(self, names):
2404        r"""
2405        Return number field isomorphic to self but with the given
2406        generator name.
2407
2408        INPUT:
2409            names -- should be exactly one variable name.
2410
2411        Also, \code{K.structure()} returns from_K and to_K, where
2412        from_K is an isomorphism from K to self and to_K is an
2413        isomorphism from self to K.
2414
2415        EXAMPLES:
2416            sage: K.<z> = NumberField(x^2 + 3); K
2417            Number Field in z with defining polynomial x^2 + 3
2418            sage: L.<ww> = K.change_name()
2419            sage: L
2420            Number Field in ww with defining polynomial x^2 + 3
2421            sage: L.structure()[0]
2422            Number field isomorphism from Number Field in ww with defining polynomial x^2 + 3 to Number Field in z with defining polynomial x^2 + 3 given by variable name change
2423            sage: L.structure()[0](ww + 5/3)
2424            z + 5/3
2425        """
2426        return self.absolute_field(names)
2427
2428    def subfields(self, degree=0, name=None):
2429        """
2430        EXAMPLES:
2431            sage: K.<a> = NumberField( [x^3 - 2, x^2 + x + 1] );
2432            sage: K = K.absolute_field('b')
2433            sage: S = K.subfields()
2434            sage: len(S)
2435            6
2436            sage: [k[0].polynomial() for k in S]
2437            [x - 3,
2438             x^2 - 3*x + 9,
2439             x^3 - 3*x^2 + 3*x + 1,
2440             x^3 - 3*x^2 + 3*x + 1,
2441             x^3 - 3*x^2 + 3*x - 17,
2442             x^6 - 3*x^5 + 6*x^4 - 11*x^3 + 12*x^2 + 3*x + 1]
2443        """
2444        return self._subfields_helper(degree=degree, name=name,
2445                                      both_maps=True, optimize=False)
2446
2447    def _subfields_helper(self, degree=0, name=None, both_maps=True, optimize=False):
2448        if name is None:
2449            name = self.variable_names()
2450        name = sage.structure.parent_gens.normalize_names(1, name)[0]
2451        try:
2452            return self.__subfields[name, degree, both_maps, optimize]
2453        except AttributeError:
2454            self.__subfields = {}
2455        except KeyError:
2456            pass
2457        f = pari(self.polynomial())
2458        if optimize:
2459            v = f.polred(2)
2460            elts = v[0]; polys = v[1]
2461        else:
2462            v = f.nfsubfields(degree)
2463            elts = [x[1] for x in v]; polys = [x[0] for x in v]
2464
2465        R = self.polynomial_ring()
2466
2467        ans = []
2468        for i in range(len(elts)):
2469            f = R(polys[i])
2470            if not (degree == 0 or f.degree() == degree):
2471                continue
2472            a = self(R(elts[i]))
2473            K = NumberField(f, names=name + str(i))
2474
2475            from_K = K.hom([a])    # check=False here ??   would be safe unless there are bugs.
2476
2477            if both_maps and K.degree() == self.degree():
2478                g = K['x'](self.polynomial())
2479                v = g.roots()
2480                a = from_K(K.gen())
2481                for i in range(len(v)):
2482                    r = g.roots()[i][0]
2483                    to_K = self.hom([r])    # check=False here ??
2484                    if to_K(a) == K.gen():
2485                        break
2486            else:
2487                to_K = None
2488            ans.append((K, from_K, to_K))
2489        ans = Sequence(ans, immutable=True, cr=True)
2490        self.__subfields[name, degree, both_maps, optimize] = ans
2491        return ans
2492
2493
2494    def maximal_order(self):
2495        """
2496        Return the maximal order, i.e., the ring of integers, associated
2497        to this number field.
2498
2499        EXAMPLES:
2500
2501        In this example, the maximal order cannot be generated
2502        by a single element.
2503            sage: k.<a> = NumberField(x^3 + x^2 - 2*x+8)
2504            sage: o = k.maximal_order()
2505            sage: o
2506            Order with module basis 1, 1/2*a^2 + 1/2*a, a^2 in Number Field in a with defining polynomial x^3 + x^2 - 2*x + 8
2507        """
2508        try:
2509            return self.__maximal_order
2510        except AttributeError:
2511            B = self.integral_basis()
2512            import sage.rings.number_field.order as order
2513            O = order.absolute_order_from_module_generators(B,
2514                     check_integral=False, check_rank=False,
2515                     check_is_ring=False, is_maximal=True)
2516            self.__maxima_order = O
2517            return O
2518
2519    def order(self, *gens, **kwds):
2520        r"""
2521        Return the order with given ring generators in the maximal
2522        order of this number field.
2523
2524        INPUT:
2525            gens -- list of elements of self; if no generators are
2526                    given, just returns the cardinality of this number
2527                    field (oo) for consistency.
2528            check_is_integral -- bool (default: True), whether to check
2529                  that each generator is integral.
2530            check_rank -- bool (default: True), whether to check that
2531                  the ring generated by gens is of full rank.
2532            allow_subfield -- bool (default: False), if True and the generators
2533                  do not generate an order, i.e., they generate a subring
2534                  of smaller rank, instead of raising an error, return
2535                  an order in a smaller number field.
2536
2537        EXAMPLES:
2538            sage: k.<i> = NumberField(x^2 + 1)
2539            sage: k.order(2*i)
2540            Order with module basis 1, 2*i in Number Field in i with defining polynomial x^2 + 1
2541            sage: k.order(10*i)
2542            Order with module basis 1, 10*i in Number Field in i with defining polynomial x^2 + 1
2543            sage: k.order(3)
2544            Traceback (most recent call last):
2545            ...
2546            ValueError: the rank of the span of gens is wrong
2547            sage: k.order(i/2)
2548            Traceback (most recent call last):
2549            ...
2550            ValueError: each generator must be integral
2551
2552        Alternatively, an order can be constructed by adjoining
2553        elements to $\ZZ$:
2554
2555        """
2556        if len(gens) == 0:
2557            return NumberField_generic.order(self)
2558        if len(gens) == 1 and isinstance(gens[0], (list, tuple)):
2559            gens = gens[0]
2560        gens = [self(x) for x in gens]
2561        import sage.rings.number_field.order as order
2562        return order.absolute_order_from_ring_generators(gens, **kwds)
2563
2564    def vector_space(self):
2565        """
2566        Return a vector space V and isomorphisms self --> V and V --> self.
2567
2568        OUTPUT:
2569            V -- a vector space over the rational numbers
2570            from_V -- an isomorphism from V to self
2571            to_V -- an isomorphism from self to V
2572
2573        EXAMPLES:
2574            sage: k.<a> = NumberField(x^3 + 2)
2575            sage: V, from_V, to_V  = k.vector_space()
2576            sage: from_V(V([1,2,3]))
2577            3*a^2 + 2*a + 1
2578            sage: to_V(1 + 2*a + 3*a^2)
2579            (1, 2, 3)
2580            sage: V
2581            Vector space of dimension 3 over Rational Field
2582            sage: to_V
2583            Isomorphism from Number Field in a with defining polynomial x^3 + 2 to Vector space of dimension 3 over Rational Field
2584            sage: from_V(to_V(2/3*a - 5/8))
2585            2/3*a - 5/8
2586            sage: to_V(from_V(V([0,-1/7,0])))
2587            (0, -1/7, 0)
2588        """
2589        try:
2590            return self.__vector_space
2591        except AttributeError:
2592            V = QQ**self.degree()
2593            from_V = maps.MapVectorSpaceToNumberField(V, self)
2594            to_V   = maps.MapNumberFieldToVectorSpace(self, V)
2595            self.__vector_space = (V, from_V, to_V)
2596            return self.__vector_space
2597
2598    def absolute_vector_space(self):
2599        r"""
2600        Return vector space over $\QQ$ corresponding to this number
2601        field, along with maps from that space to this number field
2602        and in the other direction.
2603
2604        For an absolute extension this is identical to
2605        \code{self.vector_space()}.
2606
2607        EXAMPLES:
2608            sage: K.<a> = NumberField(x^3 - 5)
2609            sage: K.absolute_vector_space()
2610            (Vector space of dimension 3 over Rational Field,
2611             Isomorphism from Vector space of dimension 3 over Rational Field to Number Field in a with defining polynomial x^3 - 5,
2612             Isomorphism from Number Field in a with defining polynomial x^3 - 5 to Vector space of dimension 3 over Rational Field)
2613        """
2614        return self.vector_space()
2615
2616    def galois_closure(self, names=None):
2617        """
2618        Return number field $K$ that is the Galois closure of self,
2619        i.e., is generated by all roots of the defining polynomial of
2620        self
2621
2622
2623        INPUT:
2624            names -- variable name for Galois closure
2625
2626        EXAMPLES:
2627            sage: K.<a> = NumberField(x^4 - 2)
2628            sage: L = K.galois_closure(); L
2629            Number Field in a2 with defining polynomial x^8 + 28*x^4 + 2500
2630            sage: K.galois_group().order()
2631            8
2632
2633            sage: phi = K.embeddings(L)[0]
2634            sage: phi(K.0)
2635            1/120*a2^5 + 19/60*a2
2636            sage: phi(K.0).minpoly()
2637            x^4 - 2
2638        """
2639        try:
2640            return self.__galois_closure
2641        except AttributeError:
2642            pass
2643        G = self.galois_group()
2644        K = self
2645        while K.degree() < G.order():
2646            K = K.composite_fields(self, names=names)[-1]
2647        self.__galois_closure = K
2648        return self.__galois_closure
2649
2650    def embeddings(self, K):
2651        """
2652        Compute all field embeddings of self into the field K (which
2653        need not even be a number field, e.g., it could be the complex
2654        numbers). This will return an identical result when given K as
2655        input again.
2656
2657        If possible, the most natural embedding of K into self
2658        is put first in the list.
2659
2660        INPUT:
2661            K -- a number field
2662
2663        EXAMPLES:
2664            sage: K.<a> = NumberField(x^3 - 2)
2665            sage: L = K.galois_closure(); L
2666            Number Field in a1 with defining polynomial x^6 + 40*x^3 + 1372
2667            sage: K.embeddings(L)[0]
2668            Ring morphism:
2669              From: Number Field in a with defining polynomial x^3 - 2
2670              To:   Number Field in a1 with defining polynomial x^6 + 40*x^3 + 1372
2671              Defn: a |--> 1/84*a1^4 + 13/42*a1
2672            sage: K.embeddings(L)  is K.embeddings(L)
2673            True
2674
2675        We embed a quadratic field into a cyclotomic field:
2677            sage: K = CyclotomicField(7)
2678            sage: L.embeddings(K)
2679            [Ring morphism: ...
2680              Defn: a |--> 2*zeta7^4 + 2*zeta7^2 + 2*zeta7 + 1,
2681             Ring morphism: ...
2682              Defn: a |--> -2*zeta7^4 - 2*zeta7^2 - 2*zeta7 - 1]
2683
2684        We embed a cubic field in the complex numbers:
2685            sage: K.<a> = NumberField(x^3 - 2)
2686            sage: K.embeddings(CC)
2687            [Ring morphism:
2688              From: Number Field in a with defining polynomial x^3 - 2
2689              To:   Complex Field with 53 bits of precision
2690              Defn: a |--> -0.629960524947437 - 1.09112363597172*I,
2691             Ring morphism:
2692              From: Number Field in a with defining polynomial x^3 - 2
2693              To:   Complex Field with 53 bits of precision
2694              Defn: a |--> -0.629960524947437 + 1.09112363597172*I,
2695             Ring morphism:
2696              From: Number Field in a with defining polynomial x^3 - 2
2697              To:   Complex Field with 53 bits of precision
2698              Defn: a |--> 1.25992104989487]
2699        """
2700        try:
2701            return self.__embeddings[K]
2702        except AttributeError:
2703            self.__embeddings = {}
2704        except KeyError:
2705            pass
2706        f = K['x'](self.defining_polynomial())
2707        r = f.roots(); r.sort()
2708        v = [self.hom([e[0]], check=False) for e in r]
2709        # If there is an embedding that preserves variable names
2710        # then it is most natural, so we put it first.
2711        put_natural_embedding_first(v)
2712
2713        self.__embeddings[K] = Sequence(v, cr=True, immutable=True, check=False, universe=self.Hom(K))
2714        return v
2715
2716    def relativize(self, alpha, names):
2717        r"""
2718        Given an element alpha in self, return a relative number field
2719        $K$ isomorphic to self that is relative over the absolute field
2720        $\QQ(\alpha)$, along with isomorphisms from $K$ to self and
2721        from self to K.
2722
2723        INPUT:
2724            alpha -- an element of self.
2725            names -- 2-tuple of names of generator for output
2726                     field K and the subfield QQ(alpha)
2727                     names[0] generators K and names[1] QQ(alpha).
2728
2729        OUTPUT:
2730            K   -- relative number field, map from K to self,
2731                   map from self to K.
2732
2733        Also, \code{K.structure()} returns from_K and to_K, where
2734        from_K is an isomorphism from K to self and to_K is an isomorphism
2735        from self to K.
2736
2737        EXAMPLES:
2738            sage: K.<a> = NumberField(x^10 - 2)
2739            sage: L.<c,d> = K.relativize(a^4 + a^2 + 2); L
2740            Number Field in c with defining polynomial x^2 + -1/5*d^4 + 8/5*d^3 - 23/5*d^2 + 7*d - 18/5 over its base field
2741            sage: c.absolute_minpoly()
2742            x^10 - 2
2743            sage: d.absolute_minpoly()
2744            x^5 - 10*x^4 + 40*x^3 - 90*x^2 + 110*x - 58
2745            sage: (a^4 + a^2 + 2).minpoly()
2746            x^5 - 10*x^4 + 40*x^3 - 90*x^2 + 110*x - 58
2747            sage: from_L, to_L = L.structure()
2748            sage: to_L(a)
2749            c
2750            sage: to_L(a^4 + a^2 + 2)
2751            d
2752            sage: from_L(to_L(a^4 + a^2 + 2))
2753            a^4 + a^2 + 2
2754        """
2755        # step 1: construct the abstract field generated by alpha.
2756        # step 2: make a relative extension of it.
2757        # step 3: construct isomorphisms
2758
2759        names = sage.structure.parent_gens.normalize_names(2, names)
2760
2761        # make sure alpha is in self
2762        alpha = self(alpha)
2763
2764        f = alpha.minpoly()
2765        L = NumberField(f, names[1])
2766
2767        g = self.defining_polynomial()
2768        h = L['x'](g)
2769        F = h.factor()
2770
2771        for f, e in F:
2772            if L.degree() * f.degree() == self.degree():
2773                M = L.extension(f, names[0])
2774                beta = M(L.gen())
2775                try:
2776                    to_M = self.hom([M.gen(0)], M, check=True)  # be paranoid
2777                except TypeError:
2778                    continue
2779                if to_M(alpha) == beta:
2780                    # Bingo.
2781                    # We have now constructed a relative
2782                    # number field M, and an isomorphism
2783                    # self --> M that sends alpha to
2784                    # the generator of the intermediate field.
2785                    from_M = M.hom([self.gen()], self, check=True)
2786                    M._set_structure(from_M, to_M)  # don't have to
2787                                                    # worry about caching since relative number fields aren't cached.
2788                    return M
2789
2790        assert False, "bug in relativize"
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801class NumberField_relative(NumberField_generic):
2802    """
2803    EXAMPLES:
2804        sage: K.<a> = NumberField(x^3 - 2)
2805        sage: t = K['x'].gen()
2806        sage: L.<b> = K.extension(t^2+t+a); L
2807        Number Field in b with defining polynomial x^2 + x + a over its base field
2808    """
2809    def __init__(self, base, polynomial, name,
2810                 latex_name=None, names=None, check=True):
2811        r"""
2812        INPUT:
2813            base -- the base field
2814            polynomial -- must be defined in the ring \code{K['x']}, where
2815                          K is the base field.
2816            name -- variable name
2817            latex_name -- latex variable name
2818            names --
2819            check -- whether to check irreducibility of polynomial.
2820
2821        EXAMPLES:
2822            sage: K.<x> = CyclotomicField(5)[]
2823            sage: W.<a> = NumberField(x^2 + 1)
2824            sage: W
2825            Number Field in a with defining polynomial x^2 + 1 over its base field
2826            sage: type(W)
2827            <class 'sage.rings.number_field.number_field.NumberField_relative'>
2828
2829        Test that check=False really skips the test:
2830            sage: W.<a> = NumberField(K.cyclotomic_polynomial(5), check=False)
2831            sage: W
2832            Number Field in a with defining polynomial x^4 + x^3 + x^2 + x + 1 over its base field
2833
2834        A relative extension of a relative extension:
2835            sage: x = var('x')
2836            sage: k.<a> = NumberField([x^2 + 2, x^2 + 1])
2837            sage: l.<b> = k.extension(x^2 + 3)
2838            sage: l
2839            Number Field in b with defining polynomial x^2 + 3 over its base field
2840            sage: l.base_field()
2841            Number Field in a0 with defining polynomial x^2 + 2 over its base field
2842            sage: l.base_field().base_field()
2843            Number Field in a1 with defining polynomial x^2 + 1
2844        """
2845        if not names is None: name = names
2846        if not is_NumberField(base):
2847            raise TypeError, "base (=%s) must be a number field"%base
2848        if not isinstance(polynomial, polynomial_element.Polynomial):
2849            try:
2850                polynomial = polynomial.polynomial(base)
2851            except (AttributeError, TypeError), msg:
2852                raise TypeError, "polynomial (=%s) must be a polynomial."%repr(polynomial)
2853        if name == base.variable_name():
2854            raise ValueError, "Base field and extension cannot have the same name"
2855        if polynomial.parent().base_ring() != base:
2856            polynomial = polynomial.change_ring(base)
2857            #raise ValueError, "The polynomial must be defined over the base field"
2858
2859        # Generate the nf and bnf corresponding to the base field
2860        # defined as polynomials in y, e.g. for rnfisfree
2861
2862        # Convert the polynomial defining the base field into a
2863        # polynomial in y to satisfy PARI's ordering requirements.
2864
2865        if base.is_relative():
2866            abs_base = base.absolute_field('a')
2867            from_abs_base, to_abs_base = abs_base.structure()
2868        else:
2869            abs_base = base
2870            from_abs_base = maps.IdentityMap(base)
2871            to_abs_base = maps.IdentityMap(base)
2872
2873        self.__absolute_base_field = abs_base, from_abs_base, to_abs_base
2874        Qx = abs_base.polynomial().parent()
2875        Qy = (abs_base.polynomial().base_ring())['y']
2876        phi = Qx.hom([Qy.gen()])
2877        base_polynomial_y = phi(abs_base.polynomial())
2878
2879        self.__base_nf = pari(base_polynomial_y).nfinit()
2880        self.__base_bnf = pari(base_polynomial_y).bnfinit()
2881
2882        # Use similar methods to convert the polynomial defining the
2883        # relative extension into a polynomial in x, with y denoting
2884        # the generator of the base field.
2885        # NOTE: This should be rewritten if there is a way to extend
2886        #       homomorphisms K -> K' to homomorphisms K[x] -> K'[x].
2887        base_field_y = NumberField(abs_base.polynomial(), 'y')
2888        Kx = base_field_y['x']
2889        i = abs_base.hom([base_field_y.gen()]) # inclusion K -> K' with a -> y
2890        rel_coeffs = [i(to_abs_base(c)) for c in polynomial.coeffs()]
2891        polynomial_y = Kx(rel_coeffs)
2892
2893        if check:
2894            if not polynomial_y.is_irreducible():
2895                raise ValueError, "defining polynomial (%s) must be irreducible"%polynomial
2896
2897
2898        self.__pari_relative_polynomial = pari(str(polynomial_y))
2899        self.__rnf = self.__base_nf.rnfinit(self.__pari_relative_polynomial)
2900
2901        self.__base_field = base
2902        self.__relative_polynomial = polynomial
2903        self.__pari_bnf_certified = False
2904        self._element_class = number_field_element.NumberFieldElement_relative
2905
2906        self.__gens = [None]
2907
2908        v = [None]
2909        K = base
2910        names = [name]
2911        while K != QQ:
2912            names.append(K.variable_name())
2913            v.append(K.gen())
2914            K = K.base_field()
2915
2916        self._assign_names(tuple(names), normalize=False)
2917
2918        NumberField_generic.__init__(self, self.absolute_polynomial(), name=None,
2919                                     latex_name=latex_name, check=False)
2920
2921        v[0] = self._gen_relative()
2922        v = [self(x) for x in v]
2923        self.__gens = tuple(v)
2924
2925
2926    def change_name(self, names):
2927        r"""
2928        Return relative number field isomorphic to self but with the
2929        given generator names.
2930
2931        INPUT:
2932            names -- number of names should be at most the number of
2933                     generators of self, i.e., the number of steps in
2934                     the tower of relative fields.
2935
2936        Also, \code{K.structure()} returns from_K and to_K, where
2937        from_K is an isomorphism from K to self and to_K is an
2938        isomorphism from self to K.
2939
2940        EXAMPLES:
2941            sage: K.<a,b> = NumberField([x^4 + 3, x^2 + 2]); K
2942            Number Field in a with defining polynomial x^4 + 3 over its base field
2943            sage: L.<c,d> = K.change_name()
2944            sage: L
2945            Number Field in c with defining polynomial x^4 + 3 over its base field
2946            sage: L.base_field()
2947            Number Field in d with defining polynomial x^2 + 2
2948
2949        An example with a 3-level tower:
2950            sage: K.<a,b,c> = NumberField([x^2 + 17, x^2 + x + 1, x^3 - 2]); K
2951            Number Field in a with defining polynomial x^2 + 17 over its base field
2952            sage: L.<m,n,r> = K.change_name()
2953            sage: L
2954            Number Field in m with defining polynomial x^2 + 17 over its base field
2955            sage: L.base_field()
2956            Number Field in n with defining polynomial x^2 + x + 1 over its base field
2957            sage: L.base_field().base_field()
2958            Number Field in r with defining polynomial x^3 - 2
2959
2960        """
2961        if len(names) == 0:
2962            names = self.variable_names()
2963        elif isinstance(names, str):
2964            names = names.split(',')
2965        K = self.base_field().change_name(tuple(names[1:]))
2966        L = K.extension(self.defining_polynomial(), names=names[0])
2967        return L
2968
2969    def is_absolute(self):
2970        """
2971        EXAMPLES:
2972            sage: K.<a,b> = NumberField([x^4 + 3, x^2 + 2]); K
2973            Number Field in a with defining polynomial x^4 + 3 over its base field
2974            sage: K.is_absolute()
2975            False
2976            sage: K.is_relative()
2977            True
2978        """
2979        return False
2980
2981    def gens(self):
2982        return self.__gens
2983
2984    def ngens(self):
2985        return len(self.__gens)
2986
2987    def gen(self, n=0):
2988        if n < 0 or n >= len(self.__gens):
2989            raise IndexError, "invalid generator %s"%n
2990        return self.__gens[n]
2991
2992    def galois_closure(self, names=None):
2993        """
2994        Return the absolute number field $K$ that is the Galois
2995        closure of self.
2996
2997        EXAMPLES:
2998        """
2999        K = self.absolute_field('a').galois_closure(names=names)
3000        if K.degree() == self.absolute_degree():
3001            return self
3002        return K
3003
3004    def absolute_degree(self):
3005        """
3006        EXAMPLES:
3007            sage: K.<a> = NumberField([x^2 + 3, x^2 + 2])
3008            sage: K.absolute_degree()
3009            4
3010            sage: K.degree()
3011            2
3012        """
3013        return self.absolute_polynomial().degree()
3014
3015    def __reduce__(self):
3016        """
3017        TESTS:
3018            sage: Z = var('Z')
3019            sage: K.<w> = NumberField(Z^3 + Z + 1)
3020            sage: L.<z> = K.extension(Z^3 + 2)
3022            sage: print L
3023            Number Field in w with defining polynomial Z^3 + Z + 1
3024            sage: print L == K
3025            True
3026        """
3027        return NumberField_relative_v1, (self.__base_field, self.polynomial(), self.variable_name(),
3028                                          self.latex_variable_name())
3029
3030    def _repr_(self):
3031        """
3032        Return string representation of this relative number field.
3033
3034        The base field is not part of the string representation.  To
3035        find out what the base field is use \code{self.base_field()}.
3036
3037        EXAMPLES:
3038            sage: k.<a, b> = NumberField([x^5 + 2, x^7 + 3])
3039            sage: k
3040            Number Field in a with defining polynomial x^5 + 2 over its base field
3041            sage: k.base_field()
3042            Number Field in b with defining polynomial x^7 + 3
3043        """
3044
3045        return "Number Field in %s with defining polynomial %s over its base field"%(self.variable_name(), self.polynomial())
3046
3047        #return "Extension by %s of the Number Field in %s with defining polynomial %s"%(
3048        #self.polynomial(), self.base_field().variable_name(),
3049        #    self.base_field().polynomial())
3050
3051    def _Hom_(self, codomain, cat=None):
3052        """
3053        Return homset of homomorphisms from this relative number field
3054        to the codomain.
3055
3056        The cat option is currently ignored.   The result is not cached.
3057
3058        EXAMPLES:
3059        This function is implicitly caled by the Hom method or function.
3060            sage: K.<a,b> = NumberField([x^3 - 2, x^2+1])
3061            sage: K.Hom(K)
3062            Automorphism group of Number Field in a with defining polynomial x^3 + -2 over its base field
3063            sage: type(K.Hom(K))
3064            <class 'sage.rings.number_field.morphism.RelativeNumberFieldHomset'>
3065        """
3066        import morphism
3067        return morphism.RelativeNumberFieldHomset(self, codomain)
3068
3069    def _latex_(self):
3070        r"""
3071        Return a \LaTeX representation of the extension.
3072
3073        EXAMPLE:
3074            sage: x = QQ['x'].0
3075            sage: K.<a> = NumberField(x^3 - 2)
3076            sage: t = K['x'].gen()
3077            sage: K.extension(t^2+t+a, 'b')._latex_()
3078            '( \\mathbf{Q}[a]/(a^{3} - 2) )[b]/(b^{2} + b + a)'
3079        """
3080        return "( %s )[%s]/(%s)"%(latex(self.base_field()), self.latex_variable_name(),
3081                              self.polynomial()._latex_(self.latex_variable_name()))
3082
3083    def __call__(self, x):
3084        """
3085        Coerce x into this relative number field.
3086
3087        EXAMPLES:
3088        We construct the composite of three quadratic fields, then
3089        coerce from the quartic subfield of the relative extension:
3090
3091            sage: k.<a,b,c> = NumberField([x^2 + 5, x^2 + 3, x^2 + 1])
3092            sage: m = k.base_field(); m
3093            Number Field in b with defining polynomial x^2 + 3 over its base field
3094            sage: k(m.0)
3095            b
3096            sage: k(2/3)
3097            2/3
3098            sage: k(m.0^4)
3099            9
3100        """
3101        if isinstance(x, number_field_element.NumberFieldElement):
3102            P = x.parent()
3103            from sage.rings.number_field.order import is_NumberFieldOrder
3104            if P is self:
3105                return x
3106            elif is_NumberFieldOrder(P) and P.number_field() is self:
3107                return self._element_class(self, x.polynomial())
3108            elif P == self:
3109                return self._element_class(self, x.polynomial())
3110            return self.__base_inclusion(self.base_field()(x))
3111
3112        if not isinstance(x, (int, long, rational.Rational,
3113                              integer.Integer, pari_gen,
3114                              polynomial_element.Polynomial,
3115                              list)):
3116            return self.base_field()(x)
3117
3118        return self._element_class(self, x)
3119
3120    def _coerce_impl(self, x):
3121        """
3122        Canonical implicit coercion of x into self.
3123
3124        Elements of this field canonically coerce in, as does anything
3125        that coerces into the base field of this field.
3126
3127        EXAMPLES:
3128            sage: k.<a> = NumberField([x^5 + 2, x^7 + 3])
3129            sage: b = k(k.base_field().gen())
3130            sage: b = k._coerce_impl(k.base_field().gen())
3131            sage: b^7
3132            -3
3133            sage: k._coerce_impl(2/3)
3134            2/3
3135            sage: c = a + b  # this works
3136        """
3137        if isinstance(x, number_field_element.NumberFieldElement):
3138            from sage.rings.number_field.order import is_NumberFieldOrder
3139            if x.parent() is self:
3140                return x
3141            elif is_NumberFieldOrder(x.parent()) and x.parent().number_field() is self:
3142                return self._element_class(self, x.polynomial())
3143            else:
3144                return self.__base_inclusion(x)
3145
3146        return self.__base_inclusion(self.base_field()._coerce_impl(x))
3147
3148    def __base_inclusion(self, element):
3149        """
3150        Given an element of the base field, give its inclusion into
3151        this extension in terms of the generator of this field.
3152
3153        This is called by the canonical coercion map on elements from
3154        the base field.
3155
3156        EXAMPLES:
3157            sage: k.<a> = NumberField([x^2 + 3, x^2 + 1])
3158            sage: m = k.base_field(); m
3159            Number Field in a1 with defining polynomial x^2 + 1
3160            sage: k._coerce_(m.0 + 2/3)
3161            a1 + 2/3
3162            sage: s = k._coerce_(m.0); s
3163            a1
3164            sage: s^2
3165            -1
3166
3167        This implicitly tests this coercion map:
3168            sage: K.<a> = NumberField([x^2 + p for p in [5,3,2]])
3169            sage: K._coerce_(K.base_field().0)
3170            a1
3171            sage: K._coerce_(K.base_field().0)^2
3172            -3
3173        """
3174        abs_base, from_abs_base, to_abs_base = self.absolute_base_field()
3175        # Write element in terms of the absolute base field
3176        element = self.base_field()._coerce_impl(element)
3177        element = to_abs_base(element)
3178        # Obtain the polynomial in y corresponding to element in terms of the absolute base
3179        f = element.polynomial('y')
3180        # Find an expression in terms of the absolute generator for self of element.
3181        expr_x = self.pari_rnf().rnfeltreltoabs(f._pari_())
3182        # Convert to a SAGE polynomial, then to one in gen(), and return it
3183        R = self.polynomial_ring()
3184        return self(R(expr_x))
3185
3186    def _ideal_class_(self):
3187        """
3188        Return the Python class used to represent ideals of a relative
3189        number field.
3190
3191        EXAMPLES:
3192            sage: k.<a> = NumberField([x^5 + 2, x^7 + 3])
3193            sage: k._ideal_class_ ()
3194            <class 'sage.rings.number_field.number_field_ideal_rel.NumberFieldIdeal_rel'>
3195        """
3196        return sage.rings.number_field.number_field_ideal_rel.NumberFieldIdeal_rel
3197
3198    def _pari_base_bnf(self, proof=None):
3199        """
3200        Return the PARI bnf (big number field) representation of the
3201        base field.
3202
3203        INPUT:
3204            proof -- bool (default: True) if True, certify correctness
3205                     of calculations (not assuming GRH).
3206
3207        EXAMPLES:
3208            sage: k.<a> = NumberField([x^3 + 2, x^2 + 2])
3209            sage: k._pari_base_bnf()
3210            [[;], matrix(0,9), [;], ... 0]
3211        """
3212        proof = proof_flag(proof)
3213        # No need to certify the same field twice, so we'll just check
3214        # that the base field is certified.
3215        if proof:
3216            self.base_field().pari_bnf_certify()
3217        return self.__base_bnf
3218
3219    def _pari_base_nf(self):
3220        """
3221        Return the PARI number field representation of the base field.
3222
3223        EXAMPLES:
3224            sage: y = polygen(QQ,'y')
3225            sage: k.<a> = NumberField([y^3 + 2, y^2 + 2])
3226            sage: k._pari_base_nf()
3227            [y^2 + 2, [0, 1], -8, 1, ..., [1, 0, 0, -2; 0, 1, 1, 0]]
3228        """
3229        return self.__base_nf
3230
3231    def is_galois(self):
3232        r"""
3233        Return True if this relative number field is Galois over $\QQ$.
3234
3235        EXAMPLES:
3236            sage: k.<a> =NumberField([x^3 - 2, x^2 + x + 1])
3237            sage: k.is_galois()
3238            True
3239            sage: k.<a> =NumberField([x^3 - 2, x^2 + 1])
3240            sage: k.is_galois()
3241            False
3242        """
3243        return self.absolute_field('a').is_galois()
3244
3245    def vector_space(self):
3246        """
3247        Return vector space over the base field of self and isomorphisms
3248        from the vector space to self and in the other direction.
3249
3250        EXAMPLES:
3251            sage: K.<a,b,c> = NumberField([x^2 + 2, x^3 + 2, x^3 + 3]); K
3252            Number Field in a with defining polynomial x^2 + 2 over its base field
3253            sage: V, from_V, to_V = K.vector_space()
3254            sage: from_V(V.0)
3255            1
3256            sage: to_V(K.0)
3257            (0, 1)
3258            sage: from_V(to_V(K.0))
3259            a
3260            sage: to_V(from_V(V.0))
3261            (1, 0)
3262            sage: to_V(from_V(V.1))
3263            (0, 1)
3264
3265        The underlying vector space and maps is cached:
3266            sage: W, from_V, to_V = K.vector_space()
3267            sage: V is W
3268            True
3269        """
3270        try:
3271            return self.__vector_space
3272        except AttributeError:
3273            pass
3274        V = self.base_field()**self.degree()
3275        from_V = maps.MapRelativeVectorSpaceToRelativeNumberField(V, self)
3276        to_V   = maps.MapRelativeNumberFieldToRelativeVectorSpace(self, V)
3277        self.__vector_space = (V, from_V, to_V)
3278        return self.__vector_space
3279
3280    def absolute_vector_space(self):
3281        """
3282        EXAMPLES:
3283            sage: K.<a,b> = NumberField([x^3 + 3, x^3 + 2]); K
3284            Number Field in a with defining polynomial x^3 + 3 over its base field
3285            sage: V,from_V,to_V = K.absolute_vector_space(); V
3286            Vector space of dimension 9 over Rational Field
3287            sage: from_V
3288            Isomorphism from Vector space of dimension 9 over Rational Field to Number Field in a with defining polynomial x^3 + 3 over its base field
3289            sage: to_V
3290            Isomorphism from Number Field in a with defining polynomial x^3 + 3 over its base field to Vector space of dimension 9 over Rational Field
3291            sage: c = (a+1)^5; c
3292            7*a^2 + (-10)*a + -29
3293            sage: to_V(c)
3294            (-29, -712/9, 19712/45, 0, -14/9, 364/45, 0, -4/9, 119/45)
3295            sage: from_V(to_V(c))
3296            7*a^2 + (-10)*a + -29
3297            sage: from_V(3*to_V(b))
3298            3*b
3299        """
3300        try:
3301            return self.__absolute_vector_space
3302        except AttributeError:
3303            pass
3304        K = self.absolute_field('a')
3305        from_K, to_K = K.structure()
3306        V, from_V, to_V = K.vector_space()
3307        fr = maps.MapVectorSpaceToRelativeNumberField(V, self, from_V, from_K)
3308        to   = maps.MapRelativeNumberFieldToVectorSpace(self, V, to_K, to_V)
3309        ans = (V, fr, to)
3310        self.__absolute_vector_space = ans
3311        return ans
3312
3313    def absolute_base_field(self):
3314        """
3315        Return the base field of this relative extension, but viewed
3316        as an absolute field over QQ.
3317
3318        EXAMPLES:
3319            sage: K.<a,b,c> = NumberField([x^2 + 2, x^3 + 3, x^3 + 2])
3320            sage: K
3321            Number Field in a with defining polynomial x^2 + 2 over its base field
3322            sage: K.base_field()
3323            Number Field in b with defining polynomial x^3 + 3 over its base field
3324            sage: K.absolute_base_field()[0]
3325            Number Field in a with defining polynomial x^9 + 3*x^6 + 165*x^3 + 1
3326            sage: K.base_field().absolute_field('z')
3327            Number Field in z with defining polynomial x^9 + 3*x^6 + 165*x^3 + 1
3328        """
3329        return self.__absolute_base_field
3330
3331    def _gen_relative(self):
3332        """
3333        Return root of defining polynomial, which is a generator of
3334        the relative number field over the base.
3335
3336        EXAMPLES:
3337            sage: k.<a> = NumberField(x^2+1); k
3338            Number Field in a with defining polynomial x^2 + 1
3339            sage: y = polygen(k)
3340            sage: m.<b> = k.extension(y^2+3); m
3341            Number Field in b with defining polynomial x^2 + 3 over its base field
3342            sage: c = m.gen(); c
3343            b
3344            sage: c^2 + 3
3345            0
3346        """
3347        try:
3348            return self.__gen_relative
3349        except AttributeError:
3350            rnf = self.pari_rnf()
3351            f = (pari('x') - rnf[10][2]*rnf[10][1]).lift()
3352            self.__gen_relative = self._element_class(self, f)
3353            return self.__gen_relative
3354
3355    def pari_polynomial(self):
3356        """
3357        PARI polynomial corresponding to the polynomial over the
3358        rationals that defines this field as an absolute number field.
3359
3360        EXAMPLES:
3361            sage: k.<a, c> = NumberField([x^2 + 3, x^2 + 1])
3362            sage: k.pari_polynomial()
3363            x^4 + 8*x^2 + 4
3364            sage: k.defining_polynomial ()
3365            x^2 + 3
3366        """
3367        try:
3368            return self.__pari_polynomial
3369        except AttributeError:
3370            poly = self.absolute_polynomial()
3371            with localvars(poly.parent(), 'x'):
3372                self.__pari_polynomial = poly._pari_()
3373            return self.__pari_polynomial
3374
3375    def pari_rnf(self):
3376        """
3377        Return the PARI relative number field object associated
3378        to this relative extension.
3379
3380        EXAMPLES:
3381            sage: k.<a> = NumberField([x^4 + 3, x^2 + 2])
3382            sage: k.pari_rnf()
3383            [x^4 + 3, [], [[108, 0; 0, 108], [3, 0]~], ... 0]
3384        """
3385        return self.__rnf
3386
3387    def pari_relative_polynomial(self):
3388        """
3389        Return the PARI relative polynomial associated to this
3390        number field.  This is always a polynomial in x and y.
3391
3392        EXAMPLES:
3393            sage: k.<i> = NumberField(x^2 + 1)
3394            sage: m.<z> = k.extension(k['w']([i,0,1]))
3395            sage: m
3396            Number Field in z with defining polynomial w^2 + i over its base field
3397            sage: m.pari_relative_polynomial ()
3398            x^2 + y
3399        """
3400        return self.__pari_relative_polynomial
3401
3402    def absolute_generator(self):
3403        """
3404        Return the chosen generator over QQ for this relative number field.
3405
3406        EXAMPLES:
3407            sage: y = polygen(QQ,'y')
3408            sage: k.<a> = NumberField([y^2 + 2, y^4 + 3])
3409            sage: g = k.absolute_generator(); g
3410            a0 + -a1
3411            sage: g.minpoly()
3412            x^2 + 2*a1*x + a1^2 + 2
3413            sage: g.absolute_minpoly()
3414            x^8 + 8*x^6 + 30*x^4 - 40*x^2 + 49
3415        """
3416        try:
3417            return self.__abs_gen
3418        except AttributeError:
3419            self.__abs_gen = self._element_class(self, QQ['x'].gen())
3420            return self.__abs_gen
3421
3422
3423    def absolute_field(self, names):
3424        r"""
3425        Return an absolute number field K that is isomorphic to this
3426        field along with a field-theoretic bijection from self to K
3427        and from K to self.
3428
3429        INPUT:
3430            names -- string; name of generator of the absolute field
3431
3432        OUTPUT:
3433            K -- an absolute number field
3434
3435        Also, \code{K.structure()} returns from_K and to_K, where
3436        from_K is an isomorphism from K to self and to_K is an isomorphism
3437        from self to K.
3438
3439        EXAMPLES:
3440            sage: K.<a,b> = NumberField([x^4 + 3, x^2 + 2]); K
3441            Number Field in a with defining polynomial x^4 + 3 over its base field
3442            sage: L.<xyz> = K.absolute_field(); L
3443            Number Field in xyz with defining polynomial x^8 + 8*x^6 + 30*x^4 - 40*x^2 + 49
3444            sage: L.<c> = K.absolute_field(); L
3445            Number Field in c with defining polynomial x^8 + 8*x^6 + 30*x^4 - 40*x^2 + 49
3446
3447            sage: from_L, to_L = L.structure()
3448            sage: from_L
3449            Isomorphism from Number Field in c with defining polynomial x^8 + 8*x^6 + 30*x^4 - 40*x^2 + 49 to Number Field in a with defining polynomial x^4 + 3 over its base field
3450            sage: from_L(c)
3451            a + -b
3452            sage: to_L
3453            Isomorphism from Number Field in a with defining polynomial x^4 + 3 over its base field to Number Field in c with defining polynomial x^8 + 8*x^6 + 30*x^4 - 40*x^2 + 49
3454            sage: to_L(a)
3455            -5/182*c^7 - 87/364*c^5 - 185/182*c^3 + 323/364*c
3456            sage: to_L(b)
3457            -5/182*c^7 - 87/364*c^5 - 185/182*c^3 - 41/364*c
3458            sage: to_L(a)^4
3459            -3
3460            sage: to_L(b)^2
3461            -2
3462        """
3463        try:
3464            return self.__absolute_field[names]
3465        except KeyError:
3466            pass
3467        except AttributeError:
3468            self.__absolute_field = {}
3469        K = NumberField(self.absolute_polynomial(), names, cache=False)
3470        from_K = maps.MapAbsoluteToRelativeNumberField(K, self)
3471        to_K = maps.MapRelativeToAbsoluteNumberField(self, K)
3472        K._set_structure(from_K, to_K)
3473        self.__absolute_field[names] = K
3474        return K
3475
3476    def absolute_polynomial(self):
3477        r"""
3478        Return the polynomial over $\QQ$ that defines this field as an
3479        extension of the rational numbers.
3480
3481        EXAMPLES:
3482            sage: k.<a, b> = NumberField([x^2 + 1, x^3 + x + 1]); k
3483            Number Field in a with defining polynomial x^2 + 1 over its base field
3484            sage: k.absolute_polynomial()
3485            x^6 + 5*x^4 - 2*x^3 + 4*x^2 + 4*x + 1
3486        """
3487        try:
3488            return self.__absolute_polynomial
3489        except AttributeError:
3490            pbn = self._pari_base_nf()
3491            prp = self.pari_relative_polynomial()
3492            pari_poly = pbn.rnfequation(prp)
3493            R = QQ['x']
3494            self.__absolute_polynomial = R(pari_poly)
3495            return self.__absolute_polynomial
3496
3497    def base_field(self):
3498        """
3499        Return the base field of this relative number field.
3500
3501        EXAMPLES:
3502            sage: k.<a> = NumberField([x^3 + x + 1])
3503            sage: R.<z> = k[]
3504            sage: L.<b> = NumberField(z^3 + a)
3505            sage: L.base_field()
3506            Number Field in a with defining polynomial x^3 + x + 1
3507            sage: L.base_field() is k
3508            True
3509
3510        This is very useful because the print representation of
3511        a relative field doesn't describe the base field.
3512            sage: L
3513            Number Field in b with defining polynomial z^3 + a over its base field
3514        """
3515        return self.__base_field
3516
3517    def base_ring(self):
3518        """
3519        This is exactly the same as base_field.
3520
3521        EXAMPLES:
3522            sage: k.<a> = NumberField([x^2 + 1, x^3 + x + 1])
3523            sage: k.base_ring()
3524            Number Field in a1 with defining polynomial x^3 + x + 1
3525            sage: k.base_field()
3526            Number Field in a1 with defining polynomial x^3 + x + 1
3527        """
3528        return self.base_field()
3529
3530    def embeddings(self, K):
3531        """
3532        Compute all field embeddings of the relative number field self
3533        into the field K (which need not even be a number field, e.g.,
3534        it could be the complex numbers). This will return an
3535        identical result when given K as input again.
3536
3537        If possible, the most natural embedding of K into self
3538        is put first in the list.
3539
3540        INPUT:
3541            K -- a number field
3542
3543        EXAMPLES:
3544            sage: K.<a,b> = NumberField([x^3 - 2, x^2+1])
3545            sage: f = K.embeddings(CC); f
3546            [Relative number field morphism:
3547              From: Number Field in a with defining polynomial x^3 + -2 over its base field
3548              To:   Complex Field with 53 bits of precision
3549              Defn: a |--> -0.629960524947442 - 1.09112363597172*I
3550                    b |--> -0.00000000000000532907051820075 + 1.00000000000000*I,
3551              ...
3552              To:   Complex Field with 53 bits of precision
3553              Defn: a |--> 1.25992104989487 + 0.000000000000000222044604925031*I
3554                    b |--> -1.00000000000000*I]
3555            sage: f[0](a)^3
3556            2.00000000000001 - 0.0000000000000279776202205539*I
3557            sage: f[0](b)^2
3558            -1.00000000000001 - 0.0000000000000106581410364015*I
3559            sage: f[0](a+b)
3560            -0.629960524947448 - 0.0911236359717185*I
3561        """
3562        try:
3563            return self.__embeddings[K]
3564        except AttributeError:
3565            self.__embeddings = {}
3566        except KeyError:
3567            pass
3568        L = self.absolute_field('a')
3569        E = L.embeddings(K)
3570        v = [self.hom(f, K) for f in E]
3571
3572        # If there is an embedding that preserves variable names
3573        # then it is most natural, so we put it first.
3574        put_natural_embedding_first(v)
3575
3576        self.__embeddings[K] = Sequence(v, cr=True, immutable=True, check=False, universe=self.Hom(K))
3577        return v
3578
3579    def relative_discriminant(self, proof=None):
3580        r"""
3581        Return the relative discriminant of this extension $L/K$ as
3582        an ideal of $K$.  If you want the (rational) discriminant of
3583        $L/Q$, use e.g. \code{L.discriminant()}.
3584
3585        TODO: Note that this uses PARI's \code{rnfdisc} function, which
3586        according to the documentation takes an \code{nf} parameter in
3587        GP but a \code{bnf} parameter in the C library.  If the C
3588        library actually accepts an \code{nf}, then this function
3589        should be fixed and the \code{proof} parameter removed.
3590
3591        INPUT:
3592            proof -- (default: False)
3593
3594        EXAMPLE:
3595            sage: K.<i> = NumberField(x^2 + 1)
3596            sage: t = K['t'].gen()
3597            sage: L.<b> = K.extension(t^4 - i)
3598            sage: L.relative_discriminant()
3599            Fractional ideal (256) of Number Field in i with defining polynomial x^2 + 1
3600            sage: factor(L.discriminant())
3601            2^24
3602            sage: factor( L.relative_discriminant().norm() )
3603            2^16
3604        """
3605        proof = proof_flag(proof)
3606
3607        bnf = self._pari_base_bnf(proof)
3608        K = self.base_field()
3609        R = K.polynomial().parent()
3610        D, d = bnf.rnfdisc(self.pari_relative_polynomial())
3611        return K.ideal([ K(R(x)) for x in convert_from_zk_basis(K, D) ])
3612
3613    def order(self, *gens, **kwds):
3614        """
3615        Return the order with given ring generators in the maximal
3616        order of this number field.
3617
3618        INPUT:
3619            gens -- list of elements of self; if no generators are
3620                    given, just returns the cardinality of this number
3621                    field (oo) for consistency.
3622            base -- base of the order, which must be an order in the base
3623                    field of the relative number field self. If not specified,
3624                    then the base defaults to the ring of integers of the
3625                    base field.
3626            check_is_integral -- bool (default: True), whether to check
3627                  that each generator is integral.
3628            check_rank -- bool (default: True), whether to check that
3629                  the ring generated by gens is of full rank.
3630            allow_subfield -- bool (default: False), if True and the generators
3631                  do not generate an order, i.e., they generate a subring
3632                  of smaller rank, instead of raising an error, return
3633                  an order in a smaller number field.
3634
3635        The base, check_is_integral, and check_rank inputs must be given as
3636        explicit keyword arguments.
3637
3638        EXAMPLES:
3639
3640        """
3641        import sage.rings.number_field.order as order
3642        if len(gens) == 0:
3643            return NumberField_generic.order(self)
3644        if len(gens) == 1 and isinstance(gens[0], (list, tuple)):
3645            gens = gens[0]
3646        gens = [self(x) for x in gens]
3647        if kwds.has_key('base'):
3648            base = kwds['base']
3649            del kwds['base']
3650            if not order.is_NumberFieldOrder(base):
3651                raise TypeError, "base must be a number field order"
3652            if base.number_field() != self.base_field():
3653                raise ValueError, "base must be an order in the base field"
3654        else:
3655            base = self.base_field().maximal_order()
3656        return order.relative_order_from_ring_generators(gens, base, **kwds)
3657
3658
3659    def galois_group(self, pari_group = True, use_kash=False):
3660        r"""
3661        Return the Galois group of the Galois closure of this number
3662        field as an abstract group.  Note that even though this is an
3663        extension $L/K$, the group will be computed as if it were $L/\QQ$.
3664
3665        For more (important!) documentation, so the documentation
3666        for Galois groups of polynomials over $\QQ$, e.g., by
3667        typing \code{K.polynomial().galois_group?}, where $K$
3668        is a number field.
3669
3670        EXAMPLE:
3671            sage: x = QQ['x'].0
3672            sage: K.<a> = NumberField(x^2 + 1)
3673            sage: R.<t> = PolynomialRing(K)
3674            sage: L = K.extension(t^5-t+a, 'b')
3675            sage: L.galois_group()
3676            Galois group PARI group [240, -1, 22, "S(5)[x]2"] of degree 10 of the number field Number Field in b with defining polynomial t^5 + (-1)*t + a over its base field
3677        """
3678        try:
3679            return self.__galois_group[pari_group, use_kash]
3680        except KeyError:
3681            pass
3682        except AttributeError:
3683            self.__galois_group = {}
3684
3685        G = self.absolute_polynomial().galois_group(pari_group = pari_group,
3686                                                    use_kash = use_kash)
3687        H = GaloisGroup(G, self)
3688        self.__galois_group[pari_group, use_kash] = H
3689        return H
3690
3691
3692    def is_free(self, proof=None):
3693        r"""
3694        Determine whether or not $L/K$ is free (i.e. if $\mathcal{O}_L$ is
3695        a free $\mathcal{O}_K$-module).
3696
3697        INPUT:
3698            proof -- default: True
3699
3700        EXAMPLES:
3701            sage: x = QQ['x'].0
3702            sage: K.<a> = NumberField(x^2+6)
3703            sage: L.<b> = K.extension(K['x'].gen()^2 + 3)    ## extend by x^2+3
3704            sage: L.is_free()
3705            False
3706        """
3707        proof = proof_flag(proof)
3708        base_bnf = self._pari_base_bnf(proof)
3709        if base_bnf.rnfisfree(self.pari_relative_polynomial()) == 1:
3710            return True
3711        return False
3712
3713    def lift_to_base(self, element):
3714        """
3715        Lift an element of this extension into the base field if possible,
3716        or raise a ValueError if it is not possible.
3717
3718        EXAMPLES:
3719            sage: x = QQ['x'].0
3720            sage: K = NumberField(x^3 - 2, 'a')
3721            sage: R = K['x']
3722            sage: L = K.extension(R.gen()^2 - K.gen(), 'b')
3723            sage: b = L.gen()
3724            sage: L.lift_to_base(b^4)
3725            a^2
3726            sage: L.lift_to_base(b)
3727            Traceback (most recent call last):
3728            ...
3729            ValueError: The element b is not in the base field
3730        """
3731        poly_xy = self.pari_rnf().rnfeltabstorel( self(element)._pari_() )
3732        str_poly = str(poly_xy)
3733        if str_poly.find('x') >= 0:
3734            raise ValueError, "The element %s is not in the base field"%element
3735        # We convert to a string to avoid some serious nastiness with
3736        # PARI polynomials secretely thinkining they are in more variables
3737        # than they are.
3738        f = QQ['y'](str_poly)
3739        return self.base_field()(f.list())
3740
3741    def polynomial(self):
3742        """
3743        Return the defining polynomial of this number field.
3744
3745        EXAMPLES:
3746            sage: y = polygen(QQ,'y')
3747            sage: k.<a> = NumberField([y^2 + y + 1, x^3 + x + 1])
3748            sage: k.polynomial()
3749            y^2 + y + 1
3750
3751        This is the same as defining_polynomial:
3752            sage: k.defining_polynomial()
3753            y^2 + y + 1
3754
3755        Use absolute polynomial for a polynomial that defines the
3756        absolute extension.
3757            sage: k.absolute_polynomial()
3758            x^6 + 3*x^5 + 8*x^4 + 9*x^3 + 7*x^2 + 6*x + 3
3759        """
3760        return self.__relative_polynomial
3761
3762    def relativize(self, alpha, names):
3763        r"""
3764        Given an element alpha in self, return a relative number field
3765        $K$ isomorphic to self that is relative over the absolute field
3766        $\QQ(\alpha)$, along with isomorphisms from $K$ to self and
3767        from self to K.
3768
3769        INPUT:
3770            alpha -- an element of self.
3771            names -- name of generator for output field K.
3772
3773        OUTPUT:
3774            K, from_K, to_K -- relative number field, map from K to self,
3775                               map from self to K.
3776
3777        EXAMPLES:
3778            sage: K.<a,b> = NumberField([x^4 + 3, x^2 + 2]); K
3779            Number Field in a with defining polynomial x^4 + 3 over its base field
3780            sage: L.<z,w> = K.relativize(a^2)
3781            sage: z^2
3782            z^2
3783            sage: w^2
3784            -3
3785            sage: L
3786            Number Field in z with defining polynomial x^4 + (-2*w + 4)*x^2 + 4*w + 1 over its base field
3787            sage: L.base_field()
3788            Number Field in w with defining polynomial x^2 + 3
3789        """
3790        K = self.absolute_field('a')
3791        from_K, to_K = K.structure()
3792        beta = to_K(alpha)
3793        S = K.relativize(beta, names)
3794        # Now S is the appropriate field,
3795        # but the structure maps attached to S
3796        # are isomorphisms with the absolute
3797        # field.  We have to compose them
3798        # with from_K and to_K to get
3799        # the appropriate maps.
3800        from_S, to_S = S.structure()
3801
3802        # Map from S to self:
3803        #   x |--> from_K(from_S(x))
3804        # Map from self to S:
3805        #   x |--> to_K(from_K(x))
3806        new_to_S = self.Hom(S)(to_S)
3807        a = from_S.abs_hom()
3808        W = a.domain()
3809        phi = W.hom([from_K(a(W.gen()))])
3810        new_from_S = S.Hom(self)(phi)
3811        S._set_structure(new_from_S, new_to_S, unsafe_force_change=True)
3812        return S
3813
3814class NumberField_cyclotomic(NumberField_absolute):
3815    """
3816    Create a cyclotomic extension of the rational field.
3817
3818    The command CyclotomicField(n) creates the n-th cyclotomic
3819    field, got by adjoing an n-th root of unity to the rational
3820    field.
3821
3822    EXAMPLES:
3823        sage: CyclotomicField(3)
3824        Cyclotomic Field of order 3 and degree 2
3825        sage: CyclotomicField(18)
3826        Cyclotomic Field of order 18 and degree 6
3827        sage: z = CyclotomicField(6).gen(); z
3828        zeta6
3829        sage: z^3
3830        -1
3831        sage: (1+z)^3
3832        6*zeta6 - 3
3833
3834        sage: K = CyclotomicField(197)
3836        True
3838        True
3839
3840        sage: cf12 = CyclotomicField( 12 )
3841        sage: z12 = cf12.0
3842        sage: cf6 = CyclotomicField( 6 )
3843        sage: z6 = cf6.0
3844        sage: FF = Frac( cf12['x'] )
3845        sage: x = FF.0
3846        sage: print z6*x^3/(z6 + x)
3847        zeta12^2*x^3/(x + zeta12^2)
3848    """
3849    def __init__(self, n, names):
3850        """
3851        A cyclomotic field, i.e., a field obtained by adjoining an
3852        n-th root of unity to the rational numbers.
3853
3854        EXAMPLES:
3855            sage: k = CyclotomicField(3)
3856            sage: type(k)
3857            <class 'sage.rings.number_field.number_field.NumberField_cyclotomic'>
3858        """
3859        f = QQ['x'].cyclotomic_polynomial(n)
3860        if names[0].startswith('zeta'):
3861            latex_name = "\\zeta_{%s}"%n
3862        else:
3863            latex_name = None
3864        NumberField_absolute.__init__(self, f,
3865                                     name= names,
3866                                     latex_name=latex_name,
3867                                     check=False)
3868#        self._element_class = NumberFieldElement_cyclotomic
3869        n = integer.Integer(n)
3870        zeta = self.gen()
3871        zeta._set_multiplicative_order(n)
3872        self.__zeta_order = n
3873
3874    def __reduce__(self):
3875        """
3876        TESTS:
3877            sage: K.<zeta7> = CyclotomicField(7)
3879            sage: print L
3880            Cyclotomic Field of order 7 and degree 6
3881            sage: print L == K
3882            True
3883        """
3884        return NumberField_cyclotomic_v1, (self.__zeta_order, self.variable_name())
3885
3886    def _repr_(self):
3887        r"""
3888        Return string representation of this cyclotomic field.
3889
3890        The order'' of the cyclotomic field $\QQ(\zeta_n)$ in the
3891        string output refers to the order of the $\zeta_n$, i.e., it
3892        is the integer $n$.  The degree is the degree of the field as
3893        an extension of $\QQ$.
3894
3895        EXAMPLES:
3896            sage: CyclotomicField(4)._repr_()
3897            'Cyclotomic Field of order 4 and degree 2'
3898            sage: CyclotomicField(400)._repr_()
3899            'Cyclotomic Field of order 400 and degree 160'
3900        """
3901        return "Cyclotomic Field of order %s and degree %s"%(
3902                self.zeta_order(), self.degree())
3903
3904    def _latex_(self):
3905        """
3906        Return the latex representation of this cyclotomic field.
3907
3908        EXAMPLES:
3909            sage: Z = CyclotomicField(4)
3910            sage: Z.gen()
3911            zeta4
3912            sage: latex(Z)
3913            \mathbf{Q}(\zeta_{4})
3914
3915        Latex printing respects the generator name.
3916            sage: k.<a> = CyclotomicField(4)
3917            sage: latex(k)
3918            \mathbf{Q}[a]/(a^{2} + 1)
3919            sage: k
3920            Cyclotomic Field of order 4 and degree 2
3921            sage: k.gen()
3922            a
3923        """
3924        v = self.latex_variable_name()
3925        if v.startswith('\\zeta_'):
3926            return "%s(%s)"%(latex(QQ), v)
3927        else:
3928            return NumberField_generic._latex_(self)
3929
3930    def __call__(self, x):
3931        """
3932        Create an element of this cyclotomic field from $x$.
3933
3934        EXAMPLES:
3935        The following example illustrates coercion from the cyclotomic
3936        field Q(zeta_42) to the cyclotomic field Q(zeta_6), in a case
3937        where such coercion is defined:
3938
3939            sage: k42 = CyclotomicField(42)
3940            sage: k6 = CyclotomicField(6)
3941            sage: a = k42.gen(0)
3942            sage: b = a^7
3943            sage: b
3944            zeta42^7
3945            sage: k6(b)
3946            zeta6
3947            sage: b^2
3948            zeta42^7 - 1
3949            sage: k6(b^2)
3950            zeta6 - 1
3951
3952        Coercion of GAP cyclotomic elements is also supported.
3953        """
3954        if isinstance(x, number_field_element.NumberFieldElement):
3955            if isinstance(x.parent(), NumberField_cyclotomic):
3956                return self._coerce_from_other_cyclotomic_field(x)
3957            else:
3958                return self._coerce_from_other_number_field(x)
3959        elif sage.interfaces.gap.is_GapElement(x):
3960            return self._coerce_from_gap(x)
3961        elif isinstance(x,str):
3962            return self._coerce_from_str(x)
3963        else:
3964            return self._coerce_non_number_field_element_in(x)
3965
3966    # TODO:
3967    # The following is very nice and much more flexible / powerful.
3968    # However, it is simply not *consistent*, since it totally
3969    # breaks the doctests in eisenstein_submodule.py.
3970    # FIX THIS.
3971
3972##     def _will_be_better_coerce_from_other_cyclotomic_field(self, x, only_canonical=False):
3973##         """
3974##         Coerce an element x of a cyclotomic field into self, if at all possible.
3975
3976##         INPUT:
3977##             x -- number field element
3978
3979##             only_canonical -- bool (default: False); Attempt to work,
3980##                    even in some cases when x is not in a subfield of
3981##                    the cyclotomics (as long as x is a root of unity).
3982
3983##         EXAMPLES:
3984##             sage: k5 = CyclotomicField(5)
3985##             sage: k3 = CyclotomicField(3)
3986##             sage: k15 = CyclotomicField(15)
3987##             sage: k15._coerce_from_other_cyclotomic_field(k3.gen())
3988##             zeta15^5
3989##             sage: k15._coerce_from_other_cyclotomic_field(k3.gen()^2 + 17/3)
3990##             -zeta15^5 + 14/3
3991##             sage: k3._coerce_from_other_cyclotomic_field(k15.gen()^5)
3992##             zeta3
3993##             sage: k3._coerce_from_other_cyclotomic_field(-2/3 * k15.gen()^5 + 2/3)
3994##             -2/3*zeta3 + 2/3
3995##         """
3996
3997##         K = x.parent()
3998
3999##         if K is self:
4000##             return x
4001##         elif K == self:
4002##             return self._element_class(self, x.polynomial())
4003##         n = K.zeta_order()
4004##         m = self.zeta_order()
4005##         print n, m, x
4006
4007
4008##         self_gen = self.gen()
4009
4010##         if m % n == 0:   # easy case
4011##             # pass this off to a method in the element class
4012##             # it can be done very quickly and easily by the pyrex<->NTL interface there
4013##             return x._lift_cyclotomic_element(self)
4014
4015##         # Whatever happens below, it has to be consistent with
4016##         #  zeta_r |---> (zeta_s)^m
4017
4018##         if m % 2 and not n%2:
4019##             m *= 2
4020##             self_gen = -self_gen
4021
4022##         if only_canonical and m % n:
4023##             raise TypeError, "no canonical coercion"
4024
4025##         if not is_CyclotomicField(K):
4026##             raise TypeError, "x must be in a cyclotomic field"
4027
4028##         v = x.list()
4029
4030##         # Find the smallest power r >= 1 of the generator g of K that is in self,
4031##         # i.e., find the smallest r such that g^r has order dividing m.
4032
4033##         d = sage.rings.arith.gcd(m,n)
4034##         r = n // d
4035
4036##         # Since we use the power basis for cyclomotic fields, if every
4037##         # v[i] with i not divisible by r is 0, then we're good.
4038
4039##         # If h generates self and has order m, then the element g^r
4040##         # maps to the power of self of order gcd(m,n)., i.e., h^(m/gcd(m,n))
4041##         #
4042##         z = self_gen**(m // d)
4043##         w = self(1)
4044
4045##         a = self(0)
4046##         for i in range(len(v)):
4047##             if i%r:
4048##                 if v[i]:
4049##                     raise TypeError, "element does not belong to cyclotomic field"
4050##             else:
4051##                 a += w*v[i]
4052##                 w *= z
4053##         return a
4054
4055    def _coerce_from_other_cyclotomic_field(self, x, only_canonical=False):
4056        """
4057        Coerce an element x of a cyclotomic field into self, if at all possible.
4058
4059        INPUT:
4060            x -- number field element
4061            only_canonical -- bool (default: False); Attempt to work, even in some
4062                   cases when x is not in a subfield of the cyclotomics (as long as x is
4063                   a root of unity).
4064        """
4065        K = x.parent()
4066        if K is self:
4067            return x
4068        elif K == self:
4069            return self._element_class(self, x.polynomial())
4070        n = K.zeta_order()
4071        m = self.zeta_order()
4072        if m % n == 0:   # easy case
4073            # pass this off to a method in the element class
4074            # it can be done very quickly and easily by the pyrex<->NTL interface there
4075            return x._lift_cyclotomic_element(self)
4076        else:
4077            if only_canonical:
4078                raise TypeError
4079            n = x.multiplicative_order()
4080            if m % n == 0:
4081                # Harder case.  E.g., x = (zeta_42)^7 and
4082                # self.__zeta = zeta_6, so it is possible to
4083                # coerce x in, but not zeta_42 in.
4084                # Algorithm:
4085                #    1. Compute self.__zeta as an element
4086                #       of K = parent of x.  Call this y.
4087                #    2. Write x as a power r of y.
4088                #       TODO: we do step two STUPIDLY.
4089                #    3. Return self.__zeta to the power r.
4090                y = K(self.zeta())
4091                z = y
4092                for r in xrange(y.multiplicative_order()):
4093                    if z == x:
4094                        return self.zeta()**(r+1)
4095                    z *= y
4096            raise TypeError, "Cannot coerce %s into %s"%(x,self)
4097        return self._element_class(self, g)
4098
4099
4100    def _coerce_from_gap(self, x):
4101        """
4102        Attempt to coerce a GAP number field element into this cyclotomic field.
4103
4104        EXAMPLES:
4105            sage: k5.<z> = CyclotomicField(5)
4106            sage: gap('E(5)^7 + 3')
4107            -3*E(5)-2*E(5)^2-3*E(5)^3-3*E(5)^4
4108            sage: w = gap('E(5)^7 + 3')
4109            sage: z^7 + 3
4110            z^2 + 3
4111            sage: k5(w)
4112            z^2 + 3
4113        """
4114        s = str(x)
4115        i = s.find('E(')
4116        if i == -1:
4117            return self(rational.Rational(s))
4118        j = i + s[i:].find(')')
4119        n = int(s[i+2:j])
4120        if n == self.zeta_order():
4121            K = self
4122        else:
4123            K = CyclotomicField(n)
4124        zeta = K.gen()
4125        s = s.replace('E(%s)'%n,'zeta')
4126        s = sage.misc.all.sage_eval(s, locals={'zeta':K.gen()})
4127        if K is self:
4128            return s
4129        else:
4130            return self(s)
4131
4132    def _coerce_impl(self, x):
4133        """
4134        Canonical implicit coercion of x into self.
4135
4136        Elements of other compatible cyclotomic fields coerce in, as
4137        do elements of the rings that coerce to all number fields
4138        (e.g., integers, rationals).
4139
4140        EXAMPLES:
4141            sage: CyclotomicField(15)._coerce_impl(CyclotomicField(5).0 - 17/3)
4142            zeta15^3 - 17/3
4143            sage: K.<a> = CyclotomicField(16)
4144            sage: K(CyclotomicField(4).0)
4145            a^4
4146        """
4147        if isinstance(x, number_field_element.NumberFieldElement) and \
4148                isinstance(x.parent(), NumberField_cyclotomic):
4149            return self._coerce_from_other_cyclotomic_field(x, only_canonical=True)
4150        return NumberField_generic._coerce_impl(self, x)
4151
4152    def is_galois(self):
4153        """
4154        Return True since all cyclotomic fields are automatically Galois.
4155
4156        EXAMPLES:
4157            sage: CyclotomicField(29).is_galois()
4158            True
4159        """
4160        return True
4161
4162    def complex_embedding(self, prec=53):
4163        r"""
4164        Return the embedding of this cyclotomic field into the
4165        approximate complex field with precision prec obtained by
4166        sending the generator $\zeta$ of self to exp(2*pi*i/n), where
4167        $n$ is the multiplicative order of $\zeta$.
4168
4169        EXAMPLES:
4170            sage: C = CyclotomicField(4)
4171            sage: C.complex_embedding()
4172            Ring morphism:
4173              From: Cyclotomic Field of order 4 and degree 2
4174              To:   Complex Field with 53 bits of precision
4175              Defn: zeta4 |--> 6.12323399573677e-17 + 1.00000000000000*I
4176
4177        Note in the example above that the way zeta is computed (using
4178        sin and cosine in MPFR) means that only the prec bits of the
4179        number after the decimal point are valid.
4180
4181            sage: K = CyclotomicField(3)
4182            sage: phi = K.complex_embedding (10)
4183            sage: phi(K.0)
4184            -0.50 + 0.87*I
4185            sage: phi(K.0^3)
4186            1.0
4187            sage: phi(K.0^3 - 1)
4188            0
4189            sage: phi(K.0^3 + 7)
4190            8.0
4191        """
4192        CC = sage.rings.complex_field.ComplexField(prec)
4193        return self.hom([CC.zeta(self.zeta_order())], check=False)
4194
4195    def complex_embeddings(self, prec=53):
4196        r"""
4197        Return all embeddings of this cyclotomic field into the
4198        approximate complex field with precision prec.
4199
4200        EXAMPLES:
4201            sage: C = CyclotomicField(4)
4202            sage: C.complex_embeddings()
4203            [Ring morphism:
4204              From: Cyclotomic Field of order 4 and degree 2
4205              To:   Complex Field with 53 bits of precision
4206              Defn: zeta4 |--> 6.12323399573677e-17 + 1.00000000000000*I, Ring morphism:
4207              From: Cyclotomic Field of order 4 and degree 2
4208              To:   Complex Field with 53 bits of precision
4209              Defn: zeta4 |--> -0.000000000000000183697019872103 - 1.00000000000000*I]
4210        """
4211        CC = sage.rings.complex_field.ComplexField(prec)
4212        n = self.zeta_order()
4213        z = CC.zeta(self.zeta_order())
4214        X = [m for m in range(n) if sage.rings.arith.gcd(m,n) == 1]
4215        return [self.hom([z**n], check=False) for n in X]
4216
4217    def next_split_prime(self, p=2):
4218        """
4219        Return the next prime integer $p$ that splits completely in
4220        this cyclotomic field (and does not ramify).
4221
4222        EXAMPLES:
4223            sage: K.<z> = CyclotomicField(3)
4224            sage: K.next_split_prime(7)
4225            13
4226        """
4227        n = self.zeta_order()
4228        while True:
4229            p = sage.rings.arith.next_prime(p)
4230            if p % n == 1:
4231                return p
4232
4233    def integral_basis(self):
4234        """
4235        Return a list of elements of this number field that are a basis
4236        for the full ring of integers.
4237
4238        This field is cyclomotic, so this is a trivial computation,
4239        since the power basis on the generator is an integral basis.
4240
4241        EXAMPLES:
4242            sage: CyclotomicField(5).integral_basis()
4243            [1, zeta5, zeta5^2, zeta5^3]
4244        """
4245        try:
4246            return self.__integral_basis
4247        except AttributeError:
4248            z = self.gen()
4249            a = self(1)
4250            B = []
4251            for n in xrange(self.degree()):
4252                B.append(a)
4253                a *= z
4254            self.__integral_basis = B
4255        return self.__integral_basis
4256
4257
4258    def zeta_order(self):
4259        """
4260        Return the order of the root of unity that generates this
4261        cyclotomic field.
4262
4263        EXAMPLES:
4264            sage: CyclotomicField(1).zeta_order()
4265            1
4266            sage: CyclotomicField(4).zeta_order()
4267            4
4268            sage: CyclotomicField(5).zeta_order()
4269            5
4270            sage: CyclotomicField(389).zeta_order()
4271            389
4272        """
4273        return self.__zeta_order
4274
4275    def _multiplicative_order_table(self):
4276        """
4277        Return a dictionary that maps powers of zeta to their order.
4278        This makes computing the orders of the elements of finite
4279        order in this field faster.
4280
4281        EXAMPLES:
4282            sage: v = CyclotomicField(6)._multiplicative_order_table()
4283            sage: w = v.items(); w.sort(); w
4284            [(-1, 2), (1, 1), (-x, 3), (-x + 1, 6), (x - 1, 3), (x, 6)]
4285        """
4286        try:
4287            return self.__multiplicative_order_table
4288        except AttributeError:
4289            t = {}
4290            x = self(1)
4291            n = self.zeta_order()
4292            m = 0
4293            zeta = self.zeta()
4294            # todo: this desperately needs to be optimized!!!
4295            for i in range(n):
4296                t[x.polynomial()] = n//arith.GCD(m,n)   # multiplicative_order of (zeta_n)**m
4297                x *= zeta
4298                m += 1
4299            self.__multiplicative_order_table = t
4300            return t
4301
4302    def zeta(self, n=None, all=False):
4303        """
4304        Returns an element of multiplicative order $n$ in this this
4305        number field, if there is one.  Raises a ValueError if there
4306        is not.
4307
4308        INPUT:
4309            n -- integer (default: None, returns element of maximal order)
4310            all -- bool (default: False) -- whether to return a list of
4311                        all n-th roots.
4312
4313        OUTPUT:
4314            root of unity or list
4315
4316        EXAMPLES:
4317            sage: k = CyclotomicField(7)
4318            sage: k.zeta()
4319            zeta7
4320            sage: k.zeta().multiplicative_order()
4321            7
4322            sage: k = CyclotomicField(49)
4323            sage: k.zeta().multiplicative_order()
4324            49
4325            sage: k.zeta(7).multiplicative_order()
4326            7
4327            sage: k.zeta()
4328            zeta49
4329            sage: k.zeta(7)
4330            zeta49^7
4331
4332            sage: K.<a> = CyclotomicField(5)
4333            sage: K.zeta(4)
4334            Traceback (most recent call last):
4335            ...
4336            ValueError: n (=4) does not divide order of generator
4337            sage: v = K.zeta(5, all=True); v
4338            [a, a^2, a^3, -a^3 - a^2 - a - 1]
4339            sage: [b^5 for b in v]
4340            [1, 1, 1, 1]
4341        """
4342        if n is None:
4343            return self.gen()
4344        else:
4345            n = integer.Integer(n)
4346            z = self.gen()
4347            m = z.multiplicative_order()
4348            if m % n != 0:
4349                raise ValueError, "n (=%s) does not divide order of generator"%n
4350                # use generic method (factor cyclotomic polynomial)
4351                #  -- this is potentially really slow, so don't do it.
4352                #return field.Field.zeta(self, n, all=all)
4353            a = z**(m//n)
4354            if all:
4355                v = [a]
4356                b = a*a
4357                for i in range(2,n):
4358                    if sage.rings.arith.gcd(i, n) == 1:
4359                        v.append(b)
4360                    b = b * a
4361                return v
4362            else:
4363                return a
4364
4366    """
4367    Create a quadratic extension of the rational field.
4368
4369    The command QuadraticExtension(a) creates the field Q(sqrt(a)).
4370
4371    EXAMPLES:
4373        Number Field in a with defining polynomial x^2 - 3
4375        Number Field in b with defining polynomial x^2 + 4
4376    """
4377    def __init__(self, polynomial, name=None, check=True):
4378        """
4379        Create a quadratic number field.
4380
4381        EXAMPLES:
4382            sage: k.<a> = QuadraticField(5, check=False); k
4383            Number Field in a with defining polynomial x^2 - 5
4384
4385        Don't do this:
4386            sage: k.<a> = QuadraticField(4, check=False); k
4387            Number Field in a with defining polynomial x^2 - 4
4388        """
4389        NumberField_absolute.__init__(self, polynomial, name=name, check=check)
4390        return
4391        # optimized quadratic elements currently disabled -- they
4392        # break docs in the modular symbols / modular forms directory!!
4394        c, b, a = [rational.Rational(t) for t in self.defining_polynomial().list()]
4395        # set the generator
4396        D = b*b - 4*a*c
4397        d = D.numer().squarefree_part() * D.denom().squarefree_part()
4398        if d % 4 != 1:
4399            d *= 4
4400        self._NumberField_generic__disc = d
4401        parts = -b/(2*a), (D/d).sqrt()/(2*a)
4402        self._NumberField_generic__gen = self._element_class(self, parts)
4403
4404    def __reduce__(self):
4405        """
4406        This is used in pickling quadratic number fields.
4407
4408        TESTS:
4411            sage: print L
4412            Number Field in z7 with defining polynomial x^2 - 7
4413            sage: print L == K
4414            True
4415        """
4417
4418
4419    def is_galois(self):
4420        """
4421        Return True since all quadratic fields are automatically Galois.
4422
4423        EXAMPLES:
4425            True
4426        """
4427        return True
4428
4429    def class_number(self, proof=None):
4430        r"""
4431        Return the size of the class group of self.
4432
4433        If proof = False (*not* the default!) and the discriminant of the
4434        field is negative, then the following warning from the PARI
4435        manual applies: IMPORTANT WARNING: For $D<0$, this function
4436        may give incorrect results when the class group has a low
4437        exponent (has many cyclic factors), because implementing
4438        Shank's method in full generality slows it down immensely.
4439
4440        EXAMPLES:
4442            3
4443
4444        These are all the primes so that the class number of $\QQ(\sqrt{-p})$ is $1$:
4445            sage: [d for d in prime_range(2,300) if not is_square(d) and QuadraticField(-d,'a').class_number() == 1]
4446            [2, 3, 7, 11, 19, 43, 67, 163]
4447
4448        It is an open problem to \emph{prove} that there are infinity
4449        many positive square-free $d$ such that $\QQ(\sqrt{d})$ has
4450        class number $1$:n
4451            sage: len([d for d in range(2,200) if not is_square(d) and QuadraticField(d,'a').class_number() == 1])
4452            121
4453        """
4454        proof = proof_flag(proof)
4455        try:
4456            return self.__class_number
4457        except AttributeError:
4458            D = self.discriminant()
4459            if D < 0 and proof:
4460                self.__class_number = pari("qfbclassno(%s,1)"%D).python()
4461            else:
4462                self.__class_number = pari("qfbclassno(%s)"%D).python()
4463            return self.__class_number
4464
4465    def hilbert_class_polynomial(self):
4466        r"""
4467        Returns a polynomial over $\QQ$ whose roots generate the
4468        Hilbert class field of this quadratic field.
4469
4470        \note{Computed using PARI via Schertz's method.  This
4471        implementation is quite fast.}
4472
4473        EXAMPLES:
4475            sage: K.hilbert_class_polynomial()
4476            x^3 + x^2 - 1
4477
4479            sage: K.class_number()
4480            21
4481            sage: K.hilbert_class_polynomial()
4482            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
4483        """
4485        g = QQ['x'](f)
4486        return g
4487
4488    def hilbert_class_field(self, names):
4489        r"""
4490        Returns the Hilbert class field of this quadratic field as an
4491        absolute extension of $\QQ$.  For a polynomial that defines a
4492        relative extension see the \code{hilbert_class_polynomial}
4493        command.
4494
4495        \note{Computed using PARI via Schertz's method.  This implementation
4496        is amazingly fast.}
4497
4498        EXAMPLES:
4499            sage: x = QQ['x'].0
4500            sage: K = NumberField(x^2 + 23, 'a')
4501            sage: K.hilbert_class_polynomial()
4502            x^3 + x^2 - 1
4503            sage: K.hilbert_class_field('h')
4504            Number Field in h with defining polynomial x^6 + 2*x^5 + 70*x^4 + 90*x^3 + 1631*x^2 + 1196*x + 12743
4505        """
4506        f = self.hilbert_class_polynomial()
4507        C = self.composite_fields(NumberField(f,'x'),names)
4508        assert len(C) == 1
4509        return C[0]
4510
4511def is_fundamental_discriminant(D):
4512    r"""
4513    Return True if the integer $D$ is a fundamental discriminant, i.e.,
4514    if $D \con 0,1\pmod{4}$, and $D\neq 0, 1$ and either (1) $D$ is square free
4515    or (2) we have $D\con 0\pmod{4}$ with $D/4 \con 2,3\pmod{4}$ and $D/4$
4516    square free.  These are exactly the discriminants of quadratic fields.
4517
4518    EXAMPLES:
4519        sage: [D for D in range(-15,15) if is_fundamental_discriminant(D)]
4520        [-15, -11, -8, -7, -4, -3, 5, 8, 12, 13]
4521        sage: [D for D in range(-15,15) if not is_square(D) and QuadraticField(D,'a').disc() == D]
4522        [-15, -11, -8, -7, -4, -3, 5, 8, 12, 13]
4523    """
4524    d = D % 4
4525    if not (d in [0,1]):
4526        return False
4527    return D != 1 and  D != 0 and \
4528           (arith.is_squarefree(D) or \
4529            (d == 0 and (D//4)%4 in [2,3] and arith.is_squarefree(D//4)))
4530
4531
4532###################
4533# For pickling
4534###################
4535
4536
4537def NumberField_absolute_v1(poly, name, latex_name):
4538    """
4539    This is used in pickling generic number fields.
4540
4541    EXAMPLES:
4542        sage: from sage.rings.number_field.number_field import NumberField_generic_v1
4543        sage: R.<x> = QQ[]
4544        sage: NumberField_generic_v1(x^2 + 1, 'i', 'i')
4545        Number Field in i with defining polynomial x^2 + 1
4546    """
4547    return NumberField_absolute(poly, name, latex_name, check=False)
4548
4549NumberField_generic_v1 = NumberField_absolute_v1  # for historical reasons only (so old objects unpickle)
4550
4551def NumberField_relative_v1(base_field, poly, name, latex_name):
4552    """
4553    This is used in pickling relative fields.
4554
4555    EXAMPLES:
4556        sage: from sage.rings.number_field.number_field import NumberField_relative_v1
4557        sage: R.<x> = CyclotomicField(3)[]
4558        sage: NumberField_relative_v1(CyclotomicField(3), x^2 + 7, 'a', 'a')
4559        Number Field in a with defining polynomial x^2 + 7 over its base field
4560    """
4561    return NumberField_relative(base_field, poly, name, latex_name, check=False)
4562
4563NumberField_extension_v1 = NumberField_relative_v1  # historical reasons only
4564
4565def NumberField_cyclotomic_v1(zeta_order, name):
4566    """
4567    This is used in pickling cyclotomic fields.
4568
4569    EXAMPLES:
4570        sage: from sage.rings.number_field.number_field import NumberField_cyclotomic_v1
4571        sage: NumberField_cyclotomic_v1(5,'a')
4572        Cyclotomic Field of order 5 and degree 4
4573        sage: NumberField_cyclotomic_v1(5,'a').variable_name()
4574        'a'
4575    """
4576    return NumberField_cyclotomic(zeta_order, name)
4577
4579    """
4580    This is used in pickling quadratic fields.
4581
4582    EXAMPLES:
4583        sage: from sage.rings.number_field.number_field import NumberField_quadratic_v1
4584        sage: R.<x> = QQ[]
4585        sage: NumberField_quadratic_v1(x^2 - 2, 'd')
4586        Number Field in d with defining polynomial x^2 - 2
4587    """