{"id":"19a9859f-e89a-4bd8-8301-e7482950b623","arxiv_id":"2411.16904","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Cubic polycirculant nut graphs exist for infinitely many orders precisely when the number of orbits is 3, 6, 7, or at least 9; they do not exist for 1, 2, 4, or 5, and the case of 8 remains open.","lead":"This paper settles, except for one open case, which cubic graphs with a cyclic symmetry can be nut graphs, meaning their adjacency matrix has a one-dimensional kernel whose vectors have no zero entries. The result extends a recent classification and supplies infinite families of such graphs, using both explicit constructions and a computer-assisted search.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The nonexistence of cubic 4- and 5-circulant nut graphs rests on an unpinned SageMath script with no output log or certificate; this is the most load-bearing unverified step in Theorem 2.","rationale":"I checked the cyclotomic factorizations in Propositions 10 and 13 and the index arithmetic in Lemmas 9 and 12; they are consistent. Lemma 15's pre-subdivision argument is plausible and the orbit-magnitude condition for iterating it is stated. The weakest point is verifiability of the computer-assisted nonexistence, exactly as the reader identified. The paper's own text points to the repository rather than proving the enumeration, and the absence of a pinned version or certificate makes the negative result depend on an external artifact. This does not reveal a mathematical error, but it justifies a conditional acceptance pending reproducible computational evidence. The reader's verdict stands.","tokens_in":16570,"tokens_out":29146,"duration_ms":257782,"concrete_test":"Pin the GitHub repository to a specific commit and run the script in a clean SageMath 9.5 environment, recording all output and hashes. Independently regenerate the connected subcubic graphs on 4 and 5 vertices with nauty's geng, add all combinations of loops, semi-edges, and parallel edges under the paper's stated constraints, and verify the counts Q(4)=12 and Q(5)=22. Then, for each quotient pregraph, independently enumerate every admissible sign matrix B (first nonzero entry of each row positive) and solve the ILP for a positive null vector, and produce a certificate or exhaustive log for each pregraph. If the independent implementation reproduces Theorem 8, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim's negative half — Theorem 8, no cubic 4- or 5-circulant nut graph — is not supported by a hand-checkable derivation. It depends wholly on the SageMath script in [1] to (i) enumerate all connected cubic quotient pregraphs of order 4 and 5 and (ii) for each pregraph X, check Proposition 6 and run the ILP from Proposition 7 over every sign matrix B with |B|=A(X). The paper reports the counts Q(4)=12, Q(5)=22 and sketches the enumeration, but the linked repository has no commit hash, no output log, and no certificates. A missing pregraph class (for instance, an overlooked loop/semi-edge placement in the quotient) or an incomplete sign-pattern enumeration in the ILP would silently destroy the conclusion. Since Theorem 2's new nonexistence results are exactly ℓ=4,5, this external computational step is the most load-bearing assumption in the paper. The positive constructions in Sections 4–6 are explicitly checkable and appear sound; the ℓ=3 base relies on the published classification [12], which is less fragile than the unpinned script.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies cubic ℓ-circulant nut graphs, i.e., cubic nut graphs admitting a cyclic automorphism group with ℓ equal-sized vertex orbits. Its main theorem states that cubic ℓ-circulant nut graphs do not exist for ℓ = 1, 2, 4, 5 and exist in infinitely many instances for every ℓ in {3, 6, 7} or ℓ ≥ 9, leaving only ℓ = 8 open. The proof combines a computer-assisted search over cubic quotient pregraphs of order 4 and 5 (Sections 2–3), explicit voltage-graph constructions for cubic 7- and 11-circulant nut graphs with cyclotomic polynomial criteria (Sections 4–5), and a \"pre-subdivision\" operation that increases the number of orbits by three and is iterated to cover the remaining congruence classes (Section 6). The case ℓ = 3 is imported from the authors' earlier classification of cubic tricirculant nut graphs [12].","tokens_in":16743,"tokens_out":12333,"duration_ms":110325,"significance":"If the main theorem is correct, the paper resolves the cubic polycirculant nut-graph existence question for every orbit count except ℓ = 8, a substantial advance over the previously known cubic 1-, 2-, and 3-circulant cases. The positive constructions are explicit and checkable by hand: each family is verified through elementary reductions to root-of-unity conditions, and the cyclotomic divisibility arguments are sound. The pre-subdivision construction is a simple and potentially reusable mechanism for increasing the orbit count. The principal weakness is that the negative results for ℓ = 4, 5 are not backed by machine-checkable certificates in the manuscript, and several assertions about the magnitude condition required for iteration are not proved here. With those gaps closed, the paper would be a strong contribution.","major_comments":[{"comment":"The nonexistence of cubic 4- and 5-circulant nut graphs is established only by the statement that running the SageMath script from [1] yields this result. The manuscript provides the counts Q(4) = 12 and Q(5) = 22 and a description of the two-step test (Propositions 6 and 7), but it does not include the code, a commit hash, an output log, or machine-checkable certificates for the per-pregraph ILP checks. Since Theorem 8 is the entire support for the negative half of Theorem 2 for ℓ = 4, 5, this is a load-bearing verification gap; please provide reproducible scripts with versioned repository contents, full output logs, certificates, or an independent verification of the enumeration and of the absence of positive null vectors.","section":"Section 3, Theorem 8"},{"comment":"The claim that all Zn-voltage pregraphs of order three from [12, Theorems 2, 11 and 14] satisfy the hypothesis of Lemma 15 (two adjacent orbits of different magnitudes) is asserted without proof or a precise quotation. This condition is needed to obtain infinitely many cubic ℓ-circulant nut graphs for ℓ = 3, 6, 9, 12, ...; please supply a short argument or exact references to the statements in [12] that imply it.","section":"Proof of Theorem 2, final paragraph"},{"comment":"The preservation of the different-magnitude condition under the pre-subdivision construction is asserted without proof: the text states that if the starting pregraph satisfies the condition, then so does the constructed pregraph. Since the construction is iterated to obtain ℓ = 10, 13, ... and ℓ = 14, 17, ..., this claim is load-bearing; please add the short magnitude computation or state explicitly which adjacent pair in the constructed pregraph has different magnitudes.","section":"Section 6, paragraph after Lemma 15"}],"minor_comments":[{"comment":"In the second paragraph of the proof, the polynomial should be 2x^2 - x + 2, not 2x^2 + x + 2, matching the factorization (x + 1)^2 (2x^2 - x + 2).","section":"Proposition 10, first case"},{"comment":"The phrase 'Theorem 1 and Proposition 8' should read 'Theorem 1 and Theorem 8', since Proposition 8 is not stated in the paper.","section":"Proof of Theorem 2"},{"comment":"The notation '2 | α, β' is ambiguous; it should be written as '2 divides α and β' or 'α and β are even'.","section":"Lemma 12"},{"comment":"The GitHub repository link should include a commit hash or version identifier so that the computational results are reproducible.","section":"Reference [1]"},{"comment":"The sentence 'It is obvious that the vertices y1, y2, y3 cannot all reside in the same orbit' could benefit from a one-sentence justification, since the argument is short but not completely immediate.","section":"Proof of Proposition 7"}],"recommendation":"major_revision","confidential_remarks":"The paper is a good fit for a combinatorics journal and the positive results appear sound. The main obstacle is the reproducibility of Theorem 8; please ask the authors to provide certificates, output logs, and a versioned repository before publication. The unsupported magnitude-condition assertions in the proof of Theorem 2 and Section 6 should also be addressed, as they are needed for the infinite families."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nThe short version: this paper settles the cubic ℓ-circulant nut graph existence question for every ℓ except 8, and the new positive constructions are solid, checkable mathematics. The negative results for ℓ=4 and 5, though, rest on an unpinned SageMath script, and that is the one thing I'd want shored up before I'd trust Theorem 2 completely.\n\nWhat's genuinely new: the nonexistence of cubic 4- and 5-circulant nut graphs, the infinite families for ℓ=7 and 11, and the pre-subdivision operation that lifts a cubic ℓ-circulant nut graph to a cubic (ℓ+3)-circulant one. The framework—voltage pregraphs and orbit-magnitude analysis—comes from prior work, especially [12], but the extension is real and the constructions are not hidden behind the computer.\n\nThe paper's best moments are Lemmas 9 and 12, which reduce the nut condition to a clean root-of-unity statement, and then to explicit cyclotomic factorizations. Those are hand-checkable. Lemma 15 is also elegant: it shows that if two adjacent orbits have different magnitudes, you can subdivide one edge with three new orbits and keep the nut property. That's a reusable tool.\n\nWhere I hesitate: Theorem 8, the nonexistence part, is the load-bearing claim and it is entirely computer-assisted. The authors link to a GitHub repository with no commit hash, no output log, and no certificates. The paper describes the enumeration and the ILP check, but a missing pregraph class or a bug in the sign-matrix enumeration would silently flip the result. This is not a fatal objection—I don't have evidence the code is wrong—but it is a verifiability gap. A second implementation or a certificate would close it.\n\nThe other soft spot is small: the proof of Theorem 2 inherits a magnitude condition for the 3-circulant pregraphs from [12] without restating or proving it. That's a citation, not a new gap, but it would help to make the dependency explicit.\n\nWho this is for: people working on nut graphs, regular graph existence problems, and circulant covers. It won't change practice outside that niche, but within it, it resolves an open case and gives a clean construction. I'd send it to a serious referee. I'd also ask the authors to pin their code, add an output log, and ideally a machine-checkable certificate for the 4- and 5-case before acceptance.","headline":"A clean extension of the cubic polycirculant nut graph classification; the positive constructions are solid, but the ℓ=4,5 nonexistence rests on an unpinned Sage script and should be strengthened before publication.","tokens_in":17318,"tokens_out":2490,"would_cite":true,"duration_ms":23022,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C25","11C08"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that cubic, 3-regular nut graphs with a cyclic symmetry having ℓ equal-sized vertex orbits exist for ℓ=3, 6, 7 and every ℓ≥9, and do not exist for ℓ=1, 2, 4, or 5, leaving ℓ=8 as the only open case.","keywords":["nut graph","polycirculant graph","cubic graph","pregraph","voltage graph","circulant graph","null space","integer linear programming"],"falsifier":"Exhibit one cubic 4- or 5-circulant nut graph, or independently re-run the authors' enumeration and find a quotient pregraph it omits or a positive-kernel sign matrix it rejects; either would break Theorem 8 and hence the negative half of Theorem 2.","tokens_in":16338,"feed_emoji":"🕸️","tokens_out":16849,"duration_ms":136273,"temperature":0.7,"pith_summary":"A nut graph is a simple graph whose adjacency matrix has a one-dimensional kernel spanned by a vector with no zero entries; an $\\ell$-circulant graph is one with a cyclic automorphism group acting with $\\ell$ vertex orbits of equal size. The paper proves that cubic (3-regular) nut graphs exist in abundance for most orbit counts: infinitely many cubic $\\ell$-circulant nut graphs exist for $\\ell=3,6,7$ and for every $\\ell\\ge 9$, while none exist for $\\ell=1,2,4,5$. This settles the cubic polycirculant nut graph existence problem for every orbit count except $\\ell=8$, which the paper leaves as a conjecture of nonexistence. The proof combines a computer-assisted enumeration of quotient pregraphs with explicit voltage-graph constructions and a pre-subdivision operation that adds three vertex orbits while preserving the nut property. If the proof is right, the possible symmetry types of cubic nut graphs are now essentially charted.","feed_headline":"No 1-,2-,4-,5-orbit cubic nut graphs; every other settled count works","feed_subtitle":"Counts 1, 2, 4, and 5 are impossible; every other settled count has infinitely many examples, leaving only the 8-orbit case open.","key_machinery":"The load-bearing object is the cyclic voltage pregraph: a pregraph whose darts carry labels in a cyclic group, so that its derived graph is automatically $\\ell$-circulant with all orbits of equal size. The null space of the derived graph is controlled by orbit magnitudes, the common absolute value of a kernel vector on each orbit. Proposition 7 turns possible nutness into a finite linear algebra test: a quotient pregraph can yield a nut graph only if some sign matrix $B$ with $|B|=A(X)$ has a positive null vector, which is checked by integer linear programming. On the construction side, Lemmas 9 and 12 reduce the nut condition for the built families to a cyclotomic-polynomial criterion: an explicit polynomial must have only $-1$ as a root among the $n$-th roots of unity. The pre-subdivision construction then inserts three new vertices into any edge whose endpoint orbits have different magnitudes, raising $\\ell$ by 3 while keeping the kernel one-dimensional and full.","core_discovery":"The central claim, Theorem 2, is a dichotomy for cubic $\\ell$-circulant nut graphs: $\\ell\\in\\{1,2,4,5\\}$ is impossible, while $\\ell=3,6,7$ or $\\ell\\ge 9$ yields infinitely many examples. The paper models every cubic $\\ell$-circulant graph as the derived graph of a cyclic voltage pregraph on $\\ell$ vertices. For $\\ell=4$ and $\\ell=5$, it enumerates all connected cubic quotient pregraphs (12 and 22 of them, respectively) and uses an orbit-magnitude argument to show none can give a nut graph. For the positive half, it constructs explicit voltage pregraphs producing infinite families of 7- and 11-circulant nut graphs, then proves a pre-subdivision lemma: replacing an edge whose endpoint orbits have different magnitudes by a three-vertex path raises $\\ell$ by 3 and preserves the nut property. Iterating this lemma from the $\\ell=3$, $\\ell=7$, and $\\ell=11$ families covers every $\\ell\\ge 9$, leaving $\\ell=8$ as the sole open case, which the authors conjecture to be empty.","pith_inferences":["Because the paper tabulates 534 quotient pregraphs for $\\ell=8$, the same enumeration pipeline is immediately applicable to test the open case; making the computer search independently verifiable would turn the $\\ell=4$ and $\\ell=5$ result into a checkable proof.","The pre-subdivision construction only needs two adjacent orbits of different magnitudes, so the same mechanism could generate infinite orbit-count families in higher-degree regular nut graphs, though the paper stays with the cubic case.","The cyclotomic-polynomial criterion behind Lemmas 9 and 12 looks like a general recipe: build a voltage pregraph whose null space reduces to a circulant matrix, then prove the corresponding polynomial has only $-1$ as a root of unity. That recipe may help attack the open degree-order-orbit problem stated as Problem 17."],"forward_implications":["Every $\\ell$ except 8 is now decided: 1, 2, 4, and 5 are impossible, and 3, 6, 7, and all $\\ell\\ge 9$ have infinitely many cubic nut graphs.","The pre-subdivision lemma can be applied repeatedly, so from any eligible seed there are infinite families at $\\ell$, $\\ell+3$, $\\ell+6$, ...; this covers the progressions 3, 6, 9, ..., 7, 10, 13, ..., and 11, 14, 17, ....","The nonexistence for $\\ell=4$ and $\\ell=5$ is a finite computation: all connected cubic quotient pregraphs of order 4 and 5 (12 and 22 of them) are inspected, and none can carry a positive kernel vector.","The constructions give concrete orders: a 7-orbit nut graph of order $7n$ for every even $n\\ge 4$, and an 11-orbit nut graph of order $11n$ for every $n\\ge 6$ with $n\\equiv 2 \\pmod 4$.","The only remaining orbit count is $\\ell=8$; Conjecture 16 states that no cubic 8-circulant nut graph exists."],"supporting_citations":[{"why":"the authors' supplementary computer script that performs the exhaustive enumeration and ILP checks used to prove nonexistence for $\\ell=4$ and $\\ell=5$.","marker":"[1]"},{"why":"Theorem 1 of this paper resolves the circulant nut graph order-degree problem and gives the no-cubic-circulant result used for $\\ell=1$.","marker":"[10]"},{"why":"provides the classification of cubic tricirculant nut graphs, the $\\ell=2$ nonexistence, and the infinite $\\ell=3$ family used as seeds, along with Lemma 3.","marker":"[12]"},{"why":"supplies the graph generation routine that enumerates all connected subcubic graphs on $\\ell$ vertices, from which quotient pregraphs are built.","marker":"[22]"},{"why":"introduces nut graphs and supplies Lemma 4 (nut graphs are connected, nonbipartite, and leafless), used to reduce to connected quotient pregraphs.","marker":"[35]"},{"why":"supplies Lemma 5 on constant or alternating values along automorphism orbits, which grounds the orbit-magnitude analysis.","marker":"[7]"},{"why":"gives the cyclotomic-polynomial irreducibility fact used to verify that the constructed polynomials have only $-1$ as a root of unity.","marker":"[19]"},{"why":"supplies the pregraph and voltage-cover definitions on which the quotient model of $\\ell$-circulant graphs rests.","marker":"[20]"}],"fun_headline_variants":["No cubic nut graphs for 1,2,4,5 orbits; all others except 8 exist infinitely","Cubic nut graphs: 1,2,4,5 impossible, 3,6,7,9+ infinite, 8 open","Infinitely many cubic nut graphs for most orbit counts; 8 is only gap","Cubic circulant nut graphs: four banned counts, all but 8 have infinite families","No 1,2,4,5-orbit cubic nut graphs; every other count infinite except 8"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The nonexistence for 4 and 5 orbits hangs on the authors' computer program being exhaustive and correct; the paper gives no independent certificate that the search missed nothing.","fun_headline_variants_meta":{"raw":{"variants":["No cubic nut graphs for 1,2,4,5 orbits; all others except 8 exist infinitely","Cubic nut graphs: 1,2,4,5 impossible, 3,6,7,9+ infinite, 8 open","Infinitely many cubic nut graphs for most orbit counts; 8 is only gap","Cubic circulant nut graphs: four banned counts, all but 8 have infinite families","No 1,2,4,5-orbit cubic nut graphs; every other count infinite except 8"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000608,"raw_usage":{"total_tokens":2866,"prompt_tokens":1016,"completion_tokens":1850,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":632,"completion_tokens_details":{"reasoning_tokens":1717}},"tokens_in":632,"tokens_out":1850,"duration_ms":12476,"temperature":1.0,"reasoning_tokens":1717,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:46:31.651280+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit one cubic 4- or 5-circulant nut graph, or independently re-run the authors' enumeration and find a quotient pregraph it omits or a positive-kernel sign matrix it rejects; either would break Theorem 8 and hence the negative half of Theorem 2.","supporting_citations":[{"cited_title":"Baˇ si´ c and I","cited_arxiv_id":null,"evidence_quote":"the authors' supplementary computer script that performs the exhaustive enumeration and ILP checks used to prove nonexistence for $\\ell=4$ and $\\ell=5$."},{"cited_title":"Damnjanovi´ c, Complete resolution of the circulant nut gra ph order–degree existence problem, Ars Math","cited_arxiv_id":null,"evidence_quote":"Theorem 1 of this paper resolves the circulant nut graph order-degree problem and gives the no-cubic-circulant result used for $\\ell=1$."},{"cited_title":"Damnjanovi´ c, N","cited_arxiv_id":null,"evidence_quote":"provides the classification of cubic tricirculant nut graphs, the $\\ell=2$ nonexistence, and the infinite $\\ell=3$ family used as seeds, along with Lemma 3."},{"cited_title":"Cvetkovi´ c, M","cited_arxiv_id":null,"evidence_quote":"supplies Lemma 5 on constant or alternating values along automorphism orbits, which grounds the orbit-magnitude analysis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the cyclotomic-polynomial irreducibility fact used to verify that the constructed polynomials have only $-1$ as a root of unity."},{"cited_title":"Malniˇ c, D","cited_arxiv_id":null,"evidence_quote":"supplies the pregraph and voltage-cover definitions on which the quotient model of $\\ell$-circulant graphs rests."}],"review_version":1}