Finding a rational point of large height on an elliptic curve knowing a real approximation

Question

Let $y^2=x(x^2+n)$ be an elliptic curve with $n\in\Bbb Z$ (the same question can of course be asked for a general e.c). I know (e.g. it has rank 1) that there exists a nontrivial rational point $(r,s)$ with $r=p/q$, probably of large height. On the other hand I have an algorithm (Heegner, Monsky,...) which can give me a real approximation $\alpha$ to $r$ to any accuracy I want. Is there any nontrivial way to search for $r$ ? The method I use for now is to compute the convergents $p_n/q_n$ of the continued fraction of $\alpha$ and test if it is on the e.c. If not, I increase the accuracy until it succeeds. It will of course eventually succeed, but in practice I need a much higher accuracy than the height of $r$ would suggest, typically 4 times or 8 times more.

Answer 1

This answer does the same, best approximations using rationals, but with a small intermezzo that shows in the particular tested cases the difference.

The best rational approximation is done not for $x$, knowing that $x\approx \xi$, but for the number $r$ from the representation $x=ar^2$, which is $r\approx \rho:=\sqrt{\xi/a}$. Here, $a$ runs in a finite set of possible representatives of $x$ modulo squares. (My notations differ.)

I have no theoretical support, so some sample cases are used to support the idea. (In some cases it may be possible to have a slightly less precision for $\xi$, and use the fact that $y$, approximated by $\eta=\sqrt{\xi(\xi^2+n)}$ should have a continued fraction convergent with denominator matching the one for $x$. But this is hard to implement, and does not work properly.)

Below, the precision is always seen when the variable $\xi$ (in code xi) is declared. Signs of the sample $x$-solutions are always positive, the code has to be slightly adapted to cover a possible negative sign of $x$ for a rational point $(x,y)$ on some elliptic curve $y^2 = x^3 + nx$.

---

---

---

Sample A: Let $n$ be the prime $197$, so our curve $E$ is given by the affine equation $y^2 =x^3 +197x$. There is a solution near $\xi = 6.494774703141405$, assume we have this information. There is a morphism $\delta:E(\Bbb Q)\to(\Bbb Q^\times$ modulo $\square$s$)$ which generically maps $(x,y)$ to $x$ modulo squares, its image is contained in the group with generators $-1,2,197$. For each of possible representatives $a$ of $x$ modulo squares (of same sign as $x$) we build $$ \rho = \sqrt{\frac \xi a}\ , \qquad \text{ then approximate $\rho$ with a rational $r$.} $$ Finally, we check if $x=ar^2$ lifts to a solution.

---

---

The sage code...

R = RealField(60)
n, xi = 197, R(6.494774703141405)

def find_point(n, xi, verbose=False):
    E = EllipticCurve(QQ, [n, 0])
    for a in (2*n).divisors():
        rho = sqrt(xi/a)
        for r in continued_fraction(rho).convergents():
            x = a*r^2
            if verbose:    print(a, r)
            if r != 0 and (a * (x*x + n)).is_square():
                P = E.lift_x( x )
                return P

find_point(n, xi)

This seem to work, and gives the point: $$ P = \left(\frac{47995604297578081}{7389879786648100}, -\frac{25038161802544048018837479}{635266655830129794121000}\right) \ . $$ We compare the magnitudes of the denominator of $x$, and of the used approximation by writing the values over each other: $$ \begin{aligned} x &= \frac{47995604297578081}{7389879786648100} \color{gray}{= \frac {109^{2} \cdot 223^{2} \cdot 9013^{2}} {2^{2} \cdot 5^{2} \cdot 7^{2} \cdot 17^{2} \cdot 29^{2} \cdot 47^{2} \cdot 53^{2}} } \\ &\approx \color{blue}{6.4947747031414047}301383334836290591\dots\ ,\\ \xi &= \color{blue}{6.4947747031414050}000000000000000000\ . \end{aligned} $$

---

Sample B: $n=1277$. We need a better precision, and start with $\xi = 93.7629105759621700670831627$. The start is done with:

R = RealField(100)
n, xi = 1277, R(93.7629105759621700670831627)
find_point(n, xi)

Then code finds the solution:

$$ \begin{aligned} x &= \frac{50090527750035893502167612761}{534225392986867374876816100} \color{gray}{= \frac {11^{2} \cdot 8543^{2} \cdot 2381632303^{2}} {2^{2} \cdot 5^{2} \cdot 504853^{2} \cdot 4578227^{2}} } \\ &\approx \color{blue} {93.762910575962170067083162695}666722792457650549379705668240\dots\ ,\\ \xi &= \color{blue} {93.762910575962170067083162700}000000000000000000000000000000\ . \end{aligned} $$

---

Sample C: $n=1700300$. We start with $\xi=2179.8360436968835516943093501472067923$:

R = RealField(125)
n, xi = 1700300, R(2179.8360436968835516943093501472067923)
find_point(n, xi)

The code finds the solution: $$ \begin{aligned} x &= \frac {6274394838762261393980197814359561450849} {2878379251001478297154242295070280964} \color{gray}{\tiny= \frac {7^{4} \cdot 7804283^{2} \cdot 207136595021^{2}} {2^{2} \cdot 29^{2} \cdot 43^{2} \cdot 67^{2} \cdot 71^{2} \cdot 109^{2} \cdot 1311951889^{2}} } \\ &\approx \color{blue} {2179.8360436968835516943093501472067922940}849889502932541523877631102154\dots\ ,\\ \xi &= \color{blue} {2179.8360436968835516943093501472067923000} 000000000000000000000000000000\ . \end{aligned} $$

---

Sample D: $n=3061$. We start with $\xi=35.0477718823448047530199139542339815092054$:

R = RealField(150)
n, xi = 3061, R(35.0477718823448047530199139542339815092054)
find_point(n, xi)

Then the code finds a solution, and the above precision cannot be relaxed: $$ \begin{aligned} x & \small= \frac {14259353034304888243978589290138373108987041}{406854766179529620199411732138817244288900} \\ & \color{gray}{=\tiny \frac {23^{2} \cdot 1559^{2} \cdot 21184217^{2} \cdot 4971226409^{2}} {2^{2} \cdot 3^{2} \cdot 5^{2} \cdot 61^{2} \cdot 157^{2} \cdot 349^{2} \cdot 541^{2} \cdot 1831^{2} \cdot 6421817^{2}} } \\ &\small\approx \color{blue} {35.04777188234480475301991395423398150920538}6292854252284936219136931760974546341489\dots\ ,\\ \xi &\small= \color{blue} {35.04777188234480475301991395423398150920540}0000000000000000000000000000000000000000\ . \end{aligned} $$

---

Sample E: In all above cases the $x$-component of the point was in fact a square. To have also some other case, let us consider $n=3746$. We start with $\xi=7.255279$:

R = RealField(40)
n, xi = 3746, R(7.2552789)

Then the same function finds a point which is $2$ modulo squares:

sage: R = RealField(40)
....: n, xi = 3746, R(7.2552789)
sage: P = find_point(n, xi)
sage: P
(704926152/97160449 : -158992024694580/957710545793 : 1)

sage: Px, Py = P.xy()
sage: Px, Px.factor()
(704926152/97160449, 2^3 * 3^4 * 7^2 * 149^2 * 9857^-2)

---

Sample F: A further example with a non-square $x$-component:

n, xi = 14492, RealField(70)(18.3899710051410135335)
P = find_point(n, xi)

and this found point has denominator in the same range of needed digits as xi:

sage: Px, Py = P.xy()
sage: Px
5083900261326529542050/276449607229141273249
sage: Px.factor()
2 * 5^2 * 7^-2 * 23^-2 * 47^2 * 103271887^-2 * 214543643^2

sage: Px.denominator()
276449607229141273249
sage: xi
18.389971005141013533

---

Sample G: I tried to find a more challenging example, where precision may count, the $n$-value is $14767$.

n = 14767
xi = RealField(175)(14.86592759619710763308278393798328876824092580458913)
P = find_point(n, xi)

The point is found, and the above longer approximation $\xi$ is needed.

$$ \begin{aligned} x & \small= \frac {2907850750824590835169955596905618580505518572626689} {195605066149283267608501070605879062874453544132025}\\ & \color{gray}{=\tiny \frac {103^{2} \cdot 709^{2} \cdot 2411^{2} \cdot 346849^{2} \cdot 883008611489^{2}} {3^{4} \cdot 5^{2} \cdot 7^{2} \cdot 11^{2} \cdot 241^{2} \cdot 647618297^{2} \cdot 25861318181^{2}} } \\ &\small\approx \color{blue} {14.865927596197107633082783937983288768240925804589129}666570851467692157\dots\ ,\\ \xi &\small= \color{blue} {14.865927596197107633082783937983288768240925804589130} 000000000000000000\ . \end{aligned} $$