verify-hunt-calibration.py

#!/usr/bin/env python3
"""Exact arithmetic checks for the Stirling/arrangement hunt calibration."""

from fractions import Fraction
from math import factorial


def stirling_first_kind(n: int) -> list[int]:
    row = [0] * (n + 1)
    row[0] = 1
    for size in range(1, n + 1):
        nxt = [0] * (n + 1)
        for cycles in range(1, size + 1):
            nxt[cycles] = row[cycles - 1] + (size - 1) * row[cycles]
        row = nxt
    return row


def binomial(n: int, k: int) -> int:
    return factorial(n) // (factorial(k) * factorial(n - k))


def unordered_bipartition_degree(hard_labels: int) -> int:
    total = 0
    for a in range(1, hard_labels):
        b = hard_labels - a
        total += binomial(hard_labels, a) * factorial(a - 1) * factorial(b - 1)
    return total // 2


for m in range(2, 13):
    c = stirling_first_kind(m)
    assert sum(c) == factorial(m)
    assert sum(c[k] for k in range(0, m + 1) if k % 2 == 0) == factorial(m) // 2
    assert sum(c[k] for k in range(0, m + 1) if k % 2 == 1) == factorial(m) // 2

    # The degree-q braid-arrangement piece has dimension [m, m-q].
    reversed_hilbert = [c[m - q] for q in range(m)]
    amplitude_blocks = [c[k] for k in range(1, m + 1)]
    assert amplitude_blocks == list(reversed(reversed_hilbert))

    weighted_stirling_degree = sum(k * c[k] for k in range(m + 1))
    harmonic_degree = factorial(m) * sum(Fraction(1, j) for j in range(1, m + 1))
    assert harmonic_degree.denominator == 1
    assert weighted_stirling_degree == harmonic_degree.numerator
    assert weighted_stirling_degree == stirling_first_kind(m + 1)[2]

    # Dong--Stieberger's conjectural factors are indexed by unordered
    # bipartitions of m+1 hard labels, including singleton sides.
    factor_degree = unordered_bipartition_degree(m + 1)
    assert factor_degree == weighted_stirling_degree

    print(
        f"m={m:2d} blocks={amplitude_blocks} "
        f"total={factorial(m):9d} half={factorial(m)//2:9d} "
        f"det_degree={factor_degree:10d}"
    )

print("all exact Stirling, parity, reversed-filtration, and determinant-degree checks passed")