Does there Exist an Algorithm which to Each Diophantine Equation Assigns an Integer which is Greater than the Modulus of Integer Solutions, if these Solutions form a Finite Set?

Article type: Research Article

Authors: Tyszka, Apoloniusz

Affiliations: Faculty of Production and Power Engineering, University of Agriculture, Poland. rttyszka@cyf-kr.edu.pl

Note: [] Address for correspondence: Balicka 116B, 30-149 Kraków, Poland

Abstract: Let En = {xi = 1; xi + xj = xk; xi · xj = xk : i; j; k ∈ {1,...,n}}. We conjecture that if a system $S \subseteq E_n$ has only finitely many solutions in integers x1,...,xn, then each such solution (x1,...,xn) satisfies |x1|,...,|xn| ≤ 22n−1. Assuming the conjecture, we prove: (1) there is an algorithm which to each Diophantine equation assigns an integer which is greater than the heights of integer (non-negative integer, rational) solutions, if these solutions form a finite set, (2) if a set $\cal{M} \subseteq \mathbb{N}$ is recursively enumerable but not recursive, then a finite-fold Diophantine representation of $\cal{M}$ does not exist.

Keywords: Davis-Putnam-Robinson-Matiyasevich theorem, Matiyasevich's conjecture on finite-fold Diophantine representations

DOI: 10.3233/FI-2013-854

Journal: Fundamenta Informaticae, vol. 125, no. 1, pp. 95-99, 2013