# Undecidable how many rational points?

Is it known to be undecidable to determine whether there are a finite number or an infinite number of rational points on an algebraic curve with rational coefficients? I know this is resolved for all but degree-3 curves (degree $\ge 4$: Falting's Theorem), and that it is an unsolved problem to distinguish between finite/infinite number of rational points for a given degree-3 curve. What I am asking is if it has been proven to be formally undecidable to answer this question, or it is possible that there exists a decision procedure?

This is well-known in the right circles; I just don't know myself. Thanks for educating me!

-
AFAIK this is open. See Poonen's survey Computing rational points on curves. My reading of the paper is that the problem is expected to be decidable. Also, where did you read that the problem is resolved for all but degree-$3$ curves? I don't think that's known, and if it is known, I would be very interested to see a reference! – Qiaochu Yuan Aug 5 '11 at 15:47
@Qiaochu: What I meant is that it is easy for linear and quadratic curves, and Falting's Theorem settles it for all degrees $d > 3$ (only a finite number). Ah, so I shouldn't have said it is determined "how many": It is determined whether infinite or finite. I will alter the question. Thanks! – Joseph O'Rourke Aug 5 '11 at 16:34
Also, distinctions based on degree are not quite accurate (for example because of reducibility). The relevant distinction is really genus; as you say, for the finiteness problem it is settled for $g \ge 2$ by Faltings' theorem and $g = 0$ by classical arguments. For $g = 1$ this is the question of computing the rank of an elliptic curve (if the curve has any rational points; otherwise it's the problem of deciding whether it has rational points). I think this is decidable conditional on certain big conjectures (BSD?). – Qiaochu Yuan Aug 5 '11 at 16:48

As you say, the open case (for determining whether there are a finite or infinite number of rational points) is the case of genus $1$. (If you are restricting to smooth curves in the projective plane, then these are smooth plane cubics.)

This is expected to be decidable. Indeed, the procedure is known; what is currently unproved is that the procedure does what it is conjectured to do.

Firstly, one has to determine if the genus one curve has any rational point at all. One can first check this locally (i.e. over $\mathbb R$ and all $\mathbb Q_p$); if there are no points over one the completions of $\mathbb Q$, then there are certainly no rational points. In practice, checking this is a matter of solving congruences and applying Hensel's lemma (and staring at a graph, in the case of $\mathbb R$-points), and hence is effective.

If the curve has points over every completion, it lies in the Shafarevic--Tate group of its Jacobian, and determining whether it is the trivial element or not is equivalent to determining if the curve has at least one rational point. The Shafarevic --Tate group is conjectured to be finite, and if it is, it is effectively computable by infinite descent; so this should also be effective.

Finally, suppose that your genus one curve has a rational point. It is then an elliptic curve, and the Birch--Swinnterton-Dyer conjecture gives a (conjectural) criterion for whether it has finite or infinitely many points. One has to check whether the $L$-function of your elliptic curve is non-zero at $s=1$ or not. Determining whether a holomorphic function vanishes at a point or not is not necessarily effective in general, but in this case, it turns out (thanks to the modularity theorem of Wiles, and the method of modular symbols) that computing the value of the $L$-function at $s = 1$ is effective. (It becomes a combinatorial problem, rather than a true problem in analysis.)

Actually, assuming finiteness of the Shafarevic--Tate group, one can also solve the question of finite/infinite number of points by infinite descent as well; there is no need to use the connection with modular forms or the Birch--Swinnerton-Dyer conjecture. (I just have a fondness for the latter, which is why it came to mind first.)

In practice, the algorithm by infinite descent I've outlined (incorporating BSD or not, depending on your inclinations) should work for any given genus $1$ curve; if it doesn't, you will have found a counterexample to (at least) one of two conjectures that are both expected to be true: the Shafarevic--Tate conjecture and/or the Birch--Swinnerton-Dyer conjecture! I imagine that some form of this algorithm is implemented in modern computer algebra languages.

-
Thank you, Matt, this is very clear! And a very interesting situation, that "algorithms" are likely implemented, they terminate, but it is not proven that they must always terminate. – Joseph O'Rourke Aug 5 '11 at 23:53
@Joseph: Dear Joseph, You're welcome. The description in your comment summarizes the situation perfectly: implemented (and practical!) algorithms that are not proven to terminate in general. This is one of the challenges, and appeals, of the subject! Best wishes, – Matt E Aug 6 '11 at 2:08