Is there an algorithm that decides the solvability of a Diophantine equation with a finite number of solutions?

Apoloniusz Tyszka

Published 2017-02-09Version 1

For a positive integer n, let {\theta}(n) denote the smallest positive integer b such that for each system S \subseteq {x_i \cdot x_j=x_k, x_i+1=x_k: i,j,k \in {1,...,n}} which has a solution in positive integers x_1,...,x_n and which has only finitely many solutions in positive integers x_1,...,x_n, there exists a solution of S in ([1,b] \cap N)^n. We conjecture that there exists an integer {\delta} \geq 9 such that the inequality {\theta}(n) \leq (2^{2^{n-5}}-1)^{2^{n-5}}+1 holds for every integer n \geq {\delta}. We prove: (1) for every integer n>9, the inequality {\theta}(n)<(2^{2^{n-5}}-1)^{2^{n-5}}+1 implies that 2^{2^{n-5}}+1 is composite, (2) the conjecture implies that there exists an algorithm which takes as input a Diophantine equation D(x_1,...,x_p)=0 and returns the message "Yes" or "No" which correctly determines the solvability of the equation D(x_1,...,x_p)=0 in positive integers, if the solution set is finite, (3) if a function f:N\{0} \to N\{0} has a finite-fold Diophantine representation, then there exists a positive integer m such that f(n)<{\theta}(n) for every integer n>m.