Matiyasevich's theorem (Pell characterization)
ProvedFamousTheorems.matiyasevicMatiyasevich's theorem, in its Pell-equation form.
The relation " is the -th solution of the Pell equation for parameter " is equivalent to an explicit finite system of Diophantine conditions: congruences and Pell equations in auxiliary variables , with no reference to recursion or induction.
The point is that the exponentially growing Pell sequences are Diophantine — definable by polynomial equations alone. This is the last missing step in the negative solution of Hilbert's tenth problem: Davis, Putnam and Robinson had reduced the problem to exhibiting a single Diophantine relation of exponential growth, and Matiyasevich supplied it in 1970 using the Fibonacci numbers, with the Pell version becoming the standard route.
The consequence is that every recursively enumerable set is Diophantine, so there is no algorithm deciding whether an arbitrary polynomial equation with integer coefficients has an integer solution. It also yields a polynomial whose positive values are exactly the primes.
Formalization note. Pell.xn and Pell.yn are the solution sequences for
, ≡ [MOD n] is congruence of naturals, and subtraction is truncated
natural subtraction. The result is Mathlib's Pell.matiyasevic.
import Mathlib
namespace FamousTheorems
universe u v
open Filter Set Topology DirectSum
theorem matiyasevic {a k x y : ℕ} :
(∃ a1 : 1 < a, Pell.xn a1 k = x ∧ Pell.yn a1 k = y) ↔
1 < a ∧ k ≤ y ∧ (x = 1 ∧ y = 0 ∨
∃ u v s t b : ℕ,
x * x - (a * a - 1) * y * y = 1 ∧ u * u - (a * a - 1) * v * v = 1 ∧
s * s - (b * b - 1) * t * t = 1 ∧ 1 < b ∧ b ≡ 1 [MOD 4 * y] ∧
b ≡ a [MOD u] ∧ 0 < v ∧ y * y ∣ v ∧ s ≡ x [MOD u] ∧ t ≡ k [MOD 4 * y]) := by sorry
end FamousTheorems