Skolem Problem: Hunt for Zeros

Introduction

Start with the Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, … Each term is the sum of the two before it. Now change the rule a little. Say each term is $2$ times the previous one, minus $2$ times the one before that, and start from $0, 1$ . You get $0, 1, 2, 2, 0, -4, -8, -8, 0, \dots$ and the sequence touches zero again and again.

Both are linear recurrence sequences (LRS): a rule $u_n = c_1 u_{n-1} + \dots + c_k u_{n-k}$ with fixed integer coefficients, plus $k$ integer starting values. The number $k$ is the order. This is among the most basic ways to generate an infinite sequence, and it shows up in population models, signal filters, loop counters and automata.

The Skolem Problem asks the simplest question one could pose about such a sequence: does it ever equal zero? You are given $c_1,\dots,c_k$ and the starting values, and you must answer yes or no, with a guarantee that your procedure always halts.

Finding a zero when one exists is easy: compute terms until you see one. The difficulty is the other direction. If no zero has shown up after a million terms, can you ever safely say there will never be one? For an arbitrary recurrence, no one knows an algorithm that provably settles it. The problem has been open for decades, and it sits next to questions about mortal matrices, termination of programs and the halting problem, although, unlike those, nobody has proved it undecidable either.

Hunt for Zeros

Choose a preset or type your own coefficients and starting values (up to order 6, integers of any size). The explorer computes exact terms with big integers, lists every zero up to the $n$ you ask for, and tries to recognize arithmetic progressions among them.

<div class="wrap">
  <div class="row">
    <label for="preset">Example</label>
    <select id="preset">
      <option value="fib">Fibonacci (one zero, at n = 0)</option>
      <option value="trib">Tribonacci from 0, 0, 1</option>
      <option value="ap">A rotating sequence (zeros every 4 steps)</option>
      <option value="two">Two progressions (multiples of 3 or 4)</option>
      <option value="sporadic">2^n − n^2 (two isolated zeros)</option>
      <option value="custom">Your own recurrence</option>
    </select>
  </div>
  <div class="formula" id="formula"></div>
  <div class="row">
    <label for="coef">Coefficients c1…ck</label>
    <input id="coef" type="text" value="1, 1" spellcheck="false" aria-label="Coefficients of the recurrence, separated by commas">
  </div>
  <div class="row">
    <label for="init">Initial values u(0)…u(k−1)</label>
    <input id="init" type="text" value="0, 1" spellcheck="false" aria-label="Initial values, separated by commas">
  </div>
  <div class="row">
    <label for="nmax">Compute up to n =</label>
    <input id="nmax" type="number" min="10" max="400" value="120">
    <button id="run" type="button">Compute</button>
  </div>
  <div class="err" id="err" role="alert"></div>
  <div class="card">
    <div class="h">First terms</div>
    <div class="mono" id="terms"></div>
  </div>
  <div class="card">
    <div class="h">Zeros found</div>
    <div id="zeros"></div>
    <div id="ap" class="ap"></div>
  </div>
  <div class="card">
    <div class="h">Sign and size of each term</div>
    <canvas id="plot" height="150" aria-label="Bar chart of the sign and base-10 logarithm of the magnitude of each term"></canvas>
    <div class="legend"><span class="sw pos"></span>positive <span class="sw neg"></span>negative <span class="sw zero"></span>zero</div>
  </div>
  <div class="card">
    <div class="h">Characteristic roots in the complex plane</div>
    <canvas id="cplane" height="210" aria-label="Complex plane showing the roots of the characteristic polynomial"></canvas>
    <div class="legend"><span class="dot dom"></span>dominant roots (largest modulus) <span class="dot oth"></span>other roots</div>
    <div class="mono small" id="rootlist"></div>
  </div>
  <div class="card">
    <div class="h">Zeros modulo small primes</div>
    <div class="small">Reduce the sequence mod p. A true zero is always a zero mod every p, and mod p the sequence is eventually periodic. Bold 0 marks positions that vanish mod p, over one period.</div>
    <div class="mono small" id="modtab"></div>
  </div>
</div>

