Module of Supersingular Points

The module of divisors on the modular curve \(X_0(N)\) over \(F_p\) supported at supersingular points.

AUTHORS:

  • William Stein

  • David Kohel

  • Iftikhar Burhanuddin

EXAMPLES:

sage: x = SupersingularModule(389)
sage: m = x.T(2).matrix()
sage: a = m.change_ring(GF(97))
sage: D = a.decomposition()
sage: D[:3]
[
(Vector space of degree 33 and dimension 1 over Finite Field of size 97
Basis matrix:
[ 0  0  0  1 96 96  1  0 95  1  1  1  1 95  2 96  0  0 96  0 96  0 96  2 96 96  0  1  0  2  1 95  0], True),
(Vector space of degree 33 and dimension 1 over Finite Field of size 97
Basis matrix:
[ 0  1 96 16 75 22 81  0  0 17 17 80 80  0  0 74 40  1 16 57 23 96 81  0 74 23  0 24  0  0 73  0  0], True),
(Vector space of degree 33 and dimension 1 over Finite Field of size 97
Basis matrix:
[ 0  1 96 90 90  7  7  0  0 91  6  6 91  0  0 91  0 13  7  0  6 84 90  0  6 91  0 90  0  0  7  0  0], True)
]
sage: len(D)
9

We compute a Hecke operator on a space of huge dimension!:

sage: X = SupersingularModule(next_prime(10000))
sage: t = X.T(2).matrix()            # long time (21s on sage.math, 2011)
sage: t.nrows()                      # long time
835
sage.modular.ssmod.ssmod.Phi2_quad(J3, ssJ1, ssJ2)

Return a certain quadratic polynomial over a finite field in indeterminate J3.

The roots of the polynomial along with ssJ1 are the neighboring/2-isogenous supersingular j-invariants of ssJ2.

INPUT:

  • J3 – indeterminate of a univariate polynomial ring defined over a finite field with p^2 elements where p is a prime number

  • ssJ2, ssJ2 – supersingular j-invariants over the finite field

OUTPUT:

  • polynomial – defined over the finite field

EXAMPLES:

The following code snippet produces a factor of the modular polynomial \(\Phi_{2}(x,j_{in})\), where \(j_{in}\) is a supersingular j-invariant defined over the finite field with \(37^2\) elements:

sage: F = GF(37^2, 'a')
sage: X = PolynomialRing(F, 'x').gen()
sage: j_in = supersingular_j(F)
sage: poly = sage.modular.ssmod.ssmod.Phi_polys(2,X,j_in)
sage: poly.roots()
[(8, 1), (27*a + 23, 1), (10*a + 20, 1)]
sage: sage.modular.ssmod.ssmod.Phi2_quad(X, F(8), j_in)
x^2 + 31*x + 31

Note

Given a root (j1,j2) to the polynomial \(Phi_2(J1,J2)\), the pairs (j2,j3) not equal to (j2,j1) which solve \(Phi_2(j2,j3)\) are roots of the quadratic equation:

J3^2 + (-j2^2 + 1488*j2 + (j1 - 162000))*J3 + (-j1 + 1488)*j2^2 + (1488*j1 + 40773375)*j2 + j1^2 - 162000*j1 + 8748000000

This will be of use to extend the 2-isogeny graph, once the initial three roots are determined for \(Phi_2(J1,J2)\).

AUTHORS:

sage.modular.ssmod.ssmod.Phi_polys(L, x, j)

Return a certain polynomial of degree \(L+1\) in the indeterminate x over a finite field.

The roots of the modular polynomial \(\Phi(L, x, j)\) are the \(L\)-isogenous supersingular j-invariants of j.

INPUT:

  • L – integer

  • x – indeterminate of a univariate polynomial ring defined over a finite field with p^2 elements, where p is a prime number

  • j – supersingular j-invariant over the finite field

OUTPUT:

  • polynomial – defined over the finite field

EXAMPLES:

The following code snippet produces the modular polynomial \(\Phi_{L}(x,j_{in})\), where \(j_{in}\) is a supersingular j-invariant defined over the finite field with \(7^2\) elements:

sage: F = GF(7^2, 'a')
sage: X = PolynomialRing(F, 'x').gen()
sage: j_in = supersingular_j(F)
sage: sage.modular.ssmod.ssmod.Phi_polys(2,X,j_in)
x^3 + 3*x^2 + 3*x + 1
sage: sage.modular.ssmod.ssmod.Phi_polys(3,X,j_in)
x^4 + 4*x^3 + 6*x^2 + 4*x + 1
sage: sage.modular.ssmod.ssmod.Phi_polys(5,X,j_in)
x^6 + 6*x^5 + x^4 + 6*x^3 + x^2 + 6*x + 1
sage: sage.modular.ssmod.ssmod.Phi_polys(7,X,j_in)
x^8 + x^7 + x + 1
sage: sage.modular.ssmod.ssmod.Phi_polys(11,X,j_in)
x^12 + 5*x^11 + 3*x^10 + 3*x^9 + 5*x^8 + x^7 + x^5 + 5*x^4 + 3*x^3 + 3*x^2 + 5*x + 1
sage: sage.modular.ssmod.ssmod.Phi_polys(13,X,j_in)
x^14 + 2*x^7 + 1
class sage.modular.ssmod.ssmod.SupersingularModule(prime=2, level=1, base_ring=Integer Ring)

Bases: sage.modular.hecke.module.HeckeModule_free_module

The module of supersingular points in a given characteristic, with given level structure.

The characteristic must not divide the level.

Note

Currently, only level 1 is implemented.

EXAMPLES:

sage: S = SupersingularModule(17)
sage: S
Module of supersingular points on X_0(1)/F_17 over Integer Ring
sage: S = SupersingularModule(16)
Traceback (most recent call last):
...
ValueError: the argument prime must be a prime number
sage: S = SupersingularModule(prime=17, level=34)
Traceback (most recent call last):
...
ValueError: the argument level must be coprime to the argument prime
sage: S = SupersingularModule(prime=17, level=5)
Traceback (most recent call last):
...
NotImplementedError: supersingular modules of level > 1 not yet implemented
dimension()

Return the dimension of the space of modular forms of weight 2 and level equal to the level associated to self.

INPUT:

  • self – SupersingularModule object

OUTPUT:

  • integer – dimension, nonnegative

EXAMPLES:

sage: S = SupersingularModule(7)
sage: S.dimension()
1

sage: S = SupersingularModule(15073)
sage: S.dimension()
1256

sage: S = SupersingularModule(83401)
sage: S.dimension()
6950

Note

The case of level > 1 has not yet been implemented.

AUTHORS:

free_module()

EXAMPLES:

sage: X = SupersingularModule(37)
sage: X.free_module()
Ambient free module of rank 3 over the principal ideal domain Integer Ring

This illustrates the fix at trac ticket #4306:

sage: X = SupersingularModule(389)
sage: X.basis()
((1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0),
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1))
hecke_matrix(L)

Return the \(L^{\text{th}}\) Hecke matrix.

INPUT:

  • self – SupersingularModule object

  • L – integer, positive

OUTPUT:

  • matrix – sparse integer matrix

EXAMPLES:

This example computes the action of the Hecke operator \(T_2\) on the module of supersingular points on \(X_0(1)/F_{37}\):

sage: S = SupersingularModule(37)
sage: M = S.hecke_matrix(2)
sage: M
[1 1 1]
[1 0 2]
[1 2 0]

This example computes the action of the Hecke operator \(T_3\) on the module of supersingular points on \(X_0(1)/F_{67}\):

sage: S = SupersingularModule(67)
sage: M = S.hecke_matrix(3)
sage: M
[0 0 0 0 2 2]
[0 0 1 1 1 1]
[0 1 0 2 0 1]
[0 1 2 0 1 0]
[1 1 0 1 0 1]
[1 1 1 0 1 0]

Note

The first list — list_j — returned by the supersingular_points function are the rows and column indexes of the above hecke matrices and its ordering should be kept in mind when interpreting these matrices.

AUTHORS:

level()

This function returns the level associated to self.

INPUT:

  • self – SupersingularModule object

OUTPUT:

  • integer – the level, positive

EXAMPLES:

sage: S = SupersingularModule(15073)
sage: S.level()
1

AUTHORS:

prime()

Return the characteristic of the finite field associated to self.

INPUT:

  • self – SupersingularModule object

OUTPUT:

  • integer – characteristic, positive

EXAMPLES:

sage: S = SupersingularModule(19)
sage: S.prime()
19

AUTHORS:

rank()

Return the dimension of the space of modular forms of weight 2 and level equal to the level associated to self.

INPUT:

  • self – SupersingularModule object

OUTPUT:

  • integer – dimension, nonnegative

EXAMPLES:

sage: S = SupersingularModule(7)
sage: S.dimension()
1

sage: S = SupersingularModule(15073)
sage: S.dimension()
1256

sage: S = SupersingularModule(83401)
sage: S.dimension()
6950

Note

The case of level > 1 has not yet been implemented.

AUTHORS:

supersingular_points()

Compute the supersingular j-invariants over the finite field associated to self.

INPUT:

  • self – SupersingularModule object

OUTPUT:

  • list_j, dict_j – list_j is the list of supersingular

    j-invariants, dict_j is a dictionary with these j-invariants as keys and their indexes as values. The latter is used to speed up j-invariant look-up. The indexes are based on the order of their discovery.

EXAMPLES:

The following examples calculate supersingular j-invariants over finite fields with characteristic 7, 11 and 37:

sage: S = SupersingularModule(7)
sage: S.supersingular_points()
([6], {6: 0})

sage: S = SupersingularModule(11)
sage: S.supersingular_points()[0]
[1, 0]

sage: S = SupersingularModule(37)
sage: S.supersingular_points()[0]
[8, 27*a + 23, 10*a + 20]

AUTHORS:

upper_bound_on_elliptic_factors(p=None, ellmax=2)

Return an upper bound (provably correct) on the number of elliptic curves of conductor equal to the level of this supersingular module.

INPUT:

  • p – (default: 997) prime to work modulo

ALGORITHM: Currently we only use \(T_2\). Function will be extended to use more Hecke operators later.

The prime p is replaced by the smallest prime that does not divide the level.

EXAMPLES:

sage: SupersingularModule(37).upper_bound_on_elliptic_factors()
2

(There are 4 elliptic curves of conductor 37, but only 2 isogeny classes.)

weight()

Return the weight associated to self.

INPUT:

  • self – SupersingularModule object

OUTPUT:

  • integer – weight, positive

EXAMPLES:

sage: S = SupersingularModule(19)
sage: S.weight()
2

AUTHORS:

sage.modular.ssmod.ssmod.dimension_supersingular_module(prime, level=1)

Return the dimension of the Supersingular module, which is equal to the dimension of the space of modular forms of weight \(2\) and conductor equal to prime times level.

INPUT:

  • prime – integer, prime

  • level – integer, positive

OUTPUT:

  • dimension – integer, nonnegative

EXAMPLES:

The code below computes the dimensions of Supersingular modules with level=1 and prime = 7, 15073 and 83401:

sage: dimension_supersingular_module(7)
1

sage: dimension_supersingular_module(15073)
1256

sage: dimension_supersingular_module(83401)
6950

Note

The case of level > 1 has not been implemented yet.

AUTHORS:

sage.modular.ssmod.ssmod.supersingular_D(prime)

Return a fundamental discriminant \(D\) of an imaginary quadratic field, where the given prime does not split.

See Silverman’s Advanced Topics in the Arithmetic of Elliptic Curves, page 184, exercise 2.30(d).

INPUT:

  • prime – integer, prime

OUTPUT:

  • D – integer, negative

EXAMPLES:

These examples return supersingular discriminants for 7, 15073 and 83401:

sage: supersingular_D(7)
-4

sage: supersingular_D(15073)
-15

sage: supersingular_D(83401)
-7

AUTHORS:

sage.modular.ssmod.ssmod.supersingular_j(FF)

Return a supersingular j-invariant over the finite field FF.

INPUT:

  • FF – finite field with p^2 elements, where p is a prime number

OUTPUT:

  • finite field element – a supersingular j-invariant defined over the finite field FF

EXAMPLES:

The following examples calculate supersingular j-invariants for a few finite fields:

sage: supersingular_j(GF(7^2, 'a'))
6

Observe that in this example the j-invariant is not defined over the prime field:

sage: supersingular_j(GF(15073^2, 'a'))
4443*a + 13964
sage: supersingular_j(GF(83401^2, 'a'))
67977

AUTHORS: