back to table · edit · history · where entries came from · files · download
6575 bytes, as of the version from 2026-10-16 11:15 (current). Recorded here, not run.
"""Independent character and monodromy checks for numberdb.org/T463.
Only Python integers and Fraction are used here. No cut-and-join values or
code are imported. Characters are obtained by Murnaghan-Nakayama rim strips,
with hook dimensions and full character orthogonality as controls.
For a fixed permutation sigma of cycle type mu, the number of ordered
r-transposition factorizations is
F_mu(r) = sum_lambda dim(lambda)*chi_lambda(mu)*c_lambda**r / d!,
where c_lambda=sum_(i,j in lambda)(j-i). This is the coefficient of sigma
in the rth power of the sum of all transpositions in Q[S_d].
To impose transitivity, subtract decompositions according to the component
containing the first cycle of sigma. For each proper subset S of the cycles
containing that cycle, subtract
sum_k binomial(r,k) C_mu[S](k) F_mu[complement](r-k).
These terms have disjoint component containing the first cycle, so each
nontransitive tuple is subtracted once. The labelled Hurwitz number equals
C_mu(r)/product(mu), by orbit-stabilizer.
"""
from functools import lru_cache
from fractions import Fraction
from math import factorial, prod, comb
from collections import Counter, defaultdict
from itertools import combinations, permutations
@lru_cache(None)
def parts(n, maximum=None):
if n == 0:
return ((),)
m = n if maximum is None else min(n,maximum)
return tuple((a,)+b for a in range(1,m+1) for b in parts(n-a,a))
@lru_cache(None)
def cells(lam):
return frozenset((i,j) for i,a in enumerate(lam) for j in range(a))
@lru_cache(None)
def character(lam, mu):
if not mu:
return int(not lam)
k=mu[0]
total=0
for nu in parts(sum(lam)-k):
if not cells(nu).issubset(cells(lam)):
continue
strip=cells(lam)-cells(nu)
if any((i+1,j) in strip and (i,j+1) in strip and (i+1,j+1) in strip for i,j in strip):
continue
reached={next(iter(strip))}
todo=list(reached)
while todo:
i,j=todo.pop()
for v in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
if v in strip and v not in reached:
reached.add(v);todo.append(v)
if reached==strip:
sign=-1 if len({i for i,j in strip}) % 2 == 0 else 1
total+=sign*character(nu,mu[1:])
return total
def dimension(lam):
hooks=prod(1+sum((i,k) in cells(lam) for k in range(j+1,max(lam)))
+sum((k,j) in cells(lam) for k in range(i+1,len(lam)))
for i,j in cells(lam))
return factorial(sum(lam))//hooks
def z_value(mu):
return prod(mu)*prod(factorial(v) for v in Counter(mu).values())
def character_controls(max_degree):
equations=0
assert character((2,1),(3,)) == -1
assert dimension((2,1)) == 2
for d in range(1,max_degree+1):
pp=parts(d)
assert sum(dimension(x)**2 for x in pp)==factorial(d)
for lam in pp:
assert character(lam,(1,)*d)==dimension(lam)
for mu in pp:
for nu in pp:
ans=sum(character(lam,mu)*character(lam,nu) for lam in pp)
assert ans==(z_value(mu) if mu==nu else 0),(d,mu,nu,ans)
equations+=1
return equations
@lru_cache(None)
def unrestricted(mu,R):
d=sum(mu)
result=[0]*(R+1)
for lam in parts(d):
weight=dimension(lam)*character(lam,mu)
content=sum(j-i for i,j in cells(lam))
for r in range(R+1):
result[r]+=weight*content**r
fac=factorial(d)
assert all(x % fac == 0 for x in result)
result=tuple(x//fac for x in result)
assert all(x>=0 for x in result)
return result
@lru_cache(None)
def connected(mu,R):
result=list(unrestricted(mu,R))
splits=Counter()
for mask in range(1 << (len(mu)-1)):
left=(mu[0],)+tuple(mu[j+1] for j in range(len(mu)-1) if mask & (1<<j))
right=tuple(mu[j+1] for j in range(len(mu)-1) if not mask & (1<<j))
if right:
splits[(left,right)]+=1
for (left,right),multiplicity in splits.items():
a=connected(left,R)
b=unrestricted(right,R)
for r in range(R+1):
result[r]-=multiplicity*sum(comb(r,k)*a[k]*b[r-k] for k in range(r+1))
assert all(x>=0 for x in result),(mu,result)
return tuple(result)
def hurwitz_character(g,mu,R=28):
r=2*g-2+sum(mu)+len(mu)
return Fraction(connected(mu,R)[r],prod(mu))
def prefactor(g,mu):
return Fraction(factorial(2*g-2+sum(mu)+len(mu))*prod(x**x for x in mu),prod(factorial(x) for x in mu))
def genus_zero(mu):
return prefactor(0,mu)*Fraction(sum(mu))**(len(mu)-3)
@lru_cache(None)
def psi_one(exponents):
"""Genus-one intersections from the string equation and <tau_1>=1/24."""
n=len(exponents)
if not n or min(exponents)<0 or sum(exponents)!=n:
return Fraction(0)
if 0 not in exponents:
assert all(x==1 for x in exponents)
return Fraction(factorial(n-1),24)
rest=list(exponents);rest.remove(0)
ans=Fraction(0)
for j,x in enumerate(rest):
if x:
reduced=rest.copy();reduced[j]-=1
ans+=psi_one(tuple(sorted(reduced)))
return ans
def vectors(total,length):
if length==1:
yield (total,)
return
for k in range(total+1):
for tail in vectors(total-k,length-1):
yield (k,)+tail
def elsv_one(mu):
"""ELSV, using psi and lambda_1 intersection formulas, not cut-and-join."""
n=len(mu)
top=sum((psi_one(tuple(sorted(a)))*prod(x**k for x,k in zip(mu,a))
for a in vectors(n,n)),Fraction(0))
hodge=Fraction(sum(mu)**(n-1),24)
return prefactor(1,mu)*(top-hodge)
def fixed_sigma(mu):
perm=list(range(sum(mu)));start=0
for m in mu:
for j in range(m):perm[start+j]=start+(j+1)%m
start+=m
return tuple(perm)
def direct_monodromy(d,R):
"""Dynamic enumeration on individual permutations and orbit partitions."""
identity=tuple(range(d))
counts={(identity,identity):1}
saved={}
pairs=list(combinations(range(d),2))
for r in range(R+1):
saved[r]={p:c for (p,blocks),c in counts.items() if len(set(blocks))==1}
if r==R:break
new=defaultdict(int)
for (p,blocks),count in counts.items():
for a,b in pairs:
perm=list(p);perm[a],perm[b]=perm[b],perm[a]
low,high=sorted((blocks[a],blocks[b]))
joined=tuple(low if x==high else x for x in blocks)
new[(tuple(perm),joined)]+=count
counts=new
return saved