Changeset 7729:b4d53385d6c7

Timestamp:

12/15/07 02:03:44 (5 years ago)

Author:

William Stein <wstein@…>

Branch:

default

Message:

Trac #1183 -- residue class fields (finish).

Location:

sage

Files:

• modules/free_module_element.pyx (modified) (1 diff)
• rings/finite_field.py (modified) (1 diff)
• rings/finite_field_givaro.pyx (modified) (1 diff)
• rings/number_field/number_field_ideal.py (modified) (2 diffs)
• rings/residue_field.pyx (modified) (14 diffs)

sage/modules/free_module_element.pyx

@@ -1019 +1019 @@
             
             if len(entries) != self.degree():
-                raise ArithmeticError, "entries must be a list of length %s"%\
+                raise TypeError, "entries must be a list of length %s"%\
                             self.degree()
             if coerce:

sage/rings/finite_field.py

@@ -419 +419 @@
 
     def gen(self, n=0):
+        """
+        Return generator of this finite field.
+        
+        EXAMPLES:
+            sage: k = GF(13)
+            sage: k.gen()
+            1
+            sage: k.gen(1)
+            Traceback (most recent call last):
+            ...
+            IndexError: only one generator
+        """
+        if n != 0:
+            raise IndexError, "only one generator"
         return self.__gen
 

sage/rings/finite_field_givaro.pyx

@@ -596 +596 @@
         EXAMPLES:
             sage: k = GF(3^4, 'b'); k.gen()
-            b        
+            b
+            sage: k.gen(1)
+            Traceback (most recent call last):
+            ...
+            IndexError: only one generator
         """
         cdef int r

sage/rings/number_field/number_field_ideal.py

@@ -849 +849 @@
             Partially defined quotient map from Number Field in i with defining polynomial x^2 + 1 to an explicit vector space representation for the quotient of the ring of integers by (p,I) for the ideal I=Fractional ideal (-i - 2).
             sage: lift
-            Lifting map to Order in Number Field in i with defining polynomial x^2 + 1 from quotient of integers by Fractional ideal (-i - 2)
+            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)
         """
         return quotient_char_p(self, p)
@@ -1021 +1021 @@
     V, from_V, to_V = K.absolute_vector_space()
     M = ZZ**(V.dimension())
-    C = [to_V(K(b.list())) for b in B]
+    C = [to_V(K(b)) for b in B]
     return M.span_of_basis(C)
         

sage/rings/residue_field.pyx

@@ -13 +13 @@
     841
 
+We reduce mod a prime for which the ring of integers is not
+monogenic (i.e., 2 is an essential discriminant divisor):
+    sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
+    sage: F = K.factor_integer(2); F
+    (Fractional ideal (1/2*a^2 - 1/2*a + 1)) * (Fractional ideal (a^2 - 2*a + 3)) * (Fractional ideal (3/2*a^2 - 5/2*a + 4))
+    sage: F[0][0].residue_field()
+    Residue field of Fractional ideal (1/2*a^2 - 1/2*a + 1)
+    sage: F[1][0].residue_field()
+    Residue field of Fractional ideal (a^2 - 2*a + 3)
+    sage: F[2][0].residue_field()
+    Residue field of Fractional ideal (3/2*a^2 - 5/2*a + 4)
+
 AUTHORS:
     -- David Roe (2007-10-3): initial version
@@ -24 +36 @@
     sage: parent(a*a)
     Residue field in zbar of Fractional ideal (17)
+
+Reducing a curve modulo a prime:
+    sage: K.<s> = NumberField(x^2+23)
+    sage: OK = K.ring_of_integers()
+    sage: E = EllipticCurve([0,0,0,K(1),K(5)])
+    sage: pp = K.factor_integer(13)[0][0]
+    sage: Fpp = OK.residue_field(pp)
+    sage: E.base_extend(Fpp)
+    Elliptic Curve defined by y^2  = x^3 + x + 5 over Residue field of Fractional ideal (13, s - 4)
 """
 
@@ -56 +77 @@
 residue_field_cache = {}
 
-def ResidueField(p, names = None, check = True, trygen=False):
+def ResidueField(p, names = None, check = True):
     """
     A function that returns the residue class field of a prime ideal p
@@ -127 +148 @@
         else:
             names = None
-    key = (p, names, trygen)
+    key = (p, names)
     if residue_field_cache.has_key(key):
         k = residue_field_cache[key]()
@@ -152 +173 @@
     gen_ok = False
     from sage.matrix.constructor import matrix
-    if trygen:
-        # This optimization not ready yet. 
-        try:
-            x = K.gen()
-            M = matrix(k, n+1, n, [to_vs(x**i).list() for i in range(n+1)])
-            print M
-            W = M.transpose().echelon_form()
-            if M.rank() == n:
-                PB = M.matrix_from_rows(range(n))
-                gen_ok = True
-                f = R((-W.column(n)).list() + [1])
-        except (TypeError, ZeroDivisionError):
-            pass
+    try:
+        x = K.gen()
+        M = matrix(k, n+1, n, [to_vs(x**i).list() for i in range(n+1)])
+        W = M.transpose().echelon_form()
+        if M.rank() == n:
+            PB = M.matrix_from_rows(range(n))
+            gen_ok = True
+            f = R((-W.column(n)).list() + [1])
+    except (TypeError, ZeroDivisionError):
+        pass
     if not gen_ok:
         bad = True
