1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Sounds like a variation of the method of undetermined coefficients. $\endgroup$
    – Max Alekseyev
    Commented Jun 19, 2022 at 2:34
  • $\begingroup$ It is not always rational to reduce all this to one equation. Because the degree of the equation will grow. It is necessary to simplify the method of creating a system of equations. And in some cases the system can be solved. First you need to understand how the system is built? $\endgroup$
    – individ
    Commented Jun 19, 2022 at 4:41

1 Answer 1

Reset to default
1
$\begingroup$

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

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

  2. 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Huh. So the problem as a whole is unsolvable. What if I'm not too concerned about "false positives", and my set of points was of some finite size (like 3 for example)? There seem to be only finitely many Diophantine equations of a given degree and "height" (maximum absolute value of a coefficient). Could one not cleverly iterate through those, weeding out most with modular restrictions, and find one that works? Also, the MRDP Theorem seems to only apply when there are either very high degree equations or many variables. If one restricted both of those, could it be done? $\endgroup$
    – Thomas Blok
    Commented Jun 19, 2022 at 1:27
  • $\begingroup$ Also, I'm not stating that the set of solutions are the only solutions. I'm trying to find a Diophantine equation so that I can generate more points. This seems like a finite process for a given degree and height $\endgroup$
    – Thomas Blok
    Commented Jun 19, 2022 at 1:29
  • 1
    $\begingroup$ @ThomasBlok if you're not too concerned about false positives, you can constantly return $\varphi(x_1,\dots,x_n) = 0$ (or something else like that). As this likely isn't interesting, you probably are somewhat concerned about false positives. It is possible in the low-degree/variables setting things become computable (for example, NP Complete Decision Problems for Binary Quadratics suggests the problem to be exp-time solvable under suitable degree/variable restrictions). $\endgroup$
    – Mark Schultz-Wu
    Commented Jun 19, 2022 at 2:06
  • $\begingroup$ @ThomasBlok If you solely want to find all diophantine equations that, for a set $S$ is small, is constantly zero on $S$, this is of course computable. It will include "boring" equations such as $\varphi(x_1,\dots,x_n) = 0$. For a given coefficient bound $c$, there should be exponentially many (in the number of terms) candidate equations, so there should be an $2^{\Omega(c)}$ time algorithm. Whether this can be substantially improved isn't something I can speak to though. $\endgroup$
    – Mark Schultz-Wu
    Commented Jun 19, 2022 at 2:12

You must log in to answer this question.

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