Is there an algorithm to solve quadratic Diophantine equations?

Question

I was asked two questions related to Diophantine equations.

1. Can one find all integer triplets $(x,y,z)$ satisfying $x^2 + x = y^2 + y + z^2 + z$? I mean some kind of parametrization which gives all solutions but no points which do not satisfy the equation.

2. Is there an algorithm that will determine, given any quadratic $Q(x_1,\ldots,x_n)$ as input, all integer points of this quadratic? In the case of existence of solution, there is an algorithm, https://math.stackexchange.com/questions/181380/second-degree-diophantine-equations/181384#comment418090_181384

Answer 1

Sierpsinski proved that whenever this diophantine equation does not have a solution for $x$ then $x^2+(x+1)^2$ is prime. It is conjectured also by Sierpinski that there are infinitely many primes of the above form but this still remains open.

So, your question cannot be answered yet. For more details see http://arxiv.org/pdf/0810.0222.pdf

Answer 2

If one is interested in efficient algorithms, as opposed to the simple existence of algorithms, it may be worth noting that, given positive integers $a$, $b$, and $c$, the question, are there positive integers $x$ and $y$ such that $ax^2+by=c$, is NP-complete. This is item AN8 in Garey and Johnson, page 250; the citation is Manders and Adleman, NP-complete decision problems for binary quadratics, J Comput System Sci 16 (1978) 168-184.

Answer 3

Let me just add that for solving quadratic diophantine equations in 2 variables, i.e. equations of the form $$ ax^2 + bxy + cy^2 + dx + ey + f = 0, \ \ a, b, c, d, e, f \in \mathbb{Z}, $$ there is a nice algorithm. Dario Alpern has created a website running a Java program which completely solves such equations for given coefficients $a, b, c, d, e$ and $f$ -- see http://www.alpertron.com.ar/JQUAD.HTM. Optionally, the program shows all steps of the solution, similar as a human might do when solving the equation by hand. The website also describes the algorithm used.

Answer 4

There are infinitely many integer solutions, so you need to specify what you mean by "can one find all". If you mean "Are all solutions given by a finite set of easily computed parametrized families?" then the answer is yes, essentially following John R Ramsden's answer (with some minor corrections).

If we set $X = 2x+1$, $Y = 2y+1$ and $Z = 2z+1$, we get the equation $X^2 + 1 = Y^2 + Z^2$. Euler showed that all solutions have the form $(ac+bd)^2 + 1 = (ac-bd)^2 + (ad+bc)^2$ where $a,b,c,d$ range over integers satisfying $ad-bc = 1$. This set is easy to parametrize, because $a,b,c,d$ describe entries of elements $\binom{ab}{cd}$ in $SL_2(\mathbb{Z})$. We are seeking odd solutions, and this condition is equivalent to $ac+bd$ odd, which can be determined by reducing matrices mod 2.

We find that any element of $SL_2(\mathbb{Z})$ congruent to $\binom{11}{01}$, $\binom{01}{11}$, $\binom{10}{11}$, or $\binom{11}{10}$ modulo 2 yields a solution to your equation. These can be easily generated, either by using the Euclidean algorithm to generate suitable elements of $SL_2(\mathbb{Z})$ from an initial choice of coprime integers, or by multiplying an initial solution by powers of the matrices $\binom{12}{01}$ and $\binom{10}{21}$. The kernel $\Gamma(2)$ of reduction mod 2 in $SL_2(\mathbb{Z})$ becomes a free group generated by those two matrices, once we quotient by $\pm \binom{10}{01}$. This sign ambiguity nicely cancels the invariance under sign change in Euler's parametrization.

Answer 5

