Explicit 𝑛-descent on elliptic curves III. Algorithms

Cremona, J.; Fisher, T.; O’Neil, C.; Simon, D.; Stoll, M.

doi:10.1090/S0025-5718-2014-02858-5

Explicit $n$-descent on elliptic curves III. Algorithms
HTML articles powered by AMS MathViewer

by J. E. Cremona, T. A. Fisher, C. O’Neil, D. Simon and M. Stoll PDF

Math. Comp. 84 (2015), 895-922 Request permission

Abstract:

This is the third in a series of papers in which we study the $n$-Selmer group of an elliptic curve, with the aim of representing its elements as curves of degree $n$ in $\mathbb {P}^{n-1}$. The methods we describe are practical in the case $n=3$ for elliptic curves over the rationals, and have been implemented in MAGMA.

One important ingredient of our work is an algorithm for trivialising central simple algebras. This is of independent interest; for example, it could be used for parametrising Brauer-Severi surfaces.

References

Sang Yook An, Seog Young Kim, David C. Marshall, Susan H. Marshall, William G. McCallum, and Alexander R. Perlis, Jacobians of genus one curves, J. Number Theory 90 (2001), no. 2, 304–315. MR 1858080, DOI 10.1006/jnth.2000.2632
H. F. Blichfeldt, A new principle in the geometry of numbers, with some applications, Trans. Amer. Math. Soc. 15 (1914), no. 3, 227–235. MR 1500976, DOI 10.1090/S0002-9947-1914-1500976-6
Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
N. Bruin, B. Poonen and M. Stoll, Generalized explicit descent and its application to curves of genus 3, Preprint (2012), arXiv:1205.4456v1 [math.NT]
J. W. S. Cassels, Arithmetic on curves of genus $1$. IV. Proof of the Hauptvermutung, J. Reine Angew. Math. 211 (1962), 95–112. MR 163915, DOI 10.1515/crll.1962.211.95
J. W. S. Cassels, Second descents for elliptic curves, J. Reine Angew. Math. 494 (1998), 101–127. Dedicated to Martin Kneser on the occasion of his 70th birthday. MR 1604468, DOI 10.1515/crll.1998.001
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
J.E. Cremona, mwrank, part of the eclib library. Available at http://www.warwick.ac.uk/staff/J.E.Cremona/mwrank/.
J.E. Cremona, Elliptic Curve Data. Available at http://www.warwick.ac.uk/staff/J.E.Cremona/ftp/data/INDEX.html.
J. E. Cremona, T. A. Fisher, C. O’Neil, D. Simon, and M. Stoll, Explicit $n$-descent on elliptic curves. I. Algebra, J. Reine Angew. Math. 615 (2008), 121–155. MR 2384334, DOI 10.1515/CRELLE.2008.012
J. E. Cremona, T. A. Fisher, C. O’Neil, D. Simon, and M. Stoll, Explicit $n$-descent on elliptic curves. II. Geometry, J. Reine Angew. Math. 632 (2009), 63–84. MR 2544143, DOI 10.1515/CRELLE.2009.050
J.E. Cremona, T.A. Fisher, C. O’Neil, D. Simon and M. Stoll, Explicit $n$-descent on elliptic curves, III Algorithms, arXiv:1107.3516v2 [math.NT]. This is the preprint version of this paper; it has a more detailed version of Sections 2 and 3, contains more examples and comes with a file that shows how to do the computations for the examples in MAGMA.
John E. Cremona, Tom A. Fisher, and Michael Stoll, Minimisation and reduction of 2-, 3- and 4-coverings of elliptic curves, Algebra Number Theory 4 (2010), no. 6, 763–820. MR 2728489, DOI 10.2140/ant.2010.4.763
B. Creutz, Explicit second $p$-descent on elliptic curves, Doctoral Thesis, Jacobs University Bremen, 2010. Available at http://www.jacobs-university.de/phd/files/1283816493.pdf.
Brendan Creutz and Robert L. Miller, Second isogeny descents and the Birch and Swinnerton-Dyer conjectural formula, J. Algebra 372 (2012), 673–701. MR 2990032, DOI 10.1016/j.jalgebra.2012.09.029
Z. Djabri, Edward F. Schaefer, and N. P. Smart, Computing the $p$-Selmer group of an elliptic curve, Trans. Amer. Math. Soc. 352 (2000), no. 12, 5583–5597. MR 1694286, DOI 10.1090/S0002-9947-00-02535-6
Claus Fieker and Damien Stehlé, Short bases of lattices over number fields, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 6197, Springer, Berlin, 2010, pp. 157–173. MR 2721419, DOI 10.1007/978-3-642-14518-6_{1}5
Tom Fisher, Finding rational points on elliptic curves using 6-descent and 12-descent, J. Algebra 320 (2008), no. 2, 853–884. MR 2422319, DOI 10.1016/j.jalgebra.2008.04.007
Tom Fisher, Some improvements to 4-descent on an elliptic curve, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 125–138. MR 2467841, DOI 10.1007/978-3-540-79456-1_{8}
T. A. Fisher and G. F. Sills, Local solubility and height bounds for coverings of elliptic curves, Math. Comp. 81 (2012), no. 279, 1635–1662. MR 2904595, DOI 10.1090/S0025-5718-2012-02587-7
T.A. Fisher, Elements of order $3$ in the Tate-Shafarevich group, online tables at http://www.dpmms.cam.ac.uk/~taf1000/g1data/order3.html.
T.A. Fisher, Explicit 5-descent on elliptic curves, in ANTS X: Proceedings of the Tenth Algorithmic Number Theory Symposium, San Diego, 2012, Everett W. Howe, Kiran S. Kedlaya (eds.), Open Book Series, Vol. 1. Mathematical Sciences Publishers, Berkeley, 2013.
C. Friedrichs, Berechnung von Maximalordnungen über Dedekindringen, Dissertation, Technische Universität Berlin, 2000. Available at http://opus.kobv.de/tuberlin/volltexte/2001/40/pdf/friedrichs_carsten.pdf.
Willem A. de Graaf, Michael Harrison, Jana Pílniková, and Josef Schicho, A Lie algebra method for rational parametrization of Severi-Brauer surfaces, J. Algebra 303 (2006), no. 2, 514–529. MR 2255120, DOI 10.1016/j.jalgebra.2005.06.022
John Hunter, The minimum discriminants of quintic fields, Proc. Glasgow Math. Assoc. 3 (1957), 57–67. MR 91309
Gábor Ivanyos and Lajos Rónyai, Finding maximal orders in semisimple algebras over $\textbf {Q}$, Comput. Complexity 3 (1993), no. 3, 245–261. MR 1246219, DOI 10.1007/BF01271370
Gábor Ivanyos, Lajos Rónyai, and Josef Schicho, Splitting full matrix algebras over algebraic number fields, J. Algebra 354 (2012), 211–223. MR 2879232, DOI 10.1016/j.jalgebra.2012.01.008
J. R. Merriman, S. Siksek, and N. P. Smart, Explicit $4$-descents on an elliptic curve, Acta Arith. 77 (1996), no. 4, 385–404. MR 1414518, DOI 10.4064/aa-77-4-385-404
Victor S. Miller, The Weil pairing, and its efficient calculation, J. Cryptology 17 (2004), no. 4, 235–261. MR 2090556, DOI 10.1007/s00145-004-0315-8
David Mumford, Varieties defined by quadratic equations, Questions on Algebraic Varieties (C.I.M.E., III Ciclo, Varenna, 1969) Edizioni Cremonese, Rome, 1970, pp. 29–100. MR 0282975
I. Reiner, Maximal orders, London Mathematical Society Monographs. New Series, vol. 28, The Clarendon Press, Oxford University Press, Oxford, 2003. Corrected reprint of the 1975 original; With a foreword by M. J. Taylor. MR 1972204
Lajos Rónyai, Computing the structure of finite algebras, J. Symbolic Comput. 9 (1990), no. 3, 355–373. MR 1056632, DOI 10.1016/S0747-7171(08)80017-X
Edward F. Schaefer, Computing a Selmer group of a Jacobian using functions on the curve, Math. Ann. 310 (1998), no. 3, 447–471. MR 1612262, DOI 10.1007/s002080050156
Edward F. Schaefer and Michael Stoll, How to do a $p$-descent on an elliptic curve, Trans. Amer. Math. Soc. 356 (2004), no. 3, 1209–1231. MR 2021618, DOI 10.1090/S0002-9947-03-03366-X
S. Siksek, Descent on curves of genus one, Ph.D. thesis, University of Exeter, 1995. Available at http://hdl.handle.net/10871/8323.
S. Stamminger, Explicit 8-descent on elliptic curves, PhD thesis, International University Bremen, 2005. Available at http://www.jacobs-university.de/phd/files/1135329284.pdf.
M. Stoll, Descent on elliptic curves, to appear in Panoramas et Synthéses 36, Société Mathématique de France. Available at http://www.mathe2.uni-bayreuth.de/stoll/talks/short-course-descent.pdf.
André Weil, Basic number theory, 3rd ed., Die Grundlehren der mathematischen Wissenschaften, Band 144, Springer-Verlag, New York-Berlin, 1974. MR 0427267
T.O. Womack, Explicit descent on elliptic curves, Ph.D. thesis, University of Nottingham, 2003. Available at http://www.warwick.ac.uk/staff/J.E.Cremona/theses/womack.pdf.