Worked solution: The MRDP theorem: Diophantine sets are exactly the recursively enumerable sets (1970)

Frequently asked questions

Why Fibonacci numbers specifically, rather than simple powers of

2

Powers of $2$ satisfy the relation $y = 2^x$ directly, but nobody could find a way to Diophantine-define that particular relation. Fibonacci numbers grow at a comparable exponential rate while additionally satisfying rich divisibility and matrix identities that happened to be exactly the right tools for a Diophantine definition.

Source

Yuri Matiyasevich, completing work of Martin Davis, Hilary Putnam, and Julia Robinson, 1970

Matiyasevich theorem

Condensed summary

Step 6 of 9: Matiyasevich 1970: the Fibonacci numbers grow Diophantine-fast

Previous step Next step

In plain words

The Fibonacci numbers $F_n$ ( $1, 1, 2, 3, 5, 8, 13, \ldots$ , each the sum of the two before it) are defined by simple addition, yet grow exponentially fast — roughly like $\varphi^n$ for the golden ratio $\varphi$ . In 1970, the 22-year-old Soviet mathematician Yuri Matiyasevich realized these numbers hide exactly the kind of exponential-growth relation Robinson's JR-hypothesis needed, expressible purely through their divisibility properties.

He proved that the relation $v = F_{2u}$ (even-indexed Fibonacci numbers, growing exponentially in $u$ ) can itself be pinned down by a genuine polynomial equation, using identities like " $F_m$ divides $F_n$ exactly when $m$ divides $n$ " — closing the eighteen-year gap left by Robinson, Davis, and Putnam.

v = F_{2u} \ \implies \ \exists \text{ polynomial } Q,\ Q(u,v,x_1,\ldots,x_k)=0 \iff v = F_{2u}

Detailed analysis

In 1970, Yuri Matiyasevich supplied the missing JR-relation using the Fibonacci numbers $F_n$ , defined by $F_0=0, F_1=1, F_{n+1}=F_n+F_{n-1}$ . Since $F_n \sim \varphi^n/\sqrt{5}$ for the golden ratio $\varphi = (1+\sqrt{5})/2$ , the relation $v = F_{2u}$ grows exponentially in $u$ , exactly the kind of growth Robinson's JR-hypothesis demanded.

Matiyasevich proved $v = F_{2u}$ is itself Diophantine by exploiting deep divisibility identities among Fibonacci numbers — most importantly $F_m \mid F_n \iff m \mid n$ and $\gcd(F_m, F_n) = F_{\gcd(m,n)}$ — together with the matrix identity $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$ , which ties Fibonacci numbers to solutions of a Pell-like equation and lets their recursive definition be re-expressed as a finite system of purely polynomial constraints.

This is exactly the JR-hypothesis Robinson had isolated nearly two decades earlier, so it completes the reduction chain from Robinson, Davis, and Putnam: exponentiation, binomial coefficients, and factorials, which Robinson had already shown follow from any JR-relation, are now all genuinely Diophantine.

Terms in this step

Fibonacci sequence: The sequence $F_0=0, F_1=1, F_{n+1}=F_n+F_{n-1}$ , growing exponentially like $\varphi^n$ for the golden ratio $\varphi$ , and satisfying rich divisibility identities that Matiyasevich exploited to make it Diophantine.

Knowledge used in this step

Linear Diophantine equations