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.
Best Answer
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.