Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Along the lines of Polynomial representing all nonnegative integers, but likely well-known question:

is there a polynomial $f \in \mathbb Q[x_1, \dots, x_n]$ such that $f(\mathbb Z\times\mathbb Z\times\dots\times\mathbb Z) = P$, the set of primes?

share|improve this question
add comment

1 Answer

up vote 18 down vote accepted

No. Any such polynomial would have the property that any of its restrictions $f(x)$ to one variable consist only of primes, but this is easily seen to be impossible, since if $p(a)$ is prime then $p(k p(a) + a)$ is divisible by $p(a)$. (Even accounting for the coefficients in $\mathbb{Q}$ is straightforward by multiplying by the common denominator and using CRT; in fact, we can show that given an integer polynomial $q(x)$ and a positive integer $n$ there exists $x_n$ such that $q(x_n)$ is divisible by $n$ distinct primes.)

However, there do exist multivariate polynomials with the property that their positive integer outputs consist of the set of primes. See the Wikipedia article.

share|improve this answer
5  
<a href="mathdl.maa.org/images/upload_library/22/Ford/…; is a reference. It is a consequence of the work of Davis, Putnam, Robinson, and Matiyasevich on Hilbert's 10th problem that the statement about positive integer outputs holds not only for the set of prime numbers, but also for any set of positive integers that can be the output of a computer program. –  Bjorn Poonen Dec 27 '09 at 0:38
1  
I believe mathworld.wolfram.com/Prime-GeneratingPolynomial.html has references. –  Gjergji Zaimi Dec 27 '09 at 0:39
    
Thanks, wonderful references! @Bjorn, references in comments don't need any tag: mathdl.maa.org/images/upload_library/22/Ford/… –  Ilya Nikokoshev Dec 27 '09 at 0:45
add comment

Your Answer

 
discard

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.