"""Independent exact checks for numberdb.org/T537. Run: sage -python checks.py Read back and check stored values: sage -python checks.py --stored Private draft reads require NUMBERDB_API_KEY. NUMBERDB_KEY_FROM_STDIN=1 is supported for the campaign wrapper. This script never writes to NumberDB. The checker decodes graph6 directly, computes all distances by Floyd-Warshall, and expands det(xI-D) over permutations, sharing neither the generator's Sage graph decoder, shortest-path routine, nor its characteristic-polynomial code. Known K2 and P3 controls precede the full comparison. Further checks include Graham-Pollak's tree determinant, complete graphs, complete bipartite graphs, coefficient identities, real roots, and independent stored adjacency/Fiedler polynomials. McKay's downloaded catalogues certify the selected isomorphism classes after explicit Sage canonicalization. """ import json import os from pathlib import Path import sys from collections import Counter from itertools import permutations from fractions import Fraction from decimal import Decimal import numberdb.sage as numberdb from sage.graphs.graph import Graph from sage.rings.integer_ring import ZZ from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing from sage.rings.qqbar import AA from sage.rings.rational_field import QQ from check import exactness, agrees_with, measure, names_its_rings from generate import DistancePolynomials HERE = Path(__file__).resolve().parent R = PolynomialRing(ZZ, 'x') x = R.gen() def decode(key): n = ord(key[0]) - 63 assert 2 <= n <= 6 bits = [(ord(ch) - 63) >> shift & 1 for ch in key[1:] for shift in range(5, -1, -1)] assert len(bits) >= n*(n-1)//2 a = [[0]*n for _ in range(n)] k = 0 for j in range(1, n): for i in range(j): a[i][j] = a[j][i] = bits[k] k += 1 return a def distances(a): n = len(a) d = [[0 if i == j else (1 if a[i][j] else n+1) for j in range(n)] for i in range(n)] for k in range(n): for i in range(n): for j in range(n): d[i][j] = min(d[i][j], d[i][k] + d[k][j]) assert all(d[i][j] < n for i in range(n) for j in range(n)) return d def direct_polynomial(d): n = len(d) total = R.zero() for perm in permutations(range(n)): inversions = sum(perm[i] > perm[j] for i in range(n) for j in range(i+1, n)) term = R((-1)**inversions) for i, j in enumerate(perm): term *= x - d[i][j] if i == j else -d[i][j] total += term return total def number(entry): return entry['number'] if isinstance(entry, dict) else entry def validate(values): assert direct_polynomial([[0, 1], [1, 0]]) == x**2-1 assert direct_polynomial([[0, 1, 2], [1, 0, 1], [2, 1, 0]]) == x**3-6*x-4 assert decode('A_') == [[0, 1], [1, 0]] assert distances(decode('BW')) == [[0, 2, 1], [2, 0, 1], [1, 1, 0]] assert not exactness(values) assert not names_its_rings(str(HERE/'generate.py')) disagreements = agrees_with(values, lambda key: direct_polynomial(distances(decode(key)))) assert not disagreements, disagreements[:5] reference = json.loads((HERE/'reference-values.json').read_text()) selected = json.loads((HERE/'selected-graphs.json').read_text()) keys = [r['g'] for r in selected] assert list(values) == keys == sorted(keys, key=lambda k: (ord(k[0]), k)) assert set(keys) == set(reference['adjacency']) == set(reference['laplacian_keys']) counts = Counter(ord(k[0])-63 for k in keys) assert counts == {2:1, 3:2, 4:6, 5:21, 6:112} catalog = set() for n in range(2, 7): raw = (HERE/f'graph{n}c.g6').read_text().splitlines() assert len(raw) == counts[n] canonical = {Graph(k, format='graph6').canonical_label(algorithm='sage').graph6_string() for k in raw} assert len(canonical) == counts[n] assert canonical == {k for k in keys if ord(k[0])-63 == n} catalog.update(canonical) assert catalog == set(keys) checks = Counter() multiple_positive = [] for key, p in values.items(): a = decode(key); d = distances(a); n = len(a) graph = Graph(key, format='graph6') assert graph.canonical_label(algorithm='sage').graph6_string() == key assert graph.is_connected() and graph.order() == n assert p.degree() == n and p[n] == 1 and p[n-1] == 0 assert p[n-2] == -sum(d[i][j]**2 for j in range(n) for i in range(j)) if n >= 3: assert p[n-3] == -2*sum(d[i][j]*d[j][k]*d[k][i] for k in range(n) for j in range(k) for i in range(j)) checks['coefficient_identities'] += 1 roots = p.roots(ring=AA) assert sum(int(m) for r,m in roots) == n checks['all_roots_real'] += 1 radius_text = number(reference['distance_radius'][key]) largest = max(root for root, multiplicity in roots) if '.' not in radius_text and 'e' not in radius_text.lower(): assert largest == ZZ(radius_text) else: decimal = Decimal(radius_text) center = Fraction(decimal) unit = Fraction(10) ** decimal.as_tuple().exponent low, high = center-unit, center+unit assert QQ(low.numerator)/QQ(low.denominator) <= largest assert largest <= QQ(high.numerator)/QQ(high.denominator) checks['distance_radius_table'] += 1 if sum(int(m) for r,m in roots if r>0)>1: multiple_positive.append(key) degrees = [sum(row) for row in a] edges = sum(degrees)//2 if edges == n-1: assert p[0] == -(n-1)*2**(n-2) assert sum(int(m) for r,m in roots if r>0)==1 assert sum(int(m) for r,m in roots if r<0)==n-1 checks['tree_determinant_and_inertia'] += 1 if edges == n*(n-1)//2: assert p == (x-(n-1))*(x+1)**(n-1) assert p == R(number(reference['adjacency'][key])) checks['complete_graph'] += 1 # An independent bipartition traversal detects every complete bipartite graph. color={0:0}; todo=[0]; bipartite=True while todo: i=todo.pop() for j in range(n): if not a[i][j]: continue if j not in color: color[j]=1-color[i];todo.append(j) elif color[j]==color[i]: bipartite=False if bipartite: left=sum(c==0 for c in color.values());right=n-left if edges == left*right: expected=(x+2)**(n-2)*((x-2*(left-1))*(x-2*(right-1))-left*right) assert p==expected checks['complete_bipartite'] += 1 if len(set(degrees))==1 and max(map(max,d))<=2: degree=degrees[0];adj=R(number(reference['adjacency'][key])) q,rem=adj.quo_rem(x-degree); assert rem==0 assert p==(x-(2*n-2-degree))*(-1)**(n-1)*q(-x-2) checks['regular_diameter_at_most_two_adjacency_relation'] += 1 if edges==n-1 and max(degrees)<=2: assert p==R(number(reference['fiedler'][str(n)])) checks['path_fiedler_table'] += 1 transmissions=[sum(row) for row in d] if len(set(transmissions))==1: assert p(transmissions[0])==0 checks['constant_transmission_root'] += 1 return {'status':'pass','entries':len(values),'counts_by_order':dict(counts), 'controls':['K2 determinant x^2-1','P3 determinant x^3-6*x-4','graph6 A_ and BW'], 'independent_determinant_matches':len(values),'mckay_census_matches':len(catalog), 'canonical_identity_matches':len(keys),'checks':dict(checks), 'graphs_with_multiple_positive_roots':multiple_positive, 'measurement':measure(values)} if __name__ == '__main__': if os.environ.get('NUMBERDB_KEY_FROM_STDIN')=='1': os.environ['NUMBERDB_API_KEY']=sys.stdin.read().strip() if '--stored' in sys.argv or os.environ.get('CHECK_STORED')=='1': document=numberdb.table('T537') values={key:R(number(v)) for key,v in document['Numbers'].items()} report=validate(values); report['input']='live database T537' else: gen=DistancePolynomials() values={p['g']:gen.value(p,100)['number'] for p in gen.enumerate()} report=validate(values);report['input']='generator' print(json.dumps(report,indent=2,default=str))