back to table · edit · history · where entries came from · files · download
7951 bytes, as of the version from 2026-10-28 11:14 (current). Recorded here, not run.
"""Independent checks for numberdb.org/T579; run: sage -python checks.py.
The expected values are computed WITHOUT importing generator arithmetic:
Z_M(t)=sum_F t^rk(F) P_(M/F)(t) is palindromic of degree rk(M)
(Proudfoot-Xu-Young, Proposition 2.3, arXiv:1706.05575). For each actual
upper flat interval we recover low KL coefficients from the high coefficients
of Z. This uses no characteristic or Mobius polynomial. Named-object flats
are independently enumerated by testing the rank of every subset and every
single-element extension, not by the generator's flats() method.
EPW Appendix A supplies 15 independently published polynomial comparisons.
Pass --stored to check the authenticated live draft as well; set
NUMBERDB_API_KEY, or pipe a key with NUMBERDB_KEY_FROM_STDIN=1.
"""
import json
import os
import re
import sys
import time
from itertools import combinations
from functools import lru_cache
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.matroids.database_matroids import (Uniform, CompleteGraphic, R10,
TicTacToe, K5dual, Fano)
S = PolynomialRing(ZZ, 't')
u = S.gen()
constructors = {'R10': R10, 'TicTacToe': TicTacToe, 'K5dual': K5dual}
def expected_selection():
rows = [(r, r+c, 'U(%d,%d)' % (r, r+c))
for r in (5, 6, 7, 8) for c in (1, 2, 3, 4)]
rows.extend([(5, 15, 'K(6)'), (6, 21, 'K(7)'), (7, 28, 'K(8)'),
(5, 10, 'R10'), (5, 9, 'TicTacToe'), (6, 10, 'K5dual')])
return [key for r, n, key in sorted(rows)]
def object_of(key):
if key.startswith('U('):
r, n = map(int, key[2:-1].split(','))
return Uniform(r, n)
if key.startswith('K('):
return CompleteGraphic(int(key[2:-1]))
return constructors[key]()
def ranked_flats(m, exhaustive=False):
ground = sorted(m.groundset(), key=str)
positions = {e: i for i, e in enumerate(ground)}
data = []
if exhaustive:
for mask in range(1 << len(ground)):
subset = [e for i, e in enumerate(ground) if (mask >> i) & 1]
rank = int(m.rank(subset))
if all(m.rank(subset+[e]) > rank
for i, e in enumerate(ground) if not ((mask >> i) & 1)):
data.append((rank, mask))
else:
for rank in range(m.rank()+1):
for flat in m.flats(rank):
data.append((int(rank), sum(1 << positions[e] for e in flat)))
data.sort()
assert data[0] == (0, 0)
assert data[-1] == (m.rank(), (1 << len(ground))-1)
return data
def from_z_symmetry(data):
top_rank = data[-1][0]
polynomials = {}
for rank_a, mask_a in reversed(data):
d = top_rank-rank_a
if d == 0:
polynomials[mask_a] = [1]
continue
total = [0]*(d+1)
for rank_b, mask_b in data:
if rank_b <= rank_a or mask_a & mask_b != mask_a:
continue
shift = rank_b-rank_a
for j, c in enumerate(polynomials[mask_b]):
total[shift+j] += c
p = [total[d-i]-total[i] for i in range((d+1)//2)]
z = total[:]
for i, c in enumerate(p):
z[i] += c
assert z == z[::-1]
assert p[0] == 1
polynomials[mask_a] = p
return S(polynomials[0])
@lru_cache(None)
def independent(key):
m = object_of(key)
assert m.is_simple()
return from_z_symmetry(ranked_flats(m, exhaustive=key in constructors))
# EPW Appendix A.1: M_(corank,rank) = U_(rank,rank+corank).
# Each tuple lists the coefficients of 1,t,t^2,t^3 in that order.
PUBLISHED = {
'U(5,6)': [1, 9, 5], 'U(6,7)': [1, 14, 21],
'U(7,8)': [1, 20, 56, 14], 'U(8,9)': [1, 27, 120, 84],
'U(5,7)': [1, 28, 21], 'U(6,8)': [1, 48, 98],
'U(7,9)': [1, 75, 288, 84], 'U(8,10)': [1, 110, 675, 552],
'U(5,8)': [1, 62, 56], 'U(6,9)': [1, 117, 288],
'U(7,10)': [1, 200, 927, 300], 'U(8,11)': [1, 319, 2365, 2145],
'K(6)': [1, 16, 15], 'K(7)': [1, 42, 175],
'K(8)': [1, 99, 1225, 735],
}
def run(stored=False):
start = time.monotonic()
controls = [('boolean', Uniform(4, 4), S.one()),
('circuit', Uniform(3, 4), 1+2*u),
('braid', CompleteGraphic(4), 1+u),
('Fano', Fano(), S.one())]
for label, m, known in controls:
assert from_z_symmetry(ranked_flats(m, exhaustive=True)) == known
print('Four known-value controls passed before comparisons.', flush=True)
# The import occurs only after the independent algorithm and controls.
from generate import MatroidKazhdanLusztig, polynomial, lattice_kl
from check import exactness, measure, names_its_rings, agrees_with
g = MatroidKazhdanLusztig()
keys = expected_selection()
assert [row['matroid'] for row in g.enumerate()] == keys
values = {key: polynomial(key) for key in keys}
assert not exactness(values)
assert not names_its_rings(os.path.join(os.path.dirname(__file__), 'generate.py'))
for key in keys:
before = time.monotonic()
alternative = independent(key)
assert values[key] == alternative, (key, values[key], alternative)
m = object_of(key)
assert values[key][0] == 1 and 2*values[key].degree() < m.rank()
assert all(c >= 0 for c in values[key].list())
assert values[key][1] == len(m.flats(m.rank()-1))-len(m.flats(1))
print(key, str(values[key]), 'independent seconds', round(time.monotonic()-before, 3), flush=True)
assert not agrees_with(values, independent)
for key, coefficients in PUBLISHED.items():
assert values[key] == S(coefficients), key
# Check the general implementation against known controls as well.
for label, m, known in controls:
assert lattice_kl(m) == known
assert independent('U(5,6)') != values['U(5,6)']+u**2
report = {'table':'T579', 'entries':len(keys), 'known_controls':4,
'z_symmetry_comparisons':len(keys), 'published_comparisons':len(PUBLISHED),
'constant_degree_positivity_linear_checks':len(keys),
'corruption_control':True, 'measurement':measure(values),
'values':{k:str(v) for k,v in values.items()},
'skill_manifest':'agents/runs/20261028T110020Z-build-skills/manifest.json',
'skill_local_sha256':'e37efb7e2ededf6c1d7134c673f152f648f26e0267c556aebdf3ec65765d8b4c',
'skill_live_sha256':'e37efb7e2ededf6c1d7134c673f152f648f26e0267c556aebdf3ec65765d8b4c'}
if stored:
if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
key = sys.stdin.read().strip()
if re.match(r'^[A-Z_][A-Z0-9_]*\s*=',key):
key=key.split('=',1)[1].strip().strip('\"\'')
os.environ['NUMBERDB_API_KEY'] = key
document=numberdb.table('T579')
entries=document['Numbers']
if isinstance(entries,dict):
readback={k:S(v['number'] if isinstance(v,dict) else v)
for k,v in entries.items()}
else:
readback={v['params']['matroid']:S(v['number']) for v in entries}
assert list(readback) == keys
assert not agrees_with(readback,independent)
for k in keys:
m=object_of(k)
assert readback[k][0] == 1 and 2*readback[k].degree() < m.rank()
assert readback[k][1] == len(m.flats(m.rank()-1))-m.size()
verification=g.verify(sample=None)
assert verification.ok
print(verification,flush=True)
report['stored_comparisons']=len(readback)
report['generator_verify']=str(verification)
report['seconds']=round(time.monotonic()-start,3)
print('RESULT_JSON '+json.dumps(report),flush=True)
return report
if __name__ == '__main__':
run(stored='--stored' in sys.argv or os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1')