"""Independent checks for Estrada indices -- numberdb.org/T545. Run `sage -python checks.py`; add --stored to check the live draft too. The stored check needs NUMBERDB_API_KEY while T545 is private. All input files named here are attached to the table. No database writes occur. Independent algorithm: decode graph6 directly, count walks by integer dynamic programming, and sum their traces divided by factorials over QQ. For maximum degree d, trace(A^k) <= n*d^k. After degree N the positive tail is at most n*d^(N+1)/(N+1)! / (1-d/(N+2)), when N+2>d. This geometric bound, exact over QQ, uses neither eigenvalues nor a matrix exponential. Controls test K2, K3, and an edgeless graph before the census. Each 100-digit stored interval must contain the entire independently certified enclosure, not just its midpoint. """ import json import math import os from pathlib import Path import sys from collections import Counter from fractions import Fraction import numberdb.sage as numberdb from sage.rings.integer_ring import ZZ from sage.rings.rational_field import QQ from sage.rings.real_arb import RealBallField from sage.rings.real_mpfi import RealIntervalField from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing from sage.graphs.graph import Graph from sage.graphs.graph_generators import graphs from sage.env import SAGE_VERSION from numberdb._write import to_text from check import exactness, measure, names_its_rings, agrees_with from generate import EstradaIndices, graph_keys, named_graphs, canonical_key, estrada HERE = Path(__file__).resolve().parent RIF = RealIntervalField(500) B = RealBallField(500) def rational_text(s): f = Fraction(s) return QQ(f.numerator) / QQ(f.denominator) def decimal_interval(s): mantissa, _, exponent = s.lower().partition('e') places = len(mantissa.partition('.')[2]) unit = QQ(10) ** (int(exponent or 0) - places) center = rational_text(s) return center - unit, center + unit def adjacency(key): """Direct graph6 decoder for the selected orders, per McKay's specification.""" n = ord(key[0]) - 63 assert 0 <= n <= 62 bits = [] for ch in key[1:]: value = ord(ch) - 63 assert 0 <= value < 64 bits.extend((value >> j) & 1 for j in range(5, -1, -1)) a = [[0] * n for _ in range(n)] pos = 0 for j in range(1, n): for i in range(j): a[i][j] = a[j][i] = bits[pos] pos += 1 return a def walk_interval(key, digits=120): a = adjacency(key) n = len(a) d = max(map(sum, a), default=0) if d == 0: return QQ(n), QQ(n), 0 power = [[int(i == j) for j in range(n)] for i in range(n)] total = QQ(n) factorial = ZZ(1) threshold = QQ(1) / ZZ(10)**digits for k in range(1, 1000): power = [[sum(power[i][v] * a[v][j] for v in range(n)) for j in range(n)] for i in range(n)] factorial *= k trace = sum(power[i][i] for i in range(n)) total += QQ(trace) / factorial if k + 2 <= d: continue bound = QQ(n * ZZ(d)**(k + 1)) / (factorial * (k + 1)) bound /= 1 - QQ(d) / (k + 2) if bound < threshold: return total, total + bound, k raise ArithmeticError('Tail failed to converge') def tight_overlap(value, other): left, right = RIF(value), RIF(other) assert left.is_NaN() is False and right.is_NaN() is False assert left.absolute_diameter() < QQ(1) / ZZ(10)**110 assert right.absolute_diameter() < QQ(1) / ZZ(10)**110 assert left.overlaps(right) def contains_written(text, lo, hi): lower, upper = decimal_interval(text) assert lower <= lo <= hi <= upper, 'Independent enclosure escapes stored decimal' def number_of(entry): return entry['number'] if isinstance(entry, dict) else entry def run(stored=False): controls = [] for key, expected in [('A_', B(1).exp()+B(-1).exp()), ('Bw', B(2).exp()+2*B(-1).exp()), ('B?', B(3))]: lo, hi, terms = walk_interval(key) tight_overlap(RIF(lo, hi), expected) assert not RIF(lo, hi).overlaps(RIF(expected + 1)) controls.append({'g':key, 'terms':terms, 'passed':True}) keys = graph_keys() assert len(keys) == 142 census = Counter(ord(g[0]) - 63 for g in keys) assert dict(census) == {2:1,3:2,4:6,5:21,6:112} for n in census: records = (HERE / f'graph{n}c.g6').read_text().splitlines() independent = {canonical_key(Graph(s, format='graph6')) for s in records} assert independent == {g for g in keys if ord(g[0])-63 == n} corpus = json.loads((HERE / 'corpus-reference.json').read_text()) for tid, entries in corpus.items(): assert set(entries) == set(keys), tid polynomials = {} R = PolynomialRing(ZZ, 'x') for key in keys: g = Graph(key, format='graph6') assert canonical_key(g) == key assert adjacency(key) == [list(row) for row in g.adjacency_matrix()] polynomials[key] = g.adjacency_matrix().charpoly('x') assert not agrees_with(polynomials, lambda key: R(number_of(corpus['T237'][key]))) generator = EstradaIndices() values = {p['g']: generator.value(p, 100) for p in generator.enumerate()} assert not exactness(values) assert not names_its_rings(str(HERE/'generate.py')) live = numberdb.table('T545')['Numbers'] if stored else None if live is not None: assert list(live) == list(keys) evidence = [] for key in keys: value = values[key]['number'] text = to_text(value, 100) lo, hi, terms = walk_interval(key) tight_overlap(value, RIF(lo, hi)) contains_written(text, lo, hi) spectral = RIF(value) contains_written(text, spectral.lower().exact_rational(), spectral.upper().exact_rational()) if live is not None: text = number_of(live[key]) contains_written(text, lo, hi) contains_written(text, spectral.lower().exact_rational(), spectral.upper().exact_rational()) assert (live[key].get('comment') if isinstance(live[key],dict) else None) == values[key].get('comment') evidence.append({'g':key, 'number':text, 'polynomial':str(polynomials[key]), 'walk_terms':terms, 'walk_enclosure':to_text(RIF(lo,hi),115), 'spectral_accuracy_bits':int(value.accuracy()), 'working_precision_bits':int(value.parent().precision())}) formulas = Counter() for n in range(2,7): key = canonical_key(graphs.CompleteGraph(n)) tight_overlap(estrada(key),B(n-1).exp()+(n-1)*B(-1).exp()) formulas['complete'] += 1 for a in range(1,n//2+1): b = n-a key = canonical_key(graphs.CompleteBipartiteGraph(a,b)) tight_overlap(estrada(key),B(a*b).sqrt().cosh()*2+n-2) formulas['complete_bipartite'] += 1 # Test the proposed spectral closed forms against live values as well. if live is not None: for n in range(2,7): k = canonical_key(graphs.CompleteGraph(n)); v=RIF(B(n-1).exp()+(n-1)*B(-1).exp()) contains_written(number_of(live[k]),v.lower().exact_rational(),v.upper().exact_rational()) for a in range(1,n//2+1): k = canonical_key(graphs.CompleteBipartiteGraph(a,n-a));v=RIF(B(a*(n-a)).sqrt().cosh()*2+n-2) contains_written(number_of(live[k]),v.lower().exact_rational(),v.upper().exact_rational()) summary = {'table':'T545','stored':stored,'sage':SAGE_VERSION,'numberdb':numberdb.__version__, 'skill_manifest':'agents/runs/20261027T103803Z-build-skills/manifest.json', 'skill_sha256':'e37efb7e2ededf6c1d7134c673f152f648f26e0267c556aebdf3ec65765d8b4c', 'controls':controls,'counts':dict(census),'corpus_keys_checked':list(corpus), 'rows_checked':len(evidence),'named_rows':len(named_graphs()), 'formulas':dict(formulas),'measure':measure(values), 'min_accuracy_bits':min(x['spectral_accuracy_bits'] for x in evidence), 'max_walk_terms':max(x['walk_terms'] for x in evidence), 'longest_stored_number':max(len(x['number']) for x in evidence), 'entries':evidence} print(json.dumps(summary,indent=2)) if __name__ == '__main__': if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1': key=sys.stdin.read().strip() if '=' in key and key.split('=',1)[0].isidentifier():key=key.split('=',1)[1].strip().strip('\"\'') numberdb.configure(api_key=key) run(stored='--stored' in sys.argv or os.environ.get('NUMBERDB_KEY_FROM_STDIN')=='1')