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?
$\begingroup$
$\endgroup$
asked Dec 27, 2009 at 0:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
answered Dec 27, 2009 at 0:30
-
5$\begingroup$ <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. $\endgroup$ Commented Dec 27, 2009 at 0:38
-
1$\begingroup$ I believe mathworld.wolfram.com/Prime-GeneratingPolynomial.html has references. $\endgroup$ Commented Dec 27, 2009 at 0:39
-
$\begingroup$ Thanks, wonderful references! @Bjorn, references in comments don't need any tag: mathdl.maa.org/images/upload_library/22/Ford/… $\endgroup$ Commented Dec 27, 2009 at 0:45