About the problem
The Davis–Putnam–Robinson–Matiyasevich theorem shows that the set of prime numbers is precisely the set of positive values of an integer polynomial. Such a polynomial is called a prime-generating polynomial. The first prime-generating polynomial, with degree 25 and with 26 variables, was found by Jones, Sato, Wada and Wiens. Later, Matiyasevich found a prime-generating polynomial with 10 variables.
This problem asks for a “small” prime-generating polynomial. Specifically, this problem asks for \(k \leq 20\) integer polynomials
\[f_1,\ldots,f_k\in \mathbb{Z}[x_1,x_2,x_3,x_4,x_5]\]each of degree at most 10, and with coefficients between \(-1000\) and \(1000\), such that the positive values of
\[P(x_1,\ldots,x_5)=(x_1+2)\left(1-f_1(\mathbf{x})^2-\cdots-f_k(\mathbf{x})^2\right)\]on \(\mathbb{N}^5\) are precisely the primes, where \(\mathbf{x}=(x_1,\ldots, x_5)\).
The verifier for this problem is slightly risky, because the positive values of the solution polynomial are sampled and tested for primality, rather than proven. It is also possible that there is no solution to this problem, or that there is a brute-force solution that isn’t insightful or computationally useful.
Prompt
A polynomial with integer coefficients can "generate the primes" in the following sense. Work
with five variables x1, x2, x3, x4, x5 ranging over the nonnegative integers N = {0, 1, 2, ...}.
Find a system of polynomials f_1, ..., f_k in Z[x1, x2, x3, x4, x5] such that, as x ranges over
the common nonnegative integer zeros of the system (the points where f_1(x) = ... = f_k(x) = 0),
the value x1 + 2 ranges over exactly the prime numbers. Concretely:
* (Primes are attained) For every prime p there is a point x in N^5 with x1 = p - 2 and
f_i(x) = 0 for all i. The offset of 2 lets the smallest prime, 2, correspond to x1 = 0.
* (Composites are excluded) There is no point x in N^5 with f_i(x) = 0 for all i for which
x1 + 2 is composite.
Constraints on the system:
* 1 <= k <= 20 polynomials.
* Each polynomial has total degree at most 10.
* Every coefficient is a nonzero integer of absolute value at most 10000.
* The witness coordinates you produce for a prime p must be nonnegative integers below 2^1000.
Polynomial encoding. A polynomial is a list of terms; a term is a list
[coefficient, e1, e2, e3, e4, e5] and denotes coefficient * x1**e1 * x2**e2 * x3**e3 * x4**e4 * x5**e5.
Each exponent vector may appear at most once per polynomial. For example x1 + 2 - x2 is
[[1, 1, 0, 0, 0, 0], [2, 0, 0, 0, 0, 0], [-1, 0, 1, 0, 0, 0]].
Solution format:
* Write a Python file that defines, at module level:
- POLYNOMIALS: the list of polynomials, in the encoding above.
- witness(p): given a prime p, returns the five nonnegative integers [x1, x2, x3, x4, x5]
with x1 == p - 2 that make every polynomial vanish. It must work for arbitrary primes,
not only small ones.
* You may optionally define PUBLIC_WITNESSES: a dict mapping the decimal string of each of the
first 1000 primes to its five witness coordinates. This is an optional convenience and may be
omitted.
* Your module is loaded in a fresh process, so do not rely on global state persisting between
calls or on any file-level side effects.