Activate

Complex multiplication for elliptic curves

This module implements the functions

• hilbert_class_polynomial
• cm_j_invariants
• cm_orders
• discriminants_with_bounded_class_number
• cm_j_invariants_and_orders
• largest_fundamental_disc_with_class_number

AUTHORS:

• Robert Bradshaw
• John Cremona
• William Stein

sage.schemes.elliptic_curves.cm.cm_j_invariants(K, proof=None)

Return a list of all CM $j$-invariants in the field $K$.

INPUT:

• K – a number field
• proof – (default: proof.number_field())

OUTPUT:

(list) – A list of CM $j$-invariants in the field $K$.

EXAMPLES:

sage: cm_j_invariants(QQ)
[-262537412640768000, -147197952000, -884736000, -12288000, -884736, -32768, -3375, 0, 1728, 8000, 54000, 287496, 16581375]

Over imaginary quadratic fields there are no more than over $QQ$:

sage: cm_j_invariants(QuadraticField(-1, 'i'))
[-262537412640768000, -147197952000, -884736000, -12288000, -884736, -32768, -3375, 0, 1728, 8000, 54000, 287496, 16581375]

Over real quadratic fields there may be more, for example:

sage: len(cm_j_invariants(QuadraticField(5, 'a')))
31

Over number fields K of many higher degrees this also works:

sage: K.<a> = NumberField(x^3 - 2)
sage: cm_j_invariants(K)
[-262537412640768000, -147197952000, -884736000,
 -884736, -32768, 8000, -3375, 16581375, 1728, 287496, 0,
 54000, -12288000,
 31710790944000*a^2 + 39953093016000*a + 50337742902000]
sage: K.<a> = NumberField(x^4 - 2)
sage: len(cm_j_invariants(K))
23

sage.schemes.elliptic_curves.cm.cm_j_invariants_and_orders(K, proof=None)

Return a list of all CM $j$-invariants in the field $K$, together with the associated orders.

INPUT:

• K – a number field
• proof – (default: proof.number_field())

OUTPUT:

(list) A list of 3-tuples $(D,f,j)$ where $j$ is a CM $j$-invariant in $K$ with quadratic fundamental discriminant $D$ and conductor $f$.

EXAMPLES:

sage: cm_j_invariants_and_orders(QQ)
[(-3, 3, -12288000), (-3, 2, 54000), (-3, 1, 0), (-4, 2, 287496), (-4, 1, 1728), (-7, 2, 16581375), (-7, 1, -3375), (-8, 1, 8000), (-11, 1, -32768), (-19, 1, -884736), (-43, 1, -884736000), (-67, 1, -147197952000), (-163, 1, -262537412640768000)]

Over an imaginary quadratic field there are no more than over $QQ$:

sage: cm_j_invariants_and_orders(QuadraticField(-1, 'i'))
[(-163, 1, -262537412640768000), (-67, 1, -147197952000),
 (-43, 1, -884736000), (-19, 1, -884736), (-11, 1, -32768),
 (-8, 1, 8000), (-7, 1, -3375), (-7, 2, 16581375), (-4, 1, 1728),
 (-4, 2, 287496), (-3, 1, 0), (-3, 2, 54000), (-3, 3, -12288000)]

Over real quadratic fields there may be more:

sage: v = cm_j_invariants_and_orders(QuadraticField(5,'a')); len(v)
31
sage: [(D, f) for D, f, j in v if j not in QQ]
[(-235, 1), (-235, 1), (-115, 1), (-115, 1), (-40, 1), (-40, 1),
 (-35, 1), (-35, 1), (-20, 1), (-20, 1), (-15, 1), (-15, 1), (-15, 2),
 (-15, 2), (-4, 5), (-4, 5), (-3, 5), (-3, 5)]

Over number fields K of many higher degrees this also works:

sage: K.<a> = NumberField(x^3 - 2)
sage: cm_j_invariants_and_orders(K)
[(-163, 1, -262537412640768000), (-67, 1, -147197952000),
 (-43, 1, -884736000), (-19, 1, -884736), (-11, 1, -32768),
 (-8, 1, 8000), (-7, 1, -3375), (-7, 2, 16581375), (-4, 1, 1728),
 (-4, 2, 287496), (-3, 1, 0), (-3, 2, 54000), (-3, 3, -12288000),
 (-3, 6, 31710790944000*a^2 + 39953093016000*a + 50337742902000)]

sage.schemes.elliptic_curves.cm.cm_orders(h, proof=None)

Return a list of all pairs $(D,f)$ where there is a CM order of discriminant $D f^2$ with class number h, with $D$ a fundamental discriminant.

INPUT:

• $h$ – positive integer
• proof – (default: proof.number_field())

OUTPUT:

• list of 2-tuples $(D,f)$

EXAMPLES:

sage: cm_orders(0)
[]
sage: v = cm_orders(1); v
[(-3, 3), (-3, 2), (-3, 1), (-4, 2), (-4, 1), (-7, 2), (-7, 1), (-8, 1), (-11, 1), (-19, 1), (-43, 1), (-67, 1), (-163, 1)]
sage: type(v[0][0]), type(v[0][1])
(<... 'sage.rings.integer.Integer'>, <... 'sage.rings.integer.Integer'>)
sage: v = cm_orders(2); v
 [(-3, 7), (-3, 5), (-3, 4), (-4, 5), (-4, 4), (-4, 3), (-7, 4), (-8, 3), (-8, 2), (-11, 3), (-15, 2), (-15, 1), (-20, 1), (-24, 1), (-35, 1), (-40, 1), (-51, 1), (-52, 1), (-88, 1), (-91, 1), (-115, 1), (-123, 1), (-148, 1), (-187, 1), (-232, 1), (-235, 1), (-267, 1), (-403, 1), (-427, 1)]
sage: len(v)
29
sage: set([hilbert_class_polynomial(D*f^2).degree() for D,f in v])
{2}

Any degree up to 100 is implemented, but may be prohibitively slow:

sage: cm_orders(3)
[(-3, 9), (-3, 6), (-11, 2), (-19, 2), (-23, 2), (-23, 1), (-31, 2), (-31, 1), (-43, 2), (-59, 1), (-67, 2), (-83, 1), (-107, 1), (-139, 1), (-163, 2), (-211, 1), (-283, 1), (-307, 1), (-331, 1), (-379, 1), (-499, 1), (-547, 1), (-643, 1), (-883, 1), (-907, 1)]
sage: len(cm_orders(4))
84

sage.schemes.elliptic_curves.cm.discriminants_with_bounded_class_number(hmax, B=None, proof=None)

Return dictionary with keys class numbers $h\le hmax$ and values the list of all pairs $(D, f)$, with $D<0$ a fundamental discriminant such that $Df^2$ has class number $h$. If the optional bound $B$ is given, return only those pairs with fundamental $|D| \le B$, though $f$ can still be arbitrarily large.

INPUT:

• hmax – integer
• $B$ – integer or None; if None returns all pairs
• proof – this code calls the PARI function qfbclassno, so it could give wrong answers when proof``==``False. The default is whatever proof.number_field() is. If proof==False and $B$ is None, at least the number of discriminants is correct, since it is double checked with Watkins’s table.

OUTPUT:

• dictionary

In case $B$ is not given, we use Mark Watkins’s: “Class numbers of imaginary quadratic fields” to compute a $B$ that captures all $h$ up to $hmax$ (only available for $hmax\le100$).

EXAMPLES:

sage: v = sage.schemes.elliptic_curves.cm.discriminants_with_bounded_class_number(3)
sage: sorted(v)
[1, 2, 3]
sage: v[1]
[(-3, 3), (-3, 2), (-3, 1), (-4, 2), (-4, 1), (-7, 2), (-7, 1), (-8, 1), (-11, 1), (-19, 1), (-43, 1), (-67, 1), (-163, 1)]
sage: v[2]
[(-3, 7), (-3, 5), (-3, 4), (-4, 5), (-4, 4), (-4, 3), (-7, 4), (-8, 3), (-8, 2), (-11, 3), (-15, 2), (-15, 1), (-20, 1), (-24, 1), (-35, 1), (-40, 1), (-51, 1), (-52, 1), (-88, 1), (-91, 1), (-115, 1), (-123, 1), (-148, 1), (-187, 1), (-232, 1), (-235, 1), (-267, 1), (-403, 1), (-427, 1)]
sage: v[3]
[(-3, 9), (-3, 6), (-11, 2), (-19, 2), (-23, 2), (-23, 1), (-31, 2), (-31, 1), (-43, 2), (-59, 1), (-67, 2), (-83, 1), (-107, 1), (-139, 1), (-163, 2), (-211, 1), (-283, 1), (-307, 1), (-331, 1), (-379, 1), (-499, 1), (-547, 1), (-643, 1), (-883, 1), (-907, 1)]
sage: v = sage.schemes.elliptic_curves.cm.discriminants_with_bounded_class_number(8, proof=False)
sage: sorted(len(v[h]) for h in v)
[13, 25, 29, 29, 38, 84, 101, 208]

Find all class numbers for discriminant up to 50:

sage: sage.schemes.elliptic_curves.cm.discriminants_with_bounded_class_number(hmax=5, B=50)
{1: [(-3, 3), (-3, 2), (-3, 1), (-4, 2), (-4, 1), (-7, 2), (-7, 1), (-8, 1), (-11, 1), (-19, 1), (-43, 1)], 2: [(-3, 7), (-3, 5), (-3, 4), (-4, 5), (-4, 4), (-4, 3), (-7, 4), (-8, 3), (-8, 2), (-11, 3), (-15, 2), (-15, 1), (-20, 1), (-24, 1), (-35, 1), (-40, 1)], 3: [(-3, 9), (-3, 6), (-11, 2), (-19, 2), (-23, 2), (-23, 1), (-31, 2), (-31, 1), (-43, 2)], 4: [(-3, 13), (-3, 11), (-3, 8), (-4, 10), (-4, 8), (-4, 7), (-4, 6), (-7, 8), (-7, 6), (-7, 3), (-8, 6), (-8, 4), (-11, 5), (-15, 4), (-19, 5), (-19, 3), (-20, 3), (-20, 2), (-24, 2), (-35, 3), (-39, 2), (-39, 1), (-40, 2), (-43, 3)], 5: [(-47, 2), (-47, 1)]}

sage.schemes.elliptic_curves.cm.hilbert_class_polynomial(D, algorithm=None)

Return the Hilbert class polynomial for discriminant $D$.

INPUT:

• D (int) – a negative integer congruent to 0 or 1 modulo 4.
• algorithm (string, default None).

OUTPUT:

(integer polynomial) The Hilbert class polynomial for the discriminant $D$.

ALGORITHM:

• If algorithm = “arb” (default): Use Arb’s implementation which uses complex interval arithmetic.
• If algorithm = “sage”: Use complex approximations to the roots.
• If algorithm = “magma”: Call the appropriate Magma function (if available).

AUTHORS:

• Sage implementation originally by Eduardo Ocampo Alvarez and AndreyTimofeev
• Sage implementation corrected by John Cremona (using corrected precision bounds from Andreas Enge)
• Magma implementation by David Kohel

EXAMPLES:

sage: hilbert_class_polynomial(-4)
x - 1728
sage: hilbert_class_polynomial(-7)
x + 3375
sage: hilbert_class_polynomial(-23)
x^3 + 3491750*x^2 - 5151296875*x + 12771880859375
sage: hilbert_class_polynomial(-37*4)
x^2 - 39660183801072000*x - 7898242515936467904000000
sage: hilbert_class_polynomial(-37*4, algorithm="magma") # optional - magma
x^2 - 39660183801072000*x - 7898242515936467904000000
sage: hilbert_class_polynomial(-163)
x + 262537412640768000
sage: hilbert_class_polynomial(-163, algorithm="sage")
x + 262537412640768000
sage: hilbert_class_polynomial(-163, algorithm="magma") # optional - magma
x + 262537412640768000

sage.schemes.elliptic_curves.cm.is_cm_j_invariant(j, method='new')

Return whether or not this is a CM $j$-invariant.

INPUT:

• j – an element of a number field $K$

OUTPUT:

A pair (bool, (d,f)) which is either (False, None) if $j$ is not a CM j-invariant or (True, (d,f)) if $j$ is the $j$-invariant of the imaginary quadratic order of discriminant $D=df^2$ where $d$ is the associated fundamental discriminant and $f$ the index.

Note

The current implementation makes use of the classification of all orders of class number up to 100, and hence will raise an error if $j$ is an algebraic integer of degree greater than this. It would be possible to implement a more general version, using the fact that $d$ must be supported on the primes dividing the discriminant of the minimal polynomial of $j$.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.cm import is_cm_j_invariant
sage: is_cm_j_invariant(0)
(True, (-3, 1))
sage: is_cm_j_invariant(8000)
(True, (-8, 1))

sage: K.<a> = QuadraticField(5)
sage: is_cm_j_invariant(282880*a + 632000)
(True, (-20, 1))
sage: K.<a> = NumberField(x^3 - 2)
sage: is_cm_j_invariant(31710790944000*a^2 + 39953093016000*a + 50337742902000)
(True, (-3, 6))

sage.schemes.elliptic_curves.cm.largest_fundamental_disc_with_class_number(h)

Return largest absolute value of any fundamental discriminant with class number $h$, and the number of fundamental discriminants with that class number. This is known for $h$ up to 100, by work of Mark Watkins.

INPUT:

• $h$ – integer

EXAMPLES:

sage: sage.schemes.elliptic_curves.cm.largest_fundamental_disc_with_class_number(0)
(0, 0)
sage: sage.schemes.elliptic_curves.cm.largest_fundamental_disc_with_class_number(1)
(163, 9)
sage: sage.schemes.elliptic_curves.cm.largest_fundamental_disc_with_class_number(2)
(427, 18)
sage: sage.schemes.elliptic_curves.cm.largest_fundamental_disc_with_class_number(10)
(13843, 87)
sage: sage.schemes.elliptic_curves.cm.largest_fundamental_disc_with_class_number(100)
(1856563, 1736)
sage: sage.schemes.elliptic_curves.cm.largest_fundamental_disc_with_class_number(101)
Traceback (most recent call last):
...
NotImplementedError: largest discriminant not known for class number 101