smoothchar.py

r"""
Smooth characters of `p`-adic fields

Let `F` be a finite extension of `\QQ_p`. Then we may consider the group of
smooth (i.e. locally constant) group homomorphisms `F^\times \to L^\times`, for
`L` any field. Such characters are important since they can be used to
parametrise smooth representations of `\mathrm{GL}_2(\QQ_p)`, which arise as
the local components of modular forms.

This module contains classes to represent such characters when `F` is `\QQ_p`
or a quadratic extension. In the latter case, we choose a quadratic extension
`K` of `\QQ` whose completion at `p` is `F`, and use Sage's wrappers of the
Pari ``idealstar`` and ``ideallog`` methods to work in the finite group
`\mathcal{O}_K / p^c` for `c \ge 0`.

An example with characters of `\QQ_7`::

    sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
    sage: K.<z> = CyclotomicField(42)
    sage: G = SmoothCharacterGroupQp(7, K)
    sage: G.unit_gens(2), G.exponents(2)
    ([3, 7], [42, 0])

The output of the last line means that the group `\QQ_7^\times / (1 + 7^2
\ZZ_7)` is isomorphic to `C_{42} \times \ZZ`, with the two factors being
generated by `3` and `7` respectively. We create a character by specifying the
images of these generators::

    sage: chi = G.character(2, [z^5, 11 + z]); chi
    Character of Q_7*, of level 2, mapping 3 |--> z^5, 7 |--> z + 11
    sage: chi(4)
    z^8
    sage: chi(42)
    z^10 + 11*z^9

Characters are themselves group elements, and basic arithmetic on them works::

    sage: chi**3
    Character of Q_7*, of level 2, mapping 3 |--> z^8 - z, 7 |--> z^3 + 33*z^2 + 363*z + 1331
    sage: chi.multiplicative_order()
    +Infinity
"""

import operator
from sage.structure.element     import MultiplicativeGroupElement
from sage.structure.parent_base import ParentWithBase
from sage.structure.sequence    import Sequence
from sage.rings.all             import QQ, ZZ, Zmod, NumberField
from sage.rings.ring import is_Ring
from sage.misc.cachefunc        import cached_method
from sage.misc.abstract_method  import abstract_method
from sage.misc.misc_c           import prod
from sage.categories.groups     import Groups
from sage.functions.other       import ceil
from sage.misc.mrange           import xmrange

from sage.structure.element import FieldElement

