Reading the Wikipedia article on Diophantine sets, I was intrigued by the following remark near the end:

Corresponding to any given consistent axiomatization of number theory, one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization.

Unfortunately, no further references are provided concerning this particular statement.

Now I cannot help but wonder: has such an 'undecidable' Diophantine equation ever been constructed for ZFC itself? In general (i.e., not specific to ZFC), is anything known about the minimal complexity of such undecidable equations (such as minimal number of variables, minimal degree)?

  • $\begingroup$ "Unfortunately, no further references are provided concerning this particular statement." --- It is explicitly stated that this result is due to Matiyasevich, and the References section gives, well, references. $\endgroup$ – Martin Brandenburg Jun 20 at 2:37
  • 1
    $\begingroup$ @MartinBrandenburg: No, it merely says that the result is derivable from Matiyasevich's Theorem. (Leaving unanswered the questions: by whom, when, how?) The references given don't specifically go into the result stated, as far as I can tell. $\endgroup$ – Kim Fierens Jun 20 at 2:42
  • 2
    $\begingroup$ This MO answer contains an almost explicit Diophantine equation whose solvability is independent of $\mathsf{ZFC}$. Determining the explicit $K$ needed would be a bit a work but should be doable from the relevant paper. $\endgroup$ – James Hanson Jun 20 at 3:42
  • 1
    $\begingroup$ Ok, I am sorry. $\endgroup$ – Martin Brandenburg Jun 20 at 9:51

A good place to start reading about this is Matiyasevich's book "Hilbert's Tenth Problem", or if you have access to it, James P. Jones' article "Universal Diophantine Equation". This gives a diophantine equation with a few parameters, and if you plug in the right numbers (not provided) for those parameters, the equation will emulate a Turing machine with undecidable halting problem.

Actually figuring out the right numbers you want is difficult, since it first requires building an explicit Turing machine whose halting problem is undecidable in the system you want (which requires encoding that system), and then running it through a fairly complicated translation.

Matiyasevich cites Jones in listing the following pairs of (number of unknowns, degree) for which a universal diophantine equation is known:

  • (58,4),
  • (38,8),
  • (32,12),
  • (29,16),
  • (28,20),
  • (26,24),
  • (25,28),
  • (24,36),
  • (21,96),
  • (19,2668),
  • (14, $2 \times 10^5$),
  • (13, $6.6\times 10^{43}$),
  • (12, $1.3\times 10^{44}$),
  • (11,$4.6\times 10^{44}$),
  • (10, $8.6\times 10^{44}$),
  • (9, $1.6 \times 10^{45}$)

These appear to be mostly applications tricks to reduce the number of variables/degree at the expense of the other applied to a base universal diophantine equation. Jones also provides a universal diophantine equation with 100 operations.

We know diophantine equations with degree 2 are solvable, so the case of diophantine equations with degree 3 is the only open one in terms of degree.

This is from 1992, so perhaps these bounds have changed since then?


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.