33
$\begingroup$

In "The New Book of Prime Number Records", Ribenboim reviews the known results on the degree and number of variables of prime-representing polynomials (those are polynomials such that the set of positive values they obtain for nonnegative integral values of the variables coincides with the set of primes). For example, it is known that there is such a polynomial with 42 variables and degree 5, as well as one with 10 variables and astronomical degree.

Ribenboim mentions that it's an open problem to determine the least number of variables possible for such a polynomial, and remarks "it cannot be 2". It's a fairly simple exercise to show that it cannot be 1, but why can't it be 2?

EDIT: here's the relevant excerpt from Ribenboim's book. Given that nobody seems to be familiar with such a proof, I'm inclined to assume that this is a typo and he just meant "it cannot be 1".

Excerpt from "The New Book of Prime Number Records"

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ You mean "the set of positive values that they obtain for non-negative values of the inputs coincides with the set of prime numbers". Otherwise I can suggest $-1$, $2 - 3x^2$ and so on. $\endgroup$ – Yuval Filmus Aug 26 '11 at 10:02
  • $\begingroup$ See also en.wikipedia.org/wiki/… $\endgroup$ – lhf Aug 26 '11 at 11:43
  • $\begingroup$ There actually is a polynomial $f(p,x_1,\ldots,x_n)$ with integer coefficients such that $p$ is a positive prime if and only if $\exists x_1,\ldots,x_n\in \mathbb{Z}\ f(p,x_1,\ldots,x_n) = 0$. I think it's a 4th-degree polynomial in 14 variables or something like that. (But ignore this comment, unless you don't ignore it.) $\endgroup$ – Michael Hardy Aug 26 '11 at 18:17
  • $\begingroup$ @Yuval: that's right, sorry. Corrected. $\endgroup$ – Alon Amit Aug 27 '11 at 1:03
  • 1
    $\begingroup$ @lhf: is there anything on that page that sheds light on my question? Sorry if I'm missing it... $\endgroup$ – Alon Amit Aug 27 '11 at 1:04
7
$\begingroup$

I asked the same question at MathOverflow (linking here) where I noted that, at least as of 1982, the problem was still open because even universal Diophantine equations were not known to be impossible with two variables.

On further searching I found a FOM posting (see link above) which shows that the universal Diophantine equation problem is still open, so it looks like Ribenboim's book is in error (probably a typo, as Alon suggests).

Improve this answer
$\endgroup$
2
$\begingroup$

Given all the evidence so far, I'm inclined to declare Ribenboim's parenthetic remark a typo. He probably meant either "it cannot be 1" or "it must be at least 2". It would be confusing and unusual for him to mention this off-hand with no reference as if it's a simple observation. That it certainly isn't.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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