back to table · edit · history · where entries came from · files · download
10041 bytes, as of the version from 2026-11-02 08:29 (current). Recorded here, not run.
"""Check T661 using a colored Young graph and exact group computations.
Run with SageMath after installing numberdb:
sage -python checks.py --document table.json --output coverage-evidence.json
Without --document, generated entries are checked. A document can be obtained
as JSON from numberdb.table('T661'); draft access requires authentication.
No network requests or writes to NumberDB are made by this checker.
"""
import argparse
from collections import Counter, defaultdict
from decimal import Decimal
from fractions import Fraction
from itertools import permutations, product
import json
from math import factorial, isqrt
from pathlib import Path
import numberdb.sage as numberdb
from numberdb._write import Entries
from sage.version import version as sage_version
from generate import CharacterDegreePowerSum, degree_histogram, selected_pairs
def children(partition):
for row in range(len(partition)):
if row == 0 or partition[row - 1] > partition[row]:
changed = list(partition)
changed[row] += 1
yield tuple(changed)
yield partition + (1,)
def branching_spectra(colors, maximum):
level = {((),) * colors: 1}
spectra = {}
for size in range(1, maximum + 1):
next_level = defaultdict(int)
for shapes, paths in level.items():
for color in range(colors):
for child in children(shapes[color]):
changed = list(shapes)
changed[color] = child
next_level[tuple(changed)] += paths
level = next_level
spectra[size] = dict(Counter(level.values()))
return spectra
def colored_partitions(colors, size):
coefficients = [1] + [0] * size
for part in range(1, size + 1):
for color in range(colors):
for index in range(part, size + 1):
coefficients[index] += coefficients[index - part]
return coefficients[size]
def symmetric_monomial_count(colors, size):
return sum(factorial(size) * colors ** (size - pairs)
// (factorial(size - 2 * pairs) * 2 ** pairs * factorial(pairs))
for pairs in range(size // 2 + 1))
def exact_moment(spectrum, exponent):
return sum((Fraction(multiplicity) * Fraction(degree) ** exponent
for degree, multiplicity in spectrum.items()), Fraction(0))
def independent_bounds(spectrum, exponent):
power = Fraction(exponent)
if power.denominator == 1:
result = exact_moment(spectrum, power.numerator)
return result, result
assert power == Fraction(9, 4)
scale = 10 ** 140
lower = upper = Fraction(0)
for degree, multiplicity in spectrum.items():
radicand = degree * scale ** 4
root = isqrt(isqrt(radicand))
assert root ** 4 <= radicand < (root + 1) ** 4
upper_root = root if root ** 4 == radicand else root + 1
lower += multiplicity * degree ** 2 * Fraction(root, scale)
upper += multiplicity * degree ** 2 * Fraction(upper_root, scale)
return lower, upper
def written_bounds(text):
text = str(text)
if '.' not in text and 'e' not in text.lower():
value = Fraction(text)
return value, value
decimal = Decimal(text)
value = Fraction(decimal)
uncertainty = Fraction(10) ** decimal.as_tuple().exponent
return value - uncertainty, value + uncertainty
def small_surface_counts(colors, size):
elements = [(permutation, labels)
for permutation in permutations(range(size))
for labels in product(range(colors), repeat=size)]
positions = {element: index for index, element in enumerate(elements)}
identity = positions[(tuple(range(size)), (0,) * size)]
multiplication = []
for permutation, labels in elements:
inverse_permutation = tuple(permutation.index(index) for index in range(size))
row = []
for other_permutation, other_labels in elements:
composed = tuple(permutation[other_permutation[index]] for index in range(size))
new_labels = tuple((labels[index] + other_labels[inverse_permutation[index]]) % colors
for index in range(size))
row.append(positions[(composed, new_labels)])
multiplication.append(row)
inverses = [row.index(identity) for row in multiplication]
commutators = Counter()
for left in range(len(elements)):
for right in range(len(elements)):
value = multiplication[left][right]
value = multiplication[value][inverses[left]]
value = multiplication[value][inverses[right]]
commutators[value] += 1
distribution = {identity: 1}
counts = {}
for genus in range(1, 4):
updated = defaultdict(int)
for left, left_count in distribution.items():
for right, right_count in commutators.items():
updated[multiplication[left][right]] += left_count * right_count
distribution = updated
assert sum(distribution.values()) == len(elements) ** (2 * genus)
counts[genus] = distribution[identity]
return len(elements), counts
class SnapshotClient:
def __init__(self, document):
self.document = document
def request(self, path, parameters):
assert path == 'api/table' and parameters == {'id': 'T661'}
return self.document
def records_from_document(document):
return [{'params': {'q': base, 'n': size, 's': exponent},
'number': value['number'] if isinstance(value, dict) else value}
for base, sizes in document['Numbers'].items()
for size, moments in sizes.items()
for exponent, value in moments.items()]
def run_checks(document=None):
assert branching_spectra(1, 3)[3] == {1: 2, 2: 1}
assert branching_spectra(2, 2)[2] == {1: 4, 2: 1}
assert independent_bounds({16: 1}, '9/4') == (Fraction(512), Fraction(512))
assert independent_bounds({1: 2, 2: 1}, '-2') == (Fraction(9, 4), Fraction(9, 4))
spectra = {}
for colors, maximum in ((1, 20), (2, 12), (3, 10)):
for size, spectrum in branching_spectra(colors, maximum).items():
spectra[colors, size] = spectrum
pairs = list(selected_pairs())
assert len(pairs) == len(set(pairs)) == 77
for colors, size in pairs:
if colors > 3:
assert size == 2
spectra[colors, size] = {1: 2 * colors, 2: (2 * colors ** 2 - 2 * colors) // 4}
spectrum = spectra[colors, size]
assert spectrum == degree_histogram(colors, size)
assert spectrum[1] == 2 * colors
assert exact_moment(spectrum, 2) == colors ** size * factorial(size)
assert exact_moment(spectrum, 1) == symmetric_monomial_count(colors, size)
if colors <= 3:
assert exact_moment(spectrum, 0) == colored_partitions(colors, size)
generator = CharacterDegreePowerSum()
entries = Entries(*generator.parameters)
accuracy = []
for parameters in generator.enumerate():
value = generator.value(parameters, 100)
entries.add(number=value, digits=100, **parameters)
if Fraction(parameters['s']).denominator != 1:
assert value.is_finite() and value > 0 and value.accuracy() >= 350
accuracy.append(int(value.accuracy()))
generated = entries.as_list()
records = records_from_document(document) if document is not None else generated
assert len(records) == 421
assert [record['params'] for record in records] == list(generator.enumerate())
integers = rationals = reals = 0
for record in records:
parameters = record['params']
spectrum = spectra[int(parameters['q']), int(parameters['n'])]
lower, upper = independent_bounds(spectrum, parameters['s'])
left, right = written_bounds(record['number'])
assert left <= lower <= upper <= right, parameters
if Fraction(parameters['s']).denominator == 1:
assert left == right == lower == upper
if lower.denominator == 1:
integers += 1
else:
rationals += 1
else:
reals += 1
assert right - left < Fraction(3, 10 ** 99) * lower
assert upper - lower < Fraction(1, 10 ** 130) * lower
surface_checks = []
for colors, size in ((1, 3), (1, 4), (2, 2), (3, 2)):
order, counts = small_surface_counts(colors, size)
for genus in (1, 2, 3):
expected = order ** (2 * genus - 1) * exact_moment(spectra[colors, size], 2 - 2 * genus)
assert counts[genus] == expected
surface_checks.append({'q': colors, 'n': size, 'order': order, 'homomorphism_counts': counts})
verified = None
if document is not None:
report = generator.verify(sample=None, client=SnapshotClient(document))
assert report.ok, str(report)
verified = str(report)
return {'table': 'T661', 'entries': len(records), 'group_pairs': len(pairs),
'exact_integers': integers, 'exact_nonintegral_rationals': rationals,
'certified_reals': reals, 'minimum_arb_accuracy_bits': min(accuracy),
'independent_branching_spectra': 38, 'sum_of_squares_checks': 77,
'gelfand_dimension_checks': 77, 'colored_partition_checks': 38,
'independent_entry_checks': len(records), 'surface_checks': surface_checks,
'verify_report': verified, 'sage_version': sage_version,
'scope': 'Independent algorithms, not an independent human review'}
if __name__ == '__main__':
parser = argparse.ArgumentParser()
parser.add_argument('--document', type=Path)
parser.add_argument('--output', type=Path)
options = parser.parse_args()
document = json.loads(options.document.read_text()) if options.document else None
evidence = run_checks(document)
output = json.dumps(evidence, indent=2) + '\n'
if options.output:
options.output.write_text(output)
print(output)