#!/usr/bin/env python3
"""Exact check of the crossing identity behind the sum-of-squares note, in every characteristic.

Independent implementation, written from the definitions in Appendix B of the Anthropic paper.
V = Z[t_1, t_2, ...] with weight(t_k) = k. D_{-k} multiplies by t_k, D_k = k d/dt_k.
For a monomial a = t_mu, a[r] = sum over (k_i) with k_i != 0, sum k_i = -r, of
    prod_i binom(-k_i - 1, mu_i - 1) * prod_{k_i<0} D_{k_i} * prod_{k_i>0} D_{k_i}  (differentiations first).
Q_s(a,b) = sum_{i=0}^{2h} (-1)^i a<i>[s-h+i] b[h-s-i], a<i> = sum_{h'} binom(h'+h, i) abar_{h'}.

p = 0: labels are all partitions of h, computations over Z.
p prime: V' = F_p[t_k : p does not divide k]/(t_k^p), labels are partitions of h with parts not divisible by p
and multiplicities < p; dim V'_E = q_p(E). All operators preserve the ideal, so we compute in V' directly.

Checks, for every s and all labels:
  (1) Q_s is the same in both orders: a<i>[..] b[..] versus b[..] a<i>[..];
  (2) sum_s A_s(x,y,u,v) = z_{mu(v)} [x=v][y=u];
  (3) rank of A_s across (x,y)|(u,v) is at most R_s = sum_i dim V'_{s+i},
      rank across (x,u)|(y,v) is at most O_s = sum_i dim V'_{2h-s-i}.
Usage: python check_pieces.py p h [h ...]
"""
import sys
from functools import lru_cache
from math import comb, log2


def binom_int(n, j):
    """Generalized binomial for integer n and j >= 0."""
    if j < 0:
        return 0
    if n >= 0:
        return comb(n, j)
    return (-1) ** j * comb(j - n - 1, j)


def partitions(n, maxpart=None):
    """Partitions of n as nonincreasing tuples."""
    if maxpart is None:
        maxpart = n
    if n == 0:
        yield ()
        return
    for k in range(min(n, maxpart), 0, -1):
        for rest in partitions(n - k, k):
            yield (k,) + rest


class Ring:
    def __init__(self, p):
        self.p = p

    def reduce(self, c):
        return c % self.p if self.p else c

    def admissible(self, mono):
        """Is this monomial nonzero in V'?"""
        if not self.p:
            return True
        from collections import Counter
        return all(k % self.p != 0 and m < self.p for k, m in Counter(mono).items())

    def labels(self, h):
        return [m for m in partitions(h) if self.admissible(m)]

    def z(self, mono):
        from collections import Counter
        from math import factorial
        v = 1
        for k, m in Counter(mono).items():
            v *= k ** m * factorial(m)
        return self.reduce(v)

    def clean(self, f):
        out = {}
        for m, c in f.items():
            c = self.reduce(c)
            if c:
                out[m] = c
        return out

    def add(self, f, g, scale=1):
        out = dict(f)
        for m, c in g.items():
            out[m] = out.get(m, 0) + scale * c
        return self.clean(out)

    def mult_t(self, l, f):
        """D_{-l}: multiply by t_l."""
        out = {}
        for m, c in f.items():
            nm = tuple(sorted(m + (l,), reverse=True))
            if self.admissible(nm):
                out[nm] = out.get(nm, 0) + c
        return self.clean(out)

    def deriv(self, k, f):
        """D_k = k d/dt_k."""
        out = {}
        for m, c in f.items():
            e = m.count(k)
            if e:
                lst = list(m)
                lst.remove(k)
                nm = tuple(lst)
                out[nm] = out.get(nm, 0) + c * k * e
        return self.clean(out)


class Ops:
    def __init__(self, ring):
        self.R = ring
        self.cache = {}

    def mono_action(self, parts, r, mono):
        """t_parts[r] applied to one basis monomial; recursion on the first part (the sum over its k)."""
        key = (parts, r, mono)
        if key in self.cache:
            return self.cache[key]
        R = self.R
        E = sum(mono)
        if not parts:
            res = {mono: 1} if r == 0 else {}
        elif E + r < 0:
            res = {}
        else:
            n, rest = parts[0], parts[1:]
            res = {}
            # k = -l < 0 : multiplication, applied after the rest
            for l in range(n, E + r + 1):
                c = R.reduce(comb(l - 1, n - 1))
                if c:
                    inner = self.mono_action(rest, r - l, mono)
                    if inner:
                        res = R.add(res, R.mult_t(l, inner), c)
            # k > 0 : differentiation, applied before the rest
            for k in set(mono):
                c = R.reduce(binom_int(-k - 1, n - 1))
                if c:
                    d = R.deriv(k, {mono: 1})
                    for m2, c2 in d.items():
                        inner = self.mono_action(rest, r + k, m2)
                        if inner:
                            res = R.add(res, inner, c * c2)
        self.cache[key] = res
        return res

    def act(self, a, r, f):
        """a[r] f with a a polynomial {monomial: coefficient}."""
        R = self.R
        out = {}
        for parts, ca in a.items():
            for m, cf in f.items():
                img = self.mono_action(parts, r, m)
                if img:
                    out = R.add(out, img, ca * cf)
        return out


def y_poly(n, ring):
    return ring.clean({(j,): comb(n, j) for j in range(1, n + 1)})


