Recursively enumerable sets of polynomials over a finite field are Diophantine (Q2464706): Difference between revisions

A relation \(R(a_1,\dots,a_m)\) (with \(a_1,\dots,a_m\in \mathbb N=\{0,1,2,\ldots \}\)) is called Diophantine over \(\mathbb Z\) if there exists a polynomial \(P(a_1,\dots,a_m, x_1,\dots,x_m)\) with integer coefficients such that \(R(a_1,\dots,a_m)\) holds if and only if \[ P(a_1,\dots,a_m,x_1,\dots,x_m)=0 \] for some \(x_1,\dots,x_m\in \mathbb Z\). The well-known Davis-Putnam-Robinson-Matiyasevich theorem states that a relation \(R(a_1,\dots,a_m)\) is recursively enumerable (r.e.) if and only if it is Diophantine. This implies the negative solution to Hilbert's Tenth Problem over \(\mathbb Z\). Let \(q\) be a prime power, and let \(\mathbb F_q\) be the finite field with \(q\) elements. On the basis of a previous paper by the same author [J. Algebra 310, No. 2, 801--828 (2007; Zbl 1160.11051)], the author shows that every r.e. relation over \(\mathbb F_q[Z]\) is Diophantine over \(\mathbb F_q[Z]\). The author also proves that for any recursive infinite algebraic extension \(F\) of \(\mathbb F_p\) a relation over \(F[Z]\) is Diophantine if and only if it is r.e. for every recursive presentation.