Diophantine Equations

A Diophantine equation is something you met in school without knowing its name: a polynomial set equal to zero, like $x^{2}$ + $y^{2}$ = $z^{2}$, where you only accept whole-number answers. No fractions, no decimals — just integers.

That one restriction changes everything. Asking "does $x^{2}$ + $y^{2}$ = $z^{2}$ have a solution?" is easy (3, 4, 5). But the general question — given any polynomial with integer coefficients, does it have an integer solution? — was so important that David Hilbert put it on his famous 1900 list as the tenth problem, asking mathematicians to find a single procedure that always answers it.

For decades people searched for that procedure. The shocking result is that they were searching for something that cannot exist — not because we are not clever enough, but because no algorithm whatsoever can do the job.

Below is a small Diophantine equation. Type integers for the unknowns and the computer checks them instantly — that part is always easy. Then press Auto-search and watch the machine try integer combinations one after another, growing the range it scans.

<p class="hint">{{hint_p}}</p>
<div class="eq" id="eq">x³ + y³ + z³ = 29</div>
<div class="inputs">
  <label>x <input id="x" type="number" value="0"></label>
  <label>y <input id="y" type="number" value="0"></label>
  <label>z <input id="z" type="number" value="0"></label>
</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="search" type="button">{{btn_search}}</button>
  <button id="harder" type="button" class="ghost">{{btn_harder}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="log" id="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.eq { font: 700 22px ui-monospace, monospace; color: #1d3557; background: #e8eef3;
      border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem .8rem; display: inline-block; margin: .2rem 0 .7rem; }
.inputs { display: flex; gap: .8rem; flex-wrap: wrap; margin-bottom: .7rem; }
.inputs label { font: 600 14px system-ui, sans-serif; display: flex; align-items: center; gap: .35rem; }
.inputs input { width: 70px; font: 600 15px ui-monospace, monospace; padding: .35rem .4rem;
                border: 1px solid #adb1b8; border-radius: 6px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.log { font: 500 12px ui-monospace, monospace; color: #555; white-space: pre-wrap;
       background: #f6f8fa; border: 1px solid #e1e6ea; border-radius: 8px; padding: .5rem .7rem;
       min-height: 2.2em; max-height: 120px; overflow: auto; }

// Code not found

Notice the asymmetry. Verifying a proposed solution is a single arithmetic step. Searching for one means widening the net forever: if a solution exists you will eventually hit it, but if none exists the search has no way to know when to give up. That "never knowing when to stop" is the whole story — and for Diophantine equations there is provably no shortcut around it.

How hard is deciding whether a Diophantine equation has integer solutions? Not hard in the sense of "slow" — hard in the sense of impossible.

• Checking a candidate is trivial: plug the numbers in and evaluate.
• Brute force scans integers in growing boxes. If a solution exists, it is found; if not, the search runs forever.
• It is undecidable. In 1970, the young mathematician Yuri Matiyasevich delivered the final piece, completing decades of work by Martin Davis, Hilary Putnam, and Julia Robinson. The result — the MRDP theorem — proves that the set of solvable Diophantine equations is exactly the class of recursively enumerable sets. Since the halting problem is recursively enumerable but not decidable, no algorithm can decide whether an arbitrary Diophantine equation has an integer solution.
• So Hilbert's request was unfulfillable. You can build a polynomial whose integer solutions correspond to a Turing machine halting. Deciding the equation would decide the halting problem — which is impossible.

That is the punchline: this is not NP-hard, not even merely intractable. It lives below the dividing line of computability itself, alongside the deepest results about what machines can never do, like those behind P vs NP but one full level more severe.

An impossibility result is not a dead end — it is a map of where effort is wasted:

• Number theory: many famous open questions can be encoded as Diophantine equations, so a universal solver would settle them all at once. Its non-existence explains why each must be attacked by hand.
• Automated theorem proving: software that searches for proofs runs straight into the same wall — there can be no procedure that decides every arithmetic statement.
• Program analysis: asking "can this program ever reach this line?" reduces to questions as hard as Diophantine solvability, which is why static analyzers must approximate.
• Teaching the limits: Hilbert's tenth is one of the most concrete demonstrations that some perfectly clear questions have no algorithmic answer.

Understand why this equation has no solver and you have met undecidability — the same barrier behind the halting problem and the outer limit of what any computer can ever do.

Diophantine equations hide a humbling secret: a question a child can state — does this polynomial have whole-number answers? — is one that no algorithm will ever answer in general. Checking stays instant; deciding is impossible, proved once and for all by the MRDP theorem in 1970.

So when an integer search runs and runs without resolution, that is not a bug or a missing trick. It is a glimpse of the true edge of computation — the place where, like the halting problem, even an infinitely patient machine can never be sure.