# What is the complexity of finding a point with a given height on elliptic curve?

It is well known that there exists a canonical height function $\hat{h}:E(\mathbb{Q})\longrightarrow\mathbb{R}$. My question is: I have a real number $h$ and elliptic curve $E$. Is there a feasible algorithm to find $P\in E(\mathbb{Q})$ such that $\hat{h}(P)=h$?What is the complexity of the best known algorithm?

• Unless $P$ is torsion, the canonical height $\hat{h}(P)$ is probably not an integer! Jan 10, 2014 at 19:27
• You are right! I have a mistake! I have a real number not an integer. Jan 11, 2014 at 4:39
• $E(\mathbf Q)$ is countable, thus the canonical height function is not surjective. Jan 11, 2014 at 9:53
• @Ari I don't think that Somayeh is trying solve $\hat h(P)=c$ for all $c\in\mathbb{R}$. Instead, he has a $c$ value that he knows comes from some $P$, and he's trying to find $P$. So the fact that $\hat h$ is not surjective doesn't matter. Jan 11, 2014 at 14:38
• @JoeSilverman Ah yes, you're right. Thank you. Jan 11, 2014 at 16:14

As Samir says, and even more, it's likely that $\hat h(P)$ is transcendental for nontorsion points. Having said that, I have an article [1] explaining how to use the value of $\hat h(P)$ to cut down on the search for $P$. The application was that in some cases one can find $\hat h(P)$ (or some small multiple of it) by computing $L'(E,1)$, so it is in fact possible to know $\hat h(P)$ without first computing $P$. However, I should also mention that Zagier noted that it's frequently (always?) more efficient to compute a Heegner point. So I think that the main application of my paper would be to prove, say, that there are no integral points (or no $S$-integral points) in the case that $E$ has rank 1, but the generator is too large ton explicitly compute by any known method.
[1] Computing rational points on rank 1 elliptic curves via $L$-series and canonical heights, Math Comp. 68 (1999), 835-858.
• I noted soon after publishing my ANTS-IV paper arxiv.org/abs/math/0005139 that this technique lets one find a point of canonical height $\hat h$ (known to sufficient precision) in time $O(\exp(\epsilon\hat h))$, but I don't know that that's ever been implemented or is likely to ever be of use, even though something like that should be available more generally for finding an $r$-th independent point knowing the first $r-1$ points and the regulator, for which we don't have a Heegner-point end run. Jan 11, 2014 at 3:38