Kamiennys Criterion¶

Kamienny’s Criterion

AUTHORS:

William Stein, February 2010

Maarten Derickx, 2010-2017

class mdsage.kamiennys_criterion.KamiennyCriterion(p, congruence_type=1, sign=1, algorithm='custom', verbose=False, dump_dir=None)¶

Bases: object

This class if for verification of Kamienny’s criterion for arbitrary fields using ell=2 for arbitrary level.

EXAMPLES:

sage: from mdsage import *
sage: C = KamiennyCriterion(31); C
Kamienny's Criterion for p=31
sage: C.dbd(2)
26 x 26 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
sage: C.dbd(2)^15==1
True
sage: C.T(2)
26 x 26 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
sage: C.t1(n=3)
26 x 26 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
sage: C.t2()
26 x 26 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
sage: C.t()
26 x 26 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)

T¶

File: mdsage/kamiennys_criterion.py (starting at line 562)

Return matrix mod 2 of the n-th Hecke operator on the +1 quotient of cuspidal modular symbols.

INPUT:

n – integer

OUTPUT:

matrix modulo 2

EXAMPLES:

sage: from mdsage import *
sage: C = KamiennyCriterion(29)
sage: C.T(2)
22 x 22 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
sage: C.T(2)[0]
(0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0)

coset_representatives_H¶

File: mdsage/kamiennys_criterion.py (starting at line 472)

Return representatives of Z/NZ^*/H where H is a subgroup of the diamond operators and N is the level. H=Z/NZ^* for Gamma0 and H=1 for Gamma1

EXAMPLES:

sage: from mdsage import *
sage: C = KamiennyCriterion(GammaH(31,[3^5]))
sage: C.coset_representatives_H()
(1, 2, 3, 4, 8)
sage: C = KamiennyCriterion(13)

dbd(d)¶

Return matrix of <d>.

INPUT:

d – integer

OUTPUT:

a matrix modulo 2

EXAMPLES:

sage: from mdsage import *
sage: C = KamiennyCriterion(29)
sage: C.dbd(2)
22 x 22 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
sage: C.dbd(2)^14==1
True
sage: C.dbd(2)[0]
(0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

dependencies(t, k, l, v)¶

Return the vectorspace of dependencies between the t*dbd(d)*T(i)*v with d a set of coset representatives of (Z/NZ)*/(+/-H) and 0<i<=kl, and t*T(l+1),…,t*T(k)

INPUT:

k – integer the size of the largest partion occuring in the partitions you want to check

l – integer which is larger then or equal to the second larges partition

hecke_polynomial¶: File: mdsage/kamiennys_criterion.py (starting at line 678)

integral_cuspidal_subspace()¶: In certatain cases this might return the integral structure of the cuspidal subspace. This code is mainly a way to compute the integral structe faster than sage does now. It returns None if it cannot find the integral subspace.

is_independent(v)¶

Return True if the Hecke operators in v are independent.

INPUT:

v – four elements of the Hecke algebra mod 2 (represented as matrices)

OUTPUT:

bool

EXAMPLES:

sage: from mdsage import *
sage: C = KamiennyCriterion(29)
sage: C.is_independent([C.T(1), C.T(2), C.T(3), C.T(4)])
True
sage: C.is_independent([C.T(1), C.T(2), C.T(3), C.T(1)+C.T(3)])
False

t(n=5, p=65521, q=3)¶

Return mod 2 matrix t, using n, p and q as options for t1 and t2. This is just the product of self.t1() and self.t2(). If p=None it uses t1 else it uses t1_prime

INPUT:

n – integer (optional default=5), used in computing t1

p – prime (optional default=46337), used in computing t1

q – prime (optional default=3), used in computing t2

OUTPUT:

a mod 2 matrix

EXAMPLES:

sage: from mdsage import *
sage: C = KamiennyCriterion(29)
sage: C.t()[0]
(1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0)

t1(n=5)¶

Return choice of element t1 of the Hecke algebra mod 2, computed using the Hecke operator $T_n$, where n is self.n

INPUT:

n – integer (optional default=5)

OUTPUT:

a mod 2 matrix

EXAMPLES:

sage: from mdsage import *
sage: C = KamiennyCriterion(29)
sage: C.t1(n=3)
22 x 22 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
sage: C.t1(n=3) == 1
True
sage: C.t1()
Traceback (most recent call last):
...
ValueError: T_5 needs to be a generator of the hecke algebra
sage: C = KamiennyCriterion(37)
sage: C.t1()[0]
 (1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1)

t1_prime¶

File: mdsage/kamiennys_criterion.py (starting at line 682)

Return a multiple of element t1 of the Hecke algebra mod 2, computed using the Hecke operator $T_n$, where n is self.n. To make computation faster we only check if …==0 mod p. Hence J will contain more elements, hence we get a multiple.

INPUT:

n – integer (optional default=5)

p – prime (optional default=65521)

OUTPUT:

a mod 2 matrix

EXAMPLES:

sage: from mdsage import *
sage: C = KamiennyCriterion(29)
sage: C.t1_prime()
22 x 22 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
sage: C.t1_prime(n=3) == 1
True
sage: C = KamiennyCriterion(37)
sage: C.t1_prime()[0]
(1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1)

t2(q=3)¶

Return mod 2 matrix t2 computed using the current choice of prime q, as returned by self.q.

INPUT:

q – integer

OUTPUT:

a mod 2 matrix

EXAMPLES:

sage: from mdsage import *
sage: C = KamiennyCriterion(29)
sage: C.t2()[0]
(0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1)

tdbdTi(t, k, v)¶

Return a list of lists which contains precomputed values of t*dbd(d)*T(i)*v with d a set of coset representatives of (Z/NZ)*/(+/-H) and 0<i<=k

INPUT:

k – integer

OUTPUT:

a list of lists containing hecke operators

EXAMPLES:

sage: from mdsage import *
sage: C = KamiennyCriterion(29,verbose=False)
sage: Id=C.t().parent().identity_matrix()
sage: C.t()==C.tdbdTi(C.t(),2,Id)[0][0]
True
sage: C.t()*C.T(2)==C.tdbdTi(C.t(),2,Id)[1][0]
True
sage: C.t()*C.dbd(2)*C.T(2)==C.tdbdTi(C.t(),2,Id)[1][1]
True

verify_criterion(d, t=None, n=5, p=65521, q=3, v=None, use_rand_vec=False, verbose=False)¶

Attempt to verify the criterion at p using the input t. If t is not given compute it using n, p and q

INPUT:

t – hecke operator (optional default=None)

n – integer (optional default=5), used in computing t1

p – prime (optional default=46337), used in computing t1

q – prime (optional default=3), used in computing t2

verbose – bool (default: True); if true, print to stdout as the computation is performed.

OUTPUT:

bool – True if criterion satisfied; otherwise, False

string – message about what happened or went wrong

EXAMPLES:

We can’t get p=29 to work no matter what I try, which nicely illustrates the various ways the criterion can fail:

sage: from mdsage import *
sage: C = KamiennyCriterion(29)
sage: C.verify_criterion(4,n=5)
dependency dimension to large to search through
(False,
 'There is a dependency of weigt 2 in dependencies(3,1)',
 [Vector space of degree 4 and dimension 0 over Finite Field of size 2
  Basis matrix:
  [], Vector space of degree 16 and dimension 8 over Finite Field of size 2
  Basis matrix:
  [1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
  [0 1 0 0 0 0 1 0 1 1 0 1 1 1 0 0]
  [0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0]
  [0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0]
  [0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 0]
  [0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0]
  [0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0]
  [0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0], Vector space of degree 28 and dimension 19 over Finite Field of size 2
  Basis matrix:
  [1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1]
  [0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0]
  [0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0]
  [0 0 0 1 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 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0]
  [0 0 0 0 0 1 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 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0]
  [0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1]
  [0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 1]
  [0 0 0 0 0 0 0 0 0 0 1 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 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1]
  [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 1 0 0]
  [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1]
  [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 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 1 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 1 0 1 0 1 1 0 1 1 1]
  [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 1]
  [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 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 1 0 1 0]])

With p=43 the criterion is satisfied for d=4, thus proving that 43 is not the order of a torsion point on any elliptic curve over a quartic field:

sage: C = KamiennyCriterion(43); C
Kamienny's Criterion for p=43
sage: C.verify_criterion(4)
(True,
 'All conditions are satified for Gamma1 d=4 p=43. Using n=5, modp=65521, q=3 in Kamienny Version 1.5 and SageMath version ...',
 [Vector space of degree 4 and dimension 0 over Finite Field of size 2
  Basis matrix:
  [], Vector space of degree 23 and dimension 2 over Finite Field of size 2
  Basis matrix:
  [1 1 0 1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 0]
  [0 0 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 0 0 0], Vector space of degree 42 and dimension 11 over Finite Field of size 2
  Basis matrix:
  [1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1]
  [0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 0]
  [0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 1 0]
  [0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0]
  [0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0]
  [0 0 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 1 0 1]
  [0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1]
  [0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 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 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 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 1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 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 1 0 1 0 0 0 1 1 1 0 1 1 0 0 0]])

mdsage.kamiennys_criterion.matrix_modp(A, p=2, sparse=False)¶

Reduce a matrix mod p (default 2). We use this function, since there are bugs in the mod 2 matrix reduction in sage. See trac ticket #sage_trac/ticket/6904

INPUT:

A – matrix

p – prime

OUTPUT:

a matrix over GF(p).

EXAMPLES:

sage: from mdsage import *
sage: matrix_modp(matrix(QQ,2,[1,3,5,2/3]))
[1 1]
[1 0]

mdsage.kamiennys_criterion.open_database(location, verbose=False)¶: Creates an sqlite database at location, ready for storing data computed by this criterion, or if it already exists it opens it.

mdsage.kamiennys_criterion.run_criterion(result_table, iterator, congruence_type, algorithm='default', verbose=False)¶: The iterator should spit out things of the form (torsion_order,degree,t1n,t1mod,t2q)

Kamiennys Criterion¶

Previous topic

Next topic

This Page