A condition equivalent to the decidability of Diophantine equations with a finite number of solutions in non-negative integers
Apoloniusz Tyszka · arXiv (Cornell University) · 2014
Let E_n={x_k=1, x_i+x_j=x_k, x_i \cdot x_j=x_k: i,j,k \in {1,...,n}}, and let \kappa \in {2,3,4,...,\omega,\omega_1}. For a positive integer n, let f_{\kappa}(n) denote the smallest non-negative integer b such that for each system S \subseteq E_n which has a solution in non-negative integers x_1,...,x_n and which has less than \kappa solutions in non-negative integers x_1,...,x_n, there exists a solution of S in non-negative integers not greater than b. We prove: (1) if a function g:N \setminus {0} \to N has a n-fold (alternatively, finite-fold) Diophantine representation, then f_{n+1} (respectively, f_{\omega}) dominates g, (2) f_{\omega_1} dominates all computable functions, (3) if the function f_n (alternatively, f_{\omega}) is majorized by a computable function, then a (n-1)-fold (respectively, finite-fold) Diophantine representation does not exist for any function of exponential growth. Let \kappa eq \omega_1, and let us consider the following three statements: (a) there exists an algorithm A (whose execution always terminates) which takes as input a Diophantine equation D and returns the answer YES or NO which indicates whether or not the equation D has a solution in non-negative integers, if the solution set Sol(D) satisfies card(Sol(D))<\kappa, (b) the function f_{\kappa} is majorized by a computable function, (c) if a set M \subseteq N^n has a (\kappa-1)-fold (finite-fold, if kappa=\omega) Diophantine representation, then M is computable. We prove that (a) is equivalent to (b) and (a) implies (c).