4

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.

Thomas Klimpel
  • 7,396

1 Answers1

3

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

André Nicolas
  • 507,029
  • 2
    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 09 '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 09 '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 09 '13 at 16:10