FA-15751 / Numerics / Open access

Walsh hadamard transform: sum wing · case 01

The exact walsh hadamard transform result violates the stated contract at sum wing.

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

ROOT CAUSE

The sum wing step uses u-v instead of u+v.

VERIFIED REPAIR

Use u+v at the sum wing step.

Unsuccessful approach: The partial repair u still violates the sum wing invariant.

Case contract

Input integer list of power-of-two length; return unnormalized Sylvester-ordered Walsh-Hadamard transform. Bounds: length<=1024.

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=x[:];n=len(a);h=1
    for _ in range(10):
     if h>=n:break
     for i in range(0,n,2*h):
      for j in range(i,i+h):
       if j+h>=n:return None
       u,v=a[j],a[j+h]
       a[j]=u-v
       a[j+h]=u-v
     h=h*2
    return a
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-4, 3], [-1, -7]), ([2, 3], [5, -1]), ([3, 3], [6, 0]), ([-5, 4], [-1, -9]), ([3, -3], [0, 6]), ([-1, -1], [-2, 0])], [([-4, 3], [-1, -7]), ([3, 3], [6, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-3, -3], [-6, 0]), ([-4, 0], [-4, -4]), ([-2, 5], [3, -7]), ([3, 1], [4, 2])], [([2, 3], [5, -1]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-5, 3], [-2, -8]), ([-2, 4], [2, -6]), ([3, 2], [5, 1]), ([-1, 5], [4, -6])], [([3, 3], [6, 0]), ([2, 2], [4, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([4, 4, 3, 4], [15, -1, 1, 1]), ([1, -2, -5, 5], [-1, -7, -1, 13]), ([1, 2, 1, -4], [0, 4, 6, -6]), ([2, -2, -2, -1], [-3, 3, 3, 5])], [([-5, 4], [-1, -9]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([2, -2, -2, 4], [2, -2, -2, 10]), ([5, -2, 5, 4], [12, 8, -6, 6]), ([5, -1, -5, 3], [2, -2, 6, 14]), ([-2, -5, 1, -3], [-9, 7, -5, -1])]]
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	`[-3, -3]`	`[-7, -3]`	Failed
explicit oracle 1	`[13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13]`	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	Failed
explicit oracle 2	`[-7, -7]`	`[-1, -7]`	Failed
explicit oracle 3	`[-1, -1]`	`[5, -1]`	Failed
explicit oracle 4	`[0, 0]`	`[6, 0]`	Failed
explicit oracle 5	`[-9, -9]`	`[-1, -9]`	Failed
explicit oracle 6	`[6, 6]`	`[0, 6]`	Failed
explicit oracle 7	`[0, 0]`	`[-2, 0]`	Failed

SHA-256 / 8f052666cd09eea4dec31ff64ec1c58c5e8843e52bc7ca5f4c310232277f124a

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=x[:];n=len(a);h=1
    for _ in range(10):
     if h>=n:break
     for i in range(0,n,2*h):
      for j in range(i,i+h):
       if j+h>=n:return None
       u,v=a[j],a[j+h]
       a[j]=u
       a[j+h]=u-v
     h=h*2
    return a
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-4, 3], [-1, -7]), ([2, 3], [5, -1]), ([3, 3], [6, 0]), ([-5, 4], [-1, -9]), ([3, -3], [0, 6]), ([-1, -1], [-2, 0])], [([-4, 3], [-1, -7]), ([3, 3], [6, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-3, -3], [-6, 0]), ([-4, 0], [-4, -4]), ([-2, 5], [3, -7]), ([3, 1], [4, 2])], [([2, 3], [5, -1]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-5, 3], [-2, -8]), ([-2, 4], [2, -6]), ([3, 2], [5, 1]), ([-1, 5], [4, -6])], [([3, 3], [6, 0]), ([2, 2], [4, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([4, 4, 3, 4], [15, -1, 1, 1]), ([1, -2, -5, 5], [-1, -7, -1, 13]), ([1, 2, 1, -4], [0, 4, 6, -6]), ([2, -2, -2, -1], [-3, 3, 3, 5])], [([-5, 4], [-1, -9]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([2, -2, -2, 4], [2, -2, -2, 10]), ([5, -2, 5, 4], [12, 8, -6, 6]), ([5, -1, -5, 3], [2, -2, 6, 14]), ([-2, -5, 1, -3], [-9, 7, -5, -1])]]
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	`[-5, -3]`	`[-7, -3]`	Failed
explicit oracle 1	`[-2, 2, 3, 8, -4, 3, 0, 13, -1, 7, 3, 9, 2, 11, 3, 13]`	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	Failed
explicit oracle 2	`[-4, -7]`	`[-1, -7]`	Failed
explicit oracle 3	`[2, -1]`	`[5, -1]`	Failed
explicit oracle 4	`[3, 0]`	`[6, 0]`	Failed
explicit oracle 5	`[-5, -9]`	`[-1, -9]`	Failed
explicit oracle 6	`[3, 6]`	`[0, 6]`	Failed
explicit oracle 7	`[-1, 0]`	`[-2, 0]`	Failed

SHA-256 / 35e807ee0103ad65a33005e87c3874454780163147471b2536a805adb93d9886

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=x[:];n=len(a);h=1
    for _ in range(10):
     if h>=n:break
     for i in range(0,n,2*h):
      for j in range(i,i+h):
       if j+h>=n:return None
       u,v=a[j],a[j+h]
       a[j]=u+v
       a[j+h]=u-v
     h=h*2
    return a
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-4, 3], [-1, -7]), ([2, 3], [5, -1]), ([3, 3], [6, 0]), ([-5, 4], [-1, -9]), ([3, -3], [0, 6]), ([-1, -1], [-2, 0])], [([-4, 3], [-1, -7]), ([3, 3], [6, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-3, -3], [-6, 0]), ([-4, 0], [-4, -4]), ([-2, 5], [3, -7]), ([3, 1], [4, 2])], [([2, 3], [5, -1]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([-5, 3], [-2, -8]), ([-2, 4], [2, -6]), ([3, 2], [5, 1]), ([-1, 5], [4, -6])], [([3, 3], [6, 0]), ([2, 2], [4, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([4, 4, 3, 4], [15, -1, 1, 1]), ([1, -2, -5, 5], [-1, -7, -1, 13]), ([1, 2, 1, -4], [0, 4, 6, -6]), ([2, -2, -2, -1], [-3, 3, 3, 5])], [([-5, 4], [-1, -9]), ([-1, -1], [-2, 0]), ([-5, -2], [-7, -3]), ([-2, -4, -5, 1, 2, 3, -1, -5, -1, 4, -1, 3, 5, 2, 2, -2], [1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]), ([2, -2, -2, 4], [2, -2, -2, 10]), ([5, -2, 5, 4], [12, 8, -6, 6]), ([5, -1, -5, 3], [2, -2, 6, 14]), ([-2, -5, 1, -3], [-9, 7, -5, -1])]]
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	`[-7, -3]`	`[-7, -3]`	Passed
explicit oracle 1	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	Passed
explicit oracle 2	`[-1, -7]`	`[-1, -7]`	Passed
explicit oracle 3	`[5, -1]`	`[5, -1]`	Passed
explicit oracle 4	`[6, 0]`	`[6, 0]`	Passed
explicit oracle 5	`[-1, -9]`	`[-1, -9]`	Passed
explicit oracle 6	`[0, 6]`	`[0, 6]`	Passed
explicit oracle 7	`[-2, 0]`	`[-2, 0]`	Passed

SHA-256 / 7b85019de41602c8639006b42f19849c3aa2bdbfde799a27b0e91ea25f04bb8c

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

Case digest / 9b729b9c064a9029211e53142b357d501ecf295a13ec8fd76ccf21c8b3c67f38