# 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_{0}^{2} - (1 + x_{1}^{2})

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.