"""Count SU(n) singlets and check the formula N(n, m) = m! L_m^(n)(1).

Counts SU(n) singlets in n^{(x)(n+m)} (x) nbar^{(x)m}, fits the polynomials P_m(n)
by finite differences, checks the difference pattern and the generating function,
and checks the proven closed form. Pure Python 3, no packages. Run:
    python3 singlets.py
"""
from collections import defaultdict
from fractions import Fraction
from math import comb, factorial


# ---------- partitions and standard Young tableaux (SYT) ----------
def partitions(m, max_part=None):
    """All partitions of m as weakly decreasing tuples."""
    max_part = m if max_part is None else max_part
    if m == 0:
        yield ()
        return
    for first in range(min(m, max_part), 0, -1):
        for rest in partitions(m - first, first):
            yield (first,) + rest


def num_syt(shape):
    """f^shape, the number of SYT of the given shape (hook-length formula)."""
    shape = [r for r in shape if r > 0]
    if not shape:
        return 1
    cols = [sum(1 for r in shape if r > j) for j in range(shape[0])]
    hooks = 1
    for i, r in enumerate(shape):
        for j in range(r):
            hooks *= (r - j) + (cols[j] - i) - 1
    return factorial(sum(shape)) // hooks


def singlets(n, m):
    """N(n^{(n+m)} (x) nbar^{m}) = sum over nu |- m with <= n rows of f^nu * f^(nu + one full column).

    Valid for every m >= 0 (no restriction m <= n+1)."""
    total = 0
    for nu in partitions(m):
        if len(nu) <= n:
            padded = list(nu) + [0] * (n - len(nu))
            total += num_syt(nu) * num_syt([r + 1 for r in padded])
    return total


# ---------- independent check: Weyl integration formula ----------
def _mul(a, b):
    out = defaultdict(int)
    for ea, ca in a.items():
        for eb, cb in b.items():
            out[tuple(x + y for x, y in zip(ea, eb))] += ca * cb
    return {e: c for e, c in out.items() if c}


def singlets_weyl(n, k, m):
    """dim of SU(n) invariants in V^{(x)k} (x) V*^{(x)m}, from the Weyl integration formula.

    Integrates (tr U)^k (tr U^dagger)^m (det U^dagger)^q over U(n), q = (k-m)/n.
    Slow: use n <= 4 and k + m <= 14."""
    if (k - m) % n:
        return 0
    q = (k - m) // n
    unit = lambda i, s: tuple(s if j == i else 0 for j in range(n))
    f = {(0,) * n: 1}
    for _ in range(k):
        f = _mul(f, {unit(i, 1): 1 for i in range(n)})
    for _ in range(m):
        f = _mul(f, {unit(i, -1): 1 for i in range(n)})
    f = _mul(f, {tuple([-q] * n): 1})
    for i in range(n):  # Haar density |Vandermonde|^2
        for j in range(i + 1, n):
            f = _mul(f, {unit(i, 1): 1, unit(j, 1): -1})
            f = _mul(f, {unit(i, -1): 1, unit(j, -1): -1})
    return f.get((0,) * n, 0) // factorial(n)


# ---------- finite-difference polynomial fit ----------
def fit_polynomial(values, x0):
    """Integer coefficients [c0, c1, ...] of the polynomial through (x0 + j, values[j]).

    Newton's forward-difference formula: P(x) = sum_j Delta^j P(x0) * binom(x - x0, j)."""
    leading, row = [], list(values)
    while row:
        leading.append(row[0])
        row = [b - a for a, b in zip(row, row[1:])]
    coeffs = [Fraction(0)] * len(values)
    for j, d in enumerate(leading):
        basis = [Fraction(1)]  # prod_{i<j} (x - x0 - i), as a coefficient list
        for i in range(j):
            shifted = [Fraction(0)] + basis
            basis = [s - (x0 + i) * b for s, b in zip(shifted, basis + [0])]
        for p, c in enumerate(basis):
            coeffs[p] += d * c / factorial(j)
    while len(coeffs) > 1 and coeffs[-1] == 0:
        coeffs.pop()
    assert all(c.denominator == 1 for c in coeffs)
    return [int(c) for c in coeffs]


def show_poly(coeffs):
    terms = []
    for p in range(len(coeffs) - 1, -1, -1):
        c = coeffs[p]
        if c == 0:
            continue
        mag = abs(c)
        body = ("" if (mag == 1 and p > 0) else str(mag)) + ("" if p == 0 else "n" if p == 1 else f"n^{p}")
        terms.append(("- " if c < 0 else "+ ") + body)
    s = " ".join(terms)
    return s[2:] if s.startswith("+ ") else "-" + s[2:]


# ---------- closed forms ----------
def closed_form(n, m):
    """sum_i (-1)^i C(m,i) (n+m)!/(n+i)!  =  m! L_m^{(n)}(1)."""
    return sum((-1) ** i * comb(m, i) * factorial(n + m) // factorial(n + i) for i in range(m + 1))


def a009940(m):
    """m! L_m(1) = sum_k (-1)^k C(m,k) m!/k!  (OEIS A009940)."""
    return sum((-1) ** k * comb(m, k) * factorial(m) // factorial(k) for k in range(m + 1))


def rising(x, r):
    out = 1
    for i in range(r):
        out *= x + i
    return out


# Expected polynomials P_0..P_10, constant term first.
EXPECTED_POLYNOMIALS = {
    0: [1], 1: [0, 1], 2: [-1, 1, 1], 3: [-4, -1, 3, 1], 4: [-15, -16, 5, 6, 1],
    5: [-56, -111, -20, 25, 10, 1], 6: [-185, -691, -356, 55, 70, 15, 1],
    7: [-204, -4145, -3577, -476, 385, 154, 21, 1],
    8: [6209, -23080, -31942, -10444, 1099, 1316, 294, 28, 1],
    9: [112400, -96159, -272064, -139966, -13692, 9219, 3444, 510, 36, 1],
    10: [1520271, 195137, -2198289, -1658010, -381445, 35763, 35553, 7710, 825, 45, 1],
}

if __name__ == "__main__":
    M = 10
    print("1. Tableau formula agrees with the Weyl integral, and the selection rule holds:")
    ok = all(singlets(n, m) == singlets_weyl(n, n + m, m)
             for n in range(1, 4) for m in range(0, 5) if 2 * m + n <= 12)
    rule = all(singlets_weyl(n, k, m) == 0 for n in range(2, 4) for m in range(0, 3)
               for k in range(m + 1, n + m))
    print("   agree:", ok, "| no singlets for m < k < n+m:", rule)

    print("\n2. Data N(n, m) for m <= n+1 (rows n, columns m):")
    for n in range(1, 8):
        print(f"   n={n}:", [singlets(n, m) for m in range(0, n + 2)])

    print("\n3. Finite-difference table in n for m = 3 (n = 2..8):")
    row = [singlets(n, 3) for n in range(2, 9)]
    level = 0
    while row and any(row):
        print(f"   Delta^{level}:", row)
        row = [b - a for a, b in zip(row, row[1:])]
        level += 1

    print("\n4. Fitted P_m(n) (from n = max(1, m-1) onward, two extra points as a check):")
    fits = {}
    for m in range(0, M + 1):
        n0 = max(1, m - 1)
        fits[m] = fit_polynomial([singlets(n, m) for n in range(n0, n0 + m + 3)], n0)
        assert len(fits[m]) == m + 1, "degree is not m"
        print(f"   P_{m}(n) = {show_poly(fits[m])}   matches expected: {fits[m] == EXPECTED_POLYNOMIALS[m]}")

    print("\n5. Pattern: P_m(n+1) - P_m(n) == m * P_{m-1}(n+1)?")
    ev = lambda c, x: sum(ci * x ** i for i, ci in enumerate(c))
    print("   ", all(ev(fits[m], x + 1) - ev(fits[m], x) == m * ev(fits[m - 1], x + 1)
                     for m in range(1, M + 1) for x in range(-5, 15)))

    print("\n6. Constant terms P_m(0) vs OEIS A009940 (m! L_m(1)):")
    print("   P_m(0):  ", [fits[m][0] for m in range(M + 1)])
    print("   A009940: ", [a009940(m) for m in range(M + 1)])
    print("   G_n = G_0/(1-t)^n, i.e. P_m(n) == sum_j C(m,j) P_j(0) n(n+1)...(n+m-j-1)?",
          all(ev(fits[m], x) == sum(comb(m, j) * fits[j][0] * rising(x, m - j) for j in range(m + 1))
              for m in range(M + 1) for x in range(0, 15)))

    print("\n7. Theorem: N(n, m) == sum_i (-1)^i C(m,i)(n+m)!/(n+i)! for all 1 <= n <= 15, m <= n+1:",
          all(singlets(n, m) == closed_form(n, m) for n in range(1, 16) for m in range(0, n + 2)))

    print("\n8. Sharpness at m = n+2: N - closed form == Catalan(n+1)?")
    for n in range(1, 7):
        gap = singlets(n, n + 2) - closed_form(n, n + 2)
        print(f"   n={n}: gap={gap}, Catalan(n+1)={comb(2 * n + 2, n + 1) // (n + 2)}")
