2
$\begingroup$

A polynomial formula for the primes (with 26 variables) was presented by Jones, J., Sato, D., Wada, H. and Wiens, D. (1976). Diophantine representation of the set of prime numbers. American Mathematical Monthly, 83, 449-464.

The set of prime numbers is identical with the set of positive values taken on by the polynomial

$(k+2)(1-(wz+h+j-q)^2-((gk+2g+k+1)\cdot(h+j)+h-z)^2-(2n+p+q+z-e)^2-(16(k+1)^3\cdot(k+2)\cdot(n+1)^2+1-f^2)^2-(e^3\cdot(e+2)(a+1)^2+1-o^2)^2-((a^2-1)y^2+1-x^2)^2-(16r^2y^4(a^2-1)+1-u^2)^2-(((a+u^2(u^2-a))^2-1)\cdot(n+4dy)^2+1-(x+cu)^2)^2-(n+l+v-y)^2-((a^2-1)l^2+1-m^2)^2-(ai+k+1-l-i)^2-(p+l(a-n-1)+b(2an+2a-n^2-2n-2)-m)^2-(q+y(a-p-1)+s(2ap+2a-p^2-2p-2)-x)^2-(z+pl(a-p)+t(2ap-p^2-1)-pm)^2)$

as the variables range over the nonnegative integers.

I am asking if there exist a similar result for the primes of the form $n²+1$, i.e., this set of prime numbers is identical with the set of positive values taken on by certain polynomial.

Improve this question
$\endgroup$
6
  • $\begingroup$ The existence of infinitely many such primes is a conjecture of Landau, and is still open. If one had a polynomial representation, I would expect it to resolve the conjecture. $\endgroup$
    – Stopple
    Commented Jan 9, 2020 at 16:32
  • 2
    $\begingroup$ @Stopple: But, there exist a such polynomial for twin primes and Mersenne primes and no one can solve these conjectures. $\endgroup$
    – Safwane
    Commented Jan 9, 2020 at 16:35
  • $\begingroup$ @Stopple: A Note on Diophantine Representations Author(s): Christoph Baxa Source: The American Mathematical Monthly, Vol. 100, No. 2 (Feb., 1993), pp. 138-143 $\endgroup$
    – Safwane
    Commented Jan 9, 2020 at 16:37
  • 1
    $\begingroup$ If we call your polynomial $P$, how about $-c(X^2+1)(P - X^2 - 1)^2 + X^2 + 1$ for some $c>1$? This will be negative if $P \neq X^2+1$, but if there is equality it will be equal to the prime $P = X^2+1$. Or am I making some silly mistake here? $\endgroup$
    – R.P.
    Commented Jan 9, 2020 at 16:39
  • 2
    $\begingroup$ @Stopple The resulting polynomial will probably be at least as complicated as the one in the body of the question. Polynomials like this are almost tautological (well, it uses Wilson's Theorem IIRC) so they are completely useless for actually studying primes. $\endgroup$
    – Wojowu
    Commented Jan 9, 2020 at 16:52

2 Answers 2

Reset to default
13
$\begingroup$

Call your polynomial $P$. I propose the following polynomial: $$ P' = (\xi^2+1)(1 - (\xi^2+1-P)^2) $$ Proof (that the positive values of $P'$ are exactly the primes of the form $N^2+1$):

Let $P_0$ be one of the values of $P$, and let $\xi_0$ be any integer.

Case (i). Suppose $P_0 = \xi_0^2+1$. Then the value of the above polynomial (with the appropriate substitutions made) is $P_0 = \xi_0^2+1$, since the second factor evaluates to unity.

Case (ii). Suppose $P_0 \neq \xi_0^2+1$. Now the second factor evaluates to some non-positive number, and hence the value of the polynomial itself is non-positive.

Now the first case gives us all primes of the form $N^2+1$ as values of $P'$, and no other values (since $P_0=\xi_0^2+1$ is positive), whereas the second case gives us zero or negative numbers exclusively. So the positive values of $P'$ are exactly the primes of the form $N^2+1$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Note that this is a template for making polynomials for some other subsets of primes. One needs a little more tweaking to make it detect primes of the form 8n+5 for example, but that is a simple exercise given this template. Gerhard "May Do Some Simple Exercise" Paseman, 2020.01.11. $\endgroup$
    – Gerhard Paseman
    Commented Jan 11, 2020 at 16:31
  • $\begingroup$ Yes, in that case you need to explicitly "enforce" $P$ to be positive, which I didn't need to do since $P=\xi^2+1$ already did it for me. But of course, one can accomplish this by using Lagrange's theorem. (Which goes to show that, while the existence of these kinds of polynomials is unlikely to yield non-trivial number-theoretical results, one sometimes needs to use non-trivial number theoretical results to construct them... :-)) $\endgroup$
    – R.P.
    Commented Jan 11, 2020 at 16:49
14
$\begingroup$

Putnam (1960) proved that a set is Diophantine if and only if it can be described as the set of positive values of a suitable polynomial with integer coefficients. Matiyasevich (1970) proved that a set is Diophantine if and only if it is recursively enumerable. It follows that every recursively enumerable set, such as the primes of the form $n^2+1$, can be described as the set of positive values of a suitable polynomial with integer coefficients.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm sorry if you don't want to answer next doubt that I've after I known the theorem in the second paragraph of your linked Wikipedia. It is well known that there exists an algorithm to find Mersenne primes (an also Fermat primes), as you know the Lucas-Lehmer primality test (respectively Pépin's test). Is the set of Mersenne primes computably enumerable? I suspect that some fails if I answer it as yes, but from the definition of the Wikipedia Recursively enumerable set, I don't get easily the idea why the set of Mersenne primes isn't computably enumerable $\endgroup$
    – user142929
    Commented Jan 24, 2020 at 19:40
  • 2
    $\begingroup$ @user142929: The sequence of Mersenne primes is not only recursively enumerable (i.e. you can generate it by a computer program) but even recursive (i.e. you can recognize its elements by a computer program). Basically every sequence you know is recursive (hence also recursively enumerable). $\endgroup$
    – GH from MO
    Commented Jan 24, 2020 at 21:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .