9
$\begingroup$

I found a question whether there are general methods to solve second degree Diophantine equations. I was unable to find an answer so is this known? In particular, the original writer wants to know whether one can find all integers satisfying $x^2 + x = y^2 + y + z^2 + z$.

$\endgroup$
  • 1
    $\begingroup$ For your equation, as was explained by Will Jagy, this is equivalent to looking for all the odd solutions of $X^2+1=Y^2+Z^2$. There are various parametric families of solutions. I have seen a nicer collection somewhere (Piezas?) but here is a start. $\endgroup$ – André Nicolas Aug 11 '12 at 20:20
4
$\begingroup$

About algorithm: There is an algorithm that will determine, given any quadratic $Q(x_1,\dots,x_n)$ as input, whether or not the Diophantine equation $Q(x_1,\dots,x_n)=0$ has a solution. This is something that I (and others) observed quite a long time ago. I have no knowledge about a nice algorithm.

Set one machine $M_1$ to search systematically for solutions. Another machine $M_2$ simultaneously checks whether there is a real solution (easy) and then checks systematically for every modulus $m$ whether there is a solution modulo $m$.

By the Hasse Principle (which in this case is a theorem), if our equation has "local" solutions (real and modulo $m$ for every $m$) then it has an integer solution. So either $M_1$ will bump into a solution or $M_2$ will find a local obstruction to a solution. Thus the algorithm terminates.

The corresponding question for cubics is unsolved. The same question for quartics (in arbitrarily many variables) is equivalent to the general problem of testing a Diophantine equation for solvability, so is recursively unsolvable.

Added: I think that the details are written out in the book Logical Number Theory I by Craig Smorynski. Very nice book, by the way.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ do you mean $Q=0?$ $\endgroup$ – Will Jagy Aug 11 '12 at 20:17
  • $\begingroup$ @WillJagy: Yes. Thank you for pointing out the typo. $\endgroup$ – André Nicolas Aug 11 '12 at 20:23
  • $\begingroup$ So there are only finitely many $m$'s to be checked? If I remember correctly, Turing machine should halt after finitely many steps for every input. $\endgroup$ – Jaakko Seppälä Aug 11 '12 at 20:29
  • $\begingroup$ The machines $M_1$ and $M_2$ operate in parallel (or equivalently make a single $M$ that alternates between an $M_1$ computation and an $M_2$ computation.) As soon as we find an integer solution we halt. As soon as we find an obstruction $m$ (no solution mod $m$) we halt. So for any input $Q$, the algorithm halts in finite time. The time will depend on $Q$. $\endgroup$ – André Nicolas Aug 11 '12 at 20:36
  • $\begingroup$ Alpern's homepage has a method to solve two variable equations, but you will find it erratic. Try x^2 + (x+1)^2 = 125*y and you get a strange mess. The solutions are x=28 + 125*k and x=96 + 125*k for k=1,2,.... $\endgroup$ – J. M. Bergot Nov 12 '17 at 22:15
3
$\begingroup$

There is an algorithm for deciding whether a single degree 2 multivariable polynomial equation has a solution in integers, due to Siegel, Zur Theorie der quadratischen Formen, Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. II 1972, 21-46. See also Grunewald and Sigel, On the integer solutions of quadratic equations, J. Reine Angew. Math. 569 (2004), 13-45.

But the Hasse principle by itself does not give an algorithm: it holds only for rational solutions, not for integer solutions.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In your book "Rational Points on Varieties" you make the comment that "the literature on rational points is vast". I have had a lot of trouble finding literature discussing how to solve diophantine equations like $x_1^2+2x_2^2+3x_3^2=7y^2$. I made up my own approach to this which you can review here : math.stackexchange.com/questions/3485896/… . Is there a good reference that completely covers the quadratic case, no matter how many variables? $\endgroup$ – AmateurMathPirate Jan 3 at 5:05
  • 2
    $\begingroup$ If by "solve" you mean decide whether an integer solution exists and find one if so, then the references in my answer explain how to do it (once you know that a solution exists, you can just do a simple search for it). If you want to parametrize all integer solutions to an inhomogeneous multivariable polynomial equation of degree 2, you won't be able to do it using polynomial parametrizations in general, because the answer involves orbits of arithmetic groups. The references above should explain this too. $\endgroup$ – Bjorn Poonen Jan 6 at 6:12
  • $\begingroup$ but it is true that any inhomogenous polynomial can be converted into a sum of squares multiplied by a constant, ex $m +(m+1) + (m+2) + ... + (n-2) + (n-1) +n = mn \to (m-n+1)m+\frac 1 2 (m-n)(m-n+1)=mn \to 2(2m-1)^2-(2n-2m+1)^2=1$. I know there's a way to solve equations like $ax_1^2+bx_2^2+cx_3^2=dy_1^2 $ Are we really so sure it can't be done in general? $\endgroup$ – AmateurMathPirate Jan 6 at 9:10
1
$\begingroup$

Rewrite this equation a little differently. $$X (X +a)+Y (Y +a)=Z (Z +a)$$

Formulas for the solution can then be written, $p,k$ - where are integers and sets us.

$$X =pk$$ $$Y =\frac{(p^2 −1)k}{2} +\frac{(p−1)a}{2}$$ $$Z =\frac{( p^2 +1)k}{2} +\frac{(p−1)a}{2}$$

If we use the solutions of Pell's equation $p^2 −2 s^2 =1$

Then the solution can be written: $$X =2(s+p)sL+as(2s+p)$$ $$Y =(2s+p)pL+as(2s+p)$$ $$Z =(2 s^2 +2ps+ p^2 )L+2as(s+p)$$

And more. $$X =2s(s−p)L+ap(s−p)$$ $$Y =(p−2s)pL+ap(s−p)$$ $$Z =(2 s^2 −2ps+ p^2 )L+ap(2s−p)$$

$L$ - given by us and can be any integer.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.