back to table · edit · history · where entries came from · files · download
8772 bytes, as of the version from 2026-10-27 11:08 (current). Recorded here, not run.
"""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')