{"id":"1add0e92-6ff8-412b-8943-a104390255a7","arxiv_id":"1908.04551","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every finite non-abelian group admits a non-Cayley Haar graph, except the dihedral groups of orders 6, 8, and 10, the quaternion group Q8, and Q8 × Z2.","lead":"This paper settles an open problem about two kinds of graphs built from finite groups, showing that for essentially every non-abelian group one can build a Haar graph that is not a Cayley graph. The only exceptions are five small groups, which is a complete and explicit answer.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The classification hinges on unshipped Magma computations in Lemma 3.3 and Lemma 4.1; if any finite-case check is wrong, Theorem 1.4 could include or exclude the wrong groups. Independent reimplementation is required.","rationale":"The reader assigned CONDITIONAL mainly because of unshipped Magma computations and reliance on Proposition 2.3. After reading the proof, I find the analytic parts internally consistent: Lemma 3.1 is fully proved, Lemma 3.2 has a complete analytic proof for p≥7, and the case splits in Lemma 4.2 appear valid, including the order-2p^2 classification and the minimal-counterexample arguments. The single most load-bearing unresolved step is the set of finite computer checks, because they are specific, unverified, and directly responsible for several inclusions and exclusions in the classification. Proposition 2.3 is also load-bearing, but it is a published theorem from [10] and is not something this paper must prove; still, an independent check of Proposition 2.3 would be desirable. Since the reader already conditioned acceptance on verifiability, I do not move the verdict; I recommend keeping CONDITIONAL until the computational claims are available or reproduced.","tokens_in":16032,"tokens_out":33291,"duration_ms":295410,"concrete_test":"Write a GAP/Magma script that reproduces every finite claim: (1) for each row i=1..9 in Lemma 3.3, construct H(G_i,S_i), compute Aut, and verify it is not vertex-transitive and has no regular subgroup; (2) enumerate all subsets S⊆Q8×Z2 containing 1 up to Aut(Q8×Z2), build H(Q8×Z2,S), and for each connected graph test whether Aut contains a regular subgroup; (3) repeat Lemma 3.2 for p=3 and p=5. If all tests pass, the computational support for Theorem 1.4 is confirmed; if any fails, the corresponding classification step collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 2.3 is an external published theorem and is not the first place to push. The proof of Theorem 1.4 contains several finite computations that are asserted without proof or accompanying code: Lemma 3.2 verifies p=3,5 for Q8×Z_p by Magma; Lemma 3.3 lists nine groups and states that each corresponding Haar graph is not vertex-transitive and G∉BC, with no proof; Lemma 4.1 asserts by Magma that all connected Haar graphs of Q8×Z2 are Cayley. These checks are load-bearing: Lemma 4.1 Case 2 eliminates four of the six order-16 candidates via rows 1–4 of Lemma 3.3 and Case 3 eliminates Q8×Z2×Z2 via row 5; Lemma 4.2 relies on rows 6, 8 and 9 to exclude Q8⋊Z3, F20 and Z_p^2⋊Z2. If any row in Lemma 3.3 is incorrect, or if the connected-Q8×Z2 check misses a non-Cayley Haar graph, then the list in Theorem 1.4 is wrong: a group not isomorphic to the five could enter BC, or Q8×Z2 could drop out. No code or detailed output is supplied, so the argument is not independently checkable as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper solves Problem 1.1 of Estélyi and Pisanski by classifying the finite non-abelian groups H with the property that every Haar graph of H is a Cayley graph. The main theorem states that the only such groups are D6, D8, D10, Q8 and Q8 × Z2. The proof has two parts: Section 3 constructs non-vertex-transitive Haar graphs that are therefore non-Cayley, using two infinite families (Lemmas 3.1 and 3.2) and a table of nine small examples (Lemma 3.3); Section 4 gives structural reductions within the class BC, first for non-abelian 2-groups (Lemma 4.1) and then for non-abelian {2,p}-groups (Lemma 4.2), before the final argument in Theorem 1.4 handles groups with several odd prime divisors. The analytic portions are detailed stabilizer computations, while several finite checks are delegated to Magma without supplying code or output.","tokens_in":16307,"tokens_out":14835,"duration_ms":128350,"significance":"If the computational assertions are correct, Theorem 1.4 resolves a natural open problem and extends the previously known cases for dihedral groups and inner-abelian groups. The paper also gives the first complete list of non-abelian groups with no GHRR, which is relevant to Problem 1.6. The hand-written parts are substantial and careful: Lemma 3.1 is proved by an explicit stabilizer argument, Lemma 3.2 contains a long analytic proof for p ≥ 7, and the reduction scheme in Section 4 is structurally sound, making good use of the published BC framework from [10]. The main weakness is reproducibility: Lemma 3.2 for p = 3, 5, the nine rows of Lemma 3.3, and the connected case of Lemma 4.1 for Q8 × Z2 are asserted only as Magma computations, with no code, transcript, or detailed output. These checks are load-bearing for the central classification, so the manuscript as submitted is not fully independently verifiable.","major_comments":[{"comment":"For p = 3 and 5 the proof is contained entirely in the sentence 'The lemma holds for p = 3 and 5 by Magma [5]'. These two primes are not covered by the analytic argument that follows, which assumes p ≥ 7, and no code, input data, or output is supplied. Since Lemma 3.2 is used to rule out Q8 × Zp for all odd p in Lemma 4.2 Case 1 and hence in Theorem 1.4, please replace this assertion by a hand proof or supply the Magma program and a transcript of its output for p = 3 and 5.","section":"Section 3, Lemma 3.2"},{"comment":"Lemma 3.3 asserts, for nine explicitly presented groups, that the corresponding Haar graph is not vertex-transitive and that the group is not in BC, with the only justification being that this 'can be checked easily by the computer software Magma'. These rows are load-bearing: rows 1-4 eliminate four of the six order-16 candidates in Lemma 4.1 Case 2, row 5 eliminates Q8 × Z2 × Z2 in Lemma 4.1 Case 3, and rows 6, 8 and 9 eliminate Q8 ⋊ Z3, F20 and Zp^2 ⋊ Z2 in Lemma 4.2. As written, the proof of Theorem 1.4 is not independently verifiable without recomputing all nine rows; please include code and full output, or give explicit stabilizer arguments, for each row.","section":"Section 3, Lemma 3.3"},{"comment":"In the proof of the sufficiency for Q8 × Z2, the connected case is dispatched by 'a computation by Magma [5] shows that all connected Haar graphs of Q8 × Z2 are Cayley graphs'. This is a finite but nontrivial enumeration, since S ranges over subsets of Q8 × Z2 containing the identity and generating the whole group, and a single missed non-Cayley example would remove Q8 × Z2 from the classification in Theorem 1.4. Please provide the Magma code, the exact list of connected S values, and the output confirming that each resulting Haar graph is Cayley, or provide a conceptual proof.","section":"Section 4, Lemma 4.1"},{"comment":"Proposition 2.3 is the structural backbone of the proof of Theorem 1.4: it supplies solvability, the condition on odd Sylow subgroups, and the existence of a D6/D8/D10/Q8 subgroup. Since it is quoted from [10], an earlier paper by the same authors, I ask that the authors indicate precisely which results in [10] yield each of (i)-(iii) and state why those results are independent of the classification completed in the present paper. I do not see a circularity in the statements themselves, but the manuscript should make the logical dependency explicit for the reader.","section":"Section 2, Proposition 2.3"}],"minor_comments":[{"comment":"In the paragraph following Eq. (6), 'anb by Eq. (1)' should read 'and by Eq. (1)'.","section":"Section 3, Lemma 3.2"},{"comment":"The presentation 'ac = b^{±1}, bc = a^{±1}b' is ambiguous; please specify whether both signs are allowed simultaneously or whether a single choice is meant.","section":"Section 3, Lemma 3.3, row 6"},{"comment":"The equality 'P2 = C_H(P2) = N_H(P2)' when P2 is abelian, of prime index, and not normal is correct, but it deserves a one-line justification because it is the step that triggers Burnside's p-nilpotency criterion.","section":"Section 4, Lemma 4.2, Case 2, Claim 1"},{"comment":"The sentence 'It seems difficulty to construct vertex-transitive non-Cayley Haar graphs' should read 'It seems difficult to construct ...'.","section":"Section 1, paragraph 4"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the main risk is reproducibility, not mathematical plausibility. The hand-written stabilizer arguments in Lemmas 3.1 and 3.2 (for p ≥ 7) appear careful and internally consistent, and the reductions in Section 4 are structurally sound. The three unshipped Magma computations are genuinely load-bearing: Lemma 3.2 for p = 3, 5, all nine rows of Lemma 3.3, and the connected Q8 × Z2 enumeration in Lemma 4.1. If those checks have been performed correctly, the classification is very likely correct. I recommend major revision so that the computational evidence is either supplied in full or replaced by explicit arguments, and so that the logical dependency on Proposition 2.3 from the authors' earlier paper [10] is stated explicitly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is the complete classification the field has been waiting for, and I'd bet the theorem is right, but the manuscript as written hides several load-bearing finite checks inside unshipped Magma computations. The referee should not desk-reject it; they should ask for code or output.\n\nThe new content is real. Estelyi and Pisanski solved the dihedral case; Feng, Kovacs, and Yang handled inner abelian groups. This paper closes the gap: if every Haar graph of a finite non-abelian H is Cayley, then H is D6, D8, D10, Q8, or Q8×Z2, and it shows those five actually have the property. The sufficiency for Q8×Z2 (Lemma 4.1) is the missing piece from the earlier work. The two infinite families of non-Cayley Haar graphs (Lemmas 3.1 and 3.2) are new, and the hand proofs for p≥7 in Lemma 3.2 are detailed and convincing — counting 4-cycles through a vertex and forcing the stabilizer to be trivial is a classic and appropriate technique.\n\nThe genuine soft spot is exactly what the reader flagged: Lemma 3.2 for p=3,5, Lemma 3.3 (nine small groups), and the connected Haar graphs of Q8×Z2 in Lemma 4.1 are asserted to be checked by Magma, but no code or output is included. These checks are load-bearing. Lemma 3.3 feeds directly into the exclusion of the order-16 groups in Lemma 4.1, and those exclusions feed the inductive subgroup argument in Lemma 4.2. If one row of the table is wrong, the list in Theorem 1.4 is wrong. That's a real risk in the manuscript as written.\n\nI don't think this is a fatal flaw. The finite cases are small enough to reimplement in GAP or Magma in an afternoon, and the table gives explicit presentations and S-sets. The paper's reliance on Proposition 2.3 from [10] is less worrying than the reader made it: it's a published structural result about the class BC, it provides the solvability and Sylow restrictions, and it's not the classification itself. The self-citation is heavy but the cited work is independent and prior.\n\nRecommendation: send it to a serious referee, and require the Magma code or a certification of the finite computations. If the code comes back clean, the paper is a clean, complete solution to an open problem. I'd cite it once it's published, and I'd put it on the reading list for anyone doing Cayley or Haar graphs.","headline":"Complete classification resolving Estelyi and Pisanski's 2016 problem; the theorem is likely right, but the referee should demand the Magma code behind the small-case checks.","tokens_in":16855,"tokens_out":2471,"would_cite":true,"duration_ms":22308,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05E18","20B25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every finite non-abelian group except five small exceptions has a Haar graph that is not a Cayley graph.","keywords":["Haar graph","Cayley graph","bi-Cayley graph","vertex-transitive graph","non-abelian group","graphical regular representation","2-group classification","classification"],"falsifier":"Take any non-abelian group not isomorphic to $D_6$, $D_8$, $D_{10}$, $Q_8$ or $Q_8 \\times \\mathbb{Z}_2$—for example the dihedral group of order 16—and enumerate all Haar graphs $H(H,S)$ with $1 \\in S$ up to isomorphism, checking for each whether it is a Cayley graph. The theorem predicts at least one non-Cayley Haar graph; exhibiting one such group with all Haar graphs Cayley would disprove the classification.","tokens_in":15832,"feed_emoji":"🕸️","tokens_out":9269,"duration_ms":83583,"temperature":0.7,"pith_summary":"This paper settles a classification question left open in 2016: which finite non-abelian groups have the property that every Haar graph is a Cayley graph? A Haar graph of a group $H$ is a bipartite graph made from two copies of $H$, with edges from $h_0$ to $(sh)_1$ determined by a subset $S \\subseteq H$. The answer is exactly five groups: the dihedral groups $D_6$, $D_8$, $D_{10}$, the quaternion group $Q_8$, and the direct product $Q_8 \\times \\mathbb{Z}_2$. Every other finite non-abelian group admits at least one Haar graph that is not a Cayley graph. Since abelian groups are already known to have the property, the theorem gives the complete boundary between the two classes of graphs.","feed_headline":"Only five non-abelian groups escape non-Cayley Haar graphs","feed_subtitle":"Complete classification: every other finite non-abelian group has a Haar graph that is not a Cayley graph.","key_machinery":"The load-bearing object is the class $BC$ of groups all of whose Haar graphs are Cayley graphs, together with the normalizer description of automorphisms of a connected Haar graph: $N_{\\mathrm{Aut}(\\Gamma)}(R(H))$ is either $R(H) \\rtimes F$ or $R(H)\\langle F, \\delta_{\\alpha,x,y}\\rangle$, depending on whether a certain set $I$ is empty. This description lets the authors force $R(H)$ to be the full automorphism group. The other engine is a structural reduction from an earlier paper: groups in $BC$ are solvable, have abelian Sylow $p$-subgroups for odd $p$, and contain a subgroup isomorphic to $D_6$, $D_8$, $D_{10}$ or $Q_8$. The classification then splits into non-abelian $2$-groups and non-abelian $\\{2,p\\}$-groups; in each case explicit connection sets $S$ are chosen so that counting $4$-cycles through the vertex $1_0$ forces the stabilizer of $1_0$ to be trivial and the graph to have two orbits.","core_discovery":"The central claim is the classification theorem: if $H$ is a finite non-abelian group and every Haar graph $H(H,S)$ is a Cayley graph, then $H$ is isomorphic to $D_6$, $D_8$, $D_{10}$, $Q_8$ or $Q_8 \\times \\mathbb{Z}_2$; conversely, each of these five groups does have the property. The proof proves the converse partly by a subgroup argument: a disconnected Haar graph over $Q_8 \\times \\mathbb{Z}_2$ splits into Cayley components, and connected ones are checked computationally; the dihedral cases come from the earlier dihedral classification. The necessity is shown by assuming a group in the class $BC$ and using a structural reduction to narrow it to non-abelian $2$-groups and non-abelian $\\{2,p\\}$-groups, then constructing, for every remaining candidate, a specific Haar graph whose automorphism group is exactly the right-translation group $R(H)$, so the graph has two orbits and cannot be a Cayley graph.","pith_inferences":["The connection sets used in the paper's constructions have at most eight elements, which suggests the obstruction to being Cayley is already present in small, local configurations rather than requiring large or elaborate connection sets.","A natural test of the classification is to enumerate all Haar graphs of every non-abelian group of order 16 or 32; the theorem predicts each has a non-Cayley Haar graph, so any group outside the five with all Haar graphs Cayley would pinpoint a gap in the structural reduction.","Because the proof makes the stabilizer $A_{1_0}$ trivial, a vertex-transitive non-Cayley Haar graph would have to come from a different mechanism, one where the automorphism group is larger than $R(H)$ but still lacks a regular subgroup."],"forward_implications":["For every finite non-abelian group outside the five listed, there is a concrete Haar graph that is not a Cayley graph, so non-Cayleyness is the rule rather than the exception among Haar graphs of non-abelian groups.","Combined with the known fact that every Haar graph of an abelian group is a Cayley graph, the theorem gives a complete dichotomy: a finite group has only Cayley Haar graphs exactly when it is abelian or is one of $D_6$, $D_8$, $D_{10}$, $Q_8$, $Q_8 \\times \\mathbb{Z}_2$.","The five exceptional groups have no Haar graph whose full automorphism group is isomorphic to the group itself, and the paper notes they are the only known non-abelian groups with no such Haar graph.","The non-Cayley Haar graphs constructed here are not vertex-transitive, so the same construction cannot produce vertex-transitive non-Cayley Haar graphs; the vertex-transitive version of the problem remains open."],"supporting_citations":[{"why":"Posed the classification problem and proved the dihedral case, giving the base cases $D_6$ and $D_{10}$ and the benchmark $D_{2n}$ result the new proof extends.","marker":"[9]"},{"why":"Provided the inner-abelian classification and the structural reduction (solvability, abelian odd Sylow subgroups, presence of $D_6$, $D_8$, $D_{10}$ or $Q_8$) that forms the backbone of the case analysis.","marker":"[10]"},{"why":"Supplied the automorphism description of bi-Cayley graphs and the normalizer decomposition used to identify $\\mathrm{Aut}(H(H,S))$ in the explicit constructions.","marker":"[28]"},{"why":"Introduced Haar graphs as voltage graphs of a dipole and fixed the terminology and basic setup used throughout the paper.","marker":"[15]"},{"why":"Gave earlier examples of Haar graphs over non-abelian groups that are not vertex-transitive, motivating the search for non-Cayley Haar graphs in full generality.","marker":"[22]"},{"why":"Provided the computational algebra system used to verify the finitely many small-order cases in Lemmas 3.2, 3.3 and 4.1.","marker":"[5]"},{"why":"Supplied the enumerations of groups of orders 16 and 32 that the 2-group part of Lemma 4.1 relies on.","marker":"[13]"}],"fun_headline_variants":["Non-Cayley Haar graphs for nearly all non-abelian groups","Five exceptions: non-abelian groups without non-Cayley Haar graphs","Haar graphs classify non-abelian groups: all but five","Non-abelian groups yield non-Cayley Haar graphs except five"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The case analysis rests on an earlier structural theorem saying that any group whose Haar graphs are all Cayley graphs is solvable, has abelian Sylow $p$-subgroups for every odd prime $p$, and contains a subgroup isomorphic to $D_6$, $D_8$, $D_{10}$ or $Q_8$; if that theorem failed, the reductions could miss groups.","fun_headline_variants_meta":{"raw":{"variants":["Non-Cayley Haar graphs for nearly all non-abelian groups","Five exceptions: non-abelian groups without non-Cayley Haar graphs","Haar graphs classify non-abelian groups: all but five","Non-abelian groups yield non-Cayley Haar graphs except five"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000656,"raw_usage":{"total_tokens":3007,"prompt_tokens":952,"completion_tokens":2055,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":1976}},"tokens_in":568,"tokens_out":2055,"duration_ms":14426,"temperature":1.0,"reasoning_tokens":1976,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:39:27.065364+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any non-abelian group not isomorphic to $D_6$, $D_8$, $D_{10}$, $Q_8$ or $Q_8 \\times \\mathbb{Z}_2$—for example the dihedral group of order 16—and enumerate all Haar graphs $H(H,S)$ with $1 \\in S$ up to isomorphism, checking for each whether it is a Cayley graph. The theorem predicts at least one non-Cayley Haar graph; exhibiting one such group with all Haar graphs Cayley would disprove the classification.","supporting_citations":[{"cited_title":"Est´ elyi and T","cited_arxiv_id":null,"evidence_quote":"Posed the classification problem and proved the dihedral case, giving the base cases $D_6$ and $D_{10}$ and the benchmark $D_{2n}$ result the new proof extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provided the inner-abelian classification and the structural reduction (solvability, abelian odd Sylow subgroups, presence of $D_6$, $D_8$, $D_{10}$ or $Q_8$) that forms the backbone of the case analysis."},{"cited_title":"Zhou and Y.-Q","cited_arxiv_id":null,"evidence_quote":"Supplied the automorphism description of bi-Cayley graphs and the normalizer decomposition used to identify $\\mathrm{Aut}(H(H,S))$ in the explicit constructions."},{"cited_title":"Hladnik, D","cited_arxiv_id":null,"evidence_quote":"Introduced Haar graphs as voltage graphs of a dipole and fixed the terminology and basic setup used throughout the paper."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gave earlier examples of Haar graphs over non-abelian groups that are not vertex-transitive, motivating the search for non-Cayley Haar graphs in full generality."},{"cited_title":"Bosma, C","cited_arxiv_id":null,"evidence_quote":"Provided the computational algebra system used to verify the finitely many small-order cases in Lemmas 3.2, 3.3 and 4.1."},{"cited_title":"Hall and J.K","cited_arxiv_id":null,"evidence_quote":"Supplied the enumerations of groups of orders 16 and 32 that the 2-group part of Lemma 4.1 relies on."}],"review_version":1}