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
  • 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$ Aug 11, 2012 at 20:20

3 Answers 3

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.

$\endgroup$
6
  • $\begingroup$ do you mean $Q=0?$ $\endgroup$
    – Will Jagy
    Aug 11, 2012 at 20:17
  • $\begingroup$ @WillJagy: Yes. Thank you for pointing out the typo. $\endgroup$ Aug 11, 2012 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$ Aug 11, 2012 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$ Aug 11, 2012 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$ Nov 12, 2017 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.

$\endgroup$
3
  • $\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$ Jan 3, 2020 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$ Jan 6, 2020 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$ Jan 6, 2020 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.

$\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.