"""Replay the shape-only pentagon metric elimination using integer arithmetic.""" import argparse import json from fractions import Fraction as F from itertools import product from math import comb, lcm from pathlib import Path import time import numpy as np from twoear_data import ear_data, monomials S = 1 << 45 U = 1 << 20 HP = 1 << 24 ANCHOR = 1 << 28 PC, QC = 10349, 1000 DEG = 4 NDEG = 2*DEG+1 MAX64 = 2**63-1 DOMAINS = { 'u_three_quarters': [(F(1,2),F(3,4)),(F(1,4),F(1)),(F(1,2),F(1)),(F(1,4),F(1))], 'a_seven_sixteenths': [(F(3,4),F(1)),(F(1,4),F(7,16)),(F(3,4),F(1)),(F(1,4),F(1))], } DIR = [(1,0),(2,1),(1,1),(1,2),(0,1),(-1,2),(-1,1),(-2,1)] COMB = [(0,1),(0,-1),(1,1),(1,-1)] W = np.array([[comb(NDEG,i)*comb(NDEG,j) for j in range(NDEG+1)] for i in range(NDEG+1)],dtype=np.int64) def maxabs(x): return max(abs(int(np.min(x))),abs(int(np.max(x)))) def half(t,axis): v=np.moveaxis(t,axis,0);n=v.shape[0]-1 assert 2*maxabs(v)=i else 0 for j in range(n+1)] for i in range(n+1)],dtype=object) coeff=right@left;k=lcm(*(v.denominator for v in coeff.flat)) op=np.array([[int(x*k) for x in row] for row in coeff],dtype=object) x=np.moveaxis(t,axis,0) return np.moveaxis((op@x.reshape(n+1,-1)).reshape(x.shape),0,axis),den*k def quant(x,d): a=(x*S)//d assert maxabs(a)1 or min(t[1] for t in vals)>1 def dual(data,sign,lo,hi): al,ah=int(lo[0]),int(hi[0]) ll=list(map(int,lo[6:15]));hh=list(map(int,hi[6:15])) detlo=dethi=0 for perm,parity in [((0,1,2),1),((1,2,0),1),((2,0,1),1), ((0,2,1),-1),((2,1,0),-1),((1,0,2),-1)]: i,j,k=perm l,h=imin(*imin(ll[i],hh[i],ll[3+j],hh[3+j]),ll[6+k],hh[6+k]) detlo,dethi=detlo+(l if parity==1 else -h),dethi+(h if parity==1 else -l) assert (detlo>0 if sign==-1 else dethi<0),('compression-map orientation',detlo,dethi) cl,ch=list(map(int,lo[15:])),list(map(int,hi[15:])) a,b=max(abs(cl[0]),abs(ch[0])),max(abs(cl[1]),abs(ch[1])) kl=[cl[2]-(a*a+al-1)//al,cl[3]-(b*b+al-1)//al] kh=ch[2:4] pl,ph=imin(cl[0],ch[0],cl[1],ch[1]) k3l=cl[4]-max(-(-ph//s) for s in (al,ah)) k3h=ch[4]-min(pl//s for s in (al,ah)) assert min(kl)>0 v=[(17*kl[1],23*kh[1]),(17*kl[0],23*kh[0]), (-40*k3h-3*sum(kh),-40*k3l+3*sum(kh))] ew=np.zeros((20,len(DIR)*3),dtype=np.int64) for i,(s,t) in enumerate(DIR): for j in range(3): ew[6+j,i*3+j]=s*s;ew[9+j,i*3+j]=t*t;ew[12+j,i*3+j]=2*s*t el,eh=(np.array(x.reshape(len(DIR),3),dtype=object) for x in enclosed(apply_all(data,ew,1))) for i in range(len(DIR)): nxt=(i+1)%len(DIR);ol=oh=0 for j,(vl,vh) in enumerate(v): a,b=(j+1)%3,(j+2)%3 l1,h1=imin(el[i,a],eh[i,a],el[nxt,b],eh[nxt,b]) l2,h2=imin(el[i,b],eh[i,b],el[nxt,a],eh[nxt,a]) l,h=imin(l1-h2,h1-l2,vl,vh);ol+=l;oh+=h assert (ol>0 if sign==1 else oh<0),('dual',i,ol,oh) def compression(data,H,lo,hi): al,ah=int(lo[0]),int(hi[0]) assert al>0 ap=anchors(data)[0] zw=np.zeros((20,20),dtype=np.int64) for i,(j,sgn) in enumerate(COMB): for k in range(5): for r in range(3): zw[6+3*j+r,5*i+k]=H[k,r] zw[12+r,5*i+k]=sgn*H[k,r] z=apply_all(data,zw,HP);zlo,zhi=enclosed(z);anchor=anchors(z).reshape(4,5) # P = C*M - A0*Z_0 - z00*A, in common fixed-point units. combined=[] for (t,te),(zt,ze) in zip(data,z): combined.append((np.concatenate([t[...,:6],zt[...,::5]],axis=-1), np.concatenate([te[:6],ze[::5]]))) pw=np.zeros((10,4),dtype=np.int64) mw=np.zeros((10,4),dtype=np.int64) for i,(j,sgn) in enumerate(COMB): pw[0,i]=-anchor[i,0];pw[6+i,i]=-ap mw[3+j,i]=PC;mw[5,i]=sgn*PC pa=apply_all(combined,pw,ANCHOR);pm=apply_all(combined,mw,QC) combined_p=[] for (p,pe),(m,me) in zip(pa,pm): assert maxabs(p)+maxabs(m)NDEG*(QC*al*loss+PC*S*prodm),('compression',i) def leaf(B,E,Fan,de,df,node): sign,V,h=node assert sign in (-1,1) and all(len(row)==3 and all(type(v) is int and abs(v)0 and x*y-z*z>HP*HP N=projection(V) data=apply_all([(a,np.full(N.shape[0],1+NDEG*d,dtype=np.int64)) for a,d in ((B,0),(E,de),(Fan,df))],N,U) lo,hi=enclosed(data) compression(data,np.array(h,dtype=np.int64),lo,hi) dual(data,sign,lo,hi) def check(family,path=None): # The covariance volume bound gives d>17/23 and normalized radius <3/20. assert 30*F(951057,10**6)/(2+F(309016,10**6))F(17,23) start=time.monotonic();box=DOMAINS[family];B,E,Fan=raw_tables(box) path=path or Path(__file__).with_name(f'metric_{family}.json') path = Path(path) tree = json.loads(path.read_text(encoding="ascii")) if isinstance(tree, dict): if (set(tree) != {"split_axis", "subtrees"} or type(tree["split_axis"]) is not int or tree["subtrees"] != ["metric_u_three_quarters_left.json", "metric_u_three_quarters_right.json"]): raise ValueError("Invalid split metric tree index") left, right = (json.loads((path.parent / name).read_text(encoding="ascii")) for name in tree["subtrees"]) tree = [tree["split_axis"], left, right] trials=exclusions=depthmax=0 def walk(node,t,u,box,de,df,depth): nonlocal trials,exclusions,depthmax depthmax=max(depthmax,depth) if node==0: assert geometry_impossible(box) exclusions+=1;return assert isinstance(node,list) and len(node)==3 if isinstance(node[1],list) and len(node[1])==2: leaf(B,t,u,de,df,node);trials+=1 if trials%10000==0:print('checked',family,trials,'seconds',round(time.monotonic()-start,2),flush=True) return k,left,right=node;assert type(k) is int and 0<=k<4 a,b=box[k];m=(a+b)/2;bl=box.copy();br=box.copy();bl[k]=(a,m);br[k]=(m,b) if k<2: x,y=half(t,k);walk(left,x,u,bl,de+1,df,depth+1);walk(right,y,u,br,de+1,df,depth+1) else: x,y=half(u,k-2);walk(left,t,x,bl,de,df+1,depth+1);walk(right,t,y,br,de,df+1,depth+1) walk(tree,E,Fan,box,0,0,0) print('PASS',family,'trials',trials,'geometric exclusions',exclusions, 'maximum depth',depthmax,'seconds',round(time.monotonic()-start,2),flush=True) if __name__=='__main__': p=argparse.ArgumentParser();p.add_argument('family',choices=DOMAINS);p.add_argument('--file') args=p.parse_args();check(args.family,args.file)