class SmoothCharacterGeneric(MultiplicativeGroupElement):
    r"""
    A smooth (i.e. locally constant) character of `F^\times`, for `F` some
    finite extension of `\QQ_p`.
    """
    def __init__(self, parent, c, values_on_gens):
        r"""
        Standard init function.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(2, QQ)
            sage: G.character(0, [17]) # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 0, mapping 2 |--> 17
            sage: G.character(1, [1, 17]) # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 0, mapping 2 |--> 17
            sage: G.character(2, [1, -1, 1, 17]) # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 2, mapping s |--> 1, 2*s + 1 |--> -1, -1 |--> 1, 2 |--> 17
            sage: G.character(2, [1, 1, 1, 17]) # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 0, mapping 2 |--> 17
        """
        MultiplicativeGroupElement.__init__(self, parent)
        self._c = c
        self._values_on_gens = values_on_gens
        self._check_level()

    def _check_level(self):
        r"""
        Checks that this character has the level it claims to have, and if not,
        decrement the level by 1. This is called by :meth:`__init__`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(5, QQ).character(5, [-1, 7]) # indirect doctest
            Character of Q_5*, of level 1, mapping 2 |--> -1, 5 |--> 7
        """
        if self.level() == 0: return
        v = self.parent().subgroup_gens(self.level())
        if all([self(x) == 1 for x in v]):
            new_gens = self.parent().unit_gens(self.level() - 1)
            new_values = [self(x) for x in new_gens]
            self._values_on_gens = Sequence(new_values, universe=self.base_ring(), immutable=True)
            self._c = self._c - 1
            self._check_level()

    def __cmp__(self, other):
        r"""
        Compare self and other. Note that this only gets called when the
        parents of self and other are identical.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp, SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupQp(7, Zmod(3)).character(1, [2, 1]) == SmoothCharacterGroupQp(7, ZZ).character(1, [-1, 1])
            True
            sage: chi1 = SmoothCharacterGroupUnramifiedQuadratic(7, QQ).character(0, [1])
            sage: chi2 = SmoothCharacterGroupQp(7, QQ).character(0, [1])
            sage: chi1 == chi2
            False
            sage: chi2.parent()(chi1) == chi2
            True
            sage: chi1 == loads(dumps(chi1))
            True
        """
        assert other.parent() is self.parent()
        return cmp(self.level(), other.level()) or cmp(self._values_on_gens, other._values_on_gens)

    def multiplicative_order(self):
        r"""
        Return the order of this character as an element of the character group.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(42)
            sage: G = SmoothCharacterGroupQp(7, K)
            sage: G.character(3, [z^10 - z^3, 11]).multiplicative_order()
            +Infinity
            sage: G.character(3, [z^10 - z^3, 1]).multiplicative_order()
            42
            sage: G.character(1, [z^7, z^14]).multiplicative_order()
            6
            sage: G.character(0, [1]).multiplicative_order()
            1
        """
        from sage.rings.arith import lcm
        from sage.rings.infinity import Infinity
        if self._values_on_gens[-1].multiplicative_order() == Infinity:
            return Infinity
        else:
            return lcm([x.multiplicative_order() for x in self._values_on_gens])

    def level(self):
        r"""
        Return the level of this character, i.e. the smallest integer `c \ge 0`
        such that it is trivial on `1 + \mathfrak{p}^c`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, QQ).character(2, [-1, 1]).level()
            1
        """
        return self._c

    def __call__(self, x):
        r"""
        Evaluate the character at ``x``, which should be a nonzero element of
        the number field of the parent group.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(42)
            sage: chi = SmoothCharacterGroupQp(7, K).character(3, [z^10 - z^3, 11])
            sage: [chi(x) for x in [1, 2, 3, 9, 21, 1/12345678]]
            [1, -z, z^10 - z^3, -z^11 - z^10 + z^8 + z^7 - z^6 - z^5 + z^3 + z^2 - 1, 11*z^10 - 11*z^3, z^7 - 1]

        Non-examples::

            sage: chi(QuadraticField(-1,'i').gen())
            Traceback (most recent call last):
            ...
            TypeError: no canonical coercion from Number Field in i with defining polynomial x^2 + 1 to Rational Field
            sage: chi(0)
            Traceback (most recent call last):
            ...
            ValueError: cannot evaluate at zero
            sage: chi(Mod(1, 12))
            Traceback (most recent call last):
            ...
            TypeError: no canonical coercion from Ring of integers modulo 12 to Rational Field

        Some examples with an unramified quadratic extension, where the choice
        of generators is arbitrary (but deterministic)::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: K.<z> = CyclotomicField(30)
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(5, K)
            sage: chi = G.character(2, [z**5, z**(-6), z**6, 3]); chi
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 2, mapping 11*s - 10 |--> z^5, 6 |--> -z^7 - z^6 + z^3 + z^2 - 1, 5*s + 1 |--> z^6, 5 |--> 3
            sage: chi(G.unit_gens(2)[0]**7 / G.unit_gens(2)[1]/5)
            1/3*z^6 - 1/3*z
            sage: chi(2)
            -z^3
        """
        v = self.parent().discrete_log(self.level(), x)
        return prod([self._values_on_gens[i] ** v[i] for i in xrange(len(v))])

    def _repr_(self):
        r"""
        String representation of this character.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(20)
            sage: SmoothCharacterGroupQp(5, K).character(2, [z, z+1])._repr_()
            'Character of Q_5*, of level 2, mapping 2 |--> z, 5 |--> z + 1'

        Examples over field extensions::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: K.<z> = CyclotomicField(15)
            sage: SmoothCharacterGroupUnramifiedQuadratic(5, K).character(2, [z**5, z**3, 1, z+1])._repr_()
            'Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 2, mapping 11*s - 10 |--> z^5, 6 |--> z^3, 5*s + 1 |--> 1, 5 |--> z + 1'
        """
        gens = self.parent().unit_gens(self.level())
        mapst = ", ".join( str(gens[i]) + ' |--> ' + str(self._values_on_gens[i]) for i in range(len(gens)) )
        return "Character of %s, of level %s, mapping %s" % (self.parent()._field_name(), self.level(), mapst)

    def _mul_(self, other):
        r"""
        Product of self and other.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(20)
            sage: chi1 = SmoothCharacterGroupQp(5, K).character(2, [z, z+1])
            sage: chi2 = SmoothCharacterGroupQp(5, K).character(2, [z^4, 3])
            sage: chi1 * chi2 # indirect doctest
            Character of Q_5*, of level 1, mapping 2 |--> z^5, 5 |--> 3*z + 3
            sage: chi2 * chi1 # indirect doctest
            Character of Q_5*, of level 1, mapping 2 |--> z^5, 5 |--> 3*z + 3
            sage: chi1 *  SmoothCharacterGroupQp(5, QQ).character(2, [-1, 7]) # indirect doctest
            Character of Q_5*, of level 2, mapping 2 |--> -z, 5 |--> 7*z + 7
        """
        if other.level() > self.level():
            return other * self
        return self.parent().character(self.level(), [self(x) * other(x) for x in self.parent().unit_gens(self.level())])

    def __invert__(self):
        r"""
        Multiplicative inverse of self.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: K.<z> = CyclotomicField(12)
            sage: chi = SmoothCharacterGroupUnramifiedQuadratic(2, K).character(4, [z**4, z**3, z**9, -1, 7]); chi
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 4, mapping s |--> z^2 - 1, 2*s + 1 |--> z^3, 4*s + 1 |--> -z^3, -1 |--> -1, 2 |--> 7
            sage: chi**(-1) # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 4, mapping s |--> -z^2, 2*s + 1 |--> -z^3, 4*s + 1 |--> z^3, -1 |--> -1, 2 |--> 1/7
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).character(0, [7]) / chi # indirect doctest
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 4, mapping s |--> -z^2, 2*s + 1 |--> -z^3, 4*s + 1 |--> z^3, -1 |--> -1, 2 |--> 1
        """
        return self.parent().character(self.level(), [~self(x) for x in self.parent().unit_gens(self.level())])

    def restrict_to_Qp(self):
        r"""
        Return the restriction of this character to `\QQ_p^\times`, embedded as
        a subfield of `F^\times`.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: SmoothCharacterGroupRamifiedQuadratic(3, 0, QQ).character(0, [2]).restrict_to_Qp()
            Character of Q_3*, of level 0, mapping 3 |--> 4
        """
        G = SmoothCharacterGroupQp(self.parent().prime(), self.base_ring())
        ugs = G.unit_gens(self.level())
        return G.character(self.level(), [self(x) for x in ugs])

    def galois_conjugate(self):
        r"""
        Return the composite of this character with the order `2` automorphism of
        `K / \QQ_p` (assuming `K` is quadratic).

        Note that this is the Galois operation on the *domain*, not on the
        *codomain*.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: K.<w> = CyclotomicField(3)
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(2, K)
            sage: chi = G.character(2, [w, -1,-1, 3*w])
            sage: chi2 = chi.galois_conjugate(); chi2
            Character of unramified extension Q_2(s)* (s^2 + s + 1 = 0), of level 2, mapping s |--> -w - 1, 2*s + 1 |--> 1, -1 |--> -1, 2 |--> 3*w

            sage: chi.restrict_to_Qp() == chi2.restrict_to_Qp()
            True
            sage: chi * chi2 == chi.parent().compose_with_norm(chi.restrict_to_Qp())
            True
        """
        K,s = self.parent().number_field().objgen()
        if K.absolute_degree() != 2:
            raise ValueError( "Character must be defined on a quadratic extension" )
        sigs = K.embeddings(K)
        sig = [x for x in sigs if x(s) != s][0]
        return self.parent().character(self.level(), [self(sig(x)) for x in self.parent().unit_gens(self.level())])


class SmoothCharacterGroupGeneric(ParentWithBase):
    r"""
    The group of smooth (i.e. locally constant) characters of a `p`-adic field,
    with values in some ring `R`. This is an abstract base class and should not
    be instantiated directly.
    """

    Element = SmoothCharacterGeneric

    def __init__(self, p, base_ring):
        r"""
        TESTS::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: G = SmoothCharacterGroupGeneric(3, QQ)
            sage: SmoothCharacterGroupGeneric(3, "hello")
            Traceback (most recent call last):
            ...
            TypeError: base ring (=hello) must be a ring
        """
        if not is_Ring(base_ring):
            raise TypeError( "base ring (=%s) must be a ring" % base_ring )
        ParentWithBase.__init__(self, base=base_ring, category=Groups())
        if not (p in ZZ and ZZ(p).is_prime()):
            raise ValueError( "p (=%s) must be a prime integer" % p )
        self._p = ZZ.coerce(p)

    def _element_constructor_(self, x):
        r"""
        Construct an element of this group from ``x`` (possibly noncanonically).
        This only works if ``x`` is a character of a field containing the field of
        self, whose values lie in a field that can be converted into self.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<i> = QuadraticField(-1)
            sage: G = SmoothCharacterGroupQp(3, QQ)
            sage: GK = SmoothCharacterGroupQp(3, K)
            sage: chi = GK(G.character(0, [4])); chi # indirect doctest
            Character of Q_3*, of level 0, mapping 3 |--> 4
            sage: chi.parent() is GK
            True
            sage: G(GK.character(0, [7])) # indirect doctest
            Character of Q_3*, of level 0, mapping 3 |--> 7
            sage: G(GK.character(0, [i])) # indirect doctest
            Traceback (most recent call last):
            ...
            TypeError: Unable to coerce i to a rational
        """
        if x == 1:
            return self.character(0, [1])
        if hasattr(x, 'parent') \
          and isinstance(x.parent(), SmoothCharacterGroupGeneric) \
          and x.parent().number_field().has_coerce_map_from(self.number_field()):
            return self.character(x.level(), [x(v) for v in self.unit_gens(x.level())])
        else:
            raise TypeError

    def __cmp__(self, other):
        r"""
        TESTS::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: G = SmoothCharacterGroupQp(3, QQ)
            sage: G == SmoothCharacterGroupQp(3, QQ[I])
            False
            sage: G == 7
            False
            sage: G == SmoothCharacterGroupQp(7, QQ)
            False
            sage: G == SmoothCharacterGroupQp(3, QQ)
            True
        """
        return cmp(type(self), type(other)) \
            or cmp(self.prime(), other.prime()) \
            or cmp(self.number_field(), other.number_field()) \
            or cmp(self.base_ring(), other.base_ring())

    def _coerce_map_from_(self, other):
        r"""
        Return True if self has a canonical coerce map from other.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<i> = QuadraticField(-1)
            sage: G = SmoothCharacterGroupQp(3, QQ)
            sage: GK = SmoothCharacterGroupQp(3, K)
            sage: G.has_coerce_map_from(GK)
            False
            sage: GK.has_coerce_map_from(G)
            True
            sage: GK.coerce(G.character(0, [4]))
            Character of Q_3*, of level 0, mapping 3 |--> 4
            sage: G.coerce(GK.character(0, [4]))
            Traceback (most recent call last):
            ...
            TypeError: no canonical coercion from Group of smooth characters of Q_3* with values in Number Field in i with defining polynomial x^2 + 1 to Group of smooth characters of Q_3* with values in Rational Field
            sage: G.character(0, [4]) in GK # indirect doctest
            True

        The coercion framework handles base extension, so we test that too::

            sage: K.<i> = QuadraticField(-1)
            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(3, QQ)
            sage: G.character(0, [1]).base_extend(K)
            Character of unramified extension Q_3(s)* (s^2 + 2*s + 2 = 0), of level 0, mapping 3 |--> 1

        """
        if isinstance(other, SmoothCharacterGroupGeneric) \
          and other.number_field() == self.number_field() \
          and self.base_ring().has_coerce_map_from(other.base_ring()):
            return True
        else:
            return False

    def prime(self):
        r"""
        The residue characteristic of the underlying field.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).prime()
            3
        """
        return self._p

    @abstract_method
    def change_ring(self, ring):
        r"""
        Return the character group of the same field, but with values in a
        different coefficient ring. To be implemented by all derived classes
        (since the generic base class can't know the parameters).

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).change_ring(ZZ)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method change_ring at ...>
        """
        pass

    def base_extend(self, ring):
        r"""
        Return the character group of the same field, but with values in a new
        coefficient ring into which the old coefficient ring coerces. An error
        will be raised if there is no coercion map from the old coefficient
        ring to the new one.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: G = SmoothCharacterGroupQp(3, QQ)
            sage: G.base_extend(QQbar)
            Group of smooth characters of Q_3* with values in Algebraic Field
            sage: G.base_extend(Zmod(3))
            Traceback (most recent call last):
            ...
            TypeError: no canonical coercion from Rational Field to Ring of integers modulo 3

        """
        if not ring.has_coerce_map_from(self.base_ring()) :
            ring.coerce(self.base_ring().an_element())
            # this is here to flush out errors

        return self.change_ring(ring)

    @abstract_method
    def _field_name(self):
        r"""
        A string representing the name of the p-adic field of which this is the
        character group. To be overridden by derived subclasses.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ)._field_name()
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method _field_name at ...>
        """
        pass

    def _repr_(self):
        r"""
        String representation of self.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, QQ)._repr_()
            'Group of smooth characters of Q_7* with values in Rational Field'
        """
        return "Group of smooth characters of %s with values in %s" % (self._field_name(), self.base_ring())

    @abstract_method
    def ideal(self, level):
        r"""
        Return the ``level``-th power of the maximal ideal of the ring of
        integers of the p-adic field. Since we approximate by using number
        field arithmetic, what is actually returned is an ideal in a number
        field.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).ideal(3)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method ideal at ...>
        """
        pass

    @abstract_method
    def unit_gens(self, level):
        r"""
        A list of generators `x_1, \dots, x_d` of the abelian group `F^\times /
        (1 + \mathfrak{p}^c)^\times`, where `c` is the given level, satisfying
        no relations other than `x_i^{n_i} = 1` for each `i` (where the
        integers `n_i` are returned by :meth:`exponents`). We adopt the
        convention that the final generator `x_d` is a uniformiser (and `n_d =
        0`).

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).unit_gens(3)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method unit_gens at ...>
        """
        pass

    @abstract_method
    def exponents(self, level):
        r"""
        The orders `n_1, \dots, n_d` of the generators `x_i` of `F^\times / (1
        + \mathfrak{p}^c)^\times` returned by :meth:`unit_gens`.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).exponents(3)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method exponents at ...>
        """
        pass

    @abstract_method
    def subgroup_gens(self, level):
        r"""
        A set of elements of `(\mathcal{O}_F / \mathfrak{p}^c)^\times`
        generating the kernel of the reduction map to `(\mathcal{O}_F /
        \mathfrak{p}^{c-1})^\times`.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).subgroup_gens(3)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method subgroup_gens at ...>
        """
        pass

    @abstract_method
    def discrete_log(self, level):
        r"""
        Given an element `x \in F^\times` (lying in the number field `K` of
        which `F` is a completion, see module docstring), express the class of
        `x` in terms of the generators of `F^\times / (1 +
        \mathfrak{p}^c)^\times` returned by :meth:`unit_gens`.

        This should be overridden by all derived classes. The method should
        first attempt to canonically coerce `x` into ``self.number_field()``,
        and check that the result is not zero.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupGeneric
            sage: SmoothCharacterGroupGeneric(3, QQ).discrete_log(3)
            Traceback (most recent call last):
            ...
            NotImplementedError: <abstract method discrete_log at ...>
        """
        pass

    def character(self, level, values_on_gens):
        r"""
        Return the unique character of the given level whose values on the
        generators returned by ``self.unit_gens(level)`` are
        ``values_on_gens``.

        INPUT:

        - ``level`` (integer) an integer `\ge 0`
        - ``values_on_gens`` (sequence) a sequence of elements of length equal
          to the length of ``self.unit_gens(level)``. The values should be
          convertible (that is, possibly noncanonically) into the base ring of self; they
          should all be units, and all but the last must be roots of unity (of
          the orders given by ``self.exponents(level)``.

        .. note::

            The character returned may have level less than ``level`` in general.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(42)
            sage: G = SmoothCharacterGroupQp(7, K)
            sage: G.character(2, [z^6, 8])
            Character of Q_7*, of level 2, mapping 3 |--> z^6, 7 |--> 8
            sage: G.character(2, [z^7, 8])
            Character of Q_7*, of level 1, mapping 3 |--> z^7, 7 |--> 8

        Non-examples::

            sage: G.character(1, [z, 1])
            Traceback (most recent call last):
            ...
            ValueError: value on generator 3 (=z) should be a root of unity of order 6
            sage: G.character(1, [1, 0])
            Traceback (most recent call last):
            ...
            ValueError: value on uniformiser 7 (=0) should be a unit

        An example with a funky coefficient ring::

            sage: G = SmoothCharacterGroupQp(7, Zmod(9))
            sage: G.character(1, [2, 2])
            Character of Q_7*, of level 1, mapping 3 |--> 2, 7 |--> 2
            sage: G.character(1, [2, 3])
            Traceback (most recent call last):
            ...
            ValueError: value on uniformiser 7 (=3) should be a unit

        TESTS::

            sage: G.character(1, [2])
            Traceback (most recent call last):
            ...
            AssertionError: 2 images must be given
        """
        S = Sequence(values_on_gens, universe=self.base_ring(), immutable=True)
        assert len(S) == len(self.unit_gens(level)), "{0} images must be given".format(len(self.unit_gens(level)))
        n = self.exponents(level)
        for i in xrange(len(S)):
            if n[i] != 0 and not S[i]**n[i] == 1:
                raise ValueError( "value on generator %s (=%s) should be a root of unity of order %s" % (self.unit_gens(level)[i], S[i], n[i]) )
            elif n[i] == 0 and not S[i].is_unit():
                raise ValueError( "value on uniformiser %s (=%s) should be a unit" % (self.unit_gens(level)[i], S[i]) )
        return self.element_class(self, level, S)

    def _an_element_(self):
        r"""
        Return an element of this group. Required by the coercion machinery.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: K.<z> = CyclotomicField(42)
            sage: G = SmoothCharacterGroupQp(7, K)
            sage: G.an_element() # indirect doctest
            Character of Q_7*, of level 0, mapping 7 |--> z
        """
        return self.character(0, [self.base_ring().an_element()])



    def _test_unitgens(self, **options):
        r"""
        Test that the generators returned by ``unit_gens`` are consistent with
        the exponents returned by ``exponents``.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, Zmod(8))._test_unitgens()
        """
        T = self._tester(**options)
        for c in xrange(6):
            gens = self.unit_gens(c)
            exps = self.exponents(c)
            T.assert_(exps[-1] == 0)
            T.assert_(all([u != 0 for u in exps[:-1]]))
            T.assert_(all([u.parent() is self.number_field() for u in gens]))

            I = self.ideal(c)
            for i in xrange(len(exps[:-1])):
                g = gens[i]
                for m in xrange(1, exps[i]):
                    if (g - 1 in I):
                        T.fail("For generator g=%s, g^%s = %s = 1 mod I, but order should be %s" % (gens[i], m, g, exps[i]))
                    g = g * gens[i]
                    # reduce g mod I
                    if hasattr(I, "small_residue"):
                        g = I.small_residue(g)
                    else: # I is an ideal of ZZ
                        g = g % (I.gen())
                if not (g - 1 in I):
                    T.fail("For generator g=%s, g^%s = %s, which is not 1 mod I" % (gens[i], exps[i], g))
            I = self.prime() if self.number_field() == QQ else self.ideal(1)
            T.assert_(gens[-1].valuation(I) == 1)

            # This implicitly tests that the gens really are gens!
            _ = self.discrete_log(c, -1)

    def _test_subgroupgens(self, **options):
        r"""
        Test that the values returned by :meth:`~subgroup_gens` are valid.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(2, CC)._test_subgroupgens()
        """
        T = self._tester(**options)
        for c in xrange(1, 6):
            sgs = self.subgroup_gens(c)
            I2 = self.ideal(c-1)
            T.assert_(all([x-1 in I2 for x in sgs]), "Kernel gens at level %s not in kernel!" % c)

            # now find the exponent of the kernel

            n1 = prod(self.exponents(c)[:-1])
            n2 = prod(self.exponents(c-1)[:-1])
            n = n1 // n2
            # if c > 1, n will be a prime here, so that logs below gets calculated correctly

            logs = []
            for idx in xmrange(len(sgs)*[n]):
                y = prod( map(operator.pow, sgs, idx) )
                L = tuple(self.discrete_log(c, y))
                if L not in logs:
                    logs.append(L)
            T.assert_(n2 * len(logs) == n1, "Kernel gens at level %s don't generate everything!" % c)

    def compose_with_norm(self, chi):
        r"""
        Calculate the character of `K^\times` given by `\chi \circ \mathrm{Norm}_{K/\QQ_p}`.
        Here `K` should be a quadratic extension and `\chi` a character of `\QQ_p^\times`.

        EXAMPLE:

        When `K` is the unramified quadratic extension, the level of the new character is the same as the old::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp, SmoothCharacterGroupRamifiedQuadratic, SmoothCharacterGroupUnramifiedQuadratic
            sage: K.<w> = CyclotomicField(6)
            sage: G = SmoothCharacterGroupQp(3, K)
            sage: chi = G.character(2, [w, 5])
            sage: H = SmoothCharacterGroupUnramifiedQuadratic(3, K)
            sage: H.compose_with_norm(chi)
            Character of unramified extension Q_3(s)* (s^2 + 2*s + 2 = 0), of level 2, mapping -2*s |--> -1, 4 |--> -w, 3*s + 1 |--> w - 1, 3 |--> 25

        In ramified cases, the level of the new character may be larger:

        .. link

        ::

            sage: H = SmoothCharacterGroupRamifiedQuadratic(3, 0, K)
            sage: H.compose_with_norm(chi)
            Character of ramified extension Q_3(s)* (s^2 - 3 = 0), of level 3, mapping 2 |--> w - 1, s + 1 |--> -w, s |--> -5

        On the other hand, since norm is not surjective, the result can even be trivial:

        .. link

        ::

            sage: chi = G.character(1, [-1, -1]); chi
            Character of Q_3*, of level 1, mapping 2 |--> -1, 3 |--> -1
            sage: H.compose_with_norm(chi)
            Character of ramified extension Q_3(s)* (s^2 - 3 = 0), of level 0, mapping s |--> 1
        """
        if chi.parent().number_field() != QQ: raise ValueError
        if self.number_field().absolute_degree() != 2: raise ValueError
        n = chi.level()
        P = chi.parent().prime() ** n
        m = self.number_field()(P).valuation(self.ideal(1))
        return self.character(m, [chi(x.norm(QQ)) for x in self.unit_gens(m)])

class SmoothCharacterGroupQp(SmoothCharacterGroupGeneric):
    r"""
    The group of smooth characters of `\QQ_p^\times`, with values in some fixed
    base ring.

    EXAMPLES::

        sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
        sage: G = SmoothCharacterGroupQp(7, QQ); G
        Group of smooth characters of Q_7* with values in Rational Field
        sage: TestSuite(G).run()
        sage: G == loads(dumps(G))
        True
    """
    def unit_gens(self, level):
        r"""
        Return a set of generators `x_1, \dots, x_d` for `\QQ_p^\times / (1 +
        p^c \ZZ_p)^\times`. These must be independent in the sense that there
        are no relations between them other than relations of the form
        `x_i^{n_i} = 1`. They need not, however, be in Smith normal form.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, QQ).unit_gens(3)
            [3, 7]
            sage: SmoothCharacterGroupQp(2, QQ).unit_gens(4)
            [15, 5, 2]
        """
        if level == 0:
            return [QQ(self.prime())]
        else:
            return [QQ(x) for x in Zmod(self.prime()**level).unit_gens()] + [QQ(self.prime())]

    def exponents(self, level):
        r"""
        Return the exponents of the generators returned by :meth:`unit_gens`.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, QQ).exponents(3)
            [294, 0]
            sage: SmoothCharacterGroupQp(2, QQ).exponents(4)
            [2, 4, 0]
        """
        if level == 0: return [0]
        return [x.multiplicative_order() for x in Zmod(self.prime()**level).unit_gens()] + [0]

    def change_ring(self, ring):
        r"""
        Return the group of characters of the same field but with values in a
        different ring. This need not have anything to do with the original
        base ring, and in particular there won't generally be a coercion map
        from self to the new group -- use
        :meth:`~SmoothCharacterGroupGeneric.base_extend` if you want this.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, Zmod(3)).change_ring(CC)
            Group of smooth characters of Q_7* with values in Complex Field with 53 bits of precision
        """
        return SmoothCharacterGroupQp(self.prime(), ring)

    def number_field(self):
        r"""
        Return the number field used for calculations (a dense subfield of the
        local field of which this is the character group). In this case, this
        is always the rational field.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, Zmod(3)).number_field()
            Rational Field
        """
        return QQ

    def ideal(self, level):
        r"""
        Return the ``level``-th power of the maximal ideal. Since we
        approximate by using rational arithmetic, what is actually returned is
        an ideal of `\ZZ`.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, Zmod(3)).ideal(2)
            Principal ideal (49) of Integer Ring
        """
        return ZZ.ideal(self.prime() ** level)

    def _field_name(self):
        r"""
        Return a string representation of the field unit group of which this is
        the character group.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: SmoothCharacterGroupQp(7, Zmod(3))._field_name()
            'Q_7*'
        """
        return "Q_%s*" % self.prime()

    def discrete_log(self, level, x):
        r"""
        Express the class of `x` in `\QQ_p^\times / (1 + p^c)^\times` in terms
        of the generators returned by :meth:`unit_gens`.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: G = SmoothCharacterGroupQp(7, QQ)
            sage: G.discrete_log(0, 14)
            [1]
            sage: G.discrete_log(1, 14)
            [2, 1]
            sage: G.discrete_log(5, 14)
            [9308, 1]
        """
        x = self.number_field().coerce(x)
        if x == 0: raise ValueError( "cannot evaluate at zero" )
        s = x.valuation(self.prime())
        return Zmod(self.prime()**level)(x / self.prime()**s).generalised_log() + [s]

    def subgroup_gens(self, level):
        r"""
        Return a list of generators for the kernel of the map `(\ZZ_p / p^c)^\times
        \to (\ZZ_p / p^{c-1})^\times`.

        INPUT:

        - ``c`` (integer) an integer `\ge 1`

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp
            sage: G = SmoothCharacterGroupQp(7, QQ)
            sage: G.subgroup_gens(1)
            [3]
            sage: G.subgroup_gens(2)
            [8]

            sage: G = SmoothCharacterGroupQp(2, QQ)
            sage: G.subgroup_gens(1)
            []
            sage: G.subgroup_gens(2)
            [3]
            sage: G.subgroup_gens(3)
            [5]
        """
        if level == 0:
            raise ValueError
        elif level == 1:
            return self.unit_gens(level)[:-1]
        else:
            return [1 + self.prime()**(level - 1)]

