back to table · edit · history · where entries came from · files · download
9946 bytes, as of the version from 2026-10-27 11:53 (current). Recorded here, not run.
"""Independent construction and numerical checks for numberdb.org/T547.
sage -python checks.py # check locally generated values
sage -python checks.py --stored # check values read from NumberDB
Uses independent graph6 decoding, permutation determinants, exact Sturm root
counts, and mpmath symmetric diagonalization. The generator uses Sage Graph,
its Laplacian characteristic polynomial, and AA root isolation. McKay's input
catalogues and neighbouring tables are read from adjacent archived files when
present, otherwise from their original public sources. NUMBERDB_API_KEY is
needed while T547 is private. NUMBERDB_KEY_FROM_STDIN=1 supports the campaign.
The stdout JSON is the numerical evidence, including all 142 written values.
"""
import json
import os
import sys
import time
import hashlib
import urllib.request
from fractions import Fraction
from pathlib import Path
from itertools import permutations
from collections import Counter
import numberdb.sage as numberdb
from numberdb._write import to_text
from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
from sage.env import SAGE_VERSION
from sage.rings.real_mpfi import RealIntervalField
import mpmath as mp
from generate import AlgebraicConnectivity, graph_keys, canonical_key
from sage.graphs.graph import Graph
from sage.graphs.graph_generators import graphs
BASE=Path(__file__).resolve().parent
R=PolynomialRing(QQ,'x')
x=R.gen()
SKILL_MANIFEST='agents/runs/20261027T114054Z-build-skills/manifest.json'
SKILL_SHA256='e37efb7e2ededf6c1d7134c673f152f648f26e0267c556aebdf3ec65765d8b4c'
def read_document(tid):
path=BASE/(tid+'.json')
if path.exists():
return json.loads(path.read_text())
return numberdb.table(tid)
def entries(doc):
block=doc['Numbers']
if isinstance(block,dict):
return {key:({'number':value} if isinstance(value,str) else value) for key,value in block.items()}
return {r['params']['g']:{k:v for k,v in r.items() if k!='params'} for r in block}
def decode(key):
n=ord(key[0])-63
assert 2<=n<=6
bits=''.join(format(ord(c)-63,'06b') for c in key[1:])
assert len(bits)==6*((n*(n-1)//2+5)//6)
a=[[0]*n for _ in range(n)]
k=0
for j in range(1,n):
for i in range(j):
a[i][j]=a[j][i]=int(bits[k]); k+=1
assert not any(int(t) for t in bits[k:])
return a
def laplacian(a):
n=len(a)
return [[sum(a[i]) if i==j else -a[i][j] for j in range(n)] for i in range(n)]
def determinant_polynomial(lap):
n=len(lap); total=R.zero()
for perm in permutations(range(n)):
term=R.one()
for i,j in enumerate(perm):
term *= x-lap[i][j] if i==j else -lap[i][j]
if not term: break
parity=sum(perm[i]>perm[j] for i in range(n) for j in range(i+1,n))%2
total += -term if parity else term
return total
def sturm(poly):
seq=[poly,poly.derivative()]
while seq[-1]:
remainder=-(seq[-2]%seq[-1])
if not remainder: break
seq.append(remainder)
return seq
def variations(seq,t):
signs=[int(f(t).sign()) for f in seq if f(t)]
return sum(a!=b for a,b in zip(signs,signs[1:]))
def q(text):
r=Fraction(str(text))
return QQ(r.numerator)/QQ(r.denominator)
def endpoints(text):
if ' +/- ' in text:
c,r=text.split(' +/- '); return q(c)-q(r),q(c)+q(r)
if text.startswith('['):
a,b=text.strip('[]').split(','); return q(a),q(b)
c=q(text)
if '.' not in text and 'e' not in text.lower(): return c,c
from decimal import Decimal
last=Decimal(text).as_tuple().exponent
ulp=QQ(10)**last
return c-ulp,c+ulp
def certify(p,low,high):
assert p(0)==0 and p.derivative()(0)!=0
nonzero=p//x
squarefree=nonzero//nonzero.gcd(nonzero.derivative())
seq=sturm(squarefree)
assert low>0
if low==high:
assert nonzero(low)==0
assert variations(seq,0)-variations(seq,high)==1
else:
assert squarefree(low)*squarefree(high)<0
assert variations(seq,0)-variations(seq,low)==0
assert variations(seq,low)-variations(seq,high)==1
def mpq(r):
return mp.mpf(str(r.numerator()))/mp.mpf(str(r.denominator()))
def main(stored=False):
start=time.monotonic()
# Controls first: the specification's decoding example and known spectra.
spec=decode('DQc')
assert {(i,j) for i in range(5) for j in range(i+1,5) if spec[i][j]}=={(0,2),(0,4),(1,3),(3,4)}
k2=laplacian(decode('A_'))
assert determinant_polynomial(k2)==x*(x-2)
certify(x*(x-2),QQ(2),QQ(2))
certify(x*(x-1)**2*(x-4),QQ(1),QQ(1))
for bad in [(QQ(3),QQ(3)),(QQ(1)/2,QQ(3)/2)]:
try: certify(x*(x-2),*bad)
except AssertionError: pass
else: raise AssertionError('Sturm rejection control failed')
third=RealIntervalField(100)(QQ(1)/QQ(3))
assert third.lower().exact_rational()<QQ(1)/QQ(3)<third.upper().exact_rational()
mp.mp.dps=150
assert abs(mp.eigsy(mp.matrix(k2),eigvals_only=True)[1]-2)<mp.mpf('1e-145')
assert mp.eigsy(mp.zeros(3),eigvals_only=True)[1]==0
generator=AlgebraicConnectivity()
keys=list(graph_keys())
census=dict(Counter(ord(k[0])-63 for k in keys))
assert census=={2:1,3:2,4:6,5:21,6:112}
assert len(keys)==len(set(keys))==142
catalogue_keys=[]; catalogue_hashes={}
for n in range(2,7):
name='graph%dc.g6'%n
path=BASE/name
data=path.read_bytes() if path.exists() else urllib.request.urlopen('https://users.cecs.anu.edu.au/~bdm/data/'+name,timeout=30).read()
catalogue_hashes[name]=hashlib.sha256(data).hexdigest()
raw=data.decode().splitlines()
assert len(raw)==census[n]
catalogue_keys.extend(canonical_key(Graph(k,format='graph6')) for k in raw)
assert set(catalogue_keys)==set(keys)
neighbours={tid:entries(read_document(tid)) for tid in ['T237','T238','T397','T400','T545','T546']}
for tid,rows in neighbours.items():
assert {k for k in rows if 2<=ord(k[0])-63<=6}==set(keys),tid
records=entries(numberdb.table('T547')) if stored else {
k:{**generator.value({'g':k},100), 'number':to_text(generator.value({'g':k},100)['number'],digits=100)} for k in keys}
assert list(records)==keys
exact=0; widths=[]; rows_out=[]; independent={}
for key in keys:
graph=Graph(key,format='graph6')
assert canonical_key(graph)==key
a=decode(key); lap=laplacian(a); n=len(a)
assert [list(row) for row in graph.adjacency_matrix()]==a
p=determinant_polynomial(lap)
assert p==R(neighbours['T238'][key]['number'])
assert p[n-1]==-sum(sum(row) for row in a)
text=records[key]['number']; low,high=endpoints(text)
certify(p,low,high)
expected=generator.value({'g':key},100)['number']
if low==high:
exact+=1; assert expected==low
else:
e_low=expected.lower().exact_rational(); e_high=expected.upper().exact_rational()
assert low<=e_low<=e_high<=high
width=e_high-e_low
assert width>0
widths.append(width)
assert width<QQ(1)/ZZ(10)**110
eigenvalues=mp.eigsy(mp.matrix(lap),eigvals_only=True)
independent[key]=eigenvalues[1]
assert abs(eigenvalues[0])<mp.mpf('1e-145')
assert eigenvalues[1]>0
if low==high:
assert abs(eigenvalues[1]-mpq(low))<mp.mpf('1e-145')
else:
assert mpq(low)<eigenvalues[1]<mpq(high)
rows_out.append({'g':key,'number':text,'laplacian_polynomial':str(p),
'independent_eigenvalue':mp.nstr(eigenvalues[1],145),
'exact':bool(low==high),'sturm_certified':True})
controls=Counter()
def compare(graph,value,kind):
key=canonical_key(graph); low,high=endpoints(records[key]['number'])
assert abs(independent[key]-value)<mp.mpf('1e-140'),(kind,key)
if low==high: assert abs(mpq(low)-value)<mp.mpf('1e-140')
else: assert mpq(low)<value<mpq(high)
controls[kind]+=1
for n in range(2,7):
compare(graphs.CompleteGraph(n),mp.mpf(n),'complete')
compare(graphs.PathGraph(n),2-2*mp.cos(mp.pi/n),'path')
if n>=3: compare(graphs.CycleGraph(n),2-2*mp.cos(2*mp.pi/n),'cycle')
for a in range(1,n//2+1):
b=n-a
value=2 if a==b==1 else (1 if a==1 else min(a,b))
compare(graphs.CompleteBipartiteGraph(a,b),mp.mpf(value),'complete_bipartite')
print(json.dumps({'table':'T547','mode':'stored' if stored else 'dry',
'skill_manifest':SKILL_MANIFEST,'skill_local_sha256':SKILL_SHA256,'skill_live_sha256':SKILL_SHA256,
'sage':SAGE_VERSION,'mpmath':mp.__version__,'numberdb':numberdb.__version__,
'census':census,'entries':len(keys),'exact_integer_entries':exact,
'irrational_entries':len(keys)-exact,'named_entries':sum(bool(r.get('comment')) for r in records.values()),
'working_bits':numberdb.bits(100,losing=80),'max_enclosure_width':mp.nstr(mpq(max(widths)),12),
'longest_written_value':max(len(r['number']) for r in records.values()),
'entries_json_bytes':len(json.dumps(records).encode()),
'sturm_certificates':len(keys),'independent_eigenvalue_checks':len(keys),'mpmath_dps':150,
'formula_controls':dict(controls),'neighbour_keys_checked':list(neighbours),
'catalogue_sha256':catalogue_hashes,'elapsed_seconds':round(time.monotonic()-start,2),
'rows':rows_out},indent=2))
if __name__=='__main__':
if os.environ.get('NUMBERDB_KEY_FROM_STDIN')=='1':
token=sys.stdin.read().strip()
if '=' in token and token.split('=',1)[0].isidentifier(): token=token.split('=',1)[1].strip().strip('\"\'')
numberdb.configure(api_key=token)
main('--stored' in sys.argv)