verify_sparse_dependencies.py

"""Finite extremal checks and packing certificates, not an asymptotic proof."""
from itertools import combinations
from collections import Counter
import random
import json

def xor(values):
    out = 0
    for x in values:
        out ^= x
    return out

def short_zero(columns, active):
    singles = {}
    for i in active:
        c = columns[i]
        if c == 0:
            return (i,)
        if c in singles:
            return (singles[c], i)
        singles[c] = i
    pairs = {}
    for i, j in combinations(active, 2):
        value = columns[i] ^ columns[j]
        if value in singles:
            return (i, j, singles[value])
        if value in pairs:
            a, b = pairs[value]
            if len({a,b,i,j}) == 4:
                return (a,b,i,j)
        else:
            pairs[value] = (i,j)
    return None

def certificate(n, columns):
    active = list(range(len(columns)))
    groups = []
    while (group := short_zero(columns, active)) is not None:
        assert 1 <= len(group) <= 4 and xor(columns[i] for i in group) == 0
        groups.append(group)
        active = [i for i in active if i not in group]
    used = [i for g in groups for i in g]
    assert len(set(used)) == len(used)
    assert len(used) + len(active) == len(columns)
    residual = [columns[i] for i in active]
    assert len(set(residual)) == len(residual) and 0 not in residual
    triples = [x for x in residual if x.bit_count() == 3]
    degrees = Counter()
    for x in triples:
        for i,j in combinations([i for i in range(n) if x >> i & 1], 2):
            degrees[i,j] += 1
    C = n*(n-1)//2
    assert sum(v*(v-1)//2 for v in degrees.values()) <= C
    assert 3*len(triples) <= 2*C
    assert len(active) <= n+C+(2*C)//3
    assert 24*len(groups) >= n*(n+5)
    return {"n":n,"S":len(columns),"groups":groups,
            "remaining_indices":active,"remaining_triples":len(triples)}

# Independently enumerate all triple families on at most five vertices.
extremal = []
for n in range(3,6):
    triples = [sum(1 << i for i in c) for c in combinations(range(n),3)]
    forbidden = [sum(1 << j for j in c) for c in combinations(range(len(triples)),4)
                 if xor(triples[j] for j in c) == 0]
    maximum = max(mask.bit_count() for mask in range(1 << len(triples))
                  if not any(mask & f == f for f in forbidden))
    assert maximum <= (2*(n*(n-1)//2))//3
    extremal.append({"n":n,"maximum_four_sum_free_triples":maximum,
                     "families_examined":1 << len(triples)})

rng = random.Random(50)
certificates = []
for n in [2,3,4,8,16,32]:
    pool = [sum(1 << i for i in c) for w in [1,2,3]
            for c in combinations(range(n),w)]
    # Unit columns certify full row rank. Remaining columns may repeat.
    columns = [1 << i for i in range(n)] + [rng.choice(pool) for _ in range(n*n)]
    result = certificate(n, columns)
    result["columns"] = columns
    certificates.append(result)

print(json.dumps({"scope":"Small exhaustive triple families and six concrete generator packing certificates only. No formal verification or check of asymptotic degree-four existence.",
                  "triple_extrema":extremal,"packing_certificates":certificates},indent=2))