Recursively enumerable sets of polynomials over a finite field
type: Item
instance of: scholarly article
title: Recursively enumerable sets of polynomials over a finite field
zbMATH Open document ID: 1160.11051
author: Jeroen Demeyer
published in: Journal of Algebra
publication date: 2007-04-16T00:00:00Z
full work available at URL: https://biblio.ugent.be/publication/373953
review text: 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…
reviewed by: Luc Bélair
Mathematics Subject Classification ID: 11U09
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 11U05
zbMATH DE Number: 5143565
zbMATH Keywords: recursively enumerable sets
zbMATH Keywords: Diophantine sets
zbMATH Keywords: Hilbert's Tenth problem
zbMATH Keywords: finite fields
MaRDI profile type: Publication
OpenAlex ID: W2010442485
cites work: Hilbert's Tenth Problem is Unsolvable
cites work: Diophantine sets over polynomial rings
cites work: Diophantine Sets Over Z[ T ]
cites work: Q3905379
cites work: Effective procedures in field theory
cites work: Q5613949
cites work: Undecidability of existential theories of rings and fields: A survey
cites work: Computable Algebra, General Theory and Theory of Computable Fields
cites work: Q3943047
cites work: Undecidable existential theories of polynomial rings and function fields
DOI: 10.1016/J.JALGEBRA.2006.09.030
description: scientific article; zbMATH DE number 5143565