解法: MRDP定理:ディオファントス集合は帰納的可算集合と一致する(1970年)

1970年、Yuri Matiyasevichは、$F_0=0, F_1=1, F_{n+1}=F_n+F_{n-1}$ で定義されるフィボナッチ数 $F_n$ を用いて、欠けていたJR関係を供給した。黄金比 $\varphi = (1+\sqrt{5})/2$ について $F_n \sim \varphi^n/\sqrt{5}$ であるから、関係 $v = F_{2u}$ は $u$ に対して指数的に増大し、まさにRobinsonのJR仮説が要求した種類の増大である。

Matiyasevichは、フィボナッチ数の間の深い整除の恒等式——最も重要なのは $F_m \mid F_n \iff m \mid n$ と $\gcd(F_m, F_n) = F_{\gcd(m,n)}$ である——と、行列の恒等式 $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$ を利用することで、$v = F_{2u}$ 自体がディオファントスであることを証明した。この行列の恒等式はフィボナッチ数をペル型方程式の解に結び付け、その再帰的な定義を純粋に多項式的な制約の有限系として書き直すことを可能にする。

これはまさに、ほぼ二十年前にRobinsonが特定していたJR仮説そのものであり、Robinson、Davis、Putnamからの帰着の連鎖を完成させる:Robinsonがすでにあらゆる JR関係から従うことを示していたべき乗、二項係数、階乗は、今やすべて真にディオファントスとなる。