# About polynomials which can represent every prime number

A friend of mine taught me the followings :

It has been known that there are some polynomials which can represent every prime number.

1. The $21$st degree polynomial with $21$ variables by Matiyasevich in $1971$.

2. A polynomial with $14$ variables by Matiyasevich and J.Robinson in $1975$.

3. A polynomial with $10$ variables by Matiyasevich.

4. The following polynomial $F(a,b,\cdots,z)$ is by James P. Jones. This is the $25$th degree polynomial with $26$ variables. If the value of $F(a,b,\cdots,z)$ is positive, then the value is a prime number. In addition to this, $F(a,b,\cdots,z)$ can represent every prime number. $$F(a,b,\cdots,z)=(k+2)\left(1-{f_1}^2-{f_2}^2-\cdots-{f_{14}}^2\right)$$ $$f_1(a,b,\cdots,z)=wz+h+j-q,$$ $$f_2(a,b,\cdots,z)=(gk+2g+k+1)(h+j)+h-z,$$ $$f_3(a,b,\cdots,z)=16(k+1)^3(k+2)(n+1)^2+1-f^2,$$ $$f_4(a,b,\cdots,z)=p+q+z+2n-e,$$ $$f_5(a,b,\cdots,z)=e^3(e+2)(a+1)^2+1-o^2,$$ $$f_6(a,b,\cdots,z)=(a^2-1)y^2+1-x^2,$$ $$f_7(a,b,\cdots,z)=16(a^2-1)r^2y^4+1-u^2,$$ $$f_8(a,b,\cdots,z)=[\{a+u^2(u^2-a)\}^2-1](n+4dy)^2+1-(x+cu)^2,$$ $$f_9(a,b,\cdots,z)=(a^2-1)l^2+1-m^2,$$ $$f_{10}(a,b,\cdots,z)=k+1+i(a-1)-l,$$ $$f_{11}(a,b,\cdots,z)=n+l+v-y,$$ $$f_{12}(a,b,\cdots,z)=p+l(a-n-1)+b\{2a(n+1)-(n+1)^2-1\}-m,$$ $$f_{13}(a,b,\cdots,z)=q+y(a-p-1)+s\{2a(p+1)-(p+1)^2-1\}-x,$$ $$f_{14}(a,b,\cdots,z)=z+pl(a-p)+t(2ap-p^2-1)-pm.$$

It is known that the following has been proven :

"$k+2$ is a prime number $\iff$ there exist $(a,b,\cdots,z)$ such that $f_1=f_2=\cdots=f_{14}=0$."

Hence, if $F(a,b,\cdots,z)\gt0$, then $f_1=f_2=\cdots=f_{14}=0$ leads that $F(a,b,\cdots,z)=k+2$ is a prime number.

On the other hand, if $P$ is a prime number, then there exists an integer $k$ such that $P=k+2$. Hence, for $(a,b,\cdots,z)$ such that $f_1=f_2=\cdots=f_{14}=0$, $F(a,b,\cdots,z)=(k+2)\left(1-{f_1}^2-{f_2}^2-\cdots-{f_{14}}^2\right)=k+2=P$.

Now we know that $F(a,b,\cdots,z)$ can represent every prime number.

By the way, it can be easily proven that no polynomial with one variable can represent every prime number.

Proof : Supposing that $f(x)=a_0x^m+a_1x^{m-1}+\cdots+a_m$ can represent every prime number, $a_0\gt0$ is needed. Then, $f(x)$ is positive if $x$ is greater than a value $x_0$. Since if $x\ge x_0$, then $f(x)$ monotonically increases, $f(n)\gt0$ for a natural number $n$ such that $x_0\le n$. Hence, we get $f(n+P)\gt f(n)=P$. However, for a natural number $k$, $$f(n+P)=a_0(n+P)^m+\cdots+a_m=a_0n^m+\cdots+a_m+P\cdot k=P(1+k).$$ Since this means $f(n+P)$ is a composite number, we now know that there exist no polynomial with one variable such that if $f(n)\gt 0$, then $f(n)$ is a prime number. Now the proof is completed.

It is said that though it is possible to have such polynomial with two variables, the degree of such polynomial would be huge.

Note that the above does not say that $F(a,b,\cdots,z)$ is a prime number for every $(a,b,\cdots,z)$.

Remark : This seems to be related with Hilbert's tenth problem.

Then, here is my question.

Your presentation is misleading. The polynomial $x$ certainly represents every prime number. The property of the polynomials you discuss is that they represent every prime number AND the only positive integers they represent are the primes. They may represent many negative integers which could be negatives of composites. As for recent results, you might try typing "Hilbert's tenth problem" into the web, and seeing what comes back at you. Then you can write up a summary, and post it here. –  Gerry Myerson Sep 23 '13 at 12:53