Does there Exist an Algorithm which to Each Diophantine Equation Assigns an Integer which is Greater than the Modulus of Integer Solutions, if these Solutions form a Finite Set?

• Autorzy: Tyszka, A.
• Języki publikacji: EN

Abstrakty

EN

Let En = {xi = 1; xi + xj = xk; xi · xj = xk : i; j; k ∈ {1,...,n}}. We conjecture that if a system S ⊆ E_n has only finitely many solutions in integers x1,...,xn, then each such solution (x1,...,xn) satisfies |x1|,...,|xn| ≤ 2²ⁿ⁻¹. Assuming the conjecture, we prove: (1) there is an algorithm which to each Diophantine equation assigns an integer which is greater than the heights of integer (non-negative integer, rational) solutions, if these solutions form a finite set, (2) if a set M Í \mathbbN is recursively enumerable but not recursive, then a finite-fold Diophantine representation of M does not exist.

Słowa kluczowe

EN

Davis-Putnam-Robinson-Matiyasevich theorem; Matiyasevich's conjecture on finite-fold Diophantine representations; algorithms; diophantine equations; integers; modules algebra; infinite; set theory

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 125, nr 1
• Strony: 85--99
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Tyszka, A.

• Faculty of Production and Power Engineering, University of Agriculture, Poland,

Bibliografia

• [1] M. Davis, On the number of solutions of Diophantine equations, Proc. Amer. Math. Soc. 35 (1972), no. 2, 552-554, http://www.jstor.org/stable/2S37646.
• [2] M. Davis, Yu. Matiyasevich, J. Robinson, Hilbert’s tenth problem. Diophantine equations: positive aspects of a negative solution, in: Mathematical developments arising from Hilbert problems (ed. F. E. Browder), Proc. Sympos. Pure Math., vol. 28, Part 2, Amer. Math. Soc., 1976, 323-378; reprinted in: The collected works of Julia Robinson (ed. S. Feferman), Amer. Math. Soc., 1996, 269-324.
• [3] L. B. Kuijer, Creating a diophantine description of a r.e. set and on the complexity of such a description, MSc thesis, Faculty of Mathematics and Natural Sciences, University of Groningen, 2010, http://irs. ub.rug.nl/dbi/4b87adf513823.
• [4] Yu. Matiyasevich, Hilbert’s tenth problem, MIT Press, Cambridge, MA, 1993.
• [5] Yu. Matiyasevich, Hilbert’s tenth problem: what was done and what is to be done. Hilbert’s tenth problem: relations with arithmetic and algebraic geometry (Ghent, 1999), 1-47, Contemp. Math. 270, Amer. Math. Soc., Providence, RI, 2000.
• [6] Yu. Matiyasevich, Towards finite-fold Diophantine representations, Zap. Nauchn. Sem. S.-Petersburg. Otdel. Mat. Inst. Steklov. (POMI) 377 (2010), 78-90, ftp://ftp.pdmi.ras.ru/pub/publicat/znsl/v377/p078.pdf.
• [7] W. Narkiewicz, Number theory, World Scientific, Singapore, 1983.
• [8] I. Niven, Quadratic Diophantine equations in the rational and quadratic fields, Trans. Amer. Math. Soc. 52 (1942), 1-11.
• [9] A. Schinzel, Integer points on conics, Comment. Math. Prace Mat. 16 (1972), 133-135, Erratum 17 (1973), 305.
• [10] M. Waldschmidt, Open Diophantine problems, Mosc. Math. J. 4 (2004), no. 1, 245-305, http://arxiv. org/abs/math/®31244®.