Methods of finding integer solutions beyond the reach of direct search

Question

Consider a classical problem: given a polynomial Diophantine equation $P(x_1,\dots,x_n)=0$, determine whether it has an integer solution. While this problem is undecidable in general, we may still hope to resolve it for restricted families of equations, e.g. for all two-variable equations or all cubic equations.

If $P=0$ has small solutions, one of them can be found by direct search. If there are no solutions, there are many methods which we may try to prove this, see e.g [1, Chapter 7]. A patricularly challenging case when solutions exist but the smallest one is beyond the reach of direct search, e.g. all variables have over 100 digits. Then direct search returns no results, and all methods for proving non-existence of solutions must nessesary fail.

I know only very few methods for finding such huge solutions, specifically:

• If $P$ is a quadratic two-variable equation, we can reduce it to Pell equation and then its fundamental solution can be found by continuing fraction method in time polynomial in the number of digits.

• If $P$ is a homogeneous three-variable equation defining an elliptic curve, then it has trivial solution $(0,0,0)$, but if we ask for positive integer solutions, the smallest one can be huge but easy to find by first computing the rank and set of generators of the elliptic curve. For an example, see Estimating the size of solutions of a diophantine equation (which is the highest-voted question with Diophantine equations tag in the Mathoverflow history)

• If the equation is of the form $y^2+kxyz+P(x)=0$, where $P$ is a monic polynomial with free term $1$ in absolute value, then there are recursive formulas presented by Denis Shatrov for generating solutions to $y^2+xyt+P(x)=0$, and we can try to generate solutions until we find one with $t$ divisible by $k$. For an example, see the answer to Can $9xy$ divide $1+x^2+x^3+y^2$? (which is the highest-voted answer I ever gave). Update 20.10.2024. Soon after asking the question, I have learned about reference [2] that describes how to generate infinitely many integer solutions to many equations of the form $xyz=P(x,y)$. By generating such solutions and looking for those one divisible by $k$, one may find huge solutions to many equations of the form $kxyz=P(x,y)$. Family $y^2+kxyz+P(x)=0$ with monic $P$ and free term $\pm 1$ described above is a very special case of this.

So, what are the other methods for finding integer solutions to the Diophantine equations for which the smallest solutions are huge? Also, what other families of equations can be resolved by (modifications of) the described three methods?

(A remark: I am not asking for methods how to speed up direct search to be able to search for solutions in $15-20$ digits, which was done e.g. for equation $x^3+y^3+z^3=33$. I am asking for methods fundamentaly different from direct seach, able to easy produce, say, $100$-digit solutions).

[1] B. Grechuk. Polynomial Diophantine Equations: A Systematic Approach. Springer International Publishing, 2024. URL https://books.google.co.uk/books?id=rj8eEQAAQBAJ.

[2] Schinzel, A., On the congruence (f(x)+g(y)+c\equiv 0\pmod{xy}) (completion of Mordell’s proof), Acta Arith. 167, No. 4, 347-374 (2015). ZBL1371.11006.

Answer 1

You say that for elliptic curves, "the smallest [integer point] can be huge but easy to find by first computing the rank and set of generators of the elliptic curve." But you do not consider the possiblity that explicitly finding generators for the Mordell-Weil group may be difficult. Indeed, conjecturally on a "random" elliptic curve $y^2=x^3+Ax+B$ of rank at least $1$ (where $A,B\in\mathbb Z$ and $\gcd(A^3,B^2)$ is $12$th power free), the logarithmic height of the smallest non-torsion point is exponential in $\max\{|A|^3,|B|^2\}$, and thus may be infeasible to write down. In the positive direction, there's Zagier's observation that in the rank $1$ case, one may be able to use the theory of Heegner points.