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

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.