back to table · edit · history · where entries came from · files · download
8203 bytes, as of the version from 2026-10-28 12:16 (current). Recorded here, not run.
"""Independent exact checks for Z-polynomials of matroids, numberdb.org/T580.
sage -python checks.py # compare all locally generated values
sage -python checks.py --stored # compare all entries read from T580
For a private draft, set NUMBERDB_API_KEY or NUMBERDB_KEY_FROM_STDIN=1.
The campaign wrapper can set NUMBERDB_STORED=1 via a wrapper script.
The independent implementation uses the characteristic-polynomial recursion,
not Z-palindromicity. Uniform restrictions are Boolean; braid restrictions are
products indexed by explicitly enumerated set partitions; named matroids use
an independently found flat lattice obtained by testing every ground-set subset.
Known-value controls run first. Dyck path peak counts supply an external
combinatorial check on every circuit-matroid entry.
"""
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.matroids import catalog
from sage.env import SAGE_VERSION
from functools import lru_cache
from collections import Counter
from math import comb
import json
import os
import sys
import time
from pathlib import Path
from check import exactness, measure, agrees_with, names_its_rings
import generate
A = PolynomialRing(ZZ, 't')
x = A.gen()
def reverse(p, degree):
return A([p[degree-i] for i in range(degree+1)])
def solve_epw(s, rank):
"""The high coefficients of t^r P(1/t) determine P uniquely."""
if rank == 0:
return A.one()
p = A([s[rank-i] for i in range((rank+1)//2)])
assert reverse(p, rank) == p+s, (rank, p, s)
return p
@lru_cache(None)
def uniform_epw(r, n):
if r == 0:
return A.one()
chi = sum(((-1)**j * comb(n,j) * x**(r-j) for j in range(r)), A.zero())
chi += (-1)**r * comb(n-1,r-1)
rhs = chi
for j in range(1,r):
rhs += comb(n,j) * (x-1)**j * uniform_epw(r-j,n-j)
return solve_epw(rhs,r)
def uniform_z(r,n):
return x**r + sum((comb(n,j)*x**j*uniform_epw(r-j,n-j)
for j in range(r)),A.zero())
def partitions(n):
"""Restricted growth construction of all set partitions, exactly once."""
if n == 0:
yield ()
return
for p in partitions(n-1):
yield p+((n-1,),)
for i in range(len(p)):
yield p[:i]+(p[i]+(n-1,),)+p[i+1:]
@lru_cache(None)
def block_types(n):
return Counter(tuple(sorted(map(len,p))) for p in partitions(n))
@lru_cache(None)
def braid_epw(m):
if m == 1:
return A.one()
rhs = A.zero()
for sizes, count in block_types(m).items():
k = len(sizes)
if k == m:
continue
chi = A.one()
for size in sizes:
for j in range(1,size):
chi *= x-j
rhs += count * chi * braid_epw(k)
return solve_epw(rhs,m-1)
def braid_z(m):
return sum((count*x**(m-len(sizes))*braid_epw(len(sizes))
for sizes,count in block_types(m).items()),A.zero())
@lru_cache(None)
def named_epw(name):
M = getattr(catalog,name)()
ground = sorted(M.groundset(),key=str)
n = len(ground)
subsets = {mask: [ground[i] for i in range(n) if mask & (1<<i)]
for mask in range(1<<n)}
rank = {mask: int(M.rank(s)) for mask,s in subsets.items()}
flats = [mask for mask in subsets
if all(rank[mask | (1<<i)] > rank[mask]
for i in range(n) if not mask & (1<<i))]
flats.sort(key=lambda f:(rank[f],f))
assert flats[0] == 0
r = rank[(1<<n)-1]
P, Z, chis = {}, {}, {}
for f in reversed(flats):
upper = [g for g in flats if g & f == f]
mu = {f: ZZ.one()}
for g in upper[1:]:
mu[g] = -sum((mu[h] for h in upper if h != g and h & g == h and h in mu),ZZ.zero())
rhs = A.zero()
for g in upper[1:]:
chi = sum((mu[h]*x**(rank[g]-rank[h])
for h in upper if h & g == h),A.zero())
rhs += chi*P[g]
P[f] = solve_epw(rhs,r-rank[f])
Z[f] = sum((x**(rank[g]-rank[f])*P[g] for g in upper),A.zero())
if f == 0:
chis[0] = sum((mu[g]*x**(r-rank[g]) for g in upper),A.zero())
# A second independent characteristic computation uses all subsets.
subset_chi = sum(((-1)**mask.bit_count()*x**(r-rank[mask])
for mask in subsets),A.zero())
assert subset_chi == chis[0]
return P[0],Z[0],{'flats':len(flats),'rank':r,'size':n,
'hyperplanes':sum(rank[f]==r-1 for f in flats),
'characteristic':str(chis[0])}
def independent(key):
if key.startswith('U('):
r,n=map(int,key[2:-1].split(',')); return uniform_z(r,n)
if key.startswith('K('):
return braid_z(int(key[2:-1]))
return named_epw(key)[1]
def dyck_peaks(n):
counts=Counter()
def walk(up,down,last,peaks):
if up == down == n:
counts[peaks] += 1
return
if up < n:
walk(up+1,down,'U',peaks)
if down < up:
walk(up,down+1,'D',peaks+(last=='U'))
walk(0,0,'',0)
return A([counts[k+1] for k in range(n)])
def controls():
assert len(list(partitions(4))) == 15
assert dyck_peaks(3) == 1+3*x+x**2
assert uniform_z(3,3) == (1+x)**3
assert uniform_z(2,4) == 1+4*x+x**2
assert uniform_z(3,4) == 1+6*x+6*x**2+x**3
assert braid_z(4) == 1+7*x+7*x**2+x**3
assert named_epw('Fano')[1] == 1+7*x+7*x**2+x**3
def main(use_stored=False):
start=time.monotonic()
controls()
print('Seven known-answer controls passed.',flush=True)
generator=generate.MatroidZ()
expected_keys=[p['matroid'] for p in generator.enumerate()]
if use_stored:
from numberdb._generate import _stored_entries
values={key:A(value) for key,value in _stored_entries(numberdb.table('T580')).items()}
assert list(values)==expected_keys
else:
values={key:generator.value({'matroid':key},100) for key in expected_keys}
assert len(values)==37
assert not names_its_rings(str(Path(__file__).with_name('generate.py')))
assert not exactness(values)
errors=agrees_with(values,independent)
assert not errors,errors
# Source identity checks on the values under test, including readback mode.
for r,n,key in generate.selection():
z=values[key]
assert z.degree()==r and z[0]==1 and z[r]==1
assert reverse(z,r)==z
assert all(c>=0 for c in z)
if key.startswith('U('):
assert z[1]==comb(n,r-1)
if n==r+1:
assert z==dyck_peaks(r+1)
assert z==A([ZZ(comb(r+1,i)*comb(r+1,i+1))//ZZ(r+1) for i in range(r+1)])
elif key.startswith('K('):
m=int(key[2:-1]); assert z[1]==2**(m-1)-1
else:
assert z[1]==named_epw(key)[2]['hyperplanes']
print(key, str(z),flush=True)
report={'table':'T580','mode':'stored' if use_stored else 'local',
'manifest':'agents/runs/20261028T114049Z-build-skills/manifest.json',
'skill_sha256':'e37efb7e2ededf6c1d7134c673f152f648f26e0267c556aebdf3ec65765d8b4c',
'sage':SAGE_VERSION,'numberdb':numberdb.__version__,
'entries':len(values),'known_answer_controls':7,'independent_coefficients_checked':len(values),
'dyck_path_comparisons':6,'identities':'degree, constant, leading, nonnegativity, symmetry, hyperplane coefficient on all 37; Narayana on all six circuit entries',
'named_objects':{k:named_epw(k)[2] for k in generate.NAMED},
'measure':measure(values),'elapsed_seconds':time.monotonic()-start,
'values':{k:str(v) for k,v in values.items()}}
print('EVIDENCE_JSON='+json.dumps(report,sort_keys=True))
return report
if __name__=='__main__':
if os.environ.get('NUMBERDB_KEY_FROM_STDIN')=='1':
secret=sys.stdin.read().strip()
if '=' in secret and secret.split('=',1)[0].isidentifier():
secret=secret.split('=',1)[1].strip().strip('\"\'')
numberdb.configure(api_key=secret)
main('--stored' in sys.argv or os.environ.get('NUMBERDB_STORED')=='1')