sd 22 -- stein -- Computing Heegner Points
system:sage


<h1 style="text-align: center;">Computing Heegner Points with Sage</h1>
<h3 style="text-align: center;">William Stein</h3>
<h3 style="text-align: center;">University of Washington</h3>

{{{id=5|

///
}}}

<h2>Relevant References</h2>

<ul>
<li><strong>Watkins: &nbsp;</strong><a href="http://arxiv.org/abs/math/0506325" target="_blank">Some remarks on Heegner point computations</a></li>
<li>Delaunay's chapter in<strong> Cohen's book: </strong><em>Number Theory: Tools and diophantine equations, <a href="http://books.google.com/books?id=8zC8VPQV8psC&amp;lpg=PR20&amp;ots=PsP5M0aHwx&amp;dq=Diophantine%20Equations,%20p-adic%20Numbers,%20and%20L-functions%20cohen&amp;pg=PA584#v=onepage&amp;q=heegner%20point%20method&amp;f=false" target="_blank">Section 8.6.&nbsp;</a></em></li>
<li><strong>Stein</strong>: <a href="http://wstein.org/papers/kolyconj2/">Heegner points on rank 2 elliptic curves</a></li>
<li><strong>Sage</strong>: <a href="../../../src/schemes/elliptic_curves/heegner.py" target="_blank">schemes/elliptic_curves/heegner.py</a>&nbsp;&nbsp;(by Stein, Bradshaw)</li>
</ul>
<p>&nbsp;</p>
<p>&nbsp;</p>

<p><strong>WARNING</strong>: Sage's Heegner points code is optimized for doing theoretical research into Kolyvagin's Euler System of Heegner Points.&nbsp;</p>
<p>It is not designed (yet!) to be used as a tool for actually efficiently computing points on curves. &nbsp; Mark Watkins has written code that is in Magma that is very highly optimized for finding points on curves (but not useful for research into Euler systems).&nbsp;</p>

{{{id=94|

///
}}}

{{{id=3|

///
}}}

{{{id=17|

///
}}}

<h2>Computing Heegner Points $y_K$</h2>

{{{id=34|
E = EllipticCurve('37a'); E
///
Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field
}}}

{{{id=28|
E.plot()
///
<html><font color='black'><img src='cell://sage0.png'></font></html>
}}}

{{{id=29|
E.rank()
///
1
}}}

{{{id=30|
E.heegner_discriminants(100)
///
[-3, -4, -7, -11, -40, -47, -67, -71, -83, -84, -95]
}}}

<h3>First a discriminant of class number 1</h3>

{{{id=38|
QuadraticField(-3,'a').class_number()
///
1
}}}

{{{id=33|
P = E.heegner_point(-3); P
///
Heegner point of discriminant -3 on elliptic curve of conductor 37
}}}

{{{id=32|
P.numerical_approx()
///
(-1.00000000000000 + 2.18015221574935e-17*I : 3.24718550659409e-17 + 4.34765071166687e-17*I : 1.00000000000000)
}}}

{{{id=39|
P.numerical_approx(prec=100)
///
(-1.0000000000000000000000000000 - 9.6895704450769185435636090117e-31*I : -5.1662376187963059639095337283e-31 - 1.9379140828452461806982502823e-30*I : 1.0000000000000000000000000000)
}}}

{{{id=36|
P.point_exact()
///
(-1 : 0 : 1)
}}}

<p>Compute the image of the Heegner point on the upper half plane as a complex number, where we view $E$ as $\mathbf{C}/\Lambda$.</p>

{{{id=40|
P.map_to_complex_numbers()
///
0.204680500375773 - 1.22569469099340*I
}}}

<p>The point in the upper half plane (really on the modular curve $X_0(N)$) that maps to the above point $P$.</p>

{{{id=44|
t = P.heegner_point_on_X0N(); t
///
Heegner point 1/74*sqrt(-3) - 21/74 of discriminant -3 on X_0(37)
}}}

{{{id=82|

///
}}}

{{{id=81|

///
}}}

{{{id=45|

///
}}}

<h3>Next, an example in which the class number is $&gt;1$.</h3>

{{{id=49|
for D in E.heegner_discriminants(100):
    print D, QuadraticField(D,'a').class_number()
///
-3 1
-4 1
-7 1
-11 1
-40 2
-47 5
-67 1
-71 7
-83 3
-84 4
-95 8
}}}

{{{id=50|
P = E.heegner_point(-47); P
///
Heegner point of discriminant -47 on elliptic curve of conductor 37
}}}

{{{id=53|
P.heegner_point_on_X0N()
///
Heegner point 1/74*sqrt(-47) - 29/74 of discriminant -47 on X_0(37)
}}}

{{{id=51|
P.numerical_approx(100)
///
(0.41295030345265522481209547079 - 1.2506651800425362123442536977*I : -1.2882357148097753052431772001 - 1.6283769583240139393113357931*I : 1.0000000000000000000000000000)
}}}

