FAILURE MAP
← Case archive

FA-15811 / Numerics / Open access

Singular hensel root tree: lifted polynomial congruence · case 01

The exact singular hensel root tree result violates the stated contract at lifted polynomial congruence.

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

ROOT CAUSE

The lifted polynomial congruence step uses sum(c*s**i for i,c in enumerate(coeff))%mod==0 instead of sum(c*s**i for i,c in enumerate(coeff))%nextmod==0.

VERIFIED REPAIR

Use sum(c*s**i for i,c in enumerate(coeff))%nextmod==0 at the lifted polynomial congruence step.

Unsuccessful approach: The partial repair sum(c*r**i for i,c in enumerate(coeff))%nextmod==0 still violates the lifted polynomial congruence invariant.

Case contract

Input [polynomial coefficients,p,k], p prime and k>=1; enumerate all roots modulo p^k, including singular roots.

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):
    coeff,p,k=x
    roots=[r for r in range(p) if sum(c*r**i for i,c in enumerate(coeff))%p==0];mod=p
    for _ in range(1,k):
     nextmod=mod*p
     out=[]
     for r in roots:
      for digit in range(p):
       s=r+digit*mod
       if sum(c*s**i for i,c in enumerate(coeff))%mod==0:out.append(s)
     roots=sorted(set(out));mod=nextmod
    return [roots,mod]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[0, 0, 1], 2, 3], [[0, 4], 8]), ([[-1, 0, 1], 3, 2], [[1, 8], 9]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[0, 0, 1], 2, 2], [[0, 2], 4]), ([[0, 0, 1], 2, 4], [[0, 4, 8, 12], 16]), ([[0, 0, 1], 3, 1], [[0], 3]), ([[0, 0, 1], 3, 2], [[0, 3, 6], 9])], [([[0, 0, 1], 3, 3], [[0, 9, 18], 27]), ([[-1, 0, 1], 5, 2], [[1, 24], 25]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[-1, 0, 1], 2, 2], [[1, 3], 4]), ([[-1, 0, 1], 2, 3], [[1, 3, 5, 7], 8]), ([[-1, 0, 1], 2, 4], [[1, 7, 9, 15], 16]), ([[-1, 0, 1], 3, 1], [[1, 2], 3])], [([[0, 0, 1], 5, 3], [[0, 25, 50, 75, 100], 125]), ([[-1, 0, 1], 7, 2], [[1, 48], 49]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[0, 2, 1], 2, 3], [[0, 2, 4, 6], 8]), ([[0, 2, 1], 2, 4], [[0, 6, 8, 14], 16]), ([[0, 2, 1], 3, 1], [[0, 1], 3]), ([[0, 2, 1], 3, 2], [[0, 7], 9])], [([[0, 0, 1], 7, 3], [[0, 49, 98, 147, 196, 245, 294], 343]), ([[0, 2, 1], 3, 2], [[0, 7], 9]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[-4, 0, 1], 2, 4], [[2, 6, 10, 14], 16]), ([[-4, 0, 1], 3, 1], [[1, 2], 3]), ([[-4, 0, 1], 3, 2], [[2, 7], 9]), ([[-4, 0, 1], 3, 3], [[2, 25], 27])], [([[-1, 0, 1], 2, 4], [[1, 7, 9, 15], 16]), ([[0, 2, 1], 5, 2], [[0, 23], 25]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[0, 0, 0, 1], 3, 1], [[0], 3]), ([[0, 0, 0, 1], 3, 2], [[0, 3, 6], 9]), ([[0, 0, 0, 1], 3, 3], [[0, 3, 6, 9, 12, 15, 18, 21, 24], 27]), ([[0, 0, 0, 1], 3, 4], [[0, 9, 18, 27, 36, 45, 54, 63, 72], 81])]]
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 fixtureActualExpectedOutcome
explicit oracle 0[[0, 2, 4, 6], 8][[0, 4], 8]Failed
explicit oracle 1[[1, 2, 4, 5, 7, 8], 9][[1, 8], 9]Failed
explicit oracle 2[[0], 2][[0], 2]Passed
explicit oracle 3[[1, 341, 344, 684, 687, 1027, 1030, 1370, 1373, 1713, 1716, 2056, 2059, 2399], 2401][[1, 2399], 2401]Failed
explicit oracle 4[[0, 2], 4][[0, 2], 4]Passed
explicit oracle 5[[0, 4, 8, 12], 16][[0, 4, 8, 12], 16]Passed
explicit oracle 6[[0], 3][[0], 3]Passed
explicit oracle 7[[0, 3, 6], 9][[0, 3, 6], 9]Passed

