Is there an algorithm which takes as input a Diophantine equation, returns an integer, and this integer is greater than the number of integer solutions, if the solution set is finite?

Apoloniusz Tyszka

Published 2013-09-14, updated 2014-03-22Version 2

Let E_n={x_i=1, x_i+x_j=x_k, x_i \cdot x_j=x_k: i,j,k \in {1,...,n}}. For a positive integer n, let f(n) denote the greatest finite total number of solutions of a subsystem of E_n in integers x_1,...,x_n. We prove: (1) the function f is strictly increasing, (2) if a non-decreasing function g from positive integers to positive integers satisfies f(n) \geq g(n) for any n, then a finite-fold Diophantine representation of g does not exist, (3) if the question of the title has a positive answer, then there is a computable strictly increasing function g from positive integers to positive integers such that f(n) \leq g(n) for any n and a finite-fold Diophantine representation of g does not exist.