# System of quadratic Diophantine equations

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.

• 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) – Balarka Sen Dec 23 '13 at 14:44
• @WillJagy Sorry, I should have specified--I mean positive integer triples – jamaicanworm Dec 23 '13 at 19:08

## 4 Answers

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.

• Do you have links to the results from Matijasevich and Skolem? – jamaicanworm Dec 26 '13 at 1:22
• 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. – 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$.

• Hi, Noam. I like it! – Will Jagy Dec 25 '13 at 4:15
• If I could give 100 up votes :) Very nice. – 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$$

• 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. – jamaicanworm Dec 23 '13 at 19:51
• 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. – Balarka Sen Dec 23 '13 at 19:52
• 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. – Will Jagy Dec 23 '13 at 20:53
• @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. – 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.