# 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:

• 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$$.

EXAMPLE:

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)
[-12288000, 54000, 0, 287496, 1728, 16581375, -3375, 8000, -32768, -884736, -884736000, -147197952000, -262537412640768000, 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$$.

EXAMPLE:

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'))
[(-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 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]
[(-3, 5), (-3, 5), (-4, 5), (-4, 5), (-15, 2), (-15, 2), (-15, 1), (-15, 1), (-20, 1), (-20, 1), (-35, 1), (-35, 1), (-40, 1), (-40, 1), (-115, 1), (-115, 1), (-235, 1), (-235, 1)]


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)
[(-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), (-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])
(<type 'sage.rings.integer.Integer'>, <type '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])
set([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: v.keys()
[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: [len(v[h]) for h in v.keys()]
[13, 29, 25, 84, 29, 101, 38, 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)

Returns the Hilbert class polynomial for discriminant $$D$$.

INPUT:

• D (int) – a negative integer congruent to 0 or 1 modulo 4.
• algorithm (string, default None) – if “sage” then use the Sage implementation; if “magma” then call Magma (if available).

OUTPUT:

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

ALGORITHM:

• If algorithm = “sage”: Use complex approximations to the roots.
• If algorithm = “magma”: Call the appropriate Magma function.

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="magma") # optional - magma
x + 262537412640768000

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