Prime-representing polynomial systems in five variables

Thanks to the solution of Hilbert's tenth problem, the prime numbers are exactly the positive values of some polynomial with integer coefficients. The explicit examples are large: one has 26 variables and degree 25, another 10 variables. The task is to describe the primes with a compact system of polynomials in only five variables.

Problem

Work over $\mathbb{N} = \{0, 1, 2, \dots\}$ and write $\mathbf{x} = (x_1, \dots, x_5)$.

Task. Find polynomials $f_1, \dots, f_k \in \mathbb{Z}[x_1, \dots, x_5]$ such that

$$\bigl\{\, x_1 + 2 \;:\; \mathbf{x} \in \mathbb{N}^5,\ f_1(\mathbf{x}) = \cdots = f_k(\mathbf{x}) = 0 \,\bigr\}$$

is exactly the set of primes. Equivalently, the positive values on $\mathbb{N}^5$ of

$$P(\mathbf{x}) = (x_1 + 2)\bigl(1 - f_1(\mathbf{x})^2 - \cdots - f_k(\mathbf{x})^2\bigr)$$

are exactly the primes.

Epoch's version bounds the size of the system: $k \le 20$, each $f_i$ of total degree at most 10, and every coefficient a nonzero integer of absolute value at most $10^4$.

Background

The theorem of Davis, Putnam, Robinson and Matiyasevich shows that every recursively enumerable set, the primes included, is the set of positive values of an integer polynomial. Jones, Sato, Wada and Wiens wrote down an explicit prime-representing polynomial of degree 25 in 26 variables [1], and Matiyasevich found one in 10 variables [2]. Jones studied how few variables and how small a degree universal Diophantine equations can have [3]. How many variables a prime-representing polynomial really needs is unknown.

What is known

• Explicit prime-representing polynomials exist with 26 variables and degree 25 [1], and with 10 variables [2].
• No representation in five variables is known (Epoch).
• Epoch notes that no such system may exist, or that one might be found by brute force without much insight.

What would count as progress

• A system $f_1, \dots, f_k$ together with an algorithm witness(p) that, for every prime $p$, returns $\mathbf{x} \in \mathbb{N}^5$ with $x_1 = p - 2$ and all $f_i(\mathbf{x}) = 0$, plus a proof that no common zero has $x_1 + 2$ composite.
• Epoch scores submissions with its own verifier: it checks the size limits, evaluates the witnesses for sampled primes below $2^{32}$, and tests the exclusion of composites by sampling rather than proof. A full proof of exclusion is still needed for the result to stand.
• A construction that explains why the system works, rather than an identity found by blind search, would be the most valuable outcome.

References

1. J. P. Jones, D. Sato, H. Wada and D. Wiens, Diophantine representation of the set of prime numbers, Amer. Math. Monthly 83 (1976), 449–464. doi:10.1080/00029890.1976.11994142
2. Yu. V. Matiyasevich, Primes are nonnegative values of a polynomial in 10 variables, J. Soviet Math. 15 (1981), 33–44. doi:10.1007/BF01404106
3. J. P. Jones, Universal Diophantine equation, J. Symbolic Logic 47 (1982), 549–571. doi:10.2307/2273588

Source

Imported from FrontierMath: Open Problems, prime-generating-polynomials, curated by Epoch AI. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.