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
MathSciNet review: 3904149
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 $p$ or $p^2$, for $p$ prime, with comparisons to existing data.

References

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, DOI https://doi.org/10.1090/S0025-5718-1980-0572871-5

S. Akhtari and M. Bhargava, A positive proportion of locally soluble Thue equations are globally insoluble, preprint. Amer. J. Math., to appear.

K. Belabas, A fast algorithm to compute cubic fields, Math. Comp. 66 (1997), no. 219, 1213–1237. MR 1415795, DOI https://doi.org/10.1090/S0025-5718-97-00846-6

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, DOI https://doi.org/10.1090/amsip/007/10

Michael A. Bennett and Amir Ghadermarzi, Mordell’s equation: a classical approach, LMS J. Comput. Math. 18 (2015), no. 1, 633–646. MR 3406453, DOI https://doi.org/10.1112/S1461157015000182

M. A. Bennett and A. Rechnitzer, Computing elliptic curves over $\mathbb {Q}$ : bad reduction at one prime, CAIMS 2015 proceedings.

L. Bernardin et al, Maple Programming Guide, Maplesoft, 2017, Waterloo ON, Canada.

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

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 https://doi.org/10.1006/jsco.1996.0125

Christophe Breuil, Brian Conrad, Fred Diamond, and Richard Taylor, On the modularity of elliptic curves over $\mathbf Q$: wild 3-adic exercises, J. Amer. Math. Soc. 14 (2001), no. 4, 843–939. MR 1839918, DOI https://doi.org/10.1090/S0894-0347-01-00370-8

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, DOI https://doi.org/10.1090/S0273-0979-1990-15937-3

Armand Brumer and Joseph H. Silverman, The number of elliptic curves over $\mathbf Q$ with conductor $N$, Manuscripta Math. 91 (1996), no. 1, 95–102. MR 1404420, DOI https://doi.org/10.1007/BF02567942

J. Coates, An effective $p$-adic analogue of a theorem of Thue. III. The diophantine equation $y^{2}=x^{3}+k$, Acta Arith. 16 (1969/70), 425–435. MR 263742, DOI https://doi.org/10.4064/aa-16-4-425-436

F. Coghlan, Elliptic Curves with Conductor $2^m3^n$, Ph.D. thesis, Manchester, England, 1967.

J. E. Cremona, Elliptic curve tables, http://johncremona.github.io/ecdata/

J. E. Cremona, Algorithms for modular elliptic curves, 2nd ed., Cambridge University Press, Cambridge, 1997. MR 1628193

J. E. Cremona, Reduction of binary cubic and quartic forms, LMS J. Comput. Math. 2 (1999), 64–94. MR 1693411, DOI https://doi.org/10.1112/S1461157000000073

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

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

H. Davenport, The reduction of a binary cubic form. I, J. London Math. Soc. 20 (1945), 14–22. MR 15432, DOI https://doi.org/10.1112/jlms/s1-20.1.14

H. Davenport, The reduction of a binary cubic form. II, J. London Math. Soc. 20 (1945), 139–147. MR 15433, DOI https://doi.org/10.1112/jlms/s1-20.3.139

H. Davenport, On the class-number of binary cubic forms. I, J. London Math. Soc. 26 (1951), 183–192. MR 43822, DOI https://doi.org/10.1112/jlms/s1-26.3.183

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 491593, DOI https://doi.org/10.1098/rspa.1971.0075

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, DOI https://doi.org/10.1090/S0025-5718-1990-0995209-4

N. D. Elkies, How many elliptic curves can have the same prime conductor?, http://math.harvard.edu/~elkies/condp_{b}anff.pdf

Noam D. Elkies, Rational points near curves and small nonzero $|x^3-y^2|$ via lattice reduction, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 33–63. MR 1850598, DOI https://doi.org/10.1007/10722028_2

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, DOI https://doi.org/10.1007/978-3-540-24847-7_3

A. Gherga, Implementation of a Thue-Mahler solver and related problems, Ph.D. thesis, University of British Columbia, 2018.

Toshihiro Hadano, On the conductor of an elliptic curve with a rational point of order $2$, Nagoya Math. J. 53 (1974), 199–210. MR 354673

B. Haible, CLN, a class library for numbers, available from http://www.ginac.de/CLN/

K. Hambrook, Implementation of a Thue-Mahler solver, M.Sc. thesis, University of British Columbia, 2011.

Helmut Hasse, Arithmetische Theorie der kubischen Zahlkörper auf klassenkörpertheoretischer Grundlage, Math. Z. 31 (1930), no. 1, 565–582 (German). MR 1545136, DOI https://doi.org/10.1007/BF01246435

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, DOI https://doi.org/10.1515/crll.1848.36.357

C. Hermite, Sur la réduction des formes cubiques à deux indéterminées, C. R. Acad. Sci. Paris 48 (1859), 351–357.

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

R. von Kanel and B. Matschke, Solving $S$-unit, Mordell, Thue, Thue-Mahler and generalized Ramanujan-Nagell equations via Shimura-Taniyama conjecture, preprint, arXiv:1605.06079.

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

The LMFDB Collaboration, The L-functions and Modular Forms Database, http://www.lmfdb.org

Kurt Mahler, Zur Approximation algebraischer Zahlen. I, Math. Ann. 107 (1933), no. 1, 691–730 (German). MR 1512822, DOI https://doi.org/10.1007/BF01448915

K. Mahler, An application of Jensen’s formula to polynomials, Mathematika 7 (1960), 98–100. MR 124467, DOI https://doi.org/10.1112/S0025579300001637

K. Mahler, An inequality for the discriminant of a polynomial, Michigan Math. J. 11 (1964), 257–262. MR 166188

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, DOI https://doi.org/10.1112/plms/s2-10.1.48

J.-F. Mestre and J. Oesterlé, Courbes de Weil semi-stables de discriminant une puissance $m$-ième, J. Reine Angew. Math. 400 (1989), 173–184 (French). MR 1013729, DOI https://doi.org/10.1515/crll.1989.400.173

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

L. J. Mordell, The Diophantine Equation y2-k=x3, Proc. London Math. Soc. (2) 13 (1914), 60–80. MR 1577519, DOI https://doi.org/10.1112/plms/s2-13.1.60

L. J. Mordell, Diophantine equations, Pure and Applied Mathematics, Vol. 30, Academic Press, London-New York, 1969. MR 0249355

Trygve Nagell, Introduction to Number Theory, John Wiley & Sons, Inc., New York; Almqvist & Wiksell, Stockholm, 1951. MR 0043111

Olaf Neumann, Elliptische Kurven mit vorgeschriebenem Reduktionsverhalten. II, Math. Nachr. 56 (1973), 269–280 (German). MR 338000, DOI https://doi.org/10.1002/mana.19730560127

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, DOI https://doi.org/10.1006/jnth.1993.1040

The PARI Group, Bordeaux. PARI/GP version 2.7.1, 2014, available at http://pari.math.u-bordeaux.fr/.

J. Park, B. Poonen, J. Voight and M. Matchett Wood, A heuristic for boundedness of ranks of elliptic curves, preprint, arXiv:1602.01431.

Attila Pethő, On the resolution of Thue inequalities, J. Symbolic Comput. 4 (1987), no. 1, 103–109. MR 908418, DOI https://doi.org/10.1016/S0747-7171%2887%2980059-7

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, DOI https://doi.org/10.1007/BFb0086553

Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI https://doi.org/10.1016/0022-314X%2880%2990084-0

K. Rubin and A. Silverberg, Mod $2$ representations of elliptic curves, Proc. Amer. Math. Soc. 129 (2001), no. 1, 53–57. MR 1694877, DOI https://doi.org/10.1090/S0002-9939-00-05539-8

The Sage Developers, SageMath, the Sage Mathematics Software System (Version 8.1), http://www.sagemath.org, 2018.

Bennett Setzer, Elliptic curves of prime conductor, J. London Math. Soc. (2) 10 (1975), 367–378. MR 371904, DOI https://doi.org/10.1112/jlms/s2-10.3.367

I. R. Šafarevič, Algebraic number fields, Proc. Internat. Congr. Mathematicians (Stockholm, 1962) Inst. Mittag-Leffler, Djursholm, 1963, pp. 163–176 (Russian). MR 0202709

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

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, DOI https://doi.org/10.4153/CMB-2006-046-1

Jonathan Sorenson and Jonathan Webster, Strong pseudoprimes to twelve prime bases, Math. Comp. 86 (2017), no. 304, 985–1003. MR 3584557, DOI https://doi.org/10.1090/S0025-5718-2016-03134-8

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

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, DOI https://doi.org/10.1007/3-540-45455-1_22

N. M. Stephens, The Birch Swinnerton-Dyer Conjecture for Selmer curves of positive rank, Ph.D. Thesis, Manchester, 1965.

O. Tange, GNU Parallel - The Command-Line Power Tool, ;login: The USENIX Magazine, (2011), 42–47.

Axel Thue, Über Annäherungswerte algebraischer Zahlen, J. Reine Angew. Math. 135 (1909), 284–305 (German). MR 1580770, DOI https://doi.org/10.1515/crll.1909.135.284

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, DOI https://doi.org/10.1016/0022-314X%2889%2990014-0

N. Tzanakis and B. M. M. de Weger, Solving a specific Thue-Mahler equation, Math. Comp. 57 (1991), no. 196, 799–815. MR 1094961, DOI https://doi.org/10.1090/S0025-5718-1991-1094961-0

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

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

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

B. M. M. de Weger, The weighted sum of two $S$-units being a square, Indag. Math. (N.S.) 1 (1990), no. 2, 243–262. MR 1060828, DOI https://doi.org/10.1016/0019-3577%2890%2990007-A

Andrew Wiles, Modular elliptic curves and Fermat’s last theorem, Ann. of Math. (2) 141 (1995), no. 3, 443–551. MR 1333035, DOI https://doi.org/10.2307/2118559