2
$\begingroup$

We found and implemented algorithm which finds integral points of infinite order $P=(X_1,Y_1)$ and $nP=(X_2,Y_2),n>1$ on an elliptic curve $E : y^2=x^3+a_4 x + a_6$.

Let $X(x)/Z(x)$ be the $X$ coordinate of the multiplication by $n$ map on $E$. $X,Z$ are polynomials in $x$.

By the integrality of $P,n P$ we have $X_2=X(X_1)/Z(X_1)$ and $Z(X_1) \mid X(X_1) \iff \gcd(Z(X_1),X(X_1))=Z(X_1)$.

Let $r$ be the resultant of $X$ and $Z$. The gcd of $X(x),Z(x)$ at integers is divisor of $r$. For all divisors $d$ of $r$, check if the root of $Z(x)=d$ is $X_1$ and it is on the curve.

So this algorithm finds all integral pairs $P,n P$ on $E$.

The complexity is the maximum of factoring the resultant and iterating over its divisors.

Scaling rationals to integers: If $(x/u,y/u)$ is on $E$, then this give rise to integral point on $y^2=x^3 + a_4 u^4 x + a_6 u^6$.

Over the rationals, assume $P=(x_1/z_1,y_1/z_1)$ is rational point and $2P=(x_2/z_2,y_2/z_2)$. If we guess a multiple of $z_1 z_2$ : $u= C z_1 z_2$, work on the isomorphic curve $E'=x^3+a_4 x u^4 + a_6 u^6$. $E'$ will have the integral points $P'=(u^2 x_1,u^3 y_1)$ and $2P'=(u^2 x_2,u^3 y_2)$. The algorithm will find the integral points $(X_1,Y_1)$,$(X_2,Y_2)$ on $E'$ and this will find rational points on $E$,$(X_1/u^2,Y_1/u^3)$ and $(X_2/u^2,Y_2/u^3)$. Observe that we need not know $z_1,z_2$, just a multiple of their product.

So the algorithm finds rational points of infinite order at the cost of guessing multiple of $z_1 z_2$ and this is efficient if $z_1 z_2$ is smooth, i.e. product of small primes.

Q1 Is this algorithm known?

We get experimental support, e.g.:

sage: k0=57;E=EllipticCurve(QQ,[0,k0^3]);pts=jorointegral1(E);pts
(-38 : 361 : 1), (112 : 1261 : 1), (456 : 9747 : 1)]

Comment claims that curves for which the algorithm works are rare. We believe this is not true, because for all $E$ of positive rank, there exists isomorphic $E'$ with $P,nP$ integral of infinite order. This can be used if the denominators $z,z_2$ are smooth.

Improve this question
$\endgroup$
6
  • $\begingroup$ I fear it is rather rare to find an $n>1$ and $P$ such that $P$ and $nP$ are integral points of infinite order on an elliptic curve. Torsion points can be found easier than that. Also $r$ is linked to the discriminant of $E$, in fact the method for $n=2$ is what is used in the proof of the theorem of Lutz-Nagell. $\endgroup$
    – Chris Wuthrich
    Commented Jun 17, 2021 at 14:51
  • $\begingroup$ @ChrisWuthrich No, it is not rare for points of infinite order. I edited with example. $\endgroup$
    – joro
    Commented Jun 17, 2021 at 15:21
  • $\begingroup$ @ChrisWuthrich By scaling rationals to integers, for all E there is isomorphic E' with two integral point P,nP. This can be used if the denominators are smooth. $\endgroup$
    – joro
    Commented Jun 17, 2021 at 15:36
  • $\begingroup$ @joro When dealing with average questions for elliptic curves over $\mathbb{Q}$, it is standard to represent them by equations $y^2=x^3+Ax+B$ which are quasi-minimal, i.e. $p^4 | A \Rightarrow p^6 \nmid B$ (such an equation is unique). Then you order them by naïve height and try to compute the density. It seems that what you are doing is counting equations, not elliptic curves. $\endgroup$
    – François Brunault
    Commented Jun 17, 2021 at 17:17
  • $\begingroup$ @joro Sure you can rescale the equation to make any pair of points integral. But then there is no point in your algorithm as you'll know the answer already. For a given, say quasi-minimal equation the set of $n>1$ with integral points $P$ and $nP$ is small if not empty. $\endgroup$
    – Chris Wuthrich
    Commented Jun 17, 2021 at 19:16

2 Answers 2

Reset to default
4
$\begingroup$

Rational points which are hard to find are those of large height, and in particular large denominator. This method will only find rational points with denominator u when you scale the equations by u, which requires knowing u in advance or looping over all possible u. Try this curve: https://www.lmfdb.org/EllipticCurve/Q/294504803/d/1

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, I didn't claim the algorithm is universal. And many thanks for making mwrank open source. $\endgroup$
    – joro
    Commented Jun 18, 2021 at 11:09
3
$\begingroup$

For what it's worth, it should not be possible to make $P$ and $nP$ integral on a quasi-minimal equation if $n$ is very large. More precisely, the following theorem holds. It quantifies what Chris Wuthrich said in the comments.

Theorem: If Lang's height conjecture is true (or if the $ABC$-conjecture is true), then there is an absolute constant $C$ such if $E/\mathbb Q$ is an elliptic curve given by a quasi-minimal Weierstrass equation, $$ E: y^2 = x^3 + Ax + B,\quad \text{$A,B\in\mathbb Z$, $\gcd(A^3,B^2)$ 12th power free,} $$ and if $P\in E(\mathbb Q)$ is a point of infinite order, then $$ P\in E(\mathbb Z) \quad\text{and}\quad nP \in E(\mathbb Z) \quad\Longrightarrow\quad n \le C. $$

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks. I suppose you assume infinite order of the point. $\endgroup$
    – joro
    Commented Jun 18, 2021 at 11:32
  • $\begingroup$ @joro Yes, infinite order. Clearly trivially false otherwise! I edited the answer. $\endgroup$
    – Joe Silverman
    Commented Jun 18, 2021 at 11:48
  • $\begingroup$ Your constraints on A,B are exactly the opposite of what I do on purpose. Large gcd of A,B on E' helps me to find rational point on the minimal model E with large denominator. $\endgroup$
    – joro
    Commented Jun 18, 2021 at 14:44
  • $\begingroup$ If you want to use non-minimal models, then it's easy (as you've indicated) to get $P$ and $nP$ integral for an arbitrarily large $n$ simply by clearing denominators. This can be done quantitatively in the sense that the denominator of $nP$ grows roughly like $\exp(n^2\hat h(P))$, so the number of digits grows quadratically with $n$. More generally, if $P_1,\ldots,P_r\in E(\mathbb Q)$ are independent points, then one can ask for the smallest $D$ that clears all of their denominators. This is in the literature, but in any case not hard to do using canonical heights. $\endgroup$
    – Joe Silverman
    Commented Jun 18, 2021 at 15:53

You must log in to answer this question.

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