Computing elliptic curves over ℚ

Bennett, Michael; Gherga, Adela; Rechnitzer, Andrew

doi:10.1090/mcom/3370

Computing elliptic curves over $\mathbb{Q}$

Authors: Michael A. Bennett, Adela Gherga and Andrew Rechnitzer
Journal: Math. Comp. 88 (2019), 1341-1390
MSC (2010): Primary 11D45, 11D61; Secondary 11J82, 11J86
DOI: https://doi.org/10.1090/mcom/3370
Published electronically: August 1, 2018
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: We discuss an algorithm for finding all elliptic curves over $\mathbb{Q}$ with a given conductor. Though based on classical ideas derived from reducing the problem to one of solving associated Thue-Mahler equations, our approach, in many cases at least, appears to be reasonably efficient computationally. We provide details of the output derived from running the algorithm, concentrating on the cases of conductor or , for prime, with comparisons to existing data.

[1] M. K. Agrawal, J. H. Coates, D. C. Hunt, and A. J. van der Poorten, Elliptic curves of conductor 11, Math. Comp. 35 (1980), no. 151, 991–1002. MR 572871, https://doi.org/10.1090/S0025-5718-1980-0572871-5
[2] S. Akhtari and M. Bhargava, A positive proportion of locally soluble Thue equations are globally insoluble, preprint. Amer. J. Math., to appear.
[3] K. Belabas, A fast algorithm to compute cubic fields, Math. Comp. 66 (1997), no. 219, 1213–1237. MR 1415795, https://doi.org/10.1090/S0025-5718-97-00846-6
[4] K. Belabas and H. Cohen, Binary cubic forms and cubic number fields, Organic mathematics (Burnaby, BC, 1995) CMS Conf. Proc., vol. 20, Amer. Math. Soc., Providence, RI, 1997, pp. 175–204. MR 1483919
[5] Michael A. Bennett and Amir Ghadermarzi, Mordell’s equation: a classical approach, LMS J. Comput. Math. 18 (2015), no. 1, 633–646. MR 3406453, https://doi.org/10.1112/S1461157015000182
[6] M. A. Bennett and A. Rechnitzer, Computing elliptic curves over $\mathbb{Q}$ : bad reduction at one prime, CAIMS 2015 proceedings.
[7] L. Bernardin et al,
Maple Programming Guide, Maplesoft, 2017, Waterloo ON, Canada.
[8] B. J. Birch and W. Kuyk (eds.), Modular functions of one variable. IV, Lecture Notes in Mathematics, Vol. 476, Springer-Verlag, Berlin-New York, 1975. MR 0376533
[9] 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, https://doi.org/10.1006/jsco.1996.0125
[10] Christophe Breuil, Brian Conrad, Fred Diamond, and Richard Taylor, On the modularity of elliptic curves over 𝐐: wild 3-adic exercises, J. Amer. Math. Soc. 14 (2001), no. 4, 843–939. MR 1839918, https://doi.org/10.1090/S0894-0347-01-00370-8
[11] Armand Brumer and Oisín McGuinness, The behavior of the Mordell-Weil group of elliptic curves, Bull. Amer. Math. Soc. (N.S.) 23 (1990), no. 2, 375–382. MR 1044170, https://doi.org/10.1090/S0273-0979-1990-15937-3
[12] Armand Brumer and Joseph H. Silverman, The number of elliptic curves over 𝐐 with conductor 𝐍, Manuscripta Math. 91 (1996), no. 1, 95–102. MR 1404420, https://doi.org/10.1007/BF02567942
[13] J. Coates, An effective 𝑝-adic analogue of a theorem of Thue. III. The diophantine equation 𝑦²=𝑥³+𝑘, Acta Arith. 16 (1969/1970), 425–435. MR 0263742, https://doi.org/10.4064/aa-16-4-425-436
[14] F. Coghlan, Elliptic Curves with Conductor , Ph.D. thesis, Manchester, England, 1967.
[15] J. E. Cremona, Elliptic curve tables, http://johncremona.github.io/ecdata/
[16] J. E. Cremona, Algorithms for modular elliptic curves, 2nd ed., Cambridge University Press, Cambridge, 1997. MR 1628193
[17] J. E. Cremona, Reduction of binary cubic and quartic forms, LMS J. Comput. Math. 2 (1999), 64–94. MR 1693411, https://doi.org/10.1112/S1461157000000073
[18] J. E. Cremona, mwrank and related programs for elliptic curves over $\mathbb{Q}$ , 1990-2017, http://www.warwick.ac.uk/staff/J.E. Cremona/mwrank/index.html
[19] J. E. Cremona and M. P. Lingham, Finding all elliptic curves with good reduction outside a given set of primes, Experiment. Math. 16 (2007), no. 3, 303–312. MR 2367320
[20] H. Davenport, The reduction of a binary cubic form. I, J. London Math. Soc. 20 (1945), 14–22. MR 0015432, https://doi.org/10.1112/jlms/s1-20.1.14
[21] H. Davenport, The reduction of a binary cubic form. II, J. London Math. Soc. 20 (1945), 139–147. MR 0015433, https://doi.org/10.1112/jlms/s1-20.3.139
[22] H. Davenport, On the class-number of binary cubic forms. I, J. London Math. Soc. 26 (1951), 183–192. MR 0043822, https://doi.org/10.1112/jlms/s1-26.3.183
[23] H. Davenport and H. Heilbronn, On the density of discriminants of cubic fields. II, Proc. Roy. Soc. London Ser. A 322 (1971), no. 1551, 405–420. MR 0491593, https://doi.org/10.1098/rspa.1971.0075
[24] Bas Edixhoven, Arnold de Groot, and Jaap Top, Elliptic curves over the rationals with bad reduction at only one prime, Math. Comp. 54 (1990), no. 189, 413–419. MR 995209, https://doi.org/10.1090/S0025-5718-1990-0995209-4
[25] N. D. Elkies, How many elliptic curves can have the same prime conductor?, http://math.harvard.edu/~elkies/condp_banff.pdf
[26] Noam D. Elkies, Rational points near curves and small nonzero |𝑥³-𝑦²| via lattice reduction, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 33–63. MR 1850598, https://doi.org/10.1007/10722028_2
[27] Noam D. Elkies and Mark Watkins, Elliptic curves of large rank and small conductor, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 42–56. MR 2137342, https://doi.org/10.1007/978-3-540-24847-7_3
[28] A. Gherga,
Implementation of a Thue-Mahler solver and related problems,
Ph.D. thesis, University of British Columbia, 2018.
[29] Toshihiro Hadano, On the conductor of an elliptic curve with a rational point of order 2, Nagoya Math. J. 53 (1974), 199–210. MR 0354673
[30] B. Haible, CLN, a class library for numbers, available from http://www.ginac.de/CLN/
[31] K. Hambrook,
Implementation of a Thue-Mahler solver,
M.Sc. thesis, University of British Columbia, 2011.
[32] Helmut Hasse, Arithmetische Theorie der kubischen Zahlkörper auf klassenkörpertheoretischer Grundlage, Math. Z. 31 (1930), no. 1, 565–582 (German). MR 1545136, https://doi.org/10.1007/BF01246435
[33] C. Hermite, Note sur la réduction des fonctions homogènes à coefficients entiers et à deux indéterminées, J. Reine Angew. Math. 36 (1848), 357–364 (French). MR 1578622, https://doi.org/10.1515/crll.1848.36.357
[34] C. Hermite, Sur la réduction des formes cubiques à deux indéterminées, C. R. Acad. Sci. Paris 48 (1859), 351-357.
[35] Gaston Julia, Étude sur les formes binaires non quadratiques à indéterminées réelles, ou complexes, ou à indéterminées conjuguées, NUMDAM, [place of publication not identified], 1917 (French). MR 3532882
[36] R. von Kanel and B. Matschke, Solving -unit, Mordell, Thue, Thue-Mahler and generalized Ramanujan-Nagell equations via Shimura-Taniyama conjecture, preprint, arXiv:1605.06079.
[37] A. Koutsianas, Computing all elliptic curves over an arbitrary number field with prescribed primes of bad reduction, Experiment. Math., http://www.tandfonline.com/doi/full/10.1080/10586458.2017.1325791
[38] Kurt Mahler, Zur Approximation algebraischer Zahlen. I, Math. Ann. 107 (1933), no. 1, 691–730 (German). MR 1512822, https://doi.org/10.1007/BF01448915
[39] K. Mahler, An application of Jensen’s formula to polynomials, Mathematika 7 (1960), 98–100. MR 0124467, https://doi.org/10.1112/S0025579300001637
[40] K. Mahler, An inequality for the discriminant of a polynomial, Michigan Math. J. 11 (1964), 257–262. MR 0166188
[41] G. B. Mathews and W. E. H. Berwick, On The Reduction of Arithmetical Binary Cubics which have a Negative Determinant, Proc. London Math. Soc. (2) 10 (1912), 48–53. MR 1576036, https://doi.org/10.1112/plms/s2-10.1.48
[42] J.-F. Mestre and J. Oesterlé, Courbes de Weil semi-stables de discriminant une puissance 𝑚-ième, J. Reine Angew. Math. 400 (1989), 173–184 (French). MR 1013729, https://doi.org/10.1515/crll.1989.400.173
[43] Gary L. Miller, Riemann’s hypothesis and tests for primality, Seventh Annual ACM Symposium on Theory of Computing (Albuquerque, N.M., 1975), Assoc. Comput. Mach., New York, 1975, pp. 234–239. MR 0480296
[44] L. J. Mordell, The Diophantine Equation y2-k=x3, Proc. London Math. Soc. (2) 13 (1914), 60–80. MR 1577519, https://doi.org/10.1112/plms/s2-13.1.60
[45] L. J. Mordell, Diophantine equations, Pure and Applied Mathematics, Vol. 30, Academic Press, London-New York, 1969. MR 0249355
[46] Trygve Nagell, Introduction to Number Theory, John Wiley & Sons, Inc., New York; Almqvist & Wiksell, Stockholm, 1951. MR 0043111
[47] Olaf Neumann, Elliptische Kurven mit vorgeschriebenem Reduktionsverhalten. II, Math. Nachr. 56 (1973), 269–280 (German). MR 0338000, https://doi.org/10.1002/mana.19730560127
[48] Ioannis Papadopoulos, Sur la classification de Néron des courbes elliptiques en caractéristique résiduelle 2 et 3, J. Number Theory 44 (1993), no. 2, 119–152 (French, with French summary). MR 1225948, https://doi.org/10.1006/jnth.1993.1040
[49] The PARI Group, Bordeaux. PARI/GP version 2.7.1, 2014, available at http://pari.math.u-bordeaux.fr/.
[50] J. Park, B. Poonen, J. Voight and M. Matchett Wood, A heuristic for boundedness of ranks of elliptic curves, preprint, arXiv:1602.01431.
[51] Attila Pethő, On the resolution of Thue inequalities, J. Symbolic Comput. 4 (1987), no. 1, 103–109. MR 908418, https://doi.org/10.1016/S0747-7171(87)80059-7
[52] Attila Pethő, On the representation of 1 by binary cubic forms with positive discriminant, Number theory (Ulm, 1987) Lecture Notes in Math., vol. 1380, Springer, New York, 1989, pp. 185–196. MR 1009801, https://doi.org/10.1007/BFb0086553
[53] Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, https://doi.org/10.1016/0022-314X(80)90084-0
[54] K. Rubin and A. Silverberg, Mod 2 representations of elliptic curves, Proc. Amer. Math. Soc. 129 (2001), no. 1, 53–57. MR 1694877, https://doi.org/10.1090/S0002-9939-00-05539-8
[55] The Sage Developers,
SageMath, the Sage Mathematics Software System (Version 8.1),
http://www.sagemath.org,
2018.
[56] Bennett Setzer, Elliptic curves of prime conductor, J. London Math. Soc. (2) 10 (1975), 367–378. MR 0371904, https://doi.org/10.1112/jlms/s2-10.3.367
[57] I. R. Šafarevič, Algebraic number fields, Proc. Internat. Congr. Mathematicians (Stockholm, 1962) Inst. Mittag-Leffler, Djursholm, 1963, pp. 163–176 (Russian). MR 0202709
[58] Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. Congressus Numerantium, No. VII. MR 0371855
[59] Alan K. Silvester, Blair K. Spearman, and Kenneth S. Williams, Cyclic cubic fields of given conductor and given index, Canad. Math. Bull. 49 (2006), no. 3, 472–480. MR 2252268, https://doi.org/10.4153/CMB-2006-046-1
[60] Jonathan Sorenson and Jonathan Webster, Strong pseudoprimes to twelve prime bases, Math. Comp. 86 (2017), no. 304, 985–1003. MR 3584557, https://doi.org/10.1090/S0025-5718-2016-03134-8
[61] Vladimir G. Sprindžuk, Classical Diophantine equations, Lecture Notes in Mathematics, vol. 1559, Springer-Verlag, Berlin, 1993. Translated from the 1982 Russian original; Translation edited by Ross Talent and Alf van der Poorten; With a foreword by van der Poorten. MR 1288309
[62] William A. Stein and Mark Watkins, A database of elliptic curves—first report, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 267–275. MR 2041090, https://doi.org/10.1007/3-540-45455-1_22
[63] N. M. Stephens, The Birch Swinnerton-Dyer Conjecture for Selmer curves of positive rank, Ph.D. Thesis, Manchester, 1965.
[64] O. Tange, GNU Parallel - The Command-Line Power Tool, ;login: The USENIX Magazine, (2011), 42-47.
[65] Axel Thue, Über Annäherungswerte algebraischer Zahlen, J. Reine Angew. Math. 135 (1909), 284–305 (German). MR 1580770, https://doi.org/10.1515/crll.1909.135.284
[66] N. Tzanakis and B. M. M. de Weger, On the practical solution of the Thue equation, J. Number Theory 31 (1989), no. 2, 99–132. MR 987566, https://doi.org/10.1016/0022-314X(89)90014-0
[67] N. Tzanakis and B. M. M. de Weger, Solving a specific Thue-Mahler equation, Math. Comp. 57 (1991), no. 196, 799–815. MR 1094961, https://doi.org/10.1090/S0025-5718-1991-1094961-0
[68] N. Tzanakis and B. M. M. de Weger, How to explicitly solve a Thue-Mahler equation, Compositio Math. 84 (1992), no. 3, 223–288. MR 1189890
[69] Mark Watkins, Stephen Donnelly, Noam D. Elkies, Tom Fisher, Andrew Granville, and Nicholas F. Rogers, Ranks of quadratic twists of elliptic curves, Numéro consacré au trimestre “Méthodes arithmétiques et applications”, automne 2013, Publ. Math. Besançon Algèbre Théorie Nr., vol. 2014/2, Presses Univ. Franche-Comté, Besançon, 2015, pp. 63–98 (English, with English and French summaries). MR 3381037
[70] B. M. M. de Weger, Algorithms for Diophantine equations, CWI Tract, vol. 65, Stichting Mathematisch Centrum, Centrum voor Wiskunde en Informatica, Amsterdam, 1989. MR 1026936
[71] B. M. M. de Weger, The weighted sum of two 𝑆-units being a square, Indag. Math. (N.S.) 1 (1990), no. 2, 243–262. MR 1060828, https://doi.org/10.1016/0019-3577(90)90007-A
[72] Andrew Wiles, Modular elliptic curves and Fermat’s last theorem, Ann. of Math. (2) 141 (1995), no. 3, 443–551. MR 1333035, https://doi.org/10.2307/2118559