generate.py

back to table · edit · history · where entries came from · files · download

3103 bytes, as of the version from 2026-10-27 04:15 (current). Recorded here, not run.

"""Distance characteristic polynomials of connected graphs -- numberdb.org/T537.

Run with SageMath (download the attached selected-graphs.json alongside this):
    sage -pip install numberdb
    sage -python generate.py             # verify all stored entries
    sage -python generate.py --fill      # write entries with NUMBERDB_API_KEY
    sage -python checks.py               # independent checks, no writes

The --fill option sends entries and attachments to the existing table; it does
not publish the draft or offer it for review. To fill, download all files named
in DistancePolynomials.files. Default enumeration is exactly the 142 connected
simple graphs on 2 through 6 vertices. The stable keys use Sage's explicit
canonical_label(algorithm='sage'), checked against T237, T238 and McKay's
catalogues. See argument-selection.md for the family and finite cutoff.

Every matrix entry and polynomial coefficient is an exact integer. Sage computes
the characteristic polynomial of the integer shortest-path distance matrix.
There is no numerical precision target for an exact Z[x] table.
"""
import json
import os
from pathlib import Path
import sys

import numberdb.sage as numberdb
from sage.graphs.graph import Graph
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

HERE = Path(__file__).resolve().parent
R = PolynomialRing(ZZ, 'x')


def selection():
    return json.loads((HERE / 'selected-graphs.json').read_text())


class DistancePolynomials(numberdb.Generator):
    table = 'T537'
    parameters = ('g',)
    type = 'Z[]'
    rigour = 'exact'
    files = ('generate.py', 'selected-graphs.json', 'argument-selection.md',
             'checks.py', 'check.py', 'reference-values.json',
             'graph2c.g6', 'graph3c.g6', 'graph4c.g6', 'graph5c.g6', 'graph6c.g6',
             'numerical-evidence.json', 'skill-evidence.json', 'source-notes.md')

    def enumerate(self):
        for row in selection():
            yield {'g': row['g']}

    def value(self, params, digits=100):
        key = params['g']
        graph = Graph(key, format='graph6')
        if graph.order() < 2 or not graph.is_connected():
            raise ValueError('A connected simple graph with at least two vertices is required')
        polynomial = R(graph.distance_matrix().change_ring(ZZ).charpoly('x'))
        result = {'number': polynomial}
        for row in selection():
            if row['g'] == key and row.get('comment'):
                result['comment'] = row['comment']
                break
        return result


if __name__ == '__main__':
    if os.environ.get('NUMBERDB_KEY_FROM_STDIN') == '1':
        os.environ['NUMBERDB_API_KEY'] = sys.stdin.read().strip()
    generator = DistancePolynomials()
    if '--fill' in sys.argv or os.environ.get('NUMBERDB_PUBLISH') == '1':
        print(generator.publish(message='Fill all 142 exact distance characteristic polynomials and attach reproducible checks'))
    else:
        report = generator.verify(sample=None)
        print(report)
        sys.exit(0 if report.ok else 1)