Existential Diophantine definability of string length (Q2419123): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Q2715533 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hilbert's Tenth Problem is Unsolvable / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4115143 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3856819 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Defining \(\mathbb Z\) in \(\mathbb Q\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2715528 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3992465 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2715529 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2715530 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3423328 / rank
 
Normal rank

Latest revision as of 09:41, 19 July 2024

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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers