Is there a method for determining if a system of quadratic diophantine equations has any solutions?

My specific example (which comes from this question) is: $$\frac{4}{3}x^2 + \frac{4}{3}x + 1 = y^2$$ $$\frac{8}{3}x^2 + \frac{8}{3}x + 1 = z^2$$ I want to know if there are any positive integer triples $(x,y,z)$ which satisfy both equations.

  • 1
    $\begingroup$ A two-fold approach would be to first solve the signed Pell equation $z^2 - 2y^2 = -1$ and then showing somehow that neither $z^2$ nor $y^2$ attains the form of what is given above. First part is easy and I think a conclusion of the second part can be drawn from parametrizing the Pell's equation. (Added : This is just a heuristic, though, so be warned before attempting) $\endgroup$ – Balarka Sen Dec 23 '13 at 14:44
  • $\begingroup$ @WillJagy Sorry, I should have specified--I mean positive integer triples $\endgroup$ – jamaicanworm Dec 23 '13 at 19:08

We consider only the general question. It was proved by Matijasevich that there is no algorithm which, on input any Diophantine equation $P(x_1,x_2,\dots,x_m)=0$, where $P$ is a polynomial with integer coefficients, will determine whether the equation has an integer solution.

Using a little trick that goes back to Skolem, given any Diophantine equation $P(x_1,x_2,\dots,x_m)=0$, we can algorithmically produce a system $Q_i(y_1,y_2, \dots, y_n)=0$, $i=1,\dots, s$ of quadratic Diophantine equations such that the system has a solution in integers if and only if $P(x_1,x_2,\dots,x_m)=0$ has a solution in integers.

It follows that there is no algorithm which, given any system of quadratic Diophantine equations, will determine whether the system has a solution in integers.

  • $\begingroup$ Do you have links to the results from Matijasevich and Skolem? $\endgroup$ – jamaicanworm Dec 26 '13 at 1:22
  • $\begingroup$ For Matijasevich, there is this.. I cannot find an original place for Skolem trick, it is mentioned in many places, including Smorynski's Logical Number Theory. Basically the idea is that for example $y=kx^3$ is repaced by $u=kx^2$, $y=ux$, and similarly for higher powers. So a single Diophantine equation is equivalent to a system of quadratics. By summing squares, one can make the original equation equivalent to a single quartic. $\endgroup$ – André Nicolas Dec 26 '13 at 1:40

Answered at the source question. Briefly: There are no such $(x,y,z)$, because then we'd have a nonconstant arithmetic progression of four squares: $$ 1 = 1^2, \ \frac43(x^2+x)+1 = y^2, \ \frac83(x^2+x)+1 = z^2, \ 4(x^2+x)+1 = (2x+1)^2. $$ The impossibility of such a progression is a theorem of Euler (1780, answering a question "first raised by Fermat in 1640" according to Keith Conrad's exposition). This even proves that there are no rational solutions $(x,y,z)$ other than the obvious ones with $x=0$ or $x=-1$.

  • 2
    $\begingroup$ Hi, Noam. I like it! $\endgroup$ – Will Jagy Dec 25 '13 at 4:15
  • $\begingroup$ If I could give 100 up votes :) Very nice. $\endgroup$ – Bumblebee Jul 3 '15 at 6:20

Incomplete... First take $w = 2 x + 1$

From $z^2 - 2 y^2 = -1$ we get the sequence of $y$ values $$ y_0 = 1, \; \; y_1 = 5, \; \; y_{n+2} = 6 y_{n+1} - y_n, $$ or $$ 1,5,29,169,985,5741,33461, 195025 \ldots $$

From $w^2 - 3 y^2 = -2$ we get the sequence of $y$ values $$ Y_0 = 1, \; \; Y_1 = 3, \; \; Y_{n+2} = 4 Y_{n+1} - Y_n, $$ or $$ 1,3,11,41,153,571,2131, 7953, 29681, 110771 \ldots $$

The question can then be written about the two sequences. They grow at different rates, so the indices would be different anyway; but, are there indices $i,j$ with $$ y_i = Y_j? $$

At the least, the matter can be experimented with further this way: both sequences have explicit recipes involving square roots and exponents, same as the Fibonacci numbers and the golden ratio. The two roots of the characteristic polynomials are real, and after a relatively short while you can ignore the power of the smaller roots, and compare $y_i$ and $Y_j$ using logarithms to find good pairs $i,j.$ Finally, as mentioned, I imagine this can be finished with some algebraic number theory. But you could also finish it by showing $\log y_m$ and $\log Y_n$ never get quite close enough.

For what it may be worth, $$ y_n = \left( \frac{\sqrt 2 + 1}{\sqrt 8} \right) \left( 3 + \sqrt 8 \right)^n + \left( \frac{\sqrt 2 - 1}{\sqrt 8} \right) \left( 3 - \sqrt 8 \right)^n $$ and $$ Y_n = \left( \frac{\sqrt 3 + 1}{\sqrt {12}} \right) \left( 2 + \sqrt 3 \right)^n + \left( \frac{\sqrt 3 - 1}{\sqrt {12}} \right) \left( 2 - \sqrt 3 \right)^n $$

  • $\begingroup$ Yes, I used a similar method in the UPDATE to my question here math.stackexchange.com/q/611135/23390 (I have both explicit formulas and want to know where they intersect). If you want to post a more complete version of this answer on that question, I will award the bounty. $\endgroup$ – jamaicanworm Dec 23 '13 at 19:51
  • 1
    $\begingroup$ This is what I was thinking. A bit of a diophantine approximation might be needed to show that $| \log Y_n - \log y_m |$ is never too small which, nevertheless, could be hard. $\endgroup$ – Balarka Sen Dec 23 '13 at 19:52
  • 1
    $\begingroup$ There is a suggestion from an expert that, because of some fortunate features of an elliptic curve that describes this thing, there may be a (probably rather long) proof by descent. I will see if I can work out such a thing myself. Meanwhile, I'm not one who could finish this using elliptic curves. $\endgroup$ – Will Jagy Dec 23 '13 at 20:53
  • $\begingroup$ @jamaicanworm, I may have spoken a little too soon. I found a complete presentation of Fermat's method of descent for some cubic curves in pages 140-149 of Andre Weil, Number Theory: An approach through history from Hammurapi to Legendre. Another example pages 150-157. Getting the method to work, when it does work, seems within reason. Knowing when it will work is entirely another matter, of course. Anyway, I will see if I can work it out over the next few days. I encourage you to do the same. $\endgroup$ – Will Jagy Dec 24 '13 at 18:24

Your specific example can be formalized in the following way:

$$ \begin{eqnarray} 4x^2+4x+3=3y^2\\ 8x^2+8x+3=3z^2\\ 4x^2+4x=3(z^2-y^2)\\ (z^2-y^2)=4x(x+1)/3 \end{eqnarray} $$

let $x+1=3n$

$$ \begin{eqnarray} (z^2-y^2)=4(3n-1)n \end{eqnarray} $$

Let $z=4n-1$ and $y=2n-1$ (more generally if $3n^2-n=uv$, then $z=u+v$ and $y=v-u$). So I would have thought there are tons of integer solutions, but there's some other constraint on the go. Let's punch $x+1=3n$ into the original expressions:

$$ \begin{eqnarray} 4x(x+1)+3&=&12n(3n-1)+3&=&3y^2\\ y^2&=&12n^2-4n+1&&\\ 8x(x+1)+3&=&24n(3n-1)+3&=&3z^2\\ z^2&=&24n^2-8n+1&&\\ z^2-y^2&=&12n^2-4n&=&y^2-1\\ (z+y)(z-y)&=&(y+1)(y-1)&& \end{eqnarray} $$

The only solution I can come up with here is $z=y$, $y=1$, $x=0$. One other approach works too:

let $x=3n$

$$ \begin{eqnarray} (z^2-y^2)=4(3n+1)n \end{eqnarray} $$

Let $z=4n+1$ and $y=2n+1$. Let's punch $x=3n$ into the original expressions:

$$ \begin{eqnarray} 4x(x+1)+3&=&12n(3n+1)+3&=&3y^2\\ y^2&=&12n^2+4n+1&&\\ 8x(x+1)+3&=&24n(3n+1)+3&=&3z^2\\ z^2&=&24n^2+8n+1&&\\ z^2-y^2&=&12n^2+4n&=&y^2-1\\ (z+y)(z-y)&=&(y+1)(y-1)&& \end{eqnarray} $$

The end result is the same.


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.