Recursively enumerable sets of polynomials over a finite field (Q875928)

Let \(A\) be a commutative ring with 1. An \(n\)-ary relation over \(A\), i.e. a set of \(n\)-tuples of elements from \(A\), is said to be Diophantine over \(A\) if there exists a polynomial \(f(x_1,\ldots,x_n,y_1,\ldots, y_m)\) over \(A\) such that the given relation coincides with the set of \((x_1,\ldots,x_n)\) such that \(f(x_1,\ldots,x_n,y_1,\ldots, y_m)=0\) has a solution \(y_1,\ldots,y_m\in A\). Hilbert's Tenth Problem for \(A\) is the question whether there exists an algorithm to decide whether or not a polynomial equation with coefficients from \(A\) in any number of variables has a solution over \(A\). The original question by Hilbert concerned the integers \(A=\mathbb{Z}\), and has a negative answer as was proven by Matiyasevic, building on work by Davis, Putnam and J. Robinson. The case \(A=\mathbb{Q}\) is still open and has generated a lot of work on the relativized problem. In this paper, the author shifts the attention toward another aspect of the original question and its solution, namely, that the class of all Diophantine sets coincides with the class of all recursively enumerable sets. Now this can also be relativized to different (recursive) rings: is it true that the class of Diophantine sets over a ring \(A\) coincides with the class of recursively enumerable sets over \(A\)? Little seems to be known and the only positive results are for the following rings of polynomials: \(A=\mathbb{Z}[Z]\) (Denef) and \(A={\mathcal O}_K[Z_1, Z_2, \ldots, Z_m]\), where \({\mathcal O}_K\) is a number ring (Zahidi). Let \(q\) be a power of a prime, and let \(Z,W\) be indeterminates. The main theorem of the paper is the following: a relation over \(\mathbb{F}_q[Z]\) is recursively enumerable if and only if it is Diophantine over \(\mathbb{F}_q[Z,W]\). The author announces that he will give in another paper a Diophantine interpretation of the ring \(\mathbb{F}_q[Z,W]\) in the ring \(\mathbb{F}_q[Z]\). Together with the above result, this would show the equivalence of the recursively enumerable sets over \(\mathbb{F}_q[Z]\) with the Diophantine sets over \(\mathbb{F}_q [Z]\). The paper is well written.