@@ -200 +218 @@
     """
     The class representing a generic residue field.
+
+    EXAMPLES:
+        sage: I = QQ[i].factor_integer(2)[0][0]; I
+        Fractional ideal (I + 1)
+        sage: k = I.residue_field(); k
+        Residue field of Fractional ideal (I + 1)
+        sage: type(k)
+        <class 'sage.rings.residue_field.ResidueFiniteField_prime_modn'>
     """
     def __init__(self, p, f, intp):
@@ -233 +259 @@
     def lift(self, x):
         """
-        Returns a lift of x to the Order, returning a "polynomial" in the generator with coefficients between 0 and p-1.
-        
+        Returns a lift of x to the Order, returning a "polynomial" in the
+        generator with coefficients between 0 and $p-1$.
+
         EXAMPLES:
             sage: K.<a> = NumberField(x^3-7)
@@ -252 +279 @@
             return self.f.lift(x)
 
+    def reduction_map(self):
+        """
+        Return the partially defined reduction map from the number
+        field to this residue class field.
+
+        EXAMPLES:
+            sage: I = QQ[2^(1/3)].factor_integer(2)[0][0]; I
+            Fractional ideal (-a)
+            sage: k = I.residue_field(); k
+            Residue field of Fractional ideal (-a)
+            sage: pi = k.reduction_map(); pi 
+            Partially defined reduction map from Number Field in a with defining polynomial x^3 - 2 to Residue field of Fractional ideal (-a)
+            sage: pi.domain()
+            Number Field in a with defining polynomial x^3 - 2
+            sage: pi.codomain()
+            Residue field of Fractional ideal (-a)
+        """
+        return self._structure[0]
+
+    def lift_map(self):
+        """
+        EXAMPLES:
+            sage: I = QQ[3^(1/3)].factor_integer(5)[1][0]; I
+            Fractional ideal (-a + 2)
+            sage: k = I.residue_field(); k
+            Residue field of Fractional ideal (-a + 2)
+            sage: f = k.lift_map(); f
+            Lifting map from Residue field of Fractional ideal (-a + 2) to Number Field in a with defining polynomial x^3 - 3
+            sage: f.domain()
+            Residue field of Fractional ideal (-a + 2)
+            sage: f.codomain()
+            Number Field in a with defining polynomial x^3 - 3
+            sage: f(k.0)
+            1
+        """
+        return self._structure[1]
+
     def __cmp__(self, x):
         """
-        Compares two residue fields: they are equal iff the primes defining them are equal.
+        Compares two residue fields: they are equal iff the primes
+        defining them are equal.
         
         EXAMPLES:
@@ -273 +338 @@
 
 class ReductionMap:
+    """
+    A reduction map from a (subset) of a number field to this residue
+    class field. 
+
+    EXAMPLES:
+        sage: I = QQ[sqrt(17)].factor_integer(5)[0][0]; I
+        Fractional ideal (5)
+        sage: k = I.residue_field(); k
+        Residue field in sqrt17bar of Fractional ideal (5)
+        sage: R = k.reduction_map(); R
+        Partially defined reduction map from Number Field in sqrt17 with defining polynomial x^2 - 17 to Residue field in sqrt17bar of Fractional ideal (5)
+    """
     def __init__(self, K, F, to_vs, PBinv):
+        """
+        Create a reduction map.
+
+        EXAMPLES:
+            sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8)
+            sage: F = K.factor_integer(2)[0][0].residue_field()
+            sage: F.reduction_map()
+            Partially defined reduction map from Number Field in a with defining polynomial x^3 + x^2 - 2*x + 8 to Residue field of Fractional ideal (1/2*a^2 - 1/2*a + 1)
+        """
         self.__K = K
         self.__F = F   # finite field
@@ -279 +365 @@
         self.__PBinv = PBinv
 
+    def domain(self):
+        """
+        Return the domain of this reduction map.
+
+        EXAMPLES:
+            sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 32)
+            sage: F = K.factor_integer(2)[0][0].residue_field()
+            sage: F.reduction_map().domain()
+            Number Field in a with defining polynomial x^3 + x^2 - 2*x + 32
+        """
+        return self.__K
+
+    def codomain(self):
+        """
+        Return the codomain of this reduction map.
+
+        EXAMPLES:
+            sage: K.<a> = NumberField(x^3 + 128)
+            sage: F = K.factor_integer(2)[0][0].residue_field()
+            sage: F.reduction_map().codomain()
+            Residue field of Fractional ideal (-1/4*a)        
+        """
+        return self.__F
+
     def __call__(self, x):
