A set $S \subset \mathbb{N}^k$ is Diophantine if $$(x_1, \dots, x_k) \in S \iff \exists y_1, \dots, y_d \, p(x_1, \dots, x_k, y_1, \dots, y_d) = 0$$

for some Diophantine (integer coefficients) polynomial $p$. The number $d$ above is the dimension of this particular representation of $S$.

It is known (Matiyasevich, 1977) that every Diophantine set can be expressed with $d \le 9$. I believe he accomplishes this by giving a "universal" Diophantine equation in nine unknowns. I am wondering if there are other interesting techniques for reducing the dimension of the representation of $S$. In other words,

Given a Diophantine polynomial $p$ representing a set $S$ with dimension $d$, what are some techniques (besides plugging into the universal Diophantine equation) that allow us to find a new Diophantine polynomial $q$ that represents $S$ with dimension $d' < d$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.