0
$\begingroup$

As in this question >> Primes of the form $x^2 + y^2 + 1$ There are $\asymp \dfrac{x}{\log^{3/2} x}$ primes of the form $a^2+b^2+1$ up to $x$. I read a book stated that there exist a polynomial $P(a_1,a_2,\dots,a_{26})$ that represents all primes $\sim\dfrac{x}{\log x}$ if its value $>0$ and if we count $P$ up to $x$.

Actually, I don't know how we can surely know and prove that about $P$ as the book said it's from computer computation. One question is about the prove or an idea to the prove of such $P$.

The other question is that what is the smallest number ($k$) of variables that the polynomial $Q(a_1,a_2,\dots, a_k)$ represents all prime (or at least represents $\sim\pi(x)$ primes up to $x$), as for $k=2$ it is clear from the asymptotic that it is not enough and $k$ should be $\le 26$? but at such a case its value must be $>0$. I'm not so sure it might turn out to have no such $k$ with no supplement condition as in the case $26$?.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Check e.g. primes.utm.edu/glossary/page.php?sort=MatijasevicPoly and references therein. $\endgroup$
    – gmvh
    Commented Feb 10, 2021 at 9:51
  • 2
    $\begingroup$ The existence of such a polynomial follows from the negative solution of Hilbert's tenth problem. Robinson and Matijasevic showed that every enumerable set is diophantine, that is, if for a set of integers $A$ there exists a computer program, that produces all elements of $A$, not necessarily in the correct order, then there exists a polynomial $P(x, y_1, \ldots, y_k)$, such that the equation $P(n, y_1, \ldots, y_k)=0$ is solvable in integers if and only if $n\in A$. The set of primes is enumerable, and from the polynomial $P$ it is easy to construct a prime producing polynomial. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Feb 10, 2021 at 11:23
  • 3
    $\begingroup$ There have been papers which reduce the number of variables from $26$, at the cost of incresing the degree of the polynomial. $\endgroup$
    – Gerry Myerson
    Commented Feb 10, 2021 at 12:01
  • $\begingroup$ The easiest way to make a polynomial that represents all primes is to make a polynomial that represents all nonnegative numbers. This can be done with a one-variable polynomial, for instance. $\endgroup$
    – Will Sawin
    Commented Feb 10, 2021 at 17:26

0

Reset to default

You must log in to answer this question.