We consider IOpen, the subsystem of PA (Peano Arithmetic) with the induction scheme restricted to quantifier-free formulas. We prove that each model of IOpen can be embedded in a model where the equation x 2 1 + x 2 2 + x 2 3 + x 2 4 = a has a solution. The main lemma states that there is no polynomial f(x,y) with coefficients in a (nonstandard) DOR M such that $|f(x,y)| for every (x,y) ∈ C, where C is (...) the curve defined on the real closure of M by C: x 2 + y 2 = a and $a > 0$ is a nonstandard element of M. (shrink)

A new method of coding Diophantine equations is introduced. This method allows checking that a coded sequence of natural numbers is a solution of a coded equation without decoding; defining by a purely existential formula, the code of an equation equivalent to a system of indefinitely many copies of an equation represented by its code. The new method leads to a much simpler construction of a universal Diophantine equation and to the existential arithmetization of Turing machines, register (...) machines, and partial recursive functions. (shrink)

We show how to determine the k-th bit of Chaitin’s algorithmically random real number Ω by solving k instances of the halting problem. From this we then reduce the problem of determining the k-th bit of Ω to determining whether a certain Diophantine equation with two parameters, k and N , has solutions for an odd or an even number of values of N . We also demonstrate two further examples of Ω in number theory: an exponential Diophantine (...) equation with a parameter k which has an odd number of solutions iff the k-th bit of Ω is 1, and a polynomial of positive integer variables and a parameter k that takes on an odd number of positive values iff the k-th bit of Ω is 1. (shrink)

A new proof is given of the celebrated theorem of M. Davis, H. Putnam and J. Robinson concerning exponential Diophantine representation of recursively enumerable predicates. The proof goes by induction on the defining scheme of a partial recursive function.

This article examines the research of Louis J. Mordell on the Diophantine equation y2-k=x3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$y^2-k=x^3$$\end{document} as it appeared in one of his first papers, published in 1914. After presenting a number of elements relating to Mordell’s mathematical youth and his (problematic) writing, we analyze the 1914 paper by following the three approaches he developed therein, respectively, based on the quadratic reciprocity law, on ideal numbers, and on binary cubic forms. This analysis (...) allows us to describe many of the difficulties in reading and understanding Mordell’s proofs, difficulties which we make explicit and comment on in depth. (shrink)

Classical results of additive number theory lead to the undecidability of the existence of solutions for diophantine equations in given special sets of integers. Those sets which are images of polynomials are covered by a more general result in the second section. In contrast, restricting diophantine equations to images of exponential functions with natural bases leads to decidable problems, as proved in the third section.

A recent proposal to solve the halting problem with the quantum adiabatic algorithm is criticized and found wanting. Contrary to other physical hypercomputers, where one believes that a physical process “computes” a (recursive-theoretic) non-computable function simply because one believes the physical theory that presumably governs or describes such process, believing the theory (i.e., quantum mechanics) in the case of the quantum adiabatic “hypercomputer” is tantamount to acknowledging that the hypercomputer cannot perform its task.

We show that if R is a nonconstant regular (semi-)local subring of a rational function field over an algebraically closed field of characteristic zero, Hilbert's Tenth Problem for this ring R has a negative answer; that is, there is no algorithm to decide whether an arbitrary Diophantine equation over R has solutions over R or not. This result can be seen as evidence for the fact that the corresponding problem for the full rational field is also unsolvable.

A previously unexplored method, combining logical and mathematical elements, is shown to yield substantial numerical improvements in the area of Diophantine approximations. Kreisel illustrated the method abstractly by noting that effective bounds on the number of elements are ensured if Herbrand terms from ineffective proofs of Σ 2 -finiteness theorems satisfy certain simple growth conditions. Here several efficient growth conditions for the same purpose are presented that are actually satisfied in practice, in particular, by the proofs of Roth's theorem (...) due to Roth himself and to Esnault and Viehweg. The analysis of the former yields an exponential bound of order exp(70ε -2 d 2 ) in place of exp(285ε -2 d 2 ) given by Davenport and Roth in 1955, where α is (real) algebraic of degree d ≥ 2 and $|\alpha - pq^{-1}| . (Thus the new bound is less than the fourth root of the old one.) The new bounds extracted from the other proof are polynomial of low degree (in ε -1 and log d). Corollaries: Apart from a new bound for the number of solutions of the corresponding Diophantine equations and inequalities (among them Thue's inequality), $\log \log q_\nu , where q ν are the denominators of the convergents to the continued fraction of α. (shrink)

We propose and investigate a uniform modal logic framework for reasoning about topology and relative distance in metric and more general distance spaces, thus enabling the comparison and combination of logics from distinct research traditions such as Tarski’s for topological closure and interior, conditional logics, and logics of comparative similarity. This framework is obtained by decomposing the underlying modal-like operators into first-order quantifier patterns. We then show that quite a powerful and natural fragment of the resulting first-order logic can be (...) captured by one binary operator comparing distances between sets and one unary operator distinguishing between realised and limit distances . Due to its greater expressive power, this logic turns out to behave quite differently from both and conditional logics. We provide finite axiomatisations and ExpTime-completeness proofs for the logics of various classes of distance spaces, in particular metric spaces. But we also show that the logic of the real line is not recursively enumerable. This result is proved by an encoding of Diophantine equations. (shrink)

We use nonstandard methods, based on iterated hyperextensions, to develop applications to Ramsey theory of the theory of monads of ultrafilters. This is performed by studying in detail arbitrary tensor products of ultrafilters, as well as by characterising their combinatorial properties by means of their monads. This extends to arbitrary sets and properties methods previously used to study partition regular Diophantine equations on. Several applications are described by means of multiple examples.

This paper develops a proof theory for logical forms of proofs in the case of monadic languages. Among the consequences are different kinds of generalization of proofs in various schematic proof systems. The results use suitable relations between logical properties of partial proof data and algebraic properties of corresponding sets of linear diophantine equations.

We present a new method for expressing Chaitin’s random real, Ω, through Diophantine equations. Where Chaitin’s method causes a particular quantity to express the bits of Ω by fluctuating between finite and infinite values, in our method this quantity is always finite and the bits of Ω are expressed in its fluctuations between odd and even values, allowing for some interesting developments. We then use exponential Diophantine equations to simplify this result and finally show how both (...) methods can also be used to create polynomials which express the bits of Ω in the number of positive values they assume. (shrink)

By the middle of the nineteenth century, it had become clear to mathematicians that the study of finite field extensions of the rational numbers is indispensable to number theory, even if one’s ultimate goal is to understand properties of diophantine expressions and equations in the ordinary integers. It can happen, however, that the “integers” in such extensions fail to satisfy unique factorization, a property that is central to reasoning about the ordinary integers. In 1844, Ernst Kummer observed that (...) unique factorization fails for the cyclotomic integers with exponent 23, i.e. the ring Z[ζ] of integers of the field Q(ζ), where ζ is a primitive twenty-third root of unity. In 1847, he published his theory of “ideal divisors” for cyclotomic integers with prime exponent. This was to remedy the situation by introducing, for each such ring of integers, an enlarged domain of divisors, and showing that each integer factors uniquely as a product of these. He did not actually construct these integers, but, rather, showed how one could characterize their behavior qua divisibility in terms of ordinary operations on the associated ring of integers. (shrink)

§1. Introduction. With Hrushovski's proof of the function field Mordell-Lang conjecture [16] the relevance of geometric stability theory to diophantine geometry first came to light. A gulf between logicians and number theorists allowed for contradictory reactions. It has been asserted that Hrushovski's proof was simply an algebraic argument masked in the language of model theory. Another camp held that this theorem was merely a clever one-off. Still others regarded the argument as magical and asked whether such sorcery could unlock (...) the secrets of a wide coterie of number theoretic problems.In the intervening years each of these prejudices has been revealed as false though such attitudes are still common. The methods pioneered in [16] have been extended and applied to a number of other problems. At their best, these methods have been integrated into the general methods for solving diophantine problems. Moreover, the newer work suggests limits to the application of model theory to diophantine geometry. For example, all such known applications are connected with commutative algebraic groups. This need not be an intrinsic restriction, but its removal requires serious advances in the model theory of fields. (shrink)

We show that Matijasevič's Theorem on the diophantine representation of r.e. predicates is provable in the subsystem I ∃ - 1 of Peano Arithmetic formed by restricting the induction scheme to diophantine formulas with no parameters. More specifically, I ∃ - 1 ⊢ IE - 1 + E ⊢ Matijasevič's Theorem where IE - 1 is the scheme of parameter-free bounded existential induction and E is an ∀∃ axiom expressing the existence of a function of exponential growth. We (...) conclude by examining the consequences of these results to the structure of countable nonstandard models of IE - 1. (shrink)

We investigate the issues of Diophantine definability over the non-finitely generated version of non-degenerate modules contained in the infinite algebraic extensions of the rational numbers. In particular, we show the following. Let k be a number field and let K inf be a normal algebraic, possibly infinite, extension of k such that k has a normal extension L linearly disjoint from K inf over k. Assume L is totally real and K inf is totally complex. Let M inf be (...) a non-degenerate O k -module, possibly non-finitely generated and contained in O Kinf . Then M inf contains a submodule M¯ inf such that M inf /M¯ inf is torsion and O k has a Diophantine definition over M¯ inf. (shrink)

Simple observations on diophantine definability over finite commutative rings lead to a characterization of those rings in terms of their diophantine behavior.

We show that Diophantine equivalence of two suitably presented countable rings implies that the existential polynomial languages of the two rings have the same "expressive power" and that their Diophantine sets are in some sense the same. We also show that a Diophantine class of countable rings is contained completely within a relative enumeration class and demonstrate that one consequence of this fact is the existence of infinitely many Diophantine classes containing holomophy rings of Q.