Parallel LLL-reduction for bounding the integral solutions of elliptic Diophantine equations

Hajdu, L.; Kovács, T.

doi:10.1090/S0025-5718-08-02160-1

Parallel LLL-reduction for bounding the integral solutions of elliptic Diophantine equations
HTML articles powered by AMS MathViewer

by L. Hajdu and T. Kovács;

Math. Comp. 78 (2009), 1201-1210

DOI: https://doi.org/10.1090/S0025-5718-08-02160-1

Published electronically: July 1, 2008

PDF | Request permission

Abstract:

Stroeker and Tzanakis gave convincing numerical and heuristic evidence for the fact that in their $\mathcal {E}llog$ method a certain parameter $\lambda$ plays a decisive role in the size of the final bound for the integral points on elliptic curves. Furthermore, they provided an algorithm to determine the Mordell-Weil basis of the curve which corresponds to the optimal choice of $\lambda$. In this paper we show that working with more Mordell-Weil bases simultaneously, the final bound for the integral points can be further decreased.

References

A. Baker, The Diophantine equation $y^{2}=ax^{3}+bx^{2}+cx+d$, J. London Math. Soc. 43 (1968), 1–9. MR 231783, DOI 10.1112/jlms/s1-43.1.1
A. I. Barvinok, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed, 34th Annual Symposium on Foundations of Computer Science (Palo Alto, CA, 1993) IEEE Comput. Soc. Press, Los Alamitos, CA, 1993, pp. 566–572. MR 1328451, DOI 10.1109/SFCS.1993.366830
Yann Bugeaud, On the size of integer solutions of elliptic equations, Bull. Austral. Math. Soc. 57 (1998), no. 2, 199–206. MR 1617363, DOI 10.1017/S0004972700031592
Yann Bugeaud, On the size of integer solutions of elliptic equations. II, Bull. Greek Math. Soc. 43 (2000), 125–130. MR 1846953
Sinnou David, Minorations de formes linéaires de logarithmes elliptiques, Mém. Soc. Math. France (N.S.) 62 (1995), iv+143 (French, with English and French summaries). MR 1385175
J. Gebel, A. Pethő, and H. G. Zimmer, Computing integral points on elliptic curves, Acta Arith. 68 (1994), no. 2, 171–192. MR 1305199, DOI 10.4064/aa-68-2-171-192
L. Hajdu, Optimal systems of fundamental $S$-units for LLL-reduction (to appear).
L. Hajdu and T. Herendi, Explicit bounds for the solutions of elliptic equations with rational coefficients, J. Symbolic Comput. 25 (1998), no. 3, 361–366. MR 1615334, DOI 10.1006/jsco.1997.0181
L. Hajdu, T. Kovács, A parallel LLL-reduction method for bounding the solutions of $S$-unit equations (manuscript).
Tünde Kovács, Combinatorial Diophantine equations—the genus 1 case, Publ. Math. Debrecen 72 (2008), no. 1-2, 243–255. MR 2376872, DOI 10.5486/pmd.2008.4003
J. A. De Loera, D. Haws, R. Hemmecke, P. Huggins, J. Tauzer, R. Yoshida, A user’s guide for LattE v1.1, Nov. 2003.
Ákos Pintér, On the magnitude of integer points on elliptic curves, Bull. Austral. Math. Soc. 52 (1995), no. 2, 195–199. MR 1348477, DOI 10.1017/S000497270001460X
Dimitrios Poulakis, Integer points on algebraic curves with exceptional units, J. Austral. Math. Soc. Ser. A 63 (1997), no. 2, 145–164. MR 1475559
Wolfgang M. Schmidt, Integer points on curves of genus $1$, Compositio Math. 81 (1992), no. 1, 33–59. MR 1145607
T. N. Shorey and R. Tijdeman, Exponential Diophantine equations, Cambridge Tracts in Mathematics, vol. 87, Cambridge University Press, Cambridge, 1986. MR 891406, DOI 10.1017/CBO9780511566042
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
R. J. Stroeker and N. Tzanakis, Solving elliptic Diophantine equations by estimating linear forms in elliptic logarithms, Acta Arith. 67 (1994), no. 2, 177–196. MR 1291875, DOI 10.4064/aa-67-2-177-196
Roel J. Stroeker and Nikos Tzanakis, On the elliptic logarithm method for elliptic Diophantine equations: reflections and an improvement, Experiment. Math. 8 (1999), no. 2, 135–149. MR 1700575
R. J. Stroeker and N. Tzanakis, Computing all integer solutions of a genus 1 equation, Math. Comp. 72 (2003), no. 244, 1917–1933. MR 1986812, DOI 10.1090/S0025-5718-03-01497-2
Roelof J. Stroeker and Benjamin M. M. de Weger, Elliptic binomial Diophantine equations, Math. Comp. 68 (1999), no. 227, 1257–1281. MR 1622097, DOI 10.1090/S0025-5718-99-01047-9
N. Tzanakis, Solving elliptic Diophantine equations by estimating linear forms in elliptic logarithms. The case of quartic equations, Acta Arith. 75 (1996), no. 2, 165–190. MR 1379397, DOI 10.4064/aa-75-2-165-190
Paul M. Voutier, An upper bound for the size of integral solutions to $Y^m=f(X)$, J. Number Theory 53 (1995), no. 2, 247–271. MR 1348763, DOI 10.1006/jnth.1995.1090
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