function_field.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/>.
#
#################################################################################


r"""
Function fields

EXAMPLES::

We create an extension of a rational function fields, and do some
simple arithmetic in it::

    sage: K.<x> = FunctionField(GF(5^2,'a')); K
    Rational function field in x over Finite Field in a of size 5^2
    sage: R.<y> = K[]
    sage: L.<y> = K.extension(y^5 - (x^3 + 2*x*y + 1/x)); L
    Function field in y defined by y^5 + 3*x*y + (4*x^4 + 4)/x
    sage: y^4
    y^4
    sage: y^5
    2*x*y + (x^4 + 1)/x
    sage: a = 1/y; a
    (4*x/(4*x^4 + 4))*y^4 + 2*x^2/(4*x^4 + 4)
    sage: a * y
    1

We next make an extension of the above function field, illustrating
that arithmetic with a tower of 3 fields is fully supported::

    sage: S.<t> = L[]
    sage: M.<t> = L.extension(t^2 - x*y)
    sage: M
    Function field in t defined by t^2 + 4*x*y
    sage: t^2
    x*y
    sage: 1/t
    ((1/(x^4 + 1))*y^4 + 2*x/(4*x^4 + 4))*t
    sage: M.base_field()
    Function field in y defined by y^5 + 3*x*y + (4*x^4 + 4)/x
    sage: M.base_field().base_field()
    Rational function field in x over Finite Field in a of size 5^2
    
"""

from sage.structure.category_object import CategoryObject
from sage.rings.ring import Field
from sage.rings.integer_ring import ZZ
from sage.structure.parent_gens import ParentWithGens
import function_field_element

from category import FunctionFields
CAT = FunctionFields()

import maps

def is_FunctionField(x):
    """
    Return True if x is of function field type.

    EXAMPLES::
    
        sage: from sage.rings.function_field.all import is_FunctionField
        sage: is_FunctionField(QQ)
        False
        sage: is_FunctionField(FunctionField(QQ,'t'))
        True
    """
    return isinstance(x, FunctionField)


class FunctionField(Field):
    """
    The abstract base class for all function fields. 
    
    EXAMPLES::
    
        sage: K.<x> = FunctionField(QQ)
        sage: isinstance(K, sage.rings.function_field.function_field.FunctionField)
        True
    """
    def characteristic(self):
        """
        Return the characteristic of this function field.

        EXAMPLES::

            sage: R.<t> = FunctionField(QQ)
            sage: R.characteristic()
            0
            sage: R.<t> = FunctionField(GF(7))
            sage: R.characteristic()
            7        
        """
        return self.constant_field().characteristic()
    
    def is_finite(self):
        """
        Return whether this function field is finite, which it is not.

        EXAMPLES::

            sage: R.<t> = FunctionField(QQ)
            sage: R.is_finite()
            False
            sage: R.<t> = FunctionField(GF(7))
            sage: R.is_finite()
            False
        """
        return False
    
    def extension(self, f, names=None):
        """
        Create an extension L = K[y]/(f(y)) of a function field,
        defined by a univariate polynomial in one variable over this
        function field K.

        INPUT:
        
            - `f` -- a univariate polynomial over self
            - ``names`` -- None or string or length-1 tuple

        OUTPUT:

            - a function field
        
        EXAMPLES::
        
            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: K.extension(y^5 - x^3 - 3*x + x*y)
            Function field in y defined by y^5 + x*y - x^3 - 3*x


        A nonintegral defining polynomial::

            sage: K.<t> = FunctionField(QQ); R.<y> = K[]
            sage: K.extension(y^3 + (1/t)*y + t^3/(t+1))
            Function field in y defined by y^3 + 1/t*y + t^3/(t + 1)

        The defining polynomial need not be monic or integral::

            sage: K.extension(t*y^3 + (1/t)*y + t^3/(t+1))
            Function field in y defined by t*y^3 + 1/t*y + t^3/(t + 1)
        """
        if names is None:
            names = f.variable_name()
        return FunctionField_polymod(f, names)

    def order_with_basis(self, basis, check=True):
        """
        Return the order with given basis over the maximal order of
        the base field.

        INPUT:

           - ``basis`` -- a list of elements of self
           - ``check`` -- bool (default: True); if True, check that
             the basis is really linearly independent

        OUTPUT:

            - an order in this function field

        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]; L.<Y> = K.extension(y^3 + x^3 + 4*x + 1)
            sage: O = L.order_with_basis([1, Y, Y^2]); O
            Order in Function field in Y defined by y^3 + x^3 + 4*x + 1
            sage: O.basis()
            (1, Y, Y^2)
            sage: O = L.order_with_basis([x, x^2 + x*Y, (2/3)*Y^2]); O
            Order in Function field in Y defined by y^3 + x^3 + 4*x + 1
            sage: O.basis()
            (x, x*Y + x^2, 2/3*Y^2)
        """
        from function_field_order import FunctionFieldOrder_basis
        return FunctionFieldOrder_basis([self(a) for a in basis], check=check)

    def order(self, x, check=True):
        """
        Return the order in this function field generated over the
        maximal order by x or the elements of x if x is a list.

        INPUT:
        
           - ``x`` -- element of self, or a list of elements of self
           - ``check`` -- bool (default: True); if True, check that
             x really generates an order

        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]; L.<Y> = K.extension(y^3 + x^3 + 4*x + 1)
            sage: O = L.order(Y); O
            Order in Function field in Y defined by y^3 + x^3 + 4*x + 1
            sage: O.basis()
            (1, Y, Y^2)

            sage: Z = K.order(x); Z
            Order in Rational function field in x over Rational Field
            sage: Z.basis()
            (1,)

        Orders with multiple generators, not yet supported::

            sage: Z = K.order([x,x^2]); Z
            Traceback (most recent call last):
            ...
            NotImplementedError
        """
        if not isinstance(x, (list, tuple)):
            x = [x]
        if len(x) == 1:
            g = x[0]
            basis = [self(1)]
            for i in range(self.degree()-1):
                basis.append(basis[-1]*g)
        else:
            raise NotImplementedError
        return self.order_with_basis(basis, check=check)

    def _coerce_map_from_(self, R):
        """
        Return True if there is a coerce map from R to self.

        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]; L.<Y> = K.extension(y^3 + x^3 + 4*x + 1)
            sage: L.equation_order()
            Order in Function field in Y defined by y^3 + x^3 + 4*x + 1
            sage: L._coerce_map_from_(L.equation_order())
            True
            sage: L._coerce_map_from_(GF(7))
            False
        """
        from function_field_order import FunctionFieldOrder
        if isinstance(R, FunctionFieldOrder) and R.fraction_field() == self:
            return True
        return False

    def hom(self, im_gens, base_morphism=None):
        """
        Create a homomorphism from self to another function field.
        
        INPUT:

           - ``im_gens`` -- a list of images of the generators of self
             and of successive base rings.
           
           - ``base_morphism`` -- (default: None) a homomorphism of
             the base ring, after the im_gens are used.  Thus if
             im_gens has length 2, then base_morphism should be a morphism
             from self.base_ring().base_ring().

        EXAMPLES::
        
        We create a rational function field, and a quadratic extension of it::
        
            sage: R.<x> = FunctionField(QQ); S.<y> = R[]
            sage: L.<y> = R.extension(y^2 - x^3 - 1)

        We make the field automorphism that sends y to -y::
        
            sage: f = L.hom(-y); f
            Morphism of function fields defined by y |--> -y

        Evaluation works::
        
            sage: f(y*x - 1/x)
            -x*y - 1/x

        We try to define an invalid morphism::
        
            sage: f = L.hom(y+1); f
            Traceback (most recent call last):
            ...
            ValueError: invalid morphism

        We make a morphism of the base rational function field::
        
            sage: phi = R.hom(x+1); phi
            Morphism of function fields defined by x |--> x + 1
            sage: phi(x^3 - 3)
            x^3 + 3*x^2 + 3*x - 2
            sage: (x+1)^3-3
            x^3 + 3*x^2 + 3*x - 2

        We make a morphism by specifying where the generators and the
        base generators go::
        
            sage: L.hom([-y, x])
            Morphism of function fields defined by y |--> -y,  x |--> x

        We make another extension of a rational function field::
        
            sage: R2.<t> = FunctionField(QQ); S2.<w> = R2[]
            sage: L2.<w> = R.extension((4*w)^2 - (t+1)^3 - 1)

        We define a morphism, by givin the images of generators::
        
            sage: f = L.hom([4*w, t+1]); f
            Morphism of function fields defined by y |--> 4*w,  x |--> t + 1

        Evaluation works, as expected::
        
            sage: f(y+x)
            4*w + t + 1
            sage: f(x*y + x/(x^2+1))
            (4*t + 4)*w + (t + 1)/(t^2 + 2*t + 2)
        """
        if not isinstance(im_gens, (list,tuple)):
            im_gens = [im_gens]
        if len(im_gens) > 1:
            base_morphism = self.base_field().hom(im_gens[1:], base_morphism)
        return maps.FunctionFieldMorphism(self.Hom(im_gens[0].parent()), im_gens[0], base_morphism)

