verify_196_orbit.py

#!/usr/bin/env python3
"""Independent digit-list replay of the checked 196-orbit certificate."""

from __future__ import annotations

import argparse
import hashlib
import json
import math
from collections import Counter
from pathlib import Path


def add_digit_lists(left: list[int], right: list[int]) -> list[int]:
    width = max(len(left), len(right))
    out: list[int] = []
    carry = 0
    for index in range(width):
        total = carry
        if index < len(left):
            total += left[index]
        if index < len(right):
            total += right[index]
        out.append(total % 10)
        carry = total // 10
    if carry:
        out.append(carry)
    while len(out) > 1 and out[-1] == 0:
        out.pop()
    return out


def next_state(digits_lsd_first: list[int]) -> list[int]:
    return add_digit_lists(digits_lsd_first, list(reversed(digits_lsd_first)))


def as_text(digits_lsd_first: list[int]) -> str:
    return "".join(str(digit) for digit in reversed(digits_lsd_first))


def carry_ins(text: str) -> list[int]:
    digits = [ord(char) - 48 for char in reversed(text)]
    result: list[int] = []
    carry = 0
    for index in range(len(digits)):
        result.append(carry)
        carry = (digits[index] + digits[-1 - index] + carry) // 10
    return result


def mi(counts: Counter[tuple[int, int]]) -> float:
    total = sum(counts.values())
    left = Counter()
    right = Counter()
    for pair, count in counts.items():
        left[pair[0]] += count
        right[pair[1]] += count
    return sum(
        count / total * math.log2(count * total / (left[a] * right[b]))
        for (a, b), count in counts.items()
    )


def subword_counts(rows: list[str], maximum: int) -> list[int]:
    answer = []
    for width in range(1, maximum + 1):
        seen = set()
        for row in rows:
            for start in range(0, len(row) - width + 1):
                seen.add(row[start : start + width])
        answer.append(len(seen))
    return answer


def independent_payload() -> dict[str, object]:
    digits = [6, 9, 1]
    states = []
    for _ in range(4_001):
        states.append(as_text(digits))
        digits = next_state(digits)

    digest = hashlib.sha256()
    for step, state in enumerate(states):
        digest.update(f"{step}:{state}\n".encode())

    rows = states[1:4_001]
    distances = []
    for step, row in enumerate(rows, start=1):
        distance = sum(row[index] != row[-1 - index] for index in range(len(row)))
        distances.append((step, len(row), distance))
    minimum = min(distance for _, _, distance in distances)
    ratio_row = min(distances, key=lambda item: item[2] / item[1])
    long = [distance / length for _, length, distance in distances if length > 100]

    grouped = {False: Counter(), True: Counter()}
    group_sizes = Counter()
    for step in range(1, 3_001):
        row = states[step]
        growth = len(row) > len(states[step - 1])
        group_sizes[growth] += 1
        for shift in range(-2, 3):
            pairs = [
                (index, len(row) - 1 - index + shift)
                for index in range(len(row))
                if 0 <= len(row) - 1 - index + shift < len(row)
            ]
            grouped[growth][shift] += sum(row[a] != row[b] for a, b in pairs) / len(pairs)

    raw = states[:4_000]
    carries = [carry_ins(row) for row in raw]
    digit_counts = Counter(char for row in raw for char in row)
    carry_counts = Counter(bit for row in carries for bit in row)
    digit_pairs: Counter[tuple[int, int]] = Counter()
    carry_pairs: Counter[tuple[int, int]] = Counter()
    for row, field in zip(raw, carries):
        for index in range(len(row)):
            digit_pairs[(ord(row[index]) - 48, ord(row[-1 - index]) - 48)] += 1
            carry_pairs[(field[index], field[-1 - index])] += 1
    digit_total = sum(digit_counts.values())
    carry_total = sum(carry_counts.values())

    return {
        "protocol": "fprd.reverse-add-196-orbit-audit.v1",
        "scope_boundary": "finite decimal orbit only; no assertion after T^4000(196)",
        "state_sequence": {
            "range": "T^k(196), 0 <= k <= 4000",
            "sha256_step_colon_state_newline": digest.hexdigest(),
            "final_digit_length": len(states[4_000]),
        },
        "reflection_distance": {
            "window": "outputs T^k(196), 1 <= k <= 4000",
            "definition": "number of ordered positions differing from reflection",
            "minimum": minimum,
            "minimum_ratio": {
                "step": ratio_row[0],
                "distance": ratio_row[2],
                "length": ratio_row[1],
                "value": round(ratio_row[2] / ratio_row[1], 12),
            },
            "mean_ratio_when_length_gt_100": round(sum(long) / len(long), 12),
            "rows_when_length_gt_100": len(long),
        },
        "shifted_axis": {
            "window": "transitions T^(k-1)(196) -> T^k(196), 1 <= k <= 3000",
            "estimator": "mean of per-output normalized mismatch fractions over valid index pairs",
            "step_counts": {"no_growth": group_sizes[False], "growth": group_sizes[True]},
            "mean_normalized_distance": {
                str(shift): {
                    "no_growth": round(grouped[False][shift] / group_sizes[False], 12),
                    "growth": round(grouped[True][shift] / group_sizes[True], 12),
                }
                for shift in range(-2, 3)
            },
        },
        "raw_complexity": {
            "window": "states T^k(196), 0 <= k < 4000",
            "subwords": "union of contiguous within-state words; row boundaries excluded",
            "digit_subword_counts_k_1_to_4": subword_counts(raw, 4),
            "carry_in_subword_counts_k_1_to_12": subword_counts(
                ["".join(map(str, field)) for field in carries], 12
            ),
            "digit_count": digit_total,
            "maximum_digit_frequency_deviation_from_one_tenth": round(
                max(abs(digit_counts[str(d)] / digit_total - 0.1) for d in range(10)), 12
            ),
            "carry_in_count": carry_total,
            "carry_in_density": round(carry_counts[1] / carry_total, 12),
            "mirrored_digit_mutual_information_bits": round(mi(digit_pairs), 12),
            "mirrored_carry_in_mutual_information_bits": round(mi(carry_pairs), 12),
        },
    }


def main() -> None:
    parser = argparse.ArgumentParser()
    parser.add_argument("certificate", type=Path)
    args = parser.parse_args()
    expected = json.loads(args.certificate.read_text(encoding="utf-8"))
    actual = independent_payload()
    if actual != expected:
        raise SystemExit("independent digit-list replay disagrees with certificate")
    print("Independent digit-list replay matched every certificate field.")


if __name__ == "__main__":
    main()