S. Carnahan (Sep 24 '13 at 18:33) showed parametrization by cosets of congruence subgroups of SL(2,Z). What is missing is parametrization of SL(2,Z) and its congruence subgroups which can be found in L.N. Vaserstei. Polynomial parametrization for the solutions of Diophantine equations and arithmetic groups , Annals of Math. 171:2 (March of 2010), 979–1009. MR2630059. Zbl 05712747

Answer 6

We first run the algorithm to determine whether any solutions exist, by dovetailing an enumeration of integer $n$-tuples together with an exhaustive search of solutions modulo prime powers, halting if it finds either an integer solution, a disproof in modular arithmetic or a disproof in the reals (e.g. by showing that the quadratic form is positive- or negative-definite). This algorithm works by the Hasse principle.

If it finds a disproof, output the empty set $\emptyset$. Otherwise, we analyse the signature of the quadratic form. If it is $+++ ... +$ or $--- ... -$, then the surface would be bounded and, as such, there is a finite solution set that can be produced by exhaustive search. Otherwise, there are infinitely many solutions (as intersecting one solution with an appropriately-chosen plane yields a generalised Pell equation). In that case, we can just exhaustively run through an enumeration of integer $n$-tuples, printing out each solution that it finds.

Answer 7

The equation is equivalent to $(2 x + 1)^2 + 1 = (2 y + 1)^2 + (2 z + 1)^2$. So given that an integer solution to this is implies integers $a, b, c, d$ with exactly one odd and $(a, d) = (b, c) = 1$ with $2 x + 1, 2 y + 1, 2 z + 1 = a c + b d, a b + c d, a c - b d$ subject to $a b - c d = 1$, it would appear the original is equivalent to the latter.

Answer 8

In 1972, Siegel [1] developed an algorithm for deciding whether a quadratic equation has an integer solution. In 2004, Grunewald and Segal [2] proved that, more generally, there is an algorithm for deciding whether the integer solution set is finite or infinite, and if finite, list all the solutions.

To "solve" equations with infinitely many integer solutions, we need to decide what "counts" as an acceptable answer. A simple example of Pell equation $x^2-2y^2=1$ shows that it is not always possible to parametrize all integer solutions using polynomial parametrizations. So, we must allow "other" descriptions of the solution set.

In fact, inspecting references [1,2] one may find that they contain "some" description of all solutions.

Every quadratic equation in variables $x=(x_1,\dots,x_n)$ can be written in matrix form as $$ x^TAx+bx=c, $$ where $A$ in $n\times n$ matrix, $b$ is a vector, and $c$ is a constant. If $A$ is singular (that is, determinant of $A$ is $0$), then there is a vector $v$ with integer entries such that $Av=0$. Let $P$ be an invertible $n\times n$ matrix with the first column $v$. Then a linear change of variables $x=Py$ results in $$ y^T P^TAP y + (bP)y = c. $$ By the choice of $P$, term $y^T P^TAP y$ does not depend on $y_1$, hence the whole equation takes the form $d y_1 = Q(y_2,\dots,y_n)$ for some polynomial $Q$. If $d=0$, we have reduced the equation to one in $n-1$ variables and can proceed by induction. If $d\neq 0$, the equation reduces to parametrising $y_2, \dots, y_n$ such that $Q(y_2,\dots,y_n)$ is divisible by $d$, which is easy.

Now let $A$ be not singular. Then let us do change of variables $x=y+h$, where $h$ is a rational vector. Then the equation reduces to $$ (y+h)^TA(y+h)+b(y+h)=c. $$ We can then solve for $h$ to make the linear part $0$, the result is $h=bA^{-1}/2$. This reduces the equation to $$ y^T A Y = c. $$ If $c=0$, this is a homogeneous equation, finding its integer solutions is essentially equivalent to finding rational solutions, and the algorithm is described in the previous answers. In short, use Hasse principle to decide if a rational solution exists, and if so, draw a line though it to generate other rational solutions. Then multiply by a common denominator to find integer solutions.

The main case is when $A$ is non-singular and $c\neq 0$. But in this case, as mentioned by Grunewald and Segal, (i) the integral orthogonal group of $A$ is finitely generated, and there is an algorithm for listing the generators, and (ii) there is a finite set of solution to our equations such that all other solutions can be constructed from this finite set by actions of this integral orthogonal group. This gives some "finite description" of all integer solutions in $y$. Because our change of variables involved rational numbers, the original variables $x_i$ are integer subject to some congruence conditions on $y_i$, so we need to start with some initial sets of solutions in $y$, apply actions by generators, and check the congruence conditions. I leave it to others to judge if this counts as an "acceptable" description of the integer solution set to the original equation. I think this description is essentially the best we can hope for.

[1] Siegel, Zur Theorie der quadratischen Formen, Nachr. Akad. Wiss. Göttingen Math.-Phys. Kl. II 1972, 21-46.

[2] Grunewald and Segal, On the integer solutions of quadratic equations, J. Reine Angew. Math. 569 (2004), 13-45.

Answer 9

Everything can be done much easier! 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.