21
$\begingroup$

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.

Improve this question
$\endgroup$
14
  • 5
    $\begingroup$ Modulo a prime power is not the same as a field of prime power order. $\endgroup$
    – Benjamin Steinberg
    Commented Aug 2, 2021 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$
    – Benjamin Steinberg
    Commented Aug 2, 2021 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$
    – Emil Jeřábek
    Commented Aug 2, 2021 at 11:27
  • 3
    $\begingroup$ @EmilJeřábek, I posted it as a CW answer. $\endgroup$
    – Benjamin Steinberg
    Commented Aug 2, 2021 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$
    – Timothy Chow
    Commented Aug 2, 2021 at 12:55

1 Answer 1

Reset to default
27
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is this algorithm practical, at least for equations with small coefficients? Is it implemented in any computer algebra system like Mathematica, magma, maple, sagemath, etc? I am aware about Magma function "IsLocallySolvable", but it is about solvability in $Q_p$ rather in $Z_p$. For $Z_p$, we can of course check solvability modulo every prime power up to some bound, but how to compute this bound for the specific equation? Will it be not galactic? If general method is not practical, is there at least a fast method for checking the solvability modulo all powers of the specific prime $p$? $\endgroup$
    – Bogdan Grechuk
    Commented Oct 20, 2021 at 12:41
  • $\begingroup$ @BogdanGrechuk, My guess is the proof is not practical given how old it is. I'm not sure if something better has been proved at least for special classes of equations $\endgroup$
    – Benjamin Steinberg
    Commented Oct 20, 2021 at 14:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .