"""Reproduce the exact budget-transfer schematic and finite operator checks.""" from pathlib import Path SVG='' Path(__file__).with_suffix(".svg").write_bytes(SVG.encode("utf-8")) from fractions import Fraction import cmath,math,itertools,json constant_checks=0 for q in range(2,13): prefix=[2*5**i for i in range(q-1)] recurrence=sum(x*x for x in prefix)+sum(prefix)**2 printed=Fraction(25**(q-1)-1,6)+Fraction(5**(q-1)-1,2)**2 assert printed==recurrence constant_checks+=1 n=12 cases=[([10,1,1],[4,4,4]),([6,4,2],[2,4,6]),([3,3,3,3],[1,5,2,4]),([5,4,3],[5,4,3])] def owners(counts): return [i for i,c in enumerate(counts) for _ in range(c)] def redistribute(old_counts,new_counts): old=owners(old_counts);new=old[:];supply=[] for i,(p,a) in enumerate(zip(old_counts,new_counts)): if p>a: candidates=[k for k,o in enumerate(old) if o==i] supply.extend(candidates[:p-a]) pos=0 for i,(p,a) in enumerate(zip(old_counts,new_counts)): if a>p: for k in supply[pos:pos+a-p]:new[k]=i pos+=a-p assert pos==len(supply) assert [new.count(i) for i in range(len(new_counts))]==new_counts diffs=[Fraction(sum((o==i)!=(r==i) for o,r in zip(old,new)),n) for i in range(len(new_counts))] assert diffs==[Fraction(abs(p-a),n) for p,a in zip(old_counts,new_counts)] return old,new,sum(diffs) def l2sq(x):return sum(abs(v)**2 for row in x for v in row)/n def diff(x,y):return [[x[a][b]-y[a][b] for b in range(n)] for a in range(n)] def pinch(x,o):return [[x[a][b] if o[a]==o[b] else 0 for b in range(n)] for a in range(n)] def diagonal(x):return [[x[a][b] if a==b else 0 for b in range(n)] for a in range(n)] operator_checks=0 for oc,nc in cases: old,new,D=redistribute(oc,nc) targets=[[[cmath.exp(2j*math.pi*a*b/n)/math.sqrt(n) for b in range(n)] for a in range(n)]] for a in range(n): for b in range(n): m=[[0j]*n for _ in range(n)];m[a][b]=1;targets.append(m) K2=sum(1 for a in range(n) for b in range(n) if a!=b and old[a]==old[b] and new[a]==new[b]) for x in targets: # These targets have operator norm1. Their old pinching is a contraction. px=pinch(x,old);rx=pinch(x,new) assert l2sq(diff(rx,px))<=4*float(D)+1e-10 b=px;c=pinch(b,new);expect=diagonal(c) eta2=l2sq(diff(c,expect));off2=l2sq(diff(b,c)) assert abs(l2sq(diff(b,expect))-(off2+eta2))<1e-10 assert off2<=4*float(D)+1e-10 assert eta2<=l2sq(b)*K2+1e-10 total=math.sqrt(l2sq(diff(x,diagonal(x)))) old_error=math.sqrt(l2sq(diff(x,b))) assert total<=old_error+math.sqrt(4*float(D)+eta2)+1e-10 operator_checks+=1 eps=Fraction(1,7);R=5 D_threshold=eps**2/(64*R**2);K2_threshold=eps**2/(16*R**2) assert 4*R**2*D_threshold+R**2*K2_threshold==eps**2/8