class SmoothCharacterGroupUnramifiedQuadratic(SmoothCharacterGroupGeneric):
    r"""
    The group of smooth characters of `\QQ_{p^2}^\times`, where `\QQ_{p^2}` is
    the unique unramified quadratic extension of `\QQ_p`. We represent
    `\QQ_{p^2}^\times` internally as the completion at the prime above `p` of a
    quadratic number field, defined by (the obvious lift to `\ZZ` of) the
    Conway polynomial modulo `p` of degree 2.

    EXAMPLE::

        sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
        sage: G = SmoothCharacterGroupUnramifiedQuadratic(3, QQ); G
        Group of smooth characters of unramified extension Q_3(s)* (s^2 + 2*s + 2 = 0) with values in Rational Field
        sage: G.unit_gens(3)
        [-11*s, 4, 3*s + 1, 3]
        sage: TestSuite(G).run()
        sage: TestSuite(SmoothCharacterGroupUnramifiedQuadratic(2, QQ)).run()
    """

    def __init__(self, prime, base_ring, names='s'):
        r"""
        Standard initialisation function.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(3, QQ, 'foo'); G
            Group of smooth characters of unramified extension Q_3(foo)* (foo^2 + 2*foo + 2 = 0) with values in Rational Field
            sage: G == loads(dumps(G))
            True
        """
        SmoothCharacterGroupGeneric.__init__(self, prime, base_ring)
        self._name = names

    def change_ring(self, ring):
        r"""
        Return the character group of the same field, but with values in a
        different coefficient ring. This need not have anything to do with the
        original base ring, and in particular there won't generally be a
        coercion map from self to the new group -- use
        :meth:`~SmoothCharacterGroupGeneric.base_extend` if you want this.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, Zmod(3), names='foo').change_ring(CC)
            Group of smooth characters of unramified extension Q_7(foo)* (foo^2 + 6*foo + 3 = 0) with values in Complex Field with 53 bits of precision
        """
        # We want to make sure that both G and the base-extended version have
        # the same values in the cache.
        from copy import copy
        G = SmoothCharacterGroupUnramifiedQuadratic(self.prime(), ring, self._name)
        try:
            G._cache___ideal = copy(self._cache___ideal)
        except AttributeError:
            pass
        return G

    def _field_name(self):
        r"""
        A string representing the unit group of which this is the character group.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, Zmod(3), 'a')._field_name()
            'unramified extension Q_7(a)* (a^2 + 6*a + 3 = 0)'
        """
        return "unramified extension Q_%s(%s)* (%s = 0)" % (self.prime(), self._name, self.number_field().polynomial().change_variable_name(self._name))

    def number_field(self):
        r"""
        Return a number field of which this is the completion at `p`, defined by a polynomial
        whose discriminant is not divisible by `p`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ, 'a').number_field()
            Number Field in a with defining polynomial x^2 + 6*x + 3
            sage: SmoothCharacterGroupUnramifiedQuadratic(5, QQ, 'b').number_field()
            Number Field in b with defining polynomial x^2 + 4*x + 2
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ, 'c').number_field()
            Number Field in c with defining polynomial x^2 + x + 1
        """
        from sage.rings.all import conway_polynomial, PolynomialRing
        fbar = conway_polynomial(self.prime(), 2)
        f = PolynomialRing(QQ,'x')([a.lift() for a in fbar])
        return NumberField(f, self._name)

    @cached_method
    def ideal(self, c):
        r"""
        Return the ideal `p^c` of ``self.number_field()``. The result is
        cached, since we use the methods
        :meth:`~sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal.idealstar` and
        :meth:`~sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal.ideallog` which
        cache a Pari ``bid`` structure.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(7, QQ, 'a'); I = G.ideal(3); I
            Fractional ideal (343)
            sage: I is G.ideal(3)
            True
        """
        return self.number_field().ideal(self.prime()**c)

    @cached_method
    def unit_gens(self, c):
        r"""
        A list of generators `x_1, \dots, x_d` of the abelian group `F^\times /
        (1 + \mathfrak{p}^c)^\times`, where `c` is the given level, satisfying
        no relations other than `x_i^{n_i} = 1` for each `i` (where the
        integers `n_i` are returned by :meth:`exponents`). We adopt the
        convention that the final generator `x_d` is a uniformiser (and `n_d =
        0`).

        ALGORITHM: Use Teichmueller lifts.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).unit_gens(0)
            [7]
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).unit_gens(1)
            [s, 7]
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).unit_gens(2)
            [22*s, 8, 7*s + 1, 7]
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).unit_gens(3)
            [169*s + 49, 8, 7*s + 1, 7]

        In the 2-adic case there can be more than 4 generators::

            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).unit_gens(0)
            [2]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).unit_gens(1)
            [s, 2]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).unit_gens(2)
            [s, 2*s + 1, -1, 2]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).unit_gens(3)
            [s, 2*s + 1, 4*s + 1, -1, 2]
        """
        # special cases

        p = self.prime()
        K = self.number_field()
        a = K.gen()

        if c == 0:
            return [K(p)]
        elif c == 1:
            return [a, K(p)]
        elif p == 2:
            if c == 2:
                return [a, 1 + 2*a, K(-1), K(2)]
            else:
                return [a, 1 + 2*a, 1 + 4*a, K(-1), K(2)]

        # general case

        b = a
        I = self.ideal(c)

        while b**(p**2 - 1) - 1 not in I:
            b = I.reduce(b**(self.prime()**2))
        return [b, K(1 + p), 1 + a*p, K(p)]

    def exponents(self, c):
        r"""
        The orders `n_1, \dots, n_d` of the generators `x_i` of `F^\times / (1
        + \mathfrak{p}^c)^\times` returned by :meth:`unit_gens`.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).exponents(2)
            [48, 7, 7, 0]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).exponents(3)
            [3, 4, 2, 2, 0]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).exponents(2)
            [3, 2, 2, 0]
        """
        p = self.prime()
        if c == 0: return [0]
        elif c == 1: return [p**2 - 1, 0]
        elif p == 2 and c >= 3:
            return [p**2 - 1, p**(c-1), p**(c-2), 2, 0]
        else: return [p**2 - 1, p**(c-1), p**(c-1),0]

    def subgroup_gens(self, level):
        r"""
        A set of elements of `(\mathcal{O}_F / \mathfrak{p}^c)^\times`
        generating the kernel of the reduction map to `(\mathcal{O}_F /
        \mathfrak{p}^{c-1})^\times`.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).subgroup_gens(1)
            [s]
            sage: SmoothCharacterGroupUnramifiedQuadratic(7, QQ).subgroup_gens(2)
            [8, 7*s + 1]
            sage: SmoothCharacterGroupUnramifiedQuadratic(2, QQ).subgroup_gens(2)
            [3, 2*s + 1]
        """
        if level == 0:
            raise ValueError
        elif level == 1:
            return self.unit_gens(level)[:-1]
        else:
            return [1 + self.prime()**(level - 1), 1 + self.prime()**(level - 1) * self.number_field().gen()]

    def quotient_gen(self, level):
        r"""
        Find an element generating the quotient

        .. math::

            \mathcal{O}_F^\times / \ZZ_p^\times \cdot (1 + p^c \mathcal{O}_F),

        where `c` is the given level.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(7,QQ)
            sage: G.quotient_gen(1)
            s
            sage: G.quotient_gen(2)
            -20*s - 21
            sage: G.quotient_gen(3)
            -69*s - 70

        For `p = 2` an error will be raised for level `\ge 3`, as the quotient is not cyclic::

            sage: G = SmoothCharacterGroupUnramifiedQuadratic(2,QQ)
            sage: G.quotient_gen(1)
            s
            sage: G.quotient_gen(2)
            -s + 2
            sage: G.quotient_gen(3)
            Traceback (most recent call last):
            ...
            ValueError: Quotient group not cyclic
        """
        if level == 0:
            raise ValueError( "Quotient group is trivial" )
        elif self.prime() == 2 and level >= 3:
            raise ValueError( "Quotient group not cyclic" )
        elif level == 1:
            return self.unit_gens(level)[0]
        else:
            return self.ideal(level).reduce(self.unit_gens(level)[0] * (1 + self.prime() * self.number_field().gen()))

    def extend_character(self, level, chi, x, check=True):
        r"""
        Return the unique character of `F^\times` which coincides with `\chi`
        on `\QQ_p^\times` and maps the generator `\alpha` returned by
        :meth:`quotient_gen` to `x`.

        INPUT:

        - ``chi``: a smooth character of `\QQ_p`, where `p` is the residue
          characteristic of `F`, with values in the base ring of self (or some
          other ring coercible to it)
        - ``level``: the level of the new character (which should be at least
          the level of ``chi``)
        - ``x``: an element of the base ring of self (or some other ring
          coercible to it).

        A ``ValueError`` will be raised if `x^t \ne \chi(\alpha^t)`, where `t`
        is the smallest integer such that `\alpha^t` is congruent modulo
        `p^{\rm level}` to an element of `\QQ_p`.

        EXAMPLES:

        We extend an unramified character of `\QQ_3^\times` to the unramified
        quadratic extension in various ways.

        ::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupQp, SmoothCharacterGroupUnramifiedQuadratic
            sage: chi = SmoothCharacterGroupQp(5, QQ).character(0, [7]); chi
            Character of Q_5*, of level 0, mapping 5 |--> 7
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(5, QQ)
            sage: G.extend_character(1, chi, -1)
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 1, mapping s |--> -1, 5 |--> 7
            sage: G.extend_character(2, chi, -1)
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 1, mapping s |--> -1, 5 |--> 7
            sage: G.extend_character(3, chi, 1)
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 0, mapping 5 |--> 7
            sage: K.<z> = CyclotomicField(6); G.base_extend(K).extend_character(1, chi, z)
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 1, mapping s |--> z, 5 |--> 7

        We extend the nontrivial quadratic character::

            sage: chi = SmoothCharacterGroupQp(5, QQ).character(1, [-1, 7])
            sage: K.<z> = CyclotomicField(24); G.base_extend(K).extend_character(1, chi, z^6)
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 1, mapping s |--> z^6, 5 |--> 7

        Extensions of higher level::

            sage: K.<z> = CyclotomicField(20); rho = G.base_extend(K).extend_character(2, chi, z); rho
            Character of unramified extension Q_5(s)* (s^2 + 4*s + 2 = 0), of level 2, mapping 11*s - 10 |--> z^5, 6 |--> 1, 5*s + 1 |--> -z^6, 5 |--> 7
            sage: rho(3)
            -1

        Examples where it doesn't work::

            sage: G.extend_character(1, chi, 1)
            Traceback (most recent call last):
            ...
            ValueError: Value at s must satisfy x^6 = chi(2) = -1, but it does not

            sage: G = SmoothCharacterGroupQp(2, QQ); H = SmoothCharacterGroupUnramifiedQuadratic(2, QQ)
            sage: chi = G.character(3, [1, -1, 7])
            sage: H.extend_character(2, chi, -1)
            Traceback (most recent call last):
            ...
            ValueError: Level of extended character cannot be smaller than level of character of Qp
        """
        chi = chi.base_extend(self.base_ring())
        if chi.level() > level:
            raise ValueError, "Level of extended character cannot be smaller than level of character of Qp"

        # check it makes sense
        e = (self.prime() + 1) * (self.prime()**(level - 1))
        v = self.ideal(level).reduce(self.quotient_gen(level) ** e)

        v = QQ(v)
        if x**e != chi(v):
            raise ValueError( "Value at %s must satisfy x^%s = chi(%s) = %s, but it does not" % (self.quotient_gen(level), e, v, chi(v)) )

        # now do the calculation
        values_on_standard_gens = []
        other_gens = [self.quotient_gen(level)] + [ZZ(z) for z in Zmod(self.prime()**level).unit_gens()]
        values_on_other_gens = [x] + [chi(u) for u in other_gens[1:]]
        for s in self.unit_gens(level)[:-1]:
            t = self.ideal(level).ideallog(s, other_gens)
            values_on_standard_gens.append( prod([values_on_other_gens[i] ** t[i] for i in xrange(len(t))]) )
        values_on_standard_gens.append(chi(self.prime()))
        chiE = self.character(level, values_on_standard_gens)

        # check it makes sense (optional but on by default)
        if check:
            assert chiE(self.quotient_gen(level)) == x
            assert chiE.restrict_to_Qp() == chi

        return chiE

    def discrete_log(self, level, x):
        r"""
        Express the class of `x` in `F^\times / (1 + \mathfrak{p}^c)^\times` in
        terms of the generators returned by ``self.unit_gens(level)``.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupUnramifiedQuadratic
            sage: G = SmoothCharacterGroupUnramifiedQuadratic(2, QQ)
            sage: G.discrete_log(0, 12)
            [2]
            sage: G.discrete_log(1, 12)
            [0, 2]
            sage: v = G.discrete_log(5, 12); v
            [0, 2, 0, 1, 2]
            sage: g = G.unit_gens(5); prod([g[i]**v[i] for i in [0..4]])/12 - 1 in G.ideal(5)
            True
            sage: G.discrete_log(3,G.number_field()([1,1]))
            [2, 0, 0, 1, 0]
            sage: H = SmoothCharacterGroupUnramifiedQuadratic(5, QQ)
            sage: x = H.number_field()([1,1]); x
            s + 1
            sage: v = H.discrete_log(5, x); v
            [22, 263, 379, 0]
            sage: h = H.unit_gens(5); prod([h[i]**v[i] for i in [0..3]])/x - 1 in H.ideal(5)
            True
        """
        x = self.number_field().coerce(x)
        if x == 0: raise ValueError( "cannot evaluate at zero" )
        n1 = x.valuation(self.number_field().ideal(self.prime()))
        x1 = x / self.prime() ** n1
        if level == 0:
            return [n1]
        else:
            return self.ideal(level).ideallog(x1, self.unit_gens(level)[:-1]) + [n1]