def poly_mul(f, g, ring):
    out = {}
    for m1, c1 in f.items():
        for m2, c2 in g.items():
            m = tuple(sorted(m1 + m2, reverse=True))
            out[m] = out.get(m, 0) + c1 * c2
    return ring.clean(out)


def a_of(mu, ring):
    """a_mu = prod_i (-1)^{mu_i - 1} y_{mu_i}. Lives in the full ring, not the quotient."""
    out = {(): 1}
    for n in mu:
        out = poly_mul(out, {m: (-1) ** (n - 1) * c for m, c in y_poly(n, ring).items()}, ring)
    return out


def a_bracket(a, h, i, ring):
    """a<i> = sum_{h'} binom(h'+h, i) abar_{h'}."""
    return ring.clean({m: comb(sum(m) + h, i) * c for m, c in a.items()})


def dims(ring, Lmax):
    if ring.p == 0:
        d = [0] * (Lmax + 1)
        d[0] = 1
        for k in range(1, Lmax + 1):
            for e in range(k, Lmax + 1):
                d[e] += d[e - k]
        return d
    d = [0] * (Lmax + 1)
    d[0] = 1
    for k in range(1, Lmax + 1):
        if k % ring.p == 0:
            continue
        new = [0] * (Lmax + 1)
        for e in range(Lmax + 1):
            if d[e]:
                for j in range(ring.p):
                    if e + j * k <= Lmax:
                        new[e + j * k] += d[e]
        d = new
    return d


def rank_mod(rows, P):
    """Rank over F_P of a list of dicts (sparse rows)."""
    piv = {}
    rk = 0
    for r in rows:
        r = {k: v % P for k, v in r.items() if v % P}
        while r:
            k = min(r)
            if k in piv:
                pr = piv[k]
                c = r[k] * pow(pr[k], -1, P) % P
                for kk, vv in pr.items():
                    nv = (r.get(kk, 0) - c * vv) % P
                    if nv:
                        r[kk] = nv
                    else:
                        r.pop(kk, None)
            else:
                piv[k] = r
                rk += 1
                break
    return rk


def check(p, h, verbose=True):
    ring = Ring(p)
    ops = Ops(ring)
    labels = ring.labels(h)
    N = len(labels)
    if N == 0:
        print(f"p={p} h={h}: no labels")
        return None
    d = dims(ring, 4 * h)
    A_polys = {x: a_of(x, ring) for x in labels}
    S_range = range(-2 * h, 2 * h + 1)
    tensors = {}
    order_ok = True
    for s in S_range:
        A = {}
        for x in labels:
            for v in labels:
                b = {v: 1}
                for y in labels:
                    # order 1: b acts first
                    tot1 = {}
                    tot2 = {}
                    for i in range(0, 2 * h + 1):
                        ai = a_bracket(A_polys[x], h, i, ring)
                        if not ai:
                            continue
                        sign = (-1) ** i
                        w = ops.act(b, h - s - i, {y: 1})
                        if w:
                            tot1 = ring.add(tot1, ops.act(ai, s - h + i, w), sign)
                        w2 = ops.act(ai, s - h + i, {y: 1})
                        if w2:
                            tot2 = ring.add(tot2, ops.act(b, h - s - i, w2), sign)
                    if tot1 != tot2:
                        order_ok = False
                    for u in labels:
                        c = tot1.get(u, 0)
                        if c:
                            A[(x, y, u, v)] = c
        tensors[s] = A
    # identity
    ident_ok = True
    total = {}
    for s in S_range:
        for key, c in tensors[s].items():
            total[key] = total.get(key, 0) + c
    for x in labels:
        for y in labels:
            for u in labels:
                for v in labels:
                    want = ring.z(v) if (x == v and y == u) else 0
                    if ring.reduce(total.get((x, y, u, v), 0) - want) != 0:
                        ident_ok = False
    # ranks; over Q use a large prime
    P = p if p else (1 << 61) - 1
    rank_ok = True
    report = []
    for s in S_range:
        A = tensors[s]
        Rs = sum(d[s + i] for i in range(0, 2 * h + 1) if 0 <= s + i <= 4 * h)
        Os = sum(d[2 * h - s - i] for i in range(0, 2 * h + 1) if 0 <= 2 * h - s - i <= 4 * h)
        rows_row = {}
        rows_col = {}
        for (x, y, u, v), c in A.items():
            rows_row.setdefault((x, y), {})[(u, v)] = c
            rows_col.setdefault((x, u), {})[(y, v)] = c
        rr = rank_mod(list(rows_row.values()), P)
        rc = rank_mod(list(rows_col.values()), P)
        if rr > Rs or rc > Os:
            rank_ok = False
        report.append((s, rr, Rs, rc, Os))
    if verbose:
        bound = sum(min(r[2], r[4]) for r in report)
        trueb = sum(min(r[1], r[3]) for r in report)
        print(f"p={p} h={h} N={N}: both orders agree: {order_ok}; identity: {ident_ok}; rank bounds: {rank_ok}; "
              f"sum_s min(R_s,O_s) = {bound}, with true ranks {trueb}; N^2 = {N*N}", flush=True)
    return order_ok and ident_ok and rank_ok


if __name__ == '__main__':
    p = int(sys.argv[1])
    ok = True
    for h in map(int, sys.argv[2:]):
        r = check(p, h)
        ok = ok and (r is not False)
    print('ALL OK' if ok else 'FAILURE')
