function_field_order.py

#################################################################################
#
# (c) Copyright 2010 William Stein
#
#  This file is part of PSAGE
#
#  PSAGE is free software: you can redistribute it and/or modify
#  it under the terms of the GNU General Public License as published by
#  the Free Software Foundation, either version 3 of the License, or
#  (at your option) any later version.
# 
#  PSAGE is distributed in the hope that it will be useful,
#  but WITHOUT ANY WARRANTY; without even the implied warranty of
#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more details.
# 
#  You should have received a copy of the GNU General Public License
#  along with this program.  If not, see <http://www.gnu.org/licenses/>.
#
#################################################################################


"""
Orders in Function Fields
"""

from sage.structure.parent_gens import ParentWithGens

from sage.rings.ring import IntegralDomain, PrincipalIdealDomain

from sage.rings.ideal import is_Ideal

class FunctionFieldOrder(IntegralDomain):
    def __init__(self, fraction_field):
        """
        EXAMPLES::

            sage: R = FunctionField(QQ,'y').maximal_order()
            sage: isinstance(R, sage.rings.function_field.function_field_order.FunctionFieldOrder)
            True
        """
        self._fraction_field = fraction_field

    def _repr_(self):
        """
        EXAMPLES::

            sage: FunctionField(QQ,'y').maximal_order()._repr_()
            'Maximal order in Rational function field in y over Rational Field'
        """
        return "Order in %s"%self.fraction_field()

    def is_finite(self):
        """
        EXAMPLES::

            sage: FunctionField(QQ,'y').maximal_order().is_finite()
            False
        """
        return False

    def is_field(self, proof=True):
        """
        EXAMPLES::

            sage: FunctionField(QQ,'y').maximal_order().is_field()
            False
        """
        return False

    def is_noetherian(self):
        """
        Return True, since orders in function fields are noetherian.
        
        EXAMPLES::

            sage: FunctionField(QQ,'y').maximal_order().is_noetherian()
            True
        """
        return True

    def fraction_field(self):
        """
        EXAMPLES::

            sage: FunctionField(QQ,'y').maximal_order().fraction_field()
            Rational function field in y over Rational Field
        """
        return self._fraction_field

    def ideal_with_gens_over_base(self, gens):
        """
        Return the fractional ideal with given generators over the
        maximal ideal of the base field.  That this is really an ideal
        is not checked.

        INPUT:

            - ``basis`` -- list of elements that are a basis for the
              ideal over the maximal order of the base field
            
        EXAMPLES::

        We construct an ideal in a rational function field::
        
            sage: R.<y> = FunctionField(QQ)
            sage: S = R.maximal_order()
            sage: I = S.ideal_with_gens_over_base([y]); I
            Ideal (y) of Maximal order in Rational function field in y over Rational Field
            sage: I*I
            Ideal (y^2) of Maximal order in Rational function field in y over Rational Field

        We construct some ideals in a nontrivial function field::

            sage: R.<x> = FunctionField(GF(7)); S.<y> = R[]
            sage: L.<y> = R.extension(y^2 - x^3 - 1)
            sage: M = L.equation_order(); M
            Order in Function field in y defined by y^2 + 6*x^3 + 6
            sage: I = M.ideal_with_gens_over_base([1, y]);  I
            Ideal (1, y) of Order in Function field in y defined by y^2 + 6*x^3 + 6
            sage: I.module()
            Free module of degree 2 and rank 2 over Maximal order in Rational function field in x over Finite Field of size 7
            Echelon basis matrix:
            [1 0]
            [0 1]
        """
        from function_field_ideal import ideal_with_gens_over_base
        return ideal_with_gens_over_base(self, [self(a) for a in gens])

    def ideal(self, *gens):
        """
        Return the fractional ideal generated by the element gens or
        the elements in gens if gens is a list.

        EXAMPLES::

            sage: R.<y> = FunctionField(QQ)
            sage: S = R.maximal_order()
            sage: S.ideal(y)
            Ideal (y) of Maximal order in Rational function field in y over Rational Field

        A fractional ideal of a nontrivial extension::

            sage: R.<x> = FunctionField(GF(7)); S.<y> = R[]
            sage: L.<y> = R.extension(y^2 - x^3 - 1)
            sage: M = L.equation_order()
            sage: M.ideal(1/y)
            Ideal (1, (6/(x^3 + 1))*y) of Order in Function field in y defined by y^2 + 6*x^3 + 6        
        """
        if len(gens) == 1:
            gens = gens[0]
            if not isinstance(gens, (list, tuple)):
                gens = [gens]
        from function_field_ideal import ideal_with_gens
        return ideal_with_gens(self, gens)


        
    

