FA-15506 / Numerics / Open access

Hensel simple root lift: root digit extension · case 01

The exact hensel simple root lift result violates the stated contract at root digit extension.

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

ROOT CAUSE

The root digit extension step uses r+correction instead of r+mod*correction.

VERIFIED REPAIR

Use r+mod*correction at the root digit extension step.

Unsuccessful approach: The partial repair r-mod*correction still violates the root digit extension invariant.

Case contract

Input [coefficients,p,r,k], p prime, r root mod p with nonzero derivative, k>=1; return unique root mod p^k congruent r mod p.

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,r,k=x
    mod=p;r%=p
    for _ in range(1,k):
     value=sum(c*r**i for i,c in enumerate(coeff))
     derivative=sum(i*coeff[i]*r**(i-1) for i in range(1,len(coeff)))
     if derivative%p==0:return None
     correction=(-(value//mod)*pow(derivative,-1,p))%p
     r=r+correction
     mod=mod*p
     r%=mod
    return [r,mod]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[1, 1, 1], 7, 2, 2], [30, 49]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 4, 1], [4, 7]), ([[1, 1, 1], 7, 4, 2], [18, 49])], [([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 13, 9, 3], [1036, 2197]), ([[1, 1, 1], 13, 9, 4], [7627, 28561]), ([[1, 1, 1], 13, 9, 5], [150432, 371293]), ([[-2, 0, 1], 7, 3, 1], [3, 7])], [([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 7, 4, 4], [1047, 2401]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-1, 1, 1], 11, 3, 5], [77234, 161051]), ([[-1, 1, 1], 11, 7, 1], [7, 11]), ([[-1, 1, 1], 11, 7, 2], [84, 121]), ([[-1, 1, 1], 11, 7, 3], [1294, 1331])], [([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 13, 3, 3], [1160, 2197]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 7, 1, 2], [1, 49]), ([[-3, 1, 2], 7, 1, 3], [1, 343]), ([[-3, 1, 2], 7, 1, 4], [1, 2401]), ([[-3, 1, 2], 7, 1, 5], [1, 16807])], [([[1, 1, 1], 7, 4, 2], [18, 49]), ([[1, 1, 1], 13, 9, 2], [22, 169]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 11, 4, 4], [7319, 14641]), ([[-3, 1, 2], 11, 4, 5], [80524, 161051]), ([[-3, 1, 2], 13, 1, 1], [1, 13]), ([[-3, 1, 2], 13, 1, 2], [1, 169])]]
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	`[6, 49]`	`[30, 49]`	Failed
explicit oracle 1	`[2, 7]`	`[2, 7]`	Passed
explicit oracle 2	`[27, 371293]`	`[371292, 371293]`	Failed
explicit oracle 3	`[6, 343]`	`[324, 343]`	Failed
explicit oracle 4	`[6, 2401]`	`[1353, 2401]`	Failed
explicit oracle 5	`[6, 16807]`	`[1353, 16807]`	Failed
explicit oracle 6	`[4, 7]`	`[4, 7]`	Passed
explicit oracle 7	`[6, 49]`	`[18, 49]`	Failed

SHA-256 / 6cf6ea32c8c5f245abe535cdc530b1e532b83ae2922d7d29937ff29a42e9d38e

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,r,k=x
    mod=p;r%=p
    for _ in range(1,k):
     value=sum(c*r**i for i,c in enumerate(coeff))
     derivative=sum(i*coeff[i]*r**(i-1) for i in range(1,len(coeff)))
     if derivative%p==0:return None
     correction=(-(value//mod)*pow(derivative,-1,p))%p
     r=r-mod*correction
     mod=mod*p
     r%=mod
    return [r,mod]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[1, 1, 1], 7, 2, 2], [30, 49]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 4, 1], [4, 7]), ([[1, 1, 1], 7, 4, 2], [18, 49])], [([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 13, 9, 3], [1036, 2197]), ([[1, 1, 1], 13, 9, 4], [7627, 28561]), ([[1, 1, 1], 13, 9, 5], [150432, 371293]), ([[-2, 0, 1], 7, 3, 1], [3, 7])], [([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 7, 4, 4], [1047, 2401]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-1, 1, 1], 11, 3, 5], [77234, 161051]), ([[-1, 1, 1], 11, 7, 1], [7, 11]), ([[-1, 1, 1], 11, 7, 2], [84, 121]), ([[-1, 1, 1], 11, 7, 3], [1294, 1331])], [([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 13, 3, 3], [1160, 2197]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 7, 1, 2], [1, 49]), ([[-3, 1, 2], 7, 1, 3], [1, 343]), ([[-3, 1, 2], 7, 1, 4], [1, 2401]), ([[-3, 1, 2], 7, 1, 5], [1, 16807])], [([[1, 1, 1], 7, 4, 2], [18, 49]), ([[1, 1, 1], 13, 9, 2], [22, 169]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 11, 4, 4], [7319, 14641]), ([[-3, 1, 2], 11, 4, 5], [80524, 161051]), ([[-3, 1, 2], 13, 1, 1], [1, 13]), ([[-3, 1, 2], 13, 1, 2], [1, 169])]]
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	`[23, 49]`	`[30, 49]`	Failed
explicit oracle 1	`[2, 7]`	`[2, 7]`	Passed
explicit oracle 2	`[92975, 371293]`	`[371292, 371293]`	Failed
explicit oracle 3	`[268, 343]`	`[324, 343]`	Failed
explicit oracle 4	`[268, 2401]`	`[1353, 2401]`	Failed
explicit oracle 5	`[14674, 16807]`	`[1353, 16807]`	Failed
explicit oracle 6	`[4, 7]`	`[4, 7]`	Passed
explicit oracle 7	`[39, 49]`	`[18, 49]`	Failed

