// job67-alt-exact-check.js -- mechanism check for Theorem 2 of the // tailcount-transport manuscript: every window of the old cyclic gap word // whose interior class word admits a legal walk on a 2-set mod q is a // sub-window of a realised maximal kill run at some alignment, so its sum is // at most a realised new gap; hence M_alt = G2(new). Stored tiles T_5..T_19 // folded by the next prime (folds 7..23), every window with a legal interior // enumerated, alignment set A_L(i) computed directly from the definition and // checked non-empty, the realised run at each a in A_L(i) extended on the big // tile Z/(qW), and the containment asserted. Also checks SUM_L nu_q(i,L) = q-2 // for every i, and M_alt = G2(new) = max realised gap. // run: node job67-alt-exact-check.js 'use strict'; function buildTiles() { const out = []; let P = 6, S = [5]; for (const q of [5, 7, 11, 13, 17, 19]) { const keep = []; for (let k = 0; k < q; k++) for (const s of S) { const r = s + k * P; if (r % q !== 0 && (r + 2) % q !== 0) keep.push(r); } P *= q; S = keep; out.push({ x: q, W: P, S }); } return out; } const NEXT = { 5: 7, 7: 11, 11: 13, 13: 17, 17: 19, 19: 23 }; const EXP_G2 = { 7: 30, 11: 42, 13: 66, 17: 108, 19: 150, 23: 204 }; const EXP_ALT = { 7: 30, 11: 42, 13: 66, 17: 108, 19: 150, 23: 204 }; let allOk = true; for (const t of buildTiles()) { const q = NEXT[t.x], W = t.W, S = t.S, D = S.length; const g = new Array(D); for (let i = 0; i < D; i++) g[i] = (i + 1 < D ? S[i + 1] : S[0] + W) - S[i]; const mod = (v, m) => ((v % m) + m) % m; // dead(v): position v in the big tile Z/(qW) dies iff q | v or q | v+2 const dead = v => mod(v, q) === 0 || mod(v + 2, q) === 0; const posOf = (idx, k) => { // slot index idx (any integer) in copy k: cyclic old index, turns add W const turns = Math.floor(idx / D), j = mod(idx, D); return S[j] + (k + turns) * W; }; // realised new gap of the maximal dead run containing old slots i+1..i+L in copy k const realised = (i, L, k) => { let lo = i + 1, hi = i + L; while (dead(posOf(lo - 1, k))) { lo--; if (i + 1 - lo > q * D) throw new Error('all dead?'); } while (dead(posOf(hi + 1, k))) { hi++; } return posOf(hi + 1, k) - posOf(lo - 1, k); }; // true G2(new) by direct fold let g2new = 0, dnew = 0; { const keep = []; for (let k = 0; k < q; k++) for (const s of S) { const v = s + k * W; if (!dead(v)) keep.push(v); } dnew = keep.length; for (let i = 0; i < keep.length; i++) { const d = (i + 1 < keep.length ? keep[i + 1] : keep[0] + q * W) - keep[i]; if (d > g2new) g2new = d; } } // enumerate windows with legal interiors; classes of gaps const cls = c => { const r = mod(c, q); return r === 0 ? 0 : r === 2 ? 2 : r === q - 2 ? -2 : null; }; let Malt = 0, nWin = 0, nChecked = 0, bad = 0, nuBad = 0, maxL = 0; for (let i = 0; i < D; i++) { // nu identity: for each a not in {0,2}, exactly one L const cnt = new Array(q).fill(0); for (let a = 0; a < q; a++) { if (a === 0 || a === 2) continue; let L = 0, G = 0; while (true) { G += g[mod(i + L, D)]; const r = mod(G, q); if (r === a || r === mod(a - 2, q)) { L++; if (L > 4 * D) throw new Error('loop'); } else break; } cnt[a]++; } let tot = 0; for (let a = 0; a < q; a++) tot += cnt[a]; if (tot !== q - 2) nuBad++; // windows of L+1 gaps starting at gap i, interior gaps i+1..i+L-1 must be a legal walk // state walk: from A legal {0,-2} (0 stays, -2 -> B); from B legal {0,+2} (0 stays, +2 -> A) for (let L = 1; ; L++) { // interior classes c_1..c_{L-1} let legalA = true, legalB = true; // walk starting in A / in B let stA = 'A', stB = 'B'; for (let j = 1; j <= L - 1; j++) { const c = cls(g[mod(i + j, D)]); if (c === null) { legalA = legalB = false; break; } if (legalA) { if (c === 0) {} else if (c === -2 && stA === 'A') stA = 'B'; else if (c === 2 && stA === 'B') stA = 'A'; else legalA = false; } if (legalB) { if (c === 0) {} else if (c === -2 && stB === 'A') stB = 'B'; else if (c === 2 && stB === 'B') stB = 'A'; else legalB = false; } } if (!legalA && !legalB) break; nWin++; if (L > maxL) maxL = L; let sum = 0; for (let j = 0; j <= L; j++) sum += g[mod(i + j, D)]; if (sum > Malt) Malt = sum; // A_L(i) directly from the definition: a with G_j in {a, a-2} for j = 1..L const AL = []; for (let a = 0; a < q; a++) { let G = 0, ok = true; for (let j = 1; j <= L; j++) { G += g[mod(i + j - 1, D)]; const r = mod(G, q); if (!(r === a || r === mod(a - 2, q))) { ok = false; break; } } if (ok) AL.push(a); } if (AL.length === 0) { bad++; console.log(' !! legal interior but A_L empty at i=' + i + ' L=' + L); continue; } if (AL.length > 2) { bad++; console.log(' !! |A_L| > 2'); } for (const a of AL) { // copy k with -(S[i] + kW) = a mod q let k = -1; for (let kk = 0; kk < q; kk++) if (mod(-(S[i] + kk * W), q) === a) { k = kk; break; } if (k < 0) { bad++; console.log(' !! no copy for a'); continue; } // slots i+1..i+L must be dead in copy k for (let j = 1; j <= L; j++) if (!dead(posOf(i + j, k))) { bad++; console.log(' !! interior slot alive at i=' + i + ' L=' + L + ' a=' + a); } const R = realised(i, L, k); nChecked++; if (R < sum) { bad++; console.log(' !! realised gap ' + R + ' < window sum ' + sum + ' at i=' + i + ' L=' + L); } } } } const ok = bad === 0 && nuBad === 0 && Malt === g2new && g2new === EXP_G2[q] && dnew === D * (q - 2); allOk = allOk && ok; console.log((ok ? 'ok ' : 'FAIL') + ' T_' + t.x + ' fold ' + q + ': D=' + D + ' D(new)=' + dnew + ' G2(new)=' + g2new + ' M_alt=' + Malt + ' legal windows=' + nWin + ' (max L=' + maxL + ') containments checked=' + nChecked + ' violations=' + bad + ' nu-identity failures=' + nuBad); } console.log(allOk ? 'ALL OK: every legal window sits inside a realised run; M_alt = G2(new) at folds 7..23' : 'SOME CHECK FAILED');