class FunctionFieldOrder_basis(FunctionFieldOrder):
    """
    An order given by a basis over the maximal order of the base
    field.
    """
    def __init__(self, basis, check=True):
        """
        EXAMPLES::

            sage: K.<x> = FunctionField(GF(7)); R.<y> = K[]; L.<Y> = K.extension(y^4 + x*y + 4*x + 1); S = L.equation_order()
            sage: S
            Order in Function field in Y defined by y^4 + x*y + 4*x + 1
            sage: type(S)
            <class 'sage.rings.function_field.function_field_order.FunctionFieldOrder_basis'>
        """
        if len(basis) == 0:
            raise ValueError, "basis must have positive length"
        
        fraction_field = basis[0].parent()
        if len(basis) != fraction_field.degree():
            raise ValueError, "length of basis must equal degree of field"
        
        FunctionFieldOrder.__init__(self, fraction_field)
        
        self._basis = tuple(basis)
        V, fr, to = fraction_field.vector_space()
        R = fraction_field.base_field().maximal_order()
        self._module = V.span([to(b) for b in basis], base_ring=R)
        self._ring = fraction_field.polynomial_ring()
        self._populate_coercion_lists_(coerce_list=[self._ring])
        if check:
            if self._module.rank() != fraction_field.degree():
                raise ValueError, "basis is not a basis"
        IntegralDomain.__init__(self, self, names = fraction_field.variable_names(), normalize = False)

    def _element_constructor_(self, f):
        """
        EXAMPLES::

            sage: R.<y> = FunctionField(QQ)
            sage: R.maximal_order()._element_constructor_(y)
            y
        """
        # HUGE TODO: have to check that f is really in self!!
        if f.parent() is self.fraction_field():
            f = f.element()
        elif f.parent() is self._ring:
            return function_field_element.FunctionFieldElement_rational(self, f)
        return function_field_element.FunctionFieldElement_rational(self, self._ring(f))

    def fraction_field(self):
        """
        EXAMPLES::

            sage: K.<x> = FunctionField(GF(7)); R.<y> = K[]; L.<Y> = K.extension(y^4 + x*y + 4*x + 1); S = L.equation_order()            
            sage: S.fraction_field()
            Function field in Y defined by y^4 + x*y + 4*x + 1
        """
        return self._fraction_field

    def basis(self):
        """
        EXAMPLES::

            sage: K.<x> = FunctionField(GF(7)); R.<y> = K[]; L.<Y> = K.extension(y^4 + x*y + 4*x + 1); S = L.equation_order()            
            sage: S.basis()
            (1, Y, Y^2, Y^3)
        """
        return self._basis

    def free_module(self):
        """
        EXAMPLES::

            sage: K.<x> = FunctionField(GF(7)); R.<y> = K[]; L.<Y> = K.extension(y^4 + x*y + 4*x + 1); S = L.equation_order()
            sage: S.free_module()
            Free module of degree 4 and rank 4 over Maximal order in Rational function field in x over Finite Field of size 7
            Echelon basis matrix:
            [1 0 0 0]
            [0 1 0 0]
            [0 0 1 0]
            [0 0 0 1]        
        """
        return self._module

##     def polynomial_quotient_ring(self):
##         """
##         Return a quotient of a (possibly multivariate) polynomial ring
##         that is isomorphic to self, along with morphisms back and
##         forth.
##         """
##         raise NotImplementedError
    

import function_field_element    
        