SHA-256 / c709565a5bfe902be86598cd72e9caa1cba175892dd346c0b1139412d183b9e2

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,r,k=x
    mod=p;r%=p
    for _ in range(1,k):
     value=sum(c*r**i for i,c in enumerate(coeff))
     derivative=sum(i*coeff[i]*r**(i-1) for i in range(1,len(coeff)))
     if derivative%p==0:return None
     correction=(-(value//mod)*pow(derivative,-1,p))%p
     r=r+mod*correction
     mod=mod*p
     r%=mod
    return [r,mod]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([[1, 1, 1], 7, 2, 2], [30, 49]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 4, 1], [4, 7]), ([[1, 1, 1], 7, 4, 2], [18, 49])], [([[1, 1, 1], 7, 2, 3], [324, 343]), ([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[1, 1, 1], 13, 9, 3], [1036, 2197]), ([[1, 1, 1], 13, 9, 4], [7627, 28561]), ([[1, 1, 1], 13, 9, 5], [150432, 371293]), ([[-2, 0, 1], 7, 3, 1], [3, 7])], [([[1, 1, 1], 7, 2, 4], [1353, 2401]), ([[1, 1, 1], 7, 4, 4], [1047, 2401]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-1, 1, 1], 11, 3, 5], [77234, 161051]), ([[-1, 1, 1], 11, 7, 1], [7, 11]), ([[-1, 1, 1], 11, 7, 2], [84, 121]), ([[-1, 1, 1], 11, 7, 3], [1294, 1331])], [([[1, 1, 1], 7, 2, 5], [1353, 16807]), ([[1, 1, 1], 13, 3, 3], [1160, 2197]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 7, 1, 2], [1, 49]), ([[-3, 1, 2], 7, 1, 3], [1, 343]), ([[-3, 1, 2], 7, 1, 4], [1, 2401]), ([[-3, 1, 2], 7, 1, 5], [1, 16807])], [([[1, 1, 1], 7, 4, 2], [18, 49]), ([[1, 1, 1], 13, 9, 2], [22, 169]), ([[1, 1, 1], 7, 2, 1], [2, 7]), ([[2, 3, 1], 13, 12, 5], [371292, 371293]), ([[-3, 1, 2], 11, 4, 4], [7319, 14641]), ([[-3, 1, 2], 11, 4, 5], [80524, 161051]), ([[-3, 1, 2], 13, 1, 1], [1, 13]), ([[-3, 1, 2], 13, 1, 2], [1, 169])]]
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	`[30, 49]`	`[30, 49]`	Passed
explicit oracle 1	`[2, 7]`	`[2, 7]`	Passed
explicit oracle 2	`[371292, 371293]`	`[371292, 371293]`	Passed
explicit oracle 3	`[324, 343]`	`[324, 343]`	Passed
explicit oracle 4	`[1353, 2401]`	`[1353, 2401]`	Passed
explicit oracle 5	`[1353, 16807]`	`[1353, 16807]`	Passed
explicit oracle 6	`[4, 7]`	`[4, 7]`	Passed
explicit oracle 7	`[18, 49]`	`[18, 49]`	Passed

SHA-256 / 3fc21f3570b1203e9f6ab5cb0666c2ee1205895ce635d31a4f7b2e4af2c99427

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

Case digest / 4d36dd24bcff3cccdd6dc651bb680b85467cf3c21b85ac0e4309a1150c3b7f35