Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.