Take a given Diophantine equation. Chances are, we can't find any solutions. But if it's an equation of a certain form, we may get lucky and may be able not only to find a solution, but be able to classify all the solutions of such an equation.

I'm preparing a talk on Diophantine Equations. I'm interested in exploring how the difficulty of Diophantine equations increase as both the number of variables and the degree of the equation increases. Of course, due to Matiyasevich's resolution of Hilbert's Tenth Problem, we know that no general algorithm to determine whether or not a given Diophantine Equation has a solution.

Here's my current understanding of the "frontier" of Diophantine Equations:

Variables $=1$, Degree $=n$:

The solutions are completely determined by the Rational Root Theorem. Once you have all the rational roots, just look for the roots that are also integers.

Variables $=k$, Degree $=1$:

The equation is of the form $$a_1 x_1 + ... + a_k x_k = d.$$

This has solutions if and only if the greatest common divisor of $a_1,...,a_k$ divides $d$, and in that case, we have a nice formula parametrising the solutions (which I won't repeat here).

Variables $=2$, Degree $=2$:

There exist solutions to an equation $P(x,y)$ if and only if we have:

1) There exist solutions to $P(x,y) \mod n$ for all integers $n$ (so in practise, you just need to verify there exists solutions $\mod p$ for all primes $p$, and then by Hensel's Lemma, and the Chinese Remainder Theorem, we have solutions for all $n$.

2) There exist real solutions to $P(x,y)$

If we can find one solution, we can find all rational solutions through stereographic projection. Once you have all rational solutions, look at the solutions where the denominator divides the numerator to get all the integer solutions.

Variables $=2$, Degree $=3$:

This is handled by elliptic curves. Broadly speaking, provided that the equation is "nice enough", the set of solutions to the Diophantine equation has an abelian group structure. This consists of a torsion free part, which can be one of 16 possible groups, and a torsion free part, which looks like $\mathbb{Z}^r$ for some natural number $r$. The $r$ here is called the rank of an elliptic curve, and computing it is, in general, computationally difficult.

Variables $\geq 2$, Degree $\geq 4$:

In general, this is no man's land. Of course, some equations we may have luck with (take $x^4 + y^4 = z^4$; there is an elementary proof that this has no solutions in the natural numbers), but in general, you're probably out of luck.

The other two types of Diophantine equations that I haven't spoken about are exponential Diophantine equations (such as Catalan's conjecture: $x^a - y^b =1$ only has one solutions, namely $x=3, a = 2, y=2, b=3$), and infinite Diophantine equations. These are even more intractable, so I won't touch on these at all.

My question is, in my above analysis, have I missed out anything obvious/is there anything glaringly wrong?



Your Answer

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

Browse other questions tagged or ask your own question.