FA-14836 / Numerics / Open access

Polynomial squarefree characteristic p: unit gcd criterion · case 01

The exact polynomial squarefree characteristic p result violates the stated contract at unit gcd criterion.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The unit gcd criterion step uses bool(f) instead of len(f)==1.

VERIFIED REPAIR

Use len(f)==1 at the unit gcd criterion step.

Unsuccessful approach: The partial repair len(f)<=2 still violates the unit gcd criterion invariant.

Case contract

Input [coefficients,p] prime p; return whether nonconstant polynomial over Fp has gcd(f,fprime)=1; constants false. Bounds: degree at most three and prime p<=7.

Why this case matters

Exact discrete arithmetic with observable algorithmic state; no floating point approximation is used.

1 / The failure

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    a,p=x
    f=[v%p for v in a]
    while f and f[-1]==0:f.pop()
    if len(f)<2:return False
    g=[(i*f[i])%p for i in range(1,len(f))]
    while g and g[-1]==0:g.pop()
    for _ in range(20):
     if not g:break
     r=f[:]
     for _ in range(20):
      if len(r)<len(g):break
      if g[-1]%p==0:return None
      c=r[-1]*pow(g[-1],-1,p)%p
      k=len(r)-len(g)
      for j in range(len(g)):r[j+k]=(r[j+k]-c*g[j])%p
      while r and r[-1]==0:r.pop()
     f,g=g,r
    return bool(f)
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[0, 0, 1], 2], False), ([[0, 0, 1], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 2], 2], False), ([[1, 1], 2], True), ([[1, 2], 2], False), ([[2, 1], 2], True)], [([[0, 2, 1], 2], False), ([[1, 2, 1], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 2, 2], 2], False), ([[2, 0, 1], 2], False), ([[2, 0, 2], 2], False), ([[2, 1, 1], 2], True)], [([[1, 0, 1], 2], False), ([[0, 0, 1, 1], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 1, 2, 1], 2], False), ([[0, 1, 2, 2], 2], True), ([[0, 2, 0, 1], 2], False), ([[0, 2, 0, 2], 2], False)], [([[1, 2, 1], 2], False), ([[0, 0, 2, 2], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 1, 1, 2], 2], True), ([[1, 1, 2, 1], 2], True), ([[1, 1, 2, 2], 2], True), ([[1, 2, 0, 1], 2], True)], [([[2, 0, 1], 2], False), ([[0, 2, 1, 2], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[2, 1, 1, 1], 2], True), ([[2, 1, 1, 2], 2], True), ([[2, 1, 2, 1], 2], False), ([[2, 1, 2, 2], 2], True)]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
explicit oracle 0	`True`	`False`	Failed
explicit oracle 1	`True`	`False`	Failed
explicit oracle 2	`True`	`True`	Passed
explicit oracle 3	`True`	`True`	Passed
explicit oracle 4	`False`	`False`	Passed
explicit oracle 5	`True`	`True`	Passed
explicit oracle 6	`False`	`False`	Passed
explicit oracle 7	`True`	`True`	Passed

