back to table · edit · history · where entries came from · files · download
10018 bytes, as of the version from 2026-10-27 03:45 (current). Recorded here, not run.
"""Independent checks for numberdb.org/T536.
Run: sage -python checks.py
Optional: sage -python checks.py --stored (authenticated while T536 is a draft).
The independent method decodes graph6 without Sage Graph, uses Floyd--Warshall
for distances, and computes exact rational Collatz--Wielandt bounds. It never
uses a characteristic polynomial or a root finder for these bounds. Separate
integer permutation determinants check the generator's full polynomials.
Stdout is JSON numerical evidence; redirect it to a file to retain it.
"""
import json
import os
from pathlib import Path
import re
import sys
import hashlib
from fractions import Fraction
from itertools import permutations
from math import gcd
from functools import reduce
from decimal import Decimal
from collections import Counter
import numberdb.sage as numberdb
from numberdb._write import to_text
from sage.graphs.graph import Graph
from sage.graphs.graph_generators import graphs
from sage.rings.rational_field import QQ
from sage.rings.qqbar import AA
from sage.rings.real_mpfi import RealIntervalField
import sage.version
from generate import DistanceSpectralRadii, selected_graphs, spectral_data
from check import exactness, names_its_rings, measure
HERE = Path(__file__).resolve().parent
def decoded_distances(key):
n = ord(key[0]) - 63
assert 2 <= n <= 6
bits = [(ord(c)-63 >> s) & 1 for c in key[1:] for s in range(5,-1,-1)]
d = [[0 if i == j else n+1 for j in range(n)] for i in range(n)]
at = 0
for j in range(1,n):
for i in range(j):
if bits[at]:
d[i][j] = d[j][i] = 1
at += 1
for k in range(n):
for i in range(n):
for j in range(n):
d[i][j] = min(d[i][j],d[i][k]+d[k][j])
assert all(d[i][j] < n for i in range(n) for j in range(n))
return d
def collatz_wielandt(d, target=115):
n = len(d)
v = [1] * n
for step in range(1,5001):
w = [sum(d[i][j]*v[j] for j in range(n)) for i in range(n)]
ratios = [Fraction(wi,vi) for wi,vi in zip(w,v)]
lo,hi = min(ratios),max(ratios)
assert 0 < lo <= hi
if (hi-lo)*10**target <= lo:
return lo,hi,step
factor = reduce(gcd,w)
v = [wi//factor for wi in w]
raise AssertionError('Rational power bounds did not converge')
def permutation_polynomial(d):
n = len(d)
coeffs = [0]*(n+1)
for perm in permutations(range(n)):
inversions = sum(perm[i] > perm[j] for i in range(n) for j in range(i+1,n))
p = [-1 if inversions%2 else 1]
for i,j in enumerate(perm):
q = [0]*(len(p)+1)
for k,a in enumerate(p):
q[k] -= a*d[i][j]
if i == j:
q[k+1] += a
p = q
coeffs = [a+b for a,b in zip(coeffs,p)]
return coeffs
def written_claim(text):
if '.' not in text and 'e' not in text.lower():
q = Fraction(text)
return q,q
centre = Fraction(text)
exponent = Decimal(text).as_tuple().exponent
ulp = Fraction(10)**exponent
return centre-ulp,centre+ulp
def rational_interval(value):
interval = RealIntervalField(500)(value)
return (Fraction(str(interval.lower().exact_rational())),
Fraction(str(interval.upper().exact_rational())))
def rounded_out(lo,hi):
scale = 10**120
lower = (lo*scale).__floor__()
upper = (hi*scale).__ceil__()
return [str(Fraction(lower,scale)),str(Fraction(upper,scale))]
def check_all(stored=None):
# Controls precede the measurement: exact K2 and K3; irrational P3;
# a deliberate wrong graph distance must not pass the P3 control.
assert collatz_wielandt([[0,1],[1,0]])[:2] == (1,1)
assert collatz_wielandt([[0,1,1],[1,0,1],[1,1,0]])[:2] == (2,2)
lo,hi,_ = collatz_wielandt([[0,1,2],[1,0,1],[2,1,0]])
assert (lo-1)**2 <= 3 <= (hi-1)**2 and hi-lo < Fraction(1,10**110)
assert not lo <= 2 <= hi
assert permutation_polynomial([[0,1],[1,0]]) == [-1,0,1]
assert permutation_polynomial([[0,1,2],[1,0,1],[2,1,0]]) == [-4,-6,0,1]
records = selected_graphs()
keys = [r['g'] for r in records]
catalogue = []
enumerated = []
for n in range(2,7):
catalogue += [Graph(k).canonical_label(algorithm='sage').graph6_string()
for k in (HERE / f'graph{n}c.g6').read_text().splitlines() if k]
enumerated += [g.canonical_label(algorithm='sage').graph6_string()
for g in graphs.nauty_geng(f'{n} -c')]
assert len(catalogue) == len(set(catalogue)) == 142
assert len(enumerated) == len(set(enumerated)) == 142
assert set(keys) == set(catalogue) == set(enumerated)
if stored is not None:
assert list(stored) == keys
fiedler = {r['g']: r for r in json.loads((HERE/'fiedler-reference.json').read_text())}
generator = DistanceSpectralRadii()
values = {}
evidence = []
counts = Counter()
min_accuracy = 10000
for key in keys:
d = decoded_distances(key)
g = Graph(key)
assert g.canonical_label(algorithm='sage').graph6_string() == key
sage_d,p,roots,largest = spectral_data(key)
assert [[int(a) for a in row] for row in sage_d.rows()] == d
pc = permutation_polynomial(d)
assert pc == [int(p[i]) for i in range(len(d)+1)]
counts['independent_polynomials'] += 1
assert p[len(d)-1] == 0
assert -2*p[len(d)-2] == sum(a*a for row in d for a in row)
assert min(map(sum,d)) <= largest <= max(map(sum,d))
n = len(d)
if g.is_tree():
assert (-1)**n * pc[0] == (-1)**(n-1)*(n-1)*2**(n-2)
assert sum(m for r,m in roots if r > 0) == 1
counts['tree_determinant_and_inertia'] += 1
if g.size() == n*(n-1)//2:
assert largest == n-1
counts['complete_graph_formula'] += 1
if n >= 3 and set(g.degree()) == {2}:
assert largest == n*n//4
counts['cycle_formula'] += 1
if g.is_bipartite():
a,b = map(len,g.bipartite_sets())
if g.size() == a*b:
assert largest == a+b-2+AA(a*a-a*b+b*b).sqrt()
counts['complete_bipartite_formula'] += 1
if len(set(map(sum,d))) == 1:
assert largest == sum(d[0])
counts['constant_transmission_formula'] += 1
if len(set(g.degree())) == 1 and max(map(max,d)) <= 2:
assert largest == 2*(n-1)-g.degree()[0]
counts['regular_diameter_two_formula'] += 1
if g.is_tree() and max(g.degree()) <= 2:
counts['path_fiedler_matrix_identity'] += 1
# Verify matrix identity via distances along a path ordering
# obtained independently by following its endpoints.
start = next(v for v in g if g.degree(v)==1)
order = [start]
while len(order) < n:
order.append(next(v for v in g.neighbors(order[-1]) if v not in order))
assert all(d[order[i]][order[j]] == abs(i-j) for i in range(n) for j in range(n))
entry = generator.value({'g':key},100)
values[key] = entry
text = to_text(entry['number'],digits=100) if stored is None else stored[key]
a,b = written_claim(text)
lo,hi,steps = collatz_wielandt(d)
if a == b:
assert lo <= a <= hi and p(QQ(a.numerator)/QQ(a.denominator)) == 0
assert largest in QQ and QQ(largest) == QQ(a.numerator)/QQ(a.denominator)
counts['exact_rational'] += 1
else:
assert a <= lo <= hi <= b, (key,'independent bounds escape written interval')
bl,bh = rational_interval(entry['number'])
assert a <= bl <= bh <= b
rel = (bh-bl)/min(abs(bl),abs(bh))
bits = rel.denominator.bit_length()-rel.numerator.bit_length()-1
min_accuracy = min(min_accuracy,bits)
assert bits >= 365
counts['certified_100_digit_decimal'] += 1
if key in fiedler:
fl,fh = written_claim(fiedler[key]['reference_number'])
assert fl <= lo <= hi <= fh
counts['stored_fiedler_eigenvalues'] += 1
counts['independent_rational_bounds'] += 1
evidence.append({'g':key,'number':text,'polynomial_coefficients':pc,
'independent_bounds':rounded_out(lo,hi),'iterations':steps})
assert not exactness(values)
assert not names_its_rings(str(HERE/'generate.py'))
return {'table':'T536','mode':'stored' if stored is not None else 'offline',
'skill_manifest':'agents/runs/20261027T033406Z-build-skills/manifest.json',
'skill_sha256':'e37efb7e2ededf6c1d7134c673f152f648f26e0267c556aebdf3ec65765d8b4c',
'sage_version':sage.version.version,'numberdb_version':numberdb.__version__,
'counts_by_order':dict(Counter(ord(g[0])-63 for g in keys)),
'checks':dict(counts),'controls':'passed before catalogue checks',
'minimum_ball_relative_bits':min_accuracy,
'maximum_power_iterations':max(r['iterations'] for r in evidence),
'measurement':measure(values),
'longest_stored_number':max(len(r['number']) for r in evidence),
'records':evidence}
if __name__ == '__main__':
if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
key = sys.stdin.read().strip()
if re.match(r'^[A-Z_][A-Z0-9_]*\s*=',key):
key=key.split('=',1)[1].strip().strip('\"\'')
numberdb.configure(api_key=key)
stored = None
if '--stored' in sys.argv or os.environ.get('NUMBERDB_PUBLISH') == '1':
table = numberdb.table('T536')
numbers = table['Numbers']
if isinstance(numbers,list):
stored = {r['params']['g']:r['number'] for r in numbers}
else:
stored = {k:(v['number'] if isinstance(v,dict) else v) for k,v in numbers.items()}
print(json.dumps(check_all(stored),indent=2))