{"id":"04fa367c-d5e0-460f-916f-797b8d6d2ffd","arxiv_id":"1908.08838","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every cyclic group is shown to have no NNN-graph: in every normal circulant, all regular subgroups isomorphic to the cyclic group are normal.","lead":"This paper proves that no cyclic group has the NNN property, meaning no Cayley graph of a cyclic group is simultaneously normal for one regular subgroup and non-normal for an isomorphic regular subgroup. The result closes a previously open question about which groups admit this unusual symmetry behavior.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.3 invokes Lemma 3.26, proved only for Z_{2^n}, to conclude non-normality for G=Z_{2^k}×B with odd B; the required composite-order bound is neither proved nor cited.","rationale":"The reader identified the same load-bearing point: Lemma 3.26 is a 2-group statement and is applied in Section 4 to cyclic groups with an odd factor. This is the weakest link in the proof of Theorem 1.3 because the divisibility-by-8 case relies on it to rule out NNN-graphs once a W-subgroup has been found. The surrounding structure is credible: Section 3 gives a detailed classification of regular subgroups of Hol(Z_{2^n}), and the reduction R=K×B in Section 4 is otherwise coherent. The gap is also easily localized and probably repairable, either by citing the thesis lemma mentioned in the introduction or by repeating the order-counting argument with |Hol(G)| replaced by 2^{2k1−1}|B|φ(|B|), which the factor of order 2 should dominate. Because the manuscript as written lacks that step, the reader's CONDITIONAL verdict is appropriate, and no further adjustment is needed.","tokens_in":28814,"tokens_out":20944,"duration_ms":214343,"concrete_test":"Check whether [25, Lemma 5.3.4] states that a circulant of an arbitrary cyclic group G with a proper W-subgroup relative to the connection set is not NNN for G. If it does, replace the invocation in the first case of Theorem 4.3 with that citation. If it does not, prove a composite-order version of Lemma 3.26: for G=Z_{2^{k1}}×B with B odd and a lexicographic product with one factor of order 2 and the other of order 2^{k1−1}|B|, show |Aut(X)|·|Aut(Y)|^{|X|} > |Hol(G)| = 2^{2k1−1}|B|φ(|B|). If this strict inequality fails for some k1≥3 and odd B, the contradiction in Theorem 4.3 is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4, proof of Theorem 4.3, first case where S=S0∪ S1, concludes that a lexicographic product of nontrivial circulants is non-normal for G by invoking Lemma 3.26. Lemma 3.26 is proved only for circulants of Z_{2^n}, with an order comparison against |Hol(Z_{2^n})|=2^{2n−1}. In Theorem 4.3, G=Z_{2^{k1}}×B with B odd, and the lexicographic product arises from the W-subgroup X={1,a^{2^{k1−1}}}; no proof or citation shows the analogous bound |Aut(X)|·|Aut(Y)|^{|X|} > |Hol(G)|. The introduction points to [25, Lemma 5.3.4] as the intended result for W-subgroups of arbitrary cyclic groups, but Section 4 does not invoke it. Without a composite-order analogue of the estimate leading to (20), the contradiction that Γ is non-normal for G is unsupported in the divisibility-by-8 case. This gap is likely repairable, since the lexicographic factor of order 2 makes the wreath-product contribution dominate |Hol(G)|, but the argument as written needs that repair or an explicit citation.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that no finite cyclic group has the NNN-property: for every cyclic group G, every circulant that is normal for G has no distinct regular subgroup isomorphic to G that is non-normal in its automorphism group. The proof splits into two cases. When the order of G is not divisible by 8, Section 2 shows that the automorphism group of a normal circulant has a unique abelian regular subgroup, and hence no NNN-graph exists. When 8 divides |G|, Section 3 classifies the regular subgroups of Hol(Z_{2^n}), identifies which cyclic regular subgroups are normal, and Section 4 uses this classification to reduce the general cyclic case to the 2-primary component. The final theorem, Theorem 1.3, states the result for all cyclic groups.","tokens_in":28998,"tokens_out":18637,"duration_ms":156862,"significance":"If the result is correct, it resolves a natural open case in the study of NNN-graphs and complements known results for elementary abelian 2-groups and CI-groups. The paper contains substantial independent technical contributions: a complete classification of regular subgroups of Hol(Z_{2^n}) (Theorem 1.4), a detailed semiregular element analysis (Section 3.2), and a normality criterion for cyclic regular subgroups (Theorem 3.24). These tools are likely to be useful beyond the NNN-property. The main result is a clean, falsifiable statement about all finite cyclic groups. The paper is not based on any fitted parameters or circular reasoning; the central claim is approached by a genuine case analysis built on prior theorems.","major_comments":[{"comment":"Lemma 3.26 is applied to a circulant of G = Z_{2^{k1}} × B with B odd, but Lemma 3.26 is proved only for the case G = Z_{2^n}. The proof of Lemma 3.26 compares |Aut(Γ)| with |Hol(Z_{2^n})| = 2^{2n-1}, whereas for the composite cyclic group G the required comparison is with |Hol(G)| = 2^{2k1-1} · |B| · |Aut(B)|, which is strictly larger when |B| > 1. The manuscript does not provide a proof or citation showing that the lexicographic product in Theorem 4.3 has more automorphisms than |Hol(G)|, so the contradiction that Γ is non-normal for G is unsupported as written. This is likely repairable: for the order-2 subgroup X, one may bound |Aut(Γ)| ≥ 2 · |Aut(Y)|² with |Aut(Y)| ≥ |G|/2, giving |Aut(Γ)| ≥ |G|²/2, and then note that |G|²/2 > |Hol(G)| for odd |B| > 1; however, the manuscript does not carry out this adjustment.","section":"Section 4, proof of Theorem 4.3, first case"},{"comment":"The proof of Lemma 3.26 asserts that a circulant has a regular automorphism group if and only if it is isomorphic to K2, and uses this to justify the strict inequality |Aut(Γ)| > 2^{n-t}(2^t)^{2^{n-t}}. This assertion is not correct: there exist circulant graphs on cyclic groups, including groups of order a power of 2, whose full automorphism group is regular (graphical regular representations, or GRRs). For order at least 16, such GRRs are known to exist for cyclic 2-groups. Consequently, when t = n-1 the right-hand side equals |Hol(Z_{2^n})| exactly, and the proof of Lemma 3.26 is incomplete as it stands. Since Lemma 3.26 is used in the main proof, this gap is load-bearing and requires repair.","section":"Lemma 3.26, inequality (20)"}],"minor_comments":[{"comment":"There is a typo in the sentence 'we have that the the only regular subgroups of the holomorph' — the word 'the' is duplicated.","section":"Page 3, second paragraph"},{"comment":"The phrase 'p1 is odd' in the lemma statement is not defined; it should be 'p1 is an odd prime' for clarity.","section":"Section 2, Lemma 2.4"},{"comment":"The term 'nontrivial circulant' is used without definition. In particular, it is unclear whether an edgeless circulant on two vertices (which has regular automorphism group) counts as nontrivial; this ambiguity is directly relevant to the strictness of inequality (20).","section":"Lemma 3.26 and Theorem 4.3"},{"comment":"In the proof of Theorem 3.17, the expression 'R/upsl⋊peR ∩ GR' appears garbled; this is likely a typesetting artifact, but the intended notation should be stated cleanly.","section":"Section 3, Theorem 3.17"},{"comment":"The paper cites [25, Lemma 5.3.4] as the result that a lexicographic product arising from a W-subgroup is not NNN for arbitrary cyclic groups, but Section 4 does not invoke this result. Either use it in Theorem 4.3 or explain why the 2-power version suffices.","section":"Introduction, paragraph on W-subgroups"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is plausible and the paper contains substantial original work, particularly the classification of regular subgroups of Hol(Z_{2^n}). The identified gaps are technical but load-bearing. The first issue (misapplication of Lemma 3.26 in Section 4) is likely fixable by adding a direct bound for the composite-order case. The second issue (the false claim about circulants with regular automorphism groups) is more serious because it affects the proof of Lemma 3.26 itself, not only its application. I recommend major revision, with careful attention to these two points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this paper proves that no cyclic group has the NNN-property, and the proof is credible. The main new work is the classification of regular subgroups of Hol(Z_{2^n}) in Theorem 1.4, a substantial technical achievement on its own. Section 2 handles the case 8∤|G| cleanly with centralizer arguments. Section 3 is the heart: a careful analysis of semiregular elements, then the classification. Section 4 assembles the cyclic case from the 2-primary part.\n\nThe soft spot is real but minor. In the proof of Theorem 4.3, the first case concludes that a lexicographic product is non-normal for G by invoking Lemma 3.26, which is proved only for circulants of Z_{2^n}. The group there is Z_{2^{k1}} × B with B odd. The introduction points to [25, Lemma 5.3.4] as the general W-subgroup result, but Section 4 does not cite it. The argument is repairable: the same counting bound works because for odd cyclic B we have |Aut(B)| < |B|, so the wreath factor still dominates |Hol(G)|. But as written, the case is not justified.\n\nThat is the only substantive issue I found. The citations look appropriate; the self-citations to the thesis lemma are used as independent input, not as a restatement of the theorem. No data or fitting concerns exist. The proof is long and mostly careful, with several genuinely independent lemmas.\n\nWho this is for: algebraic graph theorists working on Cayley graphs, normal and CI properties, and holomorphs. It settles a natural family and sharpens the boundary with elementary abelian 2-groups, where NNN-graphs do exist. The classification of regular subgroups of Hol(Z_{2^n}) will be cited independently of the main theorem.\n\nRecommendation: send it to a serious referee. The Section 4 gap should be fixed by a citation or a short proof, and then the result should go through. My own verdict is high confidence on the main theorem, conditional on that small repair.","headline":"A credible proof that cyclic groups lack the NNN-property, built on a substantial classification of regular subgroups of Hol(Z_{2^n}); one fixable gap in Section 4's use of Lemma 3.26.","tokens_in":29583,"tokens_out":4238,"would_cite":true,"duration_ms":41079,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C25","20B25","05E18"],"pacs":[],"model":"deepseek-v4-flash","headline":"Cyclic groups do not have the NNN-property: no normal circulant has an isomorphic non-normal regular subgroup.","keywords":["NNN-graphs","NNN-property","normal Cayley graphs","circulants","cyclic groups","regular subgroups","holomorph","Cayley graphs"],"falsifier":"Find a normal circulant $\\Gamma$ of a cyclic group $G = \\mathbb{Z}_{2^k} \\times B$ with $B$ odd and $k \\geq 4$ whose automorphism group contains the automorphism $y^{2^{k-4}}$ (the map $a_1 \\mapsto a_1^{5^{2^{k-4}}}$ fixing $B$). Theorem 4.3 asserts such a graph must be non-normal for $G$, so any concrete example would refute the theorem; for instance, a computer search over all inversion-closed connection sets of $\\mathbb{Z}_{48}$ could check whether any normal circulant has $y$ in its automorphism group.","tokens_in":28550,"feed_emoji":"🔄","tokens_out":8123,"duration_ms":78452,"temperature":0.7,"pith_summary":"Finite cyclic groups never give rise to NNN-graphs: if a circulant is normal for its cyclic defining group, then it has no second regular subgroup isomorphic to that same cyclic group sitting non-normally inside the automorphism group. The proof splits according to whether 8 divides the order. When 8 does not divide the order, a normal circulant has a unique abelian regular subgroup, so no NNN-graph can exist. When 8 does divide the order, the argument passes to the holomorph of the cyclic 2-group factor and classifies all regular subgroups there; the classification is strong enough to show that any subgroup that could serve as the non-normal copy forces the circulant to be non-normal after all.","feed_headline":"No cyclic group has an NNN-graph","feed_subtitle":"Proof splits on divisibility by 8 and classifies all regular subgroups of the cyclic holomorph.","key_machinery":"The central object is the holomorph $\\mathrm{Hol}(G) = G_R \\rtimes \\mathrm{Aut}(G)$, viewed as a permutation group on $G$; whenever $\\Gamma$ is normal for $G$, $\\mathrm{Aut}(\\Gamma)$ is a subgroup of $\\mathrm{Hol}(G)$, so every regular subgroup of $\\mathrm{Aut}(\\Gamma)$ is a regular subgroup of $\\mathrm{Hol}(G)$. For $G = \\mathbb{Z}_{2^n}$, Theorem 1.4 gives a complete classification of those regular subgroups up to conjugacy: the right-regular group $G_R$, cyclic subgroups $\\langle a y^{2^t}\\rangle$, and the dihedral, quaternion, quasidihedral, and $M_n(2)$ groups. The other load-bearing device is the lemma that a circulant that is a lexicographic product of two nontrivial circulants has an automorphism group strictly larger than $\\mathrm{Hol}(\\mathbb{Z}_{2^n})$, so it cannot be normal; this converts the presence of W-subgroups into non-normality.","core_discovery":"The paper's central claim is Theorem 1.3: cyclic groups do not have the NNN-property. Concretely, for every finite cyclic group $G$, every circulant $\\Gamma = \\mathrm{Cay}(G,S)$ that is normal for $G$ has no regular subgroup $H$ with $H \\cong G$, $H \\neq G_R$, and $H$ not normal in $\\mathrm{Aut}(\\Gamma)$. The proof first handles $|G|$ not divisible by 8 via a uniqueness result for abelian regular subgroups, then for $|G|$ divisible by 8 classifies the regular subgroups of $\\mathrm{Hol}(\\mathbb{Z}_{2^n})$ (Theorem 1.4), determines which cyclic regular subgroups are normal in the holomorph (Theorem 3.24), and rules out the remaining candidates by showing that the automorphisms they force into $\\mathrm{Aut}(\\Gamma)$ would make $\\Gamma$ a lexicographic product, hence non-normal.","pith_inferences":["A natural extension not pursued here would be to ask whether every group with cyclic Sylow 2-subgroup fails the NNN-property, since the obstruction in this paper lives entirely in the 2-part of the group.","One could test the pressure point computationally: enumerate all circulants of $\\mathbb{Z}_{48}$ (or other $\\mathbb{Z}_{2^k} \\times B$ with odd $B$) and check whether any normal circulant has $y^{2^{k-4}} \\in \\mathrm{Aut}(\\Gamma)$; Theorem 4.3 predicts none exists.","The classification in Theorem 1.4 may be reusable for the isomorphism problem of circulant digraphs, because it lists all possible regular groups that can appear inside the automorphism group of a normal circulant whose order is divisible by 8."],"forward_implications":["For cyclic groups of order not divisible by 8, a normal circulant has exactly one abelian regular subgroup, so the normal/non-normal regular-subgroup problem cannot even arise for such graphs.","For cyclic groups of order divisible by 8, the classification reduces the NNN-check to seven explicit conjugacy classes; any NNN candidate would have to be of the cyclic type $\\langle a y^{2^t}\\rangle$, and the proof shows that candidate is either normal or forces the graph to be non-normal.","As a direct corollary, every regular subgroup of a normal circulant that is isomorphic to the defining cyclic group is normal in the automorphism group.","The NNN phenomenon, if it exists at all for cyclic groups, cannot appear; the known examples of NNN-graphs therefore remain confined to non-cyclic groups.","The theorem settles the cyclic case of the question whether a Cayley graph can be simultaneously normal for one regular group and non-normal for an isomorphic regular group."],"supporting_citations":[{"why":"Supplies the theorem that a proper W-subgroup makes a circulant a lexicographic product, and the lemma that this cannot happen for cyclic 2-groups; it is used in Lemmas 3.26 and 3.27 and in Theorem 4.3.","marker":"[13]"},{"why":"Gives the uniqueness of regular subgroups isomorphic to $G$ inside $\\mathrm{Hol}(G)$ for abelian groups of order not divisible by 8, which underlies Theorem 2.8.","marker":"[21]"},{"why":"Provides the lemma that a W-subgroup forces a graph not to be NNN, along with background facts on normal circulants used throughout Sections 2 and 4.","marker":"[25]"},{"why":"Gives the earlier normal-circulant result with noncyclic regular subgroups that Theorem 2.7 generalizes to all cyclic groups.","marker":"[16]"},{"why":"Defines normal Cayley graphs and gives the automorphism-group decomposition $\\mathrm{Aut}(\\Gamma) = G_R \\rtimes \\mathrm{Aut}(G,S)$ used throughout the proof.","marker":"[22]"}],"fun_headline_variants":["Cyclic groups have no NNN-graphs","NNN-property fails for all cyclic groups","Cyclic groups: NNN-graph existence impossible","No cyclic Cayley graph is both normal and non-normal","Cyclic groups dodge the NNN-property"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes, without a separate proof or citation, that the lower bound on the automorphism-group size of a lexicographic product of circulants, established for $\\mathbb{Z}_{2^n}$, continues to hold for cyclic groups that also contain odd prime factors.","fun_headline_variants_meta":{"raw":{"variants":["Cyclic groups have no NNN-graphs","NNN-property fails for all cyclic groups","Cyclic groups: NNN-graph existence impossible","No cyclic Cayley graph is both normal and non-normal","Cyclic groups dodge the NNN-property"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000623,"raw_usage":{"total_tokens":2804,"prompt_tokens":782,"completion_tokens":2022,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":398,"completion_tokens_details":{"reasoning_tokens":1946}},"tokens_in":398,"tokens_out":2022,"duration_ms":14022,"temperature":1.0,"reasoning_tokens":1946,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:29:39.767513+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a normal circulant $\\Gamma$ of a cyclic group $G = \\mathbb{Z}_{2^k} \\times B$ with $B$ odd and $k \\geq 4$ whose automorphism group contains the automorphism $y^{2^{k-4}}$ (the map $a_1 \\mapsto a_1^{5^{2^{k-4}}}$ fixing $B$). Theorem 4.3 asserts such a graph must be non-normal for $G$, so any concrete example would refute the theorem; for instance, a computer search over all inversion-closed connection sets of $\\mathbb{Z}_{48}$ could check whether any normal circulant has $y$ in its automorphism group.","supporting_citations":[{"cited_title":"On Cayley digraphs on nonisomorphic 2-groups","cited_arxiv_id":null,"evidence_quote":"Supplies the theorem that a proper W-subgroup makes a circulant a lexicographic product, and the lemma that this cannot happen for cyclic 2-groups; it is used in Lemmas 3.26 and 3.27 and in Theorem 4.3."},{"cited_title":"On the multiple holomorph of a finite almost simple group","cited_arxiv_id":"1904.09754","evidence_quote":"Gives the uniqueness of regular subgroups isomorphic to $G$ inside $\\mathrm{Hol}(G)$ for abelian groups of order not divisible by 8, which underlies Theorem 2.8."},{"cited_title":"Normal and non-normal cayley graphs","cited_arxiv_id":null,"evidence_quote":"Provides the lemma that a W-subgroup forces a graph not to be NNN, along with background facts on normal circulants used throughout Sections 2 and 4."},{"cited_title":"Normal circulant graphs with noncyclic regular subgroups","cited_arxiv_id":null,"evidence_quote":"Gives the earlier normal-circulant result with noncyclic regular subgroups that Theorem 2.7 generalizes to all cyclic groups."},{"cited_title":"Automorphism groups and isomorphisms of Cayley digraphs","cited_arxiv_id":null,"evidence_quote":"Defines normal Cayley graphs and gives the automorphism-group decomposition $\\mathrm{Aut}(\\Gamma) = G_R \\rtimes \\mathrm{Aut}(G,S)$ used throughout the proof."}],"review_version":1}