Diophantine equation

In algebraic number theory , a Diophantine equation (named after the Greek mathematician Diophantos of Alexandria , around 250) is an equation of the form where a given polynomial function is with integer coefficients and only integer solutions are sought. This restriction of the solution set is useful and necessary if questions of divisibility are to be answered, if problems of congruence arithmetic are involved or if only whole-number solutions are useful in practice, e.g. B. for the number of pieces in the manufacture of several products. ${\displaystyle f(x_{1},x_{2},x_{3},\dotsc ,x_{n})=0}$ ${\displaystyle f}$

Examples

• ${\displaystyle x^{2}-y=0}$has as a solution the number pairs…, (-3, 9), (-2, 4), (-1, 1), (0, 0), (1, 1), (2, 4), (3, 9 ), ...; general: with ${\displaystyle (x,y)}$ ${\displaystyle (x,y)=\left(n,n^{2}\right)}$ ${\displaystyle n\in \mathbb {Z} .}$
• ${\displaystyle x^{4}+y^{2}+z^{20}=-7}$ is unsolvable because the left side of the equation (as the sum of squares) is never negative.
• ${\displaystyle 3x=4}$has no solution because 4 is not divisible by 3 and therefore there is no integer whose 3-fold results in 4.

Linear Diophantine equation

→ Main article : Linear Diophantine equation

Diophantine equations, in which no higher than first powers of the unknowns occur, are called linear . There are algorithms for them that can be used to find all solutions after a finite number of steps.

Famous Diophantine equations

Pythagorean triples

→ Main article : Pythagorean triple

The infinitely many integer solutions of form the so-called Pythagorean triples. You can find it essentially through the approach ${\displaystyle x^{2}+y^{2}=z^{2}}$

${\displaystyle x=u^{2}-v^{2}}$

${\displaystyle y=2uv}$

${\displaystyle z=u^{2}+v^{2}}$

Fermat's last sentence

→ Main article : Big Fermat's theorem

If one generalizes the above equation too , one obtains a Diophantine equation of degree . Fermat's last theorem is the claim made by Pierre de Fermat 400 years ago that it has no integral solution for (except for the trivial solutions in which one of the numbers is 0), which was only proven in 1994 by Andrew Wiles . ${\displaystyle x^{n}+y^{n}=z^{n}}$ ${\displaystyle n}$ ${\displaystyle n>2}$

Pell's equation

→ Main article : Pell's equation

In addition to the linear Diophantine equations, there is the so-called Pell equation

${\displaystyle x^{2}-Dy^{2}=1}$

especially important, whereby for a given natural value the smallest value pair has to be looked for first , from which all other pairs can then be easily found. If is a square number, this equation only has the trivial solutions , otherwise it has infinite solutions. Solving Pell's equation is equivalent to looking for the units in the ring of algebraic integers of the square number field , which is created from the rational number field by the addition of a square root . ${\displaystyle D}$ ${\displaystyle (x,y)}$ ${\displaystyle D}$ ${\displaystyle (x,y)=(\pm 1,0)}$ ${\displaystyle \mathbb {Q} ({\sqrt {D}})}$ ${\displaystyle \mathbb {Q} }$ ${\displaystyle D}$

Some general solution methods and finiteness theorems for classes of Diophantine equations

In 1908, Axel Thue showed that the equation

${\displaystyle f(x,y)=c}$

with an irreducible form of degree greater than or equal to 3 in two variables and an integer only has finitely many solutions (such equations are called Thue equations ). This was based on his estimations of algebraic numbers by rational ones (such investigations are called Diophantine approximations ) and is not effective (that is, one does not get a solution method from it). The theorem does not apply to degree 2, as is shown by Pell's equation with an infinite number of solutions. ${\displaystyle f(x,y)}$ ${\displaystyle c}$

In 1968 Alan Baker gave an effective upper limit for the solutions of Thue equations with his method of linear forms in logarithms of algebraic numbers, an efficient algorithm for their solution was given in 1989 by De Weger and Tzanakis.

In 1929 Carl Ludwig Siegel proved that there are only finitely many integer solutions for equations describing algebraic curves of topological gender . This proof was also ineffective and used Diophantine approximations. If we consider the body of the rational numbers instead of the whole numbers, Siegel's theorem corresponds to Mordell's conjecture . ${\displaystyle g>0}$

In 1938 Thoralf Skolem found a fairly general method of solving Diophantine equations of the form with an irreducible polynomial , which breaks down into factors in an expansion of the field of rational numbers and fulfills another additional condition. This also includes Thue's equation in the event that not all roots are real. Skolem's method is based on p-adic analysis (local method) and not on Diophantine approximations like Thue's method. ${\displaystyle P(x_{1},\dotsc ,x_{n})=0}$ ${\displaystyle P}$ ${\displaystyle m>n}$ ${\displaystyle f(x,1)=0}$

Hilbert's tenth problem

In 1900 David Hilbert presented the problem of the decidability of the solvability of a Diophantine equation as the tenth problem in his famous list of 23 mathematical problems . In 1970, Yuri Wladimirowitsch Matijassewitsch proved that the solvability of Diophantine equations is undecidable, i.e. that there can be no general algorithm that determines whether any Diophantine equation is solvable or unsolvable. Martin Davis , Hilary Putnam and Julia Robinson did important preparatory work . Davis (1953) wrote the formulation as a problem about Diophantine sets and the conjecture that these are identical to the recursively enumerable sets, the proof of which solved the 10th Hilbert problem.

A Diophantine set is a set of -Tuples of positive integers that make up a polynomial equation ${\displaystyle M}$ ${\displaystyle n}$ ${\displaystyle x=(x_{1},\dotsc ,x_{n})}$

${\displaystyle P(x_{1},\dotsc ,x_{n},a_{1},\dotsc ,a_{m})=0}$

satisfy with the also positive integer parameters : ${\displaystyle a_{1},\dotsc ,a_{m}}$

${\displaystyle M=\{x\mid \exists a_{1},\dotsc ,a_{m}\colon P(x,a_{1},\dotsc ,a_{m})=0\}}$

For example, the composite numbers form a Diophantine set (the polynomial is then with the parameters ), also the positive even numbers (polynomial ). One can also use systems of polynomial equations for the definition , because these can be reduced to the case of a single equation. Correspondingly, Diophantine functions are given by the Diophantine sets . Putnam showed in 1960 that every Diophantine set of natural numbers can be represented as a set of values ​​in the natural numbers of an integer polynomial. ${\displaystyle x-(a+1)\,(b+1)}$ ${\displaystyle a,b}$ ${\displaystyle x-2\cdot a}$ ${\displaystyle P_{i}=0}$ ${\displaystyle \sum _{i}P_{i}^{2}=0}$ ${\displaystyle y=f(x_{1},\dotsc ,x_{n})}$ ${\displaystyle M=\{y,x_{1},\dotsc ,x_{n}\}}$

