Computing elliptic curves over ℚ

Bennett, Michael; Gherga, Adela; Rechnitzer, Andrew

doi:10.1090/mcom/3370

Computing elliptic curves over $\mathbb {Q}$
HTML articles powered by AMS MathViewer

by Michael A. Bennett, Adela Gherga and Andrew Rechnitzer HTML | PDF

Math. Comp. 88 (2019), 1341-1390 Request permission

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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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_banff.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 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 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 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 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 10.1007/BF01448915
K. Mahler, An application of Jensen’s formula to polynomials, Mathematika 7 (1960), 98–100. MR 124467, DOI 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 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 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 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 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 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 10.1016/S0747-7171(87)80059-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 10.1007/BFb0086553
Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-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 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 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) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. 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 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 10.1090/mcom/3134
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, DOI 10.1007/BFb0073786
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 10.1007/3-540-45455-1_{2}2
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 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 10.1016/0022-314X(89)90014-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 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 10.1016/0019-3577(90)90007-A
Andrew Wiles, Modular elliptic curves and Fermat’s last theorem, Ann. of Math. (2) 141 (1995), no. 3, 443–551. MR 1333035, DOI 10.2307/2118559