Enumerating Diophantine equations

I mentioned this problem in passing in my last post, but it’s really not trivial. Here’s the method exposed in Matiyasevich’s Hilbert’s Tenth Problem. The method originates from Julia Robinson, in Diophantine Decision Problems (in Studies in Number Theory).

Here are the rules she offers to generate all integer polynomials P_m and all positive integer polynomials T_n:

• T_4n = n
• T_4n+1 = x_n
• T_4n+2 = T_{CantorLeft(n)} + T_{CantorRight(n)}
• T_4n+3 = T_{CantorLeft(n)} * T_{CantorRight(n)}
• P_m = T_{CantorLeft(m)} - T_{CantorRight(m)}

As you can see, T_n will includes all possible constants and unknowns, as well as any sums or products of other T_n elements. Then P_m will be the difference of any two T_n elements.

An example: P_{7,297,614,550} = 2.x₀² - (1 + x₁²)

One thing to notice is that T_n will generate duplicates. For instance, T_4n+2 = T_4m+2 when CantorLeft(n) = CantorRight(m) and CantorRight(n) = CantorLeft(m). I don’t know if there is a numbering that avoids such duplication.