{{{id=48|
y_1 = P.point_exact(100); show(y_1)
///
<html><div class="math">\newcommand{\Bold}[1]{\mathbf{#1}}\left(a : a^{4} + a - 1 : 1\right)</div></html>
}}}

<p>Note that $y_1$ is the Heegner point defined over the Hilbert Class Field. &nbsp;It has <em>not</em>&nbsp;been traced down to $K$.</p>

{{{id=41|
K = y_1[0].parent(); K
///
Number Field in a with defining polynomial x^5 - x^4 + x^3 + x^2 - 2*x + 1
}}}

<h2>Computing $y_K$ when $h_K&gt;1$</h2>
<p>Not Implemented!</p>
<p><strong>Project:</strong> The Heegner points package in Sage doesn't have a function that just computes $y_K = {\rm trace}_{H/K}(y_1)$. &nbsp;Implement such a function.</p>

{{{id=63|

///
}}}

{{{id=27|

///
}}}

<h2>Computing Heegner Points $y_1$</h2>

{{{id=2|
E = EllipticCurve('5077a'); E
///
Elliptic Curve defined by y^2 + y = x^3 - 7*x + 6 over Rational Field
}}}

{{{id=19|
E.rank()
///
3
}}}

{{{id=18|
E.heegner_discriminants(100)
///
[-3, -4, -7, -19, -40, -47, -55, -59, -71, -79, -84, -88]
}}}

{{{id=20|
P = E.heegner_point(-7); P
///
Heegner point of discriminant -7 on elliptic curve of conductor 5077
}}}

{{{id=21|
P.numerical_approx()
///
(5.24763468960140e25 - 9.42689096571972e25*I : 2.63080809434194e37 + 1.12035605894541e39*I : 1.00000000000000)
}}}

{{{id=22|
P.numerical_approx(100)
///
(0 : 1.0000000000000000000000000000 : 0)
}}}

<p>Bug in released Sage -- see <a href="http://trac.sagemath.org/sage_trac/ticket/9302" target="_blank">9302</a>. &nbsp;&nbsp;(It just gets the $x$-coordinate and lifts, and didn't do the right thing for point at infinity.)</p>

{{{id=24|
P.point_exact(100)
///
(0 : 1 : 0)
}}}

{{{id=23|

///
}}}

{{{id=13|

///
}}}

{{{id=12|

///
}}}

<h2>Computing Higher Heegner Points $y_n$</h2>
<p>First our rank 1 curve 37a again:</p>

{{{id=61|
E = EllipticCurve('37a'); E
///
Elliptic Curve defined by y^2 + y = x^3 - x over Rational Field
}}}

{{{id=60|
E.rank()
///
1
}}}

{{{id=65|
P = E.heegner_point(-3, 5); P
///
Heegner point of discriminant -3 and conductor 5 on elliptic curve of conductor 37
}}}

{{{id=64|
P.numerical_approx(100)
///
(1.5000000000000000000000000000 - 1.9364916731037084425896326999*I : -1.5904435122427102073514607000e-29 - 3.8729833462074168851792653998*I : 1.0000000000000000000000000000)
}}}

{{{id=59|
P.point_exact(100)
///
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_104.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("UC5wb2ludF9leGFjdCgxMDAp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/private/var/folders/FE/FEo498bGEOeewp0B4AIIP++++TM/-Tmp-/tmph90X0d/___code___.py", line 3, in <module>
    exec compile(u'P.point_exact(_sage_const_100 )' + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "/Users/wstein/sage/build/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/heegner.py", line 3360, in point_exact
    f = self.x_poly_exact(prec, algorithm=algorithm)
  File "/Users/wstein/sage/build/sage/local/lib/python2.6/site-packages/sage/misc/cachefunc.py", line 322, in __call__
    return self._cachedmethod._instance_call(self._instance, *args, **kwds)
  File "/Users/wstein/sage/build/sage/local/lib/python2.6/site-packages/sage/misc/cachefunc.py", line 466, in _instance_call
    cache[key] = self._cachedfunc.f(inst, *args, **kwds)
  File "/Users/wstein/sage/build/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/heegner.py", line 3243, in x_poly_exact
    n = self.ring_class_field().degree_over_K()
  File "/Users/wstein/sage/build/sage/local/lib/python2.6/site-packages/sage/misc/cachefunc.py", line 322, in __call__
    return self._cachedmethod._instance_call(self._instance, *args, **kwds)
  File "/Users/wstein/sage/build/sage/local/lib/python2.6/site-packages/sage/misc/cachefunc.py", line 466, in _instance_call
    cache[key] = self._cachedfunc.f(inst, *args, **kwds)
  File "/Users/wstein/sage/build/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/heegner.py", line 370, in degree_over_K
    return K.class_number() * self.degree_over_H()
  File "/Users/wstein/sage/build/sage/local/lib/python2.6/site-packages/sage/misc/cachefunc.py", line 322, in __call__
    return self._cachedmethod._instance_call(self._instance, *args, **kwds)
  File "/Users/wstein/sage/build/sage/local/lib/python2.6/site-packages/sage/misc/cachefunc.py", line 466, in _instance_call
    cache[key] = self._cachedfunc.f(inst, *args, **kwds)
  File "/Users/wstein/sage/build/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/heegner.py", line 419, in degree_over_H
    raise NotImplementedError
NotImplementedError
}}}

<p><strong>Project: </strong>Implement this. &nbsp;See&nbsp;<span style="white-space: pre;"><span style="font-size: large;"><a href="../../../src/schemes/elliptic_curves/heegner.py/" target="_blank">sage/schemes/elliptic_curves/heegner.py</a>, line 419: "if K.discriminant() &gt; -5:"</span></span></p>
<p>&nbsp;</p>
<p><span style="white-space: pre;"><span style="font-size: large;">The problem is just that some things aren't implemented when $K=\mathbf{Q}(i)$ or $K=\mathbf{Q}(\sqrt{-3})$.</span></span></p>

{{{id=67|
E = EllipticCurve('37a'); E
P = E.heegner_point(-7, 5); P
///
Heegner point of discriminant -7 and conductor 5 on elliptic curve of conductor 37
}}}

{{{id=10|
P.numerical_approx()
///
(5.83468606702153 + 10.1265099943474*I : -0.320931045360298 - 40.0244674238506*I : 1.00000000000000)
}}}

{{{id=9|
y_5 = P.point_exact(); y_5
///
(a : 2/369*a^5 - 11/123*a^4 + 389/369*a^3 - 144/41*a^2 + 1184/369*a - 208/123 : 1)
}}}

{{{id=70|
factor(y_5[0].parent().discriminant())
///
-1 * 5^5 * 7^3
}}}

{{{id=69|

///
}}}

{{{id=68|

///
}}}

<h2>Computing Information About Kolyvagin Classes</h2>

{{{id=15|
E = EllipticCurve('389a'); E
///
Elliptic Curve defined by y^2 + y = x^3 + x^2 - 2*x over Rational Field
}}}

{{{id=73|
E.heegner_discriminants(20)
///
[-4, -7, -11, -19]
}}}

{{{id=8|
H = heegner_points(389); H
///
Set of all Heegner points on X_0(389)
}}}

{{{id=72|
H5 = H.reduce_mod(5); H5
///
Heegner points on X_0(389) over F_5
}}}

{{{id=78|
K = QuadraticField(-7,'a')
///
}}}

{{{id=77|
p = 5
for c in primes(100):
    a_c = E.ap(c)
    print c, a_c % p, (c+1) % p, sage.schemes.elliptic_curves.heegner.is_inert(-7,c)
///
2 3 3 False
3 3 4 True
5 2 1 True
7 0 3 False
11 1 2 False
13 2 4 True
17 4 3 True
19 0 0 True
23 1 4 False
29 4 0 False
31 4 2 True
37 2 3 False
41 2 2 True
43 2 4 False
47 3 3 True
53 4 4 False
59 3 0 True
61 2 2 True
67 0 3 False
71 0 2 False
73 3 4 True
79 2 0 False
83 3 4 True
89 2 0 True
97 1 3 True
}}}

{{{id=76|

///
}}}

<h2>Verify Kolvyagin's Conjecture for a rank 2 curve:</h2>

{{{id=88|
H5
///
Heegner points on X_0(389) over F_5
}}}

<p>The following calculation shows that if we consider the Kolyvagin class for $D=-7$</p>
<p>$$ [P_{17}] \in E(K_{17})/3 E(K_{17})$$</p>
<p>and take its image in $E(\mathbf{F}_{5^2})/3E(\mathbf{F}_{5^2})$, we get $0$.</p>

{{{id=1|
H5.kolyvagin_point_on_curve(D=-7, c=17, E=E, p=3)
///
[0, 0]
}}}

<p>However, if we consider&nbsp;</p>
<p>$$ [P_{41}] \in E(K_{41})/3 E(K_{41})$$</p>
<p>and take its image in $E(\mathbf{F}_{5^2})/3E(\mathbf{F}_{5^2})$, we get something nonzero!</p>

{{{id=90|
H5.kolyvagin_point_on_curve(D=-7, c=41, E=E, p=3)
///
[1, 0]
}}}

<p>This computation is the first ever <strong>provable verification</strong> of <strong>Kolyvagin's conjecture</strong> for a curve of rank at least 2:</p>
<p><strong>Conjecture </strong>(Kolyvagin): &nbsp;Some equivalence class $[P_n] \in E(K_n)/p^m E(K_n)$ is nonzero.</p>

{{{id=86|

///
}}}

{{{id=85|

///
}}}

{{{id=84|

///
}}}

{{{id=93|

///
}}}

{{{id=83|

///
}}}