You need to know: Set of integers, set
of rational numbers, standard notations
(for all) and
(there exists), polynomials.
Background: Let denote the set of polynomials in
variable
with integer coefficients.
The Theorem: On 15th October 2010, Jochen Koenigsmann submitted to arxiv a paper in which he proved the existence of positive integer n, and a polynomial such that, for any
, we have
if and only if
.
Short context: Hilbert’s 10th problem was to find a general algorithm for deciding, given any n and any polynomial , whether or not f has a zero in
. In 1970, Matiyasevich proved that there can be no such algorithm. Hilbert’s 10th problem over
remains open. If we could define
in
as in the Theorem but with existential quantifiers
instead of universal ones
, this together with Matiyasevich theorem would give a (negative) answer to this problem. The Theorem may be considered as a major step in this direction.
Links: Free arxiv version of the original paper is here, journal version is here.