advice-score-check.py

#!/usr/bin/env python3
"""Finite identity checks only; asymptotic claims use the accompanying proof."""
import json
from fractions import Fraction
from itertools import product

def words(gs):
    c=[0]
    for g in gs:c += [x^g for x in c]
    return c
quadrant_checks=0
for size in range(1,4):
    full=(1<<(size*size))-1
    for b in range(1<<(size*size)):
        m=b.bit_count(); total_s=total_t=total_z2=0
        for u,v in product(range(1<<size),repeat=2):
            masks=[]
            for uu,vv in ((u,v),(u,((1<<size)-1)^v),(((1<<size)-1)^u,v),(((1<<size)-1)^u,((1<<size)-1)^v)):
                masks.append(sum(1<<(i*size+j) for i in range(size) for j in range(size) if uu>>i&1 and vv>>j&1))
            a,bb,c,d=[(b&q).bit_count() for q in masks]
            z=a-bb-c+d
            t=sum(max(0,2*x-m) for x in (a,bb,c,d))
            assert t<=abs(z)
            total_s+=max(0,2*a-m); total_t+=t; total_z2+=z*z
            quadrant_checks+=1
        assert total_t==4*total_s
        assert total_z2==m*(1<<(2*size))
k=2;r=2**k;n=k*r
G=[sum(1<<(i*n+j) for i in range(a*k,(a+1)*k) for j in range(n)) for a in range(r)]
P=[1<<(i*n) for a in range(r) for i in range(a*k,a*k+k-1)]
results={}
for padded in (False,True):
    E=words(G+(P if padded else []))
    C=words([G[0]^g for g in G[1:]]+(P if padded else []))
    Ew=[(b,b.bit_count()) for b in E];Cw=[(b,b.bit_count()) for b in C]
    total_gap=totalE=totalC=0;checked=0
    for u,v in product(range(1<<n),repeat=2):
        q=sum(1<<(i*n+j) for i in range(n) for j in range(n) if u>>i&1 and v>>j&1)
        e=max(2*(q&b).bit_count()-w for b,w in Ew)
        c=max(2*(q&b).bit_count()-w for b,w in Cw)
        co=[]
        for a,g in enumerate(G):
            if padded:
                g ^= sum(P[a*(k-1):(a+1)*(k-1)])
            co.append(2*(q&g).bit_count()-g.bit_count())
        predicted=min(map(abs,co)) if sum(x>0 for x in co)%2 else 0
        assert e-c==predicted,(u,v,e,c,co)
        A=2*v.bit_count()-n
        M=sum(sum(u>>i&1 for i in range(a*k,(a+1)*k))==k for a in range(r))
        if abs(A)<=n/(4*k if padded else 2*k):
            g=k*A-(k-1)*(2*(v&1)-1) if padded else k*A
            assert e-c==max(0,g)*(M%2)
            checked+=1
        total_gap+=e-c;totalE+=e;totalC+=c
    results['padded' if padded else 'simple']={'n':n,'k':k,'queries':1<<(2*n),'E_dim':len(E).bit_length()-1,'C_dim':len(C).bit_length()-1,'F_E':str(Fraction(totalE,1<<(2*n))),'F_C':str(Fraction(totalC,1<<(2*n))),'increment':str(Fraction(total_gap,1<<(2*n))),'central_queries':checked}
print(json.dumps({'quadrant_identity_checks':quadrant_checks,'increments':results},indent=2))