Verifying AI Math Constructions: Reliable Checks for Graph and Quantum Code Tasks

    This article explains how to verify AI-generated mathematical constructions separately from proofs, using two examples: a 124-vertex graph with no 3- or 4-cycles and a quantum error-correcting code under parameter constraints. It provides a Python checker for the graph case, outlines three checks for stabilizer codes, and proposes a unified verification workflow with clear boundaries between machine-checkable evidence and expert review.

    1. Why Constructions and Proofs Must Be Evaluated Separately

    Evaluation of large language models’ mathematical abilities is shifting from “can the model solve a problem?” to “can it participate in open-ended research?” Open problems do not have standard answers. A model may propose a construction, provide a proof, or find a mathematical object better than known results. These three types of output have very different levels of credibility, so they must be evaluated separately.

    Finding a better construction only requires an object that can be independently checked. Proving a new theorem requires a complete argument and peer review. The former can be verified by a program, while the latter usually depends on human reading.

    The original report was conducted jointly by academic and industry researchers and covered directions such as theorem proving, combinatorial constructions, and coding design. The two cases discussed here represent, respectively, the search for extremal objects in discrete structures and the design of codes satisfying parameter constraints in quantum information. Before using specific numbers from the report, readers should first locate the original material and check the institution, publication date, task version, and link. This article cannot replace the original materials.

    2. Graph Case: Edge Count in a Graph with No Short Cycles

    2.1 Task Requirements

    The task asks for as many edges as possible on 124 vertices, with no cycles of length 3 or 4. The girth of a graph is the length of its shortest cycle. Forbidding cycles of length 3 and 4 is equivalent to requiring girth at least 5.

    This is a classic problem in extremal graph theory: given a number of vertices and a forbidden structure, what is the maximum possible number of edges? Counting arguments can give an upper bound on the order of n^{3/2}. An exact upper bound requires consulting the literature or giving a rigorous proof; a counting estimate alone cannot provide the optimal value. Constructions that reach or approach the upper bound often require careful structural design.

    2.2 Results and Counting Conventions

    According to the original report, the model’s construction has 630 edges, while the reference construction has 629. The difference is only one edge. In extremal problems, an extra edge means that the known construction may not be optimal. However, a single-edge difference can easily come from counting errors, duplicate edges, or vertex-numbering errors. Therefore, this number cannot be accepted directly before rechecking.

    Before rechecking, confirm the counting conventions:

    • The graph is simple: no self-loops and no duplicate edges.
    • Vertices are numbered from 0 to 123.
    • The edge count is the number of deduplicated undirected edges.
    • The reference construction and the model construction use the same vertex numbering.

    Only when the conventions match does the comparison between 630 and 629 make sense.

    2.3 How to Verify a Construction

    Verifying a graph with no short cycles only requires checking two types of cycles. The decision rules are as follows.

    • A cycle of length 3 (a triangle) exists if and only if the two endpoints of some edge have a common neighbor.
    • A cycle of length 4 exists if and only if some two distinct vertices have at least two common neighbors.

    Based on these two rules, a checking program can be written. The program uses only the Python 3.8+ standard library and does not depend on third-party packages.

    Input format: n is the number of vertices, numbered from 0 to n-1; edges is a list of undirected edges, each represented as a tuple (u, v).

    1. from itertools import combinations
    2. def check_girth_at_least_5(n, edges, expected_m=None):
    3. """Check whether an undirected simple graph has girth at least 5.
    4. n: number of vertices, numbered 0..n-1
    5. edges: list of undirected edges, each as (u, v)
    6. Returns (True, info_dict) or (False, failure_evidence_dict)
    7. """
    8. adj = [set() for _ in range(n)]
    9. seen = set()
    10. for u, v in edges:
    11. if not (0 <= u < n and 0 <= v < n):
    12. return False, {"reason": "vertex out of range", "edge": (u, v)}
    13. if u == v:
    14. return False, {"reason": "self-loop", "edge": (u, v)}
    15. key = (min(u, v), max(u, v))
    16. if key in seen:
    17. return False, {"reason": "duplicate edge", "edge": key}
    18. seen.add(key)
    19. adj[u].add(v)
    20. adj[v].add(u)
    21. m = len(edges)
    22. if expected_m is not None:
    23. assert m == expected_m, f"edge count mismatch: actual {m}, expected {expected_m}"
    24. # Cycle of length 3: the two endpoints of some edge have a common neighbor
    25. for u, v in edges:
    26. common = adj[u] & adj[v]
    27. if common:
    28. w = min(common)
    29. return False, {"reason": "3-cycle", "cycle": (u, v, w)}
    30. # Cycle of length 4: some two vertices have at least two common neighbors
    31. for u, v in combinations(range(n), 2):
    32. common = adj[u] & adj[v]
    33. if len(common) >= 2:
    34. a, b = sorted(common)[:2]
    35. return False, {"reason": "4-cycle", "cycle": (u, a, v, b)}
    36. return True, {"vertices": n, "edges": m}

    Example calls:

    1. # A 5-cycle has girth 5, so the result is valid
    2. ok, info = check_girth_at_least_5(5, [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0)], expected_m=5)
    3. # ok is True; info is {'vertices': 5, 'edges': 5}
    4. # A square on four vertices contains a 4-cycle
    5. ok, info = check_girth_at_least_5(4, [(0, 1), (1, 2), (2, 3), (3, 0)])
    6. # ok is False; info is {'reason': '4-cycle', 'cycle': (0, 1, 2, 3)}

    On failure, the program returns concrete evidence. Triangle evidence (u, v, w) means that edges uv, vw, and wu all exist. Four-cycle evidence (u, a, v, b) means that edges ua, av, vb, and bu all exist. Readers can manually check this evidence using an adjacency list without trusting the program’s conclusion.

    For complexity, let m be the number of edges and d the average degree, so d = 2m/n. Building the adjacency list and deduplicating edges takes O(m). The triangle check performs one set intersection per edge, costing about O(m·d). The four-cycle check enumerates n(n−1)/2 vertex pairs and performs one set intersection for each pair, costing about O(n²·d). For a graph with n=124 and m=630, d is about 10.2, so the computation is small. If some vertex has a very large degree, the cost of a single set intersection increases, but at this scale it can still be completed quickly on ordinary devices.

    2.4 Boundary: What the Program Proves

    The checking program can only confirm two things: the construction is valid, and the edge count is exactly the given value. It cannot prove that 629 is an upper bound, nor can it prove that 630 is the maximum. To show that 630 is optimal, one needs to cite a published upper-bound proof or provide a rigorous argument that others can reproduce.

    A single-edge difference requires independent reproduction. It is advisable to recompute the girth using another data structure or another implementation, and compare the result edge by edge with the original construction file. If the two results agree, this only shows that the construction is valid and the edge count is correct. If the construction has more edges than a proven upper bound, then the checking program or the construction file contains an error, and the cause should be investigated.

    3. Quantum Error-Correcting Code Case

    A quantum error-correcting code encodes k logical qubits into n physical qubits with code distance d, denoted [[n,k,d]]. The code distance determines how many errors the code can handle. A code with distance d can detect errors on any d−1 qubits and can correct errors on any ⌊(d−1)/2⌋ qubits.

    This article does not expand the specific parameters of the code in the original report; verification should rely on the original materials. For a code proposed by a model, verification proceeds in three steps.

    1. Check whether the stabilizer generators commute pairwise. A stabilizer code is generated by a set of Pauli operators. If two generators do not commute, the code space does not exist, and the construction fails immediately. On failure, provide the two generators and the qubit positions where they do not commute.
    2. Check whether the generators are independent and whether the number of independent generators is n−k. This number determines the number of logical qubits k.
    3. Compute the code distance. The code distance equals the minimum weight of a nontrivial operator in the normalizer that is not in the stabilizer group. Small codes can be verified by exhaustive search. For larger codes, compare against public code tables, such as the quantum code parameter tables maintained by Markus Grassl at codetables.de. If the model claims a distance greater than the actual value, the failure evidence is a logical operator with weight less than the claimed distance, listing its Pauli type on each qubit.

    Aspects that require human review include: whether entries in the reference code table apply to the same class of codes, for example, whether both are linear stabilizer codes; whether the model’s claimed parameters have been compared with a baseline of the same parameters in the code table; and whether the error-correction capability depends on a specific noise model. These judgments require experts with a quantum information background and cannot be replaced by a program.

    4. Unified Verification Workflow

    Verification in the two cases can be summarized as the same workflow.

    1. Identify the task type: construction, proof, or code.
    2. Fix the conventions: definitions of objects, vertex or qubit numbering, deduplication rules, and the source of the reference baseline.
    3. First check the machine-checkable parts, including validity, constraint conditions, edge count, or code parameters. On failure, output concrete evidence, such as a triangle, a four-cycle, noncommuting generators, or a low-weight logical operator.
    4. Reproduce key numbers with an independent implementation to avoid counting errors from a single implementation.
    5. Compare with published upper bounds or public code tables. If the result exceeds a proven upper bound, suspect the construction or the checking program first.
    6. Proof-type conclusions should be handed to human review. A program passing does not mean the theorem holds.

    5. Conclusion and Boundaries

    In construction-type tasks, AI can already produce checkable objects and may exceed known references on specific numbers. Verifying such results mainly relies on program checks and independent reproduction, which are low-cost and provide direct judgments.

    Conclusions in proof-type tasks still require human review. A program cannot replace the review of a proof, and an advantage in a single number cannot be treated as a new theorem or a proof of optimality. Readers should record “finding a better construction” separately from “proving a new theorem” and keep a reproducible evidence chain.