#!/usr/bin/env python3 """Exact capped moments over the source's restricted support (k = 46). Transcription of the exact identities in eprint 2026/1893, sections 4.9-4.10, specialised to a symmetric-polynomial term (U - s(t))^e m_nu(t): Lemma 4.19 (Dirichlet / Beta): int_{s(t) <= V} (V - s(t))^b m_alpha(t) dt = V^{n+b+|alpha|} b! emb_n(alpha) prod_{q in alpha} q! / (n+b+|alpha|)! . Cap stratum: T = {t >= 0 : s(t) < U, sum_{t_i > delta} t_i <= B_{r(t)}}, r(t) = #{i : t_i > delta}. Split by r, shift rough coordinates t_i = delta+y_i, keep small ones v_i in [0,delta], and remove the box by inclusion-exclusion (source equations (76) and (77)). All arithmetic is exact (fractions.Fraction / integers). """ from __future__ import annotations from fractions import Fraction as Fr from math import comb, factorial from typing import Callable def mult(parts) -> dict: d: dict = {} for p in parts: d[p] = d.get(p, 0) + 1 return d def expand(d: dict) -> tuple: out = [] for k, v in d.items(): out += [k] * v return tuple(sorted(out, reverse=True)) def prod_fact(parts) -> int: r = 1 for p in parts: r *= factorial(p) return r def emb(n: int, nu: dict) -> int: """n! / ((n - ell(nu))! prod_q m_q!), zero when ell(nu) > n.""" ell = sum(nu.values()) if ell > n: return 0 r = factorial(n) // factorial(n - ell) for mq in nu.values(): r //= factorial(mq) return r def _distribute(mults: dict): """All vectors u_q in [0, m_q] with their product of binomials C(m_q, u_q).""" items = list(mults.items()) def rec(i, acc, coef): if i == len(items): yield dict(acc), coef return q, mq = items[i] for uq in range(mq + 1): acc[q] = uq yield from rec(i + 1, acc, coef * comb(mq, uq)) acc.pop(q, None) yield from rec(0, {}, 1) def shifted_small(h_mult: dict, m_small: int, delta: Fr) -> dict: """Inclusion-exclusion + power expansion over the small coordinates. Each small coordinate with exponent q is either left alone (j += 0, exponent q) or shifted by delta (j += 1, (delta+v)^q = sum_s C(q,s) delta^{q-s} v^s). A coordinate with exponent 0 contributes (1 - t). Returns {(j, hprime_tuple): Fraction coefficient}. """ G = {(0, ()): Fr(1)} for q, cq in h_mult.items(): opts = [(0, (q,), Fr(1))] for s in range(0, q + 1): w = Fr(-comb(q, s)) * delta ** (q - s) opts.append((1, () if s == 0 else (s,), w)) for _ in range(cq): newG: dict = {} for (j, hp), coef in G.items(): for (dj, add, w) in opts: key = (j + dj, tuple(sorted(hp + add, reverse=True))) newG[key] = newG.get(key, Fr(0)) + coef * w G = newG z = m_small - sum(h_mult.values()) if z < 0: raise ValueError("small multiplicities exceed group size") if z == 0: return G out: dict = {} for (j0, hp), coef in G.items(): for ji in range(z + 1): w = Fr(comb(z, ji) * ((-1) ** ji)) key = (j0 + ji, hp) out[key] = out.get(key, Fr(0)) + coef * w return out def expanded_rough(g_mult: dict, delta: Fr) -> dict: """Expand (delta + y)^q = sum_s C(q,s) delta^{q-s} y^s for each rough occurrence. Returns {gprime_tuple: coefficient}.""" G = {(): Fr(1)} for q, cq in g_mult.items(): opts = [] for s in range(0, q + 1): opts.append((() if s == 0 else (s,), Fr(comb(q, s)) * delta ** (q - s))) for _ in range(cq): newG: dict = {} for gp, coef in G.items(): for add, w in opts: key = tuple(sorted(gp + add, reverse=True)) newG[key] = newG.get(key, Fr(0)) + coef * w G = newG return G def capped_integral(n: int, e: int, nu, U: Fr, delta: Fr, Bfun: Callable[[int], Fr]) -> Fr: """int_T (U - s(t))^e m_nu(t) dt for the capped support in n variables.""" num = mult(nu) ell = sum(num.values()) if ell > n: return Fr(0) total = Fr(0) embn = emb(n, num) for r in range(0, n + 1): Br = Bfun(r) if r * delta > Br: break m_small = n - r for u_dist, dcoef in _distribute(num): u = sum(u_dist.values()) if u > r: continue g_mult = {q: uq for q, uq in u_dist.items() if uq > 0} h_mult = {q: num[q] - u_dist[q] for q in num if num[q] - u_dist[q] > 0} prof = embn * comb(n - ell, r - u) * dcoef if prof == 0: continue Gs = shifted_small(h_mult, m_small, delta) Gr = expanded_rough(g_mult, delta) if r >= 1 else {(): Fr(1)} for gp, coef_g in Gr.items(): deg_g = sum(gp) for (j, hp), coef2 in Gs.items(): if coef2 == 0: continue Rp = U - (r + j) * delta if Rp < 0: continue p = e + m_small + sum(hp) small = Fr(factorial(e) * prod_fact(hp), factorial(p)) if r == 0: inner = Rp ** p else: C = min(Br - r * delta, Rp) if C < 0: continue s = Fr(0) for q in range(0, p + 1): s += (Fr(comb(p, q)) * (Rp - C) ** (p - q) * Fr(factorial(q)) * C ** (r + deg_g + q) / Fr(factorial(r + deg_g + q))) inner = Fr(prod_fact(gp)) * s total += prof * coef_g * coef2 * small * inner return total def uncapped_integral(n: int, e: int, nu, U: Fr) -> Fr: """Lemma 4.19 closed form (no cap, no threshold).""" num = mult(nu) ell = sum(num.values()) if ell > n: return Fr(0) deg = sum(k * v for k, v in num.items()) return (U ** (n + e + deg) * Fr(factorial(e) * emb(n, num) * prod_fact(expand(num)), factorial(n + e + deg))) if __name__ == "__main__": U = Fr(886, 861) n = 4 print("control 1: delta = U, B = 0 => full simplex (Lemma 4.19)") ok = True for nu in [(2,), (2, 2), (4, 2), (2, 2, 2), (6, 4)]: for e in range(0, 4): a = capped_integral(n, e, nu, U, U, lambda r: Fr(0)) b = uncapped_integral(n, e, nu, U) good = (a == b) ok &= good print(f" nu={nu} e={e}: {a} vs {b} {'OK' if good else 'MISMATCH'}") print("control 1:", "PASS" if ok else "FAIL")