SHA-256 / 3e4c60a723ccc492271937b6bd5f230b0547153faf11febc01bcb15ce3ab4716

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):
    coeff,p,k=x
    roots=[r for r in range(p) if sum(c*r**i for i,c in enumerate(coeff))%p==0];mod=p
    for _ in range(1,k):
     nextmod=mod*p
     out=[]
     for r in roots:
      for digit in range(p):
       s=r+digit*mod
       if sum(c*r**i for i,c in enumerate(coeff))%nextmod==0:out.append(s)
     roots=sorted(set(out));mod=nextmod
    return [roots,mod]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[0, 0, 1], 2, 3], [[0, 4], 8]), ([[-1, 0, 1], 3, 2], [[1, 8], 9]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[0, 0, 1], 2, 2], [[0, 2], 4]), ([[0, 0, 1], 2, 4], [[0, 4, 8, 12], 16]), ([[0, 0, 1], 3, 1], [[0], 3]), ([[0, 0, 1], 3, 2], [[0, 3, 6], 9])], [([[0, 0, 1], 3, 3], [[0, 9, 18], 27]), ([[-1, 0, 1], 5, 2], [[1, 24], 25]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[-1, 0, 1], 2, 2], [[1, 3], 4]), ([[-1, 0, 1], 2, 3], [[1, 3, 5, 7], 8]), ([[-1, 0, 1], 2, 4], [[1, 7, 9, 15], 16]), ([[-1, 0, 1], 3, 1], [[1, 2], 3])], [([[0, 0, 1], 5, 3], [[0, 25, 50, 75, 100], 125]), ([[-1, 0, 1], 7, 2], [[1, 48], 49]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[0, 2, 1], 2, 3], [[0, 2, 4, 6], 8]), ([[0, 2, 1], 2, 4], [[0, 6, 8, 14], 16]), ([[0, 2, 1], 3, 1], [[0, 1], 3]), ([[0, 2, 1], 3, 2], [[0, 7], 9])], [([[0, 0, 1], 7, 3], [[0, 49, 98, 147, 196, 245, 294], 343]), ([[0, 2, 1], 3, 2], [[0, 7], 9]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[-4, 0, 1], 2, 4], [[2, 6, 10, 14], 16]), ([[-4, 0, 1], 3, 1], [[1, 2], 3]), ([[-4, 0, 1], 3, 2], [[2, 7], 9]), ([[-4, 0, 1], 3, 3], [[2, 25], 27])], [([[-1, 0, 1], 2, 4], [[1, 7, 9, 15], 16]), ([[0, 2, 1], 5, 2], [[0, 23], 25]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[0, 0, 0, 1], 3, 1], [[0], 3]), ([[0, 0, 0, 1], 3, 2], [[0, 3, 6], 9]), ([[0, 0, 0, 1], 3, 3], [[0, 3, 6, 9, 12, 15, 18, 21, 24], 27]), ([[0, 0, 0, 1], 3, 4], [[0, 9, 18, 27, 36, 45, 54, 63, 72], 81])]]
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 fixtureActualExpectedOutcome
explicit oracle 0[[0, 4], 8][[0, 4], 8]Passed
explicit oracle 1[[1, 4, 7], 9][[1, 8], 9]Failed
explicit oracle 2[[0], 2][[0], 2]Passed
explicit oracle 3[[1, 344, 687, 1030, 1373, 1716, 2059], 2401][[1, 2399], 2401]Failed
explicit oracle 4[[0, 2], 4][[0, 2], 4]Passed
explicit oracle 5[[0, 4, 8, 12], 16][[0, 4, 8, 12], 16]Passed
explicit oracle 6[[0], 3][[0], 3]Passed
explicit oracle 7[[0, 3, 6], 9][[0, 3, 6], 9]Passed

