{"challengeId":"matmul-rank-4x4-complex","entry":"verifier.mjs","sha256":"11655d316a63a77e4a35f5d95c68deed14dbeefae1aab0766e498fb2977be36a","scoreDirection":"minimize","scoreLabel":"multiplications over Z[i]","seedPolicy":{"mode":"fixed","testCount":1},"source":"// Frozen verifier for matmul-rank-4x4-complex. Self-contained (no imports): it\n// interprets the candidate's bilinear-scheme artifact and returns a Verdict. It\n// never executes agent code — build() already ran in the sandbox and handed us\n// plain data. This file is part of the challenge's PROTECTED surface.\n//\n// Fixed instance: 4x4 matrix multiply, but the scheme coefficients live in the\n// GAUSSIAN INTEGERS Z[i] (each coefficient is an integer pair [re, im] with\n// i^2 = -1). A bilinear scheme of rank R computes\n//   m_r = (u_r . vecX) * (v_r . vecY)          for r in 0..R-1\n//   out_c = sum_r w_r[c] * m_r\n// where vecX = flatten(A) = [a00..a33], vecY = flatten(B) = [b00..b33], and the\n// 16 outputs are the entries of the 4x4 product C = A*B, flattened row-major.\n//\n// Correctness is an EXACT tensor identity. The bilinear map a scheme computes has\n// coefficient, on monomial X_a * Y_b in output c,\n//   S[a][b][c] = sum_r u_r[a] * v_r[b] * w_r[c]      (complex products in Z[i])\n// The 4x4 matmul tensor T[a][b][c] is the REAL integer 1 exactly on the 64\n// (a,b,c) triples with a=(i,k), b=(k,j), c=(i,j), and 0 otherwise. We recompute\n// all 16*16*16 = 4096 coefficients with exact integer Gaussian arithmetic and\n// require, for every triple, that the SUM has imaginary part === 0 AND real part\n// === T[a][b][c]. This is a total proof over the finitely many monomials —\n// nothing to sample — so seedPolicy.mode is \"fixed\".\n\nconst N = 4; // matrix order\nconst D = N * N; // 16 inputs per matrix, 16 outputs\nconst MAX_RANK = 64; // naive is 64; Strassen-style is 49; AlphaEvolve 2025 is 48\nconst COEFF_CAP = 1 << 20; // each re/im must be a modest integer; rejects abuse\n\nfunction gate(name, pass, detail) {\n  return { name, pass, detail };\n}\nfunction bad(name, detail) {\n  return { ok: false, score: null, gates: [gate(name, false, detail)], behavior: {}, logs: [] };\n}\n\n// The 4x4 matrix-multiplication tensor as a sparse map: key = a*256 + b*16 + c.\n// T is 1 exactly on (a,b,c) with a=(i,k), b=(k,j), c=(i,j); all entries are REAL.\nfunction targetTensorSet() {\n  const set = new Set();\n  for (let i = 0; i < N; i++) {\n    for (let j = 0; j < N; j++) {\n      const c = i * N + j; // output slot (row i, col j)\n      for (let k = 0; k < N; k++) {\n        const a = i * N + k; // x_{i,k}\n        const b = k * N + j; // y_{k,j}\n        set.add((a * D + b) * D + c);\n      }\n    }\n  }\n  return set;\n}\n\nfunction isGaussVec(vec) {\n  if (!Array.isArray(vec) || vec.length !== D) return false;\n  for (const pair of vec) {\n    if (!Array.isArray(pair) || pair.length !== 2) return false;\n    const re = pair[0];\n    const im = pair[1];\n    if (!Number.isInteger(re) || !Number.isInteger(im)) return false;\n    if (re > COEFF_CAP || re < -COEFF_CAP || im > COEFF_CAP || im < -COEFF_CAP) return false;\n  }\n  return true;\n}\n\nexport function verify(ctx) {\n  const sol = ctx.solution;\n  if (!sol || typeof sol !== 'object') {\n    return bad('structure', 'expected { rank, factors:[ {u,v,w} ] }');\n  }\n  const { rank, factors } = sol;\n  if (!Number.isInteger(rank) || rank < 1 || rank > MAX_RANK) {\n    return bad('structure', `rank must be an integer in 1..${MAX_RANK}`);\n  }\n  if (!Array.isArray(factors) || factors.length !== rank) {\n    return bad('structure', `factors must be an array of exactly rank=${rank} terms`);\n  }\n  for (let r = 0; r < rank; r++) {\n    const f = factors[r];\n    if (!f || typeof f !== 'object') return bad('structure', `factors[${r}] must be { u, v, w }`);\n    if (!isGaussVec(f.u)) return bad('structure', `factors[${r}].u must be ${D} integer pairs [re,im]`);\n    if (!isGaussVec(f.v)) return bad('structure', `factors[${r}].v must be ${D} integer pairs [re,im]`);\n    if (!isGaussVec(f.w)) return bad('structure', `factors[${r}].w must be ${D} integer pairs [re,im]`);\n  }\n\n  const T = targetTensorSet();\n\n  // Recompute the bilinear coefficient tensor S = sum_r u_r[a]*v_r[b]*w_r[c] for\n  // every (a,b,c). Exact Gaussian-integer (BigInt) arithmetic — no floats, no\n  // built-in transcendental ops. Require: imaginary part 0 everywhere, and real\n  // part equal to the {0,1} target tensor everywhere.\n  let mismatch = '';\n  for (let a = 0; a < D && !mismatch; a++) {\n    for (let b = 0; b < D && !mismatch; b++) {\n      for (let c = 0; c < D && !mismatch; c++) {\n        let sumRe = 0n;\n        let sumIm = 0n;\n        for (let r = 0; r < rank; r++) {\n          const u = factors[r].u[a];\n          const v = factors[r].v[b];\n          const w = factors[r].w[c];\n          // p = u * v  (complex multiply in Z[i])\n          const uRe = BigInt(u[0]);\n          const uIm = BigInt(u[1]);\n          const vRe = BigInt(v[0]);\n          const vIm = BigInt(v[1]);\n          const pRe = uRe * vRe - uIm * vIm;\n          const pIm = uRe * vIm + uIm * vRe;\n          // q = p * w\n          const wRe = BigInt(w[0]);\n          const wIm = BigInt(w[1]);\n          sumRe += pRe * wRe - pIm * wIm;\n          sumIm += pRe * wIm + pIm * wRe;\n        }\n        const want = T.has((a * D + b) * D + c) ? 1n : 0n;\n        if (sumIm !== 0n) {\n          mismatch = `monomial X${a}*Y${b} in output ${c}: imaginary part ${sumIm} != 0`;\n        } else if (sumRe !== want) {\n          mismatch = `monomial X${a}*Y${b} in output ${c}: real part ${sumRe}, want ${want}`;\n        }\n      }\n    }\n  }\n\n  const computesMatmul = !mismatch;\n  const gates = [\n    gate(\n      'computes-4x4-matmul-over-Zi',\n      computesMatmul,\n      mismatch || `all ${D * D * D} tensor coefficients match the 4x4 matmul map with zero imaginary part`,\n    ),\n  ];\n  const ok = gates.every((g) => g.pass);\n  return {\n    ok,\n    score: ok ? rank : null,\n    gates,\n    behavior: { rank },\n    logs: [`rank=${rank} Gaussian-integer terms over Z[i]`],\n  };\n}\n"}