On the Relationship Between Matiyasevich’s and Smoryński’s Theorems

Published in Volume XXIX, Issue 1, 2019, pages 101–111, doi: 10.7561/SACS.2019.1.101

Authors: A. Peszek, A. Tyszka

Abstract

Let R be a non-zero subring of Q with or without 1. We assume that for every positive integer n there exists a computable surjection from N onto Rⁿ . Every R ∈ {Z, Q} satisfies these conditions. Matiyasevich’s theorem states that there is no algorithm to decide whether or not a given Diophantine equation has a solution in non-negative integers. Smoryński’s theorem states that the set of all Diophantine equations which have at most finitely many solutions in non-negative integers is not recursively enumerable. We prove: (1) Smoryński’s theorem easily follows from Matiyasevich’s theorem, (2) Hilbert’s Tenth Problem for solutions in R has a positive solution if and only if the set of all Diophantine equations with a finite number of solutions in R is recursively enumerable. “Hilbert’s Tenth Problem for solutions in R” is the problem of whether there exists an algorithm which for any given Diophantine equation with integer coefficients, can decide whether the equation has a solution with all unknowns taking values in R.

Full Text (PDF)

References

[1] M. Davis. On the Number of Solutions of Diophantine Equations. Proceedings of the American Mathematical Society 35(2), 552–554, 1972. doi:10.1090/S0002-9939-1972-0304347-1.

[2] M. Davis. Representation Theorems for Recursively Enumerable Sets and a Conjecture Related to Poonen’s Large Subring of Q. Journal of Mathematical Sciences 171(6), 728–730, 2010. doi:10.1007/s10958-010-0176-7.

[3] H. Friedman. Complexity of Statements. 1998. http://www.cs.nyu.edu/pipermail/fom/1998-April/001843.html.

[4] J.P. Jones. Universal Diophantine Equation. The Journal of Symbolic Logic 47(3), 549–571, 1982. doi:10.2307/2273588.

[5] M. Kim. On Relative Computability for Curves. Asia Pacific Mathematics Newsletter 3(2), 6–20, 2013. http://www.asiapacific-mathnews.com/03/0302/0016_0020.pdf.

[6] Y.V. Matiyasevich. Some Purely Mathematical Results Inspired by Mathematical Logic. In: R. E. Butts, J. Hintikka (Eds.). Logic, Foundations of Mathematics, and Computability Theory. The University of Western Ontario Series in Philosophy of Science 9, 121–127, 1977. doi:10.1007/978-94-010-1138-9_7.

[7] Y.V. Matiyasevich. Hilbert’s Tenth Problem. MIT Press, Cambridge, MA, 1993.

[8] K. Molenda, A. Peszek, M. Sporysz, A. Tyszka. Is There a Computable Upper Bound on the Heights of Rational Solutions of a Diophantine Equation with a Finite Number of Solutions? In M. Ganzha, L. Maciaszek, M. Paprzycki (Eds.) Proceedings of the 2017 Federated Conference on Computer Science and Information Systems. Annals of Computer Science and Information Systems (11), 249–258, IEEE Computer Society Press, 2017.  doi:10.15439/2017F42.

[9] A. Peszek, A. Tyszka. Hilbert’s 10th Problem for Solutions in a Subring of Q. arxiv:1909.05021, 2019.

[10] C. Smoryński. A Note on the Number of Zeros of Polynomials and Exponential Polynomials. The Journal of Symbolic Logic 42(1), 99–106, 1977. doi:10.2307/2272324.

[11] C. Smoryński. Logical Number Theory, vol. I. Springer, Berlin, 1991. doi:10.1007/978-3-642-75462-3.

Bibtex

@article{sacscuza:peszek2019orbmst,
  title={On the Relationship Between Matiyasevich’s and Smoryński’s Theorems},
  author={A. Peszek, A. Tyszka},
  journal={Scientific Annals of Computer Science},
  volume={29},
  number={1},
  organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
  year={2019},
  pages={101–111},
  publisher={Alexandru Ioan Cuza University Press, Ia\c si},
  doi={10.7561/SACS.2019.1.101}
}