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
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.
- 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
Retrieve articles in Mathematics of Computation with MSC (2010): 11D45, 11D61, 11J82, 11J86
Retrieve articles in all journals with MSC (2010): 11D45, 11D61, 11J82, 11J86
Additional Information
Michael A. Bennett
Affiliation:
Department of Mathematics, University of British Columbia, Vancouver, British Columbia, Canada
MR Author ID:
339361
Email:
bennett@math.ubc.ca
Adela Gherga
Affiliation:
Department of Mathematics, University of British Columbia, Vancouver, British Columbia, Canada
MR Author ID:
1305412
Email:
ghergaa@math.ubc.ca
Andrew Rechnitzer
Affiliation:
Department of Mathematics, University of British Columbia, Vancouver, British Columbia, Canada
MR Author ID:
626723
ORCID:
0000-0002-4386-3207
Email:
andrewr@math.ubc.ca
Received by editor(s):
October 6, 2017
Received by editor(s) in revised form:
November 1, 2017, February 21, 2018, and March 16, 2018
Published electronically:
August 1, 2018
Additional Notes:
The authors were supported in part by NSERC
Article copyright:
© Copyright 2018
American Mathematical Society