Attachment 'number_field_ideal.py'
Download 1 """
2 Number Field Ideals
3
4 AUTHORS:
5
6 - Steven Sivek (2005-05-16)
7
8 - William Stein (2007-09-06): vastly improved the doctesting
9
10 - William Stein and John Cremona (2007-01-28): new class
11 NumberFieldFractionalIdeal now used for all except the 0 ideal
12
13 - Radoslav Kirov and Alyson Deines (2010-06-22):
14 prime_to_S_part, is_S_unit, is_S_integral
15
16 We test that pickling works::
17
18 sage: K.<a> = NumberField(x^2 - 5)
19 sage: I = K.ideal(2/(5+a))
20 sage: I == loads(dumps(I))
21 True
22 """
23
24 #*****************************************************************************
25 # Copyright (C) 2004 William Stein <[email protected]>
26 #
27 # Distributed under the terms of the GNU General Public License (GPL)
28 #
29 # This code is distributed in the hope that it will be useful,
30 # but WITHOUT ANY WARRANTY; without even the implied warranty of
31 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
32 # General Public License for more details.
33 #
34 # The full text of the GPL is available at:
35 #
36 # http://www.gnu.org/licenses/
37 #*****************************************************************************
38
39 SMALL_DISC = 1000000
40
41 import operator
42
43 import sage.libs.all
44
45 import sage.misc.latex as latex
46
47 import sage.rings.field_element as field_element
48 import sage.rings.polynomial.polynomial_element as polynomial
49 import sage.rings.polynomial.polynomial_ring as polynomial_ring
50 import sage.rings.rational_field as rational_field
51 import sage.rings.integer_ring as integer_ring
52 import sage.rings.rational as rational
53 import sage.rings.integer as integer
54 import sage.rings.arith as arith
55 import sage.misc.misc as misc
56 from sage.rings.finite_rings.constructor import FiniteField
57
58 import number_field
59 import number_field_element
60
61 from sage.libs.all import pari_gen, PariError
62 from sage.rings.ideal import (Ideal_generic, Ideal_fractional)
63 from sage.misc.misc import prod
64 from sage.misc.mrange import xmrange_iter
65 from sage.structure.element import generic_power
66 from sage.structure.factorization import Factorization
67 from sage.structure.sequence import Sequence
68 from sage.structure.proof.proof import get_flag
69
70 QQ = rational_field.RationalField()
71 ZZ = integer_ring.IntegerRing()
72
73 def convert_from_idealprimedec_form(field, ideal):
74 """
75 Used internally in the number field ideal implementation for
76 converting from the form output by the PARI function ``idealprimedec``
77 to a Sage ideal.
78
79 INPUT:
80
81 - ``field`` - a number field
82
83 - ``ideal`` - a PARI prime ideal, as output by the
84 ``idealprimedec`` or ``idealfactor`` functions
85
86 EXAMPLE::
87
88 sage: from sage.rings.number_field.number_field_ideal import convert_from_idealprimedec_form
89 sage: K.<a> = NumberField(x^2 + 3)
90 sage: K_bnf = gp(K.pari_bnf())
91 sage: ideal = K_bnf.idealprimedec(3)[1]
92 sage: convert_from_idealprimedec_form(K, ideal)
93 Fractional ideal (-a)
94 sage: K.factor(3)
95 (Fractional ideal (-a))^2
96
97 """
98 # This indexation is very ugly and should be dealt with in #10002
99 p = ZZ(ideal[1])
100 alpha = field(field.pari_nf().getattr('zk') * ideal[2])
101 return field.ideal(p, alpha)
102
103 def convert_to_idealprimedec_form(field, ideal):
104 """
105 Used internally in the number field ideal implementation for
106 converting to the form output by the pari function ``idealprimedec``
107 from a Sage ideal.
108
109 INPUT:
110
111 - ``field`` - a number field
112
113 - ``ideal`` - a prime ideal
114
115 NOTE:
116
117 The algorithm implemented right now is not optimal, but works. It should
118 eventually be replaced with something better.
119
120 EXAMPLE::
121
122 sage: from sage.rings.number_field.number_field_ideal import convert_to_idealprimedec_form
123 sage: K.<a> = NumberField(x^2 + 3)
124 sage: P = K.ideal(a/2-3/2)
125 sage: convert_to_idealprimedec_form(K, P)
126 [3, [1, 2]~, 2, 1, [1, -1]~]
127
128 """
129 p = ideal.residue_field().characteristic()
130 from sage.interfaces.gp import gp
131 K_bnf = gp(field.pari_bnf())
132 for primedecform in K_bnf.idealprimedec(p):
133 if convert_from_idealprimedec_form(field, primedecform) == ideal:
134 return primedecform
135 raise RuntimeError
136
137 class NumberFieldIdeal(Ideal_generic):
138 """
139 An ideal of a number field.
140 """
141 def __init__(self, field, gens, coerce=True):
142 """
143 INPUT:
144
145 - ``field`` - a number field
146
147 - ``x`` - a list of NumberFieldElements belonging to the field
148
149 EXAMPLES::
150
151 sage: K.<i> = NumberField(x^2 + 1)
152 sage: K.ideal(7)
153 Fractional ideal (7)
154
155 Initialization from PARI::
156
157 sage: K.ideal(pari(7))
158 Fractional ideal (7)
159 sage: K.ideal(pari(4), pari(4 + 2*i))
160 Fractional ideal (2)
161 sage: K.ideal(pari("i + 2"))
162 Fractional ideal (i + 2)
163 sage: K.ideal(pari("[3,0;0,3]"))
164 Fractional ideal (3)
165 sage: F = pari(K).idealprimedec(5)
166 sage: K.ideal(F[0])
167 Fractional ideal (-i + 2)
168 """
169 if not isinstance(field, number_field.NumberField_generic):
170 raise TypeError, "field (=%s) must be a number field."%field
171
172 if len(gens) == 1 and isinstance(gens[0], (list, tuple)):
173 gens = gens[0]
174 if len(gens) == 1 and isinstance(gens[0], pari_gen):
175 # Init from PARI
176 gens = gens[0]
177 if gens.type() == "t_MAT":
178 # Assume columns are generators
179 gens = map(field, field.pari_zk() * gens)
180 elif gens.type() == "t_VEC":
181 # Assume prime ideal form
182 gens = [ZZ(gens.pr_get_p()), field(gens.pr_get_gen())]
183 else:
184 # Assume one element of the field
185 gens = [field(gens)]
186 if len(gens)==0:
187 raise ValueError, "gens must have length at least 1 (zero ideal is not a fractional ideal)"
188 Ideal_generic.__init__(self, field, gens, coerce)
189
190 def __hash__(self):
191 """
192 EXAMPLES::
193
194 sage: NumberField(x^2 + 1, 'a').ideal(7).__hash__()
195 -288230376151711715 # 64-bit
196 -67108835 # 32-bit
197 """
198 try: return self._hash
199 # At some point in the future (e.g., for relative extensions), we'll likely
200 # have to consider other hashes, like the following.
201 #except AttributeError: self._hash = hash(self.gens())
202 except AttributeError: self._hash = self.pari_hnf().__hash__()
203 return self._hash
204
205 def _latex_(self):
206 """
207 EXAMPLES::
208
209 sage: K.<a> = NumberField(x^2 + 23)
210 sage: K.ideal([2, 1/2*a - 1/2])._latex_()
211 '\\left(2, \\frac{1}{2} a - \\frac{1}{2}\\right)'
212 sage: latex(K.ideal([2, 1/2*a - 1/2]))
213 \left(2, \frac{1}{2} a - \frac{1}{2}\right)
214
215 The gens are reduced only if the norm of the discriminant of
216 the defining polynomial is at most
217 sage.rings.number_field.number_field_ideal.SMALL_DISC::
218
219 sage: K.<a> = NumberField(x^2 + 902384092834); K
220 Number Field in a with defining polynomial x^2 + 902384092834
221 sage: I = K.factor(19)[0][0]; I._latex_()
222 '\\left(19\\right)'
223
224 We can make the generators reduced by increasing SMALL_DISC.
225 We had better also set proof to False, or computing reduced
226 gens could take too long::
227
228 sage: proof.number_field(False)
229 sage: sage.rings.number_field.number_field_ideal.SMALL_DISC = 10^20
230 sage: K.<a> = NumberField(x^4 + 3*x^2 - 17)
231 sage: K.ideal([17*a,17,17,17*a])._latex_()
232 '\\left(17\\right)'
233 """
234 return '\\left(%s\\right)'%(", ".join(map(latex.latex, self._gens_repr())))
235
236 def __cmp__(self, other):
237 """
238 Compare an ideal of a number field to something else.
239
240 EXAMPLES::
241
242 sage: K.<a> = NumberField(x^2 + 3); K
243 Number Field in a with defining polynomial x^2 + 3
244 sage: f = K.factor(15); f
245 (Fractional ideal (-a))^2 * (Fractional ideal (5))
246 sage: cmp(f[0][0], f[1][0])
247 -1
248 sage: cmp(f[0][0], f[0][0])
249 0
250 sage: cmp(f[1][0], f[0][0])
251 1
252 sage: f[1][0] == 5
253 True
254 sage: f[1][0] == GF(7)(5)
255 False
256 """
257 if not isinstance(other, NumberFieldIdeal):
258 return cmp(type(self), type(other))
259 return cmp(self.pari_hnf(), other.pari_hnf())
260
261 def coordinates(self, x):
262 r"""
263 Returns the coordinate vector of `x` with respect to this ideal.
264
265 INPUT:
266 ``x`` -- an element of the number field (or ring of integers) of this ideal.
267
268 OUTPUT:
269 A vector of length `n` (the degree of the field) giving
270 the coordinates of `x` with respect to the integral basis
271 of the ideal. In general this will be a vector of
272 rationals; it will consist of integers if and only if `x`
273 is in the ideal.
274
275 AUTHOR: John Cremona 2008-10-31
276
277 ALGORITHM:
278
279 Uses linear algebra. The change-of-basis matrix is cached.
280 Provides simpler implementations for ``_contains_()``,
281 ``is_integral()`` and ``smallest_integer()``.
282
283 EXAMPLES::
284
285 sage: K.<i> = QuadraticField(-1)
286 sage: I = K.ideal(7+3*i)
287 sage: Ibasis = I.integral_basis(); Ibasis
288 [58, i + 41]
289 sage: a = 23-14*i
290 sage: acoords = I.coordinates(a); acoords
291 (597/58, -14)
292 sage: sum([Ibasis[j]*acoords[j] for j in range(2)]) == a
293 True
294 sage: b = 123+456*i
295 sage: bcoords = I.coordinates(b); bcoords
296 (-18573/58, 456)
297 sage: sum([Ibasis[j]*bcoords[j] for j in range(2)]) == b
298 True
299 """
300 K = self.number_field()
301 V, from_V, to_V = K.absolute_vector_space()
302
303 try:
304 M = self.__basis_matrix_inverse
305 except AttributeError:
306 from sage.matrix.constructor import Matrix
307 self.__basis_matrix_inverse = Matrix(map(to_V, self.integral_basis())).inverse()
308 M = self.__basis_matrix_inverse
309 return to_V(K(x))*M
310
311 def _contains_(self, x):
312 """
313 Return True if x is an element of this ideal.
314
315 This function is called (indirectly) when the ``in`` operator is used.
316
317 EXAMPLES::
318
319 sage: K.<a> = NumberField(x^2 + 23); K
320 Number Field in a with defining polynomial x^2 + 23
321 sage: I = K.factor(13)[0][0]; I
322 Fractional ideal (13, 1/2*a + 9/2)
323 sage: I._contains_(a)
324 False
325 sage: a in I
326 False
327 sage: 13 in I
328 True
329 sage: 13/2 in I
330 False
331 sage: a + 9 in I
332 True
333
334 sage: K.<a> = NumberField(x^4 + 3); K
335 Number Field in a with defining polynomial x^4 + 3
336 sage: I = K.factor(13)[0][0]
337 sage: I # random sign in output
338 Fractional ideal (-2*a^2 - 1)
339 sage: 2/3 in I
340 False
341 sage: 1 in I
342 False
343 sage: 13 in I
344 True
345 sage: 1 in I*I^(-1)
346 True
347 sage: I # random sign in output
348 Fractional ideal (-2*a^2 - 1)
349 """
350 return self.coordinates(self.number_field()(x)).denominator() == 1
351
352 def __elements_from_hnf(self, hnf):
353 """
354 Convert a PARI Hermite normal form matrix to a list of
355 NumberFieldElements.
356
357 EXAMPLES::
358
359 sage: K.<a> = NumberField(x^3 + 389); K
360 Number Field in a with defining polynomial x^3 + 389
361 sage: I = K.factor(17)[0][0]
362 sage: I # random sign in generator
363 Fractional ideal (-100*a^2 + 730*a - 5329)
364 sage: hnf = I.pari_hnf(); hnf
365 [17, 0, 13; 0, 17, 8; 0, 0, 1]
366 sage: I._NumberFieldIdeal__elements_from_hnf(hnf)
367 [17, 17*a, a^2 + 8*a + 13]
368 sage: I._NumberFieldIdeal__elements_from_hnf(hnf^(-1))
369 [1/17, 1/17*a, a^2 - 8/17*a - 13/17]
370 """
371 K = self.number_field()
372 return map(K, K.pari_zk() * hnf)
373
374 def __repr__(self):
375 """
376 Return the string representation of this number field ideal.
377
378 .. note::
379
380 Only the zero ideal actually has type NumberFieldIdeal; all
381 others have type NumberFieldFractionalIdeal. So this function
382 will only ever be called on the zero ideal.
383
384 EXAMPLES::
385
386 sage: K.<a> = NumberField(x^3-2)
387 sage: I = K.ideal(0); I
388 Ideal (0) of Number Field in a with defining polynomial x^3 - 2
389 sage: type(I)
390 <class 'sage.rings.number_field.number_field_ideal.NumberFieldIdeal'>
391 sage: I = K.ideal(1); I
392 Fractional ideal (1)
393 sage: type(I)
394 <class 'sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal'>
395 sage: I = K.ideal(a); I
396 Fractional ideal (a)
397 sage: type(I)
398 <class 'sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal'>
399 sage: I = K.ideal(1/a); I
400 Fractional ideal (1/2*a^2)
401 sage: type(I)
402 <class 'sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal'>
403 """
404 return "Ideal %s of %s"%(self._repr_short(), self.number_field())
405
406 def _repr_short(self):
407 """
408 Compact string representation of this ideal. When the norm of
409 the discriminant of the defining polynomial of the number field
410 is less than
411
412 sage.rings.number_field.number_field_ideal.SMALL_DISC
413
414 then display reduced generators. Otherwise display two
415 generators.
416
417 EXAMPLES::
418
419 sage: K.<a> = NumberField(x^4 + 389); K
420 Number Field in a with defining polynomial x^4 + 389
421 sage: I = K.factor(17)[0][0]; I
422 Fractional ideal (17, a^2 - 6)
423 sage: I._repr_short()
424 '(17, a^2 - 6)'
425
426 We use reduced gens, because the discriminant is small::
427
428 sage: K.<a> = NumberField(x^2 + 17); K
429 Number Field in a with defining polynomial x^2 + 17
430 sage: I = K.factor(17)[0][0]; I
431 Fractional ideal (-a)
432
433 Here the discriminant is 'large', so the gens aren't reduced::
434
435 sage: sage.rings.number_field.number_field_ideal.SMALL_DISC
436 1000000
437 sage: K.<a> = NumberField(x^2 + 902384094); K
438 Number Field in a with defining polynomial x^2 + 902384094
439 sage: I = K.factor(19)[0][0]; I
440 Fractional ideal (19, a + 14)
441 sage: I.gens_reduced() # long time
442 (19, a + 14)
443 """
444 return '(%s)'%(', '.join(map(str, self._gens_repr())))
445
446 def _gens_repr(self):
447 """
448 Returns tuple of generators to be used for printing this number
449 field ideal. The gens are reduced only if the absolute value of
450 the norm of the discriminant of the defining polynomial is at
451 most sage.rings.number_field.number_field_ideal.SMALL_DISC.
452
453 EXAMPLES::
454
455 sage: sage.rings.number_field.number_field_ideal.SMALL_DISC
456 1000000
457 sage: K.<a> = NumberField(x^4 + 3*x^2 - 17)
458 sage: K.discriminant() # too big
459 -1612688
460 sage: I = K.ideal([17*a*(2*a-2),17*a*(2*a-3)]); I._gens_repr()
461 (289, 17*a)
462 sage: I.gens_reduced()
463 (17*a,)
464 """
465 # If the discriminant is small, it is easy to find nice gens.
466 # Otherwise it is potentially very hard.
467 try:
468 if abs(self.number_field().defining_polynomial().discriminant().norm()) <= SMALL_DISC:
469 return self.gens_reduced()
470 except TypeError:
471 # In some cases with relative extensions, computing the
472 # discriminant of the defining polynomial is not
473 # supported.
474 pass
475 # Return two generators unless the second one is zero
476 two_gens = self.gens_two()
477 if two_gens[1]:
478 return two_gens
479 else:
480 return (two_gens[0],)
481
482 def _pari_(self):
483 """
484 Returns PARI Hermite Normal Form representations of this
485 ideal.
486
487 EXAMPLES::
488
489 sage: K.<w> = NumberField(x^2 + 23)
490 sage: I = K.class_group().0.ideal(); I
491 Fractional ideal (2, 1/2*w - 1/2)
492 sage: I._pari_()
493 [2, 0; 0, 1]
494 """
495 return self.pari_hnf()
496
497 def _pari_init_(self):
498 """
499 Returns self in PARI Hermite Normal Form as a string
500
501 EXAMPLES::
502
503 sage: K.<w> = NumberField(x^2 + 23)
504 sage: I = K.class_group().0.ideal()
505 sage: I._pari_init_()
506 '[2, 0; 0, 1]'
507 """
508 return str(self._pari_())
509
510 def pari_hnf(self):
511 """
512 Return PARI's representation of this ideal in Hermite normal form.
513
514 EXAMPLES::
515
516 sage: R.<x> = PolynomialRing(QQ)
517 sage: K.<a> = NumberField(x^3 - 2)
518 sage: I = K.ideal(2/(5+a))
519 sage: I.pari_hnf()
520 [2, 0, 50/127; 0, 2, 244/127; 0, 0, 2/127]
521 """
522 try:
523 return self.__pari_hnf
524 except AttributeError:
525 nf = self.number_field().pari_nf()
526 self.__pari_hnf = nf.idealhnf(0)
527 hnflist = [ nf.idealhnf(x.polynomial()) for x in self.gens() ]
528 for ideal in hnflist:
529 self.__pari_hnf = nf.idealadd(self.__pari_hnf, ideal)
530 return self.__pari_hnf
531
532 def basis(self):
533 r"""
534 Return an immutable sequence of elements of this ideal (note:
535 their parent is the number field) that form a basis for this
536 ideal viewed as a `\ZZ` -module.
537
538 OUTPUT:
539 basis -- an immutable sequence.
540
541 EXAMPLES::
542
543 sage: K.<z> = CyclotomicField(7)
544 sage: I = K.factor(11)[0][0]
545 sage: I.basis() # warning -- choice of basis can be somewhat random
546 [11, 11*z, 11*z^2, z^3 + 5*z^2 + 4*z + 10, z^4 + z^2 + z + 5, z^5 + z^4 + z^3 + 2*z^2 + 6*z + 5]
547
548 An example of a non-integral ideal.::
549
550 sage: J = 1/I
551 sage: J # warning -- choice of generators can be somewhat random
552 Fractional ideal (2/11*z^5 + 2/11*z^4 + 3/11*z^3 + 2/11)
553 sage: J.basis() # warning -- choice of basis can be somewhat random
554 [1, z, z^2, 1/11*z^3 + 7/11*z^2 + 6/11*z + 10/11, 1/11*z^4 + 1/11*z^2 + 1/11*z + 7/11, 1/11*z^5 + 1/11*z^4 + 1/11*z^3 + 2/11*z^2 + 8/11*z + 7/11]
555 """
556 try:
557 return self.__basis
558 except AttributeError:
559 pass
560 hnf = self.pari_hnf()
561 v = self.__elements_from_hnf(hnf)
562 O = self.number_field().maximal_order()
563 self.__basis = Sequence(v, immutable=True)
564 return self.__basis
565
566 def free_module(self):
567 r"""
568 Return the free `\ZZ`-module contained in the vector space
569 associated to the ambient number field, that corresponds
570 to this ideal.
571
572 EXAMPLES::
573
574 sage: K.<z> = CyclotomicField(7)
575 sage: I = K.factor(11)[0][0]; I
576 Fractional ideal (-2*z^4 - 2*z^2 - 2*z + 1)
577 sage: A = I.free_module()
578 sage: A # warning -- choice of basis can be somewhat random
579 Free module of degree 6 and rank 6 over Integer Ring
580 User basis matrix:
581 [11 0 0 0 0 0]
582 [ 0 11 0 0 0 0]
583 [ 0 0 11 0 0 0]
584 [10 4 5 1 0 0]
585 [ 5 1 1 0 1 0]
586 [ 5 6 2 1 1 1]
587
588 However, the actual `\ZZ`-module is not at all random::
589
590 sage: A.basis_matrix().change_ring(ZZ).echelon_form()
591 [ 1 0 0 5 1 1]
592 [ 0 1 0 1 1 7]
593 [ 0 0 1 7 6 10]
594 [ 0 0 0 11 0 0]
595 [ 0 0 0 0 11 0]
596 [ 0 0 0 0 0 11]
597
598 The ideal doesn't have to be integral::
599
600 sage: J = I^(-1)
601 sage: B = J.free_module()
602 sage: B.echelonized_basis_matrix()
603 [ 1/11 0 0 7/11 1/11 1/11]
604 [ 0 1/11 0 1/11 1/11 5/11]
605 [ 0 0 1/11 5/11 4/11 10/11]
606 [ 0 0 0 1 0 0]
607 [ 0 0 0 0 1 0]
608 [ 0 0 0 0 0 1]
609
610 This also works for relative extensions::
611
612 sage: K.<a,b> = NumberField([x^2 + 1, x^2 + 2])
613 sage: I = K.fractional_ideal(4)
614 sage: I.free_module()
615 Free module of degree 4 and rank 4 over Integer Ring
616 User basis matrix:
617 [ 4 0 0 0]
618 [ -3 7 -1 1]
619 [ 3 7 1 1]
620 [ 0 -10 0 -2]
621 sage: J = I^(-1); J.free_module()
622 Free module of degree 4 and rank 4 over Integer Ring
623 User basis matrix:
624 [ 1/4 0 0 0]
625 [-3/16 7/16 -1/16 1/16]
626 [ 3/16 7/16 1/16 1/16]
627 [ 0 -5/8 0 -1/8]
628
629 An example of intersecting ideals by intersecting free modules.::
630
631 sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
632 sage: I = K.factor(2)
633 sage: p1 = I[0][0]; p2 = I[1][0]
634 sage: N = p1.free_module().intersection(p2.free_module()); N
635 Free module of degree 3 and rank 3 over Integer Ring
636 Echelon basis matrix:
637 [ 1 1/2 1/2]
638 [ 0 1 1]
639 [ 0 0 2]
640 sage: N.index_in(p1.free_module()).abs()
641 2
642
643 TESTS:
644
645 Sage can find the free module associated to quite large ideals
646 quickly (see trac #4627)::
647
648 sage: y = polygen(ZZ)
649 sage: M.<a> = NumberField(y^20 - 2*y^19 + 10*y^17 - 15*y^16 + 40*y^14 - 64*y^13 + 46*y^12 + 8*y^11 - 32*y^10 + 8*y^9 + 46*y^8 - 64*y^7 + 40*y^6 - 15*y^4 + 10*y^3 - 2*y + 1)
650 sage: M.ideal(prod(prime_range(6000, 6200))).free_module()
651 Free module of degree 20 and rank 20 over Integer Ring
652 User basis matrix:
653 20 x 20 dense matrix over Rational Field
654 """
655 try:
656 return self.__free_module
657 except AttributeError:
658 pass
659 M = basis_to_module(self.basis(), self.number_field())
660 self.__free_module = M
661 return M
662
663 def reduce_equiv(self):
664 """
665 Return a small ideal that is equivalent to self in the group
666 of fractional ideals modulo principal ideals. Very often (but
667 not always) if self is principal then this function returns
668 the unit ideal.
669
670 ALGORITHM: Calls pari's idealred function.
671
672 EXAMPLES::
673
674 sage: K.<w> = NumberField(x^2 + 23)
675 sage: I = ideal(w*23^5); I
676 Fractional ideal (6436343*w)
677 sage: I.reduce_equiv()
678 Fractional ideal (1)
679 sage: I = K.class_group().0.ideal()^10; I
680 Fractional ideal (1024, 1/2*w + 979/2)
681 sage: I.reduce_equiv()
682 Fractional ideal (2, 1/2*w - 1/2)
683 """
684 K = self.number_field()
685 P = K.pari_nf()
686 hnf = P.idealred(self.pari_hnf())
687 gens = self.__elements_from_hnf(hnf)
688 return K.ideal(gens)
689
690 def gens_reduced(self, proof=None):
691 r"""
692 Express this ideal in terms of at most two generators, and one
693 if possible.
694
695 This function indirectly uses ``bnfisprincipal``, so set
696 ``proof=True`` if you want to prove correctness (which *is* the
697 default).
698
699 EXAMPLES::
700
701 sage: R.<x> = PolynomialRing(QQ)
702 sage: K.<a> = NumberField(x^2 + 5)
703 sage: J = K.ideal([a+2, 9])
704 sage: J.gens()
705 (a + 2, 9)
706 sage: J.gens_reduced() # random sign
707 (a + 2,)
708 sage: K.ideal([a+2, 3]).gens_reduced()
709 (3, a + 2)
710
711 TESTS::
712
713 sage: len(J.gens_reduced()) == 1
714 True
715
716 sage: all(j.parent() is K for j in J.gens())
717 True
718 sage: all(j.parent() is K for j in J.gens_reduced())
719 True
720
721 sage: K.<a> = NumberField(x^4 + 10*x^2 + 20)
722 sage: J = K.prime_above(5)
723 sage: J.is_principal()
724 False
725 sage: J.gens_reduced()
726 (5, a)
727 sage: all(j.parent() is K for j in J.gens())
728 True
729 sage: all(j.parent() is K for j in J.gens_reduced())
730 True
731 """
732 proof = get_flag(proof, "number_field")
733 try:
734 return self.__reduced_generators
735 except AttributeError:
736 # Compute the single generator, if it exists
737 if self.is_principal(proof):
738 return self.__reduced_generators
739 else:
740 return self.gens_two()
741
742 def gens_two(self):
743 r"""
744 Express this ideal using exactly two generators, the first of
745 which is a generator for the intersection of the ideal with `Q`.
746
747 ALGORITHM: uses PARI's ``idealtwoelt`` function, which runs in
748 randomized polynomial time and is very fast in practice.
749
750 EXAMPLES::
751
752 sage: R.<x> = PolynomialRing(QQ)
753 sage: K.<a> = NumberField(x^2 + 5)
754 sage: J = K.ideal([a+2, 9])
755 sage: J.gens()
756 (a + 2, 9)
757 sage: J.gens_two()
758 (9, a + 2)
759 sage: K.ideal([a+5, a+8]).gens_two()
760 (3, a + 2)
761
762 The second generator is zero if and only if the ideal is
763 generated by a rational, in contrast to the PARI function
764 ``idealtwoelt()``::
765
766 sage: I = K.ideal(12)
767 sage: pari(K).idealtwoelt(I) # Note that second element is not zero
768 [12, [0, 12]~]
769 sage: I.gens_two()
770 (12, 0)
771
772 """
773 try:
774 return self.__two_generators
775 except AttributeError:
776 K = self.number_field()
777 HNF = self.pari_hnf()
778 # Check whether the ideal is generated by an integer, i.e.
779 # whether HNF is a multiple of the identity matrix
780 if HNF.gequal(HNF[0,0]):
781 a = HNF[0,0]; alpha = 0
782 else:
783 a, alpha = K.pari_nf().idealtwoelt(HNF)
784 self.__two_generators = (K(a), K(alpha))
785 return self.__two_generators
786
787 def integral_basis(self):
788 r"""
789 Return a list of generators for this ideal as a `\ZZ`-module.
790
791 EXAMPLES::
792
793 sage: R.<x> = PolynomialRing(QQ)
794 sage: K.<i> = NumberField(x^2 + 1)
795 sage: J = K.ideal(i+1)
796 sage: J.integral_basis()
797 [2, i + 1]
798 """
799 hnf = self.pari_hnf()
800 return self.__elements_from_hnf(hnf)
801
802 def integral_split(self):
803 r"""
804 Return a tuple `(I, d)`, where `I` is an integral ideal, and `d` is the
805 smallest positive integer such that this ideal is equal to `I/d`.
806
807 EXAMPLES::
808
809 sage: R.<x> = PolynomialRing(QQ)
810 sage: K.<a> = NumberField(x^2-5)
811 sage: I = K.ideal(2/(5+a))
812 sage: I.is_integral()
813 False
814 sage: J,d = I.integral_split()
815 sage: J
816 Fractional ideal (-1/2*a + 5/2)
817 sage: J.is_integral()
818 True
819 sage: d
820 5
821 sage: I == J/d
822 True
823 """
824 try:
825 return self.__integral_split
826 except AttributeError:
827 if self.is_integral():
828 self.__integral_split = (self, ZZ(1))
829 else:
830 factors = self.factor()
831 denom_list = filter(lambda (p,e): e < 0 , factors)
832 denominator = prod([ p.smallest_integer()**(-e)
833 for (p,e) in denom_list ])
834 ## Get a list of the primes dividing the denominator
835 plist = [ p.smallest_integer() for (p,e) in denom_list ]
836 for p in plist:
837 while denominator % p == 0 and (self*(denominator/p)).is_integral():
838 denominator //= p
839 self.__integral_split = (self*denominator, denominator)
840 return self.__integral_split
841
842 def intersection(self, other):
843 r"""
844 Return the intersection of self and other.
845
846 EXAMPLE::
847
848 sage: K.<a> = QuadraticField(-11)
849 sage: p = K.ideal((a + 1)/2); q = K.ideal((a + 3)/2)
850 sage: p.intersection(q) == q.intersection(p) == K.ideal(a-2)
851 True
852
853 An example with non-principal ideals::
854
855 sage: L.<a> = NumberField(x^3 - 7)
856 sage: p = L.ideal(a^2 + a + 1, 2)
857 sage: q = L.ideal(a+1)
858 sage: p.intersection(q) == L.ideal(8, 2*a + 2)
859 True
860
861 A relative example::
862
863 sage: L.<a,b> = NumberField([x^2 + 11, x^2 - 5])
864 sage: A = L.ideal([15, (-3/2*b + 7/2)*a - 8])
865 sage: B = L.ideal([6, (-1/2*b + 1)*a - b - 5/2])
866 sage: A.intersection(B) == L.ideal(-1/2*a - 3/2*b - 1)
867 True
868 """
869 L = self.number_field()
870 other = L.ideal(other)
871 nf = L.pari_nf()
872 hnf = nf.idealintersection(self.pari_hnf(), other.pari_hnf())
873 I = L.ideal(self._NumberFieldIdeal__elements_from_hnf(hnf))
874 I.__pari_hnf = hnf
875 return I
876
877 def is_integral(self):
878 """
879 Return True if this ideal is integral.
880
881 EXAMPLES::
882
883 sage: R.<x> = PolynomialRing(QQ)
884 sage: K.<a> = NumberField(x^5-x+1)
885 sage: K.ideal(a).is_integral()
886 True
887 sage: (K.ideal(1) / (3*a+1)).is_integral()
888 False
889 """
890 try:
891 return self.__is_integral
892 except AttributeError:
893 one = self.number_field().ideal(1)
894 self.__is_integral = all([a in one for a in self.integral_basis()])
895 return self.__is_integral
896
897 def is_maximal(self):
898 """
899 Return True if this ideal is maximal. This is equivalent to
900 self being prime and nonzero.
901
902 EXAMPLES::
903
904 sage: K.<a> = NumberField(x^3 + 3); K
905 Number Field in a with defining polynomial x^3 + 3
906 sage: K.ideal(5).is_maximal()
907 False
908 sage: K.ideal(7).is_maximal()
909 True
910 """
911 return self.is_prime() and not self.is_zero()
912
913 def is_prime(self):
914 """
915 Return True if this ideal is prime.
916
917 EXAMPLES::
918
919 sage: K.<a> = NumberField(x^2 - 17); K
920 Number Field in a with defining polynomial x^2 - 17
921 sage: K.ideal(5).is_prime()
922 True
923 sage: K.ideal(13).is_prime()
924 False
925 sage: K.ideal(17).is_prime()
926 False
927 """
928 try:
929 return self._pari_prime is not None
930 except AttributeError:
931 K = self.number_field()
932 F = list(K.pari_nf().idealfactor(self.pari_hnf()))
933 ### We should definitely cache F as the factorization of self
934 P, exps = F[0], F[1]
935 if len(P) != 1 or exps[0] != 1:
936 self._pari_prime = None
937 else:
938 self._pari_prime = P[0]
939 return self._pari_prime is not None
940
941 def is_principal(self, proof=None):
942 r"""
943 Return True if this ideal is principal.
944
945 Since it uses the PARI method ``bnfisprincipal``, specify
946 ``proof=True`` (this is the default setting) to prove the correctness
947 of the output.
948
949 EXAMPLES:
950
951 sage: K = QuadraticField(-119,'a')
952 sage: P = K.factor(2)[1][0]
953 sage: P.is_principal()
954 False
955 sage: I = P^5
956 sage: I.is_principal()
957 True
958 sage: I # random
959 Fractional ideal (-1/2*a + 3/2)
960 sage: P = K.ideal([2]).factor()[1][0]
961 sage: I = P^5
962 sage: I.is_principal()
963 True
964 """
965 proof = get_flag(proof, "number_field")
966 try:
967 return self.__is_principal
968 except AttributeError:
969 if len (self.gens()) <= 1:
970 self.__is_principal = True
971 self.__reduced_generators = self.gens()
972 return self.__is_principal
973 bnf = self.number_field().pari_bnf(proof)
974 v = bnf.bnfisprincipal(self.pari_hnf())
975 self.__is_principal = not any(v[0])
976 if self.__is_principal:
977 K = self.number_field()
978 g = K(v[1])
979 self.__reduced_generators = tuple([g])
980 return self.__is_principal
981
982 def _ideal_class_log(self, proof=None):
983 r"""
984 Return the output of Pari's 'bnfisprincipal' for this ideal,
985 i.e. a vector expressing the class of this ideal in terms of a
986 set of generators for the class group.
987
988 EXAMPLE::
989
990 sage: K.<a, b> = NumberField([x^3 - x + 1, x^2 + 26])
991 sage: K.primes_above(7)[0]._ideal_class_log() # random
992 [1, 2]
993 """
994 proof = get_flag(proof, "number_field")
995 try:
996 return self.__ideal_class_log[proof]
997 except AttributeError:
998 self.__ideal_class_log = {}
999 return self._ideal_class_log(proof)
1000 except KeyError:
1001 bnf = self.number_field().pari_bnf(proof)
1002 v = bnf.bnfisprincipal(self.pari_hnf())
1003 self.__ideal_class_log[proof] = list(v[0])
1004 return self.__ideal_class_log[proof]
1005
1006 def is_zero(self):
1007 """
1008 Return True iff self is the zero ideal
1009
1010 EXAMPLES::
1011
1012 sage: K.<a> = NumberField(x^2 + 2); K
1013 Number Field in a with defining polynomial x^2 + 2
1014 sage: K.ideal(3).is_zero()
1015 False
1016 sage: I=K.ideal(0); I.is_zero()
1017 True
1018 sage: I
1019 Ideal (0) of Number Field in a with defining polynomial x^2 + 2
1020
1021 (0 is a NumberFieldIdeal, not a NumberFieldFractionIdeal)
1022 """
1023 return self == self.number_field().ideal(0)
1024
1025 def norm(self):
1026 """
1027 Return the norm of this fractional ideal as a rational number.
1028
1029 EXAMPLES::
1030
1031 sage: K.<a> = NumberField(x^4 + 23); K
1032 Number Field in a with defining polynomial x^4 + 23
1033 sage: I = K.ideal(19); I
1034 Fractional ideal (19)
1035 sage: factor(I.norm())
1036 19^4
1037 sage: F = I.factor()
1038 sage: F[0][0].norm().factor()
1039 19^2
1040 """
1041 try:
1042 return self._norm
1043 except AttributeError:
1044 pass
1045 self._norm = QQ(self.number_field().pari_nf().idealnorm(self.pari_hnf()))
1046 return self._norm
1047
1048 # synonyms (using terminology of relative number fields)
1049
1050 def absolute_norm(self):
1051 """
1052 A synonym for norm.
1053
1054 EXAMPLES::
1055
1056 sage: K.<i> = NumberField(x^2 + 1)
1057 sage: K.ideal(1 + 2*i).absolute_norm()
1058 5
1059 """
1060 return self.norm()
1061
1062 def relative_norm(self):
1063 """
1064 A synonym for norm.
1065
1066 EXAMPLES::
1067
1068 sage: K.<i> = NumberField(x^2 + 1)
1069 sage: K.ideal(1 + 2*i).relative_norm()
1070 5
1071 """
1072 return self.norm()
1073
1074 def absolute_ramification_index(self):
1075 """
1076 A synonym for ramification_index.
1077
1078 EXAMPLES::
1079
1080 sage: K.<i> = NumberField(x^2 + 1)
1081 sage: K.ideal(1 + i).absolute_ramification_index()
1082 2
1083 """
1084 return self.ramification_index()
1085
1086 def relative_ramification_index(self):
1087 """
1088 A synonym for ramification_index.
1089
1090 EXAMPLES::
1091
1092 sage: K.<i> = NumberField(x^2 + 1)
1093 sage: K.ideal(1 + i).relative_ramification_index()
1094 2
1095 """
1096 return self.ramification_index()
1097
1098 def number_field(self):
1099 """
1100 Return the number field that this is a fractional ideal in.
1101
1102 EXAMPLES::
1103
1104 sage: K.<a> = NumberField(x^2 + 2); K
1105 Number Field in a with defining polynomial x^2 + 2
1106 sage: K.ideal(3).number_field()
1107 Number Field in a with defining polynomial x^2 + 2
1108 sage: K.ideal(0).number_field() # not tested (not implemented)
1109 Number Field in a with defining polynomial x^2 + 2
1110 """
1111 return self.ring()
1112
1113 def smallest_integer(self):
1114 r"""
1115 Return the smallest non-negative integer in `I \cap \ZZ`,
1116 where `I` is this ideal. If `I = 0`, returns 0.
1117
1118 EXAMPLES::
1119
1120 sage: R.<x> = PolynomialRing(QQ)
1121 sage: K.<a> = NumberField(x^2+6)
1122 sage: I = K.ideal([4,a])/7; I
1123 Fractional ideal (2/7, 1/7*a)
1124 sage: I.smallest_integer()
1125 2
1126
1127 TESTS::
1128
1129 sage: K.<i> = QuadraticField(-1)
1130 sage: P1, P2 = [P for P,e in K.factor(13)]
1131 sage: all([(P1^i*P2^j).smallest_integer() == 13^max(i,j,0) for i in range(-3,3) for j in range(-3,3)])
1132 True
1133 sage: I = K.ideal(0)
1134 sage: I.smallest_integer()
1135 0
1136
1137 # See trac\# 4392:
1138 sage: K.<a>=QuadraticField(-5)
1139 sage: I=K.ideal(7)
1140 sage: I.smallest_integer()
1141 7
1142
1143 sage: K.<z> = CyclotomicField(13)
1144 sage: a = K([-8, -4, -4, -6, 3, -4, 8, 0, 7, 4, 1, 2])
1145 sage: I = K.ideal(a)
1146 sage: I.smallest_integer()
1147 146196692151
1148 sage: I.norm()
1149 1315770229359
1150 sage: I.norm() / I.smallest_integer()
1151 9
1152 """
1153 if self.is_zero():
1154 return ZZ(0)
1155
1156 # There is no need for caching since pari_hnf() is already cached.
1157 q = self.pari_hnf()[0,0] # PARI integer or rational
1158 return ZZ(q.numerator())
1159
1160 #Old code by John Cremona, 2008-10-30, using the new coordinates()
1161 #function instead of factorization.
1162 #
1163 #Idea: We write 1 as a Q-linear combination of the Z-basis of self,
1164 #and return the denominator of this vector.
1165 #
1166 #self.__smallest_integer = self.coordinates(1).denominator()
1167 #return self.__smallest_integer
1168
1169 def valuation(self, p):
1170 r"""
1171 Return the valuation of self at ``p``.
1172
1173 INPUT:
1174
1175 - ``p`` -- a prime ideal `\mathfrak{p}` of this number field.
1176
1177 OUTPUT:
1178
1179 (integer) The valuation of this fractional ideal at the prime
1180 `\mathfrak{p}`. If `\mathfrak{p}` is not prime, raise a
1181 ValueError.
1182
1183 EXAMPLES::
1184
1185 sage: K.<a> = NumberField(x^5 + 2); K
1186 Number Field in a with defining polynomial x^5 + 2
1187 sage: i = K.ideal(38); i
1188 Fractional ideal (38)
1189 sage: i.valuation(K.factor(19)[0][0])
1190 1
1191 sage: i.valuation(K.factor(2)[0][0])
1192 5
1193 sage: i.valuation(K.factor(3)[0][0])
1194 0
1195 sage: i.valuation(0)
1196 Traceback (most recent call last):
1197 ...
1198 ValueError: p (= 0) must be nonzero
1199 """
1200 if p==0:
1201 raise ValueError, "p (= %s) must be nonzero"%p
1202 if not isinstance(p, NumberFieldFractionalIdeal):
1203 p = self.number_field().ideal(p)
1204 if not p.is_prime():
1205 raise ValueError, "p (= %s) must be a prime"%p
1206 if p.ring() != self.number_field():
1207 raise ValueError, "p (= %s) must be an ideal in %s"%self.number_field()
1208 nf = self.number_field().pari_nf()
1209 return ZZ(nf.idealval(self.pari_hnf(), p._pari_prime))
1210
1211 def decomposition_group(self):
1212 r"""
1213 Return the decomposition group of self, as a subset of the
1214 automorphism group of the number field of self. Raises an
1215 error if the field isn't Galois. See the decomposition_group
1216 method of the ``GaloisGroup_v2`` class for further examples
1217 and doctests.
1218
1219 EXAMPLE::
1220
1221 sage: QuadraticField(-23, 'w').primes_above(7)[0].decomposition_group()
1222 Galois group of Number Field in w with defining polynomial x^2 + 23
1223 """
1224 return self.number_field().galois_group().decomposition_group(self)
1225
1226 def ramification_group(self, v):
1227 r"""
1228 Return the `v`'th ramification group of self, i.e. the set of
1229 elements `s` of the Galois group of the number field of self
1230 (which we assume is Galois) such that `s` acts trivially
1231 modulo the `(v+1)`'st power of self. See the
1232 ramification_group method of the ``GaloisGroup`` class for
1233 further examples and doctests.
1234
1235 EXAMPLE::
1236
1237 sage: QuadraticField(-23, 'w').primes_above(23)[0].ramification_group(0)
1238 Galois group of Number Field in w with defining polynomial x^2 + 23
1239 sage: QuadraticField(-23, 'w').primes_above(23)[0].ramification_group(1)
1240 Subgroup [()] of Galois group of Number Field in w with defining polynomial x^2 + 23
1241 """
1242
1243 return self.number_field().galois_group().ramification_group(self, v)
1244
1245 def inertia_group(self):
1246 r"""
1247 Return the inertia group of self, i.e. the set of elements s of the
1248 Galois group of the number field of self (which we assume is Galois)
1249 such that s acts trivially modulo self. This is the same as the 0th
1250 ramification group of self. See the inertia_group method of the
1251 ``GaloisGroup_v2`` class for further examples and doctests.
1252
1253 EXAMPLE::
1254
1255 sage: QuadraticField(-23, 'w').primes_above(23)[0].inertia_group()
1256 Galois group of Number Field in w with defining polynomial x^2 + 23
1257 """
1258 return self.ramification_group(0)
1259
1260 def random_element(self, *args, **kwds):
1261 """
1262 Return a random element of this order.
1263
1264 INPUT:
1265
1266 - ``*args``, ``*kwds`` - Parameters passed to the random integer
1267 function. See the documentation of ``ZZ.random_element()`` for
1268 details.
1269
1270 OUTPUT:
1271
1272 A random element of this fractional ideal, computed as a random
1273 `\ZZ`-linear combination of the basis.
1274
1275 EXAMPLES::
1276
1277 sage: K.<a> = NumberField(x^3 + 2)
1278 sage: I = K.ideal(1-a)
1279 sage: I.random_element() # random output
1280 -a^2 - a - 19
1281 sage: I.random_element(distribution="uniform") # random output
1282 a^2 - 2*a - 8
1283 sage: I.random_element(-30,30) # random output
1284 -7*a^2 - 17*a - 75
1285 sage: I.random_element(-100, 200).is_integral()
1286 True
1287 sage: I.random_element(-30,30).parent() is K
1288 True
1289
1290 A relative example::
1291
1292 sage: K.<a, b> = NumberField([x^2 + 2, x^2 + 1000*x + 1])
1293 sage: I = K.ideal(1-a)
1294 sage: I.random_element() # random output
1295 17/500002*a^3 + 737253/250001*a^2 - 1494505893/500002*a + 752473260/250001
1296 sage: I.random_element().is_integral()
1297 True
1298 sage: I.random_element(-100, 200).parent() is K
1299 True
1300 """
1301 if self.number_field().is_absolute():
1302 basis = self.basis()
1303 else:
1304 basis = self.absolute_ideal().basis()
1305 return self.number_field()(sum([ZZ.random_element(*args, **kwds)*a for a in basis]))
1306
1307 def artin_symbol(self):
1308 r"""
1309 Return the Artin symbol `( K / \QQ, P)`, where `K` is the
1310 number field of `P` =self. This is the unique element `s` of
1311 the decomposition group of `P` such that `s(x) = x^p \pmod{P}`
1312 where `p` is the residue characteristic of `P`. (Here `P`
1313 (self) should be prime and unramified.)
1314
1315 See the ``artin_symbol`` method of the ``GaloisGroup_v2``
1316 class for further documentation and examples.
1317
1318 EXAMPLE::
1319
1320 sage: QuadraticField(-23, 'w').primes_above(7)[0].artin_symbol()
1321 (1,2)
1322 """
1323 return self.number_field().galois_group().artin_symbol(self)
1324
1325 def residue_symbol(self, e, m, check=True):
1326 r"""
1327 The m-th power residue symbol for an element e and the proper ideal.
1328
1329 .. math:: \left(\frac{\alpha}{\mathbf{P}}\right) \equiv \alpha^{\frac{N(\mathbf{P})-1}{m}} \operatorname{mod} \mathbf{P}
1330
1331 .. note:: accepts m=1, in which case returns 1
1332
1333 .. note:: can also be called for an element from sage.rings.number_field_element.residue_symbol
1334
1335 INPUT:
1336
1337 - ``e`` - element of the number field
1338
1339 - ``m`` - positive integer
1340
1341 OUTPUT:
1342
1343 - an m-th root of unity in the number field
1344
1345 EXAMPLES::
1346
1347 Quadratic Residue (7 is not a square modulo 11)
1348 sage: K.<a> = NumberField(x-1)
1349 sage: K.ideal(11).residue_symbol(7,2)
1350 -1
1351
1352 Cubic Residue
1353 sage: K.<w> = NumberField(x^2 - x + 1)
1354 sage: K.ideal(17).residue_symbol(w^2+3,3)
1355 -w
1356
1357 """
1358 from sage.rings.arith import kronecker_symbol
1359
1360 K = self.ring()
1361 if m == 2:
1362 try:
1363 ze = ZZ(e)
1364 zp = ZZ(self.gens()[0])
1365 except TypeError:
1366 pass
1367 else:
1368 return kronecker_symbol(ze, zp)
1369 if check:
1370 if self.is_trivial():
1371 raise ValueError, "Ideal must be proper"
1372 if m < 1:
1373 raise ValueError, "Power must be positive"
1374 if not self.is_coprime(e):
1375 raise ValueError, "Element is not coprime to the ideal"
1376 if not self.is_coprime(m):
1377 raise ValueError, "Ideal is not coprime to the power"
1378 primroot = K.primitive_root_of_unity()
1379 rootorder = primroot.multiplicative_order()
1380 if check:
1381 if not rootorder%m == 0:
1382 raise ValueError, "The residue symbol to that power is not defined for the number field"
1383 if not self.is_prime():
1384 return prod(Q.residue_symbol(e,m)**i for Q, i in self.factor())
1385 k = self.residue_field()
1386 try:
1387 r = k(e)
1388 except TypeError:
1389 raise ValueError, "Element and ideal must be in a common number field"
1390 r = k(r**((1/m)*(self.absolute_norm()-1)))
1391 resroot = primroot**(rootorder/m)
1392 testroot = 1
1393 for j in range(0,m):
1394 if k(testroot) == r:
1395 return testroot
1396 testroot = testroot*resroot
1397 assert False, "This is a bug! No root equivalent to the residue class."
1398
1399 def basis_to_module(B, K):
1400 r"""
1401 Given a basis `B` of elements for a `\ZZ`-submodule of a number
1402 field `K`, return the corresponding `\ZZ`-submodule.
1403
1404 EXAMPLES::
1405
1406 sage: K.<w> = NumberField(x^4 + 1)
1407 sage: from sage.rings.number_field.number_field_ideal import basis_to_module
1408 sage: basis_to_module([K.0, K.0^2 + 3], K)
1409 Free module of degree 4 and rank 2 over Integer Ring
1410 User basis matrix:
1411 [0 1 0 0]
1412 [3 0 1 0]
1413 """
1414 V, from_V, to_V = K.absolute_vector_space()
1415 M = ZZ**(V.dimension())
1416 C = [to_V(K(b)) for b in B]
1417 return M.span_of_basis(C)
1418
1419 def is_NumberFieldIdeal(x):
1420 """
1421 Return True if x is an ideal of a number field.
1422
1423 EXAMPLES::
1424
1425 sage: from sage.rings.number_field.number_field_ideal import is_NumberFieldIdeal
1426 sage: is_NumberFieldIdeal(2/3)
1427 False
1428 sage: is_NumberFieldIdeal(ideal(5))
1429 False
1430 sage: k.<a> = NumberField(x^2 + 2)
1431 sage: I = k.ideal([a + 1]); I
1432 Fractional ideal (a + 1)
1433 sage: is_NumberFieldIdeal(I)
1434 True
1435 sage: Z = k.ideal(0); Z
1436 Ideal (0) of Number Field in a with defining polynomial x^2 + 2
1437 sage: is_NumberFieldIdeal(Z)
1438 True
1439 """
1440 return isinstance(x, NumberFieldIdeal)
1441
1442
1443 class NumberFieldFractionalIdeal(NumberFieldIdeal):
1444 r"""
1445 A fractional ideal in a number field.
1446 """
1447
1448 def __init__(self, field, gens, coerce=True):
1449 """
1450 INPUT:
1451 field -- a number field
1452 x -- a list of NumberFieldElements of the field, not all zero
1453
1454 EXAMPLES::
1455
1456 sage: NumberField(x^2 + 1, 'a').ideal(7)
1457 Fractional ideal (7)
1458 """
1459 if not isinstance(field, number_field.NumberField_generic):
1460 raise TypeError, "field (=%s) must be a number field."%field
1461
1462 if len(gens)==0:
1463 raise ValueError, "gens must have length at least 1 (zero ideal is not a fractional ideal)"
1464 if len(gens) == 1 and isinstance(gens[0], (list, tuple)):
1465 gens = gens[0]
1466 if misc.exists(gens,bool)[0]:
1467 NumberFieldIdeal.__init__(self, field, gens)
1468 else:
1469 raise ValueError, "gens must have a nonzero element (zero ideal is not a fractional ideal)"
1470
1471 def __repr__(self):
1472 """
1473 Return the string representation of this number field fractional ideal.
1474
1475 .. note::
1476
1477 Only the zero ideal actually has type NumberFieldIdeal; all
1478 others have type NumberFieldFractionalIdeal.
1479
1480 EXAMPLES::
1481
1482 sage: K.<a>=NumberField(x^2+5)
1483 sage: I = K.ideal([2,1+a]); I
1484 Fractional ideal (2, a + 1)
1485 sage: type(I)
1486 <class 'sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal'>
1487 """
1488 return "Fractional ideal %s"%self._repr_short()
1489
1490 def divides(self, other):
1491 """
1492 Returns True if this ideal divides other and False otherwise.
1493
1494 EXAMPLES::
1495
1496 sage: K.<a> = CyclotomicField(11); K
1497 Cyclotomic Field of order 11 and degree 10
1498 sage: I = K.factor(31)[0][0]; I
1499 Fractional ideal (31, a^5 + 10*a^4 - a^3 + a^2 + 9*a - 1)
1500 sage: I.divides(I)
1501 True
1502 sage: I.divides(31)
1503 True
1504 sage: I.divides(29)
1505 False
1506 """
1507 if not isinstance(other, NumberFieldIdeal):
1508 other = self.number_field().ideal(other)
1509 return (other / self).is_integral()
1510
1511 def factor(self):
1512 """
1513 Factorization of this ideal in terms of prime ideals.
1514
1515 EXAMPLES::
1516
1517 sage: K.<a> = NumberField(x^4 + 23); K
1518 Number Field in a with defining polynomial x^4 + 23
1519 sage: I = K.ideal(19); I
1520 Fractional ideal (19)
1521 sage: F = I.factor(); F
1522 (Fractional ideal (19, 1/2*a^2 + a - 17/2)) * (Fractional ideal (19, 1/2*a^2 - a - 17/2))
1523 sage: type(F)
1524 <class 'sage.structure.factorization.Factorization'>
1525 sage: list(F)
1526 [(Fractional ideal (19, 1/2*a^2 + a - 17/2), 1), (Fractional ideal (19, 1/2*a^2 - a - 17/2), 1)]
1527 sage: F.prod()
1528 Fractional ideal (19)
1529 """
1530 try:
1531 return self.__factorization
1532 except AttributeError:
1533 K = self.number_field()
1534 F = list(K.pari_nf().idealfactor(self.pari_hnf()))
1535 P, exps = F[0], F[1]
1536 A = []
1537 for i, p in enumerate(P):
1538 I = K.ideal([ZZ(p.pr_get_p()), K(p.pr_get_gen())])
1539 I._pari_prime = p
1540 A.append((I,ZZ(exps[i])))
1541 self.__factorization = Factorization(A)
1542 return self.__factorization
1543
1544 def prime_factors(self):
1545 """
1546 Return a list of the prime ideal factors of self
1547
1548 OUTPUT:
1549 list -- list of prime ideals (a new list is returned
1550 each time this function is called)
1551
1552 EXAMPLES::
1553
1554 sage: K.<w> = NumberField(x^2 + 23)
1555 sage: I = ideal(w+1)
1556 sage: I.prime_factors()
1557 [Fractional ideal (2, 1/2*w - 1/2), Fractional ideal (2, 1/2*w + 1/2), Fractional ideal (3, 1/2*w + 1/2)]
1558 """
1559 return [x[0] for x in self.factor()]
1560
1561 def __div__(self, other):
1562 """
1563 Return the quotient self / other.
1564
1565 EXAMPLES::
1566
1567 sage: R.<x> = PolynomialRing(QQ)
1568 sage: K.<a> = NumberField(x^2 - 5)
1569 sage: I = K.ideal(2/(5+a))
1570 sage: J = K.ideal(17+a)
1571 sage: I/J
1572 Fractional ideal (-17/1420*a + 1/284)
1573 sage: (I/J) * J == I
1574 True
1575 """
1576 return self * other.__invert__()
1577
1578 def __invert__(self):
1579 """
1580 Return the multiplicative inverse of self. Call with ~self.
1581
1582 EXAMPLES::
1583
1584 sage: R.<x> = PolynomialRing(QQ)
1585 sage: K.<a> = NumberField(x^3 - 2)
1586 sage: I = K.ideal(2/(5+a))
1587 sage: ~I
1588 Fractional ideal (1/2*a + 5/2)
1589 sage: 1/I
1590 Fractional ideal (1/2*a + 5/2)
1591 sage: (1/I) * I
1592 Fractional ideal (1)
1593 """
1594 nf = self.number_field().pari_nf()
1595 hnf = nf.idealdiv(self.number_field().ideal(1).pari_hnf(),
1596 self.pari_hnf())
1597 I = self.number_field().ideal(NumberFieldIdeal._NumberFieldIdeal__elements_from_hnf(self,hnf))
1598 I.__pari_hnf = hnf
1599 return I
1600
1601 def __pow__(self, r):
1602 """
1603 Return self to the power of r.
1604
1605 EXAMPLES::
1606
1607 sage: R.<x> = PolynomialRing(QQ)
1608 sage: K.<a> = NumberField(x^3 - 2)
1609 sage: I = K.ideal(2/(5+a))
1610 sage: J = I^2
1611 sage: Jinv = I^(-2)
1612 sage: J*Jinv
1613 Fractional ideal (1)
1614 """
1615 return generic_power(self, r)
1616
1617 def is_maximal(self):
1618 """
1619 Return True if this ideal is maximal. This is equivalent to
1620 self being prime, since it is nonzero.
1621
1622 EXAMPLES::
1623
1624 sage: K.<a> = NumberField(x^3 + 3); K
1625 Number Field in a with defining polynomial x^3 + 3
1626 sage: K.ideal(5).is_maximal()
1627 False
1628 sage: K.ideal(7).is_maximal()
1629 True
1630 """
1631 return self.is_prime()
1632
1633 def is_trivial(self, proof=None):
1634 """
1635 Returns True if this is a trivial ideal.
1636
1637 EXAMPLES::
1638
1639 sage: F.<a> = QuadraticField(-5)
1640 sage: I = F.ideal(3)
1641 sage: I.is_trivial()
1642 False
1643 sage: J = F.ideal(5)
1644 sage: J.is_trivial()
1645 False
1646 sage: (I+J).is_trivial()
1647 True
1648 """
1649 return self == self.number_field().ideal(1)
1650
1651 def ramification_index(self):
1652 r"""
1653 Return the ramification index of this fractional ideal,
1654 assuming it is prime. Otherwise, raise a ValueError.
1655
1656 The ramification index is the power of this prime appearing in
1657 the factorization of the prime in `\ZZ` that this prime lies
1658 over.
1659
1660 EXAMPLES::
1661
1662 sage: K.<a> = NumberField(x^2 + 2); K
1663 Number Field in a with defining polynomial x^2 + 2
1664 sage: f = K.factor(2); f
1665 (Fractional ideal (a))^2
1666 sage: f[0][0].ramification_index()
1667 2
1668 sage: K.ideal(13).ramification_index()
1669 1
1670 sage: K.ideal(17).ramification_index()
1671 Traceback (most recent call last):
1672 ...
1673 ValueError: the fractional ideal (= Fractional ideal (17)) is not prime
1674 """
1675 if self.is_prime():
1676 return ZZ(self._pari_prime.pr_get_e())
1677 raise ValueError, "the fractional ideal (= %s) is not prime"%self
1678
1679 def reduce(self, f):
1680 """
1681 Return the canonical reduction of the element of `f` modulo the ideal
1682 `I` (=self). This is an element of `R` (the ring of integers of the
1683 number field) that is equivalent modulo `I` to `f`.
1684
1685 An error is raised if this fractional ideal is not integral or
1686 the element `f` is not integral.
1687
1688 INPUT:
1689
1690 - ``f`` - an integral element of the number field
1691
1692 OUTPUT:
1693
1694 An integral element `g`, such that `f - g` belongs to the ideal self
1695 and such that `g` is a canonical reduced representative of the coset
1696 `f + I` (`I` =self) as described in the ``residues`` function, namely an integral element with coordinates `(r_0, \dots,r_{n-1})`, where:
1697
1698 - `r_i` is reduced modulo `d_i`
1699 - `d_i = b_i[i]`, with `{b_0, b_1, \dots, b_n}` HNF basis
1700 of the ideal self.
1701
1702 .. note::
1703
1704 The reduced element `g` is not necessarily small. To get a
1705 small `g` use the method ``small_residue``.
1706
1707 EXAMPLES::
1708
1709 sage: k.<a> = NumberField(x^3 + 11)
1710 sage: I = k.ideal(5, a^2 - a + 1)
1711 sage: c = 4*a + 9
1712 sage: I.reduce(c)
1713 a^2 - 2*a
1714 sage: c - I.reduce(c) in I
1715 True
1716
1717 The reduced element is in the list of canonical representatives
1718 returned by the ``residues`` method:
1719
1720 ::
1721
1722 sage: I.reduce(c) in list(I.residues())
1723 True
1724
1725 The reduced element does not necessarily have smaller norm (use
1726 ``small_residue`` for that)
1727
1728 ::
1729
1730 sage: c.norm()
1731 25
1732 sage: (I.reduce(c)).norm()
1733 209
1734 sage: (I.small_residue(c)).norm()
1735 10
1736
1737 Sometimes the canonical reduced representative of `1` won't be `1`
1738 (it depends on the choice of basis for the ring of integers):
1739
1740 ::
1741
1742 sage: k.<a> = NumberField(x^2 + 23)
1743 sage: I = k.ideal(3)
1744 sage: I.reduce(3*a + 1)
1745 -3/2*a - 1/2
1746 sage: k.ring_of_integers().basis()
1747 [1/2*a + 1/2, a]
1748
1749 AUTHOR: Maite Aranes.
1750 """
1751
1752 if not self.is_integral():
1753 raise ValueError, "reduce only defined for integral ideals"
1754
1755 R = self.number_field().maximal_order()
1756
1757 if not (f in R):
1758 raise TypeError, "reduce only defined for integral elements"
1759
1760 Rbasis = R.basis()
1761 n = len(Rbasis)
1762 from sage.matrix.all import MatrixSpace
1763 M = MatrixSpace(ZZ,n)([R.coordinates(y) for y in self.basis()])
1764
1765 D = M.hermite_form()
1766 d = [D[i,i] for i in range(n)]
1767
1768 v = R.coordinates(f)
1769
1770 for i in range(n):
1771 q, r = ZZ(v[i]).quo_rem(d[i])#v is a vector of rationals, we want division of integers
1772 if 2*r > d[i]:
1773 q = q + 1
1774 v = v - q*D[i]
1775
1776 return sum([v[i]*Rbasis[i] for i in range(n)])
1777
1778 def residues(self):
1779 """
1780 Returns a iterator through a complete list of residues modulo this integral ideal.
1781
1782 An error is raised if this fractional ideal is not integral.
1783
1784 OUTPUT:
1785
1786 An iterator through a complete list of residues modulo the integral
1787 ideal self. This list is the set of canonical reduced representatives
1788 given by all integral elements with coordinates `(r_0, \dots,r_{n-1})`,
1789 where:
1790
1791 - `r_i` is reduced modulo `d_i`
1792
1793 - `d_i = b_i[i]`, with `{b_0, b_1, \dots, b_n}` HNF basis
1794 of the ideal.
1795
1796 AUTHOR: John Cremona (modified by Maite Aranes)
1797
1798 EXAMPLES::
1799
1800 sage: K.<i>=NumberField(x^2+1)
1801 sage: res = K.ideal(2).residues(); res # random address
1802 xmrange_iter([[0, 1], [0, 1]], <function <lambda> at 0xa252144>)
1803 sage: list(res)
1804 [0, i, 1, i + 1]
1805 sage: list(K.ideal(2+i).residues())
1806 [-2*i, -i, 0, i, 2*i]
1807 sage: list(K.ideal(i).residues())
1808 [0]
1809 sage: I = K.ideal(3+6*i)
1810 sage: reps=I.residues()
1811 sage: len(list(reps)) == I.norm()
1812 True
1813 sage: all([r==s or not (r-s) in I for r in reps for s in reps]) # long time (3s)
1814 True
1815
1816 sage: K.<a> = NumberField(x^3-10)
1817 sage: I = K.ideal(a-1)
1818 sage: len(list(I.residues())) == I.norm()
1819 True
1820
1821 sage: K.<z> = CyclotomicField(11)
1822 sage: len(list(K.primes_above(3)[0].residues())) == 3**5 # long time (4s)
1823 True
1824 """
1825 if not self.is_integral():
1826 raise ValueError, "residues only defined for integral ideals"
1827
1828 R = self.number_field().maximal_order()
1829 Rbasis = R.basis()
1830 n = len(Rbasis)
1831 from sage.matrix.all import MatrixSpace
1832 M = MatrixSpace(ZZ,n)(map(R.coordinates, self.basis()))
1833
1834 D = M.hermite_form()
1835 d = [D[i,i] for i in range(n)]
1836 coord_ranges = [range((-di+2)//2,(di+2)//2) for di in d]
1837 combo = lambda c: sum([c[i]*Rbasis[i] for i in range(n)])
1838 return xmrange_iter(coord_ranges, combo)
1839
1840 def invertible_residues(self, reduce=True):
1841 r"""
1842 Returns a iterator through a list of invertible residues
1843 modulo this integral ideal.
1844
1845 An error is raised if this fractional ideal is not integral.
1846
1847 INPUT:
1848
1849 - ``reduce`` - bool. If True (default), use ``small_residue`` to get
1850 small representatives of the residues.
1851
1852 OUTPUT:
1853
1854 - An iterator through a list of invertible residues modulo this ideal
1855 `I`, i.e. a list of elements in the ring of integers `R` representing
1856 the elements of `(R/I)^*`.
1857
1858 ALGORITHM: Use pari's ``idealstar`` to find the group structure and
1859 generators of the multiplicative group modulo the ideal.
1860
1861 EXAMPLES::
1862
1863 sage: K.<i>=NumberField(x^2+1)
1864 sage: ires = K.ideal(2).invertible_residues(); ires # random address
1865 <generator object at 0xa2feb6c>
1866 sage: list(ires)
1867 [1, -i]
1868 sage: list(K.ideal(2+i).invertible_residues())
1869 [1, 2, 4, 3]
1870 sage: list(K.ideal(i).residues())
1871 [0]
1872 sage: list(K.ideal(i).invertible_residues())
1873 [1]
1874 sage: I = K.ideal(3+6*i)
1875 sage: units=I.invertible_residues()
1876 sage: len(list(units))==I.euler_phi()
1877 True
1878
1879 sage: K.<a> = NumberField(x^3-10)
1880 sage: I = K.ideal(a-1)
1881 sage: len(list(I.invertible_residues())) == I.euler_phi()
1882 True
1883
1884 sage: K.<z> = CyclotomicField(10)
1885 sage: len(list(K.primes_above(3)[0].invertible_residues()))
1886 80
1887
1888 AUTHOR: John Cremona
1889 """
1890 return self.invertible_residues_mod(subgp_gens=None, reduce=reduce)
1891
1892 def invertible_residues_mod(self, subgp_gens=[], reduce=True):
1893 r"""
1894 Returns a iterator through a list of representatives for the invertible
1895 residues modulo this integral ideal, modulo the subgroup generated by
1896 the elements in the list ``subgp_gens``.
1897
1898 INPUT:
1899
1900 - ``subgp_gens`` - either None or a list of elements of the number
1901 field of self. These need not be integral, but should be coprime to
1902 the ideal self. If the list is empty or None, the function returns
1903 an iterator through a list of representatives for the invertible
1904 residues modulo the integral ideal self.
1905
1906 - ``reduce`` - bool. If True (default), use ``small_residues`` to
1907 get small representatives of the residues.
1908
1909 .. note::
1910
1911 See also invertible_residues() for a simpler version without the subgroup.
1912
1913 OUTPUT:
1914
1915 - An iterator through a list of representatives for the invertible
1916 residues modulo self and modulo the group generated by
1917 ``subgp_gens``, i.e. a list of elements in the ring of integers `R`
1918 representing the elements of `(R/I)^*/U`, where `I` is this ideal and
1919 `U` is the subgroup of `(R/I)^*` generated by ``subgp_gens``.
1920
1921 EXAMPLES:
1922
1923 ::
1924
1925 sage: k.<a> = NumberField(x^2 +23)
1926 sage: I = k.ideal(a)
1927 sage: list(I.invertible_residues_mod([-1]))
1928 [1, 5, 2, 10, 4, 20, 8, 17, 16, 11, 9]
1929 sage: list(I.invertible_residues_mod([1/2]))
1930 [1, 5]
1931 sage: list(I.invertible_residues_mod([23]))
1932 Traceback (most recent call last):
1933 ...
1934 TypeError: the element must be invertible mod the ideal
1935
1936 ::
1937
1938 sage: K.<a> = NumberField(x^3-10)
1939 sage: I = K.ideal(a-1)
1940 sage: len(list(I.invertible_residues_mod([]))) == I.euler_phi()
1941 True
1942
1943 sage: I = K.ideal(1)
1944 sage: list(I.invertible_residues_mod([]))
1945 [1]
1946
1947 ::
1948
1949 sage: K.<z> = CyclotomicField(10)
1950 sage: len(list(K.primes_above(3)[0].invertible_residues_mod([])))
1951 80
1952
1953 AUTHOR: Maite Aranes.
1954 """
1955
1956 if self.norm() == 1:
1957 return xmrange_iter([[1]], lambda l: l[0])
1958
1959 k = self.number_field()
1960 G = self.idealstar(2)
1961
1962 invs = G.invariants()
1963 g = G.gens()
1964 n = G.ngens()
1965
1966 from sage.matrix.all import Matrix, diagonal_matrix
1967
1968 M = diagonal_matrix(ZZ, invs)
1969 if subgp_gens:
1970 Units = Matrix(ZZ, map(self.ideallog, subgp_gens))
1971 M = M.stack(Units)
1972
1973 A, U, V = M.smith_form()
1974
1975 V = V.inverse()
1976 new_basis = [prod([g[j]**V[i, j] for j in range(n)]) for i in range(n)]
1977
1978 if reduce:
1979 combo = lambda c: self.small_residue(prod([new_basis[i]**c[i] for i in range(n)]))
1980 else:
1981 combo = lambda c: prod([new_basis[i]**c[i] for i in range(n)])
1982
1983 coord_ranges = [range(A[i,i]) for i in range(n)]
1984
1985 return xmrange_iter(coord_ranges, combo)
1986
1987 def denominator(self):
1988 r"""
1989 Return the denominator ideal of this fractional ideal. Each
1990 fractional ideal has a unique expression as `N/D` where `N`,
1991 `D` are coprime integral ideals; the denominator is `D`.
1992
1993 EXAMPLES::
1994
1995 sage: K.<i>=NumberField(x^2+1)
1996 sage: I = K.ideal((3+4*i)/5); I
1997 Fractional ideal (4/5*i + 3/5)
1998 sage: I.denominator()
1999 Fractional ideal (-i + 2)
2000 sage: I.numerator()
2001 Fractional ideal (i + 2)
2002 sage: I.numerator().is_integral() and I.denominator().is_integral()
2003 True
2004 sage: I.numerator() + I.denominator() == K.unit_ideal()
2005 True
2006 sage: I.numerator()/I.denominator() == I
2007 True
2008 """
2009 try:
2010 return self._denom_ideal
2011 except AttributeError:
2012 pass
2013 self._denom_ideal = (self + self.number_field().unit_ideal())**(-1)
2014 return self._denom_ideal
2015
2016 def numerator(self):
2017 r"""
2018 Return the numerator ideal of this fractional ideal.
2019
2020 Each fractional ideal has a unique expression as `N/D` where `N`,
2021 `D` are coprime integral ideals. The numerator is `N`.
2022
2023 EXAMPLES::
2024
2025 sage: K.<i>=NumberField(x^2+1)
2026 sage: I = K.ideal((3+4*i)/5); I
2027 Fractional ideal (4/5*i + 3/5)
2028 sage: I.denominator()
2029 Fractional ideal (-i + 2)
2030 sage: I.numerator()
2031 Fractional ideal (i + 2)
2032 sage: I.numerator().is_integral() and I.denominator().is_integral()
2033 True
2034 sage: I.numerator() + I.denominator() == K.unit_ideal()
2035 True
2036 sage: I.numerator()/I.denominator() == I
2037 True
2038 """
2039 try:
2040 return self._num_ideal
2041 except AttributeError:
2042 pass
2043 self._num_ideal = self * self.denominator()
2044 return self._num_ideal
2045
2046 def is_coprime(self, other):
2047 """
2048 Returns True if this ideal is coprime to the other, else False.
2049
2050 INPUT:
2051
2052 - ``other`` -- another ideal of the same field, or generators
2053 of an ideal.
2054
2055 OUTPUT:
2056
2057 True if self and other are coprime, else False.
2058
2059 .. note::
2060
2061 This function works for fractional ideals as well as
2062 integral ideals.
2063
2064 AUTHOR: John Cremona
2065
2066 EXAMPLES::
2067
2068 sage: K.<i>=NumberField(x^2+1)
2069 sage: I = K.ideal(2+i)
2070 sage: J = K.ideal(2-i)
2071 sage: I.is_coprime(J)
2072 True
2073 sage: (I^-1).is_coprime(J^3)
2074 True
2075 sage: I.is_coprime(5)
2076 False
2077 sage: I.is_coprime(6+i)
2078 True
2079
2080 # See trac \# 4536:
2081 sage: E.<a> = NumberField(x^5 + 7*x^4 + 18*x^2 + x - 3)
2082 sage: OE = E.ring_of_integers()
2083 sage: i,j,k = [u[0] for u in factor(3*OE)]
2084 sage: (i/j).is_coprime(j/k)
2085 False
2086 sage: (j/k).is_coprime(j/k)
2087 False
2088
2089 sage: F.<a, b> = NumberField([x^2 - 2, x^2 - 3])
2090 sage: F.ideal(3 - a*b).is_coprime(F.ideal(3))
2091 False
2092 """
2093 # Catch invalid inputs by making sure that we can make an ideal out of other.
2094 K = self.number_field()
2095 one = K.unit_ideal()
2096 other = K.ideal(other)
2097 if self.is_integral() and other.is_integral():
2098 if arith.gcd(ZZ(self.absolute_norm()), ZZ(other.absolute_norm())) == 1:
2099 return True
2100 else:
2101 return self+other == one
2102 # This special case is necessary since the zero ideal is not a
2103 # fractional ideal!
2104 if other.absolute_norm() == 0:
2105 return self == one
2106 D1 = self.denominator()
2107 N1 = self.numerator()
2108 D2 = other.denominator()
2109 N2 = other.numerator()
2110 return N1+N2==one and N1+D2==one and D1+N2==one and D1+D2==one
2111
2112 def idealcoprime(self, J):
2113 """
2114 Returns l such that l*self is coprime to J.
2115
2116 INPUT:
2117
2118 - ``J`` - another integral ideal of the same field as self, which must also be integral.
2119
2120 OUTPUT:
2121
2122 - ``l`` - an element such that l*self is coprime to the ideal J
2123
2124 TODO: Extend the implementation to non-integral ideals.
2125
2126 EXAMPLES::
2127
2128 sage: k.<a> = NumberField(x^2 + 23)
2129 sage: A = k.ideal(a+1)
2130 sage: B = k.ideal(3)
2131 sage: A.is_coprime(B)
2132 False
2133 sage: lam = A.idealcoprime(B); lam
2134 -1/6*a + 1/6
2135 sage: (lam*A).is_coprime(B)
2136 True
2137
2138 ALGORITHM: Uses Pari function ``idealcoprime``.
2139 """
2140 if not (self.is_integral() and J.is_integral()):
2141 raise ValueError, "Both ideals must be integral."
2142
2143 k = self.number_field()
2144 # Catch invalid inputs by making sure that J is an ideal of the same field as self:
2145 assert k == J.number_field()
2146 l = k.pari_nf().idealcoprime(self.pari_hnf(), J.pari_hnf())
2147 return k(l)
2148
2149 def small_residue(self, f):
2150 r"""
2151 Given an element `f` of the ambient number field, returns an
2152 element `g` such that `f - g` belongs to the ideal self (which
2153 must be integral), and `g` is small.
2154
2155 .. note::
2156
2157 The reduced representative returned is not uniquely determined.
2158
2159 ALGORITHM: Uses Pari function ``nfeltreduce``.
2160
2161 EXAMPLES:
2162
2163 ::
2164
2165 sage: k.<a> = NumberField(x^2 + 5)
2166 sage: I = k.ideal(a)
2167 sage: I.small_residue(14)
2168 4
2169
2170 ::
2171
2172 sage: K.<a> = NumberField(x^5 + 7*x^4 + 18*x^2 + x - 3)
2173 sage: I = K.ideal(5)
2174 sage: I.small_residue(a^2 -13)
2175 a^2 + 5*a - 3
2176
2177 """
2178 if not self.is_integral():
2179 raise ValueError, "The ideal must be integral"
2180 k = self.number_field()
2181 return k(k.pari_nf().nfeltreduce(f._pari_(), self.pari_hnf()))
2182
2183 def _pari_bid_(self, flag=1):
2184 """
2185 Returns the pari structure ``bid`` associated to the ideal self.
2186
2187 INPUT:
2188
2189 - ``flag`` - when flag=2 it computes the generators of the group
2190 `(O_K/I)^*`, which takes more time. By default
2191 flag=1 (no generators are computed).
2192
2193 OUTPUT:
2194
2195 - The pari special structure ``bid``.
2196
2197 EXAMPLES::
2198
2199 sage: k.<a> = NumberField(x^4 + 13)
2200 sage: I = k.ideal(2, a^2 + 1)
2201 sage: hasattr(I, '_bid')
2202 False
2203 sage: bid = I._pari_bid_()
2204 sage: hasattr(I, '_bid')
2205 True
2206 sage: bid.getattr('clgp')
2207 [2, [2]]
2208 """
2209 try:
2210 bid = self._bid
2211 if flag==2:
2212 # Try to access generators, we get PariError if this fails.
2213 bid.bid_get_gen();
2214 except (AttributeError, PariError):
2215 k = self.number_field()
2216 bid = k.pari_nf().idealstar(self.pari_hnf(), flag)
2217 self._bid = bid
2218 return bid
2219
2220
2221 def idealstar(self, flag=1):
2222 r"""
2223 Returns the finite abelian group `(O_K/I)^*`, where I is the ideal self
2224 of the number field K, and `O_K` is the ring of integers of K.
2225
2226 INPUT:
2227
2228 - ``flag`` (int default 1) -- when ``flag`` =2, it also
2229 computes the generators of the group `(O_K/I)^*`, which
2230 takes more time. By default ``flag`` =1 (no generators are
2231 computed). In both cases the special pari structure ``bid``
2232 is computed as well. If ``flag`` =0 (deprecated) it computes
2233 only the group structure of `(O_K/I)^*` (with generators)
2234 and not the special ``bid`` structure.
2235
2236 OUTPUT:
2237
2238 The finite abelian group `(O_K/I)^*`.
2239
2240 .. note::
2241
2242 Uses the pari function ``idealstar``. The pari function outputs
2243 a special ``bid`` structure which is stored in the internal
2244 field ``_bid`` of the ideal (when flag=1,2). The special structure
2245 ``bid`` is used in the pari function ``ideallog``
2246 to compute discrete logarithms.
2247
2248 EXAMPLES::
2249
2250 sage: k.<a> = NumberField(x^3 - 11)
2251 sage: A = k.ideal(5)
2252 sage: G = A.idealstar(); G
2253 Multiplicative Abelian Group isomorphic to C24 x C4
2254 sage: G.gens()
2255 (f0, f1)
2256 sage: G = A.idealstar(2)
2257 sage: all([G.gens()[i] in k for i in range(G.ngens())])
2258 True
2259
2260 ALGORITHM: Uses Pari function ``idealstar``
2261 """
2262 k = self.number_field()
2263 if flag==0 and not hasattr(self, '_bid'):
2264 G = k.pari_nf().idealstar(self.pari_hnf(), 0)
2265 else:
2266 G = self._pari_bid_(flag)
2267 inv = [ZZ(c) for c in G.bid_get_cyc()]
2268
2269 from sage.groups.abelian_gps.abelian_group import AbelianGroup
2270 AG = AbelianGroup(len(inv), inv)
2271 if flag == 2 or flag == 0:
2272 g = G.bid_get_gen()
2273 AG._gens = tuple(map(k, g))
2274 return AG
2275
2276 def ideallog(self, x):
2277 r"""
2278 Returns the discrete logarithm of x with respect to the
2279 generators given in the ``bid`` structure of the ideal
2280 self.
2281
2282 INPUT:
2283
2284 - ``x`` - a non-zero element of the number field of self,
2285 which must have valuation equal to 0 at all prime ideals in
2286 the support of the ideal self.
2287
2288 OUTPUT:
2289
2290 - ``l`` - a list of integers `(x_i)` such that `0 \leq x_i < d_i` and
2291 `x = \prod_i g_i^{x_i}` in `(R/I)^*`, where `I` = self, `R` = ring of
2292 integers of the field, and `g_i` are the generators of `(R/I)^*`, of
2293 orders `d_i` respectively, as given in the ``bid`` structure of
2294 the ideal self.
2295
2296 EXAMPLES::
2297
2298 sage: k.<a> = NumberField(x^3 - 11)
2299 sage: A = k.ideal(5)
2300 sage: G = A.idealstar(2)
2301 sage: l = A.ideallog(a^2 +3)
2302 sage: r = prod([G.gens()[i]**l[i] for i in range(len(l))])
2303 sage: (a^2 + 3) - r in A
2304 True
2305 sage: A.small_residue(r) # random
2306 a^2 - 2
2307
2308 ALGORITHM: Uses Pari function ``ideallog``
2309 """
2310 k = self.number_field()
2311 if not all([k(x).valuation(p)==0 for p, e in self.factor()]):
2312 raise TypeError, "the element must be invertible mod the ideal"
2313
2314 #Now it is important to call _pari_bid_() with flag=2 to make sure
2315 #we fix a basis, since the log would be different for a different
2316 #choice of basis.
2317 return map(ZZ, k.pari_nf().ideallog(x._pari_(), self._pari_bid_(2)))
2318
2319 def element_1_mod(self, other):
2320 r"""
2321 Returns an element `r` in this ideal such that `1-r` is in other
2322
2323 An error is raised if either ideal is not integral of if they
2324 are not coprime.
2325
2326 INPUT:
2327
2328 - ``other`` -- another ideal of the same field, or generators
2329 of an ideal.
2330
2331 OUTPUT:
2332
2333 An element `r` of the ideal self such that `1-r` is in the ideal other
2334
2335 AUTHOR: Maite Aranes (modified to use PARI's idealaddtoone by Francis Clarke)
2336
2337 EXAMPLES::
2338
2339 sage: K.<a> = NumberField(x^3-2)
2340 sage: A = K.ideal(a+1); A; A.norm()
2341 Fractional ideal (a + 1)
2342 3
2343 sage: B = K.ideal(a^2-4*a+2); B; B.norm()
2344 Fractional ideal (a^2 - 4*a + 2)
2345 68
2346 sage: r = A.element_1_mod(B); r
2347 -a^2 + 4*a - 1
2348 sage: r in A
2349 True
2350 sage: 1-r in B
2351 True
2352
2353 TESTS::
2354
2355 sage: K.<a> = NumberField(x^3-2)
2356 sage: A = K.ideal(a+1)
2357 sage: B = K.ideal(a^2-4*a+1); B; B.norm()
2358 Fractional ideal (a^2 - 4*a + 1)
2359 99
2360 sage: A.element_1_mod(B)
2361 Traceback (most recent call last):
2362 ...
2363 TypeError: Fractional ideal (a + 1), Fractional ideal (a^2 - 4*a + 1) are not coprime ideals
2364
2365 sage: B = K.ideal(1/a); B
2366 Fractional ideal (1/2*a^2)
2367 sage: A.element_1_mod(B)
2368 Traceback (most recent call last):
2369 ...
2370 TypeError: Fractional ideal (1/2*a^2) is not an integral ideal
2371 """
2372 if not self.is_integral():
2373 raise TypeError, "%s is not an integral ideal"%self
2374
2375 # Catch invalid inputs by making sure that we can make an ideal out of other.
2376 K = self.number_field()
2377 other = K.ideal(other)
2378 if not other.is_integral():
2379 raise TypeError, "%s is not an integral ideal"%other
2380
2381 if not self.is_coprime(other):
2382 raise TypeError, "%s, %s are not coprime ideals"%(self, other)
2383
2384 bnf = K.pari_bnf()
2385 r = bnf.idealaddtoone(self.pari_hnf(), other.pari_hnf())[0]
2386 return K(r)
2387
2388 def euler_phi(self):
2389 r"""
2390 Returns the Euler `\varphi`-function of this integral ideal.
2391
2392 This is the order of the multiplicative group of the quotient
2393 modulo the ideal.
2394
2395 An error is raised if the ideal is not integral.
2396
2397 EXAMPLES::
2398
2399 sage: K.<i>=NumberField(x^2+1)
2400 sage: I = K.ideal(2+i)
2401 sage: [r for r in I.residues() if I.is_coprime(r)]
2402 [-2*i, -i, i, 2*i]
2403 sage: I.euler_phi()
2404 4
2405 sage: J = I^3
2406 sage: J.euler_phi()
2407 100
2408 sage: len([r for r in J.residues() if J.is_coprime(r)])
2409 100
2410 sage: J = K.ideal(3-2*i)
2411 sage: I.is_coprime(J)
2412 True
2413 sage: I.euler_phi()*J.euler_phi() == (I*J).euler_phi()
2414 True
2415 sage: L.<b> = K.extension(x^2 - 7)
2416 sage: L.ideal(3).euler_phi()
2417 64
2418 """
2419 if not self.is_integral():
2420 raise ValueError, "euler_phi only defined for integral ideals"
2421 return prod([(np-1)*np**(e-1) \
2422 for np,e in [(p.absolute_norm(),e) \
2423 for p,e in self.factor()]])
2424
2425 def prime_to_S_part(self,S):
2426 r"""
2427 Return the part of this fractional ideal which is coprime to the prime ideals in the list ``S``.
2428
2429 .. note::
2430
2431 This function assumes that `S` is a list of prime ideals,
2432 but does not check this. This function will fail if `S` is
2433 not a list of prime ideals.
2434
2435 INPUT:
2436
2437 - `S` - a list of prime ideals
2438
2439 OUTPUT:
2440
2441 A fractional ideal coprime to the primes in `S`, whose prime
2442 factorization is that of ``self`` withe the primes in `S`
2443 removed.
2444
2445 EXAMPLES::
2446
2447 sage: K.<a> = NumberField(x^2-23)
2448 sage: I = K.ideal(24)
2449 sage: S = [K.ideal(-a+5),K.ideal(5)]
2450 sage: I.prime_to_S_part(S)
2451 Fractional ideal (3)
2452 sage: J = K.ideal(15)
2453 sage: J.prime_to_S_part(S)
2454 Fractional ideal (3)
2455
2456 sage: K.<a> = NumberField(x^5-23)
2457 sage: I = K.ideal(24)
2458 sage: S = [K.ideal(15161*a^4 + 28383*a^3 + 53135*a^2 + 99478*a + 186250),K.ideal(2*a^4 + 3*a^3 + 4*a^2 + 15*a + 11), K.ideal(101)]
2459 sage: I.prime_to_S_part(S)
2460 Fractional ideal (24)
2461
2462 """
2463 a = self
2464 for p in S:
2465 n = a.valuation(p)
2466 a = a*p**(-n)
2467 return a
2468
2469 def is_S_unit(self,S):
2470 r"""
2471 Return True if this fractional ideal is a unit with respect to the list of primes ``S``.
2472
2473 INPUT:
2474
2475 - `S` - a list of prime ideals (not checked if they are
2476 indeed prime).
2477
2478 .. note::
2479
2480 This function assumes that `S` is a list of prime ideals,
2481 but does not check this. This function will fail if `S` is
2482 not a list of prime ideals.
2483
2484 OUTPUT:
2485
2486 True, if the ideal is an `S`-unit: that is, if the valuations of
2487 the ideal at all primes not in `S` are zero. False, otherwise.
2488
2489 EXAMPLES::
2490
2491 sage: K.<a> = NumberField(x^2+23)
2492 sage: I = K.ideal(2)
2493 sage: P = I.factor()[0][0]
2494 sage: I.is_S_unit([P])
2495 False
2496 """
2497 return self.prime_to_S_part(S).is_trivial()
2498
2499 def is_S_integral(self,S):
2500 r"""
2501 Return True if this fractional ideal is integral with respect to the list of primes ``S``.
2502
2503 INPUT:
2504
2505 - `S` - a list of prime ideals (not checked if they are indeed
2506 prime).
2507
2508 .. note::
2509
2510 This function assumes that `S` is a list of prime ideals,
2511 but does not check this. This function will fail if `S` is
2512 not a list of prime ideals.
2513
2514 OUTPUT:
2515
2516 True, if the ideal is `S`-integral: that is, if the valuations
2517 of the ideal at all primes not in `S` are non-negative. False,
2518 otherwise.
2519
2520 EXAMPLES::
2521
2522 sage: K.<a> = NumberField(x^2+23)
2523 sage: I = K.ideal(1/2)
2524 sage: P = K.ideal(2,1/2*a - 1/2)
2525 sage: I.is_S_integral([P])
2526 False
2527
2528 sage: J = K.ideal(1/5)
2529 sage: J.is_S_integral([K.ideal(5)])
2530 True
2531 """
2532 if self.is_integral():
2533 return True
2534 return self.prime_to_S_part(S).is_integral()
2535
2536 def prime_to_idealM_part(self, M):
2537 r"""
2538 Version for integral ideals of the ``prime_to_m_part`` function over `\ZZ`.
2539 Returns the largest divisor of self that is coprime to the ideal ``M``.
2540
2541 INPUT:
2542
2543 - ``M`` -- an integral ideal of the same field, or generators of an ideal
2544
2545 OUTPUT:
2546
2547 An ideal which is the largest divisor of self that is coprime to `M`.
2548
2549 AUTHOR: Maite Aranes
2550
2551 EXAMPLES::
2552
2553 sage: k.<a> = NumberField(x^2 + 23)
2554 sage: I = k.ideal(a+1)
2555 sage: M = k.ideal(2, 1/2*a - 1/2)
2556 sage: J = I.prime_to_idealM_part(M); J
2557 Fractional ideal (12, 1/2*a + 13/2)
2558 sage: J.is_coprime(M)
2559 True
2560
2561 sage: J = I.prime_to_idealM_part(2); J
2562 Fractional ideal (3, 1/2*a + 1/2)
2563 sage: J.is_coprime(M)
2564 True
2565 """
2566 # Catch invalid inputs by making sure that we can make an ideal out of M.
2567 k = self.number_field()
2568 M = k.ideal(M)
2569
2570 if not self.is_integral or not M.is_integral():
2571 raise TypeError, "prime_to_idealM_part defined only for integral ideals"
2572
2573 if self.is_coprime(M):
2574 return self
2575 G = self + M
2576 I = self
2577 while not G.is_trivial():
2578 I = I/G
2579 G = I + G
2580 return I
2581
2582 def _p_quotient(self, p):
2583 """
2584 This is an internal technical function that is used for example for
2585 computing the quotient of the ring of integers by a prime ideal.
2586
2587 INPUT:
2588 p -- a prime number contained in self.
2589
2590 OUTPUT:
2591 V -- a vector space of characteristic p
2592 quo -- a partially defined quotient homomorphism from the
2593 ambient number field to V
2594 lift -- a section of quo.
2595
2596 EXAMPLES::
2597
2598 sage: K.<i> = NumberField(x^2 + 1); O = K.maximal_order()
2599 sage: I = K.factor(3)[0][0]
2600 sage: Q, quo, lift = I._p_quotient(3); Q
2601 Vector space quotient V/W of dimension 2 over Finite Field of size 3 where
2602 V: Vector space of dimension 2 over Finite Field of size 3
2603 W: Vector space of degree 2 and dimension 0 over Finite Field of size 3
2604 Basis matrix:
2605 []
2606
2607 We do an example with a split prime and show both the quo and lift maps:
2608 sage: K.<i> = NumberField(x^2 + 1); O = K.maximal_order()
2609 sage: I = K.factor(5)[0][0]
2610 sage: Q,quo,lift = I._p_quotient(5)
2611 sage: lift(quo(i))
2612 3
2613 sage: lift(quo(i)) - i in I
2614 True
2615 sage: quo(lift(Q.0))
2616 (1)
2617 sage: Q.0
2618 (1)
2619 sage: Q
2620 Vector space quotient V/W of dimension 1 over Finite Field of size 5 where
2621 V: Vector space of dimension 2 over Finite Field of size 5
2622 W: Vector space of degree 2 and dimension 1 over Finite Field of size 5
2623 Basis matrix:
2624 [1 3]
2625 sage: quo
2626 Partially defined quotient map from Number Field in i with defining polynomial x^2 + 1 to an explicit vector space representation for the quotient of the ring of integers by (p,I) for the ideal I=Fractional ideal (i + 2).
2627 sage: lift
2628 Lifting map to Maximal Order in Number Field in i with defining polynomial x^2 + 1 from quotient of integers by Fractional ideal (i + 2)
2629 """
2630 return quotient_char_p(self, p)
2631
2632 def residue_field(self, names=None):
2633 r"""
2634 Return the residue class field of this fractional ideal, which
2635 must be prime.
2636
2637 EXAMPLES::
2638
2639 sage: K.<a> = NumberField(x^3-7)
2640 sage: P = K.ideal(29).factor()[0][0]
2641 sage: P.residue_field()
2642 Residue field in abar of Fractional ideal (2*a^2 + 3*a - 10)
2643 sage: P.residue_field('z')
2644 Residue field in z of Fractional ideal (2*a^2 + 3*a - 10)
2645
2646 Another example::
2647
2648 sage: K.<a> = NumberField(x^3-7)
2649 sage: P = K.ideal(389).factor()[0][0]; P
2650 Fractional ideal (389, a^2 - 44*a - 9)
2651 sage: P.residue_class_degree()
2652 2
2653 sage: P.residue_field()
2654 Residue field in abar of Fractional ideal (389, a^2 - 44*a - 9)
2655 sage: P.residue_field('z')
2656 Residue field in z of Fractional ideal (389, a^2 - 44*a - 9)
2657 sage: FF.<w> = P.residue_field()
2658 sage: FF
2659 Residue field in w of Fractional ideal (389, a^2 - 44*a - 9)
2660 sage: FF((a+1)^390)
2661 36
2662 sage: FF(a)
2663 w
2664
2665 An example of reduction maps to the residue field: these are
2666 defined on the whole valuation ring, i.e. the subring of the
2667 number field consisting of elements with non-negative
2668 valuation. This shows that the issue raised in trac \#1951
2669 has been fixed::
2670
2671 sage: K.<i> = NumberField(x^2 + 1)
2672 sage: P1, P2 = [g[0] for g in K.factor(5)]; (P1,P2)
2673 (Fractional ideal (i + 2), Fractional ideal (-i + 2))
2674 sage: a = 1/(1+2*i)
2675 sage: F1, F2 = [g.residue_field() for g in [P1,P2]]; (F1,F2)
2676 (Residue field of Fractional ideal (i + 2), Residue field of Fractional ideal (-i + 2))
2677 sage: a.valuation(P1)
2678 0
2679 sage: F1(i/7)
2680 4
2681 sage: F1(a)
2682 3
2683 sage: a.valuation(P2)
2684 -1
2685 sage: F2(a)
2686 Traceback (most recent call last):
2687 ZeroDivisionError: Cannot reduce field element -2/5*i + 1/5 modulo Fractional ideal (-i + 2): it has negative valuation
2688
2689 An example with a relative number field::
2690
2691 sage: L.<a,b> = NumberField([x^2 + 1, x^2 - 5])
2692 sage: p = L.ideal((-1/2*b - 1/2)*a + 1/2*b - 1/2)
2693 sage: R = p.residue_field(); R
2694 Residue field in abar of Fractional ideal ((-1/2*b - 1/2)*a + 1/2*b - 1/2)
2695 sage: R.cardinality()
2696 9
2697 sage: R(17)
2698 2
2699 sage: R((a + b)/17)
2700 abar
2701 sage: R(1/b)
2702 2*abar
2703
2704 """
2705 if not self.is_prime():
2706 raise ValueError, "The ideal must be prime"
2707 return self.number_field().residue_field(self, names = names)
2708
2709 def residue_class_degree(self):
2710 r"""
2711 Return the residue class degree of this fractional ideal,
2712 assuming it is prime. Otherwise, raise a ValueError.
2713
2714 The residue class degree of a prime ideal `I` is the degree of
2715 the extension `O_K/I` of its prime subfield.
2716
2717 EXAMPLES::
2718
2719 sage: K.<a> = NumberField(x^5 + 2); K
2720 Number Field in a with defining polynomial x^5 + 2
2721 sage: f = K.factor(19); f
2722 (Fractional ideal (a^2 + a - 3)) * (Fractional ideal (-2*a^4 - a^2 + 2*a - 1)) * (Fractional ideal (a^2 + a - 1))
2723 sage: [i.residue_class_degree() for i, _ in f]
2724 [2, 2, 1]
2725 """
2726 if self.is_prime():
2727 return ZZ(self._pari_prime.pr_get_f())
2728 raise ValueError, "the ideal (= %s) is not prime"%self
2729
2730 def is_NumberFieldFractionalIdeal(x):
2731 """
2732 Return True if x is a fractional ideal of a number field.
2733
2734 EXAMPLES::
2735
2736 sage: from sage.rings.number_field.number_field_ideal import is_NumberFieldFractionalIdeal
2737 sage: is_NumberFieldFractionalIdeal(2/3)
2738 False
2739 sage: is_NumberFieldFractionalIdeal(ideal(5))
2740 False
2741 sage: k.<a> = NumberField(x^2 + 2)
2742 sage: I = k.ideal([a + 1]); I
2743 Fractional ideal (a + 1)
2744 sage: is_NumberFieldFractionalIdeal(I)
2745 True
2746 sage: Z = k.ideal(0); Z
2747 Ideal (0) of Number Field in a with defining polynomial x^2 + 2
2748 sage: is_NumberFieldFractionalIdeal(Z)
2749 False
2750 """
2751 return isinstance(x, NumberFieldFractionalIdeal)
2752
2753 class QuotientMap:
2754 """
2755 Class to hold data needed by quotient maps from number field
2756 orders to residue fields. These are only partial maps: the exact
2757 domain is the appropriate valuation ring. For examples, see
2758 :meth:`~sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal.residue_field`.
2759 """
2760 def __init__(self, K, M_OK_change, Q, I):
2761 """
2762 Initialize this QuotientMap.
2763
2764 EXAMPLE::
2765
2766 sage: K.<a> = NumberField(x^3 + 4)
2767 sage: f = K.ideal(1 + a^2/2).residue_field().reduction_map(); f # indirect doctest
2768 Partially defined reduction map:
2769 From: Number Field in a with defining polynomial x^3 + 4
2770 To: Residue field of Fractional ideal (1/2*a^2 + 1)
2771 sage: f.__class__
2772 <type 'sage.rings.residue_field.ReductionMap'>
2773 """
2774 self.__M_OK_change = M_OK_change
2775 self.__Q = Q
2776 self.__K = K
2777 self.__I = I
2778 self.__L, self.__from_L, self.__to_L = K.absolute_vector_space()
2779
2780 def __call__(self, x):
2781 """
2782 Apply this QuotientMap to an element of the number field.
2783
2784 INPUT:
2785
2786 x -- an element of the field
2787
2788 EXAMPLE::
2789
2790 sage: K.<a> = NumberField(x^3 + 4)
2791 sage: f = K.ideal(1 + a^2/2).residue_field().reduction_map()
2792 sage: f(a)
2793 2
2794 """
2795 v = self.__to_L(x)
2796 w = v * self.__M_OK_change
2797 return self.__Q( list(w) )
2798
2799 def __repr__(self):
2800 """
2801 Return a string representation of this QuotientMap.
2802
2803 EXAMPLE::
2804
2805 sage: K.<a> = NumberField(x^3 + 4)
2806 sage: f = K.ideal(1 + a^2/2).residue_field().reduction_map()
2807 sage: repr(f)
2808 'Partially defined reduction map:\n From: Number Field in a with defining polynomial x^3 + 4\n To: Residue field of Fractional ideal (1/2*a^2 + 1)'
2809 """
2810 return "Partially defined quotient map from %s to an explicit vector space representation for the quotient of the ring of integers by (p,I) for the ideal I=%s."%(self.__K, self.__I)
2811
2812 class LiftMap:
2813 """
2814 Class to hold data needed by lifting maps from residue fields to
2815 number field orders.
2816 """
2817 def __init__(self, OK, M_OK_map, Q, I):
2818 """
2819 Initialize this LiftMap.
2820
2821 EXAMPLE::
2822
2823 sage: K.<a> = NumberField(x^3 + 4)
2824 sage: I = K.ideal(1 + a^2/2)
2825 sage: f = I.residue_field().lift_map()
2826 sage: f.__class__
2827 <type 'sage.rings.residue_field.LiftingMap'>
2828 """
2829 self.__I = I
2830 self.__OK = OK
2831 self.__Q = Q
2832 self.__M_OK_map = M_OK_map
2833
2834 def __call__(self, x):
2835 """
2836 Apply this LiftMap to an element of the residue field.
2837
2838 EXAMPLE::
2839
2840 sage: K.<a> = NumberField(x^3 + 4)
2841 sage: R = K.ideal(1 + a^2/2).residue_field()
2842 sage: f = R.lift_map()
2843 sage: f(R(a/17))
2844 1
2845 """
2846 # This lifts to OK tensor F_p
2847 v = self.__Q.lift(x)
2848 # This lifts to ZZ^n (= OK)
2849 w = v.lift()
2850 # Write back in terms of K
2851 z = w * self.__M_OK_map
2852 return self.__OK(z.list())
2853
2854 def __repr__(self):
2855 """
2856 Return a string representation of this QuotientMap.
2857
2858 EXAMPLE::
2859
2860 sage: K.<a> = NumberField(x^3 + 4)
2861 sage: R = K.ideal(1 + a^2/2).residue_field()
2862 sage: repr(R.lift_map())
2863 'Lifting map:\n From: Residue field of Fractional ideal (1/2*a^2 + 1)\n To: Maximal Order in Number Field in a with defining polynomial x^3 + 4'
2864 """
2865 return "Lifting map to %s from quotient of integers by %s"%(self.__OK, self.__I)
2866
2867 def quotient_char_p(I, p):
2868 r"""
2869 Given an integral ideal `I` that contains a prime number `p`, compute
2870 a vector space `V = (O_K \mod p) / (I \mod p)`, along with a
2871 homomorphism `O_K \to V` and a section `V \to O_K`.
2872
2873 EXAMPLES::
2874
2875 sage: from sage.rings.number_field.number_field_ideal import quotient_char_p
2876
2877 sage: K.<i> = NumberField(x^2 + 1); O = K.maximal_order(); I = K.fractional_ideal(15)
2878 sage: quotient_char_p(I, 5)[0]
2879 Vector space quotient V/W of dimension 2 over Finite Field of size 5 where
2880 V: Vector space of dimension 2 over Finite Field of size 5
2881 W: Vector space of degree 2 and dimension 0 over Finite Field of size 5
2882 Basis matrix:
2883 []
2884 sage: quotient_char_p(I, 3)[0]
2885 Vector space quotient V/W of dimension 2 over Finite Field of size 3 where
2886 V: Vector space of dimension 2 over Finite Field of size 3
2887 W: Vector space of degree 2 and dimension 0 over Finite Field of size 3
2888 Basis matrix:
2889 []
2890
2891 sage: I = K.factor(13)[0][0]; I
2892 Fractional ideal (-2*i + 3)
2893 sage: I.residue_class_degree()
2894 1
2895 sage: quotient_char_p(I, 13)[0]
2896 Vector space quotient V/W of dimension 1 over Finite Field of size 13 where
2897 V: Vector space of dimension 2 over Finite Field of size 13
2898 W: Vector space of degree 2 and dimension 1 over Finite Field of size 13
2899 Basis matrix:
2900 [1 8]
2901 """
2902 if not I.is_integral():
2903 raise ValueError, "I must be an integral ideal."
2904
2905 K = I.number_field()
2906 OK = K.maximal_order() # will in the long run only really need a p-maximal order.
2907 M_OK = OK.free_module()
2908 M_I = I.free_module()
2909
2910 # Now we have to quite explicitly find a way to compute
2911 # with OK / I viewed as a quotient of two F_p vector spaces,
2912 # and itself viewed as an F_p vector space.
2913
2914 # Step 1. Write each basis vector for I (as a ZZ-module)
2915 # in terms of the basis for OK.
2916
2917 B_I = M_I.basis()
2918 M_OK_mat = M_OK.basis_matrix()
2919 M_OK_change = M_OK_mat**(-1)
2920 B_I_in_terms_of_M = M_I.basis_matrix() * M_OK_change
2921
2922 # Step 2. Define "M_OK mod p" to just be (F_p)^n and
2923 # "M_I mod p" to be the reduction mod p of the elements
2924 # compute in step 1.
2925
2926 n = K.absolute_degree()
2927 k = FiniteField(p)
2928 M_OK_modp = k**n
2929 B_mod = B_I_in_terms_of_M.change_ring(k)
2930 M_I_modp = M_OK_modp.span(B_mod.row_space())
2931
2932 # Step 3. Compute the quotient of these two F_p vector space.
2933
2934 Q = M_OK_modp.quotient(M_I_modp)
2935
2936 # Step 4. Now we get the maps we need from the above data.
2937
2938 K_to_Q = QuotientMap(K, M_OK_change, Q, I)
2939 Q_to_OK = LiftMap(OK, M_OK_mat, Q, I)
2940
2941 return Q, K_to_Q, Q_to_OK
2942
2943
2944
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.