zbMATH — the first resource for mathematics

A note on diophantine representations. (English) Zbl 0805.11085
In 1971, Yu. Matiyasevich proved that every recursively enumerable (for the nonexpert this really means effectively listable) set is diophantine (the projection along some of the variables of the solution set – in a power of the integers – of a multivariable polynomial equation with integer coefficients), thus giving a negative answer to Hilbert’s 10th problem, that is, proving that there is no algorithm which can (always successfully) test diophantine equations for solvability in the integers. Matiyasevich’s Theorem really says “if you can somehow list a set of (a power of the) integers then this set is diophantine”. Usually, the known diophantine definitions of, even moderately complicated sets (in common terms), are very complicated. To find “economical” (say “useful”) representations is often quite difficult.
The paper makes an effort towards giving relatively “economical” diophantine representations of the sets of Mersenne primes, twin primes and the graph of the “factorial” function, and presents a diophantine problem whose unsolvability is equivalent to the Fermat problem.

11U05 Decidability (number-theoretic aspects)
11D99 Diophantine equations
03B25 Decidability of theories and sets of sentences
Full Text: DOI