Reverse engineering a Diophantine equation Recently, due to the help I had with another question, I was able to find a Diophantine equation of degree in four variables which is the condition to be able to construct a "rational" dodecahedron. It was a lot of work, and led to some interesting questions and results. But it got me thinking, is there a way to "cheat" at this?
What I mean here is: Say you have some points that you know satisfy a certain condition, but the algebra to get to a single equation for them is intractable. Is there a way, given those points that you already know, to construct a Diophantine equation for them? I don't just want any random Diophantine equation, I want one that is elegant enough that it is probably the "right" one. You could easily take a product over all terms $(x-x_1)^2+(y-y_1)^2+...$ so that it trivially goes through the given points.
Is it tractable, for example, to go through all possible homogeneous Diophantine equations of small (up to 5, say) degree, such that all terms have a coefficient of 0, 1, or -1, and check if some given points are on that curve? I imagine modular constraints would reduce the number of possibilities, and potentially even turn it into a linear algebra problem.
Has this been done? Can it feasibly be done?
 A: It can't be done. By the MRDP Theorem, diophantine sets are the same as c.e. (or Turing Recognizable) sets, and therefore the problem of determining whether two diophantine equations $\varphi, \hat\varphi$ have the same set of solutions is not computable.
This is to say that your algorithmic idea of, given a diophantine equation $\varphi$, to

*

*iterate through the set of "simple" diophantine equations $\hat\varphi\in S$ (for some notion of simplicity), and then


*check if $\varphi = \hat\varphi$ have the same set of solutions.
Cannot work.
No such check $=$ can be computable, as it would immediately allow one to solve the halting problem.
Your proposed check will admit "false positives", for example it will say that any diophantine equation has the same solution set as the equation $\varphi(x_1,\dots,x_n) = 0$.
While one could try to design more clever tests, they cannot escape the above argument.
Any (computable) test cannot be correct on all inputs, by reduction to the halting problem.
