Introduction

Take an algebraic expression — a product of sums, a determinant of a matrix full of variables, a tangle of brackets stacked pages deep. Multiply everything out and a question appears: is the result identically zero? Not zero for one particular input, but zero for every possible value of every variable.

It sounds like bookkeeping. The trouble is scale. A modest expression like a determinant of an n×n matrix expands into n! terms. For n = 20 that is more terms than there are atoms in a city. You can never write them all down, so you can never just "expand and look."

And yet there is a trick so simple it feels like cheating: don't expand — just plug in random numbers and see what comes out. That one idea turns a seemingly hopeless question into a coin flip. Whether you can do the same thing without the coins is one of the great open problems of computer science.

Try It: Catch the Imposter

Below are two expressions. One pair is genuinely equal (their difference is the zero polynomial); the other only looks equal but is not. You cannot tell by staring — so test them the way a computer would: feed in random numbers and compare the outputs.

<p class="hint">Two algebraic expressions. Are they the <b>same</b> polynomial? Don't expand them — just feed in a random number and compare the outputs. Each matching test is evidence they are equal; a single mismatch proves they are not.</p>
<div class="pick">
  <button id="caseA" type="button" class="sel">Pair A</button>
  <button id="caseB" type="button">Pair B</button>
</div>
<div class="poly">
  <div class="side"><span class="lbl">Left</span><code id="lhs"></code></div>
  <div class="eq">=?</div>
  <div class="side"><span class="lbl">Right</span><code id="rhs"></code></div>
</div>
<div class="readout" id="readout"></div>
<div class="status" id="status">Pick a pair, then run tests.</div>
<div class="btns">
  <button id="run" type="button">Run one test</button>
  <button id="run20" type="button">Run 20 tests</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</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; }
.pick { display: flex; gap: .4rem; margin-bottom: .7rem; }
.pick button { font: 600 13px system-ui, sans-serif; padding: .35rem .8rem; border: 1px solid #1d3557;
               background: #fff; color: #1d3557; border-radius: 999px; cursor: pointer; }
.pick button.sel { background: #1d3557; color: #fff; }
.poly { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin: .3rem 0 .6rem; }
.side { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem .7rem; flex: 1 1 200px; }
.lbl { display: block; font-size: .7rem; text-transform: uppercase; letter-spacing: .05em; color: #5a7088; margin-bottom: .2rem; }
code { font: 600 14px ui-monospace, monospace; color: #1d3557; }
.eq { font: 700 18px ui-monospace, monospace; color: #5a7088; }
.readout { font: 600 13px ui-monospace, monospace; color: #333; background: #f3f5f8;
           border-radius: 8px; padding: .5rem .7rem; margin: .3rem 0; line-height: 1.6; min-height: 4.2em; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Polynomial Identity Testing via the Schwartz-Zippel lemma.
// We never expand the polynomials. We pick a random x in {0,1,...,S-1} and
// evaluate both sides. If they ever differ, the two sides are NOT the same
// polynomial (a definite NO). If they always match after many trials, they are
// almost certainly equal: a non-zero difference of degree d disagrees on all
// but at most d of the S values, so one test is fooled with prob <= d/S, and k independent tests with prob <= (d/S)^k.
const S = 100;            // sample x from {0..99}
const MOD = 1000003;      // a prime; keep arithmetic exact and bounded

// Pair A: (x+1)(x+2)(x+3) vs x^3 + 6x^2 + 11x + 6  -> TRULY EQUAL, degree 3.
// Pair B: (x+1)(x+2)(x+3) vs x^3 + 6x^2 + 11x + 5  -> NOT equal (constant off by 1).
const CASES = {
  A: { equal: true,  d: 3,
       lText: '(x+1)(x+2)(x+3)', rText: 'x³ + 6x² + 11x + 6',
       L: x => (x+1)*(x+2)*(x+3), R: x => x*x*x + 6*x*x + 11*x + 6 },
  B: { equal: false, d: 3,
       lText: '(x+1)(x+2)(x+3)', rText: 'x³ + 6x² + 11x + 5',
       L: x => (x+1)*(x+2)*(x+3), R: x => x*x*x + 6*x*x + 11*x + 5 }
};

let key = 'A';
let tests = 0, mismatch = false;

function mod(n){ return ((n % MOD) + MOD) % MOD; }

function showCase(){
  const c = CASES[key];
  document.getElementById('lhs').textContent = c.lText;
  document.getElementById('rhs').textContent = c.rText;
  document.getElementById('caseA').classList.toggle('sel', key==='A');
  document.getElementById('caseB').classList.toggle('sel', key==='B');
}
function setStatus(t, cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function reset(){ tests=0; mismatch=false; document.getElementById('readout').textContent=''; setStatus('Pick a pair, then run tests.',''); }

function bound(){
  // false-positive probability ceiling after `tests` trials: (d/S)^tests
  const c = CASES[key];
  const p = Math.pow(c.d / S, tests);
  return p;
}

function oneTest(){
  if(mismatch) return; // already settled as NOT equal
  const c = CASES[key];
  const x = Math.floor(Math.random()*S);
  const lv = mod(c.L(x)), rv = mod(c.R(x));
  tests++;
  const ro = document.getElementById('readout');
  const same = lv === rv;
  ro.textContent = fmt('x = %x%   left = %lv%   right = %rv%   %v%', { x: x, lv: lv, rv: rv, v: same ? '→ match' : '→ MISMATCH!' });
  if(!same){
    mismatch = true;
    setStatus(fmt('✗ Outputs differ at x=%x% — the two sides are NOT the same polynomial. One test settled it.', { x: x }), 'bad');
    return;
  }
  const p = bound();
  const pct = (p*100);
  const pStr = pct < 1e-6 ? p.toExponential(2) : pct.toFixed(p>=0.01?2:6) + '%';
  setStatus(fmt(tests>1?'✓ %tests% matching tests — chance we are being fooled ≤ %pStr%. Likely equal.':'✓ %tests% matching test — chance we are being fooled ≤ %pStr%. Likely equal.', { tests: tests, pStr: pStr }), 'ok');
}
function many(n){ for(let i=0;i<n && !mismatch;i++) oneTest(); }

document.getElementById('caseA').addEventListener('click', ()=>{ key='A'; showCase(); reset(); });
document.getElementById('caseB').addEventListener('click', ()=>{ key='B'; showCase(); reset(); });
document.getElementById('run').addEventListener('click', ()=>oneTest());
document.getElementById('run20').addEventListener('click', ()=>many(20));
document.getElementById('reset').addEventListener('click', reset);
showCase(); reset();
Result
Console

Each random test that gives matching outputs is weak evidence the two sides are equal. A single test on a non-zero polynomial of degree d over a set of S values has at most a d/|S| chance of being fooled — that is the Schwartz-Zippel lemma (Schwartz and Zippel, 1979-1980). Press Run one test repeatedly and watch the chance of a false "equal" collapse: after k independent tests it is below (d/|S|)ᵏ. Checking by random sampling is almost free; proving equality without any randomness at all is the hard part.

The Real Complexity

How hard is it to decide whether a polynomial (given as a formula or circuit) is identically zero?

  • With randomness it is easy. The Schwartz-Zippel lemma gives a one-line algorithm: evaluate at random points. The error shrinks to nothing after a handful of trials, so PIT sits comfortably in the class coRP (and hence BPP) — the problems efficiently solvable with a coin and a tiny error probability.
  • Without randomness, nobody knows. Despite decades of effort, no deterministic polynomial-time algorithm for general PIT is known. Whether one exists is open — it is the canonical problem of derandomization, the quest to remove randomness from efficient algorithms.
  • It is deeply connected to the hardest questions. Kabanets and Impagliazzo (2003) proved that a fast deterministic PIT algorithm would force circuit lower bounds — it would prove that some explicit problem cannot be computed by small circuits, exactly the kind of statement at the heart of P vs NP. So derandomizing PIT is not a tidy engineering task; it would crack open barriers we have no idea how to pass.
  • Special cases have fallen. Restricted models (read-once formulas, sparse polynomials, certain depth-bounded circuits) do admit deterministic algorithms. The general case remains stubbornly open.

That is the punchline: a problem a child could solve by flipping coins resists every attempt to solve it cleanly. PIT is where the power of randomness — and our ignorance about whether it is truly necessary — comes into sharpest focus.

Where It Matters

"Are these two algebraic objects the same?" is a question hiding inside an astonishing range of algorithms, and random evaluation is the universal answer key:

  • Perfect matchings: a graph has a perfect matching exactly when a certain symbolic determinant (its Tutte/Edmonds matrix) is not the zero polynomial — checked by random evaluation, the core of fast parallel matching algorithms.
  • Primality and number theory: identity-style checks underpin classic randomized primality tests, the warm-up to the deterministic AKS test for primality.
  • Interactive proofs and verification: protocols like sum-check and the proof that IP = PSPACE lean on testing polynomial identities at random points — the foundation of modern probabilistically checkable proofs and SNARKs.
  • Program and data checking: fingerprinting two large files or two computations by evaluating a polynomial over them detects differences with near-certainty using only a few bytes.

Learn why random evaluation works and you have met one of the most reusable ideas in all of computing — and the open question of whether factoring or any other problem truly needs randomness sits right beside it.

Conclusion

Polynomial identity testing carries a strange double life. Hand it a coin and it is trivial: pick random numbers, compare, repeat until the chance of being fooled is smaller than the chance of your computer being hit by a meteor. Take the coin away and it becomes one of the deepest open problems we have — no efficient deterministic algorithm is known, and finding one would shake the foundations of complexity theory itself.

So the next time randomness feels like a shortcut, remember PIT. It is the clearest evidence that a few random bits can be worth more than any amount of cleverness — and the sharpest reminder that we still do not understand why, or whether the coins were ever truly needed. It is randomness made into a question, sitting just beside P vs NP.

Share this article

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

Comments

Loading comments...

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