# How does one search intelligently for solutions of a Diophantine equation?

Before the proof of Fermat's last theorem, much evidence was accumulated in favor of the conjecture, by using computer searches to prove that a solution would need to have very large values. What are the ideas (if any) behind these computer searches which are not specific to the Fermat curve?

Suppose that we have an irreducible polynomial $f(x_1, \dots, x_n) \in \mathbf Z[x_1, \dots, x_n]$, of large degree, and we want to use a computer to efficiently list all integer solutions of $f(x_1, \dots, x_n) = 0$ in the region $\max(|x_1|, \dots, |x_n|)\leq N$. What is the best way to proceed?

-
This is very close to being undecidable (en.wikipedia.org/wiki/Diophantine_set) so I would be surprised if there was anything you could say with no additional information about $f$. – Qiaochu Yuan May 28 '13 at 20:33
Here is a method to find rational points near a plane curve. Also, the deterministic algorithm of Lehman to factor integers (solutions of $XY-n=0$) can be generalized to other plane curves, although the computations can get pretty nasty for higher degrees. – WimC Aug 7 '13 at 7:47

You ask, what ideas of number theory, if any, can be implemented in order to facilitate the exhaustive computer search for solutions, regardless of any sort of special property of $f$? Good question, Bruno. Qiaochu Yuan is right and I would go a step further to answer in the negative. But if you are willing to expand your question a bit from no conditions on $f(x)$ to allowing $f(x)$ to have the property that the greatest integer of its slope is constant over large intervals, then there is something I can offer from my research that you may not be aware of. And if you are willing to expand your question a bit from ideas of number theory to ideas in complex analysis, then perhaps we can do even more. I expand on this latter approach in the conclusion.

There is a general approach we can use to design Euclidean-like algorithms for finding integer solutions to some types of equations. If over an interval, $f(x)$ is monotone and its domain exceeds its range, then we can narrow the interval for trial and error by finding integer solutions for $f^{−1}(x)$. And if we can do this repeatedly, then we have an algorithm.

Our objective is narrowing the interval for trial-and-error while still preserving the integer solutions. We meet this objective by performing successive iterations on $f(x)$ with the following four steps. First, we round the slope of $f(x)$ to the nearest integer. Depending on the nature of $f(x)$ and the interval, it may not be practical to use regular rounding; we may need to round up or down instead. Therefore, we round the slope of $f(x)$ to $[f'(x) + a]$ where brackets denote greatest integer and $a$ is a pre-determined constant with 0 $≤a<$ 1. Next, we subtract the integer-sloped linear equation, $y'=[f'(x) + a]x$, from $y=f(x)$. This step is only practical if $[f'(x) + a]$ is constant over a large interval. Then, we take the inverse of the difference. We repeat the process until the domain of $x$ is small enough for trial-and-error or this method becomes impractical. Finally, after an integer solution is found, we use back substitution to find the integer solution to the original equation, $y=f(x)$. We call an algorithm that uses this method a Diophantine algorithm because it works by eliminating non-integer solutions to Diophantine equations. Our method guarantees i. the preservation of all integer solutions and the non-preservation of all non-integer solutions and ii. the domain of $y-y'$ over any interval where $[f'(x) + a]$ is constant always exceeds its range.

So, our algorithm is practical for any function over any large interval where $[f'(x) + a]$ is constant. Our algorithm obviously works for linear Diophantine equations because their slope is constant. Our algorithm obviously works for Pell-like equations of the form $x^2−ny^2=s$ where |$s$| is small because they are asymptotically linear. It is less obvious that we could engineer a Diophantine algorithm for the circle equation, $𝑥^2+𝑦^2=n$, but we did. Although the slope of the circle equation diverges as $x^2$ approaches $n$, $[f'(x) + a]$ is constant over large intervals. The bad news is that for large $n$, we have to break the interval into subintervals and those subintervals into smaller subintervals with each iteration. The good news is that with each iteration, we can cut the size of most of the intervals for $x$ not by half, but into sevenths and eighths! And since we end up with a semicircle equation after each reduction, we can reduce the size of the intervals again and again! So, our algorithm works considerably better than Cornacchia’s algorithm when $n$ is the product of large primes.

What I typed above is a summary of my results. If you are interested, you can learn more about it on my site, www.greatestintegerfunctionresearch.org. I am also looking to collaborate with someone to determine if we can solve some Diophantine equations using residues. This approach requires combining expressions for integer solutions (such as sums of expressions involving $f(x)$ and the greatest integer function) with an alternative mathematical expression for the greatest integer function to create a holomorphic function. See Chapter 5 in my pdf on the Full-Text page.

-
Looks like a lot of your formatting got corrupted some how. Regards – Amzoti Aug 7 '13 at 6:25
Hi Ken, it appears to me that maybe you edited the answer somewhere else and copy-and-pasted it into the answer box here? Many of the mathematical expressions in your answer are "as-is" instead of being displayed by MathJax, this has the disadvantage that your answer is only viewable by those users with the appropriate fonts installed. For others (such as user Amzoti who commented above) it would display like gibberish. I hope I can convince you to replace mathematical statements like 𝑦 = 𝑓(𝑥) by their mathjax counterparts like $y = f(x)$. – Willie Wong Aug 7 '13 at 7:27
For more information on how to make use of our built-in MathJax support, see this meta item. – Willie Wong Aug 7 '13 at 7:28