back to table · edit · history · where entries came from · files · download
7931 bytes, as of the version from 2026-10-29 12:06 (current). Recorded here, not run.
"""Independent exact checks for numberdb.org/T608.
sage -python checks.py checks generated values locally.
sage -python checks.py --stored checks authenticated database values instead.
Set NUMBERDB_API_KEY for the private draft, or NUMBERDB_KEY_FROM_STDIN=1.
The graph atlas and edge-matrix characteristic polynomial share no enumeration
or polynomial-computation code with the generator's nauty/Bass construction.
"""
import json
import sys
from pathlib import Path
from collections import Counter, defaultdict
from itertools import combinations
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.matrix.constructor import matrix
from sage.graphs.graph import Graph
from sage.env import SAGE_VERSION
import networkx as nx
from generate import ReciprocalIhara, configure_stdin
from check import exactness, measure, agrees_with, names_its_rings
ROOT = Path(__file__).resolve().parent
R = PolynomialRing(ZZ, 'u')
u = R.gen()
def edge_polynomial(key):
graph = nx.from_graph6_bytes(key.encode('ascii'))
arcs = [(a,b) for a in graph for b in graph[a]]
size = len(arcs)
b = matrix(ZZ, size, size,
[int(v == x and w != y) for w,v in arcs for x,y in arcs])
cp = b.charpoly()
return R([cp[size-k] for k in range(size+1)])
def closed_walk_count(graph, length):
"""Count rooted, oriented reduced closed walks directly in the graph."""
total = 0
def extend(path):
nonlocal total
if len(path)-1 == length:
if path[-1] == path[0] and path[-2] != path[1]:
total += 1
return
for vertex in graph[path[-1]]:
if vertex != path[-2]:
extend(path + [vertex])
if length < 3:
return 0
for start in graph:
for first in graph[start]:
extend([start, first])
return total
def log_counts(poly, limit):
"""Coefficients of -u P'(u)/P(u), by exact convolution."""
counts = [ZZ.zero()]
for k in range(1, limit+1):
counts.append(-k*poly[k]-sum(poly[i]*counts[k-i] for i in range(1,k)))
return counts
def atlas_keys():
keys = []
for graph in nx.graph_atlas_g():
if 3 <= len(graph) <= 6 and nx.is_connected(graph) and min(dict(graph.degree()).values()) >= 2:
key = Graph(graph).canonical_label(algorithm='sage').graph6_string()
keys.append(key)
return keys
def source_diamond():
# Sato (2019), p. 204: explicit factorization of the diamond example.
return (1-u**2)*(1-u)*(1+u**2)*(1+u+2*u**2)*(1-u**2-2*u**3)
def program_control():
# The website Programs snippet uses only an integer characteristic polynomial.
graph = Graph('Bw')
arcs = [(a, b) for a in graph for b in graph.neighbors(a)]
size = len(arcs)
b = matrix(ZZ, size, size,
[int(v == x and w != y) for w, v in arcs for x, y in arcs])
c = b.charpoly()
p = R(list(reversed(c.list())))
assert p == (1-u**3)**2
def run(stored=False):
# Controls run before the general comparisons, including nonzero answers.
for n in (3,4,5,6):
g = nx.cycle_graph(n)
for length in range(1,7):
assert closed_walk_count(g,length) == (2*n if length % n == 0 else 0)
key=nx.to_graph6_bytes(g,header=False).strip().decode()
assert edge_polynomial(key) == (1-u**n)**2
assert edge_polynomial('A_') == 1
assert closed_walk_count(nx.path_graph(3),4) == 0
program_control()
generator = ReciprocalIhara()
params = list(generator.enumerate())
keys = [p['g'] for p in params]
atlas = atlas_keys()
assert len(atlas) == len(set(atlas)) == len(keys) == 76
assert set(atlas) == set(keys)
assert keys == sorted(keys,key=lambda key:(len(nx.from_graph6_bytes(key.encode())),nx.from_graph6_bytes(key.encode()).number_of_edges(),key.encode()))
neighbours=json.loads((ROOT/'neighbor-keys.json').read_text())
overlap={}
for tid, original in neighbours.items():
eligible=[]
for key in original:
g=nx.from_graph6_bytes(key.encode())
if 3 <= len(g) <= 6 and nx.is_connected(g) and min(dict(g.degree()).values()) >= 2:
assert Graph(key).canonical_label(algorithm='sage').graph6_string() == key
eligible.append(key)
assert set(eligible) == set(keys)
overlap[tid]=len(eligible)
comments={}
if stored:
document=numberdb.table('T608')
block=document['Numbers']
assert isinstance(block,dict), 'inspect new API representation before continuing'
assert list(block) == keys
values={k:R(v['number'] if isinstance(v,dict) else v) for k,v in block.items()}
comments={k:v.get('comment') for k,v in block.items() if isinstance(v,dict) and v.get('comment')}
else:
values={}
for p in params:
val=generator.value(p,100)
if isinstance(val,dict):
comments[p['g']]=val['comment'];val=val['number']
values[p['g']]=val
assert not names_its_rings(str(ROOT/'generate.py'))
assert not exactness(values)
disagreements=agrees_with(values,edge_polynomial)
assert not disagreements, disagreements
sizes=Counter(); regular=0; bipartite=0; bridges=[]; groups=defaultdict(list)
for key,poly in values.items():
g=nx.from_graph6_bytes(key.encode())
n,m=len(g),g.number_of_edges()
sizes[n]+=1
degrees=[d for _,d in g.degree()]
regular+=len(set(degrees))==1
bipartite+=nx.is_bipartite(g)
if list(nx.bridges(g)): bridges.append(key)
assert poly[0]==1 and poly[1]==0 and poly[2]==0
assert poly.degree()==2*m
leading=ZZ((-1)**(m-n))
for d in degrees: leading*=d-1
assert poly[2*m]==leading
assert poly(1)==0
counts=log_counts(poly,6)
for k in range(1,7): assert counts[k]==closed_walk_count(g,k),(key,k)
triangles=sum(1 for a,b,c in combinations(g,3) if g.has_edge(a,b) and g.has_edge(a,c) and g.has_edge(b,c))
assert poly[3]==-2*triangles
if all(d==2 for d in degrees): assert poly==(1-u**n)**2
if nx.is_bipartite(g): assert poly(-u)==poly
groups[str(poly)].append(key)
assert values['C^']==source_diamond()
assert sizes==Counter({3:1,4:3,5:11,6:61})
assert len(bridges)==1
# Check that every familiar-name annotation identifies the graph it names.
assert 'barbell' in comments[bridges[0]]
assert 'diamond' in comments['C^']
summary={'table':'T608','mode':'stored' if stored else 'offline',
'skill_manifest':'agents/runs/20261029T113821Z-build-skills/manifest.json',
'skill_sha256':'28ecbeeccb0c5e5d6eb541b5a5b0f88aec47b154374d909085116d34f5629199',
'versions':{'sage':SAGE_VERSION,'networkx':nx.__version__,'numberdb':numberdb.__version__},
'entries':len(values),'by_vertices':dict(sizes),'regular_graphs':regular,'irregular_graphs':len(values)-regular,
'bipartite_graphs':bipartite,'graphs_with_bridges':bridges,'named_entries':len(comments),
'neighbor_key_agreement':overlap,'distinct_polynomials':len(groups),
'coincidences':[g for g in groups.values() if len(g)>1], 'measurement':measure(values),
'checks':{'exactness':True,'nauty_vs_atlas':True,'directed_edge_characteristic_polynomial':len(values),
'degree_and_leading_coefficient':len(values),'direct_closed_walk_counts':len(values)*6,
'cycle_formula':4,'source_diamond_factorization':True,'program_snippet':True,
'controls':['cycles C3 through C6','single edge determinant 1','path short walks 0']},
'values':{k:str(v) for k,v in values.items()}}
print(json.dumps(summary,indent=2))
return summary
if __name__=='__main__':
configure_stdin()
run(stored='--stored' in sys.argv)