Attachment 'number_field_element.pyx'
Download 1 """
2 Number Field Elements
3
4 AUTHORS:
5
6 - William Stein: version before it got Cython'd
7
8 - Joel B. Mohler (2007-03-09): First reimplementation in Cython
9
10 - William Stein (2007-09-04): add doctests
11
12 - Robert Bradshaw (2007-09-15): specialized classes for relative and
13 absolute elements
14
15 - John Cremona (2009-05-15): added support for local and global
16 logarithmic heights.
17
18 """
19
20 #*****************************************************************************
21 # Copyright (C) 2004, 2007 William Stein <[email protected]>
22 #
23 # Distributed under the terms of the GNU General Public License (GPL)
24 #
25 # This code is distributed in the hope that it will be useful,
26 # but WITHOUT ANY WARRANTY; without even the implied warranty of
27 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
28 # General Public License for more details.
29 #
30 # The full text of the GPL is available at:
31 #
32 # http://www.gnu.org/licenses/
33 #*****************************************************************************
34
35 import operator
36
37 include '../../ext/interrupt.pxi'
38 include '../../ext/python_int.pxi'
39 include "../../ext/stdsage.pxi"
40
41 import sage.rings.field_element
42 import sage.rings.infinity
43 import sage.rings.polynomial.polynomial_element
44 import sage.rings.rational_field
45 import sage.rings.rational
46 import sage.rings.integer_ring
47 import sage.rings.integer
48 import sage.rings.arith
49
50 import number_field
51
52 from sage.rings.integer_ring cimport IntegerRing_class
53 from sage.rings.rational cimport Rational
54
55 from sage.modules.free_module_element import vector
56
57 from sage.libs.all import pari_gen, pari
58 from sage.libs.pari.gen import PariError
59 from sage.structure.element cimport Element, generic_power_c
60
61 QQ = sage.rings.rational_field.QQ
62 ZZ = sage.rings.integer_ring.ZZ
63 Integer_sage = sage.rings.integer.Integer
64
65 from sage.rings.real_mpfi import RealInterval
66
67 from sage.rings.complex_field import ComplexField
68 CC = ComplexField(53)
69
70 # this is a threshold for the charpoly() methods in this file
71 # for degrees <= this threshold, pari is used
72 # for degrees > this threshold, sage matrices are used
73 # the value was decided by running a tuning script on a number of
74 # architectures; you can find this script attached to trac
75 # ticket 5213
76 TUNE_CHARPOLY_NF = 25
77
78 def is_NumberFieldElement(x):
79 """
80 Return True if x is of type NumberFieldElement, i.e., an element of
81 a number field.
82
83 EXAMPLES::
84
85 sage: from sage.rings.number_field.number_field_element import is_NumberFieldElement
86 sage: is_NumberFieldElement(2)
87 False
88 sage: k.<a> = NumberField(x^7 + 17*x + 1)
89 sage: is_NumberFieldElement(a+1)
90 True
91 """
92 return PY_TYPE_CHECK(x, NumberFieldElement)
93
94 def __create__NumberFieldElement_version0(parent, poly):
95 """
96 Used in unpickling elements of number fields pickled under very old Sage versions.
97
98 EXAMPLE::
99
100 sage: k.<a> = NumberField(x^3 - 2)
101 sage: R.<z> = QQ[]
102 sage: sage.rings.number_field.number_field_element.__create__NumberFieldElement_version0(k, z^2 + z + 1)
103 a^2 + a + 1
104 """
105 return NumberFieldElement(parent, poly)
106
107 def __create__NumberFieldElement_version1(parent, cls, poly):
108 """
109 Used in unpickling elements of number fields.
110
111 EXAMPLES:
112
113 Since this is just used in unpickling, we unpickle.
114
115 ::
116
117 sage: k.<a> = NumberField(x^3 - 2)
118 sage: loads(dumps(a+1)) == a + 1 # indirect doctest
119 True
120
121 This also gets called for unpickling order elements; we check that #6462 is
122 fixed::
123
124 sage: L = NumberField(x^3 - x - 1,'a'); OL = L.maximal_order(); w = OL.0
125 sage: loads(dumps(w)) == w # indirect doctest
126 True
127 """
128 return cls(parent, poly)
129
130 def _inverse_mod_generic(elt, I):
131 r"""
132 Return an inverse of elt modulo the given ideal. This is a separate
133 function called from each of the OrderElement_xxx classes, since
134 otherwise we'd have to have the same code three times over (there
135 is no OrderElement_generic class - no multiple inheritance). See
136 trac 4190.
137
138 EXAMPLES::
139
140 sage: OE = NumberField(x^3 - x + 2, 'w').ring_of_integers()
141 sage: w = OE.ring_generators()[0]
142 sage: from sage.rings.number_field.number_field_element import _inverse_mod_generic
143 sage: _inverse_mod_generic(w, 13*OE)
144 6*w^2 - 6
145 """
146 from sage.matrix.constructor import matrix
147 R = elt.parent()
148 try:
149 I = R.ideal(I)
150 except ValueError:
151 raise ValueError, "inverse is only defined modulo integral ideals"
152 if I == 0:
153 raise ValueError, "inverse is not defined modulo the zero ideal"
154 n = R.absolute_degree()
155 m = matrix(ZZ, map(R.coordinates, I.integral_basis() + [elt*s for s in R.gens()]))
156 a, b = m.echelon_form(transformation=True)
157 if a[0:n] != 1:
158 raise ZeroDivisionError, "%s is not invertible modulo %s" % (elt, I)
159 v = R.coordinates(1)
160 y = R(0)
161 for j in xrange(n):
162 if v[j] != 0:
163 y += v[j] * sum([b[j,i+n] * R.gen(i) for i in xrange(n)])
164 return I.small_residue(y)
165
166 __pynac_pow = False
167
168 cdef class NumberFieldElement(FieldElement):
169 """
170 An element of a number field.
171
172 EXAMPLES::
173
174 sage: k.<a> = NumberField(x^3 + x + 1)
175 sage: a^3
176 -a - 1
177 """
178 cdef _new(self):
179 """
180 Quickly creates a new initialized NumberFieldElement with the same
181 parent as self.
182 """
183 cdef NumberFieldElement x
184 x = <NumberFieldElement>PY_NEW_SAME_TYPE(self)
185 x._parent = self._parent
186 x.__fld_numerator = self.__fld_numerator
187 x.__fld_denominator = self.__fld_denominator
188 return x
189
190 cdef number_field(self):
191 r"""
192
193 Return the number field of self. Only accessible from Cython.
194 EXAMPLE::
195
196 sage: K.<a> = NumberField(x^3 + 3)
197 sage: a._number_field() # indirect doctest
198 Number Field in a with defining polynomial x^3 + 3
199 """
200 return self._parent
201
202 def _number_field(self):
203 r"""
204 EXAMPLE::
205
206 sage: K.<a> = NumberField(x^3 + 3)
207 sage: a._number_field()
208 Number Field in a with defining polynomial x^3 + 3
209 """
210 return self.number_field()
211
212 def __init__(self, parent, f):
213 """
214 INPUT:
215
216
217 - ``parent`` - a number field
218
219 - ``f`` - defines an element of a number field.
220
221
222 EXAMPLES:
223
224 The following examples illustrate creation of elements of
225 number fields, and some basic arithmetic.
226
227 First we define a polynomial over Q::
228
229 sage: R.<x> = PolynomialRing(QQ)
230 sage: f = x^2 + 1
231
232 Next we use f to define the number field::
233
234 sage: K.<a> = NumberField(f); K
235 Number Field in a with defining polynomial x^2 + 1
236 sage: a = K.gen()
237 sage: a^2
238 -1
239 sage: (a+1)^2
240 2*a
241 sage: a^2
242 -1
243 sage: z = K(5); 1/z
244 1/5
245
246 We create a cube root of 2::
247
248 sage: K.<b> = NumberField(x^3 - 2)
249 sage: b = K.gen()
250 sage: b^3
251 2
252 sage: (b^2 + b + 1)^3
253 12*b^2 + 15*b + 19
254
255 We can create number field elements from PARI::
256
257 sage: K.<a> = NumberField(x^3 - 17)
258 sage: K(pari(42))
259 42
260 sage: K(pari("5/3"))
261 5/3
262 sage: K(pari("[3/2, -5, 0]~")) # Uses Z-basis
263 -5/3*a^2 + 5/3*a - 1/6
264 sage: K(pari("-5/3*q^2 + 5/3*q - 1/6"))
265 -5/3*a^2 + 5/3*a - 1/6
266 sage: K(pari("Mod(-5/3*q^2 + 5/3*q - 1/6, q^3 - 17)"))
267 -5/3*a^2 + 5/3*a - 1/6
268 sage: K(pari("x^5/17"))
269 a^2
270
271 This example illustrates save and load::
272
273 sage: K.<a> = NumberField(x^17 - 2)
274 sage: s = a^15 - 19*a + 3
275 sage: loads(s.dumps()) == s
276 True
277 """
278 sage.rings.field_element.FieldElement.__init__(self, parent)
279 self.__fld_numerator, self.__fld_denominator = parent.absolute_polynomial_ntl()
280
281 cdef ZZ_c coeff
282 if isinstance(f, (int, long, Integer_sage)):
283 # set it up and exit immediately
284 # fast pathway
285 (<Integer>ZZ(f))._to_ZZ(&coeff)
286 ZZX_SetCoeff( self.__numerator, 0, coeff )
287 ZZ_conv_from_int( self.__denominator, 1 )
288 return
289
290 elif isinstance(f, NumberFieldElement):
291 if PY_TYPE(self) is PY_TYPE(f):
292 self.__numerator = (<NumberFieldElement>f).__numerator
293 self.__denominator = (<NumberFieldElement>f).__denominator
294 return
295 else:
296 f = f.polynomial()
297
298 from sage.rings.number_field import number_field_rel
299 if isinstance(parent, number_field_rel.NumberField_relative):
300 ppr = parent.base_field().polynomial_ring()
301 else:
302 ppr = parent.polynomial_ring()
303
304 if isinstance(f, pari_gen):
305 if f.type() in ["t_INT", "t_FRAC", "t_POL"]:
306 pass
307 elif f.type() == "t_POLMOD":
308 f = f.lift()
309 else:
310 f = self.number_field().pari_nf().nfbasistoalg_lift(f)
311 f = ppr(f)
312 if f.degree() >= parent.absolute_degree():
313 from sage.rings.number_field import number_field_rel
314 if isinstance(parent, number_field_rel.NumberField_relative):
315 f %= ppr(parent.absolute_polynomial())
316 else:
317 f %= parent.polynomial()
318
319 # Set Denominator
320 den = f.denominator()
321 (<Integer>ZZ(den))._to_ZZ(&self.__denominator)
322
323 num = f * den
324 cdef long i
325 for i from 0 <= i <= num.degree():
326 (<Integer>ZZ(num[i]))._to_ZZ(&coeff)
327 ZZX_SetCoeff( self.__numerator, i, coeff )
328
329 def __cinit__(self):
330 r"""
331 Initialise C variables.
332
333 EXAMPLE::
334
335 sage: K.<b> = NumberField(x^3 - 2)
336 sage: b = K.gen(); b # indirect doctest
337 b
338 """
339 ZZX_construct(&self.__numerator)
340 ZZ_construct(&self.__denominator)
341
342 def __dealloc__(self):
343 ZZX_destruct(&self.__numerator)
344 ZZ_destruct(&self.__denominator)
345
346 def _lift_cyclotomic_element(self, new_parent, bint check=True, int rel=0):
347 """
348 Creates an element of the passed field from this field. This is
349 specific to creating elements in a cyclotomic field from elements
350 in another cyclotomic field, in the case that
351 self.number_field()._n() divides new_parent()._n(). This
352 function aims to make this common coercion extremely fast!
353
354 More general coercion (i.e. of zeta6 into CyclotomicField(3)) is
355 implemented in the _coerce_from_other_cyclotomic_field method
356 of a CyclotomicField.
357
358 EXAMPLES::
359
360 sage: C.<zeta5>=CyclotomicField(5)
361 sage: CyclotomicField(10)(zeta5+1) # The function _lift_cyclotomic_element does the heavy lifting in the background
362 zeta10^2 + 1
363 sage: (zeta5+1)._lift_cyclotomic_element(CyclotomicField(10)) # There is rarely a purpose to call this function directly
364 zeta10^2 + 1
365 sage: cf4 = CyclotomicField(4)
366 sage: cf1 = CyclotomicField(1) ; one = cf1.0
367 sage: cf4(one)
368 1
369 sage: type(cf4(1))
370 <type 'sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic'>
371 sage: cf33 = CyclotomicField(33) ; z33 = cf33.0
372 sage: cf66 = CyclotomicField(66) ; z66 = cf66.0
373 sage: z33._lift_cyclotomic_element(cf66)
374 zeta66^2
375 sage: z66._lift_cyclotomic_element(cf33)
376 Traceback (most recent call last):
377 ...
378 TypeError: The zeta_order of the new field must be a multiple of the zeta_order of the original.
379 sage: cf33(z66)
380 -zeta33^17
381
382 AUTHORS:
383
384 - Joel B. Mohler
385
386 - Craig Citro (fixed behavior for different representation of
387 quadratic field elements)
388 """
389 if check:
390 if not isinstance(self.number_field(), number_field.NumberField_cyclotomic) \
391 or not isinstance(new_parent, number_field.NumberField_cyclotomic):
392 raise TypeError, "The field and the new parent field must both be cyclotomic fields."
393
394 if rel == 0:
395 small_order = self.number_field()._n()
396 large_order = new_parent._n()
397
398 try:
399 rel = ZZ(large_order / small_order)
400 except TypeError:
401 raise TypeError, "The zeta_order of the new field must be a multiple of the zeta_order of the original."
402
403 ## degree 2 is handled differently, because elements are
404 ## represented differently
405 if new_parent.degree() == 2:
406 return new_parent._element_class(new_parent, self)
407
408 cdef NumberFieldElement x = <NumberFieldElement>PY_NEW_SAME_TYPE(self)
409 x._parent = <ParentWithBase>new_parent
410 x.__fld_numerator, x.__fld_denominator = new_parent.polynomial_ntl()
411 x.__denominator = self.__denominator
412 cdef ZZX_c result
413 cdef ZZ_c tmp
414 cdef int i
415 cdef ntl_ZZX _num
416 cdef ntl_ZZ _den
417 for i from 0 <= i <= ZZX_deg(self.__numerator):
418 tmp = ZZX_coeff(self.__numerator, i)
419 ZZX_SetCoeff(result, i*rel, tmp)
420 ZZX_rem(x.__numerator, result, x.__fld_numerator.x)
421 return x
422
423 def __reduce__(self):
424 """
425 Used in pickling number field elements.
426
427 Note for developers: If this is changed, please also change the doctests of __create__NumberFieldElement_version1.
428
429 EXAMPLES::
430
431 sage: k.<a> = NumberField(x^3 - 17*x^2 + 1)
432 sage: t = a.__reduce__(); t
433 (<built-in function __create__NumberFieldElement_version1>, (Number Field in a with defining polynomial x^3 - 17*x^2 + 1, <type 'sage.rings.number_field.number_field_element.NumberFieldElement_absolute'>, x))
434 sage: t[0](*t[1]) == a
435 True
436 """
437 return __create__NumberFieldElement_version1, \
438 (self.parent(), type(self), self.polynomial())
439
440 def _repr_(self):
441 """
442 String representation of this number field element, which is just a
443 polynomial in the generator.
444
445 EXAMPLES::
446
447 sage: k.<a> = NumberField(x^2 + 2)
448 sage: b = (2/3)*a + 3/5
449 sage: b._repr_()
450 '2/3*a + 3/5'
451 """
452 x = self.polynomial()
453 K = self.number_field()
454 return str(x).replace(x.parent().variable_name(), K.variable_name())
455
456 def _im_gens_(self, codomain, im_gens):
457 """
458 This is used in computing homomorphisms between number fields.
459
460 EXAMPLES::
461
462 sage: k.<a> = NumberField(x^2 - 2)
463 sage: m.<b> = NumberField(x^4 - 2)
464 sage: phi = k.hom([b^2])
465 sage: phi(a+1)
466 b^2 + 1
467 sage: (a+1)._im_gens_(m, [b^2])
468 b^2 + 1
469 """
470 # NOTE -- if you ever want to change this so relative number
471 # fields are in terms of a root of a poly. The issue is that
472 # elements of a relative number field are represented in terms
473 # of a generator for the absolute field. However the morphism
474 # gives the image of gen, which need not be a generator for
475 # the absolute field. The morphism has to be *over* the
476 # relative element.
477 return codomain(self.polynomial()(im_gens[0]))
478
479 def _latex_(self):
480 """
481 Returns the latex representation for this element.
482
483 EXAMPLES::
484
485 sage: C,zeta12=CyclotomicField(12).objgen()
486 sage: latex(zeta12^4-zeta12) # indirect doctest
487 \zeta_{12}^{2} - \zeta_{12} - 1
488 """
489 return self.polynomial()._latex_(name=self.number_field().latex_variable_name())
490
491 def _gap_init_(self):
492 """
493 Return gap string representation of self.
494
495 EXAMPLES::
496
497 sage: F=CyclotomicField(8)
498 sage: p=F.gen()^2+2*F.gen()-3
499 sage: p
500 zeta8^2 + 2*zeta8 - 3
501 sage: p._gap_init_() # The variable name $sage2 belongs to the gap(F) and is somehow random
502 'GeneratorsOfField($sage2)[1]^2 + 2*GeneratorsOfField($sage2)[1] - 3'
503 sage: gap(p._gap_init_())
504 zeta8^2+2*zeta8-3
505 """
506 s = self._repr_()
507 return s.replace(str(self.parent().gen()), 'GeneratorsOfField(%s)[1]'%sage.interfaces.gap.gap(self.parent()).name())
508
509
510 def _pari_(self, var='x'):
511 r"""
512 Convert self to a Pari element.
513
514 EXAMPLE::
515
516 sage: K.<a> = NumberField(x^3 + 2)
517 sage: (a + 2)._pari_()
518 Mod(x + 2, x^3 + 2)
519 sage: L.<b> = K.extension(x^2 + 2)
520 sage: (b + a)._pari_()
521 Mod(24/101*x^5 - 9/101*x^4 + 160/101*x^3 - 156/101*x^2 + 397/101*x + 364/101, x^6 + 6*x^4 - 4*x^3 + 12*x^2 + 24*x + 12)
522 """
523 raise NotImplementedError, "NumberFieldElement sub-classes must override _pari_"
524
525 def _pari_init_(self, var='x'):
526 """
527 Return PARI/GP string representation of self. This is used for
528 converting this number field element to PARI/GP. The returned
529 string defines a pari Mod in the variable is var, which is by
530 default 'x' - not the name of the generator of the number field.
531
532 INPUT:
533
534
535 - ``var`` - (default: 'x') the variable of the pari
536 Mod.
537
538
539 EXAMPLES::
540
541 sage: K.<a> = NumberField(x^5 - x - 1)
542 sage: ((1 + 1/3*a)^4)._pari_init_()
543 'Mod(1/81*x^4 + 4/27*x^3 + 2/3*x^2 + 4/3*x + 1, x^5 - x - 1)'
544 sage: ((1 + 1/3*a)^4)._pari_init_('a')
545 'Mod(1/81*a^4 + 4/27*a^3 + 2/3*a^2 + 4/3*a + 1, a^5 - a - 1)'
546
547 Note that _pari_init_ can fail because of reserved words in
548 PARI, and since it actually works by obtaining the PARI
549 representation of something::
550
551 sage: K.<theta> = NumberField(x^5 - x - 1)
552 sage: b = (1/2 - 2/3*theta)^3; b
553 -8/27*theta^3 + 2/3*theta^2 - 1/2*theta + 1/8
554 sage: b._pari_init_('theta')
555 Traceback (most recent call last):
556 ...
557 PariError: (26)
558
559 Fortunately pari_init returns everything in terms of x by
560 default::
561
562 sage: pari(b)
563 Mod(-8/27*x^3 + 2/3*x^2 - 1/2*x + 1/8, x^5 - x - 1)
564 """
565 return repr(self._pari_(var=var))
566
567 def __getitem__(self, n):
568 """
569 Return the n-th coefficient of this number field element, written
570 as a polynomial in the generator.
571
572 Note that `n` must be between 0 and `d-1`, where
573 `d` is the degree of the number field.
574
575 EXAMPLES::
576
577 sage: m.<b> = NumberField(x^4 - 1789)
578 sage: c = (2/3-4/5*b)^3; c
579 -64/125*b^3 + 32/25*b^2 - 16/15*b + 8/27
580 sage: c[0]
581 8/27
582 sage: c[2]
583 32/25
584 sage: c[3]
585 -64/125
586
587 We illustrate bounds checking::
588
589 sage: c[-1]
590 Traceback (most recent call last):
591 ...
592 IndexError: index must be between 0 and degree minus 1.
593 sage: c[4]
594 Traceback (most recent call last):
595 ...
596 IndexError: index must be between 0 and degree minus 1.
597
598 The list method implicitly calls ``__getitem__``::
599
600 sage: list(c)
601 [8/27, -16/15, 32/25, -64/125]
602 sage: m(list(c)) == c
603 True
604 """
605 if n < 0 or n >= self.number_field().degree(): # make this faster.
606 raise IndexError, "index must be between 0 and degree minus 1."
607 return self.polynomial()[n]
608
609 def __richcmp__(left, right, int op):
610 r"""
611 EXAMPLE::
612
613 sage: K.<a> = NumberField(x^3 - 3*x + 8)
614 sage: a + 1 > a # indirect doctest
615 True
616 sage: a + 1 < a # indirect doctest
617 False
618 """
619 return (<Element>left)._richcmp(right, op)
620
621 cdef int _cmp_c_impl(left, sage.structure.element.Element right) except -2:
622 cdef NumberFieldElement _right = right
623 return not (ZZX_equal(left.__numerator, _right.__numerator) and ZZ_equal(left.__denominator, _right.__denominator))
624
625 def _random_element(self, num_bound=None, den_bound=None, distribution=None):
626 """
627 Return a new random element with the same parent as self.
628
629 INPUT:
630
631 - ``num_bound`` - Bound for the numerator of coefficients of result
632
633 - ``den_bound`` - Bound for the denominator of coefficients of result
634
635 - ``distribution`` - Distribution to use for coefficients of result
636
637 EXAMPLES::
638
639 sage: K.<a> = NumberField(x^3-2)
640 sage: a._random_element()
641 -1/2*a^2 - 4
642 sage: K.<a> = NumberField(x^2-5)
643 sage: a._random_element()
644 -2*a - 1
645 """
646 cdef NumberFieldElement elt = self._new()
647 elt._randomize(num_bound, den_bound, distribution)
648 return elt
649
650 cdef void _randomize(self, num_bound, den_bound, distribution):
651 cdef int i
652 cdef Integer denom_temp = PY_NEW(Integer)
653 cdef Integer tmp_integer = PY_NEW(Integer)
654 cdef ZZ_c ntl_temp
655 cdef list coeff_list
656 cdef Rational tmp_rational
657
658 # It seems like a simpler approach would be to simply generate
659 # random integers for each coefficient of self.__numerator
660 # and an integer for self.__denominator. However, this would
661 # generate things with a fairly fixed shape: in particular,
662 # we'd be very unlikely to get elements like 1/3*a^3 + 1/7,
663 # or anything where the denominators are actually unrelated
664 # to one another. The extra code below is to make exactly
665 # these kinds of results possible.
666
667 if den_bound == 1:
668 # in this case, we can skip all the business with LCMs,
669 # storing a list of rationals, etc. this gives a factor of
670 # two or so speedup ...
671
672 # set the denominator
673 mpz_set_si(denom_temp.value, 1)
674 denom_temp._to_ZZ(&self.__denominator)
675 for i from 0 <= i < ZZX_deg(self.__fld_numerator.x):
676 tmp_integer = <Integer>(ZZ.random_element(x=num_bound,
677 distribution=distribution))
678 tmp_integer._to_ZZ(&ntl_temp)
679 ZZX_SetCoeff(self.__numerator, i, ntl_temp)
680
681 else:
682 coeff_list = []
683 mpz_set_si(denom_temp.value, 1)
684 tmp_integer = PY_NEW(Integer)
685
686 for i from 0 <= i < ZZX_deg(self.__fld_numerator.x):
687 tmp_rational = <Rational>(QQ.random_element(num_bound=num_bound,
688 den_bound=den_bound,
689 distribution=distribution))
690 coeff_list.append(tmp_rational)
691 mpz_lcm(denom_temp.value, denom_temp.value,
692 mpq_denref(tmp_rational.value))
693
694 # now denom_temp has the denominator, and we just need to
695 # scale the numerators and set everything appropriately
696
697 # first, the denominator (easy)
698 denom_temp._to_ZZ(&self.__denominator)
699
700 # now the coefficients themselves.
701 for i from 0 <= i < ZZX_deg(self.__fld_numerator.x):
702 # calculate the new numerator. if our old entry is
703 # p/q, and the lcm is k, it's just pk/q, which we
704 # also know is integral -- so we can use mpz_divexact
705 # below
706 tmp_rational = <Rational>(coeff_list[i])
707 mpz_mul(tmp_integer.value, mpq_numref(tmp_rational.value),
708 denom_temp.value)
709 mpz_divexact(tmp_integer.value, tmp_integer.value,
710 mpq_denref(tmp_rational.value))
711
712 # now set the coefficient of self
713 tmp_integer._to_ZZ(&ntl_temp)
714 ZZX_SetCoeff(self.__numerator, i, ntl_temp)
715
716 def __abs__(self):
717 r"""
718 Return the numerical absolute value of this number field element
719 with respect to the first archimedean embedding, to double
720 precision.
721
722 This is the ``abs( )`` Python function. If you want a
723 different embedding or precision, use
724 ``self.abs(...)``.
725
726 EXAMPLES::
727
728 sage: k.<a> = NumberField(x^3 - 2)
729 sage: abs(a)
730 1.25992104989487
731 sage: abs(a)^3
732 2.00000000000000
733 sage: a.abs(prec=128)
734 1.2599210498948731647672106072782283506
735 """
736 return self.abs(prec=53, i=0)
737
738 def abs(self, prec=53, i=0):
739 r"""
740 Return the absolute value of this element with respect to the
741 `i`-th complex embedding of parent, to the given precision.
742
743 If prec is 53 (the default), then the complex double field is
744 used; otherwise the arbitrary precision (but slow) complex
745 field is used.
746
747 INPUT:
748
749
750 - ``prec`` - (default: 53) integer bits of precision
751
752 - ``i`` - (default: ) integer, which embedding to
753 use
754
755
756 EXAMPLES::
757
758 sage: z = CyclotomicField(7).gen()
759 sage: abs(z)
760 1.00000000000000
761 sage: abs(z^2 + 17*z - 3)
762 16.0604426799931
763 sage: K.<a> = NumberField(x^3+17)
764 sage: abs(a)
765 2.57128159065824
766 sage: a.abs(prec=100)
767 2.5712815906582353554531872087
768 sage: a.abs(prec=100,i=1)
769 2.5712815906582353554531872087
770 sage: a.abs(100, 2)
771 2.5712815906582353554531872087
772
773 Here's one where the absolute value depends on the embedding.
774
775 ::
776
777 sage: K.<b> = NumberField(x^2-2)
778 sage: a = 1 + b
779 sage: a.abs(i=0)
780 0.414213562373095
781 sage: a.abs(i=1)
782 2.41421356237309
783 """
784 P = self.number_field().complex_embeddings(prec)[i]
785 return abs(P(self))
786
787 def abs_non_arch(self, P, prec=None):
788 r"""
789 Return the non-archimedean absolute value of this element with
790 respect to the prime `P`, to the given precision.
791
792 INPUT:
793
794 - ``P`` - a prime ideal of the parent of self
795
796 - ``prec`` (int) -- desired floating point precision (default:
797 default RealField precision).
798
799 OUTPUT:
800
801 (real) the non-archimedean absolute value of this element with
802 respect to the prime `P`, to the given precision. This is the
803 normalised absolute value, so that the underlying prime number
804 `p` has absolute value `1/p`.
805
806
807 EXAMPLES::
808
809 sage: K.<a> = NumberField(x^2+5)
810 sage: [1/K(2).abs_non_arch(P) for P in K.primes_above(2)]
811 [2.00000000000000]
812 sage: [1/K(3).abs_non_arch(P) for P in K.primes_above(3)]
813 [3.00000000000000, 3.00000000000000]
814 sage: [1/K(5).abs_non_arch(P) for P in K.primes_above(5)]
815 [5.00000000000000]
816
817 A relative example::
818
819 sage: L.<b> = K.extension(x^2-5)
820 sage: [b.abs_non_arch(P) for P in L.primes_above(b)]
821 [0.447213595499958, 0.447213595499958]
822 """
823 from sage.rings.real_mpfr import RealField
824 if prec is None:
825 R = RealField()
826 else:
827 R = RealField(prec)
828
829 if self.is_zero():
830 return R.zero_element()
831 val = self.valuation(P)
832 nP = P.residue_class_degree()*P.absolute_ramification_index()
833 return R(P.absolute_norm()) ** (-R(val) / R(nP))
834
835 def coordinates_in_terms_of_powers(self):
836 r"""
837 Let `\alpha` be self. Return a callable object (of type
838 :class:`~CoordinateFunction`) that takes any element of the
839 parent of self in `\QQ(\alpha)` and writes it in terms of the
840 powers of `\alpha`: `1, \alpha, \alpha^2, ...`.
841
842 (NOT CACHED).
843
844 EXAMPLES:
845
846 This function allows us to write elements of a number
847 field in terms of a different generator without having to construct
848 a whole separate number field.
849
850 ::
851
852 sage: y = polygen(QQ,'y'); K.<beta> = NumberField(y^3 - 2); K
853 Number Field in beta with defining polynomial y^3 - 2
854 sage: alpha = beta^2 + beta + 1
855 sage: c = alpha.coordinates_in_terms_of_powers(); c
856 Coordinate function that writes elements in terms of the powers of beta^2 + beta + 1
857 sage: c(beta)
858 [-2, -3, 1]
859 sage: c(alpha)
860 [0, 1, 0]
861 sage: c((1+beta)^5)
862 [3, 3, 3]
863 sage: c((1+beta)^10)
864 [54, 162, 189]
865
866 This function works even if self only generates a subfield of this
867 number field.
868
869 ::
870
871 sage: k.<a> = NumberField(x^6 - 5)
872 sage: alpha = a^3
873 sage: c = alpha.coordinates_in_terms_of_powers()
874 sage: c((2/3)*a^3 - 5/3)
875 [-5/3, 2/3]
876 sage: c
877 Coordinate function that writes elements in terms of the powers of a^3
878 sage: c(a)
879 Traceback (most recent call last):
880 ...
881 ArithmeticError: vector is not in free module
882 """
883 K = self.number_field()
884 V, from_V, to_V = K.absolute_vector_space()
885 h = K(1)
886 B = [to_V(h)]
887 f = self.absolute_minpoly()
888 for i in range(f.degree()-1):
889 h *= self
890 B.append(to_V(h))
891 W = V.span_of_basis(B)
892 return CoordinateFunction(self, W, to_V)
893
894 def complex_embeddings(self, prec=53):
895 """
896 Return the images of this element in the floating point complex
897 numbers, to the given bits of precision.
898
899 INPUT:
900
901
902 - ``prec`` - integer (default: 53) bits of precision
903
904
905 EXAMPLES::
906
907 sage: k.<a> = NumberField(x^3 - 2)
908 sage: a.complex_embeddings()
909 [-0.629960524947437 - 1.09112363597172*I, -0.629960524947437 + 1.09112363597172*I, 1.25992104989487]
910 sage: a.complex_embeddings(10)
911 [-0.63 - 1.1*I, -0.63 + 1.1*I, 1.3]
912 sage: a.complex_embeddings(100)
913 [-0.62996052494743658238360530364 - 1.0911236359717214035600726142*I, -0.62996052494743658238360530364 + 1.0911236359717214035600726142*I, 1.2599210498948731647672106073]
914 """
915 phi = self.number_field().complex_embeddings(prec)
916 return [f(self) for f in phi]
917
918 def complex_embedding(self, prec=53, i=0):
919 """
920 Return the i-th embedding of self in the complex numbers, to the
921 given precision.
922
923 EXAMPLES::
924
925 sage: k.<a> = NumberField(x^3 - 2)
926 sage: a.complex_embedding()
927 -0.629960524947437 - 1.09112363597172*I
928 sage: a.complex_embedding(10)
929 -0.63 - 1.1*I
930 sage: a.complex_embedding(100)
931 -0.62996052494743658238360530364 - 1.0911236359717214035600726142*I
932 sage: a.complex_embedding(20, 1)
933 -0.62996 + 1.0911*I
934 sage: a.complex_embedding(20, 2)
935 1.2599
936 """
937 return self.number_field().complex_embeddings(prec)[i](self)
938
939 def _mpfr_(self, R):
940 """
941 EXAMPLES::
942
943 sage: k.<a> = NumberField(x^2 + 1)
944 sage: RR(a^2)
945 -1.00000000000000
946 sage: RR(a)
947 Traceback (most recent call last):
948 ...
949 TypeError: cannot convert a to real number
950
951 sage: (a^2)._mpfr_(RR)
952 -1.00000000000000
953 """
954 C = R.complex_field()
955 tres = C(self)
956 try:
957 return R(tres)
958 except TypeError:
959 raise TypeError, "cannot convert %s to real number"%(self)
960
961 def __float__(self):
962 """
963 EXAMPLES::
964
965 sage: k.<a> = NumberField(x^2 + 1)
966 sage: float(a^2)
967 -1.0
968 sage: float(a)
969 Traceback (most recent call last):
970 ...
971 TypeError: cannot convert a to real number
972
973 sage: (a^2).__float__()
974 -1.0
975 """
976 tres = CC(self)
977 try:
978 return float(tres)
979 except TypeError:
980 raise TypeError, "cannot convert %s to real number"%(self)
981
982 def _complex_double_(self, CDF):
983 """
984 EXAMPLES::
985
986 sage: k.<a> = NumberField(x^2 + 1)
987 sage: abs(CDF(a))
988 1.0
989 """
990 return CDF(CC(self))
991
992 def __complex__(self):
993 """
994 EXAMPLES::
995
996 sage: k.<a> = NumberField(x^2 + 1)
997 sage: complex(a)
998 1j
999 sage: a.__complex__()
1000 1j
1001 """
1002 return complex(CC(self))
1003
1004 def factor(self):
1005 """
1006 Return factorization of this element into prime elements and a unit.
1007
1008 OUTPUT:
1009
1010 (Factorization) If all the prime ideals in the support are
1011 principal, the output is a Factorization as a product of prime
1012 elements raised to appropriate powers, with an appropriate
1013 unit factor.
1014
1015 Raise ValueError if the factorization of the
1016 ideal (self) contains a non-principal prime ideal.
1017
1018 EXAMPLES::
1019
1020 sage: K.<i> = NumberField(x^2+1)
1021 sage: (6*i + 6).factor()
1022 (-i) * (i + 1)^3 * 3
1023
1024 In the following example, the class number is 2. If a factorization
1025 in prime elements exists, we will find it::
1026
1027 sage: K.<a> = NumberField(x^2-10)
1028 sage: factor(169*a + 531)
1029 (-6*a - 19) * (-2*a + 9) * (-3*a - 1)
1030 sage: factor(K(3))
1031 Traceback (most recent call last):
1032 ...
1033 ValueError: Non-principal ideal in factorization
1034
1035 Factorization of 0 is not allowed::
1036
1037 sage: K.<i> = QuadraticField(-1)
1038 sage: K(0).factor()
1039 Traceback (most recent call last):
1040 ...
1041 ArithmeticError: Factorization of 0 not defined.
1042
1043 """
1044 if self.is_zero():
1045 raise ArithmeticError, "Factorization of 0 not defined."
1046
1047 K = self.parent()
1048 fac = K.ideal(self).factor()
1049 # Check whether all prime ideals in `fac` are principal
1050 for P,e in fac:
1051 if not P.is_principal():
1052 raise ValueError, "Non-principal ideal in factorization"
1053 element_fac = [(P.gens_reduced()[0],e) for P,e in fac]
1054 # Compute the product of the p^e to figure out the unit
1055 from sage.misc.all import prod
1056 element_product = prod([p**e for p,e in element_fac], K(1))
1057 from sage.structure.all import Factorization
1058 return Factorization(element_fac, unit=self/element_product)
1059
1060 def is_totally_positive(self):
1061 """
1062 Returns True if self is positive for all real embeddings of its
1063 parent number field. We do nothing at complex places, so e.g. any
1064 element of a totally complex number field will return True.
1065
1066 EXAMPLES::
1067
1068 sage: F.<b> = NumberField(x^3-3*x-1)
1069 sage: b.is_totally_positive()
1070 False
1071 sage: (b^2).is_totally_positive()
1072 True
1073
1074 TESTS:
1075
1076 Check that the output is correct even for numbers that are
1077 very close to zero (ticket #9596)::
1078
1079 sage: K.<sqrt2> = QuadraticField(2)
1080 sage: a = 30122754096401; b = 21300003689580
1081 sage: (a/b)^2 > 2
1082 True
1083 sage: (a/b+sqrt2).is_totally_positive()
1084 True
1085 sage: r = RealField(3020)(2).sqrt()*2^3000
1086 sage: a = floor(r)/2^3000
1087 sage: b = ceil(r)/2^3000
1088 sage: (a+sqrt2).is_totally_positive()
1089 False
1090 sage: (b+sqrt2).is_totally_positive()
1091 True
1092
1093 Check that 0 is handled correctly::
1094
1095 sage: K.<a> = NumberField(x^5+4*x+1)
1096 sage: K(0).is_totally_positive()
1097 False
1098 """
1099 for v in self.number_field().embeddings(sage.rings.qqbar.AA):
1100 if v(self) <= 0:
1101 return False
1102 return True
1103
1104 def is_square(self, root=False):
1105 """
1106 Return True if self is a square in its parent number field and
1107 otherwise return False.
1108
1109 INPUT:
1110
1111
1112 - ``root`` - if True, also return a square root (or
1113 None if self is not a perfect square)
1114
1115
1116 EXAMPLES::
1117
1118 sage: m.<b> = NumberField(x^4 - 1789)
1119 sage: b.is_square()
1120 False
1121 sage: c = (2/3*b + 5)^2; c
1122 4/9*b^2 + 20/3*b + 25
1123 sage: c.is_square()
1124 True
1125 sage: c.is_square(True)
1126 (True, 2/3*b + 5)
1127
1128 We also test the functional notation.
1129
1130 ::
1131
1132 sage: is_square(c, True)
1133 (True, 2/3*b + 5)
1134 sage: is_square(c)
1135 True
1136 sage: is_square(c+1)
1137 False
1138 """
1139 v = self.sqrt(all=True)
1140 t = len(v) > 0
1141 if root:
1142 if t:
1143 return t, v[0]
1144 else:
1145 return False, None
1146 else:
1147 return t
1148
1149 def sqrt(self, all=False):
1150 """
1151 Returns the square root of this number in the given number field.
1152
1153 EXAMPLES::
1154
1155 sage: K.<a> = NumberField(x^2 - 3)
1156 sage: K(3).sqrt()
1157 a
1158 sage: K(3).sqrt(all=True)
1159 [a, -a]
1160 sage: K(a^10).sqrt()
1161 9*a
1162 sage: K(49).sqrt()
1163 7
1164 sage: K(1+a).sqrt()
1165 Traceback (most recent call last):
1166 ...
1167 ValueError: a + 1 not a square in Number Field in a with defining polynomial x^2 - 3
1168 sage: K(0).sqrt()
1169 0
1170 sage: K((7+a)^2).sqrt(all=True)
1171 [a + 7, -a - 7]
1172
1173 ::
1174
1175 sage: K.<a> = CyclotomicField(7)
1176 sage: a.sqrt()
1177 a^4
1178
1179 ::
1180
1181 sage: K.<a> = NumberField(x^5 - x + 1)
1182 sage: (a^4 + a^2 - 3*a + 2).sqrt()
1183 a^3 - a^2
1184
1185 ALGORITHM: Use Pari to factor `x^2` - ``self``
1186 in K.
1187 """
1188 # For now, use pari's factoring abilities
1189 R = self.number_field()['t']
1190 f = R([-self, 0, 1])
1191 roots = f.roots()
1192 if all:
1193 return [r[0] for r in roots]
1194 elif len(roots) > 0:
1195 return roots[0][0]
1196 else:
1197 try:
1198 # This is what integers, rationals do...
1199 from sage.all import SR, sqrt
1200 return sqrt(SR(self))
1201 except TypeError:
1202 raise ValueError, "%s not a square in %s"%(self, self._parent)
1203
1204 def nth_root(self, n, all=False):
1205 r"""
1206 Return an nth root of self in the given number field.
1207
1208 EXAMPLES::
1209
1210 sage: K.<a> = NumberField(x^4-7)
1211 sage: K(7).nth_root(2)
1212 a^2
1213 sage: K((a-3)^5).nth_root(5)
1214 a - 3
1215
1216 ALGORITHM: Use Pari to factor `x^n` - ``self``
1217 in K.
1218 """
1219 R = self.number_field()['t']
1220 if not self:
1221 return [self] if all else self
1222 f = (R.gen(0) << (n-1)) - self
1223 roots = f.roots()
1224 if all:
1225 return [r[0] for r in roots]
1226 elif len(roots) > 0:
1227 return roots[0][0]
1228 else:
1229 raise ValueError, "%s not a %s-th root in %s"%(self, n, self._parent)
1230
1231 def __pow__(base, exp, dummy):
1232 """
1233 EXAMPLES::
1234
1235 sage: K.<sqrt2> = QuadraticField(2)
1236 sage: sqrt2^2
1237 2
1238 sage: sqrt2^5
1239 4*sqrt2
1240 sage: (1+sqrt2)^100
1241 66992092050551637663438906713182313772*sqrt2 + 94741125149636933417873079920900017937
1242 sage: (1+sqrt2)^-1
1243 sqrt2 - 1
1244
1245 If the exponent is not integral, perform this operation in
1246 the symbolic ring::
1247
1248 sage: sqrt2^(1/5)
1249 2^(1/10)
1250 sage: sqrt2^sqrt2
1251 2^(1/2*sqrt(2))
1252
1253 TESTS::
1254
1255 sage: 2^I
1256 2^I
1257 """
1258 if (PY_TYPE_CHECK(base, NumberFieldElement) and
1259 (PY_TYPE_CHECK(exp, Integer) or PY_TYPE_CHECK_EXACT(exp, int) or exp in ZZ)):
1260 return generic_power_c(base, exp, None)
1261 else:
1262 from sage.symbolic.power_helper import try_symbolic_power
1263 return try_symbolic_power(base, exp)
1264
1265 cdef void _reduce_c_(self):
1266 """
1267 Pull out common factors from the numerator and denominator!
1268 """
1269 cdef ZZ_c gcd
1270 cdef ZZ_c t1
1271 cdef ZZX_c t2
1272 ZZX_content(t1, self.__numerator)
1273 ZZ_GCD(gcd, t1, self.__denominator)
1274 if ZZ_sign(gcd) != ZZ_sign(self.__denominator):
1275 ZZ_negate(t1, gcd)
1276 gcd = t1
1277 ZZX_div_ZZ(t2, self.__numerator, gcd)
1278 ZZ_div(t1, self.__denominator, gcd)
1279 self.__numerator = t2
1280 self.__denominator = t1
1281
1282 cpdef ModuleElement _add_(self, ModuleElement right):
1283 r"""
1284 EXAMPLE::
1285
1286 sage: K.<s> = QuadraticField(2)
1287 sage: s + s # indirect doctest
1288 2*s
1289 sage: s + ZZ(3) # indirect doctest
1290 s + 3
1291 """
1292 cdef NumberFieldElement x
1293 cdef NumberFieldElement _right = right
1294 x = self._new()
1295 ZZ_mul(x.__denominator, self.__denominator, _right.__denominator)
1296 cdef ZZX_c t1, t2
1297 ZZX_mul_ZZ(t1, self.__numerator, _right.__denominator)
1298 ZZX_mul_ZZ(t2, _right.__numerator, self.__denominator)
1299 ZZX_add(x.__numerator, t1, t2)
1300 x._reduce_c_()
1301 return x
1302
1303 cpdef ModuleElement _sub_(self, ModuleElement right):
1304 r"""
1305 EXAMPLES::
1306
1307 sage: K.<a> = NumberField(x^3 + 2)
1308 sage: (a/2) - (a + 3) # indirect doctest
1309 -1/2*a - 3
1310 """
1311 cdef NumberFieldElement x
1312 cdef NumberFieldElement _right = right
1313 x = self._new()
1314 ZZ_mul(x.__denominator, self.__denominator, _right.__denominator)
1315 cdef ZZX_c t1, t2
1316 ZZX_mul_ZZ(t1, self.__numerator, _right.__denominator)
1317 ZZX_mul_ZZ(t2, _right.__numerator, self.__denominator)
1318 ZZX_sub(x.__numerator, t1, t2)
1319 x._reduce_c_()
1320 return x
1321
1322 cpdef RingElement _mul_(self, RingElement right):
1323 """
1324 Returns the product of self and other as elements of a number
1325 field.
1326
1327 EXAMPLES::
1328
1329 sage: C.<zeta12>=CyclotomicField(12)
1330 sage: zeta12*zeta12^11
1331 1
1332 sage: G.<a> = NumberField(x^3 + 2/3*x + 1)
1333 sage: a^3 # indirect doctest
1334 -2/3*a - 1
1335 sage: a^3+a # indirect doctest
1336 1/3*a - 1
1337 """
1338 cdef NumberFieldElement x
1339 cdef NumberFieldElement _right = right
1340 cdef ZZX_c temp
1341 cdef ZZ_c temp1
1342 x = self._new()
1343 _sig_on
1344 # MulMod doesn't handle non-monic polynomials.
1345 # Therefore, we handle the non-monic case entirely separately.
1346
1347 if ZZ_IsOne(ZZX_LeadCoeff(self.__fld_numerator.x)):
1348 ZZ_mul(x.__denominator, self.__denominator, _right.__denominator)
1349 ZZX_MulMod(x.__numerator, self.__numerator, _right.__numerator, self.__fld_numerator.x)
1350 else:
1351 ZZ_mul(x.__denominator, self.__denominator, _right.__denominator)
1352 ZZX_mul(x.__numerator, self.__numerator, _right.__numerator)
1353 if ZZX_deg(x.__numerator) >= ZZX_deg(self.__fld_numerator.x):
1354 ZZX_mul_ZZ( x.__numerator, x.__numerator, self.__fld_denominator.x )
1355 ZZX_mul_ZZ( temp, self.__fld_numerator.x, x.__denominator )
1356 ZZ_power(temp1,ZZX_LeadCoeff(temp),ZZX_deg(x.__numerator)-ZZX_deg(self.__fld_numerator.x)+1)
1357 ZZX_PseudoRem(x.__numerator, x.__numerator, temp)
1358 ZZ_mul(x.__denominator, x.__denominator, self.__fld_denominator.x)
1359 ZZ_mul(x.__denominator, x.__denominator, temp1)
1360 _sig_off
1361 x._reduce_c_()
1362 return x
1363
1364 #NOTES: In LiDIA, they build a multiplication table for the
1365 #number field, so it's not necessary to reduce modulo the
1366 #defining polynomial every time:
1367 # src/number_fields/algebraic_num/order.cc: compute_table
1368 # but asymptotically fast poly multiplication means it's
1369 # actually faster to *not* build a table!?!
1370
1371 cpdef RingElement _div_(self, RingElement right):
1372 """
1373 Returns the quotient of self and other as elements of a number
1374 field.
1375
1376 EXAMPLES::
1377
1378 sage: C.<I>=CyclotomicField(4)
1379 sage: 1/I # indirect doctest
1380 -I
1381 sage: I/0 # indirect doctest
1382 Traceback (most recent call last):
1383 ...
1384 ZeroDivisionError: rational division by zero
1385
1386 ::
1387
1388 sage: G.<a> = NumberField(x^3 + 2/3*x + 1)
1389 sage: a/a # indirect doctest
1390 1
1391 sage: 1/a # indirect doctest
1392 -a^2 - 2/3
1393 sage: a/0 # indirect doctest
1394 Traceback (most recent call last):
1395 ...
1396 ZeroDivisionError: Number field element division by zero
1397 """
1398 cdef NumberFieldElement x
1399 cdef NumberFieldElement _right = right
1400 cdef ZZX_c inv_num
1401 cdef ZZ_c inv_den
1402 cdef ZZX_c temp
1403 cdef ZZ_c temp1
1404 if not _right:
1405 raise ZeroDivisionError, "Number field element division by zero"
1406 x = self._new()
1407 _sig_on
1408 _right._invert_c_(&inv_num, &inv_den)
1409 if ZZ_IsOne(ZZX_LeadCoeff(self.__fld_numerator.x)):
1410 ZZ_mul(x.__denominator, self.__denominator, inv_den)
1411 ZZX_MulMod(x.__numerator, self.__numerator, inv_num, self.__fld_numerator.x)
1412 else:
1413 ZZ_mul(x.__denominator, self.__denominator, inv_den)
1414 ZZX_mul(x.__numerator, self.__numerator, inv_num)
1415 if ZZX_deg(x.__numerator) >= ZZX_deg(self.__fld_numerator.x):
1416 ZZX_mul_ZZ( x.__numerator, x.__numerator, self.__fld_denominator.x )
1417 ZZX_mul_ZZ( temp, self.__fld_numerator.x, x.__denominator )
1418 ZZ_power(temp1,ZZX_LeadCoeff(temp),ZZX_deg(x.__numerator)-ZZX_deg(self.__fld_numerator.x)+1)
1419 ZZX_PseudoRem(x.__numerator, x.__numerator, temp)
1420 ZZ_mul(x.__denominator, x.__denominator, self.__fld_denominator.x)
1421 ZZ_mul(x.__denominator, x.__denominator, temp1)
1422 x._reduce_c_()
1423 _sig_off
1424 return x
1425
1426 def __floordiv__(self, other):
1427 """
1428 Return the quotient of self and other. Since these are field
1429 elements the floor division is exactly the same as usual division.
1430
1431 EXAMPLES::
1432
1433 sage: m.<b> = NumberField(x^4 + x^2 + 2/3)
1434 sage: c = (1+b) // (1-b); c
1435 3/4*b^3 + 3/4*b^2 + 3/2*b + 1/2
1436 sage: (1+b) / (1-b) == c
1437 True
1438 sage: c * (1-b)
1439 b + 1
1440 """
1441 return self / other
1442
1443 def __nonzero__(self):
1444 """
1445 Return True if this number field element is nonzero.
1446
1447 EXAMPLES::
1448
1449 sage: m.<b> = CyclotomicField(17)
1450 sage: m(0).__nonzero__()
1451 False
1452 sage: b.__nonzero__()
1453 True
1454
1455 Nonzero is used by the bool command::
1456
1457 sage: bool(b + 1)
1458 True
1459 sage: bool(m(0))
1460 False
1461 """
1462 return not IsZero_ZZX(self.__numerator)
1463
1464 cpdef ModuleElement _neg_(self):
1465 r"""
1466 EXAMPLE::
1467
1468 sage: K.<a> = NumberField(x^3 + 2)
1469 sage: -a # indirect doctest
1470 -a
1471 """
1472 cdef NumberFieldElement x
1473 x = self._new()
1474 ZZX_mul_long(x.__numerator, self.__numerator, -1)
1475 x.__denominator = self.__denominator
1476 return x
1477
1478 def __copy__(self):
1479 r"""
1480 EXAMPLE::
1481
1482 sage: K.<a> = NumberField(x^3 + 2)
1483 sage: b = copy(a)
1484 sage: b == a
1485 True
1486 sage: b is a
1487 False
1488 """
1489 cdef NumberFieldElement x
1490 x = self._new()
1491 x.__numerator = self.__numerator
1492 x.__denominator = self.__denominator
1493 return x
1494
1495 def __int__(self):
1496 """
1497 Attempt to convert this number field element to a Python integer,
1498 if possible.
1499
1500 EXAMPLES::
1501
1502 sage: C.<I>=CyclotomicField(4)
1503 sage: int(1/I)
1504 Traceback (most recent call last):
1505 ...
1506 TypeError: cannot coerce nonconstant polynomial to int
1507 sage: int(I*I)
1508 -1
1509
1510 ::
1511
1512 sage: K.<a> = NumberField(x^10 - x - 1)
1513 sage: int(a)
1514 Traceback (most recent call last):
1515 ...
1516 TypeError: cannot coerce nonconstant polynomial to int
1517 sage: int(K(9390283))
1518 9390283
1519
1520 The semantics are like in Python, so the value does not have to
1521 preserved.
1522
1523 ::
1524
1525 sage: int(K(393/29))
1526 13
1527 """
1528 return int(self.polynomial())
1529
1530 def __long__(self):
1531 """
1532 Attempt to convert this number field element to a Python long, if
1533 possible.
1534
1535 EXAMPLES::
1536
1537 sage: K.<a> = NumberField(x^10 - x - 1)
1538 sage: long(a)
1539 Traceback (most recent call last):
1540 ...
1541 TypeError: cannot coerce nonconstant polynomial to long
1542 sage: long(K(1234))
1543 1234L
1544
1545 The value does not have to be preserved, in the case of fractions.
1546
1547 ::
1548
1549 sage: long(K(393/29))
1550 13L
1551 """
1552 return long(self.polynomial())
1553
1554 cdef void _invert_c_(self, ZZX_c *num, ZZ_c *den):
1555 """
1556 Computes the numerator and denominator of the multiplicative
1557 inverse of this element.
1558
1559 Suppose that this element is x/d and the parent mod'ding polynomial
1560 is M/D. The NTL function XGCD( r, s, t, a, b ) computes r,s,t such
1561 that `r=s*a+t*b`. We compute XGCD( r, s, t, x\*D, M\*d )
1562 and set num=s\*D\*d den=r
1563
1564 EXAMPLES:
1565
1566 I'd love to, but since we are dealing with c-types, I
1567 can't at this level. Check __invert__ for doc-tests that rely
1568 on this functionality.
1569 """
1570 cdef ZZX_c t # unneeded except to be there
1571 cdef ZZX_c a, b
1572 ZZX_mul_ZZ( a, self.__numerator, self.__fld_denominator.x )
1573 ZZX_mul_ZZ( b, self.__fld_numerator.x, self.__denominator )
1574 ZZX_XGCD( den[0], num[0], t, a, b, 1 )
1575 ZZX_mul_ZZ( num[0], num[0], self.__fld_denominator.x )
1576 ZZX_mul_ZZ( num[0], num[0], self.__denominator )
1577
1578 def __invert__(self):
1579 """
1580 Returns the multiplicative inverse of self in the number field.
1581
1582 EXAMPLES::
1583
1584 sage: C.<I>=CyclotomicField(4)
1585 sage: ~I
1586 -I
1587 sage: (2*I).__invert__()
1588 -1/2*I
1589 """
1590 if IsZero_ZZX(self.__numerator):
1591 raise ZeroDivisionError
1592 cdef NumberFieldElement x
1593 x = self._new()
1594 self._invert_c_(&x.__numerator, &x.__denominator)
1595 x._reduce_c_()
1596 return x
1597
1598 def _integer_(self, Z=None):
1599 """
1600 Returns an integer if this element is actually an integer.
1601
1602 EXAMPLES::
1603
1604 sage: C.<I>=CyclotomicField(4)
1605 sage: (~I)._integer_()
1606 Traceback (most recent call last):
1607 ...
1608 TypeError: Unable to coerce -I to an integer
1609 sage: (2*I*I)._integer_()
1610 -2
1611 """
1612 if ZZX_deg(self.__numerator) >= 1:
1613 raise TypeError, "Unable to coerce %s to an integer"%self
1614 return ZZ(self._rational_())
1615
1616 def _rational_(self):
1617 """
1618 Returns a rational number if this element is actually a rational
1619 number.
1620
1621 EXAMPLES::
1622
1623 sage: C.<I>=CyclotomicField(4)
1624 sage: (~I)._rational_()
1625 Traceback (most recent call last):
1626 ...
1627 TypeError: Unable to coerce -I to a rational
1628 sage: (I*I/2)._rational_()
1629 -1/2
1630 """
1631 if ZZX_deg(self.__numerator) >= 1:
1632 raise TypeError, "Unable to coerce %s to a rational"%self
1633 cdef Integer num
1634 num = PY_NEW(Integer)
1635 ZZX_getitem_as_mpz(&num.value, &self.__numerator, 0)
1636 return num / (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1637
1638 def _symbolic_(self, SR):
1639 """
1640 If an embedding into CC is specified, then a representation of this
1641 element can be made in the symbolic ring (assuming roots of the
1642 minimal polynomial can be found symbolically).
1643
1644 EXAMPLES::
1645
1646 sage: K.<a> = QuadraticField(2)
1647 sage: SR(a) # indirect doctest
1648 sqrt(2)
1649 sage: SR(3*a-5) # indirect doctest
1650 3*sqrt(2) - 5
1651 sage: K.<a> = QuadraticField(2, embedding=-1.4)
1652 sage: SR(a) # indirect doctest
1653 -sqrt(2)
1654 sage: K.<a> = NumberField(x^2 - 2)
1655 sage: SR(a) # indirect doctest
1656 Traceback (most recent call last):
1657 ...
1658 TypeError: An embedding into RR or CC must be specified.
1659
1660 Now a more complicated example::
1661
1662 sage: K.<a> = NumberField(x^3 + x - 1, embedding=0.68)
1663 sage: b = SR(a); b # indirect doctest
1664 1/3*(3*(1/18*sqrt(3)*sqrt(31) + 1/2)^(2/3) - 1)/(1/18*sqrt(3)*sqrt(31) + 1/2)^(1/3)
1665
1666 sage: (b^3 + b - 1).simplify_radical()
1667 0
1668
1669 Make sure we got the right one::
1670
1671 sage: CC(a)
1672 0.682327803828019
1673 sage: CC(b)
1674 0.682327803828019
1675
1676 Special case for cyclotomic fields::
1677
1678 sage: K.<zeta> = CyclotomicField(19)
1679 sage: SR(zeta) # indirect doctest
1680 e^(2/19*I*pi)
1681 sage: CC(zeta)
1682 0.945817241700635 + 0.324699469204683*I
1683 sage: CC(SR(zeta))
1684 0.945817241700635 + 0.324699469204683*I
1685
1686 sage: SR(zeta^5 + 2)
1687 e^(10/19*I*pi) + 2
1688
1689 For degree greater than 5, sometimes Galois theory prevents a
1690 closed-form solution. In this case, a numerical approximation
1691 is used::
1692
1693 sage: K.<a> = NumberField(x^5-x+1, embedding=-1)
1694 sage: SR(a)
1695 -1.1673040153
1696
1697 ::
1698
1699 sage: K.<a> = NumberField(x^6-x^3-1, embedding=1)
1700 sage: SR(a)
1701 1/2*(sqrt(5) + 1)^(1/3)*2^(2/3)
1702 """
1703 if self.__symbolic is None:
1704
1705 K = self._parent.fraction_field()
1706
1707 gen = K.gen()
1708 if not self is gen:
1709 try:
1710 # share the hard work...
1711 gen_image = gen._symbolic_(SR)
1712 self.__symbolic = self.polynomial()(gen_image)
1713 return self.__symbolic
1714 except TypeError:
1715 pass # we may still be able to do this particular element...
1716
1717 embedding = K.specified_complex_embedding()
1718 if embedding is None:
1719 raise TypeError, "An embedding into RR or CC must be specified."
1720
1721 if isinstance(K, number_field.NumberField_cyclotomic):
1722 # solution by radicals may be difficult, but we have a closed form
1723 from sage.all import exp, I, pi, ComplexField, RR
1724 CC = ComplexField(53)
1725 two_pi_i = 2 * pi * I
1726 k = ( K._n()*CC(K.gen()).log() / CC(two_pi_i) ).real().round() # n ln z / (2 pi i)
1727 gen_image = exp(k*two_pi_i/K._n())
1728 if self is gen:
1729 self.__symbolic = gen_image
1730 else:
1731 self.__symbolic = self.polynomial()(gen_image)
1732 else:
1733 # try to solve the minpoly and choose the closest root
1734 poly = self.minpoly()
1735 roots = []
1736 var = SR(poly.variable_name())
1737 for soln in SR(poly).solve(var, to_poly_solve=True):
1738 if soln.lhs() == var:
1739 roots.append(soln.rhs())
1740 if len(roots) != poly.degree():
1741 raise TypeError, "Unable to solve by radicals."
1742 from number_field_morphisms import matching_root
1743 from sage.rings.complex_field import ComplexField
1744 gen_image = matching_root(roots, self, ambient_field=ComplexField(53), margin=2)
1745 if gen_image is not None:
1746 self.__symbolic = gen_image
1747 else:
1748 # should be rare, e.g. if there is insufficient precision
1749 raise TypeError, "Unable to determine which root in SR is this element."
1750
1751 return self.__symbolic
1752
1753 def galois_conjugates(self, K):
1754 r"""
1755 Return all Gal(Qbar/Q)-conjugates of this number field element in
1756 the field K.
1757
1758 EXAMPLES:
1759
1760 In the first example the conjugates are obvious::
1761
1762 sage: K.<a> = NumberField(x^2 - 2)
1763 sage: a.galois_conjugates(K)
1764 [a, -a]
1765 sage: K(3).galois_conjugates(K)
1766 [3]
1767
1768 In this example the field is not Galois, so we have to pass to an
1769 extension to obtain the Galois conjugates.
1770
1771 ::
1772
1773 sage: K.<a> = NumberField(x^3 - 2)
1774 sage: c = a.galois_conjugates(K); c
1775 [a]
1776 sage: K.<a> = NumberField(x^3 - 2)
1777 sage: c = a.galois_conjugates(K.galois_closure('a1')); c
1778 [1/84*a1^4 + 13/42*a1, -1/252*a1^4 - 55/126*a1, -1/126*a1^4 + 8/63*a1]
1779 sage: c[0]^3
1780 2
1781 sage: parent(c[0])
1782 Number Field in a1 with defining polynomial x^6 + 40*x^3 + 1372
1783 sage: parent(c[0]).is_galois()
1784 True
1785
1786 There is only one Galois conjugate of `\sqrt[3]{2}` in
1787 `\QQ(\sqrt[3]{2})`.
1788
1789 ::
1790
1791 sage: a.galois_conjugates(K)
1792 [a]
1793
1794 Galois conjugates of `\sqrt[3]{2}` in the field
1795 `\QQ(\zeta_3,\sqrt[3]{2})`::
1796
1797 sage: L.<a> = CyclotomicField(3).extension(x^3 - 2)
1798 sage: a.galois_conjugates(L)
1799 [a, (-zeta3 - 1)*a, zeta3*a]
1800 """
1801 f = self.absolute_minpoly()
1802 g = K['x'](f)
1803 return [a for a,_ in g.roots()]
1804
1805 def conjugate(self):
1806 """
1807 Return the complex conjugate of the number field element.
1808 Currently, this is implemented for cyclotomic fields and quadratic
1809 extensions of Q. It seems likely that there are other number fields
1810 for which the idea of a conjugate would be easy to compute.
1811
1812 EXAMPLES::
1813
1814 sage: k.<I> = QuadraticField(-1)
1815 sage: I.conjugate()
1816 -I
1817 sage: (I/(1+I)).conjugate()
1818 -1/2*I + 1/2
1819 sage: z6=CyclotomicField(6).gen(0)
1820 sage: (2*z6).conjugate()
1821 -2*zeta6 + 2
1822 sage: K.<j,b> = QQ[sqrt(-1), sqrt(2)]
1823 sage: j.conjugate()
1824 Traceback (most recent call last):
1825 ...
1826 NotImplementedError: complex conjugation is not implemented (or doesn't make sense).
1827
1828 ::
1829
1830 sage: K.<b> = NumberField(x^3 - 2)
1831 sage: b.conjugate()
1832 Traceback (most recent call last):
1833 ...
1834 NotImplementedError: complex conjugation is not implemented (or doesn't make sense).
1835 """
1836 coeffs = self.number_field().absolute_polynomial().list()
1837 if len(coeffs) == 3 and coeffs[2] == 1 and coeffs[1] == 0:
1838 # polynomial looks like x^2+d
1839 # i.e. we live in a quadratic extension of QQ
1840 if coeffs[0] > 0:
1841 gen = self.number_field().gen()
1842 return self.polynomial()(-gen)
1843 else:
1844 return self
1845 elif isinstance(self.number_field(), number_field.NumberField_cyclotomic):
1846 # We are in a cyclotomic field
1847 # Replace the generator zeta_n with (zeta_n)^(n-1)
1848 gen = self.number_field().gen()
1849 return self.polynomial()(gen ** (gen.multiplicative_order()-1))
1850 else:
1851 raise NotImplementedError, "complex conjugation is not implemented (or doesn't make sense)."
1852
1853 def polynomial(self, var='x'):
1854 """
1855 Return the underlying polynomial corresponding to this number field
1856 element.
1857
1858 The resulting polynomial is currently *not* cached.
1859
1860 EXAMPLES::
1861
1862 sage: K.<a> = NumberField(x^5 - x - 1)
1863 sage: f = (-2/3 + 1/3*a)^4; f
1864 1/81*a^4 - 8/81*a^3 + 8/27*a^2 - 32/81*a + 16/81
1865 sage: g = f.polynomial(); g
1866 1/81*x^4 - 8/81*x^3 + 8/27*x^2 - 32/81*x + 16/81
1867 sage: parent(g)
1868 Univariate Polynomial Ring in x over Rational Field
1869
1870 Note that the result of this function is not cached (should this be
1871 changed?)::
1872
1873 sage: g is f.polynomial()
1874 False
1875 """
1876 return QQ[var](self._coefficients())
1877
1878 def __hash__(self):
1879 """
1880 Return hash of this number field element, which is just the
1881 hash of the underlying polynomial.
1882
1883 EXAMPLE::
1884
1885 sage: K.<b> = NumberField(x^3 - 2)
1886 sage: hash(b^2 + 1) == hash((b^2 + 1).polynomial()) # indirect doctest
1887 True
1888 """
1889 return hash(self.polynomial())
1890
1891 def _coefficients(self):
1892 """
1893 Return the coefficients of the underlying polynomial corresponding
1894 to this number field element.
1895
1896 OUTPUT:
1897
1898 - a list whose length corresponding to the degree of this
1899 element written in terms of a generator.
1900
1901 EXAMPLES:
1902
1903 sage: K.<b> = NumberField(x^3 - 2)
1904 sage: (b^2 + 1)._coefficients()
1905 [1, 0, 1]
1906 """
1907 coeffs = []
1908 cdef Integer den = (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1909 cdef Integer numCoeff
1910 cdef int i
1911 for i from 0 <= i <= ZZX_deg(self.__numerator):
1912 numCoeff = PY_NEW(Integer)
1913 ZZX_getitem_as_mpz(&numCoeff.value, &self.__numerator, i)
1914 coeffs.append( numCoeff / den )
1915 return coeffs
1916
1917 cdef void _ntl_coeff_as_mpz(self, mpz_t* z, long i):
1918 if i > ZZX_deg(self.__numerator):
1919 mpz_set_ui(z[0], 0)
1920 else:
1921 ZZX_getitem_as_mpz(z, &self.__numerator, i)
1922
1923 cdef void _ntl_denom_as_mpz(self, mpz_t* z):
1924 cdef Integer denom = (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1925 mpz_set(z[0], denom.value)
1926
1927 def denominator(self):
1928 """
1929 Return the denominator of this element, which is by definition the
1930 denominator of the corresponding polynomial representation. I.e.,
1931 elements of number fields are represented as a polynomial (in
1932 reduced form) modulo the modulus of the number field, and the
1933 denominator is the denominator of this polynomial.
1934
1935 EXAMPLES::
1936
1937 sage: K.<z> = CyclotomicField(3)
1938 sage: a = 1/3 + (1/5)*z
1939 sage: print a.denominator()
1940 15
1941 """
1942 return (<IntegerRing_class>ZZ)._coerce_ZZ(&self.__denominator)
1943
1944 def _set_multiplicative_order(self, n):
1945 """
1946 Set the multiplicative order of this number field element.
1947
1948 .. warning::
1949
1950 Use with caution - only for internal use! End users should
1951 never call this unless they have a very good reason to do
1952 so.
1953
1954 EXAMPLES::
1955
1956 sage: K.<a> = NumberField(x^2 + x + 1)
1957 sage: a._set_multiplicative_order(3)
1958 sage: a.multiplicative_order()
1959 3
1960
1961 You can be evil with this so be careful. That's why the function
1962 name begins with an underscore.
1963
1964 ::
1965
1966 sage: a._set_multiplicative_order(389)
1967 sage: a.multiplicative_order()
1968 389
1969 """
1970 self.__multiplicative_order = n
1971
1972 def multiplicative_order(self):
1973 """
1974 Return the multiplicative order of this number field element.
1975
1976 EXAMPLES::
1977
1978 sage: K.<z> = CyclotomicField(5)
1979 sage: z.multiplicative_order()
1980 5
1981 sage: (-z).multiplicative_order()
1982 10
1983 sage: (1+z).multiplicative_order()
1984 +Infinity
1985
1986 sage: x = polygen(QQ)
1987 sage: K.<a>=NumberField(x^40 - x^20 + 4)
1988 sage: u = 1/4*a^30 + 1/4*a^10 + 1/2
1989 sage: u.multiplicative_order()
1990 6
1991 sage: a.multiplicative_order()
1992 +Infinity
1993
1994 An example in a relative extension::
1995
1996 sage: K.<a, b> = NumberField([x^2 + x + 1, x^2 - 3])
1997 sage: z = (a - 1)*b/3
1998 sage: z.multiplicative_order()
1999 12
2000 sage: z^12==1 and z^6!=1 and z^4!=1
2001 True
2002
2003 """
2004 if self.__multiplicative_order is not None:
2005 return self.__multiplicative_order
2006
2007 one = self.number_field().one_element()
2008 infinity = sage.rings.infinity.infinity
2009
2010 if self == one:
2011 self.__multiplicative_order = ZZ(1)
2012 return self.__multiplicative_order
2013 if self == -one:
2014 self.__multiplicative_order = ZZ(2)
2015 return self.__multiplicative_order
2016
2017 if isinstance(self.number_field(), number_field.NumberField_cyclotomic):
2018 t = self.number_field()._multiplicative_order_table()
2019 f = self.polynomial()
2020 if t.has_key(f):
2021 self.__multiplicative_order = t[f]
2022 return self.__multiplicative_order
2023 else:
2024 self.__multiplicative_order = sage.rings.infinity.infinity
2025 return self.__multiplicative_order
2026
2027 if self.is_rational_c() or not self.is_integral() or not self.norm() ==1:
2028 self.__multiplicative_order = infinity
2029 return self.__multiplicative_order
2030
2031 # Now we have a unit of norm 1, and check if it is a root of unity
2032
2033 n = self.number_field().zeta_order()
2034 if not self**n ==1:
2035 self.__multiplicative_order = infinity
2036 return self.__multiplicative_order
2037 from sage.groups.generic import order_from_multiple
2038 self.__multiplicative_order = order_from_multiple(self,n,operation='*')
2039 return self.__multiplicative_order
2040
2041 def additive_order(self):
2042 r"""
2043 Return the additive order of this element (i.e. infinity if
2044 self != 0, 1 if self == 0)
2045
2046 EXAMPLES::
2047
2048 sage: K.<u> = NumberField(x^4 - 3*x^2 + 3)
2049 sage: u.additive_order()
2050 +Infinity
2051 sage: K(0).additive_order()
2052 1
2053 sage: K.ring_of_integers().characteristic() # implicit doctest
2054 0
2055 """
2056 if self == 0: return 1
2057 else: return sage.rings.infinity.infinity
2058
2059 cdef bint is_rational_c(self):
2060 return ZZX_deg(self.__numerator) == 0
2061
2062 def trace(self, K=None):
2063 """
2064 Return the absolute or relative trace of this number field
2065 element.
2066
2067 If K is given then K must be a subfield of the parent L of self, in
2068 which case the trace is the relative trace from L to K. In all
2069 other cases, the trace is the absolute trace down to QQ.
2070
2071 EXAMPLES::
2072
2073 sage: K.<a> = NumberField(x^3 -132/7*x^2 + x + 1); K
2074 Number Field in a with defining polynomial x^3 - 132/7*x^2 + x + 1
2075 sage: a.trace()
2076 132/7
2077 sage: (a+1).trace() == a.trace() + 3
2078 True
2079
2080 If we are in an order, the trace is an integer::
2081
2082 sage: K.<zeta> = CyclotomicField(17)
2083 sage: R = K.ring_of_integers()
2084 sage: R(zeta).trace().parent()
2085 Integer Ring
2086
2087 TESTS::
2088
2089 sage: F.<z> = CyclotomicField(5) ; t = 3*z**3 + 4*z**2 + 2
2090 sage: t.trace(F)
2091 3*z^3 + 4*z^2 + 2
2092 """
2093 if K is None:
2094 trace = self._pari_('x').trace()
2095 return QQ(trace) if self._parent.is_field() else ZZ(trace)
2096 return self.matrix(K).trace()
2097
2098 def norm(self, K=None):
2099 """
2100 Return the absolute or relative norm of this number field element.
2101
2102 If K is given then K must be a subfield of the parent L of self, in
2103 which case the norm is the relative norm from L to K. In all other
2104 cases, the norm is the absolute norm down to QQ.
2105
2106 EXAMPLES::
2107
2108 sage: K.<a> = NumberField(x^3 + x^2 + x - 132/7); K
2109 Number Field in a with defining polynomial x^3 + x^2 + x - 132/7
2110 sage: a.norm()
2111 132/7
2112 sage: factor(a.norm())
2113 2^2 * 3 * 7^-1 * 11
2114 sage: K(0).norm()
2115 0
2116
2117 Some complicated relatives norms in a tower of number fields.
2118
2119 ::
2120
2121 sage: K.<a,b,c> = NumberField([x^2 + 1, x^2 + 3, x^2 + 5])
2122 sage: L = K.base_field(); M = L.base_field()
2123 sage: a.norm()
2124 1
2125 sage: a.norm(L)
2126 1
2127 sage: a.norm(M)
2128 1
2129 sage: a
2130 a
2131 sage: (a+b+c).norm()
2132 121
2133 sage: (a+b+c).norm(L)
2134 2*c*b - 7
2135 sage: (a+b+c).norm(M)
2136 -11
2137
2138 We illustrate that norm is compatible with towers::
2139
2140 sage: z = (a+b+c).norm(L); z.norm(M)
2141 -11
2142
2143 If we are in an order, the norm is an integer::
2144
2145 sage: K.<a> = NumberField(x^3-2)
2146 sage: a.norm().parent()
2147 Rational Field
2148 sage: R = K.ring_of_integers()
2149 sage: R(a).norm().parent()
2150 Integer Ring
2151
2152 TESTS::
2153
2154 sage: F.<z> = CyclotomicField(5)
2155 sage: t = 3*z**3 + 4*z**2 + 2
2156 sage: t.norm(F)
2157 3*z^3 + 4*z^2 + 2
2158 """
2159 if K is None:
2160 norm = self._pari_('x').norm()
2161 return QQ(norm) if self._parent.is_field() else ZZ(norm)
2162 return self.matrix(K).determinant()
2163
2164 def vector(self):
2165 """
2166 Return vector representation of self in terms of the basis for the
2167 ambient number field.
2168
2169 EXAMPLES::
2170
2171 sage: K.<a> = NumberField(x^2 + 1)
2172 sage: (2/3*a - 5/6).vector()
2173 (-5/6, 2/3)
2174 sage: (-5/6, 2/3)
2175 (-5/6, 2/3)
2176 sage: O = K.order(2*a)
2177 sage: (O.1).vector()
2178 (0, 2)
2179 sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3])
2180 sage: (a + b).vector()
2181 (b, 1)
2182 sage: O = K.order([a,b])
2183 sage: (O.1).vector()
2184 (-b, 1)
2185 sage: (O.2).vector()
2186 (1, -b)
2187 """
2188 return self.number_field().relative_vector_space()[2](self)
2189
2190 def charpoly(self, var='x'):
2191 r"""
2192 Return the characteristic polynomial of this number field element.
2193
2194 EXAMPLE::
2195
2196 sage: K.<a> = NumberField(x^3 + 7)
2197 sage: a.charpoly()
2198 x^3 + 7
2199 sage: K(1).charpoly()
2200 x^3 - 3*x^2 + 3*x - 1
2201 """
2202 raise NotImplementedError, "Subclasses of NumberFieldElement must override charpoly()"
2203
2204 def minpoly(self, var='x'):
2205 """
2206 Return the minimal polynomial of this number field element.
2207
2208 EXAMPLES::
2209
2210 sage: K.<a> = NumberField(x^2+3)
2211 sage: a.minpoly('x')
2212 x^2 + 3
2213 sage: R.<X> = K['X']
2214 sage: L.<b> = K.extension(X^2-(22 + a))
2215 sage: b.minpoly('t')
2216 t^2 - a - 22
2217 sage: b.absolute_minpoly('t')
2218 t^4 - 44*t^2 + 487
2219 sage: b^2 - (22+a)
2220 0
2221 """
2222 return self.charpoly(var).radical() # square free part of charpoly
2223
2224 def is_integral(self):
2225 r"""
2226 Determine if a number is in the ring of integers of this number
2227 field.
2228
2229 EXAMPLES::
2230
2231 sage: K.<a> = NumberField(x^2 + 23)
2232 sage: a.is_integral()
2233 True
2234 sage: t = (1+a)/2
2235 sage: t.is_integral()
2236 True
2237 sage: t.minpoly()
2238 x^2 - x + 6
2239 sage: t = a/2
2240 sage: t.is_integral()
2241 False
2242 sage: t.minpoly()
2243 x^2 + 23/4
2244
2245 An example in a relative extension::
2246
2247 sage: K.<a,b> = NumberField([x^2+1, x^2+3])
2248 sage: (a+b).is_integral()
2249 True
2250 sage: ((a-b)/2).is_integral()
2251 False
2252 """
2253 return all([a in ZZ for a in self.absolute_minpoly()])
2254
2255 def matrix(self, base=None):
2256 r"""
2257 If base is None, return the matrix of right multiplication by the
2258 element on the power basis `1, x, x^2, \ldots, x^{d-1}` for
2259 the number field. Thus the *rows* of this matrix give the images of
2260 each of the `x^i`.
2261
2262 If base is not None, then base must be either a field that embeds
2263 in the parent of self or a morphism to the parent of self, in which
2264 case this function returns the matrix of multiplication by self on
2265 the power basis, where we view the parent field as a field over
2266 base.
2267
2268 INPUT:
2269
2270
2271 - ``base`` - field or morphism
2272
2273
2274 EXAMPLES:
2275
2276 Regular number field::
2277
2278 sage: K.<a> = NumberField(QQ['x'].0^3 - 5)
2279 sage: M = a.matrix(); M
2280 [0 1 0]
2281 [0 0 1]
2282 [5 0 0]
2283 sage: M.base_ring() is QQ
2284 True
2285
2286 Relative number field::
2287
2288 sage: L.<b> = K.extension(K['x'].0^2 - 2)
2289 sage: M = b.matrix(); M
2290 [0 1]
2291 [2 0]
2292 sage: M.base_ring() is K
2293 True
2294
2295 Absolute number field::
2296
2297 sage: M = L.absolute_field('c').gen().matrix(); M
2298 [ 0 1 0 0 0 0]
2299 [ 0 0 1 0 0 0]
2300 [ 0 0 0 1 0 0]
2301 [ 0 0 0 0 1 0]
2302 [ 0 0 0 0 0 1]
2303 [-17 -60 -12 -10 6 0]
2304 sage: M.base_ring() is QQ
2305 True
2306
2307 More complicated relative number field::
2308
2309 sage: L.<b> = K.extension(K['x'].0^2 - a); L
2310 Number Field in b with defining polynomial x^2 - a over its base field
2311 sage: M = b.matrix(); M
2312 [0 1]
2313 [a 0]
2314 sage: M.base_ring() is K
2315 True
2316
2317 An example where we explicitly give the subfield or the embedding::
2318
2319 sage: K.<a> = NumberField(x^4 + 1); L.<a2> = NumberField(x^2 + 1)
2320 sage: a.matrix(L)
2321 [ 0 1]
2322 [a2 0]
2323
2324 Notice that if we compute all embeddings and choose a different
2325 one, then the matrix is changed as it should be::
2326
2327 sage: v = L.embeddings(K)
2328 sage: a.matrix(v[1])
2329 [ 0 1]
2330 [-a2 0]
2331
2332 The norm is also changed::
2333
2334 sage: a.norm(v[1])
2335 a2
2336 sage: a.norm(v[0])
2337 -a2
2338
2339 TESTS::
2340
2341 sage: F.<z> = CyclotomicField(5) ; t = 3*z**3 + 4*z**2 + 2
2342 sage: t.matrix(F)
2343 [3*z^3 + 4*z^2 + 2]
2344 """
2345 if base is not None:
2346 if number_field.is_NumberField(base):
2347 return self._matrix_over_base(base)
2348 else:
2349 return self._matrix_over_base_morphism(base)
2350 # Multiply each power of field generator on
2351 # the left by this element; make matrix
2352 # whose rows are the coefficients of the result,
2353 # and transpose.
2354 if self.__matrix is None:
2355 K = self.number_field()
2356 v = []
2357 x = K.gen()
2358 a = K(1)
2359 d = K.relative_degree()
2360 for n in range(d):
2361 v += (a*self).list()
2362 a *= x
2363 k = K.base_ring()
2364 import sage.matrix.matrix_space
2365 M = sage.matrix.matrix_space.MatrixSpace(k, d)
2366 self.__matrix = M(v)
2367 return self.__matrix
2368
2369 def valuation(self, P):
2370 """
2371 Returns the valuation of self at a given prime ideal P.
2372
2373 INPUT:
2374
2375
2376 - ``P`` - a prime ideal of the parent of self
2377
2378
2379 EXAMPLES::
2380
2381 sage: R.<x> = QQ[]
2382 sage: K.<a> = NumberField(x^4+3*x^2-17)
2383 sage: P = K.ideal(61).factor()[0][0]
2384 sage: b = a^2 + 30
2385 sage: b.valuation(P)
2386 1
2387 sage: type(b.valuation(P))
2388 <type 'sage.rings.integer.Integer'>
2389
2390 The function can be applied to elements in relative number fields::
2391
2392 sage: L.<b> = K.extension(x^2 - 3)
2393 sage: [L(6).valuation(P) for P in L.primes_above(2)]
2394 [4]
2395 sage: [L(6).valuation(P) for P in L.primes_above(3)]
2396 [2, 2]
2397 """
2398 from number_field_ideal import is_NumberFieldIdeal
2399 from sage.rings.infinity import infinity
2400 if not is_NumberFieldIdeal(P):
2401 if is_NumberFieldElement(P):
2402 P = self.number_field().fractional_ideal(P)
2403 else:
2404 raise TypeError, "P must be an ideal"
2405 if not P.is_prime():
2406 # We always check this because it caches the pari prime representation of this ideal.
2407 raise ValueError, "P must be prime"
2408 if self == 0:
2409 return infinity
2410 return Integer_sage(self.number_field()._pari_().elementval(self._pari_(), P._pari_prime))
2411
2412 def local_height(self, P, prec=None, weighted=False):
2413 r"""
2414 Returns the local height of self at a given prime ideal `P`.
2415
2416 INPUT:
2417
2418
2419 - ``P`` - a prime ideal of the parent of self
2420
2421 - ``prec`` (int) -- desired floating point precision (defult:
2422 default RealField precision).
2423
2424 - ``weighted`` (bool, default False) -- if True, apply local
2425 degree weighting.
2426
2427 OUTPUT:
2428
2429 (real) The local height of this number field element at the
2430 place `P`. If ``weighted`` is True, this is multiplied by the
2431 local degree (as required for global heights).
2432
2433 EXAMPLES::
2434
2435 sage: R.<x> = QQ[]
2436 sage: K.<a> = NumberField(x^4+3*x^2-17)
2437 sage: P = K.ideal(61).factor()[0][0]
2438 sage: b = 1/(a^2 + 30)
2439 sage: b.local_height(P)
2440 4.11087386417331
2441 sage: b.local_height(P, weighted=True)
2442 8.22174772834662
2443 sage: b.local_height(P, 200)
2444 4.1108738641733112487513891034256147463156817430812610629374
2445 sage: (b^2).local_height(P)
2446 8.22174772834662
2447 sage: (b^-1).local_height(P)
2448 0.000000000000000
2449
2450 A relative example::
2451
2452 sage: PK.<y> = K[]
2453 sage: L.<c> = NumberField(y^2 + a)
2454 sage: L(1/4).local_height(L.ideal(2, c-a+1))
2455 1.38629436111989
2456 """
2457 if self.valuation(P) >= 0: ## includes the case self=0
2458 from sage.rings.real_mpfr import RealField
2459 if prec is None:
2460 return RealField().zero_element()
2461 else:
2462 return RealField(prec).zero_element()
2463 ht = self.abs_non_arch(P,prec).log()
2464 if not weighted:
2465 return ht
2466 nP = P.residue_class_degree()*P.absolute_ramification_index()
2467 return nP*ht
2468
2469 def local_height_arch(self, i, prec=None, weighted=False):
2470 r"""
2471 Returns the local height of self at the `i`'th infinite place.
2472
2473 INPUT:
2474
2475
2476 - ``i`` (int) - an integer in ``range(r+s)`` where `(r,s)` is the
2477 signature of the parent field (so `n=r+2s` is the degree).
2478
2479 - ``prec`` (int) -- desired floating point precision (default:
2480 default RealField precision).
2481
2482 - ``weighted`` (bool, default False) -- if True, apply local
2483 degree weighting, i.e. double the value for complex places.
2484
2485 OUTPUT:
2486
2487 (real) The archimedean local height of this number field
2488 element at the `i`'th infinite place. If ``weighted`` is
2489 True, this is multiplied by the local degree (as required for
2490 global heights), i.e. 1 for real places and 2 for complex
2491 places.
2492
2493 EXAMPLES::
2494
2495 sage: R.<x> = QQ[]
2496 sage: K.<a> = NumberField(x^4+3*x^2-17)
2497 sage: [p.codomain() for p in K.places()]
2498 [Real Field with 106 bits of precision,
2499 Real Field with 106 bits of precision,
2500 Complex Field with 53 bits of precision]
2501 sage: [a.local_height_arch(i) for i in range(3)]
2502 [0.5301924545717755083366563897519,
2503 0.5301924545717755083366563897519,
2504 0.886414217456333]
2505 sage: [a.local_height_arch(i, weighted=True) for i in range(3)]
2506 [0.5301924545717755083366563897519,
2507 0.5301924545717755083366563897519,
2508 1.77282843491267]
2509
2510 A relative example::
2511
2512 sage: L.<b, c> = NumberFieldTower([x^2 - 5, x^3 + x + 3])
2513 sage: [(b + c).local_height_arch(i) for i in range(4)]
2514 [1.238223390757884911842206617439,
2515 0.02240347229957875780769746914391,
2516 0.780028961749618,
2517 1.16048938497298]
2518 """
2519 K = self.number_field()
2520 emb = K.places(prec=prec)[i]
2521 a = emb(self).abs()
2522 Kv = emb.codomain()
2523 if a <= Kv.one_element():
2524 return Kv.zero_element()
2525 ht = a.log()
2526 from sage.rings.real_mpfr import is_RealField
2527 if weighted and not is_RealField(Kv):
2528 ht*=2
2529 return ht
2530
2531 def global_height_non_arch(self, prec=None):
2532 """
2533 Returns the total non-archimedean component of the height of self.
2534
2535 INPUT:
2536
2537 - ``prec`` (int) -- desired floating point precision (default:
2538 default RealField precision).
2539
2540 OUTPUT:
2541
2542 (real) The total non-archimedean component of the height of
2543 this number field element; that is, the sum of the local
2544 heights at all finite places, weighted by the local degrees.
2545
2546 ALGORITHM:
2547
2548 An alternative formula is `\log(d)` where `d` is the norm of
2549 the denominator ideal; this is used to avoid factorization.
2550
2551 EXAMPLES::
2552
2553 sage: R.<x> = QQ[]
2554 sage: K.<a> = NumberField(x^4+3*x^2-17)
2555 sage: b = a/6
2556 sage: b.global_height_non_arch()
2557 7.16703787691222
2558
2559 Check that this is equal to the sum of the non-archimedean
2560 local heights::
2561
2562 sage: [b.local_height(P) for P in b.support()]
2563 [0.000000000000000, 0.693147180559945, 1.09861228866811, 1.09861228866811]
2564 sage: [b.local_height(P, weighted=True) for P in b.support()]
2565 [0.000000000000000, 2.77258872223978, 2.19722457733622, 2.19722457733622]
2566 sage: sum([b.local_height(P,weighted=True) for P in b.support()])
2567 7.16703787691222
2568
2569 A relative example::
2570
2571 sage: PK.<y> = K[]
2572 sage: L.<c> = NumberField(y^2 + a)
2573 sage: (c/10).global_height_non_arch()
2574 18.4206807439524
2575 """
2576 from sage.rings.real_mpfr import RealField
2577 if prec is None:
2578 R = RealField()
2579 else:
2580 R = RealField(prec)
2581 if self.is_zero():
2582 return R.zero_element()
2583 return R(self.denominator_ideal().absolute_norm()).log()
2584
2585 def global_height_arch(self, prec=None):
2586 """
2587 Returns the total archimedean component of the height of self.
2588
2589 INPUT:
2590
2591 - ``prec`` (int) -- desired floating point precision (defult:
2592 default RealField precision).
2593
2594 OUTPUT:
2595
2596 (real) The total archimedean component of the height of
2597 this number field element; that is, the sum of the local
2598 heights at all infinite places.
2599
2600 EXAMPLES::
2601
2602 sage: R.<x> = QQ[]
2603 sage: K.<a> = NumberField(x^4+3*x^2-17)
2604 sage: b = a/2
2605 sage: b.global_height_arch()
2606 0.38653407379277...
2607 """
2608 r,s = self.number_field().signature()
2609 hts = [self.local_height_arch(i, prec, weighted=True) for i in range(r+s)]
2610 return sum(hts, hts[0].parent().zero_element())
2611
2612 def global_height(self, prec=None):
2613 """
2614 Returns the absolute logarithmic height of this number field element.
2615
2616 INPUT:
2617
2618 - ``prec`` (int) -- desired floating point precision (defult:
2619 default RealField precision).
2620
2621 OUTPUT:
2622
2623 (real) The absolute logarithmic height of this number field
2624 element; that is, the sum of the local heights at all finite
2625 and infinite places, with the contributions from the infinite
2626 places scaled by the degree to make the result independent of
2627 the parent field.
2628
2629 EXAMPLES::
2630
2631 sage: R.<x> = QQ[]
2632 sage: K.<a> = NumberField(x^4+3*x^2-17)
2633 sage: b = a/2
2634 sage: b.global_height()
2635 2.869222240687...
2636 sage: b.global_height(prec=200)
2637 2.8692222406879748488543678846959454765968722137813736080066
2638
2639 The global height of an algebraic number is absolute, i.e. it
2640 does not depend on th parent field::
2641
2642 sage: QQ(6).global_height()
2643 1.79175946922805
2644 sage: K(6).global_height()
2645 1.79175946922805
2646
2647 sage: L.<b> = NumberField((a^2).minpoly())
2648 sage: L.degree()
2649 2
2650 sage: b.global_height() # element of L (degree 2 field)
2651 1.41660667202811
2652 sage: (a^2).global_height() # element of K (degree 4 field)
2653 1.41660667202811
2654 """
2655 return self.global_height_non_arch(prec)+self.global_height_arch(prec)/self.number_field().absolute_degree()
2656
2657 def numerator_ideal(self):
2658 """
2659 Return the numerator ideal of this number field element.
2660
2661 .. note::
2662
2663 A ValueError will be raised if this function is called on
2664 0.
2665
2666 .. seealso::
2667
2668 :meth:`~denominator_ideal`
2669
2670 OUTPUT:
2671
2672 (integral ideal) The numerator ideal `N` of this element,
2673 where for a non-zero number field element `a`, the principal
2674 ideal generated by `a` has the form `N/D` where `N` and `D`
2675 are coprime integral ideals. An error is raised if the
2676 element is zero.
2677
2678 EXAMPLES::
2679
2680 sage: K.<a> = NumberField(x^2+5)
2681 sage: b = (1+a)/2
2682 sage: b.norm()
2683 3/2
2684 sage: N = b.numerator_ideal(); N
2685 Fractional ideal (3, a + 1)
2686 sage: N.norm()
2687 3
2688 sage: (1/b).numerator_ideal()
2689 Fractional ideal (2, a + 1)
2690
2691 TESTS:
2692
2693 Undefined for 0::
2694
2695 sage: K(0).numerator_ideal()
2696 Traceback (most recent call last):
2697 ...
2698 ValueError: numerator ideal of 0 is not defined.
2699 """
2700 if self.is_zero():
2701 raise ValueError, "numerator ideal of 0 is not defined."
2702 return self.number_field().ideal(self).numerator()
2703
2704 def denominator_ideal(self):
2705 """
2706 Return the denominator ideal of this number field element.
2707
2708 .. note::
2709
2710 A ValueError will be raised if this function is called on
2711 0.
2712
2713 .. seealso::
2714
2715 :meth:`~numerator_ideal`
2716
2717 OUTPUT:
2718
2719 (integral ideal) The denominator ideal `D` of this element,
2720 where for a non-zero number field element `a`, the principal
2721 ideal generated by `a` has the form `N/D` where `N` and `D`
2722 are coprime integral ideals. An error is raised if the
2723 element is zero.
2724
2725 EXAMPLES::
2726
2727 sage: K.<a> = NumberField(x^2+5)
2728 sage: b = (1+a)/2
2729 sage: b.norm()
2730 3/2
2731 sage: D = b.denominator_ideal(); D
2732 Fractional ideal (2, a + 1)
2733 sage: D.norm()
2734 2
2735 sage: (1/b).denominator_ideal()
2736 Fractional ideal (3, a + 1)
2737
2738 TESTS:
2739
2740 Undefined for 0::
2741
2742 sage: K(0).denominator_ideal()
2743 Traceback (most recent call last):
2744 ...
2745 ValueError: denominator ideal of 0 is not defined.
2746 """
2747 if self.is_zero():
2748 raise ValueError, "denominator ideal of 0 is not defined."
2749 return self.number_field().ideal(self).denominator()
2750
2751 def support(self):
2752 """
2753 Return the support of this number field element.
2754
2755 OUTPUT: A sorted list of the primes ideals at which this number
2756 field element has nonzero valuation. An error is raised if the
2757 element is zero.
2758
2759 EXAMPLES::
2760
2761 sage: x = ZZ['x'].gen()
2762 sage: F.<t> = NumberField(x^3 - 2)
2763
2764 ::
2765
2766 sage: P5s = F(5).support()
2767 sage: P5s
2768 [Fractional ideal (t^2 + 1), Fractional ideal (t^2 - 2*t - 1)]
2769 sage: all(5 in P5 for P5 in P5s)
2770 True
2771 sage: all(P5.is_prime() for P5 in P5s)
2772 True
2773 sage: [ P5.norm() for P5 in P5s ]
2774 [5, 25]
2775
2776 TESTS:
2777
2778 It doesn't make sense to factor the ideal (0)::
2779
2780 sage: F(0).support()
2781 Traceback (most recent call last):
2782 ...
2783 ArithmeticError: Support of 0 is not defined.
2784 """
2785 if self.is_zero():
2786 raise ArithmeticError, "Support of 0 is not defined."
2787 return self.number_field().primes_above(self)
2788
2789 def _matrix_over_base(self, L):
2790 """
2791 Return the matrix of self over the base field L.
2792
2793 EXAMPLES::
2794
2795 sage: K.<a> = NumberField(ZZ['x'].0^3-2, 'a')
2796 sage: L.<b> = K.extension(ZZ['x'].0^2+3, 'b')
2797 sage: L(a)._matrix_over_base(K) == L(a).matrix()
2798 True
2799 """
2800 K = self.number_field()
2801 E = L.embeddings(K)
2802 if len(E) == 0:
2803 raise ValueError, "no way to embed L into parent's base ring K"
2804 phi = E[0]
2805 return self._matrix_over_base_morphism(phi)
2806
2807 def _matrix_over_base_morphism(self, phi):
2808 """
2809 Return the matrix of self over a specified base, where phi gives a
2810 map from the specified base to self.parent().
2811
2812 EXAMPLES::
2813
2814 sage: F.<alpha> = NumberField(ZZ['x'].0^5-2)
2815 sage: h = Hom(QQ,F)([1])
2816 sage: alpha._matrix_over_base_morphism(h) == alpha.matrix()
2817 True
2818 sage: alpha._matrix_over_base_morphism(h) == alpha.matrix(QQ)
2819 True
2820 """
2821 L = phi.domain()
2822
2823 ## the code below doesn't work if the morphism is
2824 ## over QQ, since QQ.primitive_element() doesn't
2825 ## make sense
2826 if L is QQ:
2827 K = phi.codomain()
2828 if K != self.number_field():
2829 raise ValueError, "codomain of phi must be parent of self"
2830 ## the variable name is irrelevant below, because the
2831 ## matrix is over QQ
2832 F = K.absolute_field('alpha')
2833 from_f, to_F = F.structure()
2834 return to_F(self).matrix()
2835
2836 alpha = L.primitive_element()
2837 beta = phi(alpha)
2838 K = phi.codomain()
2839 if K != self.number_field():
2840 raise ValueError, "codomain of phi must be parent of self"
2841
2842 # Construct a relative extension over L (= QQ(beta))
2843 M = K.relativize(beta, ('a','b'))
2844 # variable name a is OK, since this is temporary
2845
2846 # Carry self over to M.
2847 from_M, to_M = M.structure()
2848 try:
2849 z = to_M(self)
2850 except Exception:
2851 return to_M, self, K, beta
2852
2853 # Compute the relative matrix of self, but in M
2854 R = z.matrix()
2855
2856 # Map back to L.
2857 psi = M.base_field().hom([alpha])
2858 return R.apply_morphism(psi)
2859
2860
2861 def list(self):
2862 """
2863 Return the list of coefficients of self written in terms of a power
2864 basis.
2865
2866 EXAMPLE::
2867
2868 sage: K.<a> = NumberField(x^3 - x + 2); ((a + 1)/(a + 2)).list()
2869 [1/4, 1/2, -1/4]
2870 sage: K.<a, b> = NumberField([x^3 - x + 2, x^2 + 23]); ((a + b)/(a + 2)).list()
2871 [3/4*b - 1/2, -1/2*b + 1, 1/4*b - 1/2]
2872 """
2873 raise NotImplementedError
2874
2875 def inverse_mod(self, I):
2876 """
2877 Returns the inverse of self mod the integral ideal I.
2878
2879 INPUT:
2880
2881 - ``I`` - may be an ideal of self.parent(), or an element or list
2882 of elements of self.parent() generating a nonzero ideal. A ValueError
2883 is raised if I is non-integral or zero. A ZeroDivisionError is
2884 raised if I + (x) != (1).
2885
2886 NOTE: It's not implemented yet for non-integral elements.
2887
2888 EXAMPLES::
2889
2890 sage: k.<a> = NumberField(x^2 + 23)
2891 sage: N = k.ideal(3)
2892 sage: d = 3*a + 1
2893 sage: d.inverse_mod(N)
2894 1
2895
2896 ::
2897
2898 sage: k.<a> = NumberField(x^3 + 11)
2899 sage: d = a + 13
2900 sage: d.inverse_mod(a^2)*d - 1 in k.ideal(a^2)
2901 True
2902 sage: d.inverse_mod((5, a + 1))*d - 1 in k.ideal(5, a + 1)
2903 True
2904 sage: K.<b> = k.extension(x^2 + 3)
2905 sage: b.inverse_mod([37, a - b])
2906 7
2907 sage: 7*b - 1 in K.ideal(37, a - b)
2908 True
2909 sage: b.inverse_mod([37, a - b]).parent() == K
2910 True
2911 """
2912 R = self.number_field().ring_of_integers()
2913 try:
2914 return _inverse_mod_generic(R(self), I)
2915 except TypeError: # raised by failure of R(self)
2916 raise NotImplementedError, "inverse_mod is not implemented for non-integral elements"
2917
2918
2919 def residue_symbol(self, P, m, check=True):
2920 r"""
2921 The m-th power residue symbol for an element self and proper ideal P.
2922
2923 .. math:: \left(\frac{\alpha}{\mathbf{P}}\right) \equiv \alpha^{\frac{N(\mathbf{P})-1}{m}} \operatorname{mod} \mathbf{P}
2924
2925 .. note:: accepts m=1, in which case returns 1
2926
2927 .. note:: can also be called for an ideal from sage.rings.number_field_ideal.residue_symbol
2928
2929 INPUT:
2930
2931 - ``P`` - proper ideal of the number field (or an extension)
2932
2933 - ``m`` - positive integer
2934
2935 OUTPUT:
2936
2937 - an m-th root of unity in the number field
2938
2939 EXAMPLES::
2940
2941 Quadratic Residue (7 is not a square modulo 11)
2942 sage: K.<a> = NumberField(x-1)
2943 sage: K(7).residue_symbol(K.ideal(11),2)
2944 -1
2945
2946 Cubic Residue
2947 sage: K.<w> = NumberField(x^2 - x + 1)
2948 sage: (w^2+3).residue_symbol(K.ideal(17),3)
2949 -w
2950
2951 """
2952 return P.residue_symbol(self,m,check)
2953
2954
2955
2956 cdef class NumberFieldElement_absolute(NumberFieldElement):
2957
2958 def _pari_(self, var='x'):
2959 """
2960 Return PARI C-library object corresponding to self.
2961
2962 EXAMPLES::
2963
2964 sage: k.<j> = QuadraticField(-1)
2965 sage: j._pari_('j')
2966 Mod(j, j^2 + 1)
2967 sage: pari(j)
2968 Mod(x, x^2 + 1)
2969
2970 ::
2971
2972 sage: y = QQ['y'].gen()
2973 sage: k.<j> = NumberField(y^3 - 2)
2974 sage: pari(j)
2975 Mod(x, x^3 - 2)
2976
2977 By default the variable name is 'x', since in PARI many variable
2978 names are reserved::
2979
2980 sage: theta = polygen(QQ, 'theta')
2981 sage: M.<theta> = NumberField(theta^2 + 1)
2982 sage: pari(theta)
2983 Mod(x, x^2 + 1)
2984
2985 If you try do coerce a generator called I to PARI, hell may break
2986 loose::
2987
2988 sage: k.<I> = QuadraticField(-1)
2989 sage: I._pari_('I')
2990 Traceback (most recent call last):
2991 ...
2992 PariError: incorrect type (11)
2993
2994 Instead, request the variable be named different for the coercion::
2995
2996 sage: pari(I)
2997 Mod(x, x^2 + 1)
2998 sage: I._pari_('i')
2999 Mod(i, i^2 + 1)
3000 sage: I._pari_('II')
3001 Mod(II, II^2 + 1)
3002 """
3003 try:
3004 return self.__pari[var]
3005 except KeyError:
3006 pass
3007 except TypeError:
3008 self.__pari = {}
3009 if var is None:
3010 var = self.number_field().variable_name()
3011
3012 f = self.polynomial()._pari_().subst('x', var)
3013 g = self.number_field().pari_polynomial().subst('x', var)
3014 h = f.Mod(g)
3015 self.__pari[var] = h
3016 return h
3017
3018 def _magma_init_(self, magma):
3019 """
3020 Return Magma version of this number field element.
3021
3022 INPUT:
3023
3024
3025 - ``magma`` - a Magma interpreter
3026
3027
3028 OUTPUT: MagmaElement that has parent the Magma object corresponding
3029 to the parent number field.
3030
3031 EXAMPLES::
3032
3033 sage: K.<a> = NumberField(x^3 + 2)
3034 sage: a._magma_init_(magma) # optional - magma
3035 '(_sage_[...]![0, 1, 0])'
3036 sage: magma((2/3)*a^2 - 17/3) # optional - magma
3037 1/3*(2*a^2 - 17)
3038
3039 An element of a cyclotomic field.
3040
3041 ::
3042
3043 sage: K = CyclotomicField(9)
3044 sage: K.gen()
3045 zeta9
3046 sage: K.gen()._magma_init_(magma) # optional - magma
3047 '(_sage_[...]![0, 1, 0, 0, 0, 0])'
3048 sage: magma(K.gen()) # optional - magma
3049 zeta9
3050 """
3051 K = magma(self.parent())
3052 return '(%s!%s)'%(K.name(), self.list())
3053
3054 def absolute_charpoly(self, var='x', algorithm=None):
3055 r"""
3056 Return the characteristic polynomial of this element over `\QQ`.
3057
3058 For the meaning of the optional argument ``algorithm``, see :meth:`charpoly`.
3059
3060 EXAMPLES::
3061
3062 sage: x = ZZ['x'].0
3063 sage: K.<a> = NumberField(x^4 + 2, 'a')
3064 sage: a.absolute_charpoly()
3065 x^4 + 2
3066 sage: a.absolute_charpoly('y')
3067 y^4 + 2
3068 sage: (-a^2).absolute_charpoly()
3069 x^4 + 4*x^2 + 4
3070 sage: (-a^2).absolute_minpoly()
3071 x^2 + 2
3072
3073 sage: a.absolute_charpoly(algorithm='pari') == a.absolute_charpoly(algorithm='sage')
3074 True
3075 """
3076 # this hack is necessary because quadratic fields override
3077 # charpoly(), and they don't take the argument 'algorithm'
3078 if algorithm is None:
3079 return self.charpoly(var)
3080 return self.charpoly(var, algorithm)
3081
3082 def absolute_minpoly(self, var='x', algorithm=None):
3083 r"""
3084 Return the minimal polynomial of this element over
3085 `\QQ`.
3086
3087 For the meaning of the optional argument algorithm, see :meth:`charpoly`.
3088
3089 EXAMPLES::
3090
3091 sage: x = ZZ['x'].0
3092 sage: f = x^10 - 5*x^9 + 15*x^8 - 68*x^7 + 81*x^6 - 221*x^5 + 141*x^4 - 242*x^3 - 13*x^2 - 33*x - 135
3093 sage: K.<a> = NumberField(f, 'a')
3094 sage: a.absolute_charpoly()
3095 x^10 - 5*x^9 + 15*x^8 - 68*x^7 + 81*x^6 - 221*x^5 + 141*x^4 - 242*x^3 - 13*x^2 - 33*x - 135
3096 sage: a.absolute_charpoly('y')
3097 y^10 - 5*y^9 + 15*y^8 - 68*y^7 + 81*y^6 - 221*y^5 + 141*y^4 - 242*y^3 - 13*y^2 - 33*y - 135
3098 sage: b = -79/9995*a^9 + 52/9995*a^8 + 271/9995*a^7 + 1663/9995*a^6 + 13204/9995*a^5 + 5573/9995*a^4 + 8435/1999*a^3 - 3116/9995*a^2 + 7734/1999*a + 1620/1999
3099 sage: b.absolute_charpoly()
3100 x^10 + 10*x^9 + 25*x^8 - 80*x^7 - 438*x^6 + 80*x^5 + 2950*x^4 + 1520*x^3 - 10439*x^2 - 5130*x + 18225
3101 sage: b.absolute_minpoly()
3102 x^5 + 5*x^4 - 40*x^2 - 19*x + 135
3103
3104 sage: b.absolute_minpoly(algorithm='pari') == b.absolute_minpoly(algorithm='sage')
3105 True
3106 """
3107 # this hack is necessary because quadratic fields override
3108 # minpoly(), and they don't take the argument 'algorithm'
3109 if algorithm is None:
3110 return self.minpoly(var)
3111 return self.minpoly(var, algorithm)
3112
3113 def charpoly(self, var='x', algorithm=None):
3114 r"""
3115 The characteristic polynomial of this element, over
3116 `\QQ` if self is an element of a field, and over
3117 `\ZZ` is self is an element of an order.
3118
3119 This is the same as ``self.absolute_charpoly`` since
3120 this is an element of an absolute extension.
3121
3122 The optional argument algorithm controls how the
3123 characteristic polynomial is computed: 'pari' uses Pari,
3124 'sage' uses charpoly for Sage matrices. The default value
3125 None means that 'pari' is used for small degrees (up to the
3126 value of the constant TUNE_CHARPOLY_NF, currently at 25),
3127 otherwise 'sage' is used. The constant TUNE_CHARPOLY_NF
3128 should give reasonable performance on all architectures;
3129 however, if you feel the need to customize it to your own
3130 machine, see trac ticket 5213 for a tuning script.
3131
3132 EXAMPLES:
3133
3134 We compute the characteristic polynomial of the cube root of `2`.
3135
3136 ::
3137
3138 sage: R.<x> = QQ[]
3139 sage: K.<a> = NumberField(x^3-2)
3140 sage: a.charpoly('x')
3141 x^3 - 2
3142 sage: a.charpoly('y').parent()
3143 Univariate Polynomial Ring in y over Rational Field
3144
3145 TESTS::
3146
3147 sage: R = K.ring_of_integers()
3148 sage: R(a).charpoly()
3149 x^3 - 2
3150 sage: R(a).charpoly().parent()
3151 Univariate Polynomial Ring in x over Integer Ring
3152
3153 sage: R(a).charpoly(algorithm='pari') == R(a).charpoly(algorithm='sage')
3154 True
3155 """
3156 if algorithm is None:
3157 if self._parent.degree() <= TUNE_CHARPOLY_NF:
3158 algorithm = 'pari'
3159 else:
3160 algorithm = 'sage'
3161 R = self._parent.base_ring()[var]
3162 if algorithm == 'pari':
3163 return R(self._pari_('x').charpoly())
3164 if algorithm == 'sage':
3165 return R(self.matrix().charpoly())
3166
3167 def minpoly(self, var='x', algorithm=None):
3168 """
3169 Return the minimal polynomial of this number field element.
3170
3171 For the meaning of the optional argument algorithm, see charpoly().
3172
3173 EXAMPLES:
3174
3175 We compute the characteristic polynomial of cube root of `2`.
3176
3177 ::
3178
3179 sage: R.<x> = QQ[]
3180 sage: K.<a> = NumberField(x^3-2)
3181 sage: a.minpoly('x')
3182 x^3 - 2
3183 sage: a.minpoly('y').parent()
3184 Univariate Polynomial Ring in y over Rational Field
3185
3186 TESTS::
3187
3188 sage: R = K.ring_of_integers()
3189 sage: R(a).minpoly()
3190 x^3 - 2
3191 sage: R(a).minpoly().parent()
3192 Univariate Polynomial Ring in x over Integer Ring
3193
3194 sage: R(a).minpoly(algorithm='pari') == R(a).minpoly(algorithm='sage')
3195 True
3196
3197 """
3198 return self.charpoly(var, algorithm).radical() # square free part of charpoly
3199
3200 def list(self):
3201 """
3202 Return the list of coefficients of self written in terms of a power
3203 basis.
3204
3205 EXAMPLE::
3206
3207 sage: K.<z> = CyclotomicField(3)
3208 sage: (2+3/5*z).list()
3209 [2, 3/5]
3210 sage: (5*z).list()
3211 [0, 5]
3212 sage: K(3).list()
3213 [3, 0]
3214 """
3215 n = self.number_field().degree()
3216 v = self._coefficients()
3217 z = sage.rings.rational.Rational(0)
3218 return v + [z]*(n - len(v))
3219
3220 def lift(self, var='x'):
3221 """
3222 Return an element of QQ[x], where this number field element
3223 lives in QQ[x]/(f(x)).
3224
3225 EXAMPLES::
3226
3227 sage: K.<a> = QuadraticField(-3)
3228 sage: a.lift()
3229 x
3230
3231 """
3232 R = self.number_field().base_field()[var]
3233 return R(self.list())
3234
3235 def is_real_positive(self, min_prec=53):
3236 r"""
3237 Using the ``n`` method of approximation, return ``True`` if
3238 ``self`` is a real positive number and ``False`` otherwise.
3239 This method is completely dependent of the embedding used by
3240 the ``n`` method.
3241
3242 The algorithm first checks that ``self`` is not a strictly
3243 complex number. Then if ``self`` is not zero, by approximation
3244 more and more precise, the method answers True if the
3245 number is positive. Using `RealInterval`, the result is
3246 guaranteed to be correct.
3247
3248 For CyclotomicField, the embedding is the natural one
3249 sending `zetan` on `cos(2*pi/n)`.
3250
3251 EXAMPLES::
3252
3253 sage: K.<a> = CyclotomicField(3)
3254 sage: (a+a^2).is_real_positive()
3255 False
3256 sage: (-a-a^2).is_real_positive()
3257 True
3258 sage: K.<a> = CyclotomicField(1000)
3259 sage: (a+a^(-1)).is_real_positive()
3260 True
3261 sage: K.<a> = CyclotomicField(1009)
3262 sage: d = a^252
3263 sage: (d+d.conjugate()).is_real_positive()
3264 True
3265 sage: d = a^253
3266 sage: (d+d.conjugate()).is_real_positive()
3267 False
3268 sage: K.<a> = QuadraticField(3)
3269 sage: a.is_real_positive()
3270 True
3271 sage: K.<a> = QuadraticField(-3)
3272 sage: a.is_real_positive()
3273 False
3274 sage: (a-a).is_real_positive()
3275 False
3276 """
3277 if self != self.conjugate() or self.is_zero():
3278 return False
3279 else:
3280 approx = RealInterval(self.n(min_prec).real())
3281 if approx.lower() > 0:
3282 return True
3283 else:
3284 if approx.upper() < 0:
3285 return False
3286 else:
3287 return self.is_real_positive(min_prec+20)
3288
3289 cdef class NumberFieldElement_relative(NumberFieldElement):
3290 r"""
3291 The current relative number field element implementation
3292 does everything in terms of absolute polynomials.
3293
3294 All conversions from relative polynomials, lists, vectors, etc
3295 should happen in the parent.
3296 """
3297 def __init__(self, parent, f):
3298 r"""
3299 EXAMPLE::
3300
3301 sage: L.<a, b> = NumberField([x^2 + 1, x^2 + 2])
3302 sage: type(a) # indirect doctest
3303 <type 'sage.rings.number_field.number_field_element.NumberFieldElement_relative'>
3304 """
3305 NumberFieldElement.__init__(self, parent, f)
3306
3307 def __getitem__(self, n):
3308 """
3309 Return the n-th coefficient of this relative number field element, written
3310 as a polynomial in the generator.
3311
3312 Note that `n` must be between 0 and `d-1`, where
3313 `d` is the relative degree of the number field.
3314
3315 EXAMPLES::
3316
3317 sage: K.<a, b> = NumberField([x^3 - 5, x^2 + 3])
3318 sage: c = (a + b)^3; c
3319 3*b*a^2 - 9*a - 3*b + 5
3320 sage: c[0]
3321 -3*b + 5
3322
3323 We illustrate bounds checking::
3324
3325 sage: c[-1]
3326 Traceback (most recent call last):
3327 ...
3328 IndexError: index must be between 0 and the relative degree minus 1.
3329 sage: c[4]
3330 Traceback (most recent call last):
3331 ...
3332 IndexError: index must be between 0 and the relative degree minus 1.
3333
3334 The list method implicitly calls ``__getitem__``::
3335
3336 sage: list(c)
3337 [-3*b + 5, -9, 3*b]
3338 sage: K(list(c)) == c
3339 True
3340 """
3341 if n < 0 or n >= self.parent().relative_degree():
3342 raise IndexError, "index must be between 0 and the relative degree minus 1."
3343 return self.vector()[n]
3344
3345 def list(self):
3346 """
3347 Return the list of coefficients of self written in terms of a power
3348 basis.
3349
3350 EXAMPLES::
3351
3352 sage: K.<a,b> = NumberField([x^3+2, x^2+1])
3353 sage: a.list()
3354 [0, 1, 0]
3355 sage: v = (K.base_field().0 + a)^2 ; v
3356 a^2 + 2*b*a - 1
3357 sage: v.list()
3358 [-1, 2*b, 1]
3359 """
3360 return self.vector().list()
3361
3362 def lift(self, var='x'):
3363 """
3364 Return an element of K[x], where this number field element
3365 lives in the relative number field K[x]/(f(x)).
3366
3367 EXAMPLES::
3368
3369 sage: K.<a> = QuadraticField(-3)
3370 sage: x = polygen(K)
3371 sage: L.<b> = K.extension(x^7 + 5)
3372 sage: u = L(1/2*a + 1/2 + b + (a-9)*b^5)
3373 sage: u.lift()
3374 (a - 9)*x^5 + x + 1/2*a + 1/2
3375
3376 """
3377 K = self.number_field()
3378 # Compute representation of self in terms of relative vector space.
3379 R = K.base_field()[var]
3380 return R(self.list())
3381
3382 def _pari_(self, var='x'):
3383 """
3384 Return PARI C-library object corresponding to self.
3385
3386 EXAMPLES:
3387
3388 By default the variable name is 'x', since in PARI many
3389 variable names are reserved.
3390
3391 ::
3392
3393 sage: y = QQ['y'].gen()
3394 sage: k.<j> = NumberField([y^2 - 7, y^3 - 2])
3395 sage: pari(j)
3396 Mod(42/5515*x^5 - 9/11030*x^4 - 196/1103*x^3 + 273/5515*x^2 + 10281/5515*x + 4459/11030, x^6 - 21*x^4 + 4*x^3 + 147*x^2 + 84*x - 339)
3397 sage: j^2
3398 7
3399 sage: pari(j)^2
3400 Mod(7, x^6 - 21*x^4 + 4*x^3 + 147*x^2 + 84*x - 339)
3401 sage: (j^2)._pari_('y')
3402 Mod(7, y^6 - 21*y^4 + 4*y^3 + 147*y^2 + 84*y - 339)
3403
3404 sage: K.<a> = NumberField(x^2 + 2, 'a')
3405 sage: K(1)._pari_()
3406 Mod(1, x^2 + 2)
3407 sage: K(1)._pari_('t')
3408 Mod(1, t^2 + 2)
3409
3410 sage: K.gen()._pari_()
3411 Mod(x, x^2 + 2)
3412 sage: K.gen()._pari_('t')
3413 Mod(t, t^2 + 2)
3414
3415 At this time all elements, even relative elements, are
3416 represented as absolute polynomials:
3417
3418 sage: K.<a> = NumberField(x^2 + 2, 'a')
3419 sage: L.<b> = NumberField(K['x'].0^2 + a, 'b')
3420 sage: L(1)._pari_()
3421 Mod(1, x^4 + 2)
3422 sage: L(1)._pari_('t')
3423 Mod(1, t^4 + 2)
3424 sage: L.gen()._pari_()
3425 Mod(x, x^4 + 2)
3426 sage: L.gen()._pari_('t')
3427 Mod(t, t^4 + 2)
3428
3429 sage: M.<c> = NumberField(L['x'].0^3 + b, 'c')
3430 sage: M(1)._pari_()
3431 Mod(1, x^12 + 2)
3432 sage: M(1)._pari_('t')
3433 Mod(1, t^12 + 2)
3434 sage: M.gen()._pari_()
3435 Mod(x, x^12 + 2)
3436 sage: M.gen()._pari_('t')
3437 Mod(t, t^12 + 2)
3438 """
3439 try:
3440 return self.__pari[var]
3441 except KeyError:
3442 pass
3443 except TypeError:
3444 self.__pari = {}
3445 g = self.parent().pari_polynomial(var)
3446 f = self.polynomial()._pari_()
3447 f = f.subst('x', var)
3448 h = f.Mod(g)
3449 self.__pari[var] = h
3450 return h
3451
3452 def _repr_(self):
3453 r"""
3454 EXAMPLE::
3455
3456 sage: L.<a, b> = NumberField([x^3 - x + 1, x^2 + 23])
3457 sage: repr(a^4*b) # indirect doctest
3458 'b*a^2 - b*a'
3459 """
3460 K = self.number_field()
3461 # Compute representation of self in terms of relative vector space.
3462 R = K.base_field()[K.variable_name()]
3463 return repr(R(self.list()))
3464
3465 def _latex_(self):
3466 r"""
3467 Returns the latex representation for this element.
3468
3469 EXAMPLES::
3470
3471 sage: C.<zeta> = CyclotomicField(12)
3472 sage: PC.<x> = PolynomialRing(C)
3473 sage: K.<alpha> = NumberField(x^2 - 7)
3474 sage: latex((alpha + zeta)^4) # indirect doctest
3475 \left(4 \zeta_{12}^{3} + 28 \zeta_{12}\right) \alpha + 43 \zeta_{12}^{2} + 48
3476 sage: PK.<y> = PolynomialRing(K)
3477 sage: L.<beta> = NumberField(y^3 + y + alpha)
3478 sage: latex((beta + zeta)^3) # indirect doctest
3479 3 \zeta_{12} \beta^{2} + \left(3 \zeta_{12}^{2} - 1\right) \beta - \alpha + \zeta_{12}^{3}
3480 """
3481 K = self.number_field()
3482 R = K.base_field()[K.variable_name()]
3483 return R(self.list())._latex_()
3484
3485 def charpoly(self, var='x'):
3486 r"""
3487 The characteristic polynomial of this element over its base field.
3488
3489 EXAMPLES::
3490
3491 sage: x = ZZ['x'].0
3492 sage: K.<a, b> = QQ.extension([x^2 + 2, x^5 + 400*x^4 + 11*x^2 + 2])
3493 sage: a.charpoly()
3494 x^2 + 2
3495 sage: b.charpoly()
3496 x^2 - 2*b*x + b^2
3497 sage: b.minpoly()
3498 x - b
3499
3500 sage: K.<a, b> = NumberField([x^2 + 2, x^2 + 1000*x + 1])
3501 sage: y = K['y'].0
3502 sage: L.<c> = K.extension(y^2 + a*y + b)
3503 sage: c.charpoly()
3504 x^2 + a*x + b
3505 sage: c.minpoly()
3506 x^2 + a*x + b
3507 sage: L(a).charpoly()
3508 x^2 - 2*a*x - 2
3509 sage: L(a).minpoly()
3510 x - a
3511 sage: L(b).charpoly()
3512 x^2 - 2*b*x - 1000*b - 1
3513 sage: L(b).minpoly()
3514 x - b
3515 """
3516 R = self._parent.base_ring()[var]
3517 return R(self.matrix().charpoly())
3518
3519 def absolute_charpoly(self, var='x', algorithm=None):
3520 r"""
3521 The characteristic polynomial of this element over
3522 `\QQ`.
3523
3524 We construct a relative extension and find the characteristic
3525 polynomial over `\QQ`.
3526
3527 The optional argument algorithm controls how the
3528 characteristic polynomial is computed: 'pari' uses Pari,
3529 'sage' uses charpoly for Sage matrices. The default value
3530 None means that 'pari' is used for small degrees (up to the
3531 value of the constant TUNE_CHARPOLY_NF, currently at 25),
3532 otherwise 'sage' is used. The constant TUNE_CHARPOLY_NF
3533 should give reasonable performance on all architectures;
3534 however, if you feel the need to customize it to your own
3535 machine, see trac ticket 5213 for a tuning script.
3536
3537 EXAMPLES::
3538
3539 sage: R.<x> = QQ[]
3540 sage: K.<a> = NumberField(x^3-2)
3541 sage: S.<X> = K[]
3542 sage: L.<b> = NumberField(X^3 + 17); L
3543 Number Field in b with defining polynomial X^3 + 17 over its base field
3544 sage: b.absolute_charpoly()
3545 x^9 + 51*x^6 + 867*x^3 + 4913
3546 sage: b.charpoly()(b)
3547 0
3548 sage: a = L.0; a
3549 b
3550 sage: a.absolute_charpoly('x')
3551 x^9 + 51*x^6 + 867*x^3 + 4913
3552 sage: a.absolute_charpoly('y')
3553 y^9 + 51*y^6 + 867*y^3 + 4913
3554
3555 sage: a.absolute_charpoly(algorithm='pari') == a.absolute_charpoly(algorithm='sage')
3556 True
3557 """
3558 if algorithm is None:
3559 # this might not be the optimal condition; maybe it should
3560 # be .degree() instead of .absolute_degree()
3561 # there are too many bugs in relative number fields to
3562 # figure this out now
3563 if self._parent.absolute_degree() <= TUNE_CHARPOLY_NF:
3564 algorithm = 'pari'
3565 else:
3566 algorithm = 'sage'
3567 g = self.polynomial() # in QQ[x]
3568 R = QQ[var]
3569 if algorithm == 'pari':
3570 f = self.number_field().pari_polynomial() # # field is QQ[x]/(f)
3571 return R((g._pari_().Mod(f)).charpoly()).change_variable_name(var)
3572 if algorithm == 'sage':
3573 return R(self.matrix(QQ).charpoly())
3574
3575 def absolute_minpoly(self, var='x', algorithm=None):
3576 r"""
3577 Return the minimal polynomial over `\QQ` of this element.
3578
3579 For the meaning of the optional argument ``algorithm``, see :meth:`absolute_charpoly`.
3580
3581 EXAMPLES::
3582
3583 sage: K.<a, b> = NumberField([x^2 + 2, x^2 + 1000*x + 1])
3584 sage: y = K['y'].0
3585 sage: L.<c> = K.extension(y^2 + a*y + b)
3586 sage: c.absolute_charpoly()
3587 x^8 - 1996*x^6 + 996006*x^4 + 1997996*x^2 + 1
3588 sage: c.absolute_minpoly()
3589 x^8 - 1996*x^6 + 996006*x^4 + 1997996*x^2 + 1
3590 sage: L(a).absolute_charpoly()
3591 x^8 + 8*x^6 + 24*x^4 + 32*x^2 + 16
3592 sage: L(a).absolute_minpoly()
3593 x^2 + 2
3594 sage: L(b).absolute_charpoly()
3595 x^8 + 4000*x^7 + 6000004*x^6 + 4000012000*x^5 + 1000012000006*x^4 + 4000012000*x^3 + 6000004*x^2 + 4000*x + 1
3596 sage: L(b).absolute_minpoly()
3597 x^2 + 1000*x + 1
3598 """
3599 return self.absolute_charpoly(var, algorithm).radical()
3600
3601 def valuation(self, P):
3602 """
3603 Returns the valuation of self at a given prime ideal P.
3604
3605 INPUT:
3606
3607
3608 - ``P`` - a prime ideal of relative number field which is the parent of self
3609
3610
3611 EXAMPLES::
3612
3613 sage: K.<a, b, c> = NumberField([x^2 - 2, x^2 - 3, x^2 - 5])
3614 sage: P = K.prime_factors(5)[0]
3615 sage: (2*a + b - c).valuation(P)
3616 1
3617 """
3618 P_abs = P.absolute_ideal()
3619 abs = P_abs.number_field()
3620 to_abs = abs.structure()[1]
3621 return to_abs(self).valuation(P_abs)
3622
3623
3624 cdef class OrderElement_absolute(NumberFieldElement_absolute):
3625 """
3626 Element of an order in an absolute number field.
3627
3628 EXAMPLES::
3629
3630 sage: K.<a> = NumberField(x^2 + 1)
3631 sage: O2 = K.order(2*a)
3632 sage: w = O2.1; w
3633 2*a
3634 sage: parent(w)
3635 Order in Number Field in a with defining polynomial x^2 + 1
3636
3637 sage: w.absolute_charpoly()
3638 x^2 + 4
3639 sage: w.absolute_charpoly().parent()
3640 Univariate Polynomial Ring in x over Integer Ring
3641 sage: w.absolute_minpoly()
3642 x^2 + 4
3643 sage: w.absolute_minpoly().parent()
3644 Univariate Polynomial Ring in x over Integer Ring
3645 """
3646 def __init__(self, order, f):
3647 r"""
3648 EXAMPLE::
3649
3650 sage: K.<a> = NumberField(x^3 + 2)
3651 sage: O2 = K.order(2*a)
3652 sage: type(O2.1) # indirect doctest
3653 <type 'sage.rings.number_field.number_field_element.OrderElement_absolute'>
3654 """
3655 K = order.number_field()
3656 NumberFieldElement_absolute.__init__(self, K, f)
3657 self._number_field = K
3658 (<Element>self)._parent = order
3659
3660 cdef _new(self):
3661 """
3662 Quickly creates a new initialized NumberFieldElement with the same
3663 parent as self.
3664
3665 EXAMPLES:
3666
3667 This is called implicitly in multiplication::
3668
3669 sage: O = EquationOrder(x^3 + 18, 'a')
3670 sage: O.1 * O.1 * O.1
3671 -18
3672 """
3673 cdef OrderElement_absolute x
3674 x = <OrderElement_absolute>PY_NEW_SAME_TYPE(self)
3675 x._parent = self._parent
3676 x._number_field = self._parent.number_field()
3677 x.__fld_numerator = self.__fld_numerator
3678 x.__fld_denominator = self.__fld_denominator
3679 return x
3680
3681 cdef number_field(self):
3682 r"""
3683 Return the number field of self. Only accessible from Cython.
3684
3685 EXAMPLE::
3686
3687 sage: K = NumberField(x^3 - 17, 'a')
3688 sage: OK = K.ring_of_integers()
3689 sage: a = OK(K.gen())
3690 sage: a._number_field() is K # indirect doctest
3691 True
3692 """
3693 return self._number_field
3694
3695 cpdef RingElement _div_(self, RingElement other):
3696 r"""
3697 Implement division, checking that the result has the right parent.
3698 It's not so crucial what the parent actually is, but it is crucial
3699 that the returned value really is an element of its supposed
3700 parent! This fixes trac #4190.
3701
3702 EXAMPLES::
3703
3704 sage: K = NumberField(x^3 - 17, 'a')
3705 sage: OK = K.ring_of_integers()
3706 sage: a = OK(K.gen())
3707 sage: (17/a) in OK # indirect doctest
3708 True
3709 sage: (17/a).parent() is K # indirect doctest
3710 True
3711 sage: (17/(2*a)).parent() is K # indirect doctest
3712 True
3713 sage: (17/(2*a)) in OK # indirect doctest
3714 False
3715 """
3716 cdef NumberFieldElement_absolute x
3717 x = NumberFieldElement_absolute._div_(self, other)
3718 return self._parent.number_field()(x)
3719
3720 def inverse_mod(self, I):
3721 r"""
3722 Return an inverse of self modulo the given ideal.
3723
3724 INPUT:
3725
3726
3727 - ``I`` - may be an ideal of self.parent(), or an
3728 element or list of elements of self.parent() generating a nonzero
3729 ideal. A ValueError is raised if I is non-integral or is zero.
3730 A ZeroDivisionError is raised if I + (x) != (1).
3731
3732
3733 EXAMPLES::
3734
3735 sage: OE = NumberField(x^3 - x + 2, 'w').ring_of_integers()
3736 sage: w = OE.ring_generators()[0]
3737 sage: w.inverse_mod(13*OE)
3738 6*w^2 - 6
3739 sage: w * (w.inverse_mod(13)) - 1 in 13*OE
3740 True
3741 sage: w.inverse_mod(13).parent() == OE
3742 True
3743 sage: w.inverse_mod(2*OE)
3744 Traceback (most recent call last):
3745 ...
3746 ZeroDivisionError: w is not invertible modulo Fractional ideal (2)
3747 """
3748 R = self.parent()
3749 return R(_inverse_mod_generic(self, I))
3750
3751 def __invert__(self):
3752 r"""
3753 Implement inversion, checking that the return value has the right
3754 parent. See trac #4190.
3755
3756 EXAMPLE::
3757
3758 sage: K = NumberField(x^3 -x + 2, 'a')
3759 sage: OK = K.ring_of_integers()
3760 sage: a = OK(K.gen())
3761 sage: (~a).parent() is K
3762 True
3763 sage: (~a) in OK
3764 False
3765 sage: a**(-1) in OK
3766 False
3767 """
3768 return self._parent.number_field()(NumberFieldElement_absolute.__invert__(self))
3769
3770 cdef class OrderElement_relative(NumberFieldElement_relative):
3771 """
3772 Element of an order in a relative number field.
3773
3774 EXAMPLES::
3775
3776 sage: O = EquationOrder([x^2 + x + 1, x^3 - 2],'a,b')
3777 sage: c = O.1; c
3778 (-2*b^2 - 2)*a - 2*b^2 - b
3779 sage: type(c)
3780 <type 'sage.rings.number_field.number_field_element.OrderElement_relative'>
3781 """
3782 def __init__(self, order, f):
3783 r"""
3784 EXAMPLE::
3785
3786 sage: O = EquationOrder([x^2 + x + 1, x^3 - 2],'a,b')
3787 sage: type(O.1) # indirect doctest
3788 <type 'sage.rings.number_field.number_field_element.OrderElement_relative'>
3789 """
3790 K = order.number_field()
3791 NumberFieldElement_relative.__init__(self, K, f)
3792 (<Element>self)._parent = order
3793 self._number_field = K
3794
3795 cdef number_field(self):
3796 return self._number_field
3797
3798 cdef _new(self):
3799 """
3800 Quickly creates a new initialized NumberFieldElement with the same
3801 parent as self.
3802
3803 EXAMPLES:
3804
3805 This is called implicitly in multiplication::
3806
3807 sage: O = EquationOrder([x^2 + 18, x^3 + 2], 'a,b')
3808 sage: c = O.1 * O.2; c
3809 (-23321*b^2 - 9504*b + 10830)*a + 10152*b^2 - 104562*b - 110158
3810 sage: parent(c) == O
3811 True
3812 """
3813 cdef OrderElement_relative x
3814 x = <OrderElement_relative>PY_NEW_SAME_TYPE(self)
3815 x._parent = self._parent
3816 x._number_field = self._parent.number_field()
3817 x.__fld_numerator = self.__fld_numerator
3818 x.__fld_denominator = self.__fld_denominator
3819 return x
3820
3821 cpdef RingElement _div_(self, RingElement other):
3822 r"""
3823 Implement division, checking that the result has the right parent.
3824 It's not so crucial what the parent actually is, but it is crucial
3825 that the returned value really is an element of its supposed
3826 parent. This fixes trac #4190.
3827
3828 EXAMPLES::
3829
3830 sage: K1.<a> = NumberField(x^3 - 17)
3831 sage: R.<y> = K1[]
3832 sage: K2 = K1.extension(y^2 - a, 'b')
3833 sage: OK2 = K2.order(K2.gen()) # (not maximal)
3834 sage: b = OK2.gens()[1]; b
3835 b
3836 sage: (17/b).parent() is K2 # indirect doctest
3837 True
3838 sage: (17/b) in OK2 # indirect doctest
3839 True
3840 sage: (17/b^7) in OK2 # indirect doctest
3841 False
3842 """
3843 cdef NumberFieldElement_relative x
3844 x = NumberFieldElement_relative._div_(self, other)
3845 return self._parent.number_field()(x)
3846
3847 def __invert__(self):
3848 r"""
3849 Implement division, checking that the result has the right parent.
3850 See trac #4190.
3851
3852 EXAMPLES::
3853
3854 sage: K1.<a> = NumberField(x^3 - 17)
3855 sage: R.<y> = K1[]
3856 sage: K2 = K1.extension(y^2 - a, 'b')
3857 sage: OK2 = K2.order(K2.gen()) # (not maximal)
3858 sage: b = OK2.gens()[1]; b
3859 b
3860 sage: b.parent() is OK2
3861 True
3862 sage: (~b).parent() is K2
3863 True
3864 sage: (~b) in OK2 # indirect doctest
3865 False
3866 sage: b**(-1) in OK2 # indirect doctest
3867 False
3868 """
3869 return self._parent.number_field()(NumberFieldElement_relative.__invert__(self))
3870
3871 def inverse_mod(self, I):
3872 r"""
3873 Return an inverse of self modulo the given ideal.
3874
3875 INPUT:
3876
3877
3878 - ``I`` - may be an ideal of self.parent(), or an
3879 element or list of elements of self.parent() generating a nonzero
3880 ideal. A ValueError is raised if I is non-integral or is zero.
3881 A ZeroDivisionError is raised if I + (x) != (1).
3882
3883
3884 EXAMPLES::
3885
3886 sage: E.<a,b> = NumberField([x^2 - x + 2, x^2 + 1])
3887 sage: OE = E.ring_of_integers()
3888 sage: t = OE(b - a).inverse_mod(17*b)
3889 sage: t*(b - a) - 1 in E.ideal(17*b)
3890 True
3891 sage: t.parent() == OE
3892 True
3893 """
3894 R = self.parent()
3895 return R(_inverse_mod_generic(self, I))
3896
3897 def charpoly(self, var='x'):
3898 r"""
3899 The characteristic polynomial of this order element over its base ring.
3900
3901 This special implementation works around bug \#4738. At this
3902 time the base ring of relative order elements is ZZ; it should
3903 be the ring of integers of the base field.
3904
3905 EXAMPLES::
3906
3907 sage: x = ZZ['x'].0
3908 sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3])
3909 sage: OK = K.maximal_order(); OK.basis()
3910 [1, 1/2*a - 1/2*b, -1/2*b*a + 1/2, a]
3911 sage: charpoly(OK.1)
3912 x^2 + b*x + 1
3913 sage: charpoly(OK.1).parent()
3914 Univariate Polynomial Ring in x over Maximal Order in Number Field in b with defining polynomial x^2 - 3
3915 sage: [ charpoly(t) for t in OK.basis() ]
3916 [x^2 - 2*x + 1, x^2 + b*x + 1, x^2 - x + 1, x^2 + 1]
3917 """
3918 R = self.parent().number_field().base_field().ring_of_integers()[var]
3919 return R(self.matrix().charpoly(var))
3920
3921 def minpoly(self, var='x'):
3922 r"""
3923 The minimal polynomial of this order element over its base ring.
3924
3925 This special implementation works around bug \#4738. At this
3926 time the base ring of relative order elements is ZZ; it should
3927 be the ring of integers of the base field.
3928
3929 EXAMPLES::
3930
3931 sage: x = ZZ['x'].0
3932 sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3])
3933 sage: OK = K.maximal_order(); OK.basis()
3934 [1, 1/2*a - 1/2*b, -1/2*b*a + 1/2, a]
3935 sage: minpoly(OK.1)
3936 x^2 + b*x + 1
3937 sage: charpoly(OK.1).parent()
3938 Univariate Polynomial Ring in x over Maximal Order in Number Field in b with defining polynomial x^2 - 3
3939 sage: _, u, _, v = OK.basis()
3940 sage: t = 2*u - v; t
3941 -b
3942 sage: t.charpoly()
3943 x^2 + 2*b*x + 3
3944 sage: t.minpoly()
3945 x + b
3946
3947 sage: t.absolute_charpoly()
3948 x^4 - 6*x^2 + 9
3949 sage: t.absolute_minpoly()
3950 x^2 - 3
3951 """
3952 K = self.parent().number_field()
3953 R = K.base_field().ring_of_integers()[var]
3954 return R(K(self).minpoly(var))
3955
3956 def absolute_charpoly(self, var='x'):
3957 r"""
3958 The absolute characteristic polynomial of this order element over ZZ.
3959
3960 EXAMPLES::
3961
3962 sage: x = ZZ['x'].0
3963 sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3])
3964 sage: OK = K.maximal_order()
3965 sage: _, u, _, v = OK.basis()
3966 sage: t = 2*u - v; t
3967 -b
3968 sage: t.absolute_charpoly()
3969 x^4 - 6*x^2 + 9
3970 sage: t.absolute_minpoly()
3971 x^2 - 3
3972 sage: t.absolute_charpoly().parent()
3973 Univariate Polynomial Ring in x over Integer Ring
3974 """
3975 K = self.parent().number_field()
3976 R = ZZ[var]
3977 return R(K(self).absolute_charpoly(var))
3978
3979 def absolute_minpoly(self, var='x'):
3980 r"""
3981 The absolute minimal polynomial of this order element over ZZ.
3982
3983 EXAMPLES::
3984
3985 sage: x = ZZ['x'].0
3986 sage: K.<a,b> = NumberField([x^2 + 1, x^2 - 3])
3987 sage: OK = K.maximal_order()
3988 sage: _, u, _, v = OK.basis()
3989 sage: t = 2*u - v; t
3990 -b
3991 sage: t.absolute_charpoly()
3992 x^4 - 6*x^2 + 9
3993 sage: t.absolute_minpoly()
3994 x^2 - 3
3995 sage: t.absolute_minpoly().parent()
3996 Univariate Polynomial Ring in x over Integer Ring
3997 """
3998 K = self.parent().number_field()
3999 R = ZZ[var]
4000 return R(K(self).absolute_minpoly(var))
4001
4002
4003
4004 class CoordinateFunction:
4005 r"""
4006 This class provides a callable object which expresses
4007 elements in terms of powers of a fixed field generator `\alpha`.
4008
4009 EXAMPLE::
4010
4011 sage: K.<a> = NumberField(x^2 + x + 3)
4012 sage: f = (a + 1).coordinates_in_terms_of_powers(); f
4013 Coordinate function that writes elements in terms of the powers of a + 1
4014 sage: f.__class__
4015 <class sage.rings.number_field.number_field_element.CoordinateFunction at ...>
4016 sage: f(a)
4017 [-1, 1]
4018 sage: f == loads(dumps(f))
4019 True
4020 """
4021 def __init__(self, NumberFieldElement alpha, W, to_V):
4022 r"""
4023 EXAMPLE::
4024
4025 sage: K.<a> = NumberField(x^2 + x + 3)
4026 sage: f = (a + 1).coordinates_in_terms_of_powers(); f # indirect doctest
4027 Coordinate function that writes elements in terms of the powers of a + 1
4028 """
4029 self.__alpha = alpha
4030 self.__W = W
4031 self.__to_V = to_V
4032 self.__K = alpha.number_field()
4033
4034 def __repr__(self):
4035 r"""
4036 EXAMPLE::
4037
4038 sage: K.<a> = NumberField(x^2 + x + 3)
4039 sage: f = (a + 1).coordinates_in_terms_of_powers(); repr(f) # indirect doctest
4040 'Coordinate function that writes elements in terms of the powers of a + 1'
4041 """
4042 return "Coordinate function that writes elements in terms of the powers of %s"%self.__alpha
4043
4044 def alpha(self):
4045 r"""
4046 EXAMPLE::
4047
4048 sage: K.<a> = NumberField(x^3 + 2)
4049 sage: (a + 2).coordinates_in_terms_of_powers().alpha()
4050 a + 2
4051 """
4052 return self.__alpha
4053
4054 def __call__(self, x):
4055 r"""
4056 EXAMPLE::
4057
4058 sage: K.<a> = NumberField(x^3 + 2)
4059 sage: f = (a + 2).coordinates_in_terms_of_powers()
4060 sage: f(1/a)
4061 [-2, 2, -1/2]
4062 sage: f(ZZ(2))
4063 [2, 0, 0]
4064 sage: L.<b> = K.extension(x^2 + 7)
4065 sage: g = (a + b).coordinates_in_terms_of_powers()
4066 sage: g(a/b)
4067 [-3379/5461, -371/10922, -4125/38227, -15/5461, -14/5461, -9/76454]
4068 sage: g(a)
4069 [4459/10922, -4838/5461, -273/5461, -980/5461, -9/10922, -42/5461]
4070 sage: f(b)
4071 Traceback (most recent call last):
4072 ...
4073 TypeError: Cannot coerce element into this number field
4074 """
4075 return self.__W.coordinates(self.__to_V(self.__K(x)))
4076
4077 def __cmp__(self, other):
4078 r"""
4079 EXAMPLE::
4080
4081 sage: K.<a> = NumberField(x^4 + 1)
4082 sage: f = (a + 1).coordinates_in_terms_of_powers()
4083 sage: f == loads(dumps(f))
4084 True
4085 sage: f == (a + 2).coordinates_in_terms_of_powers()
4086 False
4087 sage: f == NumberField(x^2 + 3,'b').gen().coordinates_in_terms_of_powers()
4088 False
4089 """
4090 return cmp(self.__class__, other.__class__) or cmp(self.__K, other.__K) or cmp(self.__alpha, other.__alpha)
4091
4092
4093
4094 #################
4095
4096 cdef void _ntl_poly(f, ZZX_c *num, ZZ_c *den):
4097 cdef long i
4098 cdef ZZ_c coeff
4099 cdef ntl_ZZX _num
4100 cdef ntl_ZZ _den
4101
4102 __den = f.denominator()
4103 (<Integer>ZZ(__den))._to_ZZ(den)
4104
4105 __num = f * __den
4106 for i from 0 <= i <= __num.degree():
4107 (<Integer>ZZ(__num[i]))._to_ZZ(&coeff)
4108 ZZX_SetCoeff( num[0], i, coeff )
4109
4110
Attached Files
To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.You are not allowed to attach a file to this page.