Further results on Hilbert's tenth problem

DOI10.1007/S11425-020-1813-5MaRDI QIDQ829448zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 6 May 2021

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

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

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)

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.

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

Cites work

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

Cited in

(16)

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

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)