python-r1cs-qap-coset-fft-vanishing-divisibility-exactness
Done. I built and verified the full solution from scratch; it's written to ~/SOLUTION.md (self-contained, with the complete qap.py and test_qap.py embedded).
GF(p), p = 15·2²⁷+1 = 2013265921 (2-adicity 27, generator 31). Measured float error on the example: 8.1e+36.(0)·(0)=0 rows.shift^j, and use the coset vanishing polynomial Z(x) = xⁿ − shiftⁿ, not xⁿ − 1. Using the wrong Z leaves remainder [1929514058, 209590658, 858722444] on an honest witness.GF(p), not point samples.0=0 at w=0, so bare divisibility accepts it. The standard guard is pinning the constant witness entry w[0]=1 (implemented in QAP.verify); an optional idempotence guard row w₀·w₀=w₀ is also available.python3 test_qap.py → ALL 11 TESTS PASSED, covering:
- NTT vs. naive evaluation, inverse roundtrip, coset eval/interpolation vs. independent Lagrange interpolation
- exact quotient coefficients H = [545393738, 1554782986, 760051338] with H·Z == T
- honest witness accepted, 4 near-miss witnesses rejected, zero witness rejected by the guard
- AST-level check that no float/math/numpy exists in the source
Key artifacts (shift=5, n=4):
Z(x) = [2013265296, 0, 0, 0, 1] # x^4 - 5^4
H(x) = [545393738, 1554782986, 760051338]
T(x) = A*B - C, remainder = [0]
Files: ~/qap.py, ~/test_qap.py, ~/SOLUTION.md.
# Evidence - Problem class: python-r1cs-qap-coset-fft-vanishing-divisibility-exactness - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-02T04:13:46.529Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Reduce a rank-1 constraint system to a quadratic arithmetic program: interpolate the A, B and C polynomials through an exact FFT over a coset of a smooth multiplicative subgroup, then verify a witness by checking that the target vanishing polynomial divides A(x)*B(x)-C(x) everywhere. Non-power-of-two constraint counts must be padded with rows that force the witness to stay nonzero, and all arithmetic must be exact modular field arithmetic with no floating point anywhere. Tests assert the exact quotient-polynomial coefficients, the coset evaluation vectors, and the divisibility verdict for one satisfying and one adversarially near-miss witness under python3.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-r1cs-qap-coset-fft-vanishing-divisibility-exactness", "provider": "openrouter", "solved_at": "2026-10-02T04:13:46.529Z", "version": "3.11"}