# How to express the powers of two by a Diophantine equation?

Let $P_2:=\{2^k | k\in\mathbb N\}$ be the set of powers of two. I would like to "see" a polynomial $p(z_1,\ldots,z_r)$ with integer coefficients for which $P_2 =\{n\in\mathbb N | n=p(z_1,\ldots,z_r)\text{ with }z_1,\ldots,z_r\in\mathbb Z\}$. This should be possible, because $P_2$ is clearly recursively enumerable. If it should be easier to present such a polynomial for the set of powers of another prime number, or for the set of Fibonacci numbers, this would be sufficient for me as well.

-

For the Fibonacci numbers, full details are given in this paper by Jones.

-
The fourth page of this paper gives some insight into the fact that the problem posed by Thomas Klimpel is non-trivial: Matijasevic finished the solution of 10th Hilbert's problem basically just by solving Thomas's problem. – xyzzyz Jun 9 '13 at 15:25
Not exactly, as Jones considers $\{n\in \mathbb N\mid n=p(z_1,\ldots,z_r)\text{ with }z_1,\ldots,z_r\in\mathbb N\}$ instead. But of course this can easily be cured essentially by substituting $y$ with the sum of four squares. – Hagen von Eitzen Jun 9 '13 at 15:47
@xyzzyz I hope that the wording of the question makes it clear that the question might be answerable because somebody already published the answer, not because the answer itself would be easy to compute. Of course, before Matijasevic we didn't even know that there exists a way to compute answers to such questions. – Thomas Klimpel Jun 9 '13 at 16:10