FA-15761 / Numerics / Open access

Walsh hadamard transform: butterfly span growth · case 01

The exact walsh hadamard transform result violates the stated contract at butterfly span growth.

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

ROOT CAUSE

The butterfly span growth step uses h+1 instead of h*2.

VERIFIED REPAIR

Use h*2 at the butterfly span growth step.

Unsuccessful approach: The partial repair h*4 still violates the butterfly span growth 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+1
    return a
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([2, -1, -2, 5], [4, -4, -2, 10]), ([-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])], [([4, 4, 3, 4], [15, -1, 1, 1]), ([1, 2, 1, -4], [0, 4, 6, -6]), ([-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])], [([1, -2, -5, 5], [-1, -7, -1, 13]), ([-3, -4, -3, -1], [-11, -1, -3, 3]), ([-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])], [([1, 2, 1, -4], [0, 4, 6, -6]), ([-5, -1, 0, 2], [-4, -6, -8, -2]), ([-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]), ([2, -2, -2, -1], [-3, 3, 3, 5]), ([0, 3, 2, -3], [2, 2, 4, -8])], [([2, -2, -2, -1], [-3, 3, 3, 5]), ([-2, 2, 5, 2], [7, -1, -7, -7]), ([-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	`None`	`[4, -4, -2, 10]`	Failed
explicit oracle 1	`[-7, -3]`	`[-7, -3]`	Passed
explicit oracle 2	`None`	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	Failed
explicit oracle 3	`[-1, -7]`	`[-1, -7]`	Passed
explicit oracle 4	`[5, -1]`	`[5, -1]`	Passed
explicit oracle 5	`[6, 0]`	`[6, 0]`	Passed
explicit oracle 6	`[-1, -9]`	`[-1, -9]`	Passed
explicit oracle 7	`[0, 6]`	`[0, 6]`	Passed

SHA-256 / 5ea6c17ea62eaf96c8a4d48a9fe395dd7913df816b995f4f36b63b313eae9517

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+v
       a[j+h]=u-v
     h=h*4
    return a
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([2, -1, -2, 5], [4, -4, -2, 10]), ([-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])], [([4, 4, 3, 4], [15, -1, 1, 1]), ([1, 2, 1, -4], [0, 4, 6, -6]), ([-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])], [([1, -2, -5, 5], [-1, -7, -1, 13]), ([-3, -4, -3, -1], [-11, -1, -3, 3]), ([-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])], [([1, 2, 1, -4], [0, 4, 6, -6]), ([-5, -1, 0, 2], [-4, -6, -8, -2]), ([-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]), ([2, -2, -2, -1], [-3, 3, 3, 5]), ([0, 3, 2, -3], [2, 2, 4, -8])], [([2, -2, -2, -1], [-3, 3, 3, 5]), ([-2, 2, 5, 2], [7, -1, -7, -7]), ([-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	`[1, 3, 3, -7]`	`[4, -4, -2, 10]`	Failed
explicit oracle 1	`[-7, -3]`	`[-7, -3]`	Passed
explicit oracle 2	`[-1, 1, -10, -2, -11, 3, 2, -10, 10, -2, 2, 0, -4, -8, 2, -8]`	`[1, -3, 17, 1, -11, -23, -19, 13, -23, 1, 1, 5, -7, 9, -7, 13]`	Failed
explicit oracle 3	`[-1, -7]`	`[-1, -7]`	Passed
explicit oracle 4	`[5, -1]`	`[5, -1]`	Passed
explicit oracle 5	`[6, 0]`	`[6, 0]`	Passed
explicit oracle 6	`[-1, -9]`	`[-1, -9]`	Passed
explicit oracle 7	`[0, 6]`	`[0, 6]`	Passed

SHA-256 / 3422b5bbea5a063149e419d0ee99b82d13b1751ea427694d4faa599cceabfb61

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 = [[([2, -1, -2, 5], [4, -4, -2, 10]), ([-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])], [([4, 4, 3, 4], [15, -1, 1, 1]), ([1, 2, 1, -4], [0, 4, 6, -6]), ([-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])], [([1, -2, -5, 5], [-1, -7, -1, 13]), ([-3, -4, -3, -1], [-11, -1, -3, 3]), ([-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])], [([1, 2, 1, -4], [0, 4, 6, -6]), ([-5, -1, 0, 2], [-4, -6, -8, -2]), ([-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]), ([2, -2, -2, -1], [-3, 3, 3, 5]), ([0, 3, 2, -3], [2, 2, 4, -8])], [([2, -2, -2, -1], [-3, 3, 3, 5]), ([-2, 2, 5, 2], [7, -1, -7, -7]), ([-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	`[4, -4, -2, 10]`	`[4, -4, -2, 10]`	Passed
explicit oracle 1	`[-7, -3]`	`[-7, -3]`	Passed
explicit oracle 2	`[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 3	`[-1, -7]`	`[-1, -7]`	Passed
explicit oracle 4	`[5, -1]`	`[5, -1]`	Passed
explicit oracle 5	`[6, 0]`	`[6, 0]`	Passed
explicit oracle 6	`[-1, -9]`	`[-1, -9]`	Passed
explicit oracle 7	`[0, 6]`	`[0, 6]`	Passed

SHA-256 / fba03ef841a26ef4cb9c31edec78e7f4e0bba9209cca234cb2644979c0b96632

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

Case digest / 225af955d5bc39097e8c01fcb73d5d2348d59f8f05e5293b3a9e802d57bebcf3