Effective way of finding generators on the curve and the rank conjecture - MathOverflow

Effective way of finding generators on the curve and the rank conjecture

2012-06-27T17:49:11Z

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 ? .

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.
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.

Answer by Timo Keller for Effective way of finding generators on the curve and the rank conjecture

2012-06-27T18:08:11Z

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:

$\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.
$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.

Answer by Jesper Petersen for Effective way of finding generators on the curve and the rank conjecture

2012-06-28T06:46:17Z

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$.

Answer by Joe Silverman for Effective way of finding generators on the curve and the rank conjecture

2012-06-28T15:21:50Z

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.