Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-31T19:42:00.991Z Has data issue: false hasContentIssue false
  • English
  • Français

Extensions of Hilbert's tenth problem

Published online by Cambridge University Press:  12 March 2014

Thanases Pheidas
Thanases Pheidas*
Affiliation:
Department of Mathematics, University of Crete, Heraklion, Crete, Greece, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

The present article is an attempt to bridge the gap between the researchers that work in the areas adjacent to Hilbert's Tenth Problem (for short, HTP), mainly, number theory and mathematical logic. It presents the main results that have been obtained and asks some of the open questions in the area, leading to the main unanswered question (at least in the opinion of the author)—the analogue of HTP for the rational numbers. In this respect, the article is a successor of [Da] where the reader can find more information on the solution of the initial problem. Most of the results that are presented are not new, but some of the proofs are. As the purpose of a survey article is the “unification” of the methods involved, we present a proof of the analogue of HTP in the case of polynomial rings which is more geometric in nature than the initial proof of Denef (although it uses essentially the same tools). This allows, in our opinion, an easy introduction to the utilisation of the concepts used in the more recent approaches, like that of elliptic curves. We must say that the approach to the subject that we suggest through the questions we ask (mostly consisting of generalisations of HTP to various algebraic and analytic domains) is not the only one.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 59 , Issue 2 , June 1994 , pp. 372 - 397
Copyright
Copyright © Association for Symbolic Logic 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[Ab] Aberth, O., The failure in computable analysis of a classical existence theorem for differential equations, Proceedings of the American Mathematical Society, vol. 30 (1971), pp. 151.CrossRefGoogle Scholar
[Ad] Adler, A., A reduction of homogeneous diophantine problems, Journal of the London Mathematical Society, vol. 3 (1971), pp. 446–448.CrossRefGoogle Scholar
[Ax1] Ax, J., On the undecidability of power series fields, Proceedings of the American Mathematical Society, vol. 16 (1966), pp. 846.Google Scholar
[Ax2] Ax, J., Solving diophantine equations modulo every prime, Annals of Mathematics, vol. 85 (1967), pp. 161–183.CrossRefGoogle Scholar
[Ax3] Ax, J., The elementary theory of finite fields, Annals of Mathematics, vol. 88 (1968), pp. 239–271.CrossRefGoogle Scholar
[AK] Ax, J. and Kochen, S., Diophantine problems over local fields: Decidable fields, Annals of Mathematics, vol. 83 (1966), pp. 437–456.CrossRefGoogle Scholar
[BDL] Becker, J., Denef, J., and Lipshitz, L., Further remarks on the elementary theory of power series rings, vol. 834, Lecture Notes in Mathematics, Springer-Verlag, Berlin and New York, 1980.Google Scholar
[BDLV] Becker, J., Denef, J., Lipshitz, L., and van den Dries, L., Ultraproducts and approximation in local rings I, Inventiones Mathematics, vol. 51 (1979), pp. 189–203.CrossRefGoogle Scholar
[Be] Beltyukov, A., Decidability of the universal theory of the natural numbers with addition and divisibility, Seminars of the Steklov Mathematical Institute, vol. 60 (1976), pp. 15–28, (Russian)Google Scholar
[Br] Britton, J., Integer solutions of systems of quadratic equations, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 86 (1979), pp. 385–389.CrossRefGoogle Scholar
[Ch1] Cherlin, G., Model theoretic algebra, this Journal, vol. 41 (1976), pp. 537.Google Scholar
[Ch2] Cherlin, G., Undecidability of rational function fields in nonzero characteristic, Logic Colloquium '82 (Lolli, G., Longo, G., and Marcja, A., editors), North-Holland, Amsterdam, 1984, pp. 85–95.CrossRefGoogle Scholar
[Ch3] Cherlin, G., Rings of continuous functions: decision problems, Lecture Notes in Mathematics, vol. 834, Springer-Verlag, Berlin and New York, 1980.Google Scholar
[Ch4] Cherlin, G. and Jarden, M., Undecidability of some elementary theories over PAC fields, preprint.Google Scholar
[CP] Cherlin, G. and Point, F., On extensions of Presburger arithmetic, Proceedings of the Fourth Easter Conference on Model Theory, Humboldt University, 1986, pp. 17–34.Google Scholar
[Co] Cohen, P., Decision procedures for real and p-adic fields, Communications on Pure and Applied Mathematics, vol. 22 (1969), pp. 131–151.CrossRefGoogle Scholar
[Da] Davis, M., Hilbert's tenth problem is unsolvable, American Mathematical Monthly, vol. 80 (1973), pp. 233–269.CrossRefGoogle Scholar
[DMR] Davis, M., Matjasevic, Y., and Robinson, J., Hilbert's tenth problem, Diophantine equations: positive aspects of a negative solution, Proceedings of Symposia in Pure Mathematics, vol. 28, American Mathematical Society, Providence, RI, 1976, pp. 323–378.Google Scholar
[D] Delon, F., Dans les anneaux de series formelles, preprint.Google Scholar
[De1] Denef, J., Hilbert's tenth problem for quadratic rings, Proceedings of the American Mathematical Society, vol. 48 (1975), pp. 214–220.Google Scholar
[De2] Denef, J., Diophantine sets over Z[T], Proceedings of the American Mathematical Society, vol. 69 (1978), pp. 148–150.Google Scholar
[De3] Denef, J., The diophantine problem for polynomial rings and fields of rational functions, Transactions of the American Mathematical Society, vol. 242 (1978), pp. 391–399.CrossRefGoogle Scholar
[De4] Denef, J., The diophantine problem for polynomial rings of positive characteristic, Logic Colloquium 78 (Boffa, M., van Dalen, D., and McAloon, K., editors), North-Holland, Amsterdam, 1979, pp. 131–145.Google Scholar
[De5] Denef, J., Diophantine sets over algebraic integer rings II, Transactions of the American Mathematical Society, vol. 257 (1980), pp. 227–236.CrossRefGoogle Scholar
[De6] Denef, J., p-adic semi-algebraic sets and cell decomposition, Journal für die Reine und Angewandte Mathematik, vol. 369 (1986), pp. 154–166.Google Scholar
[DL] Denef, J. and Lipshitz, L., Diophantine sets over some rings of algebraic integers, Journal of the London Mathematical Society (2), vol. 18 (1978), pp. 385–391.CrossRefGoogle Scholar
[DG] Denef, J. and Gromov, (communication by Cherlin, G.), The ring of analytic functions in the disk has undecidable theory, 1985, letter.Google Scholar
[DV] Denef, J. and van den Dries, L., p-adic and real subanalytic sets, Annals of Mathematics, vol. 128 (1988), pp. 79–138.CrossRefGoogle Scholar
[E1] Ershov, Y., Undecidability of certain fields, Dokladii Akademii Nauk SSSR, vol. 161 (1965), pp. 27–29; English translation, Soviet Mathematics Doklady , vol. 161 (1965), pp. 349–252.Google Scholar
[E2] Ershov, Y., On the elementary theory of maximal normed fields, Soviet Mathematics Doklady, vol. 165–1 (1965), pp. 1390–1393.Google Scholar
[FS] Fried, M. and Sacerdote, G., Solving diophantine problems over all residue class fields of a number field and all finite fields, Annals of Mathematics, vol. 104 (1976), pp. 203–233.CrossRefGoogle Scholar
[G] Greenberg, M., Strictly local solutions of diophantine equations, Pacific Journal of Mathematics, vol. 51 (1974), pp. 143–153.CrossRefGoogle Scholar
[GS1] Grunewald, F. and Segal, D., How to solve a quadratic equation in the integers, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 89 (1981), pp. 1–5.CrossRefGoogle Scholar
[GS2] Grunewald, F. and Segal, D., Some general algorithms I and II, Annals of Mathematics, vol. 112 (1980), pp. 531–617.CrossRefGoogle Scholar
[HR] Henson, C. Ward and Rubel, L., Some applications of Nevanlinna theory to mathematical logic: identities of exponential functions, Transactions of the American Mathematical Society, vol. 282 (1984), pp. 1–32 (also corrections).Google Scholar
[J1] Jones, J., Diophantine representation of Mersenne and Fermat primes, Acta Arithmetica, vol. 35 (1979), pp. 209–221.CrossRefGoogle Scholar
[J2] Jones, J., Undecidable diophantine equations, Bulletin of the American Mathematical Society, vol. 3 (1980), pp. 859–862.CrossRefGoogle Scholar
[J3] Jones, J., Classification of quantifier prefixes over diophantine equations, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 27 (1981), pp. 403–410.CrossRefGoogle Scholar
[JM1] Jones, J. and Matjasevic, J., A new representation for the symmetric binomial coefficient and its applications, Les Annales des Sciences Mathématiques du Quebec, vol. VI (1982), pp. 81–97.Google Scholar
[JM2] Jones, J. and Matjasevic, J., Register machine proof of the theorem on exponential diophantine representation of enumerable sets, this Journal, vol. 49 (1984), pp. 818–829.Google Scholar
[JSWW] Jones, J., Sato, D., Wada, H., and Wiens, D., Diophantine representation of the set of prime numbers, American Mathematical Monthly, vol. 83 (1976), pp. 449–464.CrossRefGoogle Scholar
[KR1] Kim, K. and Roush, F., Problems equivalent to rational diophantine solvability, Journal of Algebra, vol. 124 (1989), pp. 493–505.CrossRefGoogle Scholar
[KR2] Kim, K. and Roush, F., Diophantine unsolvability over p-adic function fields, preprint.Google Scholar
[KR3] Kim, K. and Roush, F., Diophantine undecidability of C(t1, t2), Journal of Algebra, vol. 150 (1992), pp. 35–44.CrossRefGoogle Scholar
[KR4] Kim, K. and Roush, F., Diophantine unsolvability for function fields over certain infinite fields of characteristic p, Journal of Algebra (to appear).Google Scholar
[KR5] Kim, K. and Roush, F., Undecidability of parametric solutions of polynomial equations, Proceedings of the American Mathematical Society (to appear).Google Scholar
[KR6] Kim, K. and Roush, F., An approach to rational diophantine undecidability, Proceedings of the Asian Mathematical Conference, World Scientific Press, Singapore, 1992, pp. 242–257.Google Scholar
[KR7] Kim, K. and Roush, F., A decision procedure for certain abelian varieties over function fields, Journal of Algebra (to appear).Google Scholar
[KRB] Kim, K. and Roush, F., Quadratic forms over C[t1,t2], Journal of Algebra, vol. 140 (1991), pp. 65–82.CrossRefGoogle Scholar
[K] Koppel, M., Some decidable diophantine problems: positive solution to a problem of Davis, Matijasevic, and Robinson, Proceedings of the American Mathematical Society,, vol. 77 (1979), pp. 319.Google Scholar
[La] Lang, S., Elliptic functions, Graduate Texts in Mathematics, Springer-Verlag, New York, 1987.CrossRefGoogle Scholar
[L1] Lipshitz, L., Undecidable existential problems for addition and divisibility in algebraic number rings, II, Proceedings of the American Mathematical Society, vol. 64 (1977), pp. 122–128.CrossRefGoogle Scholar
[L2] Lipshitz, L., The Diophantine problem for addition and divisibility, Transactions of the American Mathematical Society, vol. 235 (1978), pp. 271–283.CrossRefGoogle Scholar
[L3] Lipshitz, L., Undecidable existential problems for addition and divisibility in algebraic number rings, Transactions of the American Mathematical Society, vol. 241 (1978), pp. 121–128.CrossRefGoogle Scholar
[L4] Lipshitz, L., Some remarks on the diophantine problem for addition and divisibility, Bulletin de la Société Mathématique de Belgique, vol. 33 (1981), pp. 41–52.Google Scholar
[L5] Lipshitz, L., p-adic zeroes of polynomials, Journal für die Reine und Angewandte Mathematik, vol. 390 (1988), pp. 208–214.Google Scholar
[LP] Lipshitz, L. and Pheidas, T., An analogue of Hilbert's tenth problem for p-adic entire functions, preprint.Google Scholar
[Mac] Macintyre, A., On definable subsets of p-adic fields, this Journal, vol. 41 (1976), pp. 605–610.Google Scholar
[MV] Macintyre, A. and van den Dries, L., The logic of Rumely's local-glocal principle, Journal für die Riene und Angewandte Mathematik, vol. 4 (1990).Google Scholar
[Mak] Makanin, G., The problem of solvability of equations in a free semigroup, Mathematicheskii Sbornik, vol. 103 (1977); English translation, Mathematics of the USSR-Sbornik , vol. 32 (1977), pp. 129–198.Google Scholar
[Mas] Mason, R., Diophantine equations over function fields, London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge and New York, 1984.CrossRefGoogle Scholar
[M1] Matiyasevic, Y., Enumerable sets are diophantine, Dokladii Akademii Nauk SSSR, vol. 191 (1970); English translation, Soviet Mathematics Doklady , vol. 11 (1970), pp. 354–358.Google Scholar
[M2] Matiyasevic, Y., On recursive unsolvability of Hilbert's tenth problem, Proceedings of the Fourth International Congress Logic Methodology in Philosophy of Science, Bucharest 1971, North-Holland, Amsterdam, 1973.Google Scholar
[M3] Matiyasevic, Y., Arithmetical representations of enumerable sets with a small number of quantifiers, Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Academii Nauk SSSR (LOMI), vol. 32 (1972); English translation, Journal of Soviet Mathematics , vol. 6 (1976), pp. 410–416.Google Scholar
[MR1] Matiyasevic, Y. and Robinson, J., Two universal three-quantifier representations of enumerable sets, Teopiya algorifmov u matematiceskala logika (dedicated to Markov, A. A.), Vycislitel'nyi Centr. Akademii Nauka SSSR, Moscow, 1974, pp. 112–123.Google Scholar
[MR2] Matiyasevic, Y. and Robinson, J., Reduction of an arbitrary diophantine equation to one in 13 unknowns, Acta Arithmetica, vol. 27 (1975), pp. 521–533.CrossRefGoogle Scholar
[M] Miller, C. III, Some connections between Hilbert's 10th problem and the theory of groups, Word problems (Boone, , Cannonito, , and Lyndon, , editors), North-Holland, Amsterdam, 1973, pp. 483–506.Google Scholar
[Pe] Penzin, Y., The undecidability of fields of rational functions over fields of characteristic 2, Algebra i Logica, vol. 12 (1973), pp. 205–210; English translation (1974), Plenum, New York, pp. 116–119.Google Scholar
[Ph1] Pheidas, T., The diophantine problem for addition and divisibility in polynomial rings, Ph.D. thesis, Perdue University, West Lafayette, Indiana, 1985.Google Scholar
[Ph2] Pheidas, T., An undecidability result for power series rings of positive characteristic, Proceedings of the American Mathematical Society, vol. 99 (1987), pp. 364–366.CrossRefGoogle Scholar
[Ph3] Pheidas, T., An undecidability result for power series rings of positive characteristic II, Proceedings of the American Mathematical Society, vol. 100 (1987), pp. 526–530.CrossRefGoogle Scholar
[Ph4] Pheidas, T., Hilbert's tenth problem for a class of rings of algebraic integers, Proceedings of the American Mathematical Society, vol. 104 (1988), pp. 611–620.Google Scholar
[Ph5] Pheidas, T., Hilbert's tenth problem for fields of rational functions over finite fields, Inventiones Mathematicae, vol. 103 (1991), pp. 1–8.CrossRefGoogle Scholar
[PR] Pour-El, M. and Richards, I., A computable ordinary differential equation which posses no computable solution, Annals of Mathematical Logic, vol. 17 (1979), pp. 61–90.CrossRefGoogle Scholar
[P] Prestel, A., Decidable theories of preordered fields, Mathematische Annalen, vol. 258 (1982>, pp. 481–492.CrossRefGoogle Scholar
[PS1] Prestel, A. and Schmid, J., Existentially closed domains with radical relations, preprint.Google Scholar
[PS2] Prestel, A. and Schmid, J., Decidability of the rings of real algebraic and p-adic algebraic integers, Journal für die Reine und Angewandte Mathematik, vol. 414 (1991>, pp. 141–148.Google Scholar
[R1] Richard, D., The arithmetics as theories of two orders, Annals of Discrete Mathematics, vol. 23 (1984), pp. 287–312.Google Scholar
[R2] Richard, D., All arithmetical sets of power of primes are first-order definable in terms of the successor function and the coprimeness predicate, Discrete Mathematics, vol. 53 (1985), pp. 221–247.CrossRefGoogle Scholar
[R3] Richard, D., Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility, this Journal, vol. 50 (1985), pp. 927–935.Google Scholar
[R4] Richard, D., Definissabilite de l'arithmetique par coprimarite et restrictions de l'addition ou de la multiplication, Comptes Rendus de l'Académie des Sciences. Série I. Mathematique, vol. 395 (1987), pp. 665–668.Google Scholar
[Ri] Richardson, D., Some undecidable problems involving elementary functions of a real variable, this Journal, vol. 233 (1968), pp. 514.Google Scholar
[Ro1] Robinson, J., Definability and decision problems in arithmetic, this Journal, vol. 14 (1949), pp. 98–114.Google Scholar
[Ro2] Robinson, J., Existential definability in arithmetic, Transactions of the American Mathematical Society, vol. 72 (1952), pp. 437–449.CrossRefGoogle Scholar
[Ro3] Robinson, J., The undecidibility of algebraic rings and fields, Proceedings of the American Mathematical Society, vol. 10 (1959), pp. 950–957.CrossRefGoogle Scholar
[Ro4] Robinson, J., Hilbert's tenth problem, Proceedings of Symposia in Pure Mathematics, American Mathematical Society, Providence, Rhode Island, vol. 20 (1971), pp. 191–194.Google Scholar
[Rob1] Robinson, R., Undecidable rings, Transactions of the American Mathematical Society, vol. 70 (1951), pp. 137.CrossRefGoogle Scholar
[Rob2] Robinson, R., The undecidability of pure transcendental extensions of real fields, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 10 (1964), pp. 275–282.CrossRefGoogle Scholar
[Rou] Rouani, Y., Indecidabilite dans un langage enrichi de corps de series formelles en characteristique positive, Thesis, 1986.Google Scholar
[Ru1] Rumely, R., Undecidability and definability for the theory of global fields, Transactions of the American Mathematical Society, vol. 262 (1980>, pp. 195–217.CrossRefGoogle Scholar
[Ru2] Rumely, R., Arithmetic over the ring of all algebraic integers, Journal für die Reine und Angewandte Mathematik, vol. 368 (1986).Google Scholar
[S1] Seidenberg, A., A new decision method for elementary algebra, Annals of Mathematics, vol. 60 (1954), pp. 365–374.CrossRefGoogle Scholar
[Se1] Semenov, A., Logical theories of one-place functions on the set of natural numbers, Mathematics of the USSR—Izvestiya, vol. 22 (1984), pp. 587–618.CrossRefGoogle Scholar
[Se2] Semenov, A., On the definability of arithmetic in its fragments, Soviet Mathematics Doklady, vol. 25 (1982), pp. 300–303.Google Scholar
[Sh1] Shlapentokh, A., Extension of Hilbert's tenth problem to some algebraic number fields, Communications on Pure and Applied Mathematics, vol. XLII (1989), pp. 939–962.CrossRefGoogle Scholar
[Sh2] Shlapentokh, A., Diophantine definitions for some polynomial rings, Communications on Pure and Applied Mathematics (to appear).Google Scholar
[SS] Shapiro, H. and Shlapentokh, A., Diophantine relationships between algebraic number fields, Communications on Pure and Applied Mathematics, vol. ILII (1989), pp. 1113–1122.CrossRefGoogle Scholar
[Sk] Skolem, T., Uber einige Satzfunctionen in der Arithmetik, Skriftser Videnskabs Akademiet i Oslo, vol. 7, pp. 1–28.Google Scholar
[T] Tarski, A., A decision method for elementary algebra and geometry, Monograph, The Rand Corporation.Google Scholar
[Te] Terrier, V., Decidability of the existential theory of the set of natural numbers with order, divisibility, power functions, power predicates and constants, Proceedings of the American Mathematical Society (to appear).Google Scholar
[V1] van den Dries, L., A generalization of the Tarski-Seidenberg theorem, and some nondefinability results, Bulletin of the American Mathematical Society, vol. 15 (1986), pp. 189–193.CrossRefGoogle Scholar
[V2] van den Dries, L., Alfred Tarski's elimination theory for real closed fields, this Journal, vol. 53 (1988>, pp. 7–19., pp. 7–19.' href=https://scholar.google.com/scholar?q=[V2]+van+den+Dries,+L.,+Alfred+Tarski's+elimination+theory+for+real+closed+fields,+this+Journal,+vol.+53+(1988>,+pp.+7–19.>Google Scholar
[V3] van den Dries, L., Elimination theory for the ring of algebraic integers, Journal für die Reine und Angewandte Mathematik, vol. 388 (1988), pp. 189–205.Google Scholar
[V4] van den Dries, L., On the elementary theory of restricted elementary functions, this Journal, vol. 53 (1988>, pp. 796–808.,+pp.+796–808.>Google Scholar
[V5] van den Dries, L. and Macintyre, A., The logic of Rumely's local-global principle, Journal für die Reine und Angewandte Mathematik, vol. 4 (1990), pp. 1–24.Google Scholar
[V7] van den Dries, L., The logic of local fields, A remark on Ax's theorem on solvability modulo primes, Cell decomposition in good Henselian fields, Weierstrass preparation with parameters, Analytic Ax-Kochen-Ershov theorems, notes, Strategies for sequential search and selection in real time (Bruss, F. Thomas, Ferguson, Thomas S., and Samuels, Stephen M., editors), Summer Research Conference, University of Massachusetts, Amherst, 06 1990, Contemporary Mathematics, vol. 125, American Mathematical Society, Providence, Rhode Island, 1992.Google Scholar
[W] Weispfenning, V., Quantifier elimination and decision procedures for valued fields, Models and sets, vol. 1103, Lecture Notes in Mathematics, Springer-Verlag, Berlin and New York, 1984, pp. 419–472.Google Scholar
[Z] Ziegler, M., Model theory of modules, Annals of Pure and Applied Mathematical Logic, vol. 26 (1984>, pp. 149–213.CrossRefGoogle Scholar