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

Step 4 of 9: Julia Robinson's JR-hypothesis: one growth engine is enough

In plain words

Already in the early 1950s, Julia Robinson found the missing ingredient in outline, without yet proving it exists: if you can find even one Diophantine relation between two numbers $u$ and $v$ that forces $v$ to explode in size much faster than any fixed power of $u$ , that single "growth engine" can be recycled through clever algebraic tricks.

From that one relation, Robinson showed exponentiation itself becomes Diophantine; from exponentiation, binomial coefficients and factorials follow; and with all of those in hand, there is enough machinery to encode the step-by-step behavior of an arbitrary computer program. This became known as the JR-hypothesis, named for her initials.

\text{JR: } \exists \text{ Diophantine } R(u,v),\ v=u^{f(u)},\ f \to \infty \implies \text{exponentiation, } \binom{n}{k}, n! \text{ all Diophantine}

Detailed analysis

Julia Robinson identified, around 1950–52, the JR-hypothesis: the existence of a Diophantine relation $R(u,v)$ such that $R(u,v)$ holds only for pairs where $v$ grows at least exponentially in $u$ (specifically, $v \le u^u$ and, for every $k$ , eventually $v > u^k$ for some pairs satisfying $R$ ), together with some closure conditions ensuring the relation itself is well-behaved under Diophantine operations.

She proved that if any single relation satisfying JR exists, then a cascade of increasingly familiar operations becomes Diophantine one after another: first plain exponentiation $v = u^w$ , then the binomial coefficient function, then the factorial function $n!$ , each built as a Diophantine definition using the previous one as a building block. This reduced the entire remaining difficulty of Davis's conjecture to a single, sharply-defined technical target: exhibit just one genuinely Diophantine relation with exponential growth.

Robinson's own attempts using Pell equations $x^2 - (a^2-1)y^2 = 1$ (whose solutions already grow exponentially) came tantalizingly close throughout the 1950s and 1960s but could not quite close the gap; the next step describes how Davis, Putnam, and Robinson combined forces in 1961 to push the argument as far as it could go without JR itself.

Terms in this step

Pell equation: An equation of the form $x^2 - dy^2 = 1$ for a fixed non-square integer $d$ ; its solutions form a structured, exponentially growing sequence, making it a natural candidate source of Diophantine relations with fast growth.

Knowledge used in this step

Linear Diophantine equations