back to table · edit · history · where entries came from · files · download
3568 bytes, as of the version from 2026-10-27 04:54 (current). Recorded here, not run.
"""Distance Estrada indices of connected graphs -- numberdb.org/T538.
Install and run with SageMath:
sage -pip install numberdb
sage -python generate.py # verify every stored entry
sage -python generate.py --fill-draft # write entries with NUMBERDB_API_KEY
sage -python checks.py # independent numerical checks
Keep selected-graphs.json beside this file. The default enumeration is every
connected simple graph on two through six vertices, in vertex-count/graph6
order. Its graph6 identities use canonical_label(algorithm='sage').
Integer distance matrices and characteristic polynomials are exact. AA roots
are certified real algebraic numbers, with multiplicities. RealIntervalField
converts each root to an outward-rounded enclosure; Arb exponentiates and sums
those enclosures. The 96 guard bits are measured in numerical-evidence.json.
The method uses the signed eigenvalues without centering or normalization.
The fill command writes the existing draft; it does not offer or publish it.
"""
import json
from functools import lru_cache
import os
from pathlib import Path
import sys
import numberdb.sage as numberdb
from sage.graphs.graph import Graph
from sage.rings.integer_ring import ZZ
from sage.rings.qqbar import AA
from sage.rings.real_arb import RealBallField
from sage.rings.real_mpfi import RealIntervalField
WORKING_GUARD = 96
ROOT = Path(__file__).resolve().parent
def selection():
return json.loads((ROOT / 'selected-graphs.json').read_text())
@lru_cache(maxsize=512)
def distance_data(key):
graph = Graph(key, format='graph6')
if graph.order() < 2 or not graph.is_connected():
raise ValueError('A connected graph on at least two vertices is required')
distance = graph.distance_matrix().change_ring(ZZ)
polynomial = distance.charpoly('x')
roots = polynomial.roots(ring=AA)
assert sum(int(m) for _, m in roots) == graph.order()
return graph, distance, polynomial, roots
@lru_cache(maxsize=512)
def estrada(key, digits=100):
working = numberdb.bits(digits, losing=WORKING_GUARD)
ball = RealBallField(working)
interval = RealIntervalField(working)
_, _, _, roots = distance_data(key)
value = sum((ball(interval(root)).exp() * multiplicity
for root, multiplicity in roots), ball(0))
assert value.is_finite() and value > 0
assert ball(value.rad()) < abs(value) * (ball(10) ** (-(digits + 5)))
return value
class DistanceEstrada(numberdb.Generator):
table = 'T538'
parameters = ('g',)
type = 'R'
digits = 100
rigour = 'proven'
files = ('generate.py', 'selected-graphs.json', 'argument-selection.md',
'checks.py', 'check.py', 'comparison-tables.json',
'numerical-evidence.json', 'skill-evidence.json', 'sources.md')
def enumerate(self):
for row in selection():
yield {'g': row['g']}
def value(self, params, digits):
result = {'number': estrada(params['g'], digits)}
annotation = next((r.get('comment') for r in selection()
if r['g'] == params['g']), None)
if annotation:
result['comment'] = annotation
return result
if __name__ == '__main__':
generator = DistanceEstrada()
if '--fill-draft' in sys.argv:
outcome = generator.publish(message='Fill 142 certified distance Estrada indices')
print(outcome)
else:
report = generator.verify(sample=None)
print(report)
sys.exit(0 if report.ok else 1)