check_residue_selectors.py

"""Finite exact-arithmetic oracle audit; Python arithmetic is not a native operation."""
from itertools import product
import json

stats=dict(prefixes=0,sequences=0,variance_cases=0,query_answers=0,collisions=0)
def oracle(cs,m):
    groups=[[c for c in cs if c%m==r] for r in range(m)]
    return [(len(g),sum(g),sum(c*c for c in g)) for g in groups]
def variance(buckets):return sum(n*q-s*s for n,s,q in buckets)
def move(bs,c,m,new=False):
    bs=list(bs)
    if not new:
        r=c%m;n,s,q=bs[r];bs[r]=(n-1,s-c,q-c*c)
    y=c+1;r=y%m;n,s,q=bs[r];bs[r]=(n+1,s+y,q+y*y)
    return bs
for m in (2,3,5):
    for length in range(7):
        for seq in product(range(3),repeat=length):
            counts={};bs=[(0,0,0)]*m;old=[]
            for row in seq:
                c=counts.get(row,0);old.append((tuple(bs),tuple(counts.values())))
                bs=move(bs,c,m,row not in counts);counts[row]=c+1
                assert bs==oracle(counts.values(),m)
                for n,s,q in bs:assert n*q-s*s>=0
                stats['prefixes']+=1
            for b,cs in old:assert list(b)==oracle(cs,m)
            assert (variance(bs)==0)==all(len(set(c for c in counts.values() if c%m==r))<=1 for r in range(m))
            stats['sequences']+=1
# Radial rows on lengths1..4, with arbitrary repeated/missing left names.
profiles=[frozenset(i+1 for i in range(4) if mask>>i&1) for mask in range(1,16)]
for rowprofiles in product(profiles,repeat=3):
    counts=[sum(2**n for n in p) for p in rowprofiles]
    for m in (3,5):
        bs=oracle(counts,m);gate=variance(bs)==0 and sum(n>0 for n,s,q in bs)<=2
        expected=len(set(rowprofiles))<=2 and all(counts[i]%m!=counts[j]%m or rowprofiles[i]==rowprofiles[j] for i in range(3) for j in range(3))
        assert gate==expected;stats['variance_cases']+=1
        if gate:
            for selected in range(16):
                slots={}
                for v in range(4):
                    if selected>>v&1 and v<3:slots.setdefault(counts[v]%m,rowprofiles[v])
                for n in range(1,6):
                    a=any(n in p for p in slots.values())
                    b=any(selected>>v&1 and n in rowprofiles[v] for v in range(3))
                    assert a==b;stats['query_answers']+=1
# Every tested fixed finite modulus menu collides on two distinct complete levels.
for mods in ((3,),(3,5),(2,3,5,7),(4,9,11)):
    seen={}
    for n in range(1,10000):
        sig=tuple(pow(2,n,m) for m in mods)
        if sig in seen:
            a=seen[sig];assert a!=n
            for m in mods:
                assert variance(oracle((2**a,2**n),m))>0
            stats['collisions']+=1;break
        seen[sig]=n
    else:raise AssertionError('collision missing')
# Variance is not monotone, even on legal literal cardinality increments.
trace=[variance(oracle(cs,3)) for cs in ((1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4))]
assert trace==[0,0,0,9,0,0,0]
stats['variance_trace']=trace
stats['native_arithmetic_evidence']=False
print(json.dumps(stats,sort_keys=True))