check_bounded_omission_basis.py

#!/usr/bin/env python3
"""Finite semantic audit. Set operations and field arithmetic are oracle costs."""
from itertools import combinations, product
import json

counts = dict(sequences=0, prefix_queries=0, selector_failures=0, polynomial_pairs=0)
U = frozenset(range(4))
holes = [frozenset(c) for k in range(3) for c in combinations(U, k)]
rows = [U - h for h in holes]
for seq in product(rows, repeat=4):
    basis, union, truth = [], frozenset(), frozenset()
    for row in seq:
        if not basis or not row <= union:
            basis.append(row)
            union |= row
        assert len(basis) <= 3
        truth |= row
        assert union == truth
        counts['prefix_queries'] += len(U)
        for q in U:
            assert (q in union) == any(q in b for b in basis)
    assert union == frozenset().union(*seq)
    counts['sequences'] += 1
# Every proper selected subset of r+1 distinct tokens can be defeated.
for r in range(1, 7):
    V = frozenset(range(r + 4))
    for k in range(r + 1):
        for chosen in combinations(range(r + 1), k):
            j = next(i for i in range(r + 1) if i not in chosen)
            H = [frozenset((0, i + 1)) if i != j else frozenset((r + 2, r + 3)) for i in range(r + 1)]
            assert len(set(H)) == r + 1
            all_rows = [V - h for h in H]
            assert 0 in frozenset().union(*all_rows)
            assert 0 not in frozenset().union(*(all_rows[i] for i in chosen))
            counts['selector_failures'] += 1
# Characteristic polynomial reconstruction for bounded missing sets in F_17.
p = 17
V = frozenset(range(8))
def poly(H):
    c = [1]
    for a in H:
        d = [0] * (len(c) + 1)
        for i, x in enumerate(c):
            d[i] = (d[i] - a*x) % p
            d[i+1] = (d[i+1] + x) % p
        c = d
    return tuple(c)
def value(c, x):
    z = 0
    for a in reversed(c): z = (z*x + a) % p
    return z
missing = [frozenset(c) for k in range(3) for c in combinations(V,k)]
def e1(S): return sum(S) % p
def e2(S): return sum(a*b for a,b in combinations(S,2)) % p
def gcd(a,b):
    def trim(c):
        while len(c)>1 and c[-1]==0: c.pop()
        return c
    a,b=list(a),list(b)
    while b != [0]:
        c=a[:]
        while c != [0] and len(c)>=len(b):
            shift=len(c)-len(b); factor=c[-1]*pow(b[-1],-1,p)%p
            for i,x in enumerate(b): c[i+shift]=(c[i+shift]-factor*x)%p
            trim(c)
        a,b=b,c
    return tuple(x*pow(a[-1],-1,p)%p for x in a)
for H in missing:
    X = V-H
    h1=(e1(V)-e1(X))%p
    h2=(e2(V)-e2(X)-e1(X)*h1)%p
    assert h1==e1(H) and h2==e2(H)
    for z in (8,9,10):
        assert value(poly(V),z)*pow(value(poly(X),z),-1,p)%p == value(poly(H),z)
    assert frozenset(q for q in V if value(poly(H),q)==0) == H
    for K in missing:
        G=H & K
        assert gcd(poly(H),poly(K)) == poly(G)
        assert (G != H) == bool((V-K) - (V-H))
        counts['polynomial_pairs'] += 1
assert len({poly(H) for H in missing}) == len(missing)
print(json.dumps(counts, sort_keys=True))