Introduction

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

That one restriction changes everything. Asking "does x2x^{2} + y2y^{2} = z2z^{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.

Hunt for a Solution

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">A Diophantine equation only accepts <b>integer</b> answers. Type values for x, y, z and press <b>Check</b> — verifying is instant. Or press <b>Auto-search</b> and watch the machine widen its net forever, with no way to know when to give up.</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">Check</button>
  <button id="search" type="button">Auto-search</button>
  <button id="harder" type="button" class="ghost">Try the hard target</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status">Pick integers, then check.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A Diophantine equation: x^3 + y^3 + z^3 = TARGET, integers only.
// CHECKING a candidate is one arithmetic step. SEARCHING is the hard part:
// we widen the cube [-R..R]^3 and scan. If a solution exists we hit it; if the
// target has none in range, the search has no way to know it should stop —
// the essence of Hilbert's 10th being undecidable (MRDP theorem, 1970).
const EASY = 29;   // has a small solution: 3^3 + 1^3 + 1^3 = 29
const HARD = 30;   // smallest solution is enormous: stands in for "may never halt"
let target = EASY;

const $ = id => document.getElementById(id);
function setEq(){ $('eq').textContent = 'x³ + y³ + z³ = ' + target; }
function setStatus(t, cls){ const s = $('status'); s.textContent = t; s.className = 'status ' + (cls||''); }
function logLine(t){ const l = $('log'); l.textContent = t; }

function lhs(x, y, z){ return x*x*x + y*y*y + z*z*z; }
function check(x, y, z){ return lhs(x, y, z) === target; }

$('check').addEventListener('click', () => {
  const x = parseInt($('x').value, 10) || 0;
  const y = parseInt($('y').value, 10) || 0;
  const z = parseInt($('z').value, 10) || 0;
  const v = lhs(x, y, z);
  if (v === target) setStatus(fmt('✓ %x%³ + %y%³ + %z%³ = %v% — solved!', { x: x, y: y, z: z, v: v }), 'ok');
  else setStatus(fmt('✗ That gives %v%, not %target%. Keep hunting.', { v: v, target: target }), 'bad');
});

let timer = null;
function stopSearch(){ if (timer) { clearTimeout(timer); timer = null; } }

function autoSearch(){
  stopSearch();
  let R = 1, tried = 0;
  function expand(){
    // Scan the shell of the box [-R..R]^3 (cells with max|coord| === R).
    for (let x = -R; x <= R; x++)
      for (let y = -R; y <= R; y++)
        for (let z = -R; z <= R; z++) {
          if (Math.max(Math.abs(x), Math.abs(y), Math.abs(z)) !== R) continue;
          tried++;
          if (check(x, y, z)) {
            $('x').value = x; $('y').value = y; $('z').value = z;
            setStatus(fmt('✓ Found: %x%³ + %y%³ + %z%³ = %target%', { x: x, y: y, z: z, target: target }), 'ok');
            logLine(fmt('Found after %tried% candidates, range ±%R%.', { tried: tried, R: R }));
            return;
          }
        }
    logLine(fmt('Searched range ±%R% (%tried% candidates) — nothing yet. Widening…', { R: R, tried: tried }));
    setStatus('Searching… no way to know when to stop.', '');
    R++;
    if (R > 40) { logLine(fmt('Stopped at range ±40 (%tried% candidates). A real search would never give up.', { tried: tried })); setStatus('Gave up by hand — the algorithm itself never could.', 'bad'); return; }
    timer = setTimeout(expand, 90);
  }
  expand();
}

$('search').addEventListener('click', autoSearch);
$('harder').addEventListener('click', () => {
  stopSearch(); target = (target === EASY) ? HARD : EASY; setEq();
  logLine('');
  setStatus(target === HARD ? 'Now try Auto-search on this one… it will not find it in range.' : 'Back to the easy target.', '');
});
$('reset').addEventListener('click', () => {
  stopSearch(); target = EASY; setEq();
  $('x').value = 0; $('y').value = 0; $('z').value = 0;
  logLine(''); setStatus('Pick integers, then check.', '');
});
setEq();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/diophantine/Content licensed under CC BY-NC 4.0.