Recently I was reading Jones et al.'s famous paper "Diophantine Representation of the Set of Prime Numbers."

They present a Prime-Representing Polynomial in 26 variables, and outline the construction of a 12 variable one; this is the best they say they can do.

They also prove that the degree of such an expression would increase as the number of variables decreases.

Since that paper was published (1976), how far along have we come in terms of reducing the number of variables needed?

What is the "best" result, by that metric?


1 Answer 1


Apparently the record is still $10$ variables (with degree approx $10^{45}$) by Matijasevic (1977).

Ribenboim (1991) referenced nothing less than that. These entries in the Prime Glossary and Mathworld also don't mention anything smaller, though Wikipedia cites Matijasevic as showing it can be potentially reduced to just $9$ variables.

P.S. Regarding the Jones et al polynomial in 26 variables whose positive values are all primes, this has the form,

$$P(a,b,\dots z) = (k+2)(1-x_1^2-x_2^2-\dots-x_{14}^2)$$

so the only way for $P$ to be positive is if all $x_i = 0$. Thus, it is a set of 14 Diophantine equations in disguise.

  • $\begingroup$ Blessed is the theory of numbers with its stratospheric difficulties! $\endgroup$
    – Piquito
    Commented Jul 25, 2018 at 21:13

You must log in to answer this question.

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