Say that a Diophantine equation is almost-satisfiable iff for each $n\in\mathbb{N}$ it has a solution mod $n$. Trivially genuine satisfiability over $\mathbb{N}$ implies almost-satisfiability, but the converse fails - see the discussion here, or for a fun "nuke" note that almost-satisfiability is $\Pi^0_1$ and so cannot coincide with satisfiability as the latter is properly $\Sigma^0_1$ (and as far as I can tell that's actually non-circular! :P).

My question is the following: is almost-satisfiability known to be decidable?

It's plausible to me that one could whip up a Diophantine equation $\mathcal{D}_T$ such that the behavior of a given Turing machine $T$ over the first $s$ steps is connected to the behavior of $\mathcal{D}_T$ over something like $\mathbb{Z}/s\mathbb{Z}$ (sort of a "Diophantine Trakhtenbrot theorem"), but I don't actually see how to do that. Certainly I don't see how to lift any of the MRDP analysis to almost-satisfiability in a useful way. On the other hand, I also don't see how to get a $\Sigma^0_1$ definition of almost-satisfiability. Work of Berend/Bilu shows that almost-satisfiability of single-variable Diophantine equations is decidable, which is nontrivial (in contrast to genuine solvability for single-variable equations which is a trivial application of the rational roots theorem), but at a glance I don't see how to generalize their arguments to multiple variables.

  • 5
    $\begingroup$ Modulo a prime power is not the same as a field of prime power order. $\endgroup$ Aug 2 at 3:03
  • 3
    $\begingroup$ The case modulo every prime was first proved by Ax in a paper called Solving diophantine problems modulo every prime. $\endgroup$ Aug 2 at 3:26
  • 4
    $\begingroup$ @BenjaminSteinberg Actually, this paper gives a full answer to the original question: Ax indicates how to prove that “almost solvability” (which is equivalent to solvability over the $p$-adic integers $\mathbb Z_p$ for all primes $p$) is decidable in the paragraph crossing pages 170 and 171 (it is also mentioned in the introduction, see top of p. 162). $\endgroup$ Aug 2 at 11:27
  • 3
    $\begingroup$ @EmilJeřábek, I posted it as a CW answer. $\endgroup$ Aug 2 at 11:53
  • 9
    $\begingroup$ @NoahSchweber What you call "almost-solvability" is called by number theorists "local solvability." More precisely, "local solvability" also includes solvability over the real numbers, which are sometimes referred to as an "archimedean prime" (in contrast to the usual prime numbers, which are "non-archimedean primes"). Situations in which local and global solvability are equivalent are said to satisfy the Hasse principle. The terminology "local" comes from the analogy between number fields and function fields; primes are analogous to points. $\endgroup$ Aug 2 at 12:55

A Diophantine equation is almost-satisfiable iff it is satisfiable over the ring $\widehat{\mathbb Z}$, the profinite completion of $\mathbb Z$ (also called by some the Prüfer ring), by a standard compactness argument (the solutions over each $\mathbb Z/n\mathbb Z$ form an inverse system of finite sets whose inverse limit is the set of solutions over $\widehat{\mathbb Z}$, and hence if the set of solutions is non-empty for each $n$, then the inverse limit is non-empty). From the direct product decomposition $\widehat{\mathbb Z}=\prod_p \mathbb Z_p$, this in turn reduces things to solvability over the $p$-adic integers $\mathbb Z_p$ for all $p$. This question is solved in the paper J. Ax, Solving diophantine problems modulo every prime. Ann. Math. 85, 161–183 (1967) on pages 170,171. So the problem is decidable.


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.