+        """
+        Apply this reduction map to an element that coerces into the number field.
+
+        If x doesn't map because the denominator is not coprime to the
+        prime ideal, then a ZeroDivisionError exception is raised. 
+
+        EXAMPLES:
+            sage: K.<a> = NumberField(x^2 + 1)
+            sage: F = K.factor_integer(2)[0][0].residue_field()
+            sage: r = F.reduction_map(); r
+            Partially defined reduction map from Number Field in a with defining polynomial x^2 + 1 to Residue field of Fractional ideal (a + 1)
+            sage: r(2 + a)
+            1
+            sage: r(a/2)
+            Traceback (most recent call last):
+            ...
+            ZeroDivisionError: Inverse does not exist.
+        """
         # The reduction map is just x |--> F(to_vs(x) * (PB**(-1)))
         x = self.__K(x)
@@ -285 +413 @@
 
     def __repr__(self):
+        """
+        EXAMPLES:
+            sage: K.<theta_5> = CyclotomicField(5)
+            sage: F = K.factor_integer(7)[0][0].residue_field()
+            sage: F.reduction_map().__repr__()
+            'Partially defined reduction map from Cyclotomic Field of order 5 and degree 4 to Residue field in theta_5bar of Fractional ideal (7)'
+        """
         return "Partially defined reduction map from %s to %s"%(self.__K, self.__F)
 
 class LiftingMap:
+    """
+    Lifting map from residue class field to number field.
+
+    EXAMPLES:
+        sage: K.<a> = NumberField(x^3 + 2)
+        sage: F = K.factor_integer(5)[0][0].residue_field()
+        sage: F.degree()
+        2
+        sage: L = F.lift_map(); L
+        Lifting map from Residue field in abar of Fractional ideal (a^2 + 2*a - 1) to Number Field in a with defining polynomial x^3 + 2
+        sage: L(F.0^2)
+        3*a + 1
+        sage: L(3*a + 1) == F.0^2
+        True
+    """
     def __init__(self, K, F, to_order, PB):
+        """
+        Create a lifting map.
+
+        EXAMPLES:
+            sage: K.<theta_5> = CyclotomicField(5)
+            sage: F = K.factor_integer(7)[0][0].residue_field()
+            sage: F.lift_map()
+            Lifting map from Residue field in theta_5bar of Fractional ideal (7) to Cyclotomic Field of order 5 and degree 4
+        """
         self.__K = K
         self.__F = F   # finite field
@@ -294 +453 @@
         self.__PB = PB
 
+    def domain(self):
+        """
+        Return the domain of this lifting map.
+
+        EXAMPLES:
+            sage: K.<a> = NumberField(x^5 + 2)
+            sage: F = K.factor_integer(7)[0][0].residue_field()
+            sage: L = F.lift_map(); L
+            Lifting map from Residue field in abar of Fractional ideal (-2*a^4 + a^3 - 4*a^2 + 2*a - 1) to Number Field in a with defining polynomial x^5 + 2
+            sage: L.domain()
+            Residue field in abar of Fractional ideal (-2*a^4 + a^3 - 4*a^2 + 2*a - 1)
+        """
+        return self.__F
+
+    def codomain(self):
+        """
+        Return the codomain of this lifting map.
+
+        EXAMPLES:
+            sage: K.<a> = CyclotomicField(7)
+            sage: F = K.factor_integer(5)[0][0].residue_field()
+            sage: L = F.lift_map(); L
+            Lifting map from Residue field in abar of Fractional ideal (5) to Cyclotomic Field of order 7 and degree 6
+            sage: L.codomain()
+            Cyclotomic Field of order 7 and degree 6        
+        """
+        return self.__K
+
     def __call__(self, x):
+        """
+        Lift from this residue class field to the number field.
+
+        EXAMPLES:
+            sage: K.<a> = CyclotomicField(7)
+            sage: F = K.factor_integer(5)[0][0].residue_field()
+            sage: L = F.lift_map(); L
+            Lifting map from Residue field in abar of Fractional ideal (5) to Cyclotomic Field of order 7 and degree 6
+            sage: L(F.0)
+            a
+            sage: F(a)
+            abar
+        """
         # The lifting map is just x |--> to_order(x * PB)
         x = self.__F(x)
@@ -301 +501 @@
 
     def __repr__(self):
+        """
+        EXAMPLES:
+            sage: K.<theta_12> = CyclotomicField(12)
+            sage: F.<tmod> = K.factor_integer(7)[0][0].residue_field()
+            sage: F.lift_map().__repr__()
+            'Lifting map from Residue field in tmod of Fractional ideal (-3*theta_12^2 + 1) to Cyclotomic Field of order 12 and degree 4'
+        """
         return "Lifting map from %s to %s"%(self.__F, self.__K)
 
@@ -586 +793 @@
                 raise TypeError
 
-        #try:
-        #    return self.coerce_map_from(self.f.domain())(self.f.domain()(x))
-        #except (AttributeError, TypeError):
-        #    return FiniteField_givaro.__call__(self, x)
-
-
+
+