Further results on Hilbert's tenth problem

DOI10.1007/S11425-020-1813-5zbMATH Open1494.11100arXiv1704.03504OpenAlexW3119401540MaRDI QIDQ829448FDOQ829448

Authors: N. E. Zubov 

Publication date: 6 May 2021

Published in: Science China. Mathematics (Search for Journal in Brave)

Abstract: Hilbert's Tenth Problem (HTP) asks for an algorithm to test whether an arbitrary polynomial Diophantine equation with integer coefficients has solutions over the ring $mathbbZ$ of the integers. This was finally solved by Matiyasevich negatively in 1970. In this paper we obtain some further results on HTP over $mathbbZ$. We prove that there is no algorithm to determine for any $P(z_1,ldots,z_9)inmathbbZ[z_1,ldots,z_9]$ whether the equation $P(z_1,ldots,z_9)=0$ has integral solutions with $z_{9}ge0$. Consequently, there is no algorithm to test whether an arbitrary polynomial Diophantine equation $P(z_1,ldots,z_{11})=0$ (with integer coefficients) in 11 unknowns has integral solutions, which provides the best record on the original HTP over $mathbbZ$. We also prove that there is no algorithm to test for any $P(z_1,ldots,z_{17})inmathbbZ[z_1,ldots,z_{17}]$ whether $P(z_1^2,ldots,z_{17}^2)=0$ has integral solutions, and that there is a polynomial $Q(z_1,ldots,z_{20})inmathbbZ[z_1,ldots,z_{20}]$ such that ${\displaystyle }${Q(z_1^2,ldots,z_{20}^2): z_1,ldots,z_{20}inmathbb Z}cap{0,1,2,ldots}${\displaystyle }$ coincides with the set of all primes.

Full work available at URL: https://arxiv.org/abs/1704.03504

Recommendations

• Extensions of Hilbert's tenth problem
• Hilbert's tenth problem
• Hilbert's Tenth Problem
• scientific article; zbMATH DE number 1261118
• On the bounded version of Hilbert's tenth problem
• Hilbert's Tenth Problem: What was done and what is to be done
• Hilbert's tenth problem for fixed \(d\) and \(n\)
• Hilbert's Tenth Problem over number fields, a survey
• scientific article; zbMATH DE number 1101523

zbMATH Keywords

Diophantine equationundecidabilityintegral solutionpolygonal numbersHilbert's tenth problem

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Recursively (computably) enumerable sets and degrees (03D25) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Primes (11A41) Diophantine equations (11D99) Undecidability and degrees of sets of sentences (03D35) Decidability (number-theoretic aspects) (11U05)

Cites Work

• The Hardy-Littlewood method.
• The decision problem for exponential diophantine equations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reduction of an arbitrary diophantine equation to one in 13 unknowns
• Title not available (Why is that?)
• On universal sums of polygonal numbers
• A result similar to Lagrange's theorem
• Hilbert's tenth problem. Diophantine classes and extensions to global fields
• Title not available (Why is that?)
• The Diophantine Problem for Polynomial Rings and Fields of Rational Functions
• Definability and decision problems in arithmetic
• Hilbert's Tenth Problem is Unsolvable
• Universal diophantine equation
• Every Number is Expressible as the Sum of How Many Polygonal Numbers?
• Contributions to the theory of diophantine equations I. On the representation of integers by binary forms
• Title not available (Why is that?)
• Reduction of unknowns in diophantine representations
• Hilbert's Tenth Problem for Quadratic Rings
• Diophantine Sets over Some Rings of Algebraic Integers
• Title not available (Why is that?)
• An unsolvable problem in number theory
• ANEW RELATION‐COMBINING THEOREM AND ITS APPLICATION
• Primes are nonnegative values of a polynomial in 10 variables
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• Title not available (Why is that?)
• Computational complexities of diophantine equations with parameters
• Classification of Quantifier Prefixes Over Diophantine Equations
• How to Pick Out the Integers in the Rationals: An Application of Number Theory to Logic
• Arithmetical Definitions in the Ring of Integers
• Defining \(\mathbb Z\) in \(\mathbb Q\)

Cited In (16)

• Prime representing polynomial with 10 unknowns -- introduction. II
• Hilbert's tenth problem is of unification type zero
• The Hilbert's-tenth-problem operator
• On the problem of the 10th discriminant
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• Hilbert's tenth problem for fixed \(d\) and \(n\)
• Existential definability and diophantine stability
• Extensions of Hilbert's tenth problem
• Note on Quantifier Prefixes Over Diophantine Equations
• Diagonal quadratic forms and Hilbert's Tenth Problem
• Universally defining Z$\mathbb {Z}$ in Q$\mathbb {Q}$ with 10 quantifiers
• Prime representing polynomial
• On the Diophantine complexity of the set of prime numbers
• Questions of decidability and undecidability in Number Theory
• Additional results to a theorem of Eisenträger and Everest
• Title not available (Why is that?)

This page was built for publication: Further results on Hilbert's tenth problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q829448)