4
$\begingroup$

Let $E$ be an elliptic curve over rational numbers. We know that the set of integral points on $E$ is finite. What is the complexity of finding a point $P\in E(\mathbb{Z})$?

Indeed I'm trying to find integral points on an elliptic curve of the form $y^2=x^3+ax^2+bx$, if the rank is $1$, I can use Silverman's algorithm in $$COMPUTING~RATIONAL~POINTS~ON~RANK~1~ELLIPTIC~CURVES~VIA~l-SERIES~AND~CANONICAL~HEIGHTS$$ Because I know P is it's generator! But the conductor of $E$ and logarithmic height of $P$ are too large. Is there an efficient algorithm to find $P$?What is the best algortihm in the cases where $rank(E)>1$?

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
3
$\begingroup$

The best unconditional complexity bounds I know of are those coming from Baker's theory of linear forms in logarithms. Baker wrote a paper "The Diophantine equation $Y^2 = aX^3 + bX^2 + cX + d$" where he worked out some impractical but rigorous bound on the complexity of enumerating the integral points on an elliptic curve. I think that there better results on linear forms in logarithms that can improve this bound, hopefully someone will surface that can address this.

In practice, you almost never use Baker's method for computing integral points on elliptic curves. Usually one computes a basis for the Mordell-Weil group first and then uses the GPZ algorithm to enumerate the integral points. (See William Stein's answer in joro's first link for a description of the various implementations of this.) There should be some improvement in the complexity of GPZ coming from new results on linear forms in elliptic logarithms, but I'm not sure if anyone has really worked this out in detail.

The main problem with the GPZ approach is computing a Mordell-Weil basis in the first place. There is no algorithm for determining a basis for the Mordell-Weil group which has been unconditionally proven to terminate with the correct answer. This is a central problem related to BSD and the finiteness of Sha. It's also the main bottleneck in using GPZ to get a much better bound on the complexity the OP asked about.

There are conditional algorithms that assume finiteness of Sha, or the BSD rank conjecture. Assuming GRH usually helps speed up finding upper bounds on the rank in both cases. For rank at least $2$, we don't have a great way of finding rational points like the Heegner point construction for rank $1$. Hindry wrote a great paper about why computing the Mordell-Weil group is hard, and it's probably about the best place to get an idea of the complexity without getting the experience of computing a bunch of Mordell-Weil groups.

I'm pretty clueless about what the true complexity of computing the Mordell-Weil rank should be. It's somewhere between "not much easier than determining the number of prime factors of the conductor" and "not computable". Of course these are both extremes, the complexity is probably closer to $N^{1/2 + \epsilon}$ where $N$ is the conductor.

Computing ranks is still an art form. If you have a particular curve $E$ in mind, and you've tried E.gens() in Sage, MordellWeilShaInformation(E) in Magma, and looked for it at http://www.lmfdb.org, then it would be good to ask someone.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ In practice, one uses techniques based upon linear forms in elliptic logarithms because that's what the people who wrote the code in Magma and Sage used. For curves of even moderately high rank (whatever that means) one would expect that going via complex logarithms would be much faster. $\endgroup$
    – Mike Bennett
    Commented Sep 28, 2014 at 22:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .