5
$\begingroup$

Hello everyone,

I have never heard of a polynomial time running algorithm that finds the generators of elliptic curves efficiently. I do know that Nagell-Lutz theorem is useful in computing the torsion part in $$E(\mathbb{Q})=\mathbb{Z}^{\phi} \oplus E_{\rm{Torsion }}(Q).$$ So what about the count of $\phi$ and the effective generation of points.

I do know 2-descent , that doesn't not work perfectly always. Regarding the 3-descent , only some curves having CM are said to pass through it. But are there any latest advancements in the area of computing the generators of the curve, if so please give some references.

I also read the rank conjecture, for expressing the rank of the underlying abelian group $E(\mathbb{Q})$ in terms of the order of vanishing of the taylor expansion of associated $L$-function. So I again got stuck.

Why do one go for a rank, if one has a point that has infinite order ? .

  1. Rank 1-curves usually mean that they have a point of infinite order on them that can be used to generate all other points by successive chord and tangent methods.

  2. Rank 2- Curves have 2 such points of infinite order that can be used to generate all other points.

So my question is why should one bother about $n$ points ( of infinite order ) if we have one point of infinite order. To express an analogous statement, suppose think that you are given a secret map that will lead you to some treasure. After the hard journey, you at-last said " Eureka" and you have found a " Machine X" . Its written on the Machine X, that it will produce dollar notes, as many as you want. So its limit is infinity. You can extract infinite number of dollar notes from the machine. You took that machine and packed it and again saw the secret-map. There are in fact some other markings on the map that will lead you to a place that contains the same Machine X.

Do you again go to those places searching for another Machine-X if you have a Machine-X that will produce infinite amount of money. I think the analogy is clear. So if we already have a point that produces infinite points why to again bother about other points that give rise to infinite points.

So if I am right, does the task of finding $\phi$ number of generators reduce to the task of finding one generator ? . That will make the above equation look like this $$E(\mathbb{Q})=\mathbb{Z} \oplus E_{\rm{Torsion }}(Q).$$

( Which is nothing but the Rank-1 situation ).

Thank you.

$\endgroup$
6
  • $\begingroup$ I am new to the field of elliptic-curves and the associated mathematics. I know number theory, but not elliptic-curve kind of mathematics apart from cryptography. $\endgroup$ Jun 27, 2012 at 17:56
  • 3
    $\begingroup$ There is currently no known method (except exhaustive search) for finding a single point of infinite order on an elliptic curve of rank $\geq 2$. That being said, I don't see why what you write reduces to the task of finding one point of infinite order. $\endgroup$ Jun 27, 2012 at 18:58
  • $\begingroup$ I didn't mean that Francois. I said if my understanding is correct then it will be the case. But the answer by Jesper ( below ) showed that its not the case. Anyway thank you. But I think B.J.Poonen and M.Stoll have some methods in showing that. $\endgroup$ Jun 28, 2012 at 8:56
  • $\begingroup$ Small comment about the torsion part, if it interests you, Nagell-Lutz is not very efficient. Instead, once can use the classification of possible torsion over the rationals by Mazur, and this reduces finding torsion to solving a few polynomials over the rationals, which can be done efficiently, say, using the LLL algorithm. $\endgroup$ Jun 29, 2012 at 10:35
  • $\begingroup$ Oh.. Thank you @DrorSpeiser . I am now in a dilemma to choose which one is the best answer among the three given. All the 3 of them are great. Is there any way of choosing all the three answers ? $\endgroup$ Jun 29, 2012 at 10:53

3 Answers 3

1
$\begingroup$

I am not sure I am understanding correctly what you are asking for, but if (1) $\mathrm{ord}_{s=1}L(E/K,s) = \mathrm{rk}E(K)$ is known or (2) if the Tate-Shafarevich group $III(E/K)$ is finite, there is an algorithm for calculating the Mordell-Weil group $E(K)$ of an elliptic curve $E$ over a number field $K$. Ask if I shall give you more details.

Edit:

For calculating the torsion, use that $E(K)[m] \hookrightarrow \tilde{E}(k_v)$ for $(v,m) = 1$ and $v$ a place of good reduction.