class FunctionFieldOrder_rational(PrincipalIdealDomain, FunctionFieldOrder):
    """
    The maximal order in a rational function field.
    """
    def __init__(self, function_field):
        """
        EXAMPLES::
        
            sage: K.<t> = FunctionField(GF(19)); K
            Rational function field in t over Finite Field of size 19
            sage: R = K.maximal_order(); R
            Maximal order in Rational function field in t over Finite Field of size 19
            sage: type(R)
            <class 'sage.rings.function_field.function_field_order.FunctionFieldOrder_rational'>
        """
        FunctionFieldOrder.__init__(self, function_field)
        IntegralDomain.__init__(self, self, names = function_field.variable_names(), normalize = False)
        self._ring = function_field._ring
        self._populate_coercion_lists_(coerce_list=[self._ring])
        self._gen = self(self._ring.gen())
        self._basis = (self(1),)

    def basis(self):
        """
        Return basis (=1) for this order as a module over the polynomial ring.
        
        EXAMPLES::

            sage: K.<t> = FunctionField(GF(19))
            sage: M = K.maximal_order()
            sage: M.basis()
            (1,)
            sage: parent(M.basis()[0])
            Maximal order in Rational function field in t over Finite Field of size 19
        """
        return self._basis
        
    def ideal(self, *gens):
        """
        Return the fractional ideal generated by the element gens or
        the elements in gens if gens is a list.

        EXAMPLES::

            sage: R.<y> = FunctionField(QQ)
            sage: S = R.maximal_order()
            sage: S.ideal(y)
            Ideal (y) of Maximal order in Rational function field in y over Rational Field

        A fractional ideal of a nontrivial extension::

            sage: R.<x> = FunctionField(GF(7)); S.<y> = R[]
            sage: L.<y> = R.extension(y^2 - x^3 - 1)
            sage: M = L.equation_order()
            sage: M.ideal(1/y)
            Ideal (1, (6/(x^3 + 1))*y) of Order in Function field in y defined by y^2 + 6*x^3 + 6

        A non-principal ideal::

            sage: R.<x> = FunctionField(GF(7))
            sage: S = R.maximal_order()
            sage: S.ideal(x^3+1,x^3+6)
            Ideal (1) of Maximal order in Rational function field in x over Finite Field of size 7
            sage: S.ideal((x^2+1)*(x^3+1),(x^3+6)*(x^2+1))
            Ideal (x^2 + 1) of Maximal order in Rational function field in x over Finite Field of size 7    
        """
        if len(gens) == 1:
            gens = gens[0]
            if not isinstance(gens, (list, tuple)):
                if is_Ideal(gens):
                    gens = gens.gens()
                else:
                    gens = [gens]
        from function_field_ideal import ideal_with_gens
        return ideal_with_gens(self, gens)

    def _repr_(self):
        """
        EXAMPLES::
            
            sage: FunctionField(QQ,'y').maximal_order()._repr_()
            'Maximal order in Rational function field in y over Rational Field'
        """
        return "Maximal order in %s"%self.fraction_field()

    def gen(self, n=0):
        """
        EXAMPLES::

            sage: R = FunctionField(QQ,'y').maximal_order(); R.gen()
            y
            sage: R.gen(1)
            Traceback (most recent call last):
            ...
            IndexError: Only one generator.
        """
        if n != 0: raise IndexError, "Only one generator."
        return self._gen

    def ngens(self):
        """
        EXAMPLES::

            sage: R = FunctionField(QQ,'y').maximal_order(); R.ngens()
            1
        """
        return 1

    def _element_constructor_(self, f):
        """
        EXAMPLES::

            sage: R.<y> = FunctionField(QQ)
            sage: R.maximal_order()._element_constructor_(y)
            y
        """
        # HUGE TODO: have to check that f is really in self!!
        
        if f.parent() is self.fraction_field():
            f = f.element()
        if f.parent() is self._ring:
            return function_field_element.FunctionFieldElement_rational(self, f)
        return function_field_element.FunctionFieldElement_rational(self, self._ring(f))

##     def polynomial_quotient_ring(self):
##         """
##         Return a quotient of a (possibly multivariate) polynomial ring
##         that is isomorphic to self, along with morphisms back and
##         forth.

##         EXAMPLES::
##         """
##         return self._ring