SHA-256 / 74f3dfca93285d258c22c7921a89c9d2d062b6724cad6e38f10492950d4662b4

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    a,p=x
    f=[v%p for v in a]
    while f and f[-1]==0:f.pop()
    if len(f)<2:return False
    g=[(i*f[i])%p for i in range(1,len(f))]
    while g and g[-1]==0:g.pop()
    for _ in range(20):
     if not g:break
     r=f[:]
     for _ in range(20):
      if len(r)<len(g):break
      if g[-1]%p==0:return None
      c=r[-1]*pow(g[-1],-1,p)%p
      k=len(r)-len(g)
      for j in range(len(g)):r[j+k]=(r[j+k]-c*g[j])%p
      while r and r[-1]==0:r.pop()
     f,g=g,r
    return len(f)<=2
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[0, 0, 1], 2], False), ([[0, 0, 1], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 2], 2], False), ([[1, 1], 2], True), ([[1, 2], 2], False), ([[2, 1], 2], True)], [([[0, 2, 1], 2], False), ([[1, 2, 1], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 2, 2], 2], False), ([[2, 0, 1], 2], False), ([[2, 0, 2], 2], False), ([[2, 1, 1], 2], True)], [([[1, 0, 1], 2], False), ([[0, 0, 1, 1], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 1, 2, 1], 2], False), ([[0, 1, 2, 2], 2], True), ([[0, 2, 0, 1], 2], False), ([[0, 2, 0, 2], 2], False)], [([[1, 2, 1], 2], False), ([[0, 0, 2, 2], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 1, 1, 2], 2], True), ([[1, 1, 2, 1], 2], True), ([[1, 1, 2, 2], 2], True), ([[1, 2, 0, 1], 2], True)], [([[2, 0, 1], 2], False), ([[0, 2, 1, 2], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[2, 1, 1, 1], 2], True), ([[2, 1, 1, 2], 2], True), ([[2, 1, 2, 1], 2], False), ([[2, 1, 2, 2], 2], True)]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
explicit oracle 0	`False`	`False`	Passed
explicit oracle 1	`True`	`False`	Failed
explicit oracle 2	`True`	`True`	Passed
explicit oracle 3	`True`	`True`	Passed
explicit oracle 4	`False`	`False`	Passed
explicit oracle 5	`True`	`True`	Passed
explicit oracle 6	`False`	`False`	Passed
explicit oracle 7	`True`	`True`	Passed

SHA-256 / 72dcf898ab76465c902bd8049b0803d07791815347258cc92d4e5c86b1fc29d3

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    a,p=x
    f=[v%p for v in a]
    while f and f[-1]==0:f.pop()
    if len(f)<2:return False
    g=[(i*f[i])%p for i in range(1,len(f))]
    while g and g[-1]==0:g.pop()
    for _ in range(20):
     if not g:break
     r=f[:]
     for _ in range(20):
      if len(r)<len(g):break
      if g[-1]%p==0:return None
      c=r[-1]*pow(g[-1],-1,p)%p
      k=len(r)-len(g)
      for j in range(len(g)):r[j+k]=(r[j+k]-c*g[j])%p
      while r and r[-1]==0:r.pop()
     f,g=g,r
    return len(f)==1
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[0, 0, 1], 2], False), ([[0, 0, 1], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 2], 2], False), ([[1, 1], 2], True), ([[1, 2], 2], False), ([[2, 1], 2], True)], [([[0, 2, 1], 2], False), ([[1, 2, 1], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 2, 2], 2], False), ([[2, 0, 1], 2], False), ([[2, 0, 2], 2], False), ([[2, 1, 1], 2], True)], [([[1, 0, 1], 2], False), ([[0, 0, 1, 1], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[0, 1, 2, 1], 2], False), ([[0, 1, 2, 2], 2], True), ([[0, 2, 0, 1], 2], False), ([[0, 2, 0, 2], 2], False)], [([[1, 2, 1], 2], False), ([[0, 0, 2, 2], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[1, 1, 1, 2], 2], True), ([[1, 1, 2, 1], 2], True), ([[1, 1, 2, 2], 2], True), ([[1, 2, 0, 1], 2], True)], [([[2, 0, 1], 2], False), ([[0, 2, 1, 2], 3], False), ([[0, 1], 2], True), ([[2, 2, 2, 2], 7], True), ([[2, 1, 1, 1], 2], True), ([[2, 1, 1, 2], 2], True), ([[2, 1, 2, 1], 2], False), ([[2, 1, 2, 2], 2], True)]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)

Boundary fixture	Actual	Expected	Outcome
explicit oracle 0	`False`	`False`	Passed
explicit oracle 1	`False`	`False`	Passed
explicit oracle 2	`True`	`True`	Passed
explicit oracle 3	`True`	`True`	Passed
explicit oracle 4	`False`	`False`	Passed
explicit oracle 5	`True`	`True`	Passed
explicit oracle 6	`False`	`False`	Passed
explicit oracle 7	`True`	`True`	Passed

SHA-256 / d2f0cee60803ccf181d82bc61dc8a9059767d13c3816a0d5050bc5b9de147cfc

Verification & scope

A deterministic bounded teaching model. Inputs are restricted to the explicit contract; this is not a production algebra library. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:39:20.696077+00:00.

Case digest / 5fef82c350a92dcf46d702154d4ec7daab3b053c1f0bffb76b47bb8a3ac833c9