Formula For Primes - Formula Based On A System of Diophantine Equations

Formula Based On A System of Diophantine Equations

A system of 14 Diophantine equations in 26 variables can be used to obtain a Diophantine representation of the set of all primes. Jones et al. (1976) proved that a given number k + 2 is prime if and only if the following system of 14 Diophantine equations has a solution in the natural numbers:

α₀ = = 0

α₁ = = 0

α₂ = = 0

α₃ = = 0

α₄ = = 0

α₅ = = 0

α₆ = = 0

α₇ = = 0

α₈ = = 0

α₉ = = 0

α₁₀ = = 0

α₁₁ = = 0

α₁₂ = = 0

α₁₃ = = 0

The 14 equations α₀, …, α₁₃ can be used to produce a prime-generating polynomial inequality in 26 variables:

i.e.:

is a polynomial inequality in 26 variables, and the set of prime numbers is identical to the set of positive values taken on by the left-hand side as the variables a, b, …, z range over the nonnegative integers.

A general theorem of Matiyasevich says that if a set is defined by a system of Diophantine equations, it can also be defined by a system of Diophantine equations in only 9 variables. Hence, there is a prime-generating polynomial as above with only 10 variables. However, its degree is large (in the order of 1045). On the other hand, there also exists such a set of equations of degree only 4, but in 58 variables.(Jones 1982)