""" Kamienny's Criterion AUTHOR: - William Stein, February 2010 """ class KamiennyCriterion: """ This class if for verification of Kamienny's criterion for quartic fields using ell=2 for a given p. EXAMPLES:: 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 sage: C.T(2) 26 x 26 dense matrix over Finite Field of size 2 sage: C.t1() J = [] 26 x 26 dense matrix over Finite Field of size 2 sage: C.t2() 26 x 26 dense matrix over Finite Field of size 2 sage: C.t() J = [] 26 x 26 dense matrix over Finite Field of size 2 """ def __init__(self, p, q=3, n=5, use_integral_structure=False, verbose=True): """ Create a Kamienny criterion object. INPUT: - `p` -- prime -- verify that there is no order p torsion over a quartic field - `q` -- prime, used in computing t2 - `n` -- integer, used in computing t1 - ``use_integral_structure`` -- whether to write all Hecke operators wrt an integral basis before reducing them; needed if the criterion isn't working or if there is a 2 in the denominator of some matrix. - ``verbose`` -- bool; whether to print extra stuff while running. EXAMPLES:: sage: C = KamiennyCriterion(29, 5, 7, use_integral_structure=True, verbose=False); C Kamienny's Criterion for p=29 sage: C.use_integral_structure True sage: C.p 29 sage: C.q 5 sage: C.n 7 sage: C.verbose False """ if not is_prime(p): raise ValueError, "p must be prime" if p < 25: print "WARNING: p must be at least 25 for the criterion to work." self.p = p if not is_prime(q): raise ValueError, "q must be prime" self.q = q self.n = n self.M = ModularSymbols(Gamma1(p), sign=1) self.S = self.M.cuspidal_submodule() self.use_integral_structure = use_integral_structure self.verbose = verbose def __repr__(self): """ Return string representation. EXAMPLES:: sage: KamiennyCriterion(29).__repr__() "Kamienny's Criterion for p=29" """ return "Kamienny's Criterion for p=%s"%self.p def dbd(self, d): """ Return matrix of . INPUT: - `d` -- integer OUTPUT: - a matrix modulo 2 EXAMPLES:: sage: C = KamiennyCriterion(29) sage: C.dbd(2) 22 x 22 dense matrix over Finite Field of size 2 sage: C.dbd(2)[0] (0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0) """ try: return self._dbd[d%self.p] except AttributeError: pass # Find a generator of the integers modulo p: z = primitive_root(self.p) # Compute corresponding operator on integral cuspidal modular symbols if self.use_integral_structure: V = self.S.integral_structure() X = matrix_mod2(self.M.diamond_bracket_operator(z).matrix().restrict(V)) else: X = matrix_mod2(self.S.diamond_bracket_operator(z).matrix()) # Take powers to make list self._dbd of all dbd's such that # self._dbd[d] = v = [None]*self.p v[z] = X a = Mod(z, self.p) Y = X for i in range(self.p-2): Y *= X a *= z v[a] = Y assert v.count(None) == 1 self._dbd = v return v[d%self.p] @cached_method def T(self, n): """ 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: C = KamiennyCriterion(29) sage: C.T(2) 22 x 22 dense matrix over Finite Field of size 2 sage: C.T(2)[0] (0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0) """ if self.use_integral_structure: V = self.S.integral_structure() T = self.M.hecke_matrix(n).restrict(V) else: T = self.S.hecke_matrix(n) return matrix_mod2(T) def t1(self): """ Return choice of element t1 of the Hecke algebra mod 2, computed using the Hecke operator $T_n$, where n is self.n OUTPUT: - a mod 2 matrix EXAMPLES:: sage: C = KamiennyCriterion(29) sage: C.t1() J = [] 22 x 22 dense matrix over Finite Field of size 2 sage: C.t1() == 1 J = [] True sage: C = KamiennyCriterion(37) sage: C.t1()[0] J = [1] (0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1) """ n = self.n T = self.S.hecke_matrix(n) f = T.charpoly() F = f.factor() # Compute the iterators of T acting on the winding element. e = self.M([0,oo]).element().dense_vector() t = self.M.hecke_matrix(n).dense_matrix() g = t.charpoly() Z = t.iterates(e, t.nrows(), rows=True) # We find all factors F[i][0] for f such that # (g/F[i][0])(t) * e = 0. # We do this by computing the polynomial # h = g/F[i][0], # turning it into a vector v, and computing # the matrix product v * Z. If the product # is 0, then e is killed by h(t). J = [] for i in range(len(F)): h, r = g.quo_rem(F[i][0]^F[i][1]) assert r == 0 v = vector(QQ, h.padded_list(t.nrows())) if v*Z == 0: J.append(i) if self.verbose: print "J =", J if len(J) == 0: # The annihilator of e is the 0 ideal. return matrix_mod2(identity_matrix(T.nrows())) # Finally compute t1. I'm concerned about how # long this will take, so we reduce T mod 2 first. # It is important to call "self.T(2)" to get the mod-2 # reduction of T2 with respect to the right basis (e.g., the # integral basis in case use_integral_structure is true. Tmod2 = self.T(2) g = prod(F[i][0].change_ring(GF(2))^F[i][1] for i in J) t1 = g(Tmod2) return t1 def t2(self): """ Return mod 2 matrix t2 computed using the current choice of prime q, as returned by self.q. OUTPUT: - a mod 2 matrix EXAMPLES:: sage: C = KamiennyCriterion(29) sage: C.t2()[0] (0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1) """ q = self.q return self.T(q) - q*self.dbd(q) - 1 def t(self): """ Return mod 2 matrix t, using current choice of self.q and self.n. This is just the product of self.t1() and self.t2(). OUTPUT: - a mod 2 matrix EXAMPLES:: sage: C = KamiennyCriterion(29) sage: C.t()[0] J = [] (0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1) """ return self.t1() * self.t2() def verify_criterion(self, verbose=True): """ Attempt to verify the criterion at p using currently selected choice of Hecke operator t. INPUT: - `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: C = KamiennyCriterion(29) sage: C.verify_criterion() J = [] partition 4=4... partition 4=1+3... partition 4=2+2... partition 4=1+1+2... partition 4=1+1+1+1... (False, 'Fails with partition 4=1+1+1+1 and d1=2, d2=5, d3=12') sage: C.q=7 sage: C.verify_criterion() J = [] partition 4=4... partition 4=1+3... (False, 'Fails with partition 4=1+3 and d=12') sage: C.q=23 sage: C.verify_criterion() J = [] partition 4=4... (False, 'Fails with partition 4=4') With p=31 the criterion is satisfied, thus proving that 31 is not the order of a torsion point on any elliptic curve over a quartic field:: sage: C = KamiennyCriterion(31); C Kamienny's Criterion for p=31 sage: C.verify_criterion() J = [] partition 4=4... partition 4=1+3... partition 4=2+2... partition 4=1+1+2... partition 4=1+1+1+1... (True, 'All conditions are satified') """ t = self.t() T2 = self.T(2) T3 = self.T(3) T4 = self.T(4) p = self.p # partition 4=4: if verbose: print "partition 4=4..." if not self.is_independent([t, t*T2, t*T3, t*T4]): return False, "Fails with partition 4=4" # partition 4=1+3 if verbose: print "partition 4=1+3..." for d in [2..p//2]: dbd = self.dbd(d) if not self.is_independent([t, t*dbd, t*dbd*T2, t*dbd*T3]): return False, "Fails with partition 4=1+3 and d=%s"%d # partition 4=2+2 if verbose: print "partition 4=2+2..." for d in [2..p//2]: dbd = self.dbd(d) if not self.is_independent([t, t*T2, t*dbd, t*dbd*T2]): return False, "Fails with partition 4=2+2 and d=%s"%d # partition 4=1+1+2 if verbose: print "partition 4=1+1+2..." # Iterate over pairs of distinct integers for d1 in [2..p//2]: for d2 in [d1+1..p//2]: dbd1 = self.dbd(d1) dbd2 = self.dbd(d2) if not self.is_independent([t, t*dbd1, t*dbd2, t*dbd2*T2]): return False, "Fails with partition 4=1+1+2 and d1=%s, d2=%s"%(d1,d2) # swap dbd1, dbd2 = dbd2, dbd1 if not self.is_independent([t, t*dbd1, t*dbd2, t*dbd2*T2]): return False, "Fails with partition 4=1+1+2 and d1=%s, d2=%s"%(d1,d2) # partition 4=1+1+1+1 if verbose: print "partition 4=1+1+1+1..." for d1 in [2..p//2]: for d2 in [d1+1..p//2]: for d3 in [d2+1..p//2]: dbd1 = self.dbd(d1) dbd2 = self.dbd(d2) dbd3 = self.dbd(d3) if not self.is_independent([t, t*dbd1, t*dbd2, t*dbd3]): return False, "Fails with partition 4=1+1+1+1 and d1=%s, d2=%s, d3=%s"%(d1,d2,d3) return True, "All conditions are satified" def is_independent(self, v): """ Return True if the four Hecke operators in v are independent. INPUT: - `v` -- four elements of the Hecke algebra mod 2 (represented as matrices) OUTPUT: - bool EXAMPLES:: 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 """ X = matrix(GF(2), 4, sum([a.list() for a in v], [])) c = sage.matrix.matrix_modn_dense.Matrix_modn_dense(X.parent(),X.list(),False,True) return c.rank() == 4 # This crashes! See http://trac.sagemath.org/sage_trac/ticket/8301 # return matrix(GF(2), 4, sum([a.list() for a in v], [])).rank() == 4 raise NotImplementedError def matrix_mod2(A): """ Reduce a matrix mod 2. We use this function, since there are bugs in the mod 2 matrix reduction in sage. See http://trac.sagemath.org/sage_trac/ticket/6904 INPUT: - `A` -- matrix OUTPUT: - a matrix over GF(2). EXAMPLES:: sage: matrix_mod2(matrix(QQ,2,[1,3,5,2/3])) [1 1] [1 0] """ return matrix(GF(2), A.nrows(), A.ncols(), A.list())