8
$\begingroup$

Hi folks,

Let E be a global minimal model of an elliptic curve over QQ, with a 2-torsion point which generates the torsion subgroup, and with Mordell-Weil rank 1 (under BSD). Let RegSha be equal to Regulator(E)*#Sha(E) which has been computed using the BSD formula.

(Assume computing R the non-torsion rational point generator of the Mordell-Weil group E(QQ) using descent by 2-isogeny is time consuming.)

Does the RegSha information make it "easier" to compute R? If so kindly supply search strategy.

Regards, Ifti

Improve this question
$\endgroup$
1
  • $\begingroup$ This is a very interesting question. I'll remark/remind that in the analogous case of a real quadratic field, it certainly does help to know $R_Kh_K$ when trying to compute the fundamental unit. Though, I am not aware of an Arakelov theory for elliptic curves mimicking this. If there was one, probably, it would be known that Sha is finite. $\endgroup$
    – Dror Speiser
    Commented Feb 4, 2012 at 9:24

3 Answers 3

Reset to default
12
$\begingroup$

I described an algorithm of this sort in the paper listed below. The algorithm is also good at finding (or ruling out) the existence of S-integral points. However, I will note that for finding a rational point of infinite order, it is probably more efficient to compute a Heegner point.

  • MR1627825 (99i:11043) Silverman, Joseph H. Computing rational points on rank 1 elliptic curves via L-series and canonical heights. Math. Comp. 68 (1999), no. 226, 835–858

@Dror Speiser: It really doesn't matter whether one knows that Sha is finite, one simply takes the value of Regulator(E)*#Sha(E) and does the computation as if Sha(E)=1. If that doesn't give a point, then one assumes that #Sha(E)=4 and repeats. It generally won't take very many iterations to strip away #Sha(E).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The techniques described in my ANTS-IV paper (arXiv.org/pdf/math/0005139v1.pdf) yield a subexponential-time algorithm. Still, the Heegner-point technique is better in the usual case of rank 1. #Sha can be ignored because it's a square: if #Sha = $n^2$ then Reg*#Sha is the height of $n$ times a generator, so find that point and then saturate to find $n$ and the generator. (This also happens for the Heegner-point technique; see for instance my ANTS-I paper.) $\endgroup$
    – Noam D. Elkies
    Commented Feb 4, 2012 at 18:44
  • $\begingroup$ My comment is not in regards to constructing a search algorithm, but an algorithm mimicking the case of finding a fundamental unit in a real quadratic field. In that case, given $R_Kh_K$, we get the unit in log-polynomial time in the discriminant - much faster than a search algorithm. Thus, it would be interesting to construct an analogue Arakelov theory for elliptic curves. But, as it does in the field case, this would probably prove the finiteness of Sha - not that you need finiteness of Sha for a search algorithm. Hence, it must be hard. $\endgroup$
    – Dror Speiser
    Commented Feb 4, 2012 at 20:20
11
$\begingroup$

Since I cannot (yet) post comments, I'll post this as an answer, even though it is more a comment on Joe Silverman's answer.

