{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R168",
  "content_hash": null,
  "slug": "cst101-artifact-bareiss-cofactor",
  "type": "artifact",
  "title": "Independent exact Laplacian-cofactor check",
  "summary": "Fraction-free Bareiss elimination of a 100 by 100 Laplacian minor reproduces the 97-digit maximum.",
  "relevance": "For Most spanning trees in a 10-regular circulant on 101 vertices, record cst101-artifact-bareiss-cofactor (“Independent exact Laplacian-cofactor check”) supplies evidence or a replay used to check the packet. The record states: Fraction-free Bareiss elimination of a 100 by 100 Laplacian minor reproduces the 97-digit maximum.",
  "relevance_source": "recorded",
  "body": "The replay constructs the integer Laplacian directly from the canonical step set and deletes vertex 100. Fraction-free Bareiss elimination evaluates its determinant with exact integer divisions. Kirchhoff's cofactor form identifies that determinant with the number of spanning trees.\n\nThe result agrees with the modular spectral sweep and factors as\n\\[\n101\\left(163751635943365250046066837250008630123794408131\\right)^2.\n\\]\nThis also checks the square form proved for odd-order even-valent circulants by Mednykh and Mednykh. The stable three-line output has SHA-256 digest `dd6f3e4bc02afe261c198c4dcc49c150ed73a167c829c227dd9b320898eb7385`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "the attaining graph with step set {1,15,18,22,27} on Z/101Z",
    "bounds": {
      "vertices": {
        "min": 101,
        "max": 101
      },
      "laplacian_minor_order": {
        "min": 100,
        "max": 100
      }
    },
    "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": "Kirchhoff cofactor replay and Mednykh and Mednykh, Theorem 3"
    },
    "outputs": "laplacian_minor_order=100\ndeterminant=2708274425686971438523646018073797918175286202944373217379948692092215150697249050994964490229261\nfactorization=101*163751635943365250046066837250008630123794408131^2\n",
    "inline_source": [
      "from math import isqrt",
      "",
      "N = 101",
      "S = {1, 15, 18, 22, 27}",
      "EXPECTED = int(",
      "    \"270827442568697143852364601807379791817528620294437321737994869209221515\"",
      "    \"0697249050994964490229261\"",
      ")",
      "",
      "minor = []",
      "for i in range(N - 1):",
      "    row = []",
      "    for j in range(N - 1):",
      "        distance = min((i - j) % N, (j - i) % N)",
      "        row.append(10 if i == j else (-1 if distance in S else 0))",
      "    minor.append(row)",
      "",
      "previous = 1",
      "sign = 1",
      "for k in range(N - 2):",
      "    if minor[k][k] == 0:",
      "        pivot_row = next(i for i in range(k + 1, N - 1) if minor[i][k])",
      "        minor[k], minor[pivot_row] = minor[pivot_row], minor[k]",
      "        sign = -sign",
      "    pivot = minor[k][k]",
      "    for i in range(k + 1, N - 1):",
      "        left = minor[i][k]",
      "        for j in range(k + 1, N - 1):",
      "            minor[i][j] = (",
      "                minor[i][j] * pivot - left * minor[k][j]",
      "            ) // previous",
      "        minor[i][k] = 0",
      "    previous = pivot",
      "",
      "determinant = sign * minor[-1][-1]",
      "assert determinant == EXPECTED",
      "square_root = isqrt(determinant // N)",
      "assert determinant == N * square_root * square_root",
      "print(f\"laplacian_minor_order={N - 1}\")",
      "print(f\"determinant={determinant}\")",
      "print(f\"factorization=101*{square_root}^2\")"
    ],
    "missing": [
      "command"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1711.00175",
    "locator": "Kirchhoff cofactor replay and Mednykh and Mednykh, Theorem 3"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R171",
      "title": "The exact maximum has 97 digits",
      "object_type": "claim",
      "relation": "independently_verifies",
      "direction": "outgoing"
    },
    {
      "slug": "circulant-spanning-trees-101-degree10",
      "title": "circulant spanning trees 101 degree10",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}