Existential Diophantine definability of string length (Q2419123)

From MaRDI portal
Revision as of 01:10, 20 March 2024 by Openalex240319060354 (talk | contribs) (Set OpenAlex properties.)
scientific article
Language Label Description Also known as
English
Existential Diophantine definability of string length
scientific article

    Statements

    Existential Diophantine definability of string length (English)
    0 references
    0 references
    29 May 2019
    0 references
    The main result of the paper under review concerns a Diophantine definition of exponentiation over \(\mathbb N\) constructed by Yu. Matiyasevich as a final part of the solution of Hilbert's Tenth Problem. (The other parts of the solution are due to M. Davis, H. Putnam and J. Robinson.) The result of Matyasevich says that there exists a polynomial equation \(P(x, y, u_1,\ldots, u_r)\) with coefficients in \(\mathbb{Z}\) such that for all pairs \((x,y) \in \mathbb N^2\) \[ \exists u_1,\ldots,u_r \in \mathbb N^r: P(x, y, u_1,\ldots, u_r)=0 \] if and only if \(y=2^x\). The author claims that at least two of the variables \(u_1,\ldots,u_r\) have binary representation of length doubly exponential in \(x\). More precisely, the claim is that the lower bound on the string length is \(2^{2^{\Omega(x)}}\). Unfortunately, the reviewer was not able to find the definition of \(\Omega(x)\) in the article. The proof relies on some basic facts concerning Diophantine definitions over positive integers and contains numerous typos.
    0 references
    existential Diophantine
    0 references
    integer exponentiation
    0 references
    doubly exponential size
    0 references

    Identifiers