SHA-256 / 098cdf87519c3633cf93f5129ec124f3682eb20eec6d221150c9343557be8c29

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):
    coeff,p,k=x
    roots=[r for r in range(p) if sum(c*r**i for i,c in enumerate(coeff))%p==0];mod=p
    for _ in range(1,k):
     nextmod=mod*p
     out=[]
     for r in roots:
      for digit in range(p):
       s=r+digit*mod
       if sum(c*s**i for i,c in enumerate(coeff))%nextmod==0:out.append(s)
     roots=sorted(set(out));mod=nextmod
    return [roots,mod]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[0, 0, 1], 2, 3], [[0, 4], 8]), ([[-1, 0, 1], 3, 2], [[1, 8], 9]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[0, 0, 1], 2, 2], [[0, 2], 4]), ([[0, 0, 1], 2, 4], [[0, 4, 8, 12], 16]), ([[0, 0, 1], 3, 1], [[0], 3]), ([[0, 0, 1], 3, 2], [[0, 3, 6], 9])], [([[0, 0, 1], 3, 3], [[0, 9, 18], 27]), ([[-1, 0, 1], 5, 2], [[1, 24], 25]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[-1, 0, 1], 2, 2], [[1, 3], 4]), ([[-1, 0, 1], 2, 3], [[1, 3, 5, 7], 8]), ([[-1, 0, 1], 2, 4], [[1, 7, 9, 15], 16]), ([[-1, 0, 1], 3, 1], [[1, 2], 3])], [([[0, 0, 1], 5, 3], [[0, 25, 50, 75, 100], 125]), ([[-1, 0, 1], 7, 2], [[1, 48], 49]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[0, 2, 1], 2, 3], [[0, 2, 4, 6], 8]), ([[0, 2, 1], 2, 4], [[0, 6, 8, 14], 16]), ([[0, 2, 1], 3, 1], [[0, 1], 3]), ([[0, 2, 1], 3, 2], [[0, 7], 9])], [([[0, 0, 1], 7, 3], [[0, 49, 98, 147, 196, 245, 294], 343]), ([[0, 2, 1], 3, 2], [[0, 7], 9]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[-4, 0, 1], 2, 4], [[2, 6, 10, 14], 16]), ([[-4, 0, 1], 3, 1], [[1, 2], 3]), ([[-4, 0, 1], 3, 2], [[2, 7], 9]), ([[-4, 0, 1], 3, 3], [[2, 25], 27])], [([[-1, 0, 1], 2, 4], [[1, 7, 9, 15], 16]), ([[0, 2, 1], 5, 2], [[0, 23], 25]), ([[0, 0, 1], 2, 1], [[0], 2]), ([[-2, 1, 1], 7, 4], [[1, 2399], 2401]), ([[0, 0, 0, 1], 3, 1], [[0], 3]), ([[0, 0, 0, 1], 3, 2], [[0, 3, 6], 9]), ([[0, 0, 0, 1], 3, 3], [[0, 3, 6, 9, 12, 15, 18, 21, 24], 27]), ([[0, 0, 0, 1], 3, 4], [[0, 9, 18, 27, 36, 45, 54, 63, 72], 81])]]
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 fixtureActualExpectedOutcome
explicit oracle 0[[0, 4], 8][[0, 4], 8]Passed
explicit oracle 1[[1, 8], 9][[1, 8], 9]Passed
explicit oracle 2[[0], 2][[0], 2]Passed
explicit oracle 3[[1, 2399], 2401][[1, 2399], 2401]Passed
explicit oracle 4[[0, 2], 4][[0, 2], 4]Passed
explicit oracle 5[[0, 4, 8, 12], 16][[0, 4, 8, 12], 16]Passed
explicit oracle 6[[0], 3][[0], 3]Passed
explicit oracle 7[[0, 3, 6], 9][[0, 3, 6], 9]Passed

SHA-256 / ce3b93737c16846505da9bbbeef0130b571a975c7c6de47613c88b196a9dd595

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:30.446728+00:00.

Case digest / a6633c6f6de6f10a18738a681cef29c048da6ca867352253c8d1cdc092e19bb9