{"id":"82d6d062-8630-4758-8feb-eb2c58840cfa","arxiv_id":"2608.00900","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"F_4, the four-dimensional dual-cube, admits two completely independent spanning trees, completing the classification for all n≥4.","lead":"The paper proves that the four-dimensional dual-cube graph, the last open case in its family, contains two completely separate spanning trees. It completes the classification for all dimensions and provides a compact algebraic rule verified by a small computer program.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central claim rests on the correctness of the distributed Python verifier, which was not independently executed; a bug in F4 reconstruction or in the 8128-path check would invalidate Theorem 3.","rationale":"The paper's mathematical argument is explicit and coherent: the partition satisfies Araki's condition, the tree construction via functional orientation is valid, and the edge-count constraints are satisfied. The only load-bearing step that is not a formal derivation is the finite machine check, so the reader's identification of verifier correctness as the weakest assumption is accurate. However, the verifier is provided, simple, solver-free, and backed by a second witness; this is exactly the kind of reproducible artifact that supports a computer-assisted proof. The concern does not undermine the verdict; it simply highlights that an independent execution is a worthwhile confirmation step. Hence UNCHANGED.","tokens_in":4161,"tokens_out":8531,"duration_ms":88240,"concrete_test":"Download the repository, run the supplied verifier (`python3 verify_anf_structure.py anf-construction.json`), and then independently re-implement the verification from scratch—e.g., in SageMath/NetworkX—rebuilding F4 from the bit definition in Section 2, evaluating z, constructing T'_1 and T'_2 from the JSON edge lists, and directly checking all 8128 unordered pairs for openly disjoint paths. Also independently confirm |V1|=|V2|=64 and the component counts in Proposition 1. If the two implementations agree, the concern is settled.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 1 is established only by the verifier, and the CIST property is established only by step (iv)'s exhaustive pair check. The verifier is a hand-written Python program, not formally verified; its correctness depends on the bit-indexing of F4, the evaluation of polynomial (1), and the tree-path computation all being implemented exactly as specified in Section 2–3. The paper provides a URL but not the code in the manuscript; the second 'independently fixed' witness is mentioned but not detailed. The assertion-stripping refusal is not a flaw, but it means a naive -O run would silently skip all checks. The exact-search results in Section 5 are not load-bearing for the positive theorem, and the construction itself is mathematically coherent: the functional orientation argument is sound, and the edge counts (254/256) are consistent. Thus the only real soft spot is trust in the checker, not in the graph theory.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper settles the previously open case n=4 for the existence of two completely independent spanning trees (CISTs) in the dual-cube F_n. The construction is an explicit vertex partition defined by a ten-term cubic polynomial over F_2 in the seven vertex bits. The author proves, by a brute-force solver-free verifier, that the two induced subgraphs are connected and unicyclic, that the cut graph has two unicyclic components, and that the resulting explicit trees satisfy the CIST path-openness condition for all 8128 unordered vertex pairs. The claimed consequence is the classification: F_n admits two CISTs if and only if n≥4, using prior work for n≥5 and edge-count obstructions for n≤3. The paper also reports exact infeasibility results for simpler ANF rules, with the caveat that those results are solver-dependent and not load-bearing for the main theorem.","tokens_in":4308,"tokens_out":14747,"duration_ms":169784,"significance":"If the verification is correct, this completes the classification of CISTs in dual-cubes, resolving a case that had resisted more than 700 hours of inconclusive computation. The construction is remarkably compact—a single ten-term cubic polynomial—and the correctness check is directly tied to the definition of CIST rather than to a solver. The paper provides a public verifier, a second independently fixed witness, and honest caveats on the solver-based negative results. These are notable strengths for a computational note.","major_comments":[],"minor_comments":[{"comment":"The text states that F_4 consists of sixteen Q_3 clusters 'joined by a perfect matching of 128 cross-edges'. A perfect matching on 128 vertices contains 64 edges, and the sixteen Q_3 clusters contribute 192 edges; the total is then 256, matching the stated edge count. Please correct '128 cross-edges' to '64 cross-edges', or clarify if a different edge set is meant.","section":"Section 2, paragraph 2"},{"comment":"The proof of the main theorem rests entirely on the verifier, but the verifier code is only available at a GitHub URL. For archival and reproducibility, include the verifier and certificate as supplementary material or an appendix, with a version/checksum, and provide a compact specification (pseudocode or assertion list) of the four checks. The refusal to run under assertion-stripping mode is a useful safeguard, but the actual checks should be documented so that the finite computation is self-contained.","section":"Section 4 and Data availability"},{"comment":"The assertion that T'_1 and T'_2 are edge-disjoint spanning trees with internal-vertex sets exactly V_1 and V_2 is not proved in the text; it is only verified by the program (step iii). Since the direct CIST check in step (iv) is the load-bearing verification, this is not a mathematical gap, but a short argument (e.g., why the functional orientation prevents same-part vertices from becoming leaves) would improve readability and reduce over-reliance on inspecting the code.","section":"Section 3, tree construction"},{"comment":"Remark 1 is a useful caveat, but it should be framed as an observation rather than a claim that the approach of [7] cannot apply, since the authors state they have not consulted the full sufficient condition. The remark is not used in the proof; consider softening the wording to 'we note that the known cluster-based constructions appear not to apply'.","section":"Remark 1"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a computational existence proof and the main claim is very likely correct. The central reservation is the usual one for computer-assisted proofs: trust in the verifier. The availability of the code and a second independent witness mitigates this. I recommend that the journal archive the repository (e.g., via Zenodo) and that the final version include the verifier code or at least a complete specification of the checks. The author's explicit AI-assistance disclosure and priority disclaimer are transparent and appropriate. My recommendation is minor_revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does what it says: it closes the last open case in the dual-cube CIST classification. Lalou et al. left F4 unresolved after 700+ hours of computation; Prajapati gives an explicit ten-term cubic polynomial over F2 that partitions the 128 vertices into two valid internal-vertex sets, and the trees are pinned down in a certificate. That is a genuinely new result, and the construction is compact enough to print. The edge-count observation (254 of 256 edges used, balanced 64/64 internal sets) is a nice check that the construction is tight.\n\nThe strongest feature is the verification story. The verifier is solver-free, uses only the Python standard library, rebuilds F4 from the bit definition, evaluates the polynomial, reconstructs the trees, and checks all 8128 vertex pairs directly against the definition of complete independence. So the positive theorem does not rest on Theorem 2 or on the search software that found the polynomial. The paper is also honest about the limits of the negative results: the exact infeasibility claims in Section 5 are scoped to the exact-complement model and are solver-dependent, and the author says so plainly. The AI-assistance disclosure and the refusal to claim priority pending expert review are refreshingly straightforward.\n\nThe soft spots are minor and are exactly what the stress-test note identified. The central claim is proven by a finite computation delegated to a Python program that I have not run. A bug in the bit indexing, in the polynomial evaluation, or in the path-computation step would invalidate Theorem 3. The code is not printed in the manuscript, only distributed via a URL. That is the one load-bearing assumption, and it is the kind of thing a referee should check by actually running the one-command verifier. The paper's own note that the verifier refuses to run under assertion-stripping -O mode is a sensible safeguard, not a flaw. The remark about not having access to the full sufficient condition in [7] is a minor gap; it does not affect the proof. The negative search results are not load-bearing for the main theorem, so even if the solver had a bug, the classification still follows from Proposition 1 and Theorem 2.\n\nI think the paper deserves a serious referee and, if the verifier runs cleanly, publication. The work is narrow—it completes a classification in a specific interconnection-network literature—but it is correct in its own terms and provides reproducible artifacts. I would bring it to a reading group on algorithmic graph theory or computational proof certificates, but only if the group cares about CIST constructions or machine-checked finite certificates. For my own work, I would not cite it in the next year unless I were working on dual-cube variants, but I would want it in the record. Send it to peer review.","headline":"Settles the F4 CIST case with a clean finite certificate; the only real risk is the unchecked verifier, which is one command away.","tokens_in":4816,"tokens_out":971,"would_cite":false,"duration_ms":12863,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C05","05C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper constructs two completely independent spanning trees in the four-dimensional dual-cube, completing the classification: F_n admits such a pair if and only if n≥4.","keywords":["dual-cube","completely independent spanning trees","F_4","explicit construction","algebraic normal form","graph partition","verification certificate","interconnection networks"],"falsifier":"Run an independent implementation of the verification—rebuilding $F_4$ from its definition, evaluating the polynomial, reconstructing the two trees, and checking all 8128 path pairs—in a separate language; the claim fails if any pair of tree paths shares a vertex other than its endpoints, or if $F_4[V_1]$ or $F_4[V_2]$ is disconnected.","tokens_in":3971,"feed_emoji":"🌳","tokens_out":10243,"duration_ms":99107,"temperature":0.7,"pith_summary":"This paper settles the last open case in the existence question for two completely independent spanning trees (CISTs) in the dual-cube family. The four-dimensional dual-cube $F_4$, a 4-regular graph on 128 vertices, was the only unresolved dimension after earlier work had proved existence for $n\\ge 5$ and impossibility for $n\\le 3$. The author constructs two such trees explicitly: their internal-vertex sets are the two sides of a partition defined by a single ten-term cubic polynomial over $\\mathbb{F}_2$ in the seven vertex bits. Correctness is reduced to finite connectivity checks, which a small solver-free Python verifier performs exhaustively, including all 8128 path pairs. The result completes the classification: $F_n$ admits two CISTs if and only if $n\\ge 4$.","feed_headline":"Ten-term polynomial settles all dual-cube spanning-tree cases","feed_subtitle":"With F_4 solved, dual-cubes have two completely independent spanning trees exactly when n≥4.","key_machinery":"The central object is the partition $\\{V_1,V_2\\}$ defined by the ten-term cubic algebraic-normal-form polynomial $z$ over $\\mathbb{F}_2$ (equation 1), evaluated on the seven bits of each vertex of $F_4$. The mechanism that turns this partition into trees is the partition characterization of completely independent spanning trees: two CISTs exist exactly when the two induced subgraphs are connected and the cut subgraph between them has no tree component. Here the cut subgraph has two unicyclic components, so no tree component; the explicit tree edges are then read off by removing one cycle edge per side and orienting cut edges functionally. The polynomial is what makes the finite verification","core_discovery":"The central claim is Theorem 3: $F_4$ admits two completely independent spanning trees. The proof uses the partition characterization: a graph has two CISTs exactly when its vertices split into two connected induced subgraphs whose connecting cut subgraph has no tree component. The paper exhibits such a partition through a ten-term cubic polynomial over $\\mathbb{F}_2$: $V_1=\\{v:z(v)=1\\}$ and $V_2=\\{v:z(v)=0\\}$. The induced subgraphs are connected, each with 64 vertices and 64 edges, and the bipartite cut graph has two unicyclic components. Removing the unique cycle edge from each side and orienting cut edges yields two edge-disjoint spanning trees whose internal-vertex sets are exactly $V_1$","pith_inferences":["- An algebraically defined partition of this kind could be tried for three or more completely independent spanning trees in higher-dimensional dual-cubes, which remains an open conjecture.","- The ten-term minimality bound is relative to the exact-complement model in which every vertex is internal in exactly one tree; allowing some vertices to be leaves in both trees might admit a simpler rule, so the bound is not yet a universal lower bound.","- Because the positive certificate is verified by a solver-free program, its finite checks could be translated into a formal proof-assistant development, removing reliance on the verifier's correctness.","- The compound structure $F_4=K_{8,8}(Q_3)$ blocks per-cluster constructions, so the global polynomial partition demonstrates a way past cluster-level obstructions in other compound graphs."],"forward_implications":["- The classification is complete: $F_n$ admits two completely independent spanning trees if and only if $n\\ge 4$.","- The pair in $F_4$ is maximally edge-efficient: the two trees jointly use 254 of the graph's 256 edges, leaving exactly two edges unused.","- The certificate is independently checkable: a short solver-free program rebuilds $F_4$ from its bit definition and verifies all 8128 vertex-pair paths directly against the definition of complete independence.","- Within the search model, no affine or quadratic rule of the same shape works, and ten terms is the minimum for a cubic rule, so the constructed polynomial is near-minimal among ruled partitions."],"supporting_citations":[{"why":"Supplies the characterization of completely independent spanning trees via edge-disjointness and internal vertices, used to count edges and internal-vertex patterns in $F_4$.","marker":"[1]"},{"why":"Gives the vertex-partition criterion that reduces existence of two CISTs to connected induced subgraphs and a treeless cut graph.","marker":"[3]"},{"why":"Introduces the dual-cube $F_n$ and fixes the vertex set and edge structure of $F_4$.","marker":"[4]"},{"why":"Restates the partition criterion in the form the paper applies to construct the two trees.","marker":"[8]"},{"why":"Proves existence for $n\\ge 5$ and impossibility for $n\\le 3$, leaving $F_4$ as the open case settled here.","marker":"[9]"}],"fun_headline_variants":["Explicit construction settles F_4 spanning-tree case","Ten-term cubic polynomial solves dual-cube CIST problem","F_4 dual-cube now has two independent spanning trees","Classification complete: dual-cubes have CISTs for n≥4","Machine-verified polynomial cracks last dual-cube case"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The load-bearing premise is that the Python verifier correctly implements the bit-level definition of $F_4$ and the tree-path computations; the paper supplies the program but not a formal proof of the verifier's correctness, so a bug there would invalidate the central claim.","fun_headline_variants_meta":{"raw":{"variants":["Explicit construction settles F_4 spanning-tree case","Ten-term cubic polynomial solves dual-cube CIST problem","F_4 dual-cube now has two independent spanning trees","Classification complete: dual-cubes have CISTs for n≥4","Machine-verified polynomial cracks last dual-cube case"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000214,"raw_usage":{"total_tokens":1272,"prompt_tokens":761,"completion_tokens":511,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":505,"completion_tokens_details":{"reasoning_tokens":428}},"tokens_in":505,"tokens_out":511,"duration_ms":5600,"temperature":1.0,"reasoning_tokens":428,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T00:41:40.085152+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an independent implementation of the verification—rebuilding $F_4$ from its definition, evaluating the polynomial, reconstructing the two trees, and checking all 8128 path pairs—in a separate language; the claim fails if any pair of tree paths shares a vertex other than its endpoints, or if $F_4[V_1]$ or $F_4[V_2]$ is disconnected.","supporting_citations":[{"cited_title":"Hasunuma, Completely independent spanning trees in the underlying graph of a line digraph,Discrete Math.234 (2001) 149–157","cited_arxiv_id":null,"evidence_quote":"Supplies the characterization of completely independent spanning trees via edge-disjointness and internal vertices, used to count edges and internal-vertex patterns in $F_4$."},{"cited_title":"Araki, Dirac’s condition for completely independent spanning trees,J","cited_arxiv_id":null,"evidence_quote":"Gives the vertex-partition criterion that reduces existence of two CISTs to connected induced subgraphs and a treeless cut graph."},{"cited_title":"Li and S","cited_arxiv_id":null,"evidence_quote":"Introduces the dual-cube $F_n$ and fixes the vertex set and edge structure of $F_4$."},{"cited_title":"Qin, R.-X","cited_arxiv_id":null,"evidence_quote":"Restates the partition criterion in the form the paper applies to construct the two trees."},{"cited_title":"Constructing two completely independent spanning trees in the dual-cube","cited_arxiv_id":"2607.25917","evidence_quote":"Proves existence for $n\\ge 5$ and impossibility for $n\\le 3$, leaving $F_4$ as the open case settled here."}],"review_version":1}