2011-07-03-saturation_idea

326 days ago by WilliamStein

Slow but direct way to saturate.

Let Q1, Q2 be gens for a subgroup of finite index of E(K)/tor. Check for each element Q of this set:

 {Q1 + b*Q2 : 0 &lt = b < ell } union {Q2}

if Q is divisible by ell; if not, then the subgroup is ell-saturated.
def sat2(Q1, Q2, ell): """ INPUT: - Q1, Q2 -- generators for a finite index subgroup of Mordell-Weil - ell -- any prime OUTPUT: - True, [Q1,Q2] if the subgroup is ell-saturated - False, [P1, P2] generating a bigger subgroup if not ell-saturated. Of course, the bigger subgroup might itself *not* be ell-saturated yet. """ for b in range(ell): v = (Q1 + b*Q2).division_points(ell) if len(v) > 0: return False, [v[0], Q2] v = Q2.division_points(ell) if len(v) > 0: return False, [Q1, v[0]] return True, [Q1, Q2] 
       
K.<a> = NumberField(x^2 - x - 1) import psage.ellcurve.lseries.sqrt5 as sqrt5w 
       
E = EllipticCurve([0,-a,1,-a-1,2*a+1] ) Q1, Q2 = E.gens() 
       
sat2(Q1, Q2, 2) 
        
(True, [(0 : -a - 1 : 1), (-3/4*a + 1/4 : -5/4*a - 5/8 : 1)])
(True, [(0 : -a - 1 : 1), (-3/4*a + 1/4 : -5/4*a - 5/8 : 1)])
sat2(Q1, Q2, 3) 
        
(False, [(0 : -a - 1 : 1), (a + 1 : -a - 1 : 1)])
(False, [(0 : -a - 1 : 1), (a + 1 : -a - 1 : 1)])
t, (P1, P2) = sat2(Q1, Q2, 3) 
       
sat2(P1, P2, 3) 
        
(True, [(0 : -a - 1 : 1), (a + 1 : -a - 1 : 1)])
(True, [(0 : -a - 1 : 1), (a + 1 : -a - 1 : 1)])

How slow is this?
for ell in primes(20): t = cputime() z = sat2(Q1, Q2, ell) print ell, cputime(t) 
        
2 0.01
3 0.04
5 0.12
7 0.3
11 2.03
13 3.25
17 33.07
2 0.01
3 0.04
5 0.12
7 0.3
11 2.03
13 3.25
17 33.07

Thus this algorithm is very simple to implement, but is extremeley insanely slow compared to the reduction-modulo-primes algorithm that we have also implemented.  This is thus just a nice double check in small cases that we're getting the right answer.