:root {
  --bg: #ffffff; --fg: #1d2733; --muted: #5b6878; --card: #f2f5f9; --line: #d3dbe5;
  --accent: #1d5fa8; --pos: #2a7fc4; --neg: #d9822b; --zero: #d23c4a; --on-accent: #ffffff;
  --dom: #d23c4a; --oth: #6b7a8c;
}
@media (prefers-color-scheme: dark) {
  :root {
    --bg: #14181d; --fg: #e4eaf1; --muted: #9aa8b8; --card: #1d2430; --line: #333e4d;
    --accent: #6cb0f0; --pos: #5aa9ec; --neg: #f0a24f; --zero: #ff6b78; --on-accent: #0b1117;
    --dom: #ff6b78; --oth: #8fa0b4;
  }
}
* { box-sizing: border-box; }
body { margin: 0; background: var(--bg); color: var(--fg); font: 14px/1.45 system-ui, sans-serif; }
.wrap { padding: 8px; max-width: 760px; margin: 0 auto; }
.row { display: flex; gap: 8px; align-items: center; flex-wrap: wrap; margin: 6px 0; }
label { font-weight: 600; min-width: 96px; }
select, input { font: inherit; color: var(--fg); background: var(--card); border: 1px solid var(--line); border-radius: 6px; padding: 5px 8px; min-width: 0; flex: 1 1 140px; }
input[type=number] { flex: 0 0 90px; }
button { font: 600 14px system-ui, sans-serif; padding: 6px 14px; border: 0; border-radius: 6px; background: var(--accent); color: var(--on-accent); cursor: pointer; }
.formula { font-family: ui-monospace, Consolas, monospace; color: var(--muted); font-size: 13px; overflow-wrap: anywhere; }
.err { color: var(--zero); font-weight: 600; min-height: 1.2em; }
.card { background: var(--card); border: 1px solid var(--line); border-radius: 8px; padding: 8px 10px; margin: 8px 0; }
.h { font-weight: 700; margin-bottom: 4px; }
.mono { font-family: ui-monospace, Consolas, monospace; overflow-wrap: anywhere; }
.small { font-size: 12.5px; color: var(--muted); }
canvas { width: 100%; display: block; background: var(--bg); border: 1px solid var(--line); border-radius: 6px; }
.legend { font-size: 12px; color: var(--muted); margin-top: 4px; display: flex; flex-wrap: wrap; gap: 4px 10px; align-items: center; }
.sw { display: inline-block; width: 10px; height: 10px; margin-right: 3px; border-radius: 2px; }
.sw.pos { background: var(--pos); } .sw.neg { background: var(--neg); } .sw.zero { background: var(--zero); }
.dot { display: inline-block; width: 10px; height: 10px; margin-right: 3px; border-radius: 50%; }
.dot.dom { background: var(--dom); } .dot.oth { background: var(--oth); }
.zchip { display: inline-block; background: var(--zero); color: #fff; border-radius: 10px; padding: 0 7px; margin: 2px 3px 2px 0; font: 600 12px ui-monospace, monospace; }
.ap { margin-top: 6px; font-weight: 600; color: var(--accent); }
.bits { letter-spacing: 1px; }
.bits b { color: var(--zero); }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const PRESETS = {
  fib: { c: '1, 1', i: '0, 1', n: 120 },
  trib: { c: '1, 1, 1', i: '0, 0, 1', n: 120 },
  ap: { c: '2, -2', i: '0, 1', n: 120 },
  two: { c: '2, -2, 4, -4', i: '0, 1, 2, 0', n: 120 },
  sporadic: { c: '5, -9, 7, -2', i: '1, 1, 0, -1', n: 120 },
  custom: { c: '0, 0, 0, 0, 1, 1', i: '1, 0, 0, 0, 0, 3', n: 120 }
};
const PRIMES = [2, 3, 5, 7, 11, 13];
const $ = (id) => document.getElementById(id);

function parseList(text) {
  const parts = text.split(/[\s,;]+/).filter((x) => x.length);
  return parts.map((p) => {
    if (!/^[+-]?\d+$/.test(p)) throw new Error('bad');
    return BigInt(p);
  });
}

function genTerms(c, init, N) {
  const u = init.slice();
  const k = c.length;
  while (u.length <= N) {
    let s = 0n;
    for (let j = 0; j < k; j++) s += c[j] * u[u.length - 1 - j];
    u.push(s);
  }
  return u.slice(0, N + 1);
}

function zeroIndices(u) {
  const z = [];
  for (let n = 0; n < u.length; n++) if (u[n] === 0n) z.push(n);
  return z;
}

function log10Big(x) {
  const s = (x < 0n ? -x : x).toString();
  if (s.length <= 15) return Math.log10(Number(s) + 1);
  return s.length - 1 + Math.log10(Number(s.slice(0, 15)) / 1e14);
}

function cmul(a, b) { return [a[0] * b[0] - a[1] * b[1], a[0] * b[1] + a[1] * b[0]]; }
function cadd(a, b) { return [a[0] + b[0], a[1] + b[1]]; }
function csub(a, b) { return [a[0] - b[0], a[1] - b[1]]; }
function cdiv(a, b) {
  const d = b[0] * b[0] + b[1] * b[1];
  return [(a[0] * b[0] + a[1] * b[1]) / d, (a[1] * b[0] - a[0] * b[1]) / d];
}

function charRoots(c) {
  const k = c.length;
  const a = [1];
  for (let j = 0; j < k; j++) a.push(-Number(c[j]));
  let R = 1;
  for (let j = 1; j <= k; j++) R = Math.max(R, 1 + Math.abs(a[j]));
  const z = [];
  for (let j = 0; j < k; j++) {
    const ang = 2 * Math.PI * j / k + 0.4;
    const rad = R * 0.5;
    z.push([rad * Math.cos(ang), rad * Math.sin(ang)]);
  }
  const ev = (x) => {
    let r = [1, 0];
    for (let j = 1; j <= k; j++) r = cadd(cmul(r, x), [a[j], 0]);
    return r;
  };
  for (let it = 0; it < 2000; it++) {
    let delta = 0;
    for (let i = 0; i < k; i++) {
      let den = [1, 0];
      for (let j = 0; j < k; j++) if (j !== i) den = cmul(den, csub(z[i], z[j]));
      if (den[0] === 0 && den[1] === 0) den = [1e-12, 0];
      const step = cdiv(ev(z[i]), den);
      z[i] = csub(z[i], step);
      delta = Math.max(delta, Math.hypot(step[0], step[1]));
    }
    if (delta < 1e-13) break;
  }
  return z;
}

function findProgressions(zeros, N) {
  const zset = new Set(zeros);
  const covered = new Set();
  const found = [];
  for (let m = 1; m <= Math.floor(N / 3); m++) {
    for (let r = 0; r < m; r++) {
      const members = zeros.filter((n) => n % m === r);
      if (members.length < 3) continue;
      let start = -1;
      for (let n0 = r; n0 <= N; n0 += m) {
        let all = true;
        for (let n = n0; n <= N; n += m) if (!zset.has(n)) { all = false; break; }
        if (all) { start = n0; break; }
      }
      if (start < 0 || Math.floor((N - start) / m) < 2) continue;
      let fresh = false;
      for (let n = start; n <= N; n += m) if (!covered.has(n)) fresh = true;
      if (!fresh) continue;
      for (let n = start; n <= N; n += m) covered.add(n);
      found.push({ m, r, start });
    }
  }
  const isolated = zeros.filter((n) => !covered.has(n));
  return { found, isolated };
}

function modPattern(c, init, p) {
  const k = c.length;
  const bp = BigInt(p);
  const cm = c.map((x) => Number(((x % bp) + bp) % bp));
  let st = [];
  for (let i = 0; i < k; i++) st.push(Number(((init[i] % bp) + bp) % bp));
  const seen = new Map();
  const seq = [];
  const CAP = 20000;
  let n = 0;
  while (n < CAP) {
    const key = st.join(',');
    if (seen.has(key)) {
      const mu = seen.get(key);
      return { mu, L: n - mu, seq: seq.slice(mu, n), full: true };
    }
    seen.set(key, n);
    seq.push(st[0]);
    let nx = 0;
    for (let j = 0; j < k; j++) nx += cm[j] * st[k - 1 - j];
    st = st.slice(1);
    st.push(nx % p);
    n++;
  }
  return { mu: 0, L: 0, seq: [], full: false };
}

function drawPlot(u, zeros) {
  const cv = $('plot');
  const w = cv.clientWidth || 600;
  const h = 150;
  const dpr = window.devicePixelRatio || 1;
  cv.width = Math.floor(w * dpr);
  cv.height = Math.floor(h * dpr);
  const g = cv.getContext('2d');
  g.setTransform(dpr, 0, 0, dpr, 0, 0);
  const css = getComputedStyle(document.documentElement);
  g.clearRect(0, 0, w, h);
  const logs = u.map(log10Big);
  const mx = Math.max(1, ...logs);
  const mid = h / 2;
  const bw = w / u.length;
  for (let n = 0; n < u.length; n++) {
    const x = n * bw;
    if (u[n] === 0n) continue;
    const hh = (logs[n] / mx) * (mid - 8);
    g.fillStyle = css.getPropertyValue(u[n] > 0n ? '--pos' : '--neg');
    if (u[n] > 0n) g.fillRect(x, mid - hh, Math.max(1, bw - 0.5), hh);
    else g.fillRect(x, mid, Math.max(1, bw - 0.5), hh);
  }
  g.strokeStyle = css.getPropertyValue('--muted');
  g.beginPath();
  g.moveTo(0, mid);
  g.lineTo(w, mid);
  g.stroke();
  g.fillStyle = css.getPropertyValue('--zero');
  for (const n of zeros) {
    g.beginPath();
    g.arc(n * bw + bw / 2, mid, Math.max(2.5, Math.min(5, bw)), 0, 2 * Math.PI);
    g.fill();
  }
  g.fillStyle = css.getPropertyValue('--muted');
  g.font = '11px system-ui, sans-serif';
  g.fillText('log10|u|  ' + mx.toFixed(1), 4, 12);
  g.fillText('n = 0 … ' + (u.length - 1), 4, h - 4);
}

function drawRoots(roots) {
  const cv = $('cplane');
  const w = cv.clientWidth || 600;
  const h = 210;
  const dpr = window.devicePixelRatio || 1;
  cv.width = Math.floor(w * dpr);
  cv.height = Math.floor(h * dpr);
  const g = cv.getContext('2d');
  g.setTransform(dpr, 0, 0, dpr, 0, 0);
  const css = getComputedStyle(document.documentElement);
  const mods = roots.map((z) => Math.hypot(z[0], z[1]));
  const rmax = Math.max(...mods, 1e-9);
  const scale = (Math.min(w / 2, h / 2) - 14) / (rmax * 1.1);
  const cx = w / 2;
  const cy = h / 2;
  g.strokeStyle = css.getPropertyValue('--line');
  g.beginPath();
  g.moveTo(0, cy); g.lineTo(w, cy); g.moveTo(cx, 0); g.lineTo(cx, h);
  g.stroke();
  g.setLineDash([3, 3]);
  g.beginPath();
  g.arc(cx, cy, 1 * scale, 0, 2 * Math.PI);
  g.stroke();
  g.beginPath();
  g.arc(cx, cy, rmax * scale, 0, 2 * Math.PI);
  g.strokeStyle = css.getPropertyValue('--dom');
  g.stroke();
  g.setLineDash([]);
  roots.forEach((z, i) => {
    const dom = mods[i] >= rmax * (1 - 1e-3);
    g.fillStyle = css.getPropertyValue(dom ? '--dom' : '--oth');
    g.beginPath();
    g.arc(cx + z[0] * scale, cy - z[1] * scale, dom ? 6 : 4.5, 0, 2 * Math.PI);
    g.fill();
  });
  g.fillStyle = css.getPropertyValue('--muted');
  g.font = '11px system-ui, sans-serif';
  g.fillText('Re', w - 18, cy - 4);
  g.fillText('Im', cx + 4, 12);
  g.fillText('|z| = 1', cx + scale + 3, cy + 12);
}

function showFormula(c) {
  const parts = c.map((x, j) => '(' + x + ')·u(n−' + (j + 1) + ')');
  $('formula').textContent = 'u(n) = ' + parts.join(' + ');
}

function run() {
  $('err').textContent = '';
  let c, init;
  try {
    c = parseList($('coef').value);
    init = parseList($('init').value);
  } catch (e) {
    $('err').textContent = "Enter integers separated by commas, for example: 1, 1";
    return;
  }
  if (c.length < 1 || c.length > 6) { $('err').textContent = "The order must be between 1 and 6."; return; }
  if (init.length !== c.length) { $('err').textContent = fmt("You need exactly %k% initial values, one per coefficient.", { k: c.length }); return; }
  let N = parseInt($('nmax').value, 10);
  if (!(N >= 10)) N = 10;
  if (N > 400) N = 400;
  $('nmax').value = N;
  showFormula(c);
  const u = genTerms(c, init, N);
  const zeros = zeroIndices(u);
  const head = u.slice(0, 14).map((x) => {
    const s = x.toString();
    return s.length > 14 ? s.slice(0, 6) + '…(' + s.length + ')' : s;
  });
  $('terms').textContent = head.join(', ') + ', …';
  const zEl = $('zeros');
  const apEl = $('ap');
  zEl.textContent = '';
  apEl.textContent = '';
  if (zeros.length === 0) {
    zEl.textContent = fmt("No zero among u(0) … u(%n%).", { n: N });
  } else {
    zEl.append(fmt("%z% zeros among u(0) … u(%n%):", { z: zeros.length, n: N }) + ' ');
    zeros.slice(0, 60).forEach((n) => {
      const s = document.createElement('span');
      s.className = 'zchip';
      s.textContent = n;
      zEl.appendChild(s);
    });
    if (zeros.length > 60) zEl.append('…');
    if (zeros.length === u.length) {
      apEl.textContent = "Every term is zero.";
    } else {
      const { found, isolated } = findProgressions(zeros, N);
      const lines = found.map((f) => fmt("Pattern: u(n) = 0 for every n ≡ %r% (mod %m%) from n = %s% on.", { r: f.r, m: f.m, s: f.start }));
      if (isolated.length) lines.push(fmt("Isolated zeros: %list%", { list: isolated.slice(0, 20).join(', ') }));
      apEl.innerHTML = lines.join('<br>');
    }
  }
  drawPlot(u, zeros);
  const roots = charRoots(c);
  drawRoots(roots);
  const mods = roots.map((z) => Math.hypot(z[0], z[1]));
  const rmax = Math.max(...mods);
  $('rootlist').innerHTML = roots.map((z, i) => {
    const dom = mods[i] >= rmax * (1 - 1e-3);
    const im = (z[1] < 0 ? '−' : '+') + Math.abs(z[1]).toFixed(4);
    const t = z[0].toFixed(4) + ' ' + im + 'i  |z|=' + mods[i].toFixed(4);
    return dom ? '<b>' + t + '</b>' : t;
  }).join('<br>');
  const rows = [];
  for (const p of PRIMES) {
    const r = modPattern(c, init, p);
    if (!r.full) { rows.push(fmt("mod %p%: period longer than the search limit", { p })); continue; }
    const shown = r.seq.slice(0, 48).map((x) => (x === 0 ? '<b>0</b>' : '·')).join('');
    const nz = r.seq.filter((x) => x === 0).length;
    rows.push(fmt("mod %p%: period %L% (after %mu% preperiodic terms), %z% zero positions per period", { p, L: r.L, mu: r.mu, z: nz }) + '<br><span class="bits">' + shown + (r.L > 48 ? '…' : '') + '</span>');
  }
  $('modtab').innerHTML = rows.join('<br>');
}

function loadPreset() {
  const p = PRESETS[$('preset').value];
  $('coef').value = p.c;
  $('init').value = p.i;
  $('nmax').value = p.n;
  run();
}

$('preset').addEventListener('change', loadPreset);
$('run').addEventListener('click', run);
$('coef').addEventListener('input', () => { $('preset').value = 'custom'; });
$('init').addEventListener('input', () => { $('preset').value = 'custom'; });
window.addEventListener('resize', run);
run();

<div class="wrap">
  <div class="row">
    <label for="preset">Example</label>
    <select id="preset">
      <option value="fib">Fibonacci (one zero, at n = 0)</option>
      <option value="trib">Tribonacci from 0, 0, 1</option>
      <option value="ap">A rotating sequence (zeros every 4 steps)</option>
      <option value="two">Two progressions (multiples of 3 or 4)</option>
      <option value="sporadic">2^n − n^2 (two isolated zeros)</option>
      <option value="custom">Your own recurrence</option>
    </select>
  </div>
  <div class="formula" id="formula"></div>
  <div class="row">
    <label for="coef">Coefficients c1…ck</label>
    <input id="coef" type="text" value="1, 1" spellcheck="false" aria-label="Coefficients of the recurrence, separated by commas">
  </div>
  <div class="row">
    <label for="init">Initial values u(0)…u(k−1)</label>
    <input id="init" type="text" value="0, 1" spellcheck="false" aria-label="Initial values, separated by commas">
  </div>
  <div class="row">
    <label for="nmax">Compute up to n =</label>
    <input id="nmax" type="number" min="10" max="400" value="120">
    <button id="run" type="button">Compute</button>
  </div>
  <div class="err" id="err" role="alert"></div>
  <div class="card">
    <div class="h">First terms</div>
    <div class="mono" id="terms"></div>
  </div>
  <div class="card">
    <div class="h">Zeros found</div>
    <div id="zeros"></div>
    <div id="ap" class="ap"></div>
  </div>
  <div class="card">
    <div class="h">Sign and size of each term</div>
    <canvas id="plot" height="150" aria-label="Bar chart of the sign and base-10 logarithm of the magnitude of each term"></canvas>
    <div class="legend"><span class="sw pos"></span>positive <span class="sw neg"></span>negative <span class="sw zero"></span>zero</div>
  </div>
  <div class="card">
    <div class="h">Characteristic roots in the complex plane</div>
    <canvas id="cplane" height="210" aria-label="Complex plane showing the roots of the characteristic polynomial"></canvas>
    <div class="legend"><span class="dot dom"></span>dominant roots (largest modulus) <span class="dot oth"></span>other roots</div>
    <div class="mono small" id="rootlist"></div>
  </div>
  <div class="card">
    <div class="h">Zeros modulo small primes</div>
    <div class="small">Reduce the sequence mod p. A true zero is always a zero mod every p, and mod p the sequence is eventually periodic. Bold 0 marks positions that vanish mod p, over one period.</div>
    <div class="mono small" id="modtab"></div>
  </div>
</div>

:root {
  --bg: #ffffff; --fg: #1d2733; --muted: #5b6878; --card: #f2f5f9; --line: #d3dbe5;
  --accent: #1d5fa8; --pos: #2a7fc4; --neg: #d9822b; --zero: #d23c4a; --on-accent: #ffffff;
  --dom: #d23c4a; --oth: #6b7a8c;
}
@media (prefers-color-scheme: dark) {
  :root {
    --bg: #14181d; --fg: #e4eaf1; --muted: #9aa8b8; --card: #1d2430; --line: #333e4d;
    --accent: #6cb0f0; --pos: #5aa9ec; --neg: #f0a24f; --zero: #ff6b78; --on-accent: #0b1117;
    --dom: #ff6b78; --oth: #8fa0b4;
  }
}
* { box-sizing: border-box; }
body { margin: 0; background: var(--bg); color: var(--fg); font: 14px/1.45 system-ui, sans-serif; }
.wrap { padding: 8px; max-width: 760px; margin: 0 auto; }
.row { display: flex; gap: 8px; align-items: center; flex-wrap: wrap; margin: 6px 0; }
label { font-weight: 600; min-width: 96px; }
select, input { font: inherit; color: var(--fg); background: var(--card); border: 1px solid var(--line); border-radius: 6px; padding: 5px 8px; min-width: 0; flex: 1 1 140px; }
input[type=number] { flex: 0 0 90px; }
button { font: 600 14px system-ui, sans-serif; padding: 6px 14px; border: 0; border-radius: 6px; background: var(--accent); color: var(--on-accent); cursor: pointer; }
.formula { font-family: ui-monospace, Consolas, monospace; color: var(--muted); font-size: 13px; overflow-wrap: anywhere; }
.err { color: var(--zero); font-weight: 600; min-height: 1.2em; }
.card { background: var(--card); border: 1px solid var(--line); border-radius: 8px; padding: 8px 10px; margin: 8px 0; }
.h { font-weight: 700; margin-bottom: 4px; }
.mono { font-family: ui-monospace, Consolas, monospace; overflow-wrap: anywhere; }
.small { font-size: 12.5px; color: var(--muted); }
canvas { width: 100%; display: block; background: var(--bg); border: 1px solid var(--line); border-radius: 6px; }
.legend { font-size: 12px; color: var(--muted); margin-top: 4px; display: flex; flex-wrap: wrap; gap: 4px 10px; align-items: center; }
.sw { display: inline-block; width: 10px; height: 10px; margin-right: 3px; border-radius: 2px; }
.sw.pos { background: var(--pos); } .sw.neg { background: var(--neg); } .sw.zero { background: var(--zero); }
.dot { display: inline-block; width: 10px; height: 10px; margin-right: 3px; border-radius: 50%; }
.dot.dom { background: var(--dom); } .dot.oth { background: var(--oth); }
.zchip { display: inline-block; background: var(--zero); color: #fff; border-radius: 10px; padding: 0 7px; margin: 2px 3px 2px 0; font: 600 12px ui-monospace, monospace; }
.ap { margin-top: 6px; font-weight: 600; color: var(--accent); }
.bits { letter-spacing: 1px; }
.bits b { color: var(--zero); }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
const PRESETS = {
  fib: { c: '1, 1', i: '0, 1', n: 120 },
  trib: { c: '1, 1, 1', i: '0, 0, 1', n: 120 },
  ap: { c: '2, -2', i: '0, 1', n: 120 },
  two: { c: '2, -2, 4, -4', i: '0, 1, 2, 0', n: 120 },
  sporadic: { c: '5, -9, 7, -2', i: '1, 1, 0, -1', n: 120 },
  custom: { c: '0, 0, 0, 0, 1, 1', i: '1, 0, 0, 0, 0, 3', n: 120 }
};
const PRIMES = [2, 3, 5, 7, 11, 13];
const $ = (id) => document.getElementById(id);

function parseList(text) {
  const parts = text.split(/[\s,;]+/).filter((x) => x.length);
  return parts.map((p) => {
    if (!/^[+-]?\d+$/.test(p)) throw new Error('bad');
    return BigInt(p);
  });
}

function genTerms(c, init, N) {
  const u = init.slice();
  const k = c.length;
  while (u.length <= N) {
    let s = 0n;
    for (let j = 0; j < k; j++) s += c[j] * u[u.length - 1 - j];
    u.push(s);
  }
  return u.slice(0, N + 1);
}

function zeroIndices(u) {
  const z = [];
  for (let n = 0; n < u.length; n++) if (u[n] === 0n) z.push(n);
  return z;
}

function log10Big(x) {
  const s = (x < 0n ? -x : x).toString();
  if (s.length <= 15) return Math.log10(Number(s) + 1);
  return s.length - 1 + Math.log10(Number(s.slice(0, 15)) / 1e14);
}

function cmul(a, b) { return [a[0] * b[0] - a[1] * b[1], a[0] * b[1] + a[1] * b[0]]; }
function cadd(a, b) { return [a[0] + b[0], a[1] + b[1]]; }
function csub(a, b) { return [a[0] - b[0], a[1] - b[1]]; }
function cdiv(a, b) {
  const d = b[0] * b[0] + b[1] * b[1];
  return [(a[0] * b[0] + a[1] * b[1]) / d, (a[1] * b[0] - a[0] * b[1]) / d];
}

function charRoots(c) {
  const k = c.length;
  const a = [1];
  for (let j = 0; j < k; j++) a.push(-Number(c[j]));
  let R = 1;
  for (let j = 1; j <= k; j++) R = Math.max(R, 1 + Math.abs(a[j]));
  const z = [];
  for (let j = 0; j < k; j++) {
    const ang = 2 * Math.PI * j / k + 0.4;
    const rad = R * 0.5;
    z.push([rad * Math.cos(ang), rad * Math.sin(ang)]);
  }
  const ev = (x) => {
    let r = [1, 0];
    for (let j = 1; j <= k; j++) r = cadd(cmul(r, x), [a[j], 0]);
    return r;
  };
  for (let it = 0; it < 2000; it++) {
    let delta = 0;
    for (let i = 0; i < k; i++) {
      let den = [1, 0];
      for (let j = 0; j < k; j++) if (j !== i) den = cmul(den, csub(z[i], z[j]));
      if (den[0] === 0 && den[1] === 0) den = [1e-12, 0];
      const step = cdiv(ev(z[i]), den);
      z[i] = csub(z[i], step);
      delta = Math.max(delta, Math.hypot(step[0], step[1]));
    }
    if (delta < 1e-13) break;
  }
  return z;
}

function findProgressions(zeros, N) {
  const zset = new Set(zeros);
  const covered = new Set();
  const found = [];
  for (let m = 1; m <= Math.floor(N / 3); m++) {
    for (let r = 0; r < m; r++) {
      const members = zeros.filter((n) => n % m === r);
      if (members.length < 3) continue;
      let start = -1;
      for (let n0 = r; n0 <= N; n0 += m) {
        let all = true;
        for (let n = n0; n <= N; n += m) if (!zset.has(n)) { all = false; break; }
        if (all) { start = n0; break; }
      }
      if (start < 0 || Math.floor((N - start) / m) < 2) continue;
      let fresh = false;
      for (let n = start; n <= N; n += m) if (!covered.has(n)) fresh = true;
      if (!fresh) continue;
      for (let n = start; n <= N; n += m) covered.add(n);
      found.push({ m, r, start });
    }
  }
  const isolated = zeros.filter((n) => !covered.has(n));
  return { found, isolated };
}

function modPattern(c, init, p) {
  const k = c.length;
  const bp = BigInt(p);
  const cm = c.map((x) => Number(((x % bp) + bp) % bp));
  let st = [];
  for (let i = 0; i < k; i++) st.push(Number(((init[i] % bp) + bp) % bp));
  const seen = new Map();
  const seq = [];
  const CAP = 20000;
  let n = 0;
  while (n < CAP) {
    const key = st.join(',');
    if (seen.has(key)) {
      const mu = seen.get(key);
      return { mu, L: n - mu, seq: seq.slice(mu, n), full: true };
    }
    seen.set(key, n);
    seq.push(st[0]);
    let nx = 0;
    for (let j = 0; j < k; j++) nx += cm[j] * st[k - 1 - j];
    st = st.slice(1);
    st.push(nx % p);
    n++;
  }
  return { mu: 0, L: 0, seq: [], full: false };
}

function drawPlot(u, zeros) {
  const cv = $('plot');
  const w = cv.clientWidth || 600;
  const h = 150;
  const dpr = window.devicePixelRatio || 1;
  cv.width = Math.floor(w * dpr);
  cv.height = Math.floor(h * dpr);
  const g = cv.getContext('2d');
  g.setTransform(dpr, 0, 0, dpr, 0, 0);
  const css = getComputedStyle(document.documentElement);
  g.clearRect(0, 0, w, h);
  const logs = u.map(log10Big);
  const mx = Math.max(1, ...logs);
  const mid = h / 2;
  const bw = w / u.length;
  for (let n = 0; n < u.length; n++) {
    const x = n * bw;
    if (u[n] === 0n) continue;
    const hh = (logs[n] / mx) * (mid - 8);
    g.fillStyle = css.getPropertyValue(u[n] > 0n ? '--pos' : '--neg');
    if (u[n] > 0n) g.fillRect(x, mid - hh, Math.max(1, bw - 0.5), hh);
    else g.fillRect(x, mid, Math.max(1, bw - 0.5), hh);
  }
  g.strokeStyle = css.getPropertyValue('--muted');
  g.beginPath();
  g.moveTo(0, mid);
  g.lineTo(w, mid);
  g.stroke();
  g.fillStyle = css.getPropertyValue('--zero');
  for (const n of zeros) {
    g.beginPath();
    g.arc(n * bw + bw / 2, mid, Math.max(2.5, Math.min(5, bw)), 0, 2 * Math.PI);
    g.fill();
  }
  g.fillStyle = css.getPropertyValue('--muted');
  g.font = '11px system-ui, sans-serif';
  g.fillText('log10|u|  ' + mx.toFixed(1), 4, 12);
  g.fillText('n = 0 … ' + (u.length - 1), 4, h - 4);
}

function drawRoots(roots) {
  const cv = $('cplane');
  const w = cv.clientWidth || 600;
  const h = 210;
  const dpr = window.devicePixelRatio || 1;
  cv.width = Math.floor(w * dpr);
  cv.height = Math.floor(h * dpr);
  const g = cv.getContext('2d');
  g.setTransform(dpr, 0, 0, dpr, 0, 0);
  const css = getComputedStyle(document.documentElement);
  const mods = roots.map((z) => Math.hypot(z[0], z[1]));
  const rmax = Math.max(...mods, 1e-9);
  const scale = (Math.min(w / 2, h / 2) - 14) / (rmax * 1.1);
  const cx = w / 2;
  const cy = h / 2;
  g.strokeStyle = css.getPropertyValue('--line');
  g.beginPath();
  g.moveTo(0, cy); g.lineTo(w, cy); g.moveTo(cx, 0); g.lineTo(cx, h);
  g.stroke();
  g.setLineDash([3, 3]);
  g.beginPath();
  g.arc(cx, cy, 1 * scale, 0, 2 * Math.PI);
  g.stroke();
  g.beginPath();
  g.arc(cx, cy, rmax * scale, 0, 2 * Math.PI);
  g.strokeStyle = css.getPropertyValue('--dom');
  g.stroke();
  g.setLineDash([]);
  roots.forEach((z, i) => {
    const dom = mods[i] >= rmax * (1 - 1e-3);
    g.fillStyle = css.getPropertyValue(dom ? '--dom' : '--oth');
    g.beginPath();
    g.arc(cx + z[0] * scale, cy - z[1] * scale, dom ? 6 : 4.5, 0, 2 * Math.PI);
    g.fill();
  });
  g.fillStyle = css.getPropertyValue('--muted');
  g.font = '11px system-ui, sans-serif';
  g.fillText('Re', w - 18, cy - 4);
  g.fillText('Im', cx + 4, 12);
  g.fillText('|z| = 1', cx + scale + 3, cy + 12);
}

function showFormula(c) {
  const parts = c.map((x, j) => '(' + x + ')·u(n−' + (j + 1) + ')');
  $('formula').textContent = 'u(n) = ' + parts.join(' + ');
}

function run() {
  $('err').textContent = '';
  let c, init;
  try {
    c = parseList($('coef').value);
    init = parseList($('init').value);
  } catch (e) {
    $('err').textContent = "Enter integers separated by commas, for example: 1, 1";
    return;
  }
  if (c.length < 1 || c.length > 6) { $('err').textContent = "The order must be between 1 and 6."; return; }
  if (init.length !== c.length) { $('err').textContent = fmt("You need exactly %k% initial values, one per coefficient.", { k: c.length }); return; }
  let N = parseInt($('nmax').value, 10);
  if (!(N >= 10)) N = 10;
  if (N > 400) N = 400;
  $('nmax').value = N;
  showFormula(c);
  const u = genTerms(c, init, N);
  const zeros = zeroIndices(u);
  const head = u.slice(0, 14).map((x) => {
    const s = x.toString();
    return s.length > 14 ? s.slice(0, 6) + '…(' + s.length + ')' : s;
  });
  $('terms').textContent = head.join(', ') + ', …';
  const zEl = $('zeros');
  const apEl = $('ap');
  zEl.textContent = '';
  apEl.textContent = '';
  if (zeros.length === 0) {
    zEl.textContent = fmt("No zero among u(0) … u(%n%).", { n: N });
  } else {
    zEl.append(fmt("%z% zeros among u(0) … u(%n%):", { z: zeros.length, n: N }) + ' ');
    zeros.slice(0, 60).forEach((n) => {
      const s = document.createElement('span');
      s.className = 'zchip';
      s.textContent = n;
      zEl.appendChild(s);
    });
    if (zeros.length > 60) zEl.append('…');
    if (zeros.length === u.length) {
      apEl.textContent = "Every term is zero.";
    } else {
      const { found, isolated } = findProgressions(zeros, N);
      const lines = found.map((f) => fmt("Pattern: u(n) = 0 for every n ≡ %r% (mod %m%) from n = %s% on.", { r: f.r, m: f.m, s: f.start }));
      if (isolated.length) lines.push(fmt("Isolated zeros: %list%", { list: isolated.slice(0, 20).join(', ') }));
      apEl.innerHTML = lines.join('<br>');
    }
  }
  drawPlot(u, zeros);
  const roots = charRoots(c);
  drawRoots(roots);
  const mods = roots.map((z) => Math.hypot(z[0], z[1]));
  const rmax = Math.max(...mods);
  $('rootlist').innerHTML = roots.map((z, i) => {
    const dom = mods[i] >= rmax * (1 - 1e-3);
    const im = (z[1] < 0 ? '−' : '+') + Math.abs(z[1]).toFixed(4);
    const t = z[0].toFixed(4) + ' ' + im + 'i  |z|=' + mods[i].toFixed(4);
    return dom ? '<b>' + t + '</b>' : t;
  }).join('<br>');
  const rows = [];
  for (const p of PRIMES) {
    const r = modPattern(c, init, p);
    if (!r.full) { rows.push(fmt("mod %p%: period longer than the search limit", { p })); continue; }
    const shown = r.seq.slice(0, 48).map((x) => (x === 0 ? '<b>0</b>' : '·')).join('');
    const nz = r.seq.filter((x) => x === 0).length;
    rows.push(fmt("mod %p%: period %L% (after %mu% preperiodic terms), %z% zero positions per period", { p, L: r.L, mu: r.mu, z: nz }) + '<br><span class="bits">' + shown + (r.L > 48 ? '…' : '') + '</span>');
  }
  $('modtab').innerHTML = rows.join('<br>');
}

function loadPreset() {
  const p = PRESETS[$('preset').value];
  $('coef').value = p.c;
  $('init').value = p.i;
  $('nmax').value = p.n;
  run();
}

$('preset').addEventListener('change', loadPreset);
$('run').addEventListener('click', run);
$('coef').addEventListener('input', () => { $('preset').value = 'custom'; });
$('init').addEventListener('input', () => { $('preset').value = 'custom'; });
window.addEventListener('resize', run);
run();

Result

Console

Some things to try:

Fibonacci has a single zero, at $n=0$ . Its two characteristic roots are real, and the larger one (the golden ratio) dominates.
The rotating sequence has roots $1\pm i$ , which have the same modulus. Neither dominates, the signs rotate, and the zeros form the progression $n\equiv 0 \pmod 4$ .
Two progressions is the product of that sequence with another rotating one, and its zeros are the multiples of $3$ or of $4$ .
$2^n-n^2$ has only two zeros, at $n=2$ and $n=4$ , and then the exponential wins for good. This is the shape of the hard instances: a few sporadic zeros that no pattern predicts.
Look at the plane of roots. Roots of the same largest modulus compete, and that competition is where the number theory gets hard.
The modular table shows the sequence reduced modulo small primes. Every true zero is also a zero modulo every number, so a modulus where the sequence never vanishes would prove there is no zero. This is the idea behind the Skolem Conjecture described below.

The Real Complexity

Setting. A linear recurrence sequence has the closed form $u_n=\sum_i P_i(n)\,\lambda_i^{\,n}$ , where the $\lambda_i$ are the roots of the characteristic polynomial $x^k-c_1x^{k-1}-\dots-c_k$ and the $P_i$ are polynomials. For Fibonacci, $u_n=(\varphi^n-\psi^n)/\sqrt5$ . A zero is a solution $n$ of an exponential equation in one integer unknown.

A semi-decision procedure. Zeros are easy to find and hard to rule out:

n = 0
loop:
    if u(n) == 0: return "zero at n"
    n = n + 1          # never stops if there is no zero

This halts exactly on the "yes" instances. A decision procedure also needs a bound $B$ , computable from the input, such that no zero can occur beyond $B$ . Nobody knows how to compute one in general.

What is known.

Skolem–Mahler–Lech theorem. Skolem (1934), Mahler (1935) and Lech (1953) proved successively more general versions of the same statement: over a field of characteristic $0$ , the zero set of any LRS is a finite set together with finitely many arithmetic progressions. The proof uses $p$ -adic analysis and is ineffective: it does not give a bound on where the last sporadic zero can be, so it does not yield an algorithm. Characteristic $0$ is essential. Over $\mathbb F_p(t)$ , the sequence $(1+t)^n-t^n-1$ has zeros exactly at the powers of $p$ , which is not a finite union of progressions.
Number of zeros. A bound on the number of zeros of a non-degenerate sequence in terms of the order alone is known (this is a result of W. M. Schmidt). A bound on how large the zeros can be is a different and much harder matter.
Orders up to 4 are decidable. Mignotte, Shorey and Tijdeman (1984) and, independently, Vereshchagin (1985) showed the Skolem Problem is decidable for orders at most $4$ . The tool is Baker's theory of linear forms in logarithms, together with its $p$ -adic analogues, which bound the zeros when one root dominates the others.
Order 5 and above is open. In 2005 a proof for order $5$ was announced, but it was later found to have a serious gap, and it is not accepted. A 2026 survey by Bacik, Karimov, Luca, Nieuwveld, Ouaknine, Purser and Worrell exhibits a concrete order-6 integer sequence for which the problem remains unsolved.
Hardness. Blondel and Portier (2002) proved that the problem is NP-hard when the order is part of the input. No upper bound on the complexity is known for general orders, because it is not even known to be decidable.
Positivity. The companion question is whether $u_n\ge 0$ for all $n$ . Ouaknine and Worrell (SODA 2014) showed Positivity is decidable up to order $5$ , and that extending this to order $6$ would require major advances in the Diophantine approximation of transcendental numbers. Positivity is at least as hard as Skolem through a transformation that increases the order: a Skolem instance of order $k$ becomes a Positivity instance of higher order, so decidability of Positivity would settle Skolem but not conversely.
Conditional algorithms. Bilu, Luca, Nieuwveld, Ouaknine, Purser and Worrell (arXiv preprint, April 2022, Skolem Meets Schanuel) gave an algorithm for simple sequences, meaning all characteristic roots are distinct. When it halts it outputs the exact zero set with a certificate. They proved it always halts assuming two conjectures: the Skolem Conjecture, an exponential local-global principle (roughly: a sequence with no zero should always reveal this modulo some number), and the $p$ -adic Schanuel Conjecture. A 2025 follow-up on the $p$ -adic Skolem problem (Bacik, Ouaknine, Purser, Worrell; STACS 2026) keeps correctness unconditional and makes only termination depend on $p$ -adic Schanuel.
Recent progress. The 2026 survey also reports randomized polynomial-time algorithms for low orders and "universal Skolem sets" of density one, and discusses barriers for Positivity beyond order $5$ .

Why it is hard. A zero means that finitely many complex exponentials cancel perfectly, $\sum_i P_i(n)\lambda_i^n=0$ . When the roots have different moduli, the largest one wins for big $n$ and the zeros are bounded. When several roots share the largest modulus they rotate against each other, and whether the rotation lands exactly on a cancellation is a question about how well irrational angles can be approximated by rationals. Controlling that is the content of Baker-type bounds, and they are not strong enough yet for general order $5$ and above.

Where It Matters

Recurrences are the arithmetic of linear dynamical systems, so a question about their zeros is a question about what such systems can do.

Linear dynamical systems. If a state vector evolves as $x_{n+1}=Mx_n$ and we ask whether it ever lands on the hyperplane $\{x: c^{\top}x=0\}$ , the quantity $c^{\top}M^nx_0$ is a linear recurrence sequence by the Cayley–Hamilton theorem. Asking whether the orbit reaches a specific point is the Orbit Problem, which Kannan and Lipton showed decidable in polynomial time in 1986. The hyperplane version is the Skolem Problem and is still open.
Program termination and verification. A loop that repeatedly applies a linear update and exits when a linear guard becomes true is analyzed through exactly these sequences. This is a tame cousin of termination analysis, and a decision procedure for Skolem would settle the corresponding reachability questions.
Markov chains and automata. The probability that a Markov chain is in a given set at step $n$ , or the weight a one-letter weighted automaton assigns to the word of length $n$ , is a linear recurrence sequence in $n$ . Whether that quantity ever equals a given rational threshold exactly is a Skolem instance.
Number theory. A zero is a solution to a one-variable exponential Diophantine equation, and Baker's method, continued fractions and $p$ -adic analysis are the tools that apply.
A map of the frontier. Unrestricted products of matrices can encode undecidable problems, as with mortal matrices, and the halting problem is the template for those. A single matrix power is far tamer, and Skolem is the point where that tameness is not yet understood.

The same recurrences also show how deceptive simple systems can be. Compare the Collatz conjecture, where one explicit rule defeats all known proof methods.

Conclusion

The Skolem Problem is as small as an open problem gets: a recurrence, some integers, one yes-or-no question. Zeros, when they exist, are easy to find. The structure of the full zero set is understood through the Skolem–Mahler–Lech theorem. Yet nobody can say, for every recurrence, how far one would have to look before concluding that no zero exists.

What we do know is a ladder: decidable up to order $4$ , NP-hard in general, tied to Positivity and to Diophantine approximation, and conditionally solvable for simple sequences if two deep conjectures in $p$ -adic number theory hold. Each rung required new mathematics, and the next one may too.

Try the explorer on an order-5 or order-6 recurrence of your own. You will find the zeros in a heartbeat, if there are any. Proving that you have found them all is the open problem.

Comments

Loading comments...

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

Cookies & privacy

The Skolem Problem

A one-line rule, a few integers, and a question nobody can answer in general