class SmoothCharacterGroupRamifiedQuadratic(SmoothCharacterGroupGeneric):
    r"""
    The group of smooth characters of `K^\times`, where `K` is a ramified
    quadratic extension of `\QQ_p`, and `p \ne 2`.
    """
    def __init__(self, prime, flag, base_ring, names='s'):
        r"""
        Standard initialisation function.

        INPUT:

        - ``prime`` -- a prime integer
        - ``flag`` -- either 0 or 1
        - ``base_ring`` -- a ring
        - ``names`` -- a variable name (default ``s``)

        If ``flag`` is 0, return the group of characters of the multiplicative
        group of the field `\QQ_p(\sqrt{p})`. If ``flag`` is 1, use the
        extension `\QQ_p(\sqrt{dp})`, where `d` is `-1` (if `p = 3 \pmod 4`) or
        the smallest positive quadratic nonresidue mod `p` otherwise.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G1 = SmoothCharacterGroupRamifiedQuadratic(3, 0, QQ); G1
            Group of smooth characters of ramified extension Q_3(s)* (s^2 - 3 = 0) with values in Rational Field
            sage: G2 = SmoothCharacterGroupRamifiedQuadratic(3, 1, QQ); G2
            Group of smooth characters of ramified extension Q_3(s)* (s^2 + 3 = 0) with values in Rational Field
            sage: G3 = SmoothCharacterGroupRamifiedQuadratic(5, 1, QQ); G3
            Group of smooth characters of ramified extension Q_5(s)* (s^2 - 10 = 0) with values in Rational Field

        TESTS:

        .. link

        ::

            sage: TestSuite(G1).run()
            sage: TestSuite(G2).run()
            sage: TestSuite(G3).run()
        """
        if prime == 2: raise NotImplementedError( "Wildly ramified extensions not supported" )
        SmoothCharacterGroupGeneric.__init__(self, prime, base_ring)
        self._name = names
        if flag not in [0, 1]:
            raise ValueError( "Flag must be 0 (for Qp(sqrt(p)) ) or 1 (for the other ramified extension)" )
        self._flag = flag
        if flag == 0:
            self._unif_sqr = self.prime()
        else:
            if self.prime() % 4 == 3:
                self._unif_sqr = -self.prime()
            else:
                self._unif_sqr = ZZ(Zmod(self.prime()).quadratic_nonresidue()) * self.prime()

    def change_ring(self, ring):
        r"""
        Return the character group of the same field, but with values in a
        different coefficient ring. This need not have anything to do with the
        original base ring, and in particular there won't generally be a
        coercion map from self to the new group -- use
        :meth:`~SmoothCharacterGroupGeneric.base_extend` if you want this.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: SmoothCharacterGroupRamifiedQuadratic(7, 1, Zmod(3), names='foo').change_ring(CC)
            Group of smooth characters of ramified extension Q_7(foo)* (foo^2 + 7 = 0) with values in Complex Field with 53 bits of precision
        """
        return SmoothCharacterGroupRamifiedQuadratic(self.prime(), self._flag, ring, self._name)

    def _field_name(self):
        r"""
        A string representing the unit group of which this is the character group.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: SmoothCharacterGroupRamifiedQuadratic(7, 0, Zmod(3), 'a')._field_name()
            'ramified extension Q_7(a)* (a^2 - 7 = 0)'
        """
        return "ramified extension Q_%s(%s)* (%s = 0)" % (self.prime(), self._name, self.number_field().polynomial().change_variable_name(self._name))

    def number_field(self):
        r"""
        Return a number field of which this is the completion at `p`.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: SmoothCharacterGroupRamifiedQuadratic(7, 0, QQ, 'a').number_field()
            Number Field in a with defining polynomial x^2 - 7
            sage: SmoothCharacterGroupRamifiedQuadratic(5, 1, QQ, 'b').number_field()
            Number Field in b with defining polynomial x^2 - 10
            sage: SmoothCharacterGroupRamifiedQuadratic(7, 1, Zmod(6), 'c').number_field()
            Number Field in c with defining polynomial x^2 + 7
        """
        from sage.rings.all import PolynomialRing
        R, x = PolynomialRing(QQ, 'x').objgen()
        f = x**2 - self._unif_sqr
        return NumberField(f, self._name)

    @cached_method
    def ideal(self, c):
        r"""
        Return the ideal `p^c` of ``self.number_field()``. The result is
        cached, since we use the methods
        :meth:`~sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal.idealstar` and
        :meth:`~sage.rings.number_field.number_field_ideal.NumberFieldFractionalIdeal.ideallog` which
        cache a Pari ``bid`` structure.

        EXAMPLES::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G = SmoothCharacterGroupRamifiedQuadratic(5, 1, QQ, 'a'); I = G.ideal(3); I
            Fractional ideal (25, 5*a)
            sage: I is G.ideal(3)
            True
        """
        return self.number_field().ideal([self.prime(), self.number_field().gen()])**c

    def unit_gens(self, c):
        r"""
        A list of generators `x_1, \dots, x_d` of the abelian group `F^\times /
        (1 + \mathfrak{p}^c)^\times`, where `c` is the given level, satisfying
        no relations other than `x_i^{n_i} = 1` for each `i` (where the
        integers `n_i` are returned by :meth:`exponents`). We adopt the
        convention that the final generator `x_d` is a uniformiser.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G = SmoothCharacterGroupRamifiedQuadratic(5, 0, QQ)
            sage: G.unit_gens(0)
            [s]
            sage: G.unit_gens(1)
            [2, s]
            sage: G.unit_gens(8)
            [2, s + 1, s]
        """
        d = ceil(ZZ(c) / 2)
        p = self.prime()
        K,s = self.number_field().objgen()
        zpgens = [K(ZZ(x)) for x in Zmod(p**d).unit_gens()]
        if c == 0:
            return [s]
        if c == 1:
            return zpgens + [s]
        elif p > 3 or self._unif_sqr == 3 or c <= 3:
            return zpgens + [1 + s, s]
        else:
            # Awkward case: K = Q_3(sqrt(-3)). Here the exponential map doesn't
            # converge on 1 + P, and the quotient (O_K*) / (Zp*) isn't
            # topologically cyclic. I don't know an explicit set of good
            # generators here, so we let Pari do the work and put up with the
            # rather arbitrary (nondeterministic?) results.
            return list(self.ideal(c).idealstar(2).gens_values()) + [s]

    def exponents(self, c):
        r"""
        Return the orders of the independent generators of the unit group
        returned by :meth:`~unit_gens`.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G = SmoothCharacterGroupRamifiedQuadratic(5, 0, QQ)
            sage: G.exponents(0)
            (0,)
            sage: G.exponents(1)
            (4, 0)
            sage: G.exponents(8)
            (500, 625, 0)
        """
        c = ZZ(c)
        d = ceil(c / 2)
        p = self.prime()
        if c == 0:
            return tuple([0])
        elif c == 1:
            return tuple([p - 1, 0])
        elif p > 3 or self._unif_sqr == 3 or c <= 3:
            return tuple([p**(d-1)*(p - 1), p**ceil((c - 1)/2), 0])
        else:
            # awkward case, see above
            return self.ideal(c).idealstar(2).gens_orders() + (0,)

    def subgroup_gens(self, level):
        r"""
        A set of elements of `(\mathcal{O}_F / \mathfrak{p}^c)^\times`
        generating the kernel of the reduction map to `(\mathcal{O}_F /
        \mathfrak{p}^{c-1})^\times`.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G = SmoothCharacterGroupRamifiedQuadratic(3, 1, QQ)
            sage: G.subgroup_gens(2)
            [s + 1]
        """
        if level == 0:
            raise ValueError
        elif level == 1:
            return self.unit_gens(level)[:-1]
        else:
            return [1 + self.number_field().gen()**(level - 1)]

    def discrete_log(self, level, x):
        r"""
        Solve the discrete log problem in the unit group.

        EXAMPLE::

            sage: from sage.modular.local_comp.smoothchar import SmoothCharacterGroupRamifiedQuadratic
            sage: G = SmoothCharacterGroupRamifiedQuadratic(3, 1, QQ)
            sage: s = G.number_field().gen()
            sage: G.discrete_log(4, 3 + 2*s)
            [5, 2, 1, 1]
            sage: gs = G.unit_gens(4); gs[0]^5 * gs[1]^2 * gs[2] * gs[3] - (3 + 2*s) in G.ideal(4)
            True
        """
        x = self.number_field().coerce(x)
        if x == 0: raise ValueError, "cannot evaluate at zero"
        n1 = x.valuation(self.ideal(1))
        x1 = x / self.number_field().gen()**n1
        if level == 0:
            return [n1]
        else:
            return self.ideal(level).ideallog(x1, self.unit_gens(level)[:-1]) + [n1]