"""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)