#!/usr/bin/env node 'use strict'; // job #12: break search for the Localized Merge Lemma, research/LOCALIZED-GAP.md sections 2, 3 and 8. // // Objects (as in research/localized-03-merge-lemma.js and -04-maxsum.js): T_x = the integers r >= 1 with r and // r+2 both x-rough (no prime factor <= x); folding by p = nextprime(x) kills the slots with r = 0 or -2 mod p. // M(T,Y) = largest gap of T starting below Y; maxsum_2(T,Y) = largest s_{i+2} - s_i with s_i < Y (right end // uncapped, the scripts' rule (a)). // // The three quantities change only at slots, so EVERY Y is covered by Y in (s_t, s_{t+1}] for each index t. // For every evaluated prime x and every such Y this checks // (L) M(T_x,Y) <= (p-2)/4 => M(T_p,Y) <= maxsum_2(T_x,Y) (the lemma as stated) // (L') every T_x gap starting at a slot <= the first slot >= Y is < p-2 => the same conclusion // and, for every new gap G starting at a slot a with M(T_x, a+1) <= (p-2)/4, the proof's steps with // M = M(T_x, a+1) (the smallest admissible Y) and with M = M(T_x, Y_end) (the largest): // j <= ceil(G/(p-2)), G <= (j+1)M, G <= (G/(p-2) + 2)M, G <= (8/3)M, G < p-2. // Fact B: the distance between consecutive kills against p-2, over every scanned slot. // Section S: maxsum_m under rules (a) start < Y, (b) whole window < Y, (c) slot list cut at Y+4096, at small Y. // // Deterministic; elapsed time goes to stderr. A finite search: a measurement, not a proof. // Usage: node lemma-boundary.js [YMAX=2^31] [XDENSE=5000] [NCHECK=20] [XTOP=20011] const YMAX = Number(process.argv[2] || 2 ** 31); const XDENSE = Number(process.argv[3] || 5000); const NCHECK = Number(process.argv[4] || 20); const XTOP = Number(process.argv[5] || 20011); const DENSE_CAP = Math.min(YMAX, 2 ** 26); if (!(YMAX + 70 < 2 ** 32)) throw new Error('YMAX too large for the 32-bit bitset'); const t0 = Date.now(); const el = () => ((Date.now() - t0) / 1000).toFixed(1); function primesUpTo(n) { const s = new Uint8Array(n + 1), out = []; for (let i = 2; i <= n; i++) if (!s[i]) { out.push(i); for (let j = i * i; j <= n; j += i) s[j] = 1; } return out; } const PR = primesUpTo(XTOP + 2000); const nextPrime = x => PR[PR.indexOf(x) + 1]; // ---- bitset of x-rough integers ---- const LIM = YMAX + 66; const W = new Uint32Array(Math.floor((YMAX + 70) / 32) + 2).fill(0xFFFFFFFF); W[0] &= ~1; function strike(p) { for (let j = p; j <= LIM; j += p) W[j >>> 5] &= ~(1 << (j & 31)); } function extract(B) { // twin slots r in [1, B] let out = new Uint32Array(1 << 16), n = 0; const lastW = Math.floor(B / 32); for (let w = 0; w <= lastW; w++) { const a = W[w]; if (a === 0) continue; let t = a & ((a >>> 2) | (W[w + 1] << 30)); if (t === 0) continue; const base = w * 32; while (t !== 0) { const low = t & -t, r = base + (31 - Math.clz32(low)); if (r >= 1 && r <= B) { if (n === out.length) { const g = new Uint32Array(out.length * 2); g.set(out); out = g; } out[n++] = r; } t ^= low; } } return { S: out, n }; } // ---- the scan for one (x, p) on slots S[0..n) ---- function scan(S, n, x, p, final) { const thr = (p - 2) / 4; const K = new Uint8Array(n); for (let i = 0; i < n; i++) K[i] = (S[i] % p === 0 || (S[i] + 2) % p === 0) ? 1 : 0; const NS = new Int32Array(n + 1); NS[n] = -1; for (let i = n - 1; i >= 0; i--) NS[i] = K[i] ? NS[i + 1] : i; const r = { x, p, thr, n, B: S[n - 1], A: { fused: 0, cells: 0, viol: 0, maxRatio: 0, maxJ: 0, j2: 0, newGaps: 0, Yend: null, Mend: 0, capped: false, failJ: 0, fail1: 0, fail2: 0, fail3: 0, failLen: 0, worst2: 0, worst1: 0, fail1End: 0, fail2End: 0, big4096: 0 }, Bp: { cells: 0, viol: 0, maxJ: 0, j2: 0, Yend: null, capped: false, big4096: 0 }, minKill: Infinity, closeKills: 0, kills: 0 }; let prevKill = -1; for (let i = 0; i < n; i++) if (K[i]) { r.kills++; if (prevKill >= 0) { const d = S[i] - S[prevKill]; if (d < r.minKill) r.minKill = d; if (d < p - 2) r.closeKills++; } prevKill = i; } let Mold = 0, ms2 = 0, Mnew = 0, doneA = false, doneB = false, stopA = -1; let t = 0; for (; t + 2 < n; t++) { const gap = S[t + 1] - S[t]; if (gap > Mold) Mold = gap; const w2 = S[t + 2] - S[t]; if (w2 > ms2) ms2 = w2; let G = -1, j = -1; if (!K[t]) { const nx = NS[t + 1]; if (nx < 0) break; // the new gap starting here ends beyond the data G = S[nx] - S[t]; j = nx - t - 1; if (G > Mnew) Mnew = G; } if (!doneA) { if (Mold > thr) { doneA = true; stopA = t; r.A.Yend = S[t]; } else { const A = r.A; A.cells++; A.Mend = Mold; if (Mnew > ms2) { A.viol++; console.log(` VIOLATION (L) x=${x} p=${p} Y in (${S[t]}, ${S[t + 1]}]: M(T_p,Y)=${Mnew} > maxsum_2(T_x,Y)=${ms2}, M(T_x,Y)=${Mold} <= ${thr}`); } if (Mnew / ms2 > A.maxRatio) A.maxRatio = Mnew / ms2; if (G >= 0) { A.newGaps++; if (j >= 1) A.fused++; if (j > A.maxJ) A.maxJ = j; if (j >= 2) { A.j2++; console.log(` BOUNDARY j>=2 inside (L)'s hypothesis: x=${x} p=${p} a=${S[t]} G=${G} j=${j} M=${Mold}`); } const M = Mold; if (j > Math.ceil(G / (p - 2))) A.failJ++; if (G > (j + 1) * M) A.fail1++; const s2 = G / ((G / (p - 2) + 2) * M); if (s2 > 1 + 1e-12) A.fail2++; if (s2 > A.worst2) A.worst2 = s2; if (G > (8 / 3) * M) A.fail3++; if (G >= p - 2) A.failLen++; if (G / ((j + 1) * M) > A.worst1) A.worst1 = G / ((j + 1) * M); if (G > 4096) A.big4096++; } } } if (!doneB) { const next = S[t + 2] - S[t + 1]; if (Math.max(Mold, next) >= p - 2) { doneB = true; r.Bp.Yend = S[t]; } else { const Bq = r.Bp; Bq.cells++; if (Mnew > ms2) { Bq.viol++; console.log(` VIOLATION (L') x=${x} p=${p} Y in (${S[t]}, ${S[t + 1]}]: ${Mnew} > ${ms2}`); } if (G >= 0) { if (j > Bq.maxJ) Bq.maxJ = j; if (j >= 2) Bq.j2++; if (G > 4096) Bq.big4096++; } } } if (doneA && doneB) break; } if (!(doneA && doneB)) { if (!final) return null; if (!doneA) { r.A.capped = true; r.A.Yend = S[t]; } if (!doneB) { r.Bp.capped = true; r.Bp.Yend = S[t]; } stopA = doneA ? stopA : t; } // the proof's steps at the largest admissible Y: M = M(T_x, Y_end) const M = r.A.Mend; for (let u = 0; u < stopA; u++) { if (K[u]) continue; const nx = NS[u + 1]; if (nx < 0) break; const G = S[nx] - S[u], j = nx - u - 1; if (G > (j + 1) * M) r.A.fail1End++; if (G > (G / (p - 2) + 2) * M * (1 + 1e-12)) r.A.fail2End++; } return r; } function evaluate(x, capB) { const p = nextPrime(x); let B = Math.min(capB, Math.max(1 << 20, 8 * p * p)); for (;;) { const { S, n } = extract(B); const res = scan(S, n, x, p, B >= capB); if (res) return res; B = Math.min(capB, B * 2); } } // ---- section S: strict vs buffered maxsum ---- const S_X = new Set([101, 307, 997, 3001]); // small windows const S_Y = [1e3, 3e3, 1e4, 3e4, 1e5, 3e5, 1e6, 1e7]; const S_XB = new Set([2153, 3001, 6803, 16001]); // the windows section 8 names const S_YB = [1e7, 1e8, 1e9]; const S_M = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]; const sRows = [], sTot = { cells: 0, acDiff: 0, cEmpty: 0, abDiff: 0, bEmpty: 0, m2diff: 0, bigCells: 0, bigAcDiff: 0, bigAbDiff: 0 }; function sectionS(x) { const Ys = [...(S_X.has(x) ? S_Y : []), ...(S_XB.has(x) ? S_YB : [])].filter((v, i, arr) => arr.indexOf(v) === i); const { S, n } = extract(Math.min(YMAX, Math.max(...Ys) + 2 ** 21)); for (const Y of Ys) { const big = S_XB.has(x) && S_YB.includes(Y); let iY = 0; while (iY < n && S[iY] < Y) iY++; let iC = iY; while (iC < n && S[iC] <= Y + 4096) iC++; const diffs = []; for (const m of S_M) { if (iY - 1 + m >= n) continue; let va = 0, vb = 0, vc = 0; for (let i = 0; i < iY; i++) { const v = S[i + m] - S[i]; if (v > va) va = v; if (i + m < iY && v > vb) vb = v; if (i + m < iC && v > vc) vc = v; } sTot.cells++; if (big) sTot.bigCells++; if (vc === 0) sTot.cEmpty++; else if (va !== vc) { sTot.acDiff++; if (big) sTot.bigAcDiff++; } if (vb === 0) sTot.bEmpty++; else if (va !== vb) { sTot.abDiff++; if (big) sTot.bigAbDiff++; } if (m === 2 && ((vc > 0 && va !== vc) || (vb > 0 && va !== vb))) sTot.m2diff++; if (va !== vc || va !== vb) diffs.push(`m=${m}: a=${va} b=${vb || '-'} c=${vc || '-'}${vb ? ` a/b=${(va / vb).toFixed(4)}` : ''}${vc ? ` a/c=${(va / vc).toFixed(4)}` : ''}`); } sRows.push(` x=${x} Y=${Y.toExponential(0)} slots below Y ${iY}: ${diffs.length ? diffs.join('; ') : 'a = b = c for every m'}`); } } // ---- main pass ---- const dense = PR.filter(x => x >= 3 && x <= XDENSE); const upper = PR.filter(x => x > XDENSE && x <= XTOP); const checks = new Set(); for (let i = 0; i < NCHECK; i++) { const target = XDENSE * Math.pow(XTOP / XDENSE, (i + 1) / NCHECK); let best = upper[0]; for (const q of upper) if (Math.abs(q - target) < Math.abs(best - target)) best = q; checks.add(best); } for (const x of [13933, 16001]) if (x <= XTOP && PR.includes(x)) checks.add(x); const evalSet = new Set([...dense, ...checks]); console.log(`lemma-boundary: YMAX=${YMAX}, dense x = 3..${XDENSE} (${dense.length} primes, slots to ${DENSE_CAP}), checkpoints ${[...checks].sort((a, b) => a - b).join(',')} (slots to ${YMAX})`); const rows = [], TOT = { fusedA: 0, xFused: 0, x: 0, cellsA: 0, violA: 0, j2A: 0, newGapsA: 0, failJ: 0, fail1: 0, fail2: 0, fail3: 0, failLen: 0, fail1End: 0, fail2End: 0, cellsB: 0, violB: 0, j2B: 0, closeKills: 0, kills: 0, big4096A: 0, big4096B: 0 }; const worst = { ratioA: { v: 0 }, worst2: { v: 0 }, worst1: { v: 0 }, maxJB: { v: 0 }, killSlack: { v: Infinity } }; let fromX = 3; for (const x of PR) { if (x > XTOP) break; strike(x); if (S_X.has(x) || S_XB.has(x)) sectionS(x); if (!evalSet.has(x)) continue; const r = evaluate(x, x <= XDENSE ? DENSE_CAP : YMAX); TOT.x++; const A = r.A, Bq = r.Bp; TOT.fusedA += A.fused; if (A.fused) TOT.xFused++; TOT.cellsA += A.cells; TOT.violA += A.viol; TOT.j2A += A.j2; TOT.newGapsA += A.newGaps; TOT.failJ += A.failJ; TOT.fail1 += A.fail1; TOT.fail2 += A.fail2; TOT.fail3 += A.fail3; TOT.failLen += A.failLen; TOT.fail1End += A.fail1End; TOT.fail2End += A.fail2End; TOT.big4096A += A.big4096; TOT.big4096B += Bq.big4096; TOT.cellsB += Bq.cells; TOT.violB += Bq.viol; TOT.j2B += Bq.j2; TOT.closeKills += r.closeKills; TOT.kills += r.kills; if (A.maxRatio > worst.ratioA.v) worst.ratioA = { v: A.maxRatio, x }; if (A.worst2 > worst.worst2.v) worst.worst2 = { v: A.worst2, x }; if (A.worst1 > worst.worst1.v) worst.worst1 = { v: A.worst1, x }; if (Bq.maxJ > worst.maxJB.v) worst.maxJB = { v: Bq.maxJ, x }; if (r.minKill - (r.p - 2) < worst.killSlack.v) worst.killSlack = { v: r.minKill - (r.p - 2), x, minKill: r.minKill, p: r.p }; const notable = A.viol || A.j2 || Bq.viol || Bq.j2 || r.closeKills; if (notable || x <= 7 || checks.has(x) || dense.indexOf(x) % 60 === 0 || (A.cells > 0 && fromX === 3)) { if (A.cells > 0 && fromX === 3) fromX = x; rows.push(`${String(x).padEnd(6)}${String(r.p).padEnd(6)}${(A.cells ? `(.., ${A.Yend}]${A.capped ? '+' : ''}` : 'empty').padEnd(22)}${String(A.cells).padEnd(9)}${String(A.viol).padEnd(5)}` + `${A.maxRatio.toFixed(4).padEnd(8)}${String(A.maxJ).padEnd(4)}${String(A.j2).padEnd(4)}${`${A.fail1}/${A.fail2}/${A.fail3}/${A.failLen}`.padEnd(16)}${`${A.fail1End}/${A.fail2End}`.padEnd(8)}` + `${(Bq.cells ? `${Bq.Yend}${Bq.capped ? '+' : ''}` : 'empty').padEnd(13)}${String(Bq.viol).padEnd(5)}${String(Bq.maxJ).padEnd(4)}${String(r.minKill === Infinity ? '-' : r.minKill).padEnd(7)}${String(r.closeKills)}`); } if (checks.has(x)) console.error(`[${el()}s] x=${x} done`); } console.log(`first x with a nonempty (L) hypothesis region: ${fromX}`); console.log('columns: x p | (L): Y range where M(T_x,Y) <= (p-2)/4 (+ = still holding at the scan cap), Y-cells, violations, max M(T_p,Y)/maxsum_2, max kills j, j>=2 |'); console.log(' proof steps at Y = a+1: fails of G<=(j+1)M / G<=(G/(p-2)+2)M / G<=(8/3)M / G= 2: ${TOT.j2A}; max M(T_p,Y)/maxsum_2 ${worst.ratioA.v.toFixed(6)} at x=${worst.ratioA.x}`); console.log(` proof steps at Y = a+1: j > ceil(G/(p-2)) ${TOT.failJ}; G > (j+1)M ${TOT.fail1} (largest G/((j+1)M) ${worst.worst1.v.toFixed(6)} at x=${worst.worst1.x}); ` + `G > (G/(p-2)+2)M ${TOT.fail2} (largest ratio ${worst.worst2.v.toFixed(6)} at x=${worst.worst2.x}); G > (8/3)M ${TOT.fail3}; G >= p-2 ${TOT.failLen}`); console.log(` new gaps inside (L) that fuse old gaps (j >= 1): ${TOT.fusedA}, at ${TOT.xFused} of the evaluated x`); console.log(` proof steps at Y = Y_end: G > (j+1)M ${TOT.fail1End}; G > (G/(p-2)+2)M ${TOT.fail2End}; new gaps > 4096 inside (L) ${TOT.big4096A}`); console.log(`(L') Y-cells ${TOT.cellsB}, violations ${TOT.violB}, new gaps with j >= 2 ${TOT.j2B}, max j ${worst.maxJB.v}; new gaps > 4096 inside (L') ${TOT.big4096B}`); console.log(`Fact B: kills scanned ${TOT.kills}, consecutive kills closer than p-2: ${TOT.closeKills}; smallest (distance - (p-2)) ${worst.killSlack.v} at x=${worst.killSlack.x} (p=${worst.killSlack.p}, distance ${worst.killSlack.minKill})`); console.log(`Section S: maxsum_m under (a) start < Y, uncapped; (b) whole window < Y; (c) slot list cut at Y+4096. m in {${S_M.join(',')}}`); console.log(` small windows: x in {${[...S_X].join(',')}}, Y in {${S_Y.join(',')}}; section 8 windows: x in {${[...S_XB].join(',')}}, Y in {${S_YB.join(',')}}`); for (const row of sRows) console.log(row); console.log(` cells ${sTot.cells}; (a) != (c) with (c) defined ${sTot.acDiff}; (c) empty ${sTot.cEmpty}; (a) != (b) with (b) defined ${sTot.abDiff}; (b) empty ${sTot.bEmpty}`); console.log(` at Y in {1e7,1e8,1e9}: cells ${sTot.bigCells}, (a) != (c) ${sTot.bigAcDiff}, (a) != (b) ${sTot.bigAbDiff}; cells with m = 2 where any rule differs: ${sTot.m2diff}`); console.error(`elapsed ${el()} s`);