Let $H$ be the bound for the multiplicative height (so $H = e^h$ if $h$ is a bound for the logarithmic height) of the point you want to find. Then (as is pointed out in Joe's paper) a naive search on the elliptic curve has a complexity of roughly $H^{3/2}$, whereas his algorithm gives you $H$. On the other hand, searching for the point on a 2-covering can be done in time essentially $H^{1/2}$ (the logarithmic height goes down by a factor of 4), and if I remember correctly, this is what mwrank does. Using $n$-coverings for arbitrary $n$, the complexity drops to $H^{1/((n-1)n)}$, but of course the implied constant grows (there are roughly $n^r$ covering curves to consider when the rank is $r$, and the complexity of the lattice computations also goes up, since one has to use rank-$n$ lattices). In addition, of course, you have to add the time you need to compute the $n$-coverings in the first place, which for $n = p$ a prime usually involves computing class and unit groups of fields of degree about $p^2$. For composite $n$, the complexity tends to be better, though.

The exponent $1/((n-1)n)$ comes from two ingredients: the first is that the logarithmic height of the preimage of your point on the covering curve goes down by a factor of $1/(2n)$. The second is the lattice-based point search method mentioned by Noam Elkies in his comment that gives you a complexity of $B^{2/(n-1)}$ for a search for points up to multiplicative height $B$ on a smooth curve in ${\mathbb P}^{n-1}$. Picking a good value of $n$ should lead to something subexponential; I assume this is what Noam was having in mind (his ANTS IV paper describes a version of the lattice-based point search).

The point I want to make is that descent and searching on coverings usually gives you a faster way of finding points than Joe's method, even without knowledge of the exact canonical height (the height is still useful since it gives you a bound for the search). Tom Fisher has demonstrated that this can be very effective already for relatively small values of $n$ like 6 or 12.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Reading the original question again, one of the assumptions was that there is a rational 2-torsion point. If you use the covering curve coming from 2-isogeny descent, the height goes down by a factor of 2, and so you get a linear search algorithm, which has the same complexity as Joe Silverman's. So I would say the answer to the original question is No. $\endgroup$
    – Michael Stoll
    Commented Feb 5, 2012 at 13:06
  • $\begingroup$ @Michael: Good point. But regarding your added comment, couldn't one use the $L$-series value on both $E$ and its 2-isogenous curve $E'$ in parallel, thereby automatically getting the 2-factor gain, since on one of the curves, the height will be smaller. In any case, I wasn't suggesting that the algorithm in my paper was better (or even as good) as other methods, but I think it does give one answer to the OP's question. Also, if you have a curve where the generator is huge, my algorithm can be used to efficiently show that $E(\mathbb{Z})=\emptyset$, which could be useful. $\endgroup$
    – Joe Silverman
    Commented Feb 5, 2012 at 13:30
  • $\begingroup$ @Joe: I didn't mean to imply that your algorithm was not useful, only that it is not faster when applied to search for a generator. Regarding your suggestion to use both $E$ and $E'$, this will only be faster when the generator of the other curve is the smaller one. $\endgroup$
    – Michael Stoll
    Commented Feb 5, 2012 at 13:56
  • 1
    $\begingroup$ Actually I wasn't going to use descent (though naturally descent helps). Suppose I know $\hat h(P)$ to high precision, and also know in which component $P$ goes modulo each factor $p$ of $\Delta_E$ where $c_p > 1$. Then $\exp \hat h(P)$ is a transcendental homogeneous function of the numerator and denominator of $x(P)$. This lets us find the numerator and denominator in time $\exp \epsilon \hat h(P)$. Unfortunately this requires lattice reduction in dimension $\sim \epsilon^{-2}$, so it is not practical to make $\epsilon$ at all small. $\endgroup$
    – Noam D. Elkies
    Commented Feb 6, 2012 at 0:21
8
$\begingroup$

This paper called "Two $p$-adic $L$-functions and rational points on elliptic curves with supersingular reduction" by Kurihara and Pollack uses another idea than Heegner points, more in the spirit of the question. However rather than taking the real valued height and the real valued $L$-function, they take the $p$-adic version. If $p$ is a prime of supersingular reduction, then there are two of both, which gives more information. In fact one finds the $p$-adic logarithm of a point of infinite order to any desired accuracy by computing the leading terms of the two $p$-adic $L$-functions. To make thing fast, they use overcongergent modular symbols to compute it.

Improve this answer
$\endgroup$
1
  • $\begingroup$ "To make thing fast, they use overcongergent modular symbols to compute it. " I guess it takes time $N^2$ or $N^3$ in the level. They work with twists, to soften this. The classical method can emulate the same idea for twists, as with Elkies (1994), and a paper of Delaunay and Roblot. jtnb.cedram.org/item?id=JTNB_2008__20_3_601_0 $\endgroup$
    – Junkie
    Commented Feb 5, 2012 at 23:32

You must log in to answer this question.

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