ell_egros.py

"""
Construction of elliptic curves with good reduction outside a finite
set of primes

A theorem of Shafarevich states that, over a number field `K`, given
any finite set `S` of primes of `K`, there are (up to isomorphism)
only a finite set of elliptic curves defined over `K` with good
reduction at all primes outside `S`.  An explicit form of the theorem
with an algorithm for finding this finite set was given in "Finding
all elliptic curves with good reduction outside a given set of primes"
by John Cremona and Mark Lingham, Experimental Mathematics 16 No.3
(2007), 303-312.  The method requires computation of the class and
unit groups of `K` as well as all the `S`-integral points on a
collection of auxiliary elliptic curves defined over `K`.

This implementation (April 2009) is only for the case `K=\Q`, where in
many cases the determination of the necessary sets of `S`-integral
points is possible.  The main user-level function is
EllipticCurves_with_good_reduction_outside_S(), defined in
constrictor.py.  Users should note carefully the following points: 

(1) the number of auxiliary curves to be considered is exponential in
the size of `S` (specifically, `2.6**s` where `s=|S|`).  

(2) For some of the auxiliary curves it is impossible at present to
provably find all the `S`-integral points using the current
algorithms, which rely on first finding a basis for their Mordell-Weil
groups using 2-descent.  A warning is output in cases where the set of
points (and hence the final output) is not guaranteed to be complete.
Using the "proof=False" flag suppresses these warnings.

EXAMPLES: We find all elliptic curves with good reduction outside 2,
listing the label of each:

    sage: [e.label() for e in EllipticCurves_with_good_reduction_outside_S([2])]
    ['32a1',
    '32a2',
    '32a3',
    '32a4',
    '64a1',
    '64a2',
    '64a3',
    '64a4',
    '128a1',
    '128a2',
    '128b1',
    '128b2',
    '128c1',
    '128c2',
    '128d1',
    '128d2',
    '256a1',
    '256a2',
    '256b1',
    '256b2',
    '256c1',
    '256c2',
    '256d1',
    '256d2']

Secondly we try the same with `S={11}`; note that warning messages are
printed without proof=False (unless the optional database is
installed: two of the auxiliary curves whose Mordell-Weil bases are
required have conductors 13068 and 52272 so are in the database)::

    sage: [e.label() for e in EllipticCurves_with_good_reduction_outside_S([11], proof=False)]  # long time (13s on sage.math, 2011)
    ['11a1', '11a2', '11a3', '121a1', '121a2', '121b1', '121b2', '121c1', '121c2', '121d1', '121d2', '121d3']


AUTHORS:
   * John Cremona (6 April 2009): initial version (over Q only).
"""

#*****************************************************************************
#   Copyright (C) 2009 John Cremona <[email protected]>
#
#  Distributed under the terms of the GNU General Public License (GPL)
#
#    This code 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.
#
#  The full text of the GPL is available at:
#
#                  http://www.gnu.org/licenses/
#*****************************************************************************

from sage.misc.misc import prod
from sage.misc.all import xmrange
from sage.rings.all import QQ
from constructor import EllipticCurve, EllipticCurve_from_j

def is_possible_j(j,S=[]):
    r"""
    Tests if the rational `j` is a possible `j`-invariant of an
    elliptic curve with good reduction outside `S`.

    .. note::

    The condition used is necessary but not sufficient unless S
    contains both 2 and 3.

    EXAMPLES::
        sage: from sage.schemes.elliptic_curves.ell_egros import is_possible_j
        sage: is_possible_j(0,[])
        False
        sage: is_possible_j(1728,[])
        True
        sage: is_possible_j(-4096/11,[11])
        True
    """
    j = QQ(j)
    return (j.is_zero() and 3 in S) \
        or (j==1728)                \
        or (j.is_S_integral(S)      \
            and j.prime_to_S_part(S).is_nth_power(3) \
            and (j-1728).prime_to_S_part(S).abs().is_square())


def curve_cmp(E1,E2):
    r"""
    Comparison function for elliptic curves over `Q`.

    Order by label if in the database, else first by conductor, then
    by c_invariants.
    """
    t = cmp(E1.conductor(),E2.conductor())
    if t:
        return t

    # Now they have the same conductor
    try:
        from sage.databases.cremona import parse_cremona_label, class_to_int
        k1 = parse_cremona_label(E1.label())
        k2 = parse_cremona_label(E2.label())        
        t = cmp(class_to_int(k1[1]),class_to_int(k2[1]))
        if t:
            return t
        return cmp(k1[2],k2[2])
    except RuntimeError: # if not in database, label() will fail
        pass

    return cmp(E1.ainvs(),E2.ainvs())

def egros_from_j_1728(S=[]): 
    r"""
    Given a list of primes S, returns a list of elliptic curves over Q
    with j-invariant 1728 and good reduction outside S, by checking
    all relevant quartic twists.

    INPUT:
               
        -  S - list of primes (default: empty list).

    .. note::

        Primality of elements of S is not checked, and the output
        is undefined if S is not a list or contains non-primes.

    OUTPUT:

        A sorted list of all elliptic curves defined over `Q` with
        `j`-invariant equal to `1728` and with good reduction at
        all primes outside the list ``S``.

    EXAMPLES::

        sage: from sage.schemes.elliptic_curves.ell_egros import egros_from_j_1728
        sage: egros_from_j_1728([])
        []
        sage: egros_from_j_1728([3])
        []
        sage: [e.cremona_label() for e in egros_from_j_1728([2])]
        ['32a1', '32a2', '64a1', '64a4', '256b1', '256b2', '256c1', '256c2']

    """
    Elist=[]    
    no2 = not 2 in S
    for ei in xmrange([2] + [4]*len(S)):  
        u = prod([p**e for p,e in zip([-1]+S,ei)],QQ(1))
        if no2:
            u*=4 ## make sure 12|val(D,2)
        Eu = EllipticCurve([0,0,0,u,0]).minimal_model()
        if Eu.has_good_reduction_outside_S(S):
            Elist += [Eu]
    Elist.sort(cmp=curve_cmp)
    return Elist

def egros_from_j_0(S=[]):
    r"""
    Given a list of primes S, returns a list of elliptic curves over Q
    with j-invariant 0 and good reduction outside S, by checking all
    relevant sextic twists.

    INPUT:
               
        -  S - list of primes (default: empty list).

    .. note::

        Primality of elements of S is not checked, and the output
        is undefined if S is not a list or contains non-primes.

    OUTPUT:

        A sorted list of all elliptic curves defined over `Q` with
        `j`-invariant equal to `0` and with good reduction at
        all primes outside the list ``S``.
               
    EXAMPLES::

        sage: from sage.schemes.elliptic_curves.ell_egros import egros_from_j_0
        sage: egros_from_j_0([])
        []
        sage: egros_from_j_0([2])
        []
        sage: [e.label() for e in egros_from_j_0([3])]
        ['27a1', '27a3', '243a1', '243a2', '243b1', '243b2']
        sage: len(egros_from_j_0([2,3,5]))
        432
    """
    Elist=[]    
    if not 3 in S:
        return Elist
    no2 = not 2 in S
    for ei in xmrange([2] + [6]*len(S)):  
        u = prod([p**e for p,e in zip([-1]+S,ei)],QQ(1))
        if no2:
            u*=16 ## make sure 12|val(D,2)
        Eu = EllipticCurve([0,0,0,0,u]).minimal_model()
        if Eu.has_good_reduction_outside_S(S):
            Elist += [Eu]
    Elist.sort(cmp=curve_cmp)
    return Elist

def egros_from_j(j,S=[]): 
    r"""
    Given a rational j and a list of primes S, returns a list of
    elliptic curves over Q with j-invariant j and good reduction
    outside S, by checking all relevant quadratic twists.

    INPUT:
               
        -  j - a rational number.

        -  S - list of primes (default: empty list).

    .. note::

        Primality of elements of S is not checked, and the output
        is undefined if S is not a list or contains non-primes.

    OUTPUT:

        A sorted list of all elliptic curves defined over `Q` with
        `j`-invariant equal to `j` and with good reduction at
        all primes outside the list ``S``.
               
    EXAMPLES::

        sage: from sage.schemes.elliptic_curves.ell_egros import egros_from_j
        sage: [e.label() for e in egros_from_j(0,[3])]
        ['27a1', '27a3', '243a1', '243a2', '243b1', '243b2']
        sage: [e.label() for e in egros_from_j(1728,[2])]
        ['32a1', '32a2', '64a1', '64a4', '256b1', '256b2', '256c1', '256c2']
        sage: elist=egros_from_j(-4096/11,[11])
        sage: [e.label() for e in elist]
        ['11a3', '121d1']

    """
    if j == 1728:
        return egros_from_j_1728(S)

    if j == 0:
        return egros_from_j_0(S)

    # Now j != 0, 1728

    E = EllipticCurve_from_j(j)
    Elist=[]

    for ei in xmrange([2]*(1+len(S))):  
        u = prod([p**e for p,e in zip(reversed([-1]+S),ei)],QQ(1))
        Eu = E.quadratic_twist(u).minimal_model()
        if Eu.has_good_reduction_outside_S(S):
            Elist += [Eu]

    Elist.sort(cmp=curve_cmp)
    return Elist

