{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R169",
  "content_hash": null,
  "slug": "cst101-artifact-exact-orbit-sweep",
  "type": "artifact",
  "title": "Exact orbit sweep with modular Matrix-Tree products",
  "summary": "Standard-library Python visits all 2,118,760 step sets, computes one exact count per orbit, and hashes the full canonical result table.",
  "relevance": "For Most spanning trees in a 10-regular circulant on 101 vertices, record cst101-artifact-exact-orbit-sweep (“Exact orbit sweep with modular Matrix-Tree products”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python visits all 2,118,760 step sets, computes one exact count per orbit, and hashes the full canonical result table.",
  "relevance_source": "recorded",
  "body": "The program stores each step set as a 50-bit integer. For a first unseen set, it generates all 50 signed-unit images, marks the orbit seen, and uses the smallest bit mask as representative. Assertions fix the complete orbit distribution before accepting the optimum.\n\nFor each representative, six finite-field Fourier tables supply the 50 paired Laplacian eigenvalues. Native integer modular arithmetic produces six exact residues, and incremental Chinese remaindering reconstructs the tree count. The product of the moduli is larger than the universal spectral upper bound, so no two possible counts share a residue vector.\n\nA SHA-256 stream covers the representative mask, its orbit size, and its reconstructed 48-byte little-endian tree count. Its digest is `422da911117db6d7008b3683660583752b1152e49a15522c52f9267d664b4771`. The stable seven-line output has SHA-256 digest `3936bd3c064fae74cbcc3e4147ab4db608e7f558ad84e02e1cd345d3ff56643d`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "all five-element step sets in {1,...,50}, represented by every orbit under signed multiplication modulo 101",
    "bounds": {
      "step_sets": {
        "min": 2118760,
        "max": 2118760
      },
      "signed_unit_orbits": {
        "min": 42376,
        "max": 42376
      },
      "modular_spectra_per_orbit": {
        "min": 6,
        "max": 6
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_python_exact_computation",
    "entrypoint": "join source_lines with newline and run with python3",
    "runtime": "CPython 3.9 or later, standard library only",
    "citation": {
      "url": "https://arxiv.org/abs/1711.00175",
      "locator": "Self-contained CPython computation executed by TheoremDB entry research on 2026-07-25"
    },
    "outputs": "subsets=2118760 orbit_representatives=42376\norbit_sizes=10:1,50:42375\nmaximum=2708274425686971438523646018073797918175286202944373217379948692092215150697249050994964490229261 maximizing_orbits=1\ncanonical_support={1,15,18,22,27} sampled_support={4,7,13,29,41}\nrunner_up=2705790677807473137809613684625587492780256938436447544415672932035143210140285775448737562551029 support={7,15,16,18,28}\ncrt_modulus_bits=366\ncanonical_exact_records_sha256=422da911117db6d7008b3683660583752b1152e49a15522c52f9267d664b4771\n",
    "inline_source": [
      "from hashlib import sha256",
      "from itertools import combinations",
      "from struct import pack",
      "",
      "N = 101",
      "PRIMES = [",
      "    2305843009213689133,",
      "    2305843009213687921,",
      "    2305843009213683881,",
      "    2305843009213683679,",
      "    2305843009213683073,",
      "    2305843009213679437,",
      "]",
      "ROOTS = [",
      "    1160806057837852116,",
      "    128642504887337648,",
      "    729449869172511575,",
      "    1053915148049707494,",
      "    290335823430761657,",
      "    285492777286681628,",
      "]",
      "EXPECTED_MAX = int(",
      "    \"270827442568697143852364601807379791817528620294437321737994869209221515\"",
      "    \"0697249050994964490229261\"",
      ")",
      "EXPECTED_SECOND = int(",
      "    \"270579067780747313780961368462558749278025693843644754441567293203514321\"",
      "    \"0140285775448737562551029\"",
      ")",
      "",
      "step_image = [[0] * 51 for _ in range(51)]",
      "for u in range(1, 51):",
      "    for s in range(1, 51):",
      "        r = u * s % N",
      "        r = min(r, N - r)",
      "        step_image[u][s] = 1 << (r - 1)",
      "",
      "",
      "def transform(steps, u):",
      "    return sum(step_image[u][s] for s in steps)",
      "",
      "",
      "tables = []",
      "for p, root in zip(PRIMES, ROOTS):",
      "    powers = [1]",
      "    for _ in range(100):",
      "        powers.append(powers[-1] * root % p)",
      "    assert powers[101 - 1] != 1 and powers[-1] * root % p == 1",
      "    table = [[0] * 51 for _ in range(51)]",
      "    for k in range(1, 51):",
      "        for s in range(1, 51):",
      "            e = k * s % N",
      "            table[k][s] = (powers[e] + powers[N - e]) % p",
      "    tables.append(table)",
      "",
      "crt_modulus = 1",
      "crt_before = []",
      "crt_inverse = []",
      "for p in PRIMES:",
      "    crt_before.append(crt_modulus)",
      "    crt_inverse.append(pow(crt_modulus, -1, p))",
      "    crt_modulus *= p",
      "",
      "",
      "def tree_count(steps):",
      "    residues = []",
      "    for p, table in zip(PRIMES, tables):",
      "        half_norm = 1",
      "        for k in range(1, 51):",
      "            eigenvalue = (10 - sum(table[k][s] for s in steps)) % p",
      "            half_norm = half_norm * eigenvalue % p",
      "        residues.append(half_norm * half_norm * pow(101, -1, p) % p)",
      "    x = 0",
      "    for residue, p, modulus, inverse in zip(",
      "        residues, PRIMES, crt_before, crt_inverse",
      "    ):",
      "        x += ((residue - x) * inverse % p) * modulus",
      "    return x",
      "",
      "",
      "seen = set()",
      "orbit_histogram = {}",
      "records_hash = sha256()",
      "best = (-1, None)",
      "second = (-1, None)",
      "maximizing_orbits = 0",
      "representatives = 0",
      "",
      "for steps in combinations(range(1, 51), 5):",
      "    mask = sum(1 << (s - 1) for s in steps)",
      "    if mask in seen:",
      "        continue",
      "    orbit = {transform(steps, u) for u in range(1, 51)}",
      "    seen.update(orbit)",
      "    representative = min(orbit)",
      "    representative_steps = tuple(",
      "        i + 1 for i in range(50) if representative >> i & 1",
      "    )",
      "    trees = tree_count(representative_steps)",
      "    representatives += 1",
      "    orbit_histogram[len(orbit)] = orbit_histogram.get(len(orbit), 0) + 1",
      "    records_hash.update(pack(\"<QB\", representative, len(orbit)))",
      "    records_hash.update(trees.to_bytes(48, \"little\"))",
      "    if trees > best[0]:",
      "        second = best",
      "        best = (trees, representative_steps)",
      "        maximizing_orbits = 1",
      "    elif trees == best[0]:",
      "        maximizing_orbits += 1",
      "    elif trees > second[0]:",
      "        second = (trees, representative_steps)",
      "",
      "assert len(seen) == 2118760",
      "assert representatives == 42376",
      "assert orbit_histogram == {50: 42375, 10: 1}",
      "assert best == (EXPECTED_MAX, (1, 15, 18, 22, 27))",
      "assert second == (EXPECTED_SECOND, (7, 15, 16, 18, 28))",
      "assert maximizing_orbits == 1",
      "assert crt_modulus > 10**101",
      "",
      "sample = {4, 7, 13, 29, 41}",
      "assert {",
      "    min(4 * s % N, N - (4 * s % N)) for s in best[1]",
      "} == sample",
      "",
      "print(f\"subsets={len(seen)} orbit_representatives={representatives}\")",
      "print(\"orbit_sizes=10:1,50:42375\")",
      "print(f\"maximum={best[0]} maximizing_orbits={maximizing_orbits}\")",
      "print(\"canonical_support={1,15,18,22,27} sampled_support={4,7,13,29,41}\")",
      "print(f\"runner_up={second[0]} support={{7,15,16,18,28}}\")",
      "print(f\"crt_modulus_bits={crt_modulus.bit_length()}\")",
      "print(f\"canonical_exact_records_sha256={records_hash.hexdigest()}\")"
    ],
    "missing": [
      "command"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1711.00175",
    "locator": "Self-contained CPython computation executed by TheoremDB entry research on 2026-07-25"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R171",
      "title": "The exact maximum has 97 digits",
      "object_type": "claim",
      "relation": "evidences",
      "direction": "outgoing"
    },
    {
      "slug": "R172",
      "title": "Six finite-field spectra determine every tree count exactly",
      "object_type": "claim",
      "relation": "tests",
      "direction": "outgoing"
    },
    {
      "slug": "circulant-spanning-trees-101-degree10",
      "title": "circulant spanning trees 101 degree10",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}