It is sometimes difficult to show that a lot is Diophantine. For example with the set of prime numbers, as opposed to the composite numbers (because the complement of a Diophantine set does not have to be Diophantine according to Martin Davis), with the powers of 2 and the values ​​of the factorials . Julia Robinson initially failed to show that Diophantine is. But she showed that this would follow if one could find a Diophantine set with exponential growth, that is, those sets in whose defining equation one of the variables appears as an exponent. More precisely, this means that (Julia Robinson's hypothesis): ${\displaystyle n!}$ ${\displaystyle \{(a,b,c)\mid a=b^{c}\}}$

There is a Diophantine set such that: ${\displaystyle D}$

• From follows . ${\displaystyle u,v\in D}$ ${\displaystyle v\leq u^{u}}$
• For anything positive there is with . ${\displaystyle k}$ ${\displaystyle u,v\in D}$ ${\displaystyle v>u^{k}}$

Diophantine sets are by definition recursively enumerable (there is an algorithm that stops on input from this set).

Together with Davis and Putnam, Robinson showed that the recursively enumerable sets are exactly the Diophantine exponential sets and the theorem

"Every recursively enumerable set is Diophantine"

would follow if one could prove the existence of an exponentially growing Diophantine set (for which Julia Robinson's hypothesis holds true). In 1970, Matiyasevich succeeded in doing this with the help of Fibonacci numbers , an exponentially growing sequence of natural numbers. His example consisted of ten polynomial equations with 15 unknowns.

Since according to the computability theory there are recursively enumerable sets that are not decidable (according to an argument based on Cantor diagonalization as in the case of the holding problem ), it follows that Hilbert's tenth problem is not solvable.

Since the prime numbers can be enumerated recursively, it also follows that there is a Diophantine equation whose solution consists of all prime numbers and only these.

It has been known since Thoralf Skolem that all Diophantine equations can be reduced to such fourth or smaller degrees. Matyasevich also succeeded in showing that polynomials in nine or fewer unknowns are sufficient to represent Diophantine sets.

In connection with Gödel's incompleteness results it also follows that in every axiom system of arithmetic there are Diophantine equations which have no solution, but which cannot be proven within the axiom system.

literature

• Louis Mordell : Diophantine Equations. Academic Press, 1969.
• GH Hardy , EM Wright: An Introduction to the Theory of Numbers. 5th ed., Clarendon Press, Oxford, England 1979.

On Hilbert's tenth problem:

• Yuri W. Matijassewitsch: Hilbert's Tenth Problem. Foundations of Computing Series. MIT Press, Cambridge MA et al. a. 1993, ISBN 0-262-13295-8 .
• Martin Davis, Reuben Hersh: Hilbert's tenth problem. Scientific American, Volume 229, Nov. 1973.
• Martin Davis: Hilbert's tenth problem is unsolvable. American Mathematical Monthly, Volume 80, 1973, pp. 233-269.
• Martin Davis, Yuri Matiyasevich, Julia Robinson: Hilbert's tenth problem, Diophantine equations, positive aspects of a negative solution. In: F. Browder: Mathematical Developments Arising from Hilbert's Problems. AMS, Part 2, 1976, pp. 323-378.
• Alexandra Shlapentokh: Hilbert's tenth problem: Diophantine classes and extensions to global fields. Cambridge UP, 2006.

Web links

• Eric W. Weisstein : Diophantine Equation . In: MathWorld (English).
• Christian Spannagel : Diophantine equation. Lecture series, 2012.
• Jordan Ellenberg : Arithmetic Geometry.

References and comments

1. ↑ A. Thue: Remarks on certain approximate fractions of algebraic numbers. Vid.-Selsk., Math.-Naturwiss. Class, No. 3, Oslo 1908.
2. ↑ In other words: has at least three different roots. ${\displaystyle f(x,1)=0}$
3. ^ A. Baker: Contributions to the Theory of Diophantine Equations. I. On the Representation of Integers by Binary Forms. Phil. Transactions Royal Society, Vol. 263, 1968, pp. 173-191.
4. ↑ N. Tzanakis, BMM De Weger: On the practical solution of the Thue equation. J. of Number Theory, Vol. 31, 1989, pp. 99-132.
5. ^ CL Siegel: About some applications of Diophantine approximations. Meeting reports of the Prussian Academy of Sciences, Math.-Phys. Class, 1929, No. 1.
6. ↑ A proof can be found in:
   J.-P. Serre: Lectures on the Mordell-Weil Theorem. Vieweg, 1998.
   A proof with the subspace theorem by Wolfgang Schmidt after Umberto Zannier and P. Corvaja can be found in:
   E. Bombieri, W. Gubler: Heights in Diophantine Geometry. Cambridge UP, 2006.
7. ^ Th. Skolem: Diophantine equations. Results of mathematics and its border areas. Springer, Berlin 1938, presented in:
   ZI Borevich, IR Shafarevich: Number Theory. Birkhäuser, 1966.
   L. Mordell: Diophantine Equations. 1969, chapter 23.
8. ^ M. Davis: Arithmetical problems and recursively enumerable predicates. J. Symb. Logic, Vol. 18, 1953, pp. 33-41.
9. ↑ It can be shown without loss of generality that one only needs to consider natural numbers instead of whole numbers.
10. ↑ H. Putnam: An unsolvable problem in number theory. J. Symb. Logic, Vol. 25, 1960, pp. 220-232.
11. ↑ M. Davis, H. Putnam, J. Robinson: The decision problem for exponential diophantine equations. Annals of Mathematics, Volume 74, 1961, pp. 425-436.
12. ↑ Explicitly stated for example in Davis: Hilbert's tenth problem. Scientific American, Nov. 1973, p. 91.
13. ^ Davis: Hilbert's tenth problem. Scientific American, Nov. 1973, p. 91.