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

  • 1
    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.2011-08-26
  • 0
    See also http://en.wikipedia.org/wiki/Formula_for_primes#Formula_based_on_a_system_of_Diophantine_equations2011-08-26
  • 0
    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.)2011-08-26
  • 0
    @Yuval: that's right, sorry. Corrected.2011-08-27
  • 1
    @lhf: is there anything on that page that sheds light on my question? Sorry if I'm missing it...2011-08-27
  • 0
    @Alon, "[there] is a polynomial inequality in 26 variables, and the set of prime numbers is identical to the set of positive values taken on by this polynomial inequality as the variables range over the nonnegative integers.". But, no, it does not say anything about fewer variables.2011-08-27
  • 0
    Why cant it be 1 variable?2011-08-27
  • 0
    @grok_it, if $p(x) \in \mathbb{Z}[x]$ is any nonconstant polynomial with integer coefficients and $a, b \in \mathbb{N}$, then there is a nonconstant polynomial $q(x) \in \mathbb{Z}[x]$ such that $p(an+b) = aq(n)+p(b)$ for all $n \in \mathbb{Z}$. Now choose $b$ such that $p(b)>1$ and set $a=p(b)$ to find (infinitely many) values of $p(x)$ that are divisible by $p(b)$.2011-08-28
  • 0
    @grok_it: A one-variable polynomial grows too fast. If the leading term is $ax^n$, then successive values differ by more than $ax^{n-1}/2$ for sufficiently large $x$, whereas successive primes differ by about $\log x$ on average.2011-09-01
  • 0
    @lhf I had an "answer" posted. Then I realized that $p(x,y)$ is allowed to take negative values, even for positive inputs. I realized that exactly as I was trying to figure out why the argument didn't generalize to 3 variables. I've deleted my answer while I think about it more.2011-09-01
  • 0
    Very interesting question. I've thought a bit about it but the problem has resisted my (rather clumsy) attacks.2011-09-09

2 Answers 2

7

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).

3

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.