For calculating the rank:

  1. $\mathrm{ord}_{s=1}L(E/K,s) = \mathrm{rk}E(K)$: There is an algorithm which computes $L^{(n)}(E/K,1)$ up to an arbitrary precision, so one can check if it does not vanish (one can not determine if it is equal to $0$. Now the algorithm is as follows: Search in parallel for a non-torsion point and calculate $L(E/K,1)$. If you find a point, move on to $L^{(2)}(E/K,1)$; else you will find after a finite time that $L(E/K,1) \neq 0$. Repeat.

  2. $III(E/K) = H^1(\mathcal{O}_K, \mathcal{E})$, $\mathcal{E}$ the Néron model of $E/K$, is finite: This is motivated by the analogy with the (finite) class group $H^1(\mathcal{O}_K, \mathbf{G}_m)$. See http://jmilne.org/math/Books/ectext0.pdf p. 126 for the algorithm.

$\endgroup$
2
  • $\begingroup$ +1 , oh, I didn't understand how can one connect algebraic version to an analytic version. In the (1) L.H.S is an analytic one and R.H.S is an algebraic one. But this may be an interplay between analytic number theory and algebraic number theory. But the Sha group is the kernel of some $H^1$ groups. So if we can show that there are finite number of elements that map to trivial element on the other side of map its done. But why should I believe in such Local-Global lift, for at-least degree curves. $\endgroup$ Jun 28, 2012 at 7:42
  • $\begingroup$ Please see this $\endgroup$ Jun 28, 2012 at 7:42
6
$\begingroup$

We do not currently know an effective algorithm to compute the rank of an elliptic curve or to compute generators for its Mordell-Weil group. One can "do descents by day and search for points by night", and in practice, the process will stop. BTW, people do 3 and 4 (and maybe even 5) descents these days, and they're not restricted to CM curves. Finally, I'll mention that if $E(\mathbb{Q})$ has rank 1, then one can use Heegner points to find a rational point of infinite order, or one can use the value of $L'(E,1)$ (sort of as described in Keller's answer) to do a very efficient search. (This last algorithm is in a paper of mine). However, neither method is practical if the conductor $N$ of the curve is too large. Roughly, for both methods one needs to compute the value of a series that doesn't begin to converge until you take $O(\sqrt{N})$ terms.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you Joe. But I am wondered are you the same Joseph Silverman who wrote the Bible " Arithmetic of Elliptic curves " ?. My God, at the beginning I didn't believe that. But after verifying your MO account I came to know that. But I am very honored that you have answered my question in a standard manner. I thought that MO is a normal community but never expected that Big-shots in mathematics are present here. I generally see people keeping the same name of Big-Shot and try to imitate them in online blogs. But this is not the case here. Thank you again. $\endgroup$ Jun 28, 2012 at 16:54
  • $\begingroup$ @Shanmukha Srinivasan: I certainly don't consider myself a "big shot". But in any case, quite a few established mathematicians use MO. For example, Tao, Poonen, Elkies, Ellenberg (under JSE), Voloch, to name just a few top people who work in number theory and post on MO. $\endgroup$ Jun 28, 2012 at 17:49
2
$\begingroup$

Your question seems to suggest that you think that one point of infinite order is enough to generate the full set of solutions of a given curve. This is not always the case. If a curve has rank $n$ then exactly $n$ points of infinite order is needed to generate the full group.

Think of a curve of rank, say, $3$. The full group is isomorphic to $\mathbb{Z}^3$, yet none of the points corresponding to $(\pm1,0,0)$, $(0,\pm1,0)$ or $(0,0,\pm1)$ all of infinite order can generate $\mathbb{Z}^3$.

$\endgroup$
4
  • $\begingroup$ Oh this is what I was exactly asking for. Thank you Jesper for your clarification !!. $\endgroup$ Jun 28, 2012 at 7:33
  • 1
    $\begingroup$ Well there's yet another problem. Even if you had a rank one elliptic curve, where there is a "good method" for finding a point of infinite order, the subgroup generated by that point might not consist of all points of infinite order. This is to say, that the subgroup might have finite index in the whole Mordell-Weil group. $\endgroup$
    – stankewicz
    Jun 28, 2012 at 21:53
  • $\begingroup$ Oh.. My doubt got clarified now .. Cheers .. @stankewicz $\endgroup$ Jun 29, 2012 at 10:54
  • $\begingroup$ @stankewicz: This "saturation" problem is solved for elliptic curves over number fields in M. Prickett's thesis. Given a point you can use geometry of numbers to bound the index by some integer N, and then for those primes p < N, you can check wether your points are divisible by p. etheses.nottingham.ac.uk/52/1/thesis.pdf $\endgroup$ Jul 20, 2012 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.