Changeset 7727:8915b2343245

Timestamp:

12/02/07 05:13:19 (5 years ago)

Author:

William Stein <wstein@…>

Branch:

default

Message:

work in progress on residue class fields.

Files:

• sage/rings/number_field/number_field_ideal.py (modified) (2 diffs)
• sage/rings/residue_field.pyx (modified) (14 diffs)
• setup.py (modified) (1 diff)

sage/rings/number_field/number_field_ideal.py

@@ -1021 +1021 @@
     V, from_V, to_V = K.absolute_vector_space()
     M = ZZ**(V.dimension())
-    C = [to_V(b) for b in B]
+    C = [to_V(K(b.list())) for b in B]
     return M.span_of_basis(C)
         
@@ -1098 +1098 @@
     
     K    = I.number_field()
-    OK   = K.maximal_order(p)  # really only need a p-maximal order.
+    OK   = K.maximal_order()  # will in the long run only really need a p-maximal order.
     M_OK = OK.free_module()
     M_I  = I.free_module()

sage/rings/residue_field.pyx

@@ -50 +50 @@
 from sage.structure.parent_base import ParentWithBase
 
+from sage.modules.free_module_element import FreeModuleElement
+
 from sage.rings.polynomial.polynomial_ring import PolynomialRing
 
@@ -89 +91 @@
         sage: k.0^3 - 875
         2
+
+    An example where the residue class field is large but of degree 1:
+        sage: K.<a> = NumberField(x^3-875); P = K.ideal(2007).factor()[0][0]; k = K.residue_field(P); k
+        Residue field of Fractional ideal (-2/25*a^2 - 2/5*a - 3)
+        sage: k(a)
+        168
+        sage: k(a)^3 - 875
+        0
+
+    In this example, 2 is an inessential discriminant divisor, so divides
+    the index of ZZ[a] in the maximal order for all a.
+        sage: K.<a> = NumberField(x^3 + x^2 - 2*x + 8); P = K.ideal(2).factor()[0][0]; P
+        Fractional ideal (1/2*a^2 - 1/2*a + 1)
+        sage: F = K.residue_field(P); F
+        Residue field of Fractional ideal (1/2*a^2 - 1/2*a + 1)
+        sage: F(a)
+        0
+        sage: B = K.maximal_order().basis(); B
+        [1, 1/2*a^2 + 1/2*a, a^2]
+        sage: F(B[1])
+        1
+        sage: F(B[2])
+        0
+        sage: F
+        Residue field of Fractional ideal (1/2*a^2 - 1/2*a + 1)
+        sage: F.degree()
+        1
     """
     if isinstance(names, tuple):
@@ -100 +129 @@
         if k is not None:
             return k
-    if PY_TYPE_CHECK(p, Integer):
-        if check and not p.is_prime():
+    if check:
+        if not is_NumberFieldIdeal(p):
+            raise TypeError, "p must be a prime ideal in the ring of integers of a number field."
+        if not p.is_prime():
             raise ValueError, "p must be prime"
-        if names is None:
-            names = 'x'
-        k = ResidueFiniteField_prime_modn(p, names)
-    elif is_NumberFieldIdeal(p):
-        if names is None:
-            names = '%sbar'%(p.number_field().variable_name())
-        if check and not p.is_prime():
-            raise ValueError, "p must be prime"
-        # Should generalize to allowing residue fields of relative extensions to be extensions of finite fields.
-        characteristic = p.smallest_integer()
-
-        K = p.number_field()
-        OK = K.maximal_order() # should change to p.order once this works.
-        
-        U, to_vs, to_order = p._p_quotient(characteristic)
-        k = U.base_ring()
-        R = PolynomialRing(k, names)
-        n = p.residue_class_degree()
-        gen_ok = False
-        from sage.matrix.constructor import matrix
-        try:
-            x = K.gen()
-            M = matrix(k, n+1, n, [to_vs(x**i).list() for i in range(n+1)]).transpose()
-            M.echelonize()
-            if M.rank() == n:
-                gen_ok = True
-                f = R((-M.column(n)).list() + [1])
-        except TypeError:
-            pass
-        if not gen_ok:
-            bad = True
-            for u in U: # using this iterator may not be optimal, we may get a long string of non-generators
-                if u:
-                    x = to_order(u)
-                    M = matrix(k, n+1, n, [to_vs(x**i).list() for i in range(n+1)]).transpose()
-                    M.echelonize()
-                    if M.rank() == n:
-                        f = R((-M.column(n)).list() + [1])
-                        bad = False
-                        break
-            assert not bad, "error -- didn't find a generator."
-        if n == 1:
-            k = ResidueFiniteField_prime_modn(p, names, im_gen = -f[0], intp = p.smallest_integer())
+
+    if names is None:
+        names = '%sbar'%(p.number_field().variable_name())
+    # Should generalize to allowing residue fields of relative extensions to be extensions of finite fields.
+    characteristic = p.smallest_integer()
+
+    K = p.number_field()
+    OK = K.maximal_order() # should change to p.order once this works.
+
+    U, to_vs, to_order = p._p_quotient(characteristic)
+    k = U.base_ring()
+    R = PolynomialRing(k, names)
+    n = p.residue_class_degree()
+    gen_ok = False
+    from sage.matrix.constructor import matrix
+    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:
+        pass
+    if not gen_ok:
+        bad = True
+        for u in U: # using this iterator may not be optimal, we may get a long string of non-generators
+            if u:
+                x = to_order(u)
+                M = matrix(k, n+1, n, [to_vs(x**i).list() for i in range(n+1)])
+                W = M.transpose().echelon_form()
+                if W.rank() == n:
+                    f = R((-W.column(n)).list() + [1])
+                    PB = M.matrix_from_rows(range(n))
+                    bad = False
+                    break
+        assert not bad, "error -- didn't find a generator."
+    if n == 1:
+        k = ResidueFiniteField_prime_modn(p, names, im_gen = -f[0], intp = p.smallest_integer())
+    else:
+        q = characteristic**(f.degree())
+        if q < Integer(2)**Integer(16):
+            k = ResidueFiniteField_givaro(p, q, names, f, characteristic)            
         else:
-            q = characteristic**(f.degree())
-            if q < Integer(2)**Integer(16):
-                k = ResidueFiniteField_givaro(p, q, names, f, characteristic)            
-            else:
-                k = ResidueFiniteField_ext_pari(p, q, names, f, characteristic)
-            k.structure = (U, to_vs, to_order)
-    else: # Add support for primes in other rings later.
-        raise TypeError, "p must be a prime in the integers or a number field"
+            k = ResidueFiniteField_ext_pari(p, q, names, f, characteristic)
+    # end creating field.
+
+    # The reduction map is just x |--> k(to_vs(x) * (PB**(-1)))
+    # The lifting map is just x |--> to_order(x * PB)
+    pi = ReductionMap(K, k, to_vs, PB**(-1))
+    lift = LiftingMap(K, k, to_order, PB)
+    k._structure = (pi, lift)
+                
     residue_field_cache[key] = weakref.ref(k)
     return k
@@ -232 +265 @@
                 return -1
         return cmp(type(self), type(x))
+
+class ReductionMap:
+    def __init__(self, K, F, to_vs, PBinv):
+        self.__K = K
+        self.__F = F   # finite field
+        self.__to_vs = to_vs
+        self.__PBinv = PBinv
+
+    def __call__(self, x):
+        # The reduction map is just x |--> F(to_vs(x) * (PB**(-1)))
+        x = self.__K(x)
+        return self.__F(self.__to_vs(x) * self.__PBinv)
+
+    def __repr__(self):
+        return "Partially defined reduction map from %s to %s"%(self.__K, self.__F)
+
+class LiftingMap:
+    def __init__(self, K, F, to_order, PB):
+        self.__K = K
+        self.__F = F   # finite field
+        self.__to_order = to_order
+        self.__PB = PB
+
+    def __call__(self, x):
+        # The lifting map is just x |--> to_order(x * PB)
+        x = self.__F(x)
+        v = x.polynomial().padded_list(self.__F.degree())
+        return self.__to_order(self.__PB.linear_combination_of_rows(v))
+
+    def __repr__(self):
+        return "Lifting map from %s to %s"%(self.__F, self.__K)
 
 cdef class NFResidueFieldHomomorphism(ResidueFieldHomomorphism):
@@ -276 +340 @@
         """
         self.im_gen = im_gen