class FunctionField_polymod(FunctionField):
    """
    A function field defined by a univariate polynomial, as an
    extension of the base field.
    
    EXAMPLES::

    We make a function field defined by a degree 5 polynomial over the
    rational function field over the rational numbers::
    
        sage: K.<x> = FunctionField(QQ)
        sage: R.<y> = K[]
        sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x)); L
        Function field in w defined by y^5 - 2*x*y + (-x^4 - 1)/x

    We next make a function field over the above nontrivial function
    field L::

        sage: S.<T> = L[]
        sage: M.<alpha> = L.extension(T^2 + w*T + y); M
        Function field in alpha defined by T^2 + w*T + w
        sage: 1/alpha
        ((x/(-x^4 - 1))*w^4 - 2*x^2/(-x^4 - 1))*alpha - 1
        sage: alpha * (1/alpha)
        1

    We drill down the tower of function fields::
    
        sage: M.base_field()
        Function field in w defined by y^5 - 2*x*y + (-x^4 - 1)/x
        sage: M.base_field().base_field()
        Rational function field in x over Rational Field
        sage: M.base_field().base_field().constant_field()
        Rational Field
        sage: M.constant_base_field()
        Rational Field
    """
    def __init__(self, polynomial, names, category=CAT):
        """
        Create a function field defined as an extension of another
        function field by adjoining a root of a univariate polynomial.

        INPUT:

            - ``polynomial`` -- a univariate polynomial over a function field
            - ``names`` -- variable names (as a tuple of length 1 or string)
            - ``category`` -- a category (defaults to category of function fields)
        
        EXAMPLES::

        We create an extension of function fields::
        
            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L = K.extension(y^5 - x^3 - 3*x + x*y); L
            Function field in y defined by y^5 + x*y - x^3 - 3*x

        Note the type::
        
            sage: type(L)
            <class 'sage.rings.function_field.function_field.FunctionField_polymod_with_category'>

        We can set the variable name, which doesn't have to be y::
        
            sage: L.<w> = K.extension(y^5 - x^3 - 3*x + x*y); L
            Function field in w defined by y^5 + x*y - x^3 - 3*x
        """
        from sage.rings.polynomial.all import is_Polynomial
        if names is None:
            names = (polynomial.variable_name(), )
        if not is_Polynomial(polynomial):
            raise TypeError, "polynomial must be a polynomial"
        if polynomial.degree() <= 0:
            raise ValueError, "polynomial must have positive degree"
        base_field = polynomial.base_ring()
        if not isinstance(base_field, FunctionField):
            raise TypeError, "polynomial must be over a function"
        self._base_field = base_field
        self._polynomial = polynomial
        
        ParentWithGens.__init__(self, base_field,
                                names=names, category = category)

        self._hash = hash(polynomial)
        self._ring = self._polynomial.parent()
        self._populate_coercion_lists_(coerce_list=[base_field, self._ring])
        self._gen = self(self._ring.gen())

    def __hash__(self):
        """
        Return hash of this function field.
        
        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L = K.extension(y^5 - x^3 - 3*x + x*y); hash(L)
            3183366741743088279             # 64-bit
            ?                               # 32-bit

        """
        return self._hash

    def monic_integral_model(self, names):
        """
        Return a function field isomorphic to self, but with defining
        polynomial that is monic and integral over the base field.

        INPUT::

            - ``names`` -- name of the generator of the new field this function constructs

        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<alpha> = K.extension(x^2*y^5 - 1/x); L
            Function field in alpha defined by x^2*y^5 - 1/x
            sage: A, from_A, to_A = L.monic_integral_model('beta')
            sage: A
            Function field in beta defined by y^5 - x^12
            sage: from_A
            Morphism of function fields defined by beta |--> x^3*alpha
            sage: to_A
            Morphism of function fields defined by alpha |--> 1/x^3*beta
            sage: to_A(alpha)
            1/x^3*beta
            sage: from_A(to_A(alpha))
            alpha
            sage: from_A(to_A(1/alpha))
            x^3*alpha^4
            sage: from_A(to_A(1/alpha)) == 1/alpha
            True            
        """
        g, d = self._make_monic(self.polynomial())
        R = self.base_field()
        K = R.extension(g, names=names)
        to_K = self.hom(K.gen() / d)
        from_K = K.hom(self.gen() * d)
        return K, from_K, to_K

    def _make_monic(self, f):
        r"""
        Let alpha be a root of f.  This function returns a monic
        integral polynomial g and an element d of the base field such
        that g(alpha*d) = 0.
        
        EXAMPLES::
        
            sage: K.<x> = FunctionField(QQ); R.<y> = K[];
            sage: L.<alpha> = K.extension(x^2*y^5 - 1/x)
            sage: g, d = L._make_monic(L.polynomial()); g,d
            (y^5 - x^12, x^3)
            sage: g(alpha*d)
            0
        """
        R = f.base_ring()
        if not isinstance(R, RationalFunctionField):
            raise NotImplementedError
        
        # make f monic
        n = f.degree()
        c = f.leading_coefficient()
        if c != 1:
            f = f / c

        # find lcm of denominators
        from sage.rings.arith import lcm
        # would be good to replace this by minimal...
        d = lcm([b.denominator() for b in f.list() if b])
        if d != 1:
            x = f.parent().gen()
            g = (d**n) * f(x/d)
        else:
            g = f
        return g, d

    def constant_field(self):
        """
        Return the algebraic closure of the constant field of the base
        field in this function field.

        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x))
            sage: L.constant_field()
            Traceback (most recent call last):
            ...
            NotImplementedError
        """
        raise NotImplementedError

    def constant_base_field(self):
        """
        Return the constant field of the base rational function field.
                
        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x)); L
            Function field in w defined by y^5 - 2*x*y + (-x^4 - 1)/x
            sage: L.constant_base_field()
            Rational Field
        """
        return self.base_field().constant_base_field()

    def degree(self):
        """
        Return the degree of this function field over its base
        function field.
        
        EXAMPLES::

            sage: K.<x> = FunctionField(QQ)
            sage: R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x)); L
            Function field in w defined by y^5 - 2*x*y + (-x^4 - 1)/x
            sage: L.degree()
            5        
        """
        return self._polynomial.degree()
        
    def _repr_(self):
        """
        Return string representation of this function field.
        
        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x))
            sage: L._repr_()
            'Function field in w defined by y^5 - 2*x*y + (-x^4 - 1)/x'
        """
        return "Function field in %s defined by %s"%(self.variable_name(), self._polynomial)

    def base_field(self):
        """
        Return the base field of this function field.  This function
        field is presented as L = K[y]/(f(y)), and the base field is
        by definition the field K.
        
        EXAMPLES::
            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x))
            sage: L.base_field()
            Rational function field in x over Rational Field
        """
        return self._base_field

    def random_element(self, *args, **kwds):
        """
        Create a random element of this function field.  Parameters
        are passed onto the random_element method of the base_field.

        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^2 - (x^2 + x))
            sage: L.random_element()
            ((x^2 - x + 2/3)/(x^2 + 1/3*x - 1))*w^2 + ((-1/4*x^2 + 1/2*x - 1)/(-5/2*x + 2/3))*w + (-1/2*x^2 - 4)/(-12*x^2 + 1/2*x - 1/95)
        """
        return self(self._ring.random_element(degree=self.degree(), *args, **kwds))

    def polynomial(self):
        """
        Return the univariate polynomial that defines this function
        field, i.e., the polynomial f(y) so that this function field
        is of the form K[y]/(f(y)).
        
        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x))
            sage: L.polynomial()
            y^5 - 2*x*y + (-x^4 - 1)/x
        """
        return self._polynomial

    def polynomial_ring(self):
        """
        Return the polynomial ring used to represents elements of this
        function field.  If we view this function field as being presented
        as K[y]/(f(y)), then this function returns the ring K[y].
        
        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x))
            sage: L.polynomial_ring()
            Univariate Polynomial Ring in y over Rational function field in x over Rational Field
        """
        return self._ring

    def vector_space(self):
        """
        Return a vector space V and isomorphisms self --> V and V --> self.

        This function allows us to identify the elements of self with
        elements of a vector space over the base field, which is
        useful for representation and arithmetic with orders, ideals,
        etc.
        
        OUTPUT:

            -  ``V`` - a vector space over the rational numbers
            -  ``from_V`` - an isomorphism from V to self
            -  ``to_V`` - an isomorphism from self to V

        EXAMPLES::

        We define a function field::
        
            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x)); L
            Function field in w defined by y^5 - 2*x*y + (-x^4 - 1)/x

        We get the vector spaces, and maps back and forth::
        
            sage: V, from_V, to_V = L.vector_space()
            sage: V
            Vector space of dimension 5 over Rational function field in x over Rational Field
            sage: from_V
            Isomorphism map:
              From: Vector space of dimension 5 over Rational function field in x over Rational Field
              To:   Function field in w defined by y^5 - 2*x*y + (-x^4 - 1)/x
            sage: to_V
            Isomorphism map:
              From: Function field in w defined by y^5 - 2*x*y + (-x^4 - 1)/x
              To:   Vector space of dimension 5 over Rational function field in x over Rational Field

        We convert an element of the vector space back to the function field::
        
            sage: from_V(V.1)
            w

        We define an interesting element of the function field::
        
            sage: a = 1/L.0; a
            (-x/(-x^4 - 1))*w^4 + 2*x^2/(-x^4 - 1)

        We convert it to the vector space, and get a vector over the base field::
        
            sage: to_V(a)
            (2*x^2/(-x^4 - 1), 0, 0, 0, -x/(-x^4 - 1))

        We convert to and back, and get the same element::
        
            sage: from_V(to_V(a)) == a
            True

        In the other direction::

            sage: v = x*V.0 + (1/x)*V.1
            sage: to_V(from_V(v)) == v
            True
        """
        try: return self._vector_space
        except AttributeError:
            V = self.base_field()**self.degree()
            from_V = maps.MapVectorSpaceToFunctionField(V, self)
            to_V   = maps.MapFunctionFieldToVectorSpace(self, V)
            self._vector_space = (V, from_V, to_V)
            return self._vector_space
        

    def maximal_order(self):
        """
        Return the maximal_order of self.  If we view self as L =
        K[y]/(f(y)), then this is the ring of elements of L that are
        integral over K.
        
        EXAMPLES::

        This is not yet implemented...::
        
            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x))
            sage: L.maximal_order()
            Traceback (most recent call last):
            ...
            NotImplementedError
        """
        raise NotImplementedError

    def _element_constructor_(self, x):
        r"""
        Make x into an element of this function field, possibly not canonically.

        INPUT:
        
            - ``x`` - the element
         
        OUTPUT:
        
            ``x``, as an element of this function field

        TESTS::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x))
            sage: L._element_constructor_(L.polynomial_ring().gen())
            w
        """
        if x.parent() is self._ring:
            return function_field_element.FunctionFieldElement_polymod(self, x)
        if isinstance(x, function_field_element.FunctionFieldElement):
            return function_field_element.FunctionFieldElement_polymod(self, self._ring(x.element()))            
        return function_field_element.FunctionFieldElement_polymod(self, self._ring(x))
    

    def gen(self, n=0):
        """
        Return the n-th generator of this function field.  By default n=0; any other
        value of n leads to an error.   The generator is the class of y, if we view
        self as being presented as K[y]/(f(y)).
        
        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x))
            sage: L.gen()
            w
            sage: L.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):
        """
        Return the number of generators of this function field over
        its base field.  This is by definition 1.
        
        EXAMPLES::
        
            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x))
            sage: L.ngens()
            1
        """
        return 1

    def equation_order(self):
        """
        If we view self as being presented as K[y]/(f(y)), then this
        function returns the order generated by the class of y.  If f
        is not monic, then self._make_monic is called, and instead we
        get the order generated by some integral multiple of a root of
        alpha.
        
        EXAMPLES::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<w> = K.extension(y^5 - (x^3 + 2*x*y + 1/x))
            sage: L.equation_order()
            Order in Function field in w defined by y^5 - 2*x*y + (-x^4 - 1)/x

        We try an example, in which the defining polynomial is not
        monic and is not integral::

            sage: K.<x> = FunctionField(QQ); R.<y> = K[]
            sage: L.<alpha> = K.extension(x^2*y^5 - 1/x); L
            Function field in alpha defined by x^2*y^5 - 1/x
            sage: O = L.equation_order(); O
            Order in Function field in alpha defined by x^2*y^5 - 1/x
            sage: O.basis()
            (1, x^3*alpha, x^6*alpha^2, x^9*alpha^3, x^12*alpha^4)
        """
        d = self._make_monic(self.polynomial())[1]
        return self.order(d*self.gen(), check=False)
    

class RationalFunctionField(FunctionField):
    """
    A rational function field K(t) in one variable, over an arbitrary
    base field.
    
    EXAMPLES::

        sage: K.<t> = FunctionField(GF(3)); K
        Rational function field in t over Finite Field of size 3
        sage: K.gen()
        t
        sage: 1/t + t^3 + 5
        (t^4 + 2*t + 1)/t

    There are various ways to get at the underlying fields and rings
    associated to a rational function field::

        sage: K.<t> = FunctionField(GF(7))
        sage: K.base_field()
        Rational function field in t over Finite Field of size 7
        sage: K.field()
        Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 7
        sage: K.constant_field()
        Finite Field of size 7
        sage: K.maximal_order()
        Maximal order in Rational function field in t over Finite Field of size 7

    We define a morphism::

        sage: K.<W> = FunctionField(QQ)
        sage: L = FunctionField(QQ, 'tbar')         # give var name as second input
        sage: K.hom(L.gen())
        Morphism of function fields defined by W |--> tbar
    """
    def __init__(self, constant_field, names, category=CAT):
        """
        Create a rational function field in one variable.

        INPUT:

            - ``constant_field`` -- an arbitrary field
            - ``names`` -- a string or tuple of length 1
            - ``category`` -- default: FunctionFields()
        
        EXAMPLES::

            sage: K.<t> = FunctionField(CC); K
            Rational function field in t over Complex Field with 53 bits of precision
            sage: K.category()
            Category of function fields
            sage: FunctionField(QQ[I], 'alpha')
            Rational function field in alpha over Number Field in I with defining polynomial x^2 + 1

        Must be over a field::
        
            sage: FunctionField(ZZ, 't')
            Traceback (most recent call last):
            ...
            TypeError: constant_field must be a field
        """
        if names is None:
            raise ValueError, "variable name must be specified"
        elif not isinstance(names, tuple):
            names = (names, )
        if not constant_field.is_field():
            raise TypeError, "constant_field must be a field"
        ParentWithGens.__init__(self, self, names=names, category = category)
        R = constant_field[names[0]]
        self._hash = hash((constant_field, names))
        self._constant_field = constant_field
        self._ring = R
        self._field = R.fraction_field()
        self._populate_coercion_lists_(coerce_list=[self._field])
        self._gen = self(R.gen())

    def __hash__(self):
        """
        Return hash of this function field.

        EXAMPLES::
        
            sage: K.<t> = FunctionField(QQ)
            sage: hash(K)
            502145503910697533              # 64-bit
            ?                               # 32-bit            
        """
        return self._hash

    def _repr_(self):
        """
        Return string representation of this function field.
        
        EXAMPLES::
        
            sage: K.<t> = FunctionField(QQ)
            sage: K._repr_()
            'Rational function field in t over Rational Field'
        """
        return "Rational function field in %s over %s"%(
            self.variable_name(), self._constant_field)

    def _element_constructor_(self, x):
        r"""
        Coerce x into an element of this function field, possibly not canonically.

        INPUT:
        
            - ``x`` - the element
         
        OUTPUT:
        
            ``x``, as an element of this function field

        EXAMPLES::
        
            sage: K.<t> = FunctionField(QQ)
            sage: a = K._element_constructor_(K.maximal_order().gen()); a
            t
            sage: a.parent()
            Rational function field in t over Rational Field
        """
        if x.parent() is self._field:
            return function_field_element.FunctionFieldElement_rational(self, x)
        if isinstance(x, function_field_element.FunctionFieldElement):
            return function_field_element.FunctionFieldElement_rational(self, self._field(x.element()))
        if x.parent() is self.polynomial_ring():
            return x[0]
        return function_field_element.FunctionFieldElement_rational(self, self._field(x))

    # nonoptimized
    def _to_bivariate_polynomial(self, f):
        """
        Convert f from a univariate polynomial over the rational function
        field into a bivariate polynomial and a denominator.

        INPUT:

            - f -- a univariate polynomial over self.

        OUTPUT:

            - 2-variate polynomial, denominator

        EXAMPLES::
        
            sage: R.<t> = FunctionField(GF(7))
            sage: S.<X> = R[]
            sage: f = (1/t)*(X^4 - 1/t^2)*(X^3 - t^3)
            sage: R._to_bivariate_polynomial(f)
            (x^7*t^2 - x^4*t^5 - x^3 + t^3, t^3)        
        """
        v = f.list()
        from sage.rings.arith import LCM
        denom = LCM([a.denominator() for a in v])
        S = denom.parent()
        x,t = S.base_ring()['x,t'].gens()
        phi = S.hom([t])
        return sum([phi((denom * v[i]).numerator()) * x**i for i in range(len(v))]), denom

    def _factor_univariate_polynomial(self, f, proof=True):
        """
        Factor the univariate polynomial f over self.

        EXAMPLES::

        We do a factorization over the function field over the rationals::

            sage: R.<t> = FunctionField(QQ)
            sage: S.<X> = R[]
            sage: f = (1/t)*(X^4 - 1/t^2)*(X^3 - t^3)
            sage: f.factor()             # indirect doctest
            (1/t) * (X - t) * (X^2 - 1/t) * (X^2 + 1/t) * (X^2 + t*X + t^2)
            sage: f.factor().prod() == f
            True        

        You must pass in proof=False over finite fields, due to
        Singular's factoring algorithm being incomplete::

            sage: R.<t> = FunctionField(GF(7))
            sage: S.<X> = R[]
            sage: f = (1/t)*(X^4 - 1/t^2)*(X^3 - t^3)
            sage: f.factor()
            Traceback (most recent call last):
            ...
            NotImplementedError: proof = True factorization not implemented.  Call factor with proof=False.
            sage: f.factor(proof=False)
            (1/t) * (X + 3*t) * (X + 5*t) * (X + 6*t) * (X^2 + 1/t) * (X^2 + 6/t)
            sage: f.factor(proof=False).prod() == f
            True

        Factoring over a function field over a non-prime finite field::

            sage: k.<a> = GF(9)
            sage: R.<t> = FunctionField(k)
            sage: S.<X> = R[]
            sage: f = (1/t)*(X^3 - a*t^3)
            sage: f.factor(proof=False)
            (1/t) * (X + (a + 2)*t)^3
            sage: f.factor(proof=False).prod() == f
            True
        """
        F, d = self._to_bivariate_polynomial(f)
        fac = F.factor(proof=proof)
        x = f.parent().gen()
        t = f.parent().base_ring().gen()
        phi = F.parent().hom([x, t])
        v = [(phi(P),e) for P, e in fac]
        unit = phi(fac.unit())/d
        w = []
        for a, e in v:
            c = a.leading_coefficient()
            a = a/c
            unit *= (c**e)
            w.append((a,e))
        from sage.structure.factorization import Factorization
        return Factorization(w, unit=unit)

    def polynomial_ring(self, var='x'):
        """
        Return polynomial ring K[var] that could be used to represent
        elements of self, if self were viewed as K[var]/(var).
        
        EXAMPLES::
        
            sage: K.<x> = FunctionField(QQ)
            sage: K.polynomial_ring()
            Univariate Polynomial Ring in x over Rational function field in x over Rational Field
            sage: K.polynomial_ring('T')
            Univariate Polynomial Ring in T over Rational function field in x over Rational Field
        """
        if var != 'x': return self[var]
        try: return self._polynomial_ring
        except AttributeError:
            self._polynomial_ring = self[var]
            return self._polynomial_ring

    def vector_space(self):
        """
        Return a vector space V and isomorphisms self --> V and V --> self.
        
        OUTPUT:

            -  ``V`` - a vector space over the rational numbers
            -  ``from_V`` - an isomorphism from V to self
            -  ``to_V`` - an isomorphism from self to V

        EXAMPLES::

            sage: K.<x> = FunctionField(QQ)
            sage: K.vector_space()
            (Vector space of dimension 1 over Rational function field in x over Rational Field, Isomorphism map:
              From: Vector space of dimension 1 over Rational function field in x over Rational Field
              To:   Rational function field in x over Rational Field, Isomorphism map:
              From: Rational function field in x over Rational Field
              To:   Vector space of dimension 1 over Rational function field in x over Rational Field)
        """
        try: return self._vector_space
        except AttributeError:
            V = self.base_field()**1
            from_V = maps.MapVectorSpaceToFunctionField(V, self)
            to_V   = maps.MapFunctionFieldToVectorSpace(self, V)
            self._vector_space = (V, from_V, to_V)
            return self._vector_space

    def random_element(self, *args, **kwds):
        """
        Create a random element of this rational function field.
        Parameters are passed onto the random_element method of the
        underlying fraction field.

        EXAMPLES::

            sage: FunctionField(QQ,'alpha').random_element()
            (-1/2*alpha^2 - 4)/(-12*alpha^2 + 1/2*alpha - 1/95)
        """
        return self(self._field.random_element(*args, **kwds))

    def degree(self):
        """
        Return the degree over the base field of this rational
        function field, which is 1.
        
        EXAMPLES::
        
            sage: K.<t> = FunctionField(QQ)
            sage: K.degree()
            1
        """
        return ZZ(1)
    
    def gen(self, n=0):
        """
        Return the n-th generator of this function field.  If n is not
        0, then an IndexError is raised.

        EXAMPLES::
            
            sage: K.<t> = FunctionField(QQ); K.gen()
            t
            sage: K.gen().parent()
            Rational function field in t over Rational Field
            sage: K.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):
        """
        Return the number of generators, which is 1.
        
        EXAMPLES::

            sage: K.<t> = FunctionField(QQ)
            sage: K.ngens()
            1
        """
        return 1
    
    def base_field(self):
        """
        Return the base field of this rational function field, which is just
        this function field itself.
        
        EXAMPLES::
        
            sage: K.<t> = FunctionField(GF(7))
            sage: K.base_field()
            Rational function field in t over Finite Field of size 7
        """
        return self

    def hom(self, im_gens, base_morphism=None):
        """
        Create a homomorphism from self to another function field.

        INPUT:

            - ``im_gens`` -- exactly one element of some function field
            - ``base_morphism`` -- ignored

        OUTPUT:

            - a map between function fields

        EXAMPLES::

        We make a map from a rational function field to itself::

            sage: R.<x> = FunctionField(GF(7))
            sage: R.hom( (x^4 + 2)/x)
            Morphism of function fields defined by x |--> (x^4 + 2)/x        
        
        We construct a map from a rational function field into a
        non-rational extension field::
        
            sage: R.<x> = FunctionField(GF(7)); S.<y> = R[]
            sage: L.<y> = R.extension(y^3 + 6*x^3 + x)
            sage: f = R.hom(y^2 + y  + 2); f
            Morphism of function fields defined by x |--> y^2 + y + 2
            sage: f(x)
            y^2 + y + 2
            sage: f(x^2)
            5*y^2 + (x^3 + 6*x + 4)*y + 2*x^3 + 5*x + 4        
        """
        if isinstance(im_gens, CategoryObject):
            return self.Hom(im_gens).natural_map()
        if not isinstance(im_gens, (list,tuple)):
            im_gens = [im_gens]
        if len(im_gens) != 1:
            raise ValueError, "there must be exactly one generator"
        x = im_gens[0]
        return maps.FunctionFieldMorphism_rational(self.Hom(x.parent()), x)

    def field(self):
        """
        Return the underlying field, forgetting the function field
        structure.
        
        EXAMPLES::

            sage: K.<t> = FunctionField(GF(7))
            sage: K.field()
            Fraction Field of Univariate Polynomial Ring in t over Finite Field of size 7
        """
        return self._field

    def maximal_order(self):
        """
        Return the maximal order of this function field.  Since this
        is a rational function field it is of the form K(t), and the
        maximal order is by definition K[t].
        
        EXAMPLES::
        
            sage: K.<t> = FunctionField(QQ)
            sage: K.maximal_order()
            Maximal order in Rational function field in t over Rational Field
            sage: K.equation_order()
            Maximal order in Rational function field in t over Rational Field
        """
        try: return self._maximal_order
        except AttributeError:
            from function_field_order import FunctionFieldOrder_rational
            self._maximal_order = FunctionFieldOrder_rational(self)
            return self._maximal_order

    equation_order = maximal_order

    def constant_base_field(self):
        """
        Return the field that this rational function field is a
        transcendental extension of.

        EXAMPLES::

            sage: K.<t> = FunctionField(QQ)
            sage: K.constant_field()
            Rational Field
        """
        return self._constant_field

    constant_field = constant_base_field