def egros_from_jlist(jlist,S=[]): 
    r"""
    Given a list of rational j and a list of primes S, returns a list
    of elliptic curves over Q with j-invariant in the list and good
    reduction outside S.

    INPUT:
               
        -  j - list of rational numbers.

        -  S - list of primes (default: empty list).

    .. note::

        Primality of elements of S is not checked, and the output
        is undefined if S is not a list or contains non-primes.

    OUTPUT:

        A sorted list of all elliptic curves defined over `Q` with
        `j`-invariant in the list ``jlist`` and with good reduction at
        all primes outside the list ``S``.
               
    EXAMPLES::

        sage: from sage.schemes.elliptic_curves.ell_egros import egros_get_j, egros_from_jlist
        sage: jlist=egros_get_j([3])
        sage: elist=egros_from_jlist(jlist,[3])
        sage: [e.label() for e in elist]
        ['27a1', '27a2', '27a3', '27a4', '243a1', '243a2', '243b1', '243b2']
        sage: [e.ainvs() for e in elist]
        [(0, 0, 1, 0, -7),
        (0, 0, 1, -270, -1708),
        (0, 0, 1, 0, 0),
        (0, 0, 1, -30, 63),
        (0, 0, 1, 0, -1),
        (0, 0, 1, 0, 20),
        (0, 0, 1, 0, 2),
        (0, 0, 1, 0, -61)]
    """
    elist = sum([egros_from_j(j,S) for j in jlist],[])
    elist.sort(cmp=curve_cmp)
    return elist

def egros_get_j(S=[], proof=None, verbose=False):
    r"""
    Returns a list of rational `j` such that all elliptic curves
    defined over `Q` with good reduction outside `S` have
    `j`-invariant in the list, sorted by height.

    INPUT:
               
        -  ``S`` - list of primes (default: empty list).

        - ``proof`` - True/False (default True): the MW basis for
          auxiliary curves will be computed with this proof flag.

        - ``verbose`` - True/False (default False): if True, some
          details of the computation will be output.

    .. note::

        Proof flag: The algorithm used requires determining all
        S-integral points on several auxiliary curves, which in turn
        requires the computation of their generators.  This is not
        always possible (even in theory) using current knowledge.

        The value of this flag is passed to the function which
        computes generators of various auxiliary elliptic curves, in
        order to find their S-integral points.  Set to False if the
        default (True) causes warning messages, but note that you can
        then not rely on the set of invariants returned being
        complete.

    EXAMPLES::

        sage: from sage.schemes.elliptic_curves.ell_egros import egros_get_j
        sage: egros_get_j([])
        [1728]
        sage: egros_get_j([2])
        [128, 432, -864, 1728, 3375/2, -3456, 6912, 8000, 10976, -35937/4, 287496, -784446336, -189613868625/128]
        sage: egros_get_j([3])
        [0, -576, 1536, 1728, -5184, -13824, 21952/9, -41472, 140608/3, -12288000]
        sage: jlist=egros_get_j([2,3]); len(jlist) # long time (30s)
        83

    """
    if not all([p.is_prime() for p in S]):
        raise ValueError, "Elements of S must be prime."

        if proof is None:
            from sage.structure.proof.proof import get_flag
            proof = get_flag(proof, "elliptic_curve")
        else:
            proof = bool(proof)

    if verbose:
        import sys  # so we can flush stdout for debugging

    SS = [-1] + S

    jlist=[]
    wcount=0
    nw = 6**len(S) * 2

    if verbose:
        print "Finding possible j invariants for S = ",S
        print "Using ", nw, " twists of base curve"
        sys.stdout.flush()

    for ei in xmrange([6]*len(S) + [2]):  
        w = prod([p**e for p,e in zip(reversed(SS),ei)],QQ(1))
        wcount+=1
        if verbose:
            print "Curve #",wcount, "/",nw,":";
            print "w = ",w,"=",w.factor()
            sys.stdout.flush()
        a6 = -1728*w
        d2 = 0
        d3 = 0
        u0 = (2**d2)*(3**d3)
        E = EllipticCurve([0,0,0,0,a6])
        # This curve may not be minimal at 2 or 3, but the
        # S-integral_points function requires minimality at primes in
        # S, so we find a new model which is p-minimal at both 2 and 3
        # if they are in S.  Note that the isomorphism between models
        # will preserve S-integrality of points.
        E2 = E.local_minimal_model(2) if 2 in S else E
        E23 = E2.local_minimal_model(3) if 3 in S else E2
        urst = E23.isomorphism_to(E)    
        
        try:
            pts = E23.S_integral_points(S,proof=proof)
        except RuntimeError:
            pts=[]
            print "Failed to find S-integral points on ",E23.ainvs()
            if proof:
                if verbose:
                    print "--trying again with proof=False"
                    sys.stdout.flush()
                pts = E23.S_integral_points(S,proof=False)
                if verbose:
                    print "--done"
        if verbose:
            print len(pts), " S-integral points: ",pts
            sys.stdout.flush()
        for P in pts:
            P = urst(P)
            x = P[0]
            y = P[1]
            j = x**3 /w
            assert j-1728 == y**2 /w
            if is_possible_j(j,S):
                if not j in jlist:
                    if verbose:
                        print "Adding possible j = ",j
                        sys.stdout.flush()
                    jlist += [j]
            else:
                if True: #verbose:
                    print "Discarding illegal j = ",j
                    sys.stdout.flush()
    height_cmp = lambda j1,j2: cmp(j1.height(),j2.height())
    jlist.sort(cmp=height_cmp)
    return jlist