-        self.p = p
+        self.p = p 
         ResidueFieldHomomorphism.__init__(self,Hom(p.number_field().maximal_order(), k, Rings())) # should eventually change to p.order()
 
@@ -291 +355 @@
             13*abar^2 + 7*abar + 21
         """
-        y = x.polynomial().change_ring(self.codomain().base_ring())(self.im_gen)  #polynomial should change to absolute_polynomial?
+        #y = x.polynomial().change_ring(self.codomain().base_ring())(self.im_gen)  #polynomial should change to absolute_polynomial?
+        y = self.codomain()(x)
         (<Element>y)._set_parent_c(self.codomain())
         return y        
@@ -303 +368 @@
             sage: K.<a> = NumberField(x^3-7)
             sage: P = K.ideal(29).factor()[0][0]
-            sage: k =K.residue_field(P)
+            sage: k = K.residue_field(P)
             sage: OK = K.maximal_order()
             sage: f = k.coerce_map_from(OK)
@@ -315 +380 @@
         if self.domain() is ZZ:
             return x.lift()
-        return self.domain()(x.polynomial().change_ring(self.domain().base_ring())(self.domain().ring_generators()[0]))  #polynomial should change to absolute_polynomial?
+        else:
+            return self.codomain()._structure[1](x)
+           
+        # return self.domain()(x.polynomial().change_ring(self.domain().base_ring())(self.domain().ring_generators()[0]))  #polynomial should change to absolute_polynomial?
         
 
@@ -346 +414 @@
         """
         INPUT:
-           p -- An integral prime or a prime ideal of a number field.
+           p -- A prime ideal of a number field.
            name -- the name of the generator of this extension
            im_gen -- the image of the generator of the number field in this finite field.
@@ -384 +452 @@
         """
         try:
-            return self.coerce_map_from(self.f.domain())(self.f.domain()(x))
-        except (AttributeError, TypeError):
             return FiniteField_prime_modn.__call__(self, x)
+        except TypeError:
+            if isinstance(x, FreeModuleElement):
+                return FiniteField_prime_modn.__call__(self, x[0])
+            else:
+                return self._structure[0](x)
+        #try:
+        #    return self.coerce_map_from(self.f.domain())(self.f.domain()(x))
+        #except (AttributeError, TypeError):
+        #    return FiniteField_prime_modn.__call__(self, x)
 
 class ResidueFiniteField_ext_pari(ResidueField_generic, FiniteField_ext_pari):
@@ -395 +470 @@
         sage: K.<a> = NumberField(x^3-7)
         sage: P = K.ideal(923478923).factor()[0][0]
-        sage: k =K.residue_field(P)
+        sage: k = K.residue_field(P)
         sage: k.degree()
         2
@@ -438 +513 @@
         """
         try:
-            return self.coerce_map_from(self.f.domain())(self.f.domain()(x))
-        except (AttributeError, TypeError):
             return FiniteField_ext_pari.__call__(self, x)
+        except TypeError:
+            return self._structure[0](x)
+        #try:
+        #    return self.coerce_map_from(self.f.domain())(self.f.domain()(x))
+        #except (AttributeError, TypeError):
+        #    return FiniteField_ext_pari.__call__(self, x)
 
 class ResidueFiniteField_givaro(ResidueField_generic, FiniteField_givaro):
@@ -474 +553 @@
             sage: K.<a> = NumberField(x^4+3*x^2-17)
             sage: P = K.ideal(61).factor()[0][0]
-            sage: k =K.residue_field(P)
+            sage: k = K.residue_field(P)
         """
         FiniteField_givaro.__init__(self, q, name, g)
@@ -494 +573 @@
         """
         try:
-            return self.coerce_map_from(self.f.domain())(self.f.domain()(x))
-        except (AttributeError, TypeError):
             return FiniteField_givaro.__call__(self, x)
-
+        except TypeError:
+            try:
+                return self._structure[0](x)
+            except:
+                raise TypeError
+
+        #try:
+        #    return self.coerce_map_from(self.f.domain())(self.f.domain()(x))
+        #except (AttributeError, TypeError):
+        #    return FiniteField_givaro.__call__(self, x)
+
+

setup.py

@@ -1099 +1099 @@
 if not sdist and do_cython:
     cython(ext_modules)
+    pass